 # boris-lenzinger's solution

## to Alphametics in the Java Track

Published at Oct 19 2019 · 0 comments
Instructions
Test suite
Solution

Write a function to solve alphametics puzzles.

Alphametics is a puzzle where letters in words are replaced with numbers.

For example `SEND + MORE = MONEY`:

``````  S E N D
M O R E +
-----------
M O N E Y
``````

Replacing these with valid numbers gives:

``````  9 5 6 7
1 0 8 5 +
-----------
1 0 6 5 2
``````

This is correct because every letter is replaced by a different number and the words, translated into numbers, then make a valid sum.

Each letter must represent a different digit, and the leading digit of a multi-digit number must not be zero.

Write a function to solve alphametics puzzles.

## Setup

Go through the setup instructions for Java to install the necessary dependencies:

https://exercism.io/tracks/java/installation

# Running the tests

You can run all the tests for an exercise by entering the following in your terminal:

``````\$ gradle test
``````

Use `gradlew.bat` if you're on Windows

In the test suites all tests but the first have been skipped.

Once you get a test passing, you can enable the next one by removing the `@Ignore("Remove to run test")` annotation.

## Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

### AlphameticsTest.java

``````import org.junit.Ignore;
import org.junit.Rule;
import org.junit.Test;
import org.junit.rules.ExpectedException;

import static org.hamcrest.CoreMatchers.*;
import static org.junit.Assert.*;

public class AlphameticsTest {
@Rule
public ExpectedException expectedException = ExpectedException.none();

@Test
public void testThreeLetters() throws UnsolvablePuzzleException {
expected.put('I', 1);
expected.put('B', 9);
expected.put('L', 0);

assertEquals(expected, new Alphametics("I + BB == ILL").solve());
}

@Ignore("Remove to run test")
@Test
public void testUniqueValue() throws UnsolvablePuzzleException {
expectedException.expect(UnsolvablePuzzleException.class);
new Alphametics("A == B").solve();
}

@Ignore("Remove to run test")
@Test
public void testLeadingZero() throws UnsolvablePuzzleException {
expectedException.expect(UnsolvablePuzzleException.class);
assertNull(new Alphametics("ACA + DD == BD").solve());
}

@Ignore("Remove to run test")
@Test
public void testTwoDigitsFinalCarry() throws UnsolvablePuzzleException {
expected.put('A', 9);
expected.put('B', 1);
expected.put('C', 0);

assertEquals(expected, new Alphametics("A + A + A + A + A + A + A + A + A + A + A + B == BCC").solve());
}

@Ignore("Remove to run test")
@Test
public void testFourLetters() throws UnsolvablePuzzleException {
expected.put('A', 9);
expected.put('S', 2);
expected.put('M', 1);
expected.put('O', 0);

assertEquals(expected, new Alphametics("AS + A == MOM").solve());
}

@Ignore("Remove to run test")
@Test
public void testSixLetters() throws UnsolvablePuzzleException {
expected.put('N', 7);
expected.put('O', 4);
expected.put('T', 9);
expected.put('L', 1);
expected.put('A', 0);
expected.put('E', 2);

assertEquals(expected, new Alphametics("NO + NO + TOO == LATE").solve());
}

@Ignore("Remove to run test")
@Test
public void testSevenLetters() throws UnsolvablePuzzleException {
expected.put('E', 4);
expected.put('G', 2);
expected.put('H', 5);
expected.put('I', 0);
expected.put('L', 1);
expected.put('S', 9);
expected.put('T', 7);

assertEquals(expected, new Alphametics("HE + SEES + THE == LIGHT").solve());
}

@Ignore("Remove to run test")
@Test
public void testEightLetters() throws UnsolvablePuzzleException {
expected.put('S', 9);
expected.put('E', 5);
expected.put('N', 6);
expected.put('D', 7);
expected.put('M', 1);
expected.put('O', 0);
expected.put('R', 8);
expected.put('Y', 2);

assertEquals(expected, new Alphametics("SEND + MORE == MONEY").solve());
}

@Ignore("Remove to run test")
@Test
public void testTenLetters() throws UnsolvablePuzzleException {
expected.put('A', 5);
expected.put('D', 3);
expected.put('E', 4);
expected.put('F', 7);
expected.put('G', 8);
expected.put('N', 0);
expected.put('O', 2);
expected.put('R', 1);
expected.put('S', 6);
expected.put('T', 9);

assertEquals(expected, new Alphametics("AND + A + STRONG + OFFENSE + AS + A + GOOD == DEFENSE").solve());
}

@Ignore("Remove to run test")
@Test
public void testTenLetters41Addends() throws UnsolvablePuzzleException {
expected.put('A', 1);
expected.put('E', 0);
expected.put('F', 5);
expected.put('H', 8);
expected.put('I', 7);
expected.put('L', 2);
expected.put('O', 6);
expected.put('R', 3);
expected.put('S', 4);
expected.put('T', 9);

assertEquals(expected, new Alphametics("THIS + A + FIRE + THEREFORE + FOR + ALL + HISTORIES + I + TELL + A + " +
"TALE + THAT + FALSIFIES + ITS + TITLE + TIS + A + LIE + THE + TALE + OF + THE + LAST + FIRE + " +
"HORSES + LATE + AFTER + THE + FIRST + FATHERS + FORESEE + THE + HORRORS + THE + LAST + FREE + " +
"TROLL + TERRIFIES + THE + HORSES + OF + FIRE + THE + TROLL + RESTS + AT + THE + HOLE + OF + " +
"LOSSES + IT + IS + THERE + THAT + SHE + STORES + ROLES + OF + LEATHERS + AFTER + SHE + SATISFIES + " +
"HER + HATE + OFF + THOSE + FEARS + A + TASTE + RISES + AS + SHE + HEARS + THE + LEAST + FAR + " +
"HORSE + THOSE + FAST + HORSES + THAT + FIRST + HEAR + THE + TROLL + FLEE + OFF + TO + THE + " +
"FOREST + THE + HORSES + THAT + ALERTS + RAISE + THE + STARES + OF + THE + OTHERS + AS + THE + " +
"TROLL + ASSAILS + AT + THE + TOTAL + SHIFT + HER + TEETH + TEAR + HOOF + OFF + TORSO + AS + THE + " +
"LAST + HORSE + FORFEITS + ITS + LIFE + THE + FIRST + FATHERS + HEAR + OF + THE + HORRORS + THEIR + " +
"FEARS + THAT + THE + FIRES + FOR + THEIR + FEASTS + ARREST + AS + THE + FIRST + FATHERS + " +
"RESETTLE + THE + LAST + OF + THE + FIRE + HORSES + THE + LAST + TROLL + HARASSES + THE + FOREST + " +
"HEART + FREE + AT + LAST + OF + THE + LAST + TROLL + ALL + OFFER + THEIR + FIRE + HEAT + TO + THE + " +
"ASSISTERS + FAR + OFF + THE + TROLL + FASTS + ITS + LIFE + SHORTER + AS + STARS + RISE + THE + " +
"HORSES + REST + SAFE + AFTER + ALL + SHARE + HOT + FISH + AS + THEIR + AFFILIATES + TAILOR + A + " +
"ROOFS + FOR + THEIR + SAFE == FORTRESSES").solve());
}
}``````
``````import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

