Avatar of clechasseur

clechasseur's solution

to Alphametics in the Java Track

Published at Jul 09 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 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 testTwoDigitsFinalCarry() throws UnsolvablePuzzleException {
        LinkedHashMap<Character, Integer> expected = new LinkedHashMap<>();
        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 {
        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());
    }
}
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Alphametics {
    private static final List<List<Integer>> INT_PERMUTATIONS = PermutationsHelper.getAllIntPermutations();

    private final Puzzle puzzle;

    Alphametics(String puzzle) {
        this.puzzle = new Puzzle(puzzle);
    }

    Map<Character, Integer> solve() throws UnsolvablePuzzleException {
        List<Map<Character, Integer>> permutations = getPermutations(this.puzzle.getLetters(), this.puzzle.getEdgeLetters());
        for (Map<Character, Integer> permutation : permutations) {
            if (this.puzzle.solve(permutation)) {
                return permutation;
            }
        }
        throw new UnsolvablePuzzleException();
    }

    private List<Map<Character, Integer>> getPermutations(Set<Character> letters, Set<Character> edgeLetters) {
        List<Map<Character, Integer>> permutations = new ArrayList<>();
        INT_PERMUTATIONS.forEach(intPermutation -> {
            SortedMap<Character, Integer> permutation = new TreeMap<>();
            int i = 0;
            for (Character c : letters) {
                permutation.put(c, intPermutation.get(i++));
            }
            if (isValidPermutation(permutation, edgeLetters)) {
                permutations.add(permutation);
            }
        });
        return permutations;
    }

    private boolean isValidPermutation(Map<Character, Integer> permutation, Set<Character> edgeLetters) {
        for (Character c : edgeLetters) {
            if (permutation.get(c) == 0) {
                return false;
            }
        }
        return true;
    }

    private static class Puzzle {
        private final List<String> leftSide = new ArrayList<>();
        private final String rightSide;
        private final Set<Character> letters = new HashSet<>();
        private final Set<Character> edgeLetters = new HashSet<>();

        Puzzle(String puzzle) {
            // Ultra-non-generic parsing Inc. (tm)
            Pattern pattern = Pattern.compile("[A-Z]+");
            Matcher matcher = pattern.matcher(puzzle);
            while (matcher.find()) {
                String block = matcher.group();
                edgeLetters.add(block.charAt(0));
                for (int i = 0; i < block.length(); ++i) {
                    letters.add(block.charAt(i));
                }
                leftSide.add(block);
            }
            if (!leftSide.isEmpty()) {
                rightSide = leftSide.remove(leftSide.size() - 1);
            } else {
                rightSide = "";
            }
        }

        Set<Character> getLetters() {
            return this.letters;
        }

        Set<Character> getEdgeLetters() {
            return this.edgeLetters;
        }

        boolean solve(Map<Character, Integer> permutation) {
            long leftTotal = 0;
            for (String block : this.leftSide) {
                leftTotal += getBlockTotal(block, permutation);
            }
            long rightTotal = getBlockTotal(this.rightSide, permutation);
            return leftTotal == rightTotal;
        }

        private long getBlockTotal(String block, Map<Character, Integer> permutation) {
            StringBuilder sb = new StringBuilder();
            for (char c : block.toCharArray()) {
                sb.append(permutation.get(c));
            }
            return Long.valueOf(sb.toString());
        }
    }

    private static class PermutationsHelper {
        static List<List<Integer>> getAllIntPermutations() {
            List<Integer> arr = new ArrayList<>();
            for (int i = 0; i <= 9; ++i) {
                arr.add(i);
            }
            List<List<Integer>> allPermutations = new ArrayList<>();
            permute(arr, 0, allPermutations);
            return allPermutations;
        }

        // Taken from https://stackoverflow.com/questions/2920315/permutation-of-array
        private static void permute(List<Integer> arr, int k, List<List<Integer>> allPermutations) {
            for (int i = k; i < arr.size(); i++) {
                Collections.swap(arr, i, k);
                permute(arr, k + 1, allPermutations);
                Collections.swap(arr, k, i);
            }
            if (k == arr.size() - 1 ){
                allPermutations.add(new ArrayList<>(arr));
            }
        }
    }
}

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?