Daily Programmer 326

jsolve.js

// 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()