Skip to content

Instantly share code, notes, and snippets.

@sasha240100
Last active April 27, 2018 12:50
Show Gist options
  • Save sasha240100/28d82c4e96597d3c51cc204aa55e8c92 to your computer and use it in GitHub Desktop.
Save sasha240100/28d82c4e96597d3c51cc204aa55e8c92 to your computer and use it in GitHub Desktop.
function isSquare(a, b) {
return Math.sqrt(a + b) % 1 === 0;
}
function remove_pair(a, b, _pairs) {
_pairs[a] = _pairs[a].filter(s => s !== b);
_pairs[b] = _pairs[b].filter(s => s !== a);
}
const clone = (obj) => JSON.parse(JSON.stringify(obj));
function square_sums_row(n) {
const pairs = {};
let arr = [];
let all_seq = [];
for (let i = 1; i <= n; i++) {
arr[i - 1] = i;
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (isSquare(arr[i], arr[j])) {
if (pairs[arr[i]]) {
pairs[arr[i]].push(arr[j]);
} else {
pairs[arr[i]] = [arr[j]];
}
}
}
}
for (let j = 0; j < n; j++) {
const cloned_pairs = clone(pairs);
const seq = [];
seq[0] = arr[j];
function addSeq(start = 1, _seq, offset = 0) {
let i = start;
while (true) {
const prev = _seq[i - 1];
let maybe_next = cloned_pairs[prev];
let next = maybe_next[offset];
if (offset === 0 && maybe_next.length > 1) {
for (let k = 1; k < maybe_next.length; k++) {
addSeq(_seq.length, clone(_seq), k);
}
}
offset = 0;
if (!next) break;
_seq[i] = next;
remove_pair(prev, _seq[i], cloned_pairs);
i++;
}
for (let l = 0; l < _seq.length; l++) {
if (_seq.indexOf(_seq[l]) !== l)
_seq.splice(l, 1);
}
all_seq.push(_seq);
}
addSeq(1, seq);
}
all_seq.sort((a1, a2) => a1.length > a2.length);
return all_seq[all_seq.length - 1];
}
console.log(square_sums_row(15));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment