SEND MORE MONEY

send_more_money.js

'use strict';
/**
Javascript (ES6) implementation of a puzzle: each letter is a digit (0-9) and we have to find values for the letters in SEND MORE MONEY such that:
1. replacing the letters with the correspondign digits the expression SEND + MORE = MONEY is true
2. the first digits of each word are not 0
*/

const leftpart1 = 'SEND'.split('');
const leftpart2 = 'MORE'.split('');

const rightpart = 'MONEY'.split('');
//concatenate the arrays and take distinct letters. Order is not important
const possibleLetters = [...new Set(leftpart1.concat(leftpart2).concat(rightpart))];

/**
* Value of the characters in an array given the map of their values
The value map must be complete
*/
const numberValue = function(chars, values){
  let ps = 0;
  chars.forEach((c, i) => ps += Math.pow(10, chars.length - i - 1) * (values[c]));
  return ps;
};

/**
* given a map of values, tells whether we can stop processing the solution right now.
For now, no check is made and it works by pure brute force
*/
const canBeDiscarded = function(values) {
  return false;
};

/*
given a partial solution, adds values and recursively tries them
*/
const solve = function(partialSolution){
  //console.log('trying with ',partialSolution);
  //find a letter that can be assigned
  for(let l of possibleLetters) {
     if (typeof partialSolution[l] !== 'undefined')
        continue;
      //the letter can be assigned, so try all 10 digits recursively
      for(let d = 0; d < 10; d++ ) {
        //first letter cannot be 0
        if (d === 0 && (leftpart1[0] === l || leftpart2[0] === l || rightpart[0] === l)) {
          continue;
        }
        //clone the object and assign the letter
        let solutionIncrement = {};
        solutionIncrement[l] = d;
        const candidatePartialSolution = Object.assign(solutionIncrement, partialSolution);
        //recursion
        if (!canBeDiscarded(candidatePartialSolution)) {
          solve(candidatePartialSolution);
        }
      }
      //all 10 digits were tried, terminate this branch
      return;
  }
  //no remaining letters found, this is a leaf in the solution tree. Check whether we found a solution or not
  if (numberValue(leftpart1, partialSolution) + numberValue(leftpart2, partialSolution) === numberValue(rightpart, partialSolution)) {
    console.log('FOUND A SOLUTION: ' + JSON.stringify(partialSolution, null, 2));
  }
  else {
  // console.log('INVALID SOLUTION: ' + JSON.stringify(partialSolution, null, 2));
  }
};

//start with an empty solution
solve({});