Avatar of boris-lenzinger

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 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.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
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
     */
    void add(Integer value) {
        this.representation.add(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
 * to not melt with "business" code and breaks readibility.
 *
 */
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();
                combination.add(list.get(i));
                result.add(combination);
            } else {
                for (int j = 0; j < subchoices.size(); j++) {
                    subchoices.get(j).add(list.get(i));
                    result.add(subchoices.get(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.
     */
    void addSolution(Solution s) {
        String fingerprint = s.fingerprint();
        if (!this.fingerprints.containsKey(fingerprint)) {
            this.fingerprints.put(fingerprint, new Short((short) 1));
            this.representation.add(s);
        }
    }

    /**
     * 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++) {
                addSolution(l.get(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)) {
                newsolutions.addSolution(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++) {
                        candidateSolution.addIdentifiedLetter(uniqLettersWithNoValue.get(j), permutation.get(j));
                    }
                    for (int j = 0; j < uniqLettersWithNoValue.size(); j++) {
                        Character letter = uniqLettersWithNoValue.get(j);
                        if (lettersThatMustNotBeZero.contains(letter) && candidateSolution.valueFor(letter) == 0) {
                            // this solution is discarded
                            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)) {
                        newsolutions.addSolution(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
     * of the equal sign in the input.
     */
    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[0].trim();
        result = partsOfEquation[1].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) {
            cannotBeZero.add(word.charAt(0));
        }
        cannotBeZero.add(result.charAt(0));
    }

    /**
     * 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) {
                letters.add(w.charAt(wordLength - index));
            }
        }
        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());
        Set<Character> lettersSet = new HashSet<>(allChars);
        if (lettersSet.size() > 10) {
            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
        solutionsFromPreviousEquation.addSolution(new Solution());
        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();
        }
        return new LinkedHashMap<>(solutionsFromPreviousEquation.representation.get(0).representation);
    }

    /**
     * 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;
    }

}

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?