Created
August 18, 2017 03:25
-
-
Save erantapaa/0ce4d426578230b8efe192b1224259f0 to your computer and use it in GitHub Desktop.
Daily Programmer 326
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Code to solve Daily Programmer problem 326 - Multifaceted Alphabet Blocks | |
var fs = require("fs") | |
var contents = fs.readFileSync('real_words.txt').toString(); | |
var all_words = contents.split(/\s+/) | |
nwords = all_words.length | |
console.log("nwords:", nwords) | |
// return a histogram of an array of words | |
function compute_hwords(words) { | |
var hwords = [] | |
for (var i = 0; i < words.length; ++i) { | |
var hw = Array(26).fill(0) | |
for (var j = 0; j < words[i].length; ++j) { | |
var ch = words[i].charCodeAt(j) | |
hw[ch-97]++ | |
} | |
hwords.push(hw) | |
} | |
return hwords | |
} | |
function lpad(s, n) { | |
s = "" + s | |
if (s.length < n) { | |
return " ".repeat(n - s.length) + s | |
} else { | |
return s | |
} | |
} | |
// convert a string to an array of blocks | |
function to_blocks(str) { | |
var arr = str.split(/\s+/) | |
blocks = [] | |
for (var i = 0; i < arr.length; ++i) { | |
var blk = [] | |
for (var j = 0; j < arr[i].length; ++j) { | |
blk.push( arr[i].charCodeAt(j) - 97 ) | |
} | |
blocks.push(blk) | |
} | |
return blocks | |
} | |
function show_blocks(blocks) { | |
var rows = [] | |
for (var i = 0; i < blocks.length; ++i) { | |
var row = [] | |
for (var j = 0; j < blocks[i].length; ++j) { | |
row.push( String.fromCharCode(97+blocks[i][j]) ) | |
} | |
rows.push( row.join('') ) | |
} | |
return rows | |
} | |
function show_blocks_optimized(blocks) { | |
var rows = [] | |
for (var i = 0; i < blocks.length; ++i) { | |
var row = [] | |
for (var j = 0; j < blocks[i].length; ++j) { | |
row.push( String.fromCharCode(97+blocks[i][j]) ) | |
} | |
rows.push( row.sort().join('') ) | |
} | |
return rows | |
} | |
// base pick on the most frequent letter | |
function most_frequent(hwords, n, s, used, mark, solved) { | |
var hcount = Array(26).fill(0) | |
var nwords = hwords.length | |
for (var i = 0; i < nwords; ++i) { | |
if (!mark[i]) { | |
for (var ch = 0; ch < 26; ++ch) { | |
hcount[ch] += hwords[i][ch] | |
} | |
} | |
} | |
// find the most frequent letter | |
var best = -1 | |
var best_count = -1 | |
for (var ch = 0; ch < 26; ++ch) { | |
if ((!used[ch]) && (hcount[ch] > best_count)) { | |
best = ch | |
best_count = hcount[ch] | |
} | |
} | |
if (best_count <= 0) { | |
return -1; // signal no more letters | |
} | |
return best | |
} | |
function solve(words, pickfn) { | |
var hwords = compute_hwords(words) | |
var solved = Array(nwords).fill(0) // words which have solutions | |
var blocks = [] | |
var total_removed = 0 | |
var n = 1 | |
loop1: | |
for (n = 1; ; ++n) { | |
// solve for block n | |
if (blocks[n-1] === undefined) { | |
blocks[n-1] = [] | |
} | |
// console.log("n = " + n + " blocks: ", blocks) | |
var used = Array(26).fill(0) // letters used in this block | |
var mark = Array(nwords).fill(0) // words used in this block | |
for (var s = 0; s < n; ++s) { | |
var ch = pickfn(hwords, n, s, used, mark, solved) | |
if (ch < 0) { | |
if (s == 0) { | |
break loop1 | |
} else { | |
break | |
} | |
} | |
blocks[n-1][s] = ch | |
used[ch] = 1 | |
// Remove from histogram | |
for (var i = 0; i < nwords; ++i) { | |
if (!mark[i] && hwords[i][ch]) { | |
hwords[i][ch]-- | |
mark[i] = 1 | |
} | |
} | |
var removed = 0 | |
for (var i = 0; i < nwords; ++i) { | |
if (!solved[i]) { | |
var sol = find_cover(blocks, 0, words[i], "") | |
if (!(sol === null)) { | |
for (var ch = 0; ch < 26; ++ch) { | |
hwords[i][ch] = 0 | |
} | |
solved[i] = 1 | |
removed++ | |
} | |
} | |
} | |
if (removed > 0) { | |
total_removed += removed | |
console.log("n: " + lpad(n, 2) + " s: " + lpad(s, 2) + " removed: " + lpad(removed,5) + " total: " + lpad(total_removed,5)) | |
} | |
} | |
} | |
if (blocks.length && blocks[blocks.length-1].length == 0) { | |
blocks.pop() | |
} | |
return blocks | |
} | |
function find_cover(blocks, b, word, path) { | |
if (word.length == 0) { | |
return path + ('.'.repeat(blocks.length - b)) | |
} | |
if (b >= blocks.length) { | |
return null | |
} | |
if (blocks.length - b < word.length) { | |
return null | |
} | |
var blen = blocks[b].length | |
for (var i = 0; i < blen; ++i) { | |
var ch = String.fromCharCode( 97 + blocks[b][i] ) | |
var j = word.indexOf(ch) | |
if (j >= 0) { | |
var word2 = word.substring(0, j) + word.substring(j+1) | |
var sol = find_cover(blocks, b+1, word2, path + ch) | |
if (!(sol === null)) { | |
return sol | |
} | |
} | |
} | |
return find_cover(blocks, b+1, word, path+".") | |
} | |
function compute_solutions(blocks, words) { | |
var nwords = words.length | |
var solution = Array(nwords).fill(null) | |
for (var i = 0; i < nwords; ++i) { | |
var sol = find_cover(blocks, 0, words[i], "") | |
solution[i] = sol | |
} | |
return solution | |
} | |
function compute_solutions2(blocks, words, maxbad) { | |
var nwords = words.length | |
var solution = Array(nwords).fill(null) | |
var nbad = 0 | |
for (var i = 0; i < nwords; ++i) { | |
var sol = find_cover(blocks, 0, words[i], "") | |
solution[i] = sol | |
if (sol === null) { | |
nbad++ | |
if (nbad >= maxbad) { | |
return null | |
} | |
} | |
} | |
return { solution: solution, nbad: nbad } | |
} | |
function make_solution(blocks, words) { | |
var solution = compute_solutions(blocks, words) | |
var nbad = 0 | |
for (var i = 0; i < solution.length; ++i) { | |
if (solution[i] === null) { | |
nbad++ | |
} | |
} | |
best = { blocks: blocks, solution: solution, nbad: nbad, words: words } | |
return best | |
} | |
// return a new block array with a character replaced | |
function replace_block_char(blocks, n, s, ch) { | |
var newblocks = blocks.slice() | |
newblocks[n] = blocks[n].slice() | |
newblocks[n][s] = ch | |
return newblocks | |
} | |
function try_replace(best, n, s, ch) { | |
if (best.blocks[n][s] == ch) { | |
return best | |
} | |
var oldch = String.fromCharCode(97+best.blocks[n][s]) | |
var others = "" // the other characters in the block | |
for (var i = 0; i < best.blocks[n].length; ++i) { | |
if (i != s) { | |
others += String.fromCharCode(97+best.blocks[n][i]) | |
} | |
} | |
var newch = String.fromCharCode(97+ch) | |
if (others.indexOf(newch) >= 0) { | |
// replacing character with another one in the same block | |
return best | |
} | |
var blocks = replace_block_char(best.blocks, n, s, ch) | |
var nwords = best.words.length | |
var solution = Array(nwords).fill(null) | |
var nbad = 0 | |
// first iterate over the bad words | |
for (var i = 0; i < nwords; ++i) { | |
if (best.solution[i] === null) { | |
var sol = find_cover(blocks, 0, best.words[i], "") | |
solution[i] = sol | |
if (sol === null) { | |
nbad++ | |
if (nbad >= best.nbad) { | |
return best | |
} | |
} | |
} | |
} | |
// then iterate over the other words | |
for (var i = 0; i < nwords; ++i) { | |
if (best.solution[i] === null) | |
continue | |
if (best.solution[i].charAt(n) == oldch) { | |
var sol = find_cover(blocks, 0, best.words[i], "") | |
solution[i] = sol | |
if (sol === null) { | |
nbad++ | |
if (nbad >= best.nbad) { | |
return best | |
} | |
} | |
} else { | |
solution[i] = best.solution[i] | |
} | |
} | |
return { blocks: blocks | |
, solution: solution | |
, nbad: nbad | |
, words: best.words | |
} | |
} | |
function show_best(best, one_line) { | |
console.log("blocks: " + best.blocks.length + " nbad: " + best.nbad) | |
var sep = one_line ? " / " : "\n" | |
console.log( show_blocks_optimized(best.blocks).join(sep) ) | |
} | |
// apply f until best.nbad doesn't change | |
function fix_nbad(f) { | |
return function(best) { | |
var k | |
for (k = 1; ; ++k) { | |
console.log("sweep #" + k + " nbad: " + best.nbad) | |
var next = f(best) | |
console.log("--- next:") | |
show_best(next, 1) | |
if (next.nbad >= best.nbad) { | |
break | |
} | |
best = next | |
if (best.nbad <= 0) break | |
} | |
console.log("sweeps: " + k) | |
return best | |
} | |
} | |
// iterate try_replace over a generator | |
function iterate_try_replace(gen) { | |
return function(best) { | |
for (var nsch of gen) { | |
var n = nsch[0] | |
var s = nsch[1] | |
for (var ch = 0; ch < 26; ++ch) { | |
var next = try_replace(best, n, s, ch) | |
if (next.nbad < best.nbad) { | |
console.log("" + n + " " + s + " ch: " + ch + " nbad: " + next.nbad) | |
best = next | |
if (best.nbad <= 0) { | |
return best | |
} | |
} | |
} | |
} | |
return best | |
} | |
} | |
// try_sweep :: (block -> gen) -> best -> best | |
function try_sweep(gen_factory) { | |
return function(best) { | |
var f = function(b) { | |
return iterate_try_replace( gen_factory(b.blocks) )(b) | |
} | |
return fix_nbad(f)(best) | |
} | |
} | |
// generator for all cells in the blocks | |
// all_block_cells :: block -> gen | |
function* all_block_cells(blocks) { | |
for (var n = 0; n < blocks.length; ++n) { | |
for (var s = 0; s < blocks[n].length; ++s) { | |
yield [n, s] | |
} | |
} | |
} | |
// same as all_block_cells except skip over cells up through (n0, s0) | |
// all_block_cells_from :: int -> int -> block -> gen | |
function all_block_cells_from(n0, s0) { | |
return function*(blocks) { | |
for (var n = n0; n < blocks.length; ++n) { | |
for (var s = 0; s < blocks[n].length; ++s) { | |
if ((n == n0) && s < s0) continue | |
yield [n, s] | |
} | |
} | |
} | |
} | |
// masked_cells :: perms -> (block -> gen) | |
function masked_cells(perms) { | |
return function*(blocks) { | |
for (var n = 0; n < blocks.length; ++n) { | |
for (var s = 0; s < blocks[n].length; ++s) { | |
console.log("n = " + n + " , s = " + s) | |
var ch = index_block(perms, n, s) | |
if (ch >= 0) continue | |
yield [n, s] | |
} | |
} | |
} | |
} | |
function index_block(mask, n, s) { | |
if (mask[n] && s < mask[n].length) { | |
var ch = mask[n].charCodeAt(s)-97 | |
if (ch >= 0 && ch < 26) { | |
return ch | |
} | |
} | |
return -1 | |
} | |
// create a pick function which always selects | |
// certain letters in certain positions | |
function pickfn_perms(perms) { | |
if (perms === null) { | |
perms = [] | |
} | |
var pickfn = function(hwords, n, s, used, mark, solved) { | |
var ch = index_block(perms, n-1, s) | |
if (ch >= 0) { | |
return ch | |
} | |
return most_frequent(hwords, n, s, used, mark, solved) | |
} | |
return pickfn | |
} | |
// start with a greedy solution and then sweep over | |
// cells until nbad doesn't change | |
function greedy_and_sweep(pickfn, gen_factory) { | |
var blocks = solve(all_words, pickfn) | |
console.log("blocks:\n" + show_blocks_optimized(blocks).join("\n")) | |
if (blocks.length > 14) { | |
while (blocks.length > 14) { | |
blocks.pop() | |
} | |
var best = make_solution(blocks, all_words) | |
best = try_sweep(gen_factory)(best) | |
show_best(best) | |
} | |
} | |
function test1() { | |
// produces: e / hi / aos / lnrt / ... | |
greedy_and_sweep(most_frequent, all_block_cells) | |
} | |
function test2() { | |
// produces: a / ae / ior / ... | |
var perms = [ "a", "a" ] | |
var pickfn = pickfn_perms(perms) | |
greedy_and_sweep(pickfn, masked_cells(perms)) | |
} | |
function test3(ch) { | |
// see if we can find a solution starting: a / aX / ... | |
var perms = [ "a", "a" + ch ] | |
var pickfn = pickfn_perms(perms) | |
greedy_and_sweep(pickfn, masked_cells(perms)) | |
} | |
function test4() { | |
var blocks = to_blocks("a ab eio inos lnrst ceilot ceilors cdeglmos cdlmnprsu eghilmnrtu bdfglmnptvy cefhilmnosyz acdhklmnrsvwx abfgijkopqsuwz") | |
var best = make_solution(blocks, all_words) | |
best = try_sweep( all_block_cells_from(2, 0) )(best) | |
show_best(best) | |
} | |
test4() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment