Avatar of argonauta

argonauta's solution

to Alphametics in the Java Track

Published at May 23 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.

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 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

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */


import java.util.LinkedHashMap;

/**
 *
 * @author janpierarmijos
 */
public class Alphametics {
     private String chair;

       char[] s1 = new char[10];
        char[] s2 = new char[10];
        char[] s3 = new char[10];
        int[] assinged = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        char[] c = new char[11];

        int[] val = new int[11];
        int topc = 0;
    
    
    public Alphametics(String chair) {
        this.chair = chair;
    }

    public Alphametics() {
    }
    
    char [] getLetters(String letters){
       String acum="";
       
       while (letters.length()!=0) {  
           String ca=letters.substring(0, 1);
           acum+=ca;
           letters=letters.replaceAll(ca, "");
       }
     
       char [] caracter=acum.toCharArray();
       
       return caracter;
   }
    
    LinkedHashMap<Character, Integer>  btn_ok_Click(){
        LinkedHashMap<Character, Integer> ans=new LinkedHashMap<>();
        String temp=chair.replaceAll("[\\s+==]", "");
        c=this.getLetters(temp);
        topc=c.length;
         if (solve(0, assinged)==1)
            {
                for(int i=0;i<c.length;i++)
              
               // System.out.println(c[i]+"--->"+val[i]);
                    ans.put(c[i], val[i]);
            }
            /*else
            
         System.out.println("Sorry");*/
            return ans;
    }
    
    
    

     int solve(int ind,int []temp1) {
         int [] temp2 = new int[10];
	        int flag=0;
                exit :
	        for(int i=0;i<10;i++)
	        {
		        if(temp1[i]==0)
		        {
		            for(int j=0;j<10;j++)
			            temp2[j]=temp1[j];
	                temp2[i]=1;
	                val[ind]=i;
	                if(ind==(c.length-1))
	                {
		                if(verify()==1)
			            {
			                flag=1;
			                //goto exit;
                                        break;
			            }
	                }
	                else
	                {
                        if(solve(ind+1,temp2)==1)
                        {
		                    flag=1;
		                    break;
                        }
                    }
	            }
            }

            if(flag!=0)
	            return 1;
            else
	            return 0;
    }

    private int verify() {
         int ans=0,s=0;
             String g=chair.replaceAll("[\\s]", "");
      
       String [] letters=g.split("==");
       String [] sum=letters[0].split("[+]");
       String resul=letters[1];
       
       for (int i = 0; i < sum.length; i++) {
           String string = sum[i];
           s+=converToNum(string);
           
       }
       int y=converToNum(resul);
       // System.out.println(s+"  "+y);
            if(s==y)
	       ans=1;
			
            return ans;
    }
    
    
     int converToNum(String cadena){
            int y=0;
            s1=cadena.toCharArray();
            long power=1;
	        char ch;
	        int i=cadena.length()-1;
	        int in1;
         int n1 = 0;
	        while(i>=0)
		    {
		        ch=s1[i];
		        in1=0;
		        while(in1!=c.length)
		        {
		            if(c[in1]==ch)
			       		break;
		            else
			        	in1++;
		        }
			    n1+=power*val[in1];
			    power *=10;
			    i--;
		    }
                return n1;
        }
        
     
     
     /* public static void main(String [] args){
        /* 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").btn_ok_Click();*/
     //}
}

src/main/java/Alphametrics.java

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */


import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Random;
import java.util.Stack;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 *
 * @author janpierarmijos
 */
public class Alphametrics {
    
     LinkedHashMap<Character, Integer>  ans=new LinkedHashMap<>(); 
    char [] ver;
     private String chair;

      int comp;

     
     char[] c = new char[11];

    public Alphametrics(String chair) {
        this.chair = chair;
    }

    public Alphametrics() {
    }
      
    
     char [] getLetters(String letters){
       String acum="";
       
       while (letters.length()!=0) {  
           String ca=letters.substring(0, 1);
           acum+=ca;
           letters=letters.replaceAll(ca, "");
       }
     
       char [] caracter=acum.toCharArray();
       
       return caracter;
       }
     
     
     