/**
* Representation of a permutation of numbers. This makes it easier to read the
* code to use named structure instead of "technical" structures.
*
* The type could have been made generic but this would be overkill and really
* pointless for this exercice.
*
*/
class Permutation {
List<Integer> representation;

/**
* Creates a permutation backed with a List structure.
*/
Permutation() {
this.representation = new ArrayList<>();
}

/**
* Adds and element in the permutation.
*
* @param value
*/
}

/**
* Returns the i-th element of the permutation. Index starts at 0.
*
* @param index
* @return
*/
Integer get(int index) {
return this.representation.get(index);
}

}

/**
* Supplies functions to generate permutations. It has been put in another class
*
*/
class PermutationHelper {
static List<Permutation> computeAllPossiblePermutationsOfSizeNInSetOfP(List<Integer> list, int chooseN) {
if (chooseN == 0) {
// stop case of recurrence
return new ArrayList<Permutation>();
}
List<Permutation> result = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
List<Integer> clone = new ArrayList<>(list);
clone.remove(list.get(i));
List<Permutation> subchoices = computeAllPossiblePermutationsOfSizeNInSetOfP(clone, chooseN - 1);
if (subchoices.size() == 0) {
Permutation combination = new Permutation();
} else {
for (int j = 0; j < subchoices.size(); j++) {
}
}
}
return result;
}

}

