# artemkorsakov's solution

## to Alphametics in the Java Track

Published at Mar 17 2019 · 0 comments
Instructions
Test suite
Solution

#### Note:

This exercise has changed since this solution was written.

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.

# Running the tests

You can run all the tests for an exercise by entering

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

## 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 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());
}
}``````

### src/main/java/Alphametics.java

``````import java.util.*;

public class Alphametics {
private String equation;
private List<String> terms;
private String result;

Alphametics(String equation) throws UnsolvablePuzzleException {
this.equation = equation.replaceAll(" ", "");
calculateMembers();
}

LinkedHashMap<Character, Integer> solve() throws UnsolvablePuzzleException {
Set<Character> unique = new HashSet<>();
for (char c : equation.replaceAll("[^A-Z]", "").toCharArray()) {
}
PossibleValues possibleValues = new PossibleValues(new ArrayList<>(unique));
possibleValues.checkFirstLetterInResult(terms, result);

while (!possibleValues.isSuccess()) {
LinkedHashMap<Character, List<Integer>> tmpPv = possibleValues.getPossibleValues();
char candidateChar = tmpPv.keySet().stream().min(Comparator.comparingInt(o -> tmpPv.get(o).size())).orElseThrow();
int candidateNum = tmpPv.get(candidateChar).get(0);
List<LinkedHashMap<Character, Integer>> tmpMaps = possibleValues.getPossibleMaps(candidateChar, candidateNum);
for (LinkedHashMap<Character, Integer> tmpMap : tmpMaps) {
TempResult tr = new TempResult(tmpMap);
if (tr.isResultCorrect(terms, result)) {
return tmpMap;
}
}
possibleValues.remove(candidateChar, candidateNum);
}

return possibleValues.getResult();
}

private void calculateMembers() throws UnsolvablePuzzleException {
// If there are more than 10 letters then there is no solution.
if (equation.replaceAll("[^A-Z]", "").chars().distinct().count() > 10) {
throw new UnsolvablePuzzleException();
}

String[] members = equation.split("==");
if (members.length != 2) {
throw new UnsolvablePuzzleException();
}

terms = Arrays.asList(members[0].split("\\+"));
Collections.sort(terms);
result = members[1];

// The length of each term on the left of the equation must not be longer than the length of the result.
// If one member is left and right then the task has no unique solution.
if (terms.size() == 1 || terms.stream().anyMatch(t -> t.length() > result.length())) {
throw new UnsolvablePuzzleException();
}
}
}``````

### src/main/java/TempResult.java

``````import java.util.LinkedHashMap;
import java.util.List;

class TempResult {
private LinkedHashMap<Character, Integer> tmpMap;

TempResult(LinkedHashMap<Character, Integer> tmpMap) {
this.tmpMap = tmpMap;
}

boolean isResultCorrect(List<String> terms, String result) {
long sum = getNumber(result);
String prevTerm = "";
long prevNumber = 0L;
for (String term : terms) {
if (!prevTerm.equals(term)) {
prevTerm = term;
prevNumber = getNumber(term);
}
sum -= prevNumber;
if (sum < 0) {
return false;
}
}
return sum == 0;
}

private long getNumber(String number) {
for (char key : tmpMap.keySet()) {
number = number.replace(key + "", tmpMap.get(key) + "");
}
return Long.parseLong(number);
}
}``````

### src/main/java/PossibleValues.java

``````import java.util.*;
import java.util.stream.Collectors;

// Possible values for letters.
class PossibleValues {
private LinkedHashMap<Character, List<Integer>> possibleValues;

PossibleValues(List<Character> chars) {
ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
possibleValues = new LinkedHashMap<>();
for (char ch : chars) {
possibleValues.put(ch, numbers);
}
}

boolean isSuccess() {
return possibleValues.values().stream().allMatch(v -> v.size() == 1);
}

LinkedHashMap<Character, Integer> getResult() {
for (char key : possibleValues.keySet()) {
result.put(key, possibleValues.get(key).get(0));
}

return result;
}

LinkedHashMap<Character, List<Integer>> getPossibleValues() {
return possibleValues;
}

// Returns a list of possible dictionaries under the assumption that
// the specified character is equal to the specified value.
List<LinkedHashMap<Character, Integer>> getPossibleMaps(char letter, int possibleValue) {
List<LinkedHashMap<Character, Integer>> result = new ArrayList<>();
List<Character> keysSortedByCountOfValues = possibleValues.keySet().stream()
.sorted(Comparator.comparingInt(k -> possibleValues.get(k).size()))
.collect(Collectors.toList());

for (char key : keysSortedByCountOfValues) {
List<Integer> values = key == letter ? Collections.singletonList(possibleValue) : possibleValues.get(key);
if (result.size() == 0) {
for (int value : values) {
tmp.put(key, value);
}
} else {
List<LinkedHashMap<Character, Integer>> tmp = new ArrayList<>();
for (int j = 0; j < result.size(); j++) {
LinkedHashMap<Character, Integer> curDic = result.get(j);
List<Integer> curValues = values.stream().filter(v -> !curDic.containsValue(v)).collect(Collectors.toList());

if (curValues.size() == 0) {
result.remove(curDic);
continue;
}

for (int curValue : curValues) {
if (!curDic.keySet().contains(key)) {
curDic.put(key, curValue);
} else {
newDictionary.remove(key);
newDictionary.put(key, curValue);
}
}
}
}
}

return result.stream().filter(map -> map.keySet().size() == possibleValues.keySet().size()).collect(Collectors.toList());
}

/*
* Remove value from the list of possible.
* If nothing is left then throw the exception.
* If only one is left then remove it from the rest chars.
*/
void remove(char ch, int val) throws UnsolvablePuzzleException {
if (!possibleValues.get(ch).contains(val)) {
return;
}

ArrayList<Integer> list = new ArrayList<>(possibleValues.get(ch));
list.remove((Object) val);
possibleValues.replace(ch, list);

if (list.size() == 0) {
throw new UnsolvablePuzzleException();
}
if (list.size() == 1) {
removeFromAllWithoutGiven(list.get(0), ch);
}
}

// The leading digit of a multi-digit number must not be zero.
void removeLeadingZero(List<String> terms, String result) throws UnsolvablePuzzleException {
remove(result.charAt(0), 0);
for (char ch : terms.stream().map(t -> t.charAt(0)).distinct().collect(Collectors.toList())) {
remove(ch, 0);
}
}

void checkFirstLetterInResult(List<String> terms, String result) throws UnsolvablePuzzleException {
String max = terms.stream().mapToLong(t -> (long) Math.pow(10, t.length())).sum() + "";
if (max.length() > result.length()) {
return;
}

if (max.startsWith("1")) {
setOne(result.charAt(0));
} else {
for (int i = Character.getNumericValue(max.charAt(0)) + 1; i < 10; i++) {
remove(result.charAt(0), i);
}
}
}

// Set the only possible value for the character.
private void setOne(char ch) throws UnsolvablePuzzleException {
possibleValues.remove(ch);
possibleValues.put(ch, Collections.singletonList(1));
removeFromAllWithoutGiven(1, ch);
}

private void removeFromAllWithoutGiven(int value, char ch) throws UnsolvablePuzzleException {
for (char key : possibleValues.keySet()) {
if (key == ch) {
continue;
}
remove(key, value);
}
}
}``````