[2018-01-08] Challenge #346 [Easy] Cryptarithmetic Solver https://www.reddit.com/r/dailyprogrammer/comments/7p5p2o/20180108_challenge_346_easy_cryptarithmetic_solver/

cryptarithmetic.js

#
# [2018-01-08] Challenge #346 [Easy] Cryptarithmetic Solver
# https://www.reddit.com/r/dailyprogrammer/comments/7p5p2o/20180108_challenge_346_easy_cryptarithmetic_solver/
#
# Cryptarithms are a kind of mathematical puzzle. 
# Each puzzle consists of a basic equation of arithmetic (involving addition, subtraction, division, etc.) with words, where each letter represents a different digit.
# The goal of the puzzle is to find the correct number substitution for each letter in order to make a valid equation.
#
# by Kory Becker
# http://primaryobjects.com
#

const util = require('util');

const inputs = [
  'THIS + IS + HIS == CLAIM',
  'WHAT + WAS + THY == CAUSE',
  'HIS + HORSE + IS == SLAIN',
  'HERE + SHE == COMES',
  'FOR + LACK + OF == TREAD',
  'I + WILL + PAY + THE == THEFT'
];

var tokenize = function(input) {
  // Extract the left-side from the right-side of the equation.
  const parts = input.split(/[\+\= ]/).filter(part => part !== '');

  // Get unique tokens and initialize lowest possible values to start with.
  let tokens = {};
  parts.forEach(part => {
    for (let i=0; i<part.length; i++) {
      const token = part[i];

      // If this is the first token in the word, it must be at least 1 (no leading zeroes). If a token was already assigned a 1, use 1 even if the current word has the token in the middle of the word (0).
      tokens[token] = { value: i === 0 ? 1 : (tokens[token] ? tokens[token].value : 0), first: tokens[token] && tokens[token].first || i === 0 };
    }
  });

  return { parts: parts, tokens: tokens };
}

var encode = function(parts, tokens) {
  // Replace the characters in each part by their cooresponding values in tokens.
  let equation = [];

  for (let i=0; i<parts.length; i++) {
    const part = parts[i];
    let number = '';

    for (let j=0; j<part.length; j++) {
      const ch = part[j];
      const value = tokens[ch].value;

      number += value;
    }

    equation.push(parseInt(number));
  }

  return equation;
}

var complete = function(equation) {
  // Check if the left-side equals the right-side of the equation.
  let sum = 0;

  for (let i=0; i<equation.length - 1; i++) {
    sum += equation[i];
  }

  return { sum: sum, target: equation[equation.length - 1], success: (sum === equation[equation.length - 1]) };
}

var random = function(max) {
  return Math.floor(Math.random() * Math.floor(max));
}

var solve = function(input, tokens, verbose) {
  let count = 0;
  var fringe = [ tokens ];
  let result = null;

  while (fringe.length) {
    // Get the next state.
    const values = fringe.shift();

    // Encode the equation with values from the state.
    const equation = encode(input, values)
    const balance = complete(equation);

    if (verbose && ++count % 100000 === 0) {
      count = 0;
      console.log(equation);
      console.log(result);
    }

    if (balance.success) {
      // Solution found!
      result = { values: values, equation: equation, balance: balance };
      break;
    }
    else {
      // Add child states. A child state will be 
      let child = {};
      const keys = Object.keys(values);
      for (let i=0; i<keys.length; i++) {
        const key = keys[i];
        const first = values[key].first;
        let r = random(10);
        r = first && !r ? 1 : r; // No leading zeroes.

        child[key] = { value: r, first: first };
      }

      fringe.push(child);
    }
  }

  return result;
}

inputs.forEach(input => {
  const data = tokenize(input);

  console.log(data.parts);

  const result = solve(data.parts, data.tokens);

  console.log('*** Solution ***');
  console.log(util.inspect(result, true, 10));
  console.log('');
});

output.txt

[ 'THIS', 'IS', 'HIS', 'CLAIM' ]
*** Solution ***
{ values:
   { T: { value: 9, first: true },
     H: { value: 8, first: true },
     I: { value: 5, first: true },
     S: { value: 3, first: false },
     C: { value: 1, first: true },
     L: { value: 0, first: false },
     A: { value: 7, first: false },
     M: { value: 9, first: false } },
  equation: [ 9853, 53, 853, 10759, [length]: 4 ],
  balance: { sum: 10759, target: 10759, success: true } }

[ 'WHAT', 'WAS', 'THY', 'CAUSE' ]
*** Solution ***
{ values:
   { W: { value: 9, first: true },
     H: { value: 7, first: false },
     A: { value: 0, first: false },
     T: { value: 1, first: true },
     S: { value: 8, first: false },
     Y: { value: 1, first: false },
     C: { value: 1, first: true },
     U: { value: 7, first: false },
     E: { value: 0, first: false } },
  equation: [ 9701, 908, 171, 10780, [length]: 4 ],
  balance: { sum: 10780, target: 10780, success: true } }

[ 'HIS', 'HORSE', 'IS', 'SLAIN' ]
*** Solution ***
{ values:
   { H: { value: 4, first: true },
     I: { value: 5, first: true },
     S: { value: 4, first: true },
     O: { value: 8, first: false },
     R: { value: 5, first: false },
     E: { value: 4, first: false },
     L: { value: 9, first: false },
     A: { value: 0, first: false },
     N: { value: 2, first: false } },
  equation: [ 454, 48544, 54, 49052, [length]: 4 ],
  balance: { sum: 49052, target: 49052, success: true } }

[ 'HERE', 'SHE', 'COMES' ]
*** Solution ***
{ values:
   { H: { value: 9, first: true },
     E: { value: 9, first: false },
     R: { value: 9, first: false },
     S: { value: 8, first: true },
     C: { value: 1, first: true },
     O: { value: 0, first: false },
     M: { value: 8, first: false } },
  equation: [ 9999, 899, 10898, [length]: 3 ],
  balance: { sum: 10898, target: 10898, success: true } }

[ 'FOR', 'LACK', 'OF', 'TREAD' ]
*** Solution ***
{ values:
   { F: { value: 7, first: true },
     O: { value: 2, first: true },
     R: { value: 0, first: false },
     L: { value: 9, first: true },
     A: { value: 8, first: false },
     C: { value: 3, first: false },
     K: { value: 6, first: false },
     T: { value: 1, first: true },
     E: { value: 5, first: false },
     D: { value: 3, first: false } },
  equation: [ 720, 9836, 27, 10583, [length]: 4 ],
  balance: { sum: 10583, target: 10583, success: true } }

[ 'I', 'WILL', 'PAY', 'THE', 'THEFT' ]
*** Solution ***
{ values:
   { I: { value: 5, first: true },
     W: { value: 9, first: true },
     L: { value: 9, first: false },
     P: { value: 4, first: true },
     A: { value: 5, first: false },
     Y: { value: 6, first: false },
     T: { value: 1, first: true },
     H: { value: 0, first: false },
     E: { value: 1, first: false },
     F: { value: 6, first: false } },
  equation: [ 5, 9599, 456, 101, 10161, [length]: 5 ],
  balance: { sum: 10161, target: 10161, success: true } }