NOTICE: By continued use of this site you understand and agree to the binding Terms of Service and Privacy Policy.
// ==UserScript==
// @namespace https://openuserjs.org/users/preciousmouse
// @name dashi solution
// @description auto solve dashi problem
// @author preciousmouse
// @copyright 2020, preciousmouse (https://openuserjs.org/users/preciousmouse)
// @license MIT
// @version 1.7
// @updateURL https://openuserjs.org/meta/preciousmouse/dashi_solution.user.js
// @downloadURL https://openuserjs.org/install/preciousmouse/dashi_solution.user.js
// @supportURL https://github.com/puzzle-resolution/dashi
// @require https://cdnjs.cloudflare.com/ajax/libs/babel-standalone/6.18.2/babel.js
// @require https://cdnjs.cloudflare.com/ajax/libs/babel-polyfill/6.16.0/polyfill.js
// @require http://requirejs.org/docs/release/2.1.5/comments/require.js
// @include https://cn.puzzle-bridges.com/
// @include https://cn.puzzle-bridges.com/?*
// @grant none
// ==/UserScript==
// ==OpenUserJS==
// @author preciousmouse
// ==/OpenUserJS==
console.log("dashi solution. set 'window.useRobot = false' to disable auto submiting.")
window.useRobot = true;
function replaceAnswer(answer) {
if (document && $) {
$('#puzzleForm').attr('onsubmit', `console.log('customer onsubmit');
Game.saveState();
Game.tickTimer();
this.jstimerPersonal.value = Game.getTimer();
this.ansH.value = '${answer}';`);
$("#btnReady").off("click"); //卸载post提交答案方法，绕过Game组件逻辑
window.useRobot && $("#robot").attr('value', '1');
}
}
function submitAnswer() {
var _a;
(_a = document.querySelector('#btnReady')) === null || _a === void 0 ? void 0 : _a.click();
}
//向量ab和ac叉乘
function cross(a, b, c) {
return (b.row - a.row) * (c.col - a.col) - (b.col - a.col) * (c.row - a.row);
}
//计算几何，判断两线段是否相交（T型此处认为不相交）
function intersection(l1, l2) {
const a = l1.p, b = l1.q, c = l2.p, d = l2.q;
//快速排斥
if (Math.min(a.row, b.row) > Math.max(c.row, d.row)
|| Math.min(a.col, b.col) > Math.max(c.col, d.col)
|| Math.min(c.row, d.row) > Math.max(a.row, b.row)
|| Math.min(c.col, d.col) > Math.max(a.col, b.col)) {
return false;
}
//跨立实验
const h = cross(a, b, c);
const i = cross(a, b, d);
const j = cross(d, c, a);
const k = cross(d, c, b);
return h * i < 0 && j * k < 0;
}
class Hashi {
constructor(points) {
this.points = points;
this.nearestPointMap = this.initNearestPoints(this.points);
}
initNearestPoints(task) {
var _a, _b;
let rows = {}, columns = {};
for (let p of task) {
if (rows[p.row] === undefined) {
rows[p.row] = {};
}
rows[p.row][p.col] = p;
if (columns[p.col] === undefined) {
columns[p.col] = {};
}
columns[p.col][p.row] = p;
}
// let map: { [key in string]: Partial<{ top: string; bottom: string; left: string; right: string; }> } = {};
let map = {};
for (let p of task) {
const row = rows[p.row];
const rowKeys = Object.keys(row);
const pRowIndex = rowKeys.indexOf(p.col.toString());
const col = columns[p.col];
const colKeys = Object.keys(col);
const pColIndex = colKeys.indexOf(p.row.toString());
map[p.index] = {
// top: getPointMapKey(col[pColIndex - 1]),
// bottom: getPointMapKey(col[pColIndex + 1]),
// left: getPointMapKey(row[pRowIndex - 1]),
// right: getPointMapKey(row[pRowIndex + 1]),
bottom: (_a = Object.values(col)[pColIndex + 1]) === null || _a === void 0 ? void 0 : _a.index,
right: (_b = Object.values(row)[pRowIndex + 1]) === null || _b === void 0 ? void 0 : _b.index,
};
}
return map;
}
checkBridge(array) {
for (const { p, q } of array) {
if (p.row == q.row && p.col == q.col) {
throw new Error(`error while checkBridge: p、q 是同一点. ${JSON.stringify(array)}. 异常点对: ${JSON.stringify([p, q])}`);
}
if (p.row != q.row && p.col != q.col) {
throw new Error(`error while checkBridge: p、q 不在同一水平或竖直方向. ${JSON.stringify(array)}. 异常点对: ${JSON.stringify([p, q])}`);
}
if ((p.row == q.row && p.col > q.col) || (p.col == q.col && p.row > q.row)) {
throw new Error(`error while checkBridge: p、q 顺序错位. ${JSON.stringify(array)}. 异常点对: ${JSON.stringify([p, q])}`);
}
}
}
newBridge(p1, p2, count) {
this.checkBridge([{ p: p1, q: p2 }]);
let [p, q] = p1.row < p2.row ? [p1, p2] : p1.row > p2.row ? [p2, p1] : p1.col < p2.col ? [p1, p2] : [p2, p1];
return { p: Object.assign({}, p), q: Object.assign({}, q), count };
}
bridgeIsAvaliable(bridge, selectedBridge) {
// checkBridge([bridge, ...data.selectedBridge.values()]);
this.checkBridge([bridge]);
for (let b of selectedBridge.values()) {
if (intersection(bridge, b)) {
return false;
}
}
return true;
}
getAvaliableBridge(data) {
// console.log('getAvaliableBridge', data.currentPointIndex, { ...data });
const { points, nearestPointMap } = this;
const { currentPointIndex, selectedBridge, currentPointStatus } = data;
const p = points[currentPointIndex];
const p_status = currentPointStatus[currentPointIndex];
let res = [undefined, undefined];
const { bottom, right } = nearestPointMap[p.index];
if (bottom && p_status < +p.number) {
const b_p = points[bottom];
const b_p_status = currentPointStatus[bottom];
if (b_p_status < +b_p.number) {
const bridge = this.newBridge(p, b_p, Math.min(2, +p.number - p_status, +b_p.number - b_p_status));
this.bridgeIsAvaliable(bridge, selectedBridge) && (res[0] = bridge);
}
}
if (right && p_status < +p.number) {
const r_p = points[right];
const r_p_status = currentPointStatus[right];
if (r_p_status < +r_p.number) {
const bridge = this.newBridge(p, r_p, Math.min(2, +p.number - p_status, +r_p.number - r_p_status));
this.bridgeIsAvaliable(bridge, selectedBridge) && (res[1] = bridge);
}
}
return res;
}
getBridgeCases(avaliableBridges, restCount) {
const cases = {
[0]: [],
[1]: [1, 3],
[2]: [2, 4, 6],
[3]: [5, 7],
[4]: [8],
[5]: [8],
[6]: [8],
[7]: [8],
[8]: [8],
}[restCount];
const [bottom, right] = avaliableBridges;
return cases.map(c => ({
[1]: right && right.count >= 1
? [undefined, right && this.newBridge(right.p, right.q, 1)]
: [undefined, undefined],
[2]: right && right.count >= 2
? [undefined, right && this.newBridge(right.p, right.q, 2)]
: [undefined, undefined],
[3]: bottom && bottom.count >= 1
? [bottom && this.newBridge(bottom.p, bottom.q, 1), undefined]
: [undefined, undefined],
[4]: bottom && bottom.count >= 1 && right && right.count >= 1
? [bottom && this.newBridge(bottom.p, bottom.q, 1), right && this.newBridge(right.p, right.q, 1)]
: [undefined, undefined],
[5]: bottom && bottom.count >= 1 && right && right.count >= 2
? [bottom && this.newBridge(bottom.p, bottom.q, 1), right && this.newBridge(right.p, right.q, 2)]
: [undefined, undefined],
[6]: bottom && bottom.count >= 2
? [bottom && this.newBridge(bottom.p, bottom.q, 2), undefined]
: [undefined, undefined],
[7]: bottom && bottom.count >= 2 && right && right.count >= 1
? [bottom && this.newBridge(bottom.p, bottom.q, 2), right && this.newBridge(right.p, right.q, 1)]
: [undefined, undefined],
[8]: bottom && bottom.count >= 2 && right && right.count >= 2
? [bottom && this.newBridge(bottom.p, bottom.q, 2), right && this.newBridge(right.p, right.q, 2)]
: [undefined, undefined],
}[c])).filter(c => !(c[0] === undefined && c[1] === undefined));
}
verificate(data) {
// console.warn('verificate1', { ...data });
const { points } = this;
const { currentPointStatus, selectedBridge } = data;
//判断所有节点count是否完成
for (const [index, point] of points.entries()) {
if (+point.number !== currentPointStatus[index]) {
// console.log('节点未完成');
return false;
}
}
// console.log('节点已完成');
//并查集 判断节点是否全连通
const set = Array.from(new Array(points.length).keys());
const findSet = (v) => {
let t1, t2 = v;
while (v != set[v])
v = set[v];
while (t2 != set[t2]) {
t1 = set[t2];
set[t2] = v;
t2 = t1;
}
return v;
};
const unionSet = (a, b) => {
const a1 = findSet(a), b1 = findSet(b);
if (a1 != b1) {
set[a1] = b1;
}
};
//初始化bridge连接
for (const b of selectedBridge.values()) {
unionSet(b.p.index, b.q.index);
}
//统计集合数
const counts = Array.from(new Array(points.length).keys()).filter(i => findSet(i) == i).length;
return counts === 1;
}
recu(data) {
// console.warn('recu1', data.currentPointIndex, { ...data });
const { points, nearestPointMap } = this;
const { currentPointIndex, selectedBridge, currentPointStatus } = data;
if (currentPointIndex == points.length) { //递归边界
// console.log('到达递归边界');
if (this.verificate(data))
return data;
else
return false;
}
const point = points[currentPointIndex];
const avaliableBridges = this.getAvaliableBridge(data);
// console.log('avaliableBridges', avaliableBridges);
if (avaliableBridges[0] === undefined && avaliableBridges[1] === undefined) {
if (+point.number == currentPointStatus[currentPointIndex]) {
return this.recu({ currentPointIndex: currentPointIndex + 1, selectedBridge: new Map(selectedBridge), currentPointStatus: [...currentPointStatus] });
}
else {
return false;
} //若无可用边，但节点count未完成，则返回失败
}
else {
const p_status = currentPointStatus[currentPointIndex];
const p_rest_count = +point.number - p_status;
const cases = this.getBridgeCases(avaliableBridges, p_rest_count);
// console.log('bridge cases', cases);
for (const c of cases) {
// console.log('执行case', c);
const [bottom, right] = c;
const nextSelectedBridge = new Map(selectedBridge);
let nextCurrentPointStatus = [...currentPointStatus];
if (bottom) {
nextSelectedBridge.set(`${bottom.p.index}_${bottom.q.index}`, bottom);
nextCurrentPointStatus[bottom.p.index] += bottom.count;
nextCurrentPointStatus[bottom.q.index] += bottom.count;
}
if (right) {
nextSelectedBridge.set(`${right.p.index}_${right.q.index}`, right);
nextCurrentPointStatus[right.p.index] += right.count;
nextCurrentPointStatus[right.q.index] += right.count;
}
const res = this.recu({ currentPointIndex: currentPointIndex + 1, selectedBridge: nextSelectedBridge, currentPointStatus: nextCurrentPointStatus });
if (res) {
return res;
}
}
return false;
}
}
solve() {
const result = this.recu({
currentPointIndex: 0,
selectedBridge: new Map(),
currentPointStatus: Array(this.points.length).fill(0),
});
// console.log('result', result, result && JSON.stringify([...result.selectedBridge.entries()]));
return (this.answer = (result ? this.generaterAnawer(result.selectedBridge) : ''));
}
generaterAnawer(selectedBridge) {
return [...selectedBridge.values()]
.sort((a, b) => (a.p.index == b.p.index ? (a.q.index == b.q.index ? 0
: a.q.index < b.q.index ? -1 : 1) : (a.p.index < b.p.index ? -1 : 1)))
.map(b => `${b.p.col},${b.p.row},${b.q.col},${b.q.row},${b.count}`)
.join(';');
}
}
function registerWorkerWithBlob(config) {
const { scriptStr, postMessageStr, onMessage } = config;
const blob = new Blob([scriptStr], { type: 'text/javascript' });
const url = URL.createObjectURL(blob);
const worker = new Worker(url);
worker.onmessage = onMessage;
worker.postMessage(postMessageStr);
}
(() => {
const puzzleWidth = {
0: 7, 1: 7, 2: 7,
3: 10, 4: 10, 5: 10,
6: 15, 7: 15, 8: 15,
9: 25, 10: 25, 11: 25,
13: 30, 12: 30, 14: 40,
}[+Object.fromEntries([...new URL(location.href).searchParams]).size || 0];
const taskKey = task; //test
const tasks = ( Game.task);
console.log('task', taskKey, tasks);
const onmessage = (e) => {
const tasks = JSON.parse(e.data);
const hashi = new Hashi(tasks);
const answer = hashi.solve();
postMessage(answer);
};
//此处采用hack写法，需要写进所有依赖函数
const scriptStr = `
cross=${cross.toString()}
intersection=${intersection.toString()}
${Hashi.toString()}
onmessage=${onmessage.toString()}
`;
const timer1 = new Date;
registerWorkerWithBlob({
scriptStr,
postMessageStr: JSON.stringify(tasks),
onMessage: (e) => {
const timer2 = new Date;
const answer = e.data;
console.log('answer', answer);
console.log('耗时', timer2.valueOf() - timer1.valueOf(), 'ms');
replaceAnswer(answer);
window.submit = submitAnswer;
window.useRobot && submitAnswer();
}
});
})();