/**
* Representation of a solution for a character equation. A solution for a
* character equation consists of a list of letters where each letter has a
* value associated. The value is between 0 and 9.
*/
class Solution {
Map<Character, Integer> representation;

/**
* Initializes the structure.
*/
Solution() {
representation = new HashMap<Character, Integer>();
}

/**
* Generates an uniq string for a solution. This is used to check if two
* solutions are the same of if they are different.
*/
String fingerprint() {
StringBuilder fingerprint = new StringBuilder();
List<Character> keys = new ArrayList<>(this.representation.keySet());
Collections.sort(keys);
for (Character letter : keys) {
if (fingerprint.length() > 0) {
fingerprint.append(",");
}
fingerprint.append(letter).append("=").append(representation.get(letter).toString());
}
return fingerprint.toString();
}

/**
* Checks if a solution has a value for a letter.
*
* @param letter the letter to be checked
* @return the value associated to this letter
*/
boolean hasValueFor(Character letter) {
return this.representation.containsKey(letter);
}

/**
* Returns the value of a letter for a given letter.
*
* @param letter
* @return
*/
Integer valueFor(Character letter) {
return this.representation.get(letter);
}

/**
* Merges 2 solutions together.
*
* @param otherSolution the solution to merge into this solution
*/
void mergeWith(Solution otherSolution) {
this.representation.putAll(otherSolution.representation);
}

/**
* Returns the values (among 0 up to 9) that are not attributed to the letters
* stored in the solution.
*/
List<Integer> getUnusedValues() {
List<Integer> availableValues = new ArrayList<>(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
availableValues.removeAll(this.representation.values());

return availableValues;
}

/**
* Add a new letter with a value to the solution. If the letter was already in
* the solution, its value will be overriden.
*
* @param letter
* @param value
*/
void addIdentifiedLetter(Character letter, Integer value) {
this.representation.put(letter, value);
}

/**
* Returns the list of the letters passed as parameters that are not referenced
* in the solution.
*
* @param letters
* @return
*/
List<Character> listUnknownLettersAmong(Character... letters) {
List<Character> unidentifiedChars = new ArrayList<>(Arrays.asList(letters));
for (Character identified : this.representation.keySet()) {
while (unidentifiedChars.contains(identified)) {
unidentifiedChars.remove(identified);
}
}
return new ArrayList<>(new HashSet<>(unidentifiedChars));
}
}

/**
* Logical structure to store list of solutions for a characters equation.
*/
class Solutions {
List<Solution> representation;
/**
* Fast way to check if a solution is already in the list of solutions. It
* stores the fingerprints of all the stored solutions.
*/
Map<String, Short> fingerprints;

/**
* Initializes the structure.
*/
Solutions() {
this.representation = new ArrayList<>();
this.fingerprints = new HashMap<>();
}

/**
* Adds a solution to the existing solutions only if the fingerprint of the new
* solution is part of the list of the fingerprints.
*/
String fingerprint = s.fingerprint();
if (!this.fingerprints.containsKey(fingerprint)) {
this.fingerprints.put(fingerprint, new Short((short) 1));
}
}

/**
* Returns the number of solutions stored.
*/
int count() {
return this.representation.size();
}

/**
* Returns the i-th solution.
*/
Solution get(int index) {
return this.representation.get(index);
}

/**
* Merges another set of solutions to this set.
*
* @param l
*/
void mergeWith(Solutions l) {
if (l.count() > 0) {
for (int i = 0; i < l.count(); i++) {
}
}
}
}

