Skip to content

Instantly share code, notes, and snippets.

@fluffywaffles
Created October 30, 2015 04:56
Show Gist options
  • Save fluffywaffles/ebe13645d0b449c882bb to your computer and use it in GitHub Desktop.
Save fluffywaffles/ebe13645d0b449c882bb to your computer and use it in GitHub Desktop.
var T = [
[ 1, 2, 3 ],
[ 2, 2, 2 ],
[ 3, 2, 1 ]
]
var symbols = [ 1, 2, 3 ]
function translateToProduct (k, i, ps) {
// i says where to start partitioning
// k says how many partitions
var a = 0, b = 1, c = 2, d = 4
, ab = k
while (ab > 0) {
if ( i % 2 == 1 ) {
T [a] [ T [b] [c] ]
T [ T [a] [b] ] [c]
} else {
T [ T [a] [b] ] [ T [c] [d] ]
T [ T [a] [ T [b] [c] ] ] [d]
T [a] [ T [ T [b] [c] ] [d] ]
}
}
return t_pos
}
function canMakeProduct (ps, t) {
var n = ps.length
, k_max = n / 2
, memo = []
, i, k
memo[n] = []
for (i = 0; i < n; i ++) {
memo[n].push(0)
memo[i] = [ 0 ]
}
for (i = n - 1; i >= 0; i--) {
for (k = 0; k < n; k ++) {
var t_pos = translateToProduct(k, i, ps)
if (t_pos == t) {
memo[i][k] = 1
} else {
memo[i][k] = (memo[i + 1][k] || memo[i][k - 1]) ? 1 : 0
}
}
}
console.log(memo)
return memo[0][n - 1]
}
canMakeProduct([ 1, 2, 3 ], 3)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment