Avatar of artemkorsakov

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

in your terminal.

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 java.util.LinkedHashMap;

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 {
        LinkedHashMap<Character, Integer> expected = new LinkedHashMap<>();
        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 {
        LinkedHashMap<Character, Integer> expected = new LinkedHashMap<>();
        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 {
        LinkedHashMap<Character, Integer> expected = new LinkedHashMap<>();
        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 {
        LinkedHashMap<Character, Integer> expected = new LinkedHashMap<>();
        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 {
        LinkedHashMap<Character, Integer> expected = new LinkedHashMap<>();
        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 {
        LinkedHashMap<Character, Integer> expected = new LinkedHashMap<>();
        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 {
        LinkedHashMap<Character, Integer> expected = new LinkedHashMap<>();
        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()) {
            unique.add(c);
        }
        PossibleValues possibleValues = new PossibleValues(new ArrayList<>(unique));
        possibleValues.removeLeadingZero(terms, result);
        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() {
        LinkedHashMap<Character, Integer> result = new LinkedHashMap<>();
        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) {
                    LinkedHashMap<Character, Integer> tmp = new LinkedHashMap<>();
                    tmp.put(key, value);
                    result.add(tmp);
                }
            } 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 {
                            LinkedHashMap<Character, Integer> newDictionary = new LinkedHashMap<>(curDic);
                            newDictionary.remove(key);
                            newDictionary.put(key, curValue);
                            tmp.add(newDictionary);
                        }
                    }
                }
                result.addAll(tmp);
            }
        }

        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);
        }
    }
}

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?