/**
* A riddle is a letter equation to solve. It is a column of the global problem
* to solve. The idea is to subdivide the problem in columns to be solved.
*/
class Riddle {
/**
* The list of letters to sum to get the result.
*/
Character[] lettersToSum;
/**
* The letter that is the result of the sum of the other letters. The equality
* is modulo 10.
*/
Character result;
/**
* The carry from the previous riddle.
*/
int carry;
/**
* The solution that have been found to solve the previous column.
*/
Solution identifiedLetters;
/**
* A constraint indicating which letters must no be zero. They are the first
* letter of each word of the riddle.
*/
Set<Character> lettersThatMustNotBeZero;

/**
* Use this constructor for initial startup. This is working only for the first
* column to be solved (which is the last column of the words in the sum).
*/
Riddle(Character[] letters, Character result, Set<Character> lettersNotZero) {
this.lettersToSum = letters;
this.result = result;
this.carry = 0;
this.identifiedLetters = new Solution();
this.lettersThatMustNotBeZero = lettersNotZero;
}

/**
* Use this constructor when you have a possible solution.
*
* @param letters           the letters that must be summed to reach the result
* @param result            the letter that is the sum (modulo 10) of the others
* @param carry             the carry from the previous potential solution
* @param identifiedLetters the letters for which we think we have a solution.
*                          This is a list of possibilities.
* @param lettersNotZero    each start of a word cannot be zero. This list
*                          stores the letters that cannot be zero.
*/
Riddle(Character[] letters, Character result, int carry, Solution identifiedLetters,
Set<Character> lettersNotZero) {
this.lettersToSum = letters;
this.result = result;
this.carry = carry;
this.identifiedLetters = identifiedLetters;
this.lettersThatMustNotBeZero = lettersNotZero;
}

/**
* Generic method to append an element to an array.
*/
private static <T> T[] append(T[] arr, T lastElement) {
final int N = arr.length;
arr = Arrays.copyOf(arr, N + 1);
arr[N] = lastElement;
return arr;
}

/**
* Checks if the solution passed in parameter matches the following constraints
* of the riddle: does the sum of the letters proposed in the solution solves
* the equation: sum of the letters plus the carry equals the result of the
* riddle (modulo 10).
*
* @param candidate
* @return
*/
private boolean solutionMatchesConstraints(Solution candidate) {
// no unknown value. This new equation is used to filter some solutions...
int sum = 0;
for (int k = 0; k < this.lettersToSum.length; k++) {
if (candidate.hasValueFor(lettersToSum[k])) {
sum += candidate.valueFor(lettersToSum[k]);
}
}
sum += this.carry;
int expectedSum = candidate.valueFor(this.result);
// if that matches, merge the identified letters and the new combination to a
// new solution and add it to the output list
if (sum % 10 == expectedSum) {
return true;
}
return false;
}

/**
* Computes all the solutions that solves the letter equation. There are
* probably more than 1. If none is found, sends back an empty set of solutions.
*
* @return
*/
Solutions computeSolutions() {
Solutions newsolutions = new Solutions();
// identify the possible values for the unknown letters = P
List<Integer> availableValues = this.identifiedLetters.getUnusedValues();
// identify the letters with no value = N
List<Character> uniqLettersWithNoValue = this.identifiedLetters
.listUnknownLettersAmong(append(this.lettersToSum, result));

if (uniqLettersWithNoValue.size() == 0) {
if (solutionMatchesConstraints(this.identifiedLetters)) {
}
} else {
// build all the permutations based of N among the possible P values
List<Permutation> permutations = PermutationHelper
.computeAllPossiblePermutationsOfSizeNInSetOfP(availableValues, uniqLettersWithNoValue.size());
// for every permutation, check if the letter not equal to zero is matched
// and check if the sum matches (modulo 10).
for (Permutation permutation : permutations) {
nextPermutation: {
Solution candidateSolution = new Solution();
for (int j = 0; j < uniqLettersWithNoValue.size(); j++) {
}
for (int j = 0; j < uniqLettersWithNoValue.size(); j++) {
Character letter = uniqLettersWithNoValue.get(j);
if (lettersThatMustNotBeZero.contains(letter) && candidateSolution.valueFor(letter) == 0) {
break nextPermutation;
}
}
// the permutation does not violate any simple rule. Merging the solutions to
// build the candidate
candidateSolution.mergeWith(this.identifiedLetters);
// now let's check the sum
if (solutionMatchesConstraints(candidateSolution)) {
}
}
}
}
return newsolutions;
}
}

/**
* The words equation solver.
*/
class Alphametics {

/**
* The initial word equation passed as parameter.
*/
String input;
/**
* The list of words on the left side of the equal sign of the equation to be
* solved.
*/
String[] words;
/**
* The word that must match the sum of the other words. It is on the right side
*/
String result;
/**
* The number of columns (or riddle) to be solved. This is basically the number
* of letters in the result world.
*/
int totalNumberOfEquations;

/**
* Stores the letters that cannot be zero by definition: the first letter of
* each word cannot be zero.
*/
Set<Character> cannotBeZero;

/**
* Solves alphametics puzzles.
*
* [Alphametics](https://en.wikipedia.org/wiki/Alphametics) is a puzzle where
* letters in words are replaced with numbers.
*
* For example `SEND + MORE = MONEY`:
*
* ```text S E N D M O R E + ----------- M O N E Y ```
*
* Replacing these with valid numbers gives:
*
* ```text 9 5 6 7 1 0 8 5 + ----------- 1 0 6 5 2 ```
*
* This is correct because every letter is replaced by a different number and
* the words, translated into numbers, then make a valid sum.
*
* Each letter must represent a different digit, and the leading digit of a
* multi-digit number must not be zero.
*
* @param riddle
*/
Alphametics(String riddle) {
String[] partsOfEquation = riddle.split("==");
input = partsOfEquation.trim();
result = partsOfEquation.trim();
cannotBeZero = new HashSet<>();
splitWords();
totalNumberOfEquations = result.length();
}

/**
* Separates the words of the equation in an array and prepares the list of the
* letters that cannot be zero.
*
* @see cannotBeZero
*/
private void splitWords() {
words = input.split("\\s*\\+\\s*");
for (int i = 0; i < words.length; i++) {
words[i] = words[i].trim();
}
for (String word : words) {
}
}

/**
* For a given number of equation (starting at 1, which is the sum of all the
* letters in the last column), the function returns the list of the letters
* that will be added to get to the matching result letter. This can be empty if
* the longest word is the result and no word has the same size. In this case
* the only value that will be in the sum will be the carry of the previous
* column.
*/
private Character[] getListOfLettersInSum(int index) {
List<Character> letters = new ArrayList<>();
for (int i = 0; i < words.length; i++) {
String w = words[i];
int wordLength = w.length();
if (index <= wordLength) {
}
}
return letters.stream().toArray(Character[]::new);
}

/**
* If the riddle has more than 10 letters, this is an issue since there are only
* 10 ciphers available. Determining if the riddle has more than 10 letters is a
* show stopper.
*
* @return
*/
private boolean riddleHasMoreThan10Letters() {
List<Character> allChars = input.replaceAll("\\s*\\+\\s*", "").replaceAll("\\s*", "").chars()
.mapToObj(c -> (char) c).collect(Collectors.toList());
return true;
}
return false;
}

