Avatar of birlibirloque

birlibirloque's solution

to Alphametics in the Java Track

Published at May 12 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());
    }
}
import java.util.*;
import java.util.stream.Stream;

public class Alphametics {

    private final String                            sum;
    private final String[]                          addends;
    private       LinkedHashMap<Character, Integer> decoder = new LinkedHashMap<>();
    private boolean solve = false;

    public Alphametics(String puzzle) throws UnsolvablePuzzleException {

        this.sum = puzzle.split(" == ")[1];
        this.addends = puzzle.split(" == ")[0].split(" \\+ ");

        checkIdentity();
        checkLeadingZero();
        createDecoder(puzzle);
    }

    private void checkIdentity() throws UnsolvablePuzzleException {
        if ((addends.length == 1) && (!sum.equals(addends[0])))
            throw new UnsolvablePuzzleException();
    }

    private void checkLeadingZero() throws UnsolvablePuzzleException {
        if (Stream.of(this.addends).anyMatch(addend -> addend.length() > this.sum.length())) {
            throw new UnsolvablePuzzleException();
        }
    }

    private void createDecoder(String puzzle) {
        puzzle.codePoints()
                .filter(Character::isLetter)
                .forEach(c -> decoder.put((char) c, 0));
    }

    public LinkedHashMap<Character, Integer> solve() throws UnsolvablePuzzleException {

        int[] digits = {0,1,2,3,4,5,6,7,8,9};
        if (!checkCombinations(digits, decoder.size(), 0, new int [decoder.size()])) {
            throw new UnsolvablePuzzleException();
        }
        return decoder;
    }

    private boolean checkCombinations(int[] arr, int len, int startPosition, int[] combination) {
        if (len == 0){
            return (checkPermutations(Arrays.copyOf(combination, combination.length), combination.length));
        }
        for (int i = startPosition; i <= arr.length-len; i++){
            combination[combination.length - len] = arr[i];
            if (checkCombinations(arr, len-1, i+1, combination))
                return true;
        }
        return false;
    }

    private boolean checkPermutations(int[] a, int size)
    {
        if (size == 1) {

            loadDecoderWith(a);
            return isResolve();
        }

        for (int i=0; i<size && !solve; i++)
        {
            if (checkPermutations(a, size-1))
                return true;

            if (size % 2 == 1)
            {
                int temp = a[0];
                a[0] = a[size-1];
                a[size-1] = temp;
            }

            else
            {
                int temp = a[i];
                a[i] = a[size-1];
                a[size-1] = temp;
            }
        }
        return false;
    }

    private void loadDecoderWith(int[] a) {
        int i = 0;
        for (Character k : decoder.keySet()){
            decoder.replace(k, a[i++]);
        }
    }

    private boolean isResolve() {
        return decodeAddends(this.addends).equals(decodeNumber(this.sum));
    }

    private Long decodeAddends(String[] numbers) {
        Long sum = 0L;
        for (String number : numbers) {
            Long addend = this.decodeNumber(number);
            if (addend < 0) break;
            sum += addend;
        }
        return sum;
    }

    private Long decodeNumber(String number) {
        String decoded = number.chars()
                .mapToObj(c -> (char)c)
                .map(decoder::get)
                .map(String::valueOf)
                .reduce("", String::concat);

        if (decoded.startsWith("0")) {
            return -1L;
        }
        return Long.valueOf(decoded);
    }
}

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?