wordle-solver/wordle.js

// encodes the result of the guess as a number in base 3
// where
// 0 means no match
// 1 means an exact match, and
// 2 means it's somewhere in the word
function compute_match(guess, word) {
  var ret = 0
  var matched = 0
  const notmatched = []

  const last = Math.min(guess.length, word.length)-1
  for (var i = last; i >= 0; i--) {
    ret *= 3
    matched *= 2
    if (guess[i] == word[i]) {
      //console.log("match ", i)
      ret += 1
      matched += 1
    } else {
      notmatched.push(word[i])
    }
  }
  var mul = 1
  for (var i = 0; i <= last; i++) {
    if ((matched % 2) == 0) {
      // check against the notmatched array
      for (var j = 0; j < notmatched.length; j++) {
        if (notmatched[j] == guess[i]) {
          //console.log("exists", i, j, guess, notmatched)
          notmatched[j] = '-'
          ret += 2*mul
          break
        }
      }
    }
    mul *= 3
    matched = Math.floor(matched/2)
  }

  return ret
}

// converts the base 3 number into something that's readable
function dump_match(v) {
  var ret = []
  for (var i = 0; i < 5; i++) {
    ret.push(v % 3)
    v = Math.floor(v/3)
  }
  return ret
}

function undump_match(l) {
  var mul = 1
  var ret = 0
  for (var i = 0; i < 5; i++) {
    ret += l[i]*mul
    mul *= 3
  }
  return ret
}

var all_matches_buffer = null
var all_matches = null
const precompute_all = (() => {
  var idx = 0
  var init_start = null
  var num_loops = 10
  return () => {
    const l = words.length
    const start = Date.now()
    if (idx == 0) {
      all_matches_buffer = new ArrayBuffer(l*l)
      all_matches = new Uint8Array(all_matches_buffer)
      init_start = start
    }
    for (var i = 0; i < num_loops && idx < l; i++, idx++) {
      for (var j = 0; j < l; j++) {
        all_matches[idx*l + j] = compute_match(words[idx], words[j])
      }
    }
    if (idx < l) {
      status("computing word " + idx + "/" + words.length + " " + words[idx])
    }
    const end = Date.now()
    const millis = end - start
    num_loops = Math.floor(num_loops - 0.5*(millis - 50))
    num_loops = Math.max(num_loops, 1)

    if (idx >= l) {
      inited = true
      console.log("precompute done, mem = " + all_matches.length + " bytes")
      log("precompute done, mem = " + all_matches.length + " bytes")
      status("precompute done, mem = " + all_matches.length + " bytes")
      log("took " + (end - init_start) + " ms")
      console.log("took " + (end - init_start) + " ms")
    } else {
      setTimeout(precompute_all, 0)
    }
  }
})()

const LIST_END = (1<<16) - 1
function calc_entropy_with_cache(valid_words, guess_idx, cache) {
  var entropy = 0
  cache.fill(0)

  const l = words.length
  var view = new Uint8Array(all_matches_buffer, guess_idx*l)

  var num_words = 0
  for (var i = 0; i < valid_words.length; i++) {
    if (valid_words[i] == LIST_END) break
    cache[view[valid_words[i]]] += 1
    num_words++
  }

  const log2 = Math.log(2)
  for (var i = 0; i < 5*5*5*5*5; i++) {
    if (cache[i] == 0) continue
    var prob = cache[i]/num_words
    //console.log("prob ", i, prob)
    entropy += -Math.log(prob)/log2*prob
  }
  return entropy
}

function calc_entropy(valid_words, guess_idx) {
  return calc_entropy_with_cache(valid_words, guess_idx, new Uint16Array(5*5*5*5*5))
}

function calc_best_word(valid_words) {
  var cur_best = -1
  var best_entropy = -1

  const cache = new Uint16Array(5*5*5*5*5)

  /*
  for (var i = 0; i < valid_words.length; i++) {
    if (valid_words[i] == LIST_END) break
    var entropy = calc_entropy_with_cache(valid_words, valid_words[i], cache)
    if (entropy > best_entropy) {
      cur_best = valid_words[i]
      best_entropy = entropy
    }
  }
  */
  for (var i = 0; i < words.length; i++) {
    var entropy = calc_entropy_with_cache(valid_words, i, cache)
    if (entropy > best_entropy) {
      cur_best = i
      best_entropy = entropy
    }
  }

  return [cur_best, best_entropy]
}

function invalidate_words(valid_words, guess, match_result) {
  const l = words.length
  var view = new Uint8Array(all_matches_buffer, guess*l)

  var idx = 0
  for (var i = 0; i < valid_words.length; i++) {
    if (valid_words[i] == LIST_END) break
    if (view[valid_words[i]] == match_result) {
      valid_words[idx] = valid_words[i]
      idx++
    }
  }
  if (idx != valid_words.length) valid_words[idx] = LIST_END
  return idx
}

function gen_all_words_list() {
  var ret = new Uint16Array(words.length)
  for (var i = 0; i < words.length; i++) {
    ret[i] = i
  }
  return ret
}

function words_len(v) {
  for (var i = 0; i < v.length; i++) {
    if (v[i] == LIST_END) return i
  }
  return v.length
}