/**
* Solve makes a brute force computation to find out a unique solution. If there
* is no unique solution, if the number of different letters is more than 10 or
* if there are no solution, an UnsolvablePuzzleException exception is thrown.
*
* This is the algorithm that is used to compute the solutions: First we compute
* all the possible solutions for the last column. The only variables here are
* the different letters. There is no possible carry so we are that the sum is
* exact. Once we found the list of the possible (partial) solutions, we focus
* on the next column. We build a riddle with the next column and we run through
* each solution computed in the previous iteration. Based on this list of
* letters, we compute the sum of the letters in the previous column. This tells
* the carry to report to the actuel sum. Then we solve the riddle based on the
* existing letters and the possible values that we pick in the remaining
* values.
*/
LinkedHashMap<Character, Integer> solve() throws UnsolvablePuzzleException {
if (riddleHasMoreThan10Letters()) {
throw new UnsolvablePuzzleException();
}
// now have to brute force the riddle...but with some constraints that will
// decrease the number of possibilities.
int carry = 0;
Solutions solutionsFromPreviousEquation = new Solutions();
// for first round, add empty values
Solutions possibleSolutionsUntilIthEquation;
for (int i = 1; i <= this.totalNumberOfEquations; i++) {
possibleSolutionsUntilIthEquation = new Solutions();
for (Solution identifiedLetters : solutionsFromPreviousEquation.representation) {
Character[] equation = getListOfLettersInSum(i);
Character result = getResultOfSum(i);
carry = computeCarryForIthEquation(i, identifiedLetters);
Riddle riddle = new Riddle(equation, result, carry, identifiedLetters, this.cannotBeZero);
possibleSolutionsUntilIthEquation.mergeWith(riddle.computeSolutions());
}
// save the results computed to re-inject in the next equations
solutionsFromPreviousEquation = new Solutions();
solutionsFromPreviousEquation.mergeWith(possibleSolutionsUntilIthEquation);
}
if (solutionsFromPreviousEquation.count() != 1) {
throw new UnsolvablePuzzleException();
}
}

/**
* Returns the letter that is the result of the sum of letters in the equation
* number passed as parameter.
*/
private Character getResultOfSum(int equationNumber) {
return this.result.charAt(result.length() - equationNumber);
}

/**
* Computes the carry reported for equation passed in parameter and the set of
* possible values for the letters.
*
* @param equationNumber                  the N-th equation of the riddle. They
*                                        are counted from the end of the string
*                                        to the beginning of the word.
* @param guessedValuesUntilNowForLetters a solution computed for the values of
*                                        the letters
* @return
*/
private int computeCarryForIthEquation(int equationNumber, Solution guessedValuesUntilNowForLetters) {
if (equationNumber == 1) {
// no carry for first equation since not yet any addition
return 0;
}

int carry = 0;
int sum = 0;
for (int i = 1; i < equationNumber; i++) {
sum = computeSumForEquation(getListOfLettersInSum(i), guessedValuesUntilNowForLetters) + carry;
carry = Math.floorDiv(sum, 10);
}
return carry;
}

/**
* Sums the letters passed as parameter using the values stored in the proposed
* solution parameter.
*/
private int computeSumForEquation(Character[] letters, Solution proposedSolution) {
StringBuilder s = new StringBuilder();
for (int i = 0; i < letters.length; i++) {
s.append(letters[i]);
}
int value = 0;
for (Character c : letters) {
value += proposedSolution.valueFor(c);
}
return value;
}

}``````