Generating from binary recursion, we use multiple recursion when a method may ma
ID: 3674806 • Letter: G
Question
Generating from binary recursion, we use multiple recursion when a method may
make multiple recursive calls, with that number potentially being more than two.
One of the most common applications of this type of recursion is used when we
want to enumerate various configurations in order to solve a combinatorial puzzle.
For example, the following are all instances of summation puzzles :
pot + pan = bib
dog + cat = pig
boy + girl = baby
To solve such a puzzle, we need to assign a unique digit (that is, 0; 1; ; 9)
to each (case-insensitive) letter in the equation, in order to make the equation true.
Write a Java program with multiple recursion for solving summation puzzles by
enumerating and testing all possible configurations.
Implement the ordered lists, as discussed in Algorithm PuzzleSolve(k; S;U)
as singly linked lists. Name your main class PuzzleSolve, in which a puzzle instance is read from stdin (in one line) and configurations
satisfying the puzzle are output to stdout. If no configuration satisfies
the input puzzle instance, output via stdout that no solution exists. Those equations
where such a digit assignment is not possible are also considered without a solution.
Sample Input and Output
To invoke the program:
java PuzzleSolve.class
Sample Input: (one line only)
a + a = b EOF
The EOF character can be typed by D or Z (on Windows).
Output format:
(Print to console, for example, using System.out.println())
The 1st line: unique letters in the equation in any order.
The 2nd line: digits assigned to the letters (the first solution)
The 3rd line: the 2nd solution (if any)
One additional line for each alternative solution.
In case no solution exists, PuzzleSolve simply outputs the first line (the
unique letters, may be more than 10 letters).
Expected Output with the above input:
Possible output 1
ab
12
24
36
48
Possible output 2
ba
21
42
63
84
Explanation / Answer
puzzleSolve.java
import java.util.*;
public class puzzleSolve
{
private SinglyLinkedList _uniqueLetters;
private String[] _words;
private SinglyLinkedList _numberAssignment;
private SinglyLinkedList _numberList;
private String _combinedString;
/*
* Takes the input from the user, determines the number of unique letters in the equation,
* makes sure there are no more than 10 unique letters for the 10 digits, prints out the
* unique letters, creates a linked list of the 10 digits and a blank list for the number
* assignments, then passes the number of unique letters, the digit list, and the blank list
* to the recursiveSolver method.
*/
public void puzzleSolve(String puzzle)
{
_words = puzzle.split("[\+=]"); //split for any operand
for(int i = 0; i < _words.length; i++)
{
_words[i] = _words[i].trim(); //get rid of whitespace
}
_combinedString = puzzle;
_uniqueLetters = new SinglyLinkedList();
boolean[] alphabet = new boolean[26];
for(int i = 0; i < alphabet.length; i++)
{
alphabet[i] = false;
}
for(int i = 0; i < _combinedString.length(); i++)
{
if(_combinedString.charAt(i) >= 'a' && _combinedString.charAt(i) <= 'z')
{ //ignores operands
int index = _combinedString.charAt(i) - 'a';
if(!alphabet[index])
{
alphabet[index] = true;
Node newLetter = new Node(_combinedString.charAt(i), null);
_uniqueLetters.addLast(newLetter);
}
}
}
// check if we have too many unique letters
if (_uniqueLetters.getSize()> 10)
{
System.out.println(_uniqueLetters);
System.exit(0);
}
// print the alphabet
System.out.println(_uniqueLetters);
// initial list of unused digits
_numberList = new SinglyLinkedList();
for (int k = 0; k < 10; k++)
{
Node data = new Node(k);
_numberList.addLast(data);
}
//make sure _numberAssignments is an empty list
_numberAssignment = new SinglyLinkedList();
// run recursive solver
recursiveSolver((int) _uniqueLetters.getSize(), _numberAssignment, _numberList);
}
/*
* Utilizes recursion to find if a certain order of numbers satisfies the word
* equation when the digits are assigned to their letters. Uses recursion down
* to a depth k dependent on the number of unique letters to assign an order of
* numbers from the digits list to the initially empty list of number assignments.
*/
public void recursiveSolver(int k, SinglyLinkedList numberAssignment,
SinglyLinkedList digitList)
{
if (k == 0)
{
evaluate(numberAssignment);
return;
}
else
{
int numChoices = digitList.getSize();
for(int i = 0; i < numChoices; i++ )
{
Node tempNode = digitList.removeFirst();
//Node lastAssignedNode = numberAssignment._tail;
numberAssignment.addFirst(tempNode);
// recurse
recursiveSolver(k-1, numberAssignment, digitList);
// fix the lists
tempNode = numberAssignment.removeFirst();
digitList.addLast(tempNode);
}
}
}
/*
* Tests to see if the given order of number assignments satisfies the word equation
* by replacing the letters in the equation with their assigned values by stepping through
* each node and then splits the number chunks by the operands. These chunks of strings are
* then converted into their integer values and tested to see if the sum on the left side
* is equal to the number chunk on the right side. If there's equality, print that solution.
*/
public void evaluate(SinglyLinkedList assignment)
{
//_numberAssignment/digitNode is not equalling _numberList
String digitString = _combinedString;
// replace all letters with digits
Node digitNode = assignment._head, letterNode = _uniqueLetters._head; //assignment's head is 1 less than it should be
for ( ; digitNode != null && letterNode != null; )
{
String letter = "" + letterNode.getElement();
String digit = "" + digitNode.getElement();
// replace all instances of leter in _combinedString with digit
digitString = digitString.replaceAll(letter, digit);
// next iteration
digitNode = digitNode.getNext(); //digit is 1 less than what it should be
letterNode = letterNode.getNext();
}
// split the equation into chunks of numbers
String[] numberAsStringArray = digitString.split("[\+=]");
int[] numberAsIntegerArray = new int[numberAsStringArray.length];
int sum = 0, lastPartValue = 0;
for(int i = 0; i < numberAsStringArray.length; i++)
{
numberAsIntegerArray[i] = (int) Integer.parseInt(numberAsStringArray[i].trim());
if(i == numberAsStringArray.length - 1)
{
// the last part
lastPartValue = numberAsIntegerArray[i];
}
else
{
// not the last part
sum += numberAsIntegerArray[i];
}
}
// check if the sum equals the last part
if(sum == lastPartValue)
{
// System.out.println("Solution found: ");
System.out.println(_numberAssignment);
}
}
// main method
public static void main(String[] args)
{
puzzleSolve ps = new puzzleSolve();
Scanner input = new Scanner(System.in);
System.out.println("Enter puzzle:");
String puzzle = input.nextLine();
ps.puzzleSolve(puzzle);
input.close();
}
}
Node.java
public class Node
{
private Object _element;
private Node _next;
public Node()
{
this(null, null);
}
public Node(Object element)
{
this(element, null);
}
public Node(Object element, Node next)
{
_element = element;
_next = next;
}
public Node getNext()
{
return _next;
}
public Object getElement()
{
return _element;
}
public void setNext(Node newNext)
{
_next = newNext;
}
public void setElement(Object element)
{
_element = element;
}
}
SinglyLinkedList.java
public class SinglyLinkedList
{
protected Node _tail;
protected Node _head;
protected int _size;
public SinglyLinkedList()
{
_tail = null;
_head = null;
_size = 0;
}
public int getSize()
{
return _size;
}
@Override
public String toString()
{
String result = "";
Node tempNode = this._head;
while (tempNode != null)
{
result = result + tempNode.getElement();
tempNode = tempNode.getNext();
}
return result;
}
public void addLast(Node data)
{
if (_tail == null)
{
data.setNext(null);
_head = _tail = data;
}
else
{
_tail.setNext(data);
_tail = data;
data.setNext(null);
}
_size++;
}
public void addFirst(Node data)
{
if (_head == null)
{
_head = _tail = data;
data.setNext(null);
}
else
{
data.setNext(_head);
_head = data;
}
}
public Node removeFirst()
{
Node tempNode = _head;
_head = _head.getNext();
_size--;
return tempNode;
}
}
output
Enter puzzle:
a + a = b
ab
12
24
36
48
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.