     void btn_ok_Click() throws UnsolvablePuzzleException{
        String temp=chair.replaceAll("[\\s+==]", "");
        c=this.getLetters(temp);
       
      
         for (int i = 0; i < c.length; i++) {
             char d = c[i];
             ans.put(d, 0);
         }
        
         String temp2=chair.replaceAll("\\s", "");
        String [] h=temp2.split("==");
         String [] cont=h[0].split("[+]");
         String resul=h[1];
         
         if (cont.length==1 || (cont.length<resul.length())) {
            throw new UnsolvablePuzzleException();
         }
         
         
         
         if (this.thereAreResidue(resul, cont)==true) {
            ver=resul.toCharArray();
             ans.put(ver[0], 1);
             ans.put(ver[1],0);
             
             while (this.compobar(cont, resul)!=1) {             
              this.fillHashMap();
         }
         }else if (ver==null){
             
            // while (this.compobar(cont, resul)!=1 && comp!=0) {             
             // this.fillHashMap2();
        // }
        
        ans=new Alphametics(chair).btn_ok_Click();
        /*for (Map.Entry<Character, Integer> entry : ans.entrySet()) {
                 Character key = entry.getKey();
                 Integer value = entry.getValue();
                 System.out.println(key+"------>"+value);
                 
             }*/
         }
             
        // System.out.println(comp);
      
        
         if (this.compobar(cont, resul)==1) {
             for (Map.Entry<Character, Integer> entry : ans.entrySet()) {
                 Character key = entry.getKey();
                 Integer value = entry.getValue();
                 System.out.println(key+"------>"+value);
                 
             }
              
         }
        
    }
     
     
        void fillHashMap(){
            int u=9;
            int pos=1;
            
            if (ver.length>0) {
                 u=7;
                 pos=2;
            }
            
    int nCartas = 9;
    Stack < Integer > pCartas = new Stack <> ();
   /* for (int i = 0; i <nCartas ; i++) {
      pos = (int) Math.floor(Math.random() * nCartas )+1;
      while (pCartas.contains(pos)) {
        pos = (int) Math.floor(Math.random() * nCartas )+1;
      }
        
              pCartas.push(pos);
     
    }*/
    
   Random random = new Random();
    
            while (pCartas.size()!=u) {                
                 int randomInteger = pos+random.nextInt(9);
                if (!pCartas.contains(randomInteger)) {
                     pCartas.push(randomInteger);
                }
            }


  
            for (Map.Entry<Character, Integer> entry : ans.entrySet()) {
                Character key = entry.getKey();
              // cont++;
             
                if (ver.length>0) {
                    if (!key.equals(ver[0]) && !key.equals(ver[1]) ) {
                        ans.put(key, pCartas.pop());
                        
                    }
                    
                    
                } else {
                    ans.put(key, pCartas.pop());
                    
                }
                
            }
   
        }
     
     
        
         
        void fillHashMap2(){
            int u=9;
            int pos;
            
       
            
    int nCartas = 9;
    Stack < Integer > pCartas = new Stack <> ();
    for (int i = 0; i <nCartas ; i++) {
      pos = (int) Math.floor(Math.random() * nCartas )+1;
      while (pCartas.contains(pos)) {
        pos = (int) Math.floor(Math.random() * nCartas )+1;
      }
        comp=pos;
        pCartas.push(pos);
     
    }
    


         
  
            for (Map.Entry<Character, Integer> entry : ans.entrySet()) {
                Character key = entry.getKey();
              ans.put(key, pCartas.pop());
             }
   
        }
     
     
        
        
        
     
        boolean thereAreResidue(String resul,String [] cont){
         boolean flag=true;
         for (int i = 0; i < cont.length; i++) {
           
             if (cont[i].length()==resul.length()) {
                flag=false;
                 break;
                  
             }
             
         }
         return flag;
     }
        
        
       int compobar(String [] cont,String resul) {
         
          int subtotal=0,total=0;
           
           for (String string : cont) {
               subtotal+=returnNumber(string);
           }
          
              total= returnNumber(resul);   
           if (subtotal==total) {
               return 1;
           } else {
               return 0;
           }
 
    }
      
       
         private int returnNumber(String resul) {
             int cant=0;
             long power=1;
             char [] can=resul.toCharArray();
             
             for (int i = can.length-1; i>=0; i--) {
                
                 cant+=power*ans.get(can[i]);
                 power*=10;
             }
             
             return cant;
             
    }
        
    public static void main(String [] args){
         try {
             new Alphametrics("AND + A + STRONG + OFFENSE + AS + A + GOOD == DEFENSE").btn_ok_Click();
         } catch (UnsolvablePuzzleException ex) {
             Logger.getLogger(Alphametrics.class.getName()).log(Level.SEVERE, null, ex);
         }
            
     
     } 

   
    
}

src/main/java/UnsolvablePuzzleException.java

class UnsolvablePuzzleException extends Exception {
	public UnsolvablePuzzleException() {
        super();
    }
}

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?