Cryptarithmetic puzzle
Cryptarithmetic, also known as alphametics or cryptarithms, is a type of mathematical puzzle where mathematical operations are represented by letters or symbols. The goal of the puzzle is to find the numerical values that each letter or symbol represents, so that the mathematical equation is true.
In a typical cryptarithmetic puzzle, a set of letters or symbols represent digits in a simple arithmetic equation. For example, the letters A, B, and C might represent the digits 2, 5, and 7 respectively. The puzzle would then be to find the value of the expression "AB + C" which would be equivalent to a known value, say 19.
The challenge in solving a cryptarithmetic puzzle is to find the correct assignment of digits to letters, so that the arithmetic expression is valid. This is usually done through a process of trial and error, by testing different combinations of digits until a solution is found.
Code Solution
/*
C program for
Cryptarithmetic puzzle
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Define node which is contain letter and resultant value
struct Node
{
char letter;
int value;
};
//
int isValid(struct Node *result, int count , const char *s1 , const char *s2 , const char *s3)
{
int v1 = 0;
int v2 = 0;
int v3 = 0;
// Loop controlling variables
int i = 0;
int j = 0;
int multiplier = 1;
for (i = strlen(s1) - 1; i >= 0; i--)
{
j = 0;
while (j < count && result[j].letter != s1[i])
{
j++;
}
v1 = v1 + multiplier *result[j].value;
multiplier *= 10;
}
multiplier = 1;
for (i = strlen(s2) - 1; i >= 0; i--)
{
j = 0;
while (j < count && result[j].letter != s2[i])
{
j++;
}
v2 = v2 + multiplier *result[j].value;
multiplier *= 10;
}
multiplier = 1;
for (i = strlen(s3) - 1; i >= 0; i--)
{
j = 0;
while (j < count && result[j].letter != s3[i])
{
j++;
}
v3 = v3 + multiplier *result[j].value;
multiplier *= 10;
}
if (v3 == (v1 + v2))
{
return 1;
}
else
{
return 0;
}
}
// Find solution
int permutation(int count, int use[], struct Node *result, int n , const char *s1 , const char *s2 , const char *s3)
{
// Loop controlling variables
int i = 0;
int j = 0;
if (n == count - 1)
{
for (i = 0; i < 10; i++)
{
if (use[i] == 0)
{
result[n].value = i;
if (isValid(result, count, s1, s2, s3) == 1)
{
return 1;
}
}
}
return 0;
}
for (i = 0; i < 10; i++)
{
if (use[i] == 0)
{
result[n].value = i;
use[i] = 1;
if (permutation(count, use, result, n + 1, s1, s2, s3) == 1)
{
// When get a result
return 1;
}
use[i] = 0;
}
}
return 0;
}
// Calculate the frequency of character
void frequency(int freq[] , const char *str)
{
int i = 0;
int len = strlen(str);
// Calculate character frequency of givens const char *
for (i = 0; i < len; i++)
{
freq[str[i] - 'A']++;
}
}
// Cryptarithmetic handles requests to solve puzzles
void cryptarithmeticPuzzle(const char *s1 , const char *s2 , const char *s3)
{
// Use to count frequency of each character
int freq[26];
// Use to count of unique characters
int count = 0;
// Loop controlling variables
int i = 0;
int j = 0;
// Set initial frequency
for (i = 0; i < 26; i++)
{
freq[i] = 0;
}
// Count frequency of each character in a given const char *( form of A-Z).
frequency(freq, s1);
frequency(freq, s2);
frequency(freq, s3);
// Count the number of repeating elements
for (i = 0; i < 26; i++)
{
if (freq[i] > 0)
{
// When element occurrences
count++;
}
}
if (count > 10)
{
// When string are not valid
printf("Invalid string");
}
else
{
// Use to track numbers
int use[10];
struct Node *result = (struct Node *) malloc(sizeof(struct Node) *count);
for (i = 0, j = 0; i < 26; i++)
{
if (freq[i] > 0)
{
// Set node value
result[j].letter = i + 'A';
result[j].value = 0;
// visit to next node
j++;
}
}
// Set initial values
for (i = 0; i < count; ++i)
{
// Here zero indicate empty slot
use[i] = 0;
}
if (permutation(count, use, result, 0, s1, s2, s3) == 1)
{
printf(" Given : %s %s %s \n",s1,s2,s3);
printf(" Solution \n");
// Display solution
for (j = 0; j < count; j++)
{
printf(" %c = %d ", result[j].letter, result[j].value);
}
}
else
{
// When no solution
printf("No Result");
}
free(result);
result = NULL;
}
}
int main()
{
const char *s1 = "SUN";
const char *s2 = "RUN";
const char *s3 = "FAST";
// Test
cryptarithmeticPuzzle(s1, s2, s3);
}
Output
Given : SUN RUN FAST
Solution
A = 0 F = 1 N = 2 R = 3 S = 6 T = 4 U = 8
/*
Java Program for
Cryptarithmetic puzzle
*/
// Define node which is contain letter and resultant value
class Node
{
public char letter;
public int value;
public Node()
{
this.letter = ' ';
this.value = 0;
}
};
// Binary Tree
public class Puzzle
{
public boolean isValid(Node[] result, int count, String s1, String s2, String s3)
{
int v1 = 0;
int v2 = 0;
int v3 = 0;
// Loop controlling variables
int i = 0;
int j = 0;
int multiplier = 1;
for (i = s1.length() - 1; i >= 0; i--)
{
j = 0;
while (j < count && result[j].letter != s1.charAt(i))
{
j++;
}
v1 = v1 + multiplier * result[j].value;
multiplier *= 10;
}
multiplier = 1;
for (i = s2.length() - 1; i >= 0; i--)
{
j = 0;
while (j < count && result[j].letter != s2.charAt(i))
{
j++;
}
v2 = v2 + multiplier * result[j].value;
multiplier *= 10;
}
multiplier = 1;
for (i = s3.length() - 1; i >= 0; i--)
{
j = 0;
while (j < count && result[j].letter != s3.charAt(i))
{
j++;
}
v3 = v3 + multiplier * result[j].value;
multiplier *= 10;
}
if (v3 == (v1 + v2))
{
return true;
}
else
{
return false;
}
}
// Find solution
public boolean permutation(int count, boolean[] use, Node[] result, int n, String s1, String s2, String s3)
{
// Loop controlling variables
int i = 0;
int j = 0;
if (n == count - 1)
{
for (i = 0; i < 10; i++)
{
if (use[i] == false)
{
result[n].value = i;
if (isValid(result, count, s1, s2, s3) == true)
{
return true;
}
}
}
return false;
}
for (i = 0; i < 10; i++)
{
if (use[i] == false)
{
result[n].value = i;
use[i] = true;
if (permutation(count, use, result, n + 1, s1, s2, s3) == true)
{
// When get a result
return true;
}
use[i] = false;
}
}
return false;
}
// Calculate the frequency of character
public void frequency(int[] freq, String str)
{
int i = 0;
int len = str.length();
// Calculate character frequency of givens String *
for (i = 0; i < len; i++)
{
freq[str.charAt(i) - 'A']++;
}
}
// Cryptarithmetic handles requests to solve puzzles
public void cryptarithmeticPuzzle(String s1, String s2, String s3)
{
// Use to count frequency of each character
int[] freq = new int[26];
// Use to count of unique characters
int count = 0;
// Loop controlling variables
int i = 0;
int j = 0;
// Set initial frequency
for (i = 0; i < 26; i++)
{
freq[i] = 0;
}
// Count frequency of each character in a given String *( form of A-Z).
frequency(freq, s1);
frequency(freq, s2);
frequency(freq, s3);
// Count the number of repeating elements
for (i = 0; i < 26; i++)
{
if (freq[i] > 0)
{
// When element occurrences
count++;
}
}
if (count > 10)
{
// When string are not valid
System.out.print("Invalid string");
}
else
{
// Use to track numbers
boolean[] use = new boolean[10];
Node[] result = new Node[count];
for (i = 0; i < count; i++)
{
result[i] = new Node();
}
for (i = 0, j = 0; i < 26; i++)
{
if (freq[i] > 0)
{
// Set node value
result[j].letter = (char)(i + 'A');
result[j].value = 0;
// visit to next node
j++;
}
}
// Set initial values
for (i = 0; i < count; ++i)
{
// Here zero indicate empty slot
use[i] = false;
}
if (permutation(count, use, result, 0, s1, s2, s3) == true)
{
System.out.print(" Given : " + s1 + " " + s2 + " " + s3 + " \n");
System.out.print(" Solution \n");
// Display solution
for (j = 0; j < count; j++)
{
System.out.print(" " + result[j].letter + " = " + result[j].value);
}
}
else
{
// When no solution
System.out.print("No Result");
}
}
}
public static void main(String[] args)
{
Puzzle task = new Puzzle();
String s1 = "SUN";
String s2 = "RUN";
String s3 = "FAST";
// Test
task.cryptarithmeticPuzzle(s1, s2, s3);
}
}
Output
Given : SUN RUN FAST
Solution
A = 0 F = 1 N = 2 R = 3 S = 6 T = 4 U = 8
// Include header file
#include <iostream>
#include<string.h>
using namespace std;
/*
C++ Program for
Cryptarithmetic puzzle
*/
// Define node which is contain letter and resultant value
class Node
{
public:
char letter;
int value;
Node()
{
this->letter = ' ';
this->value = 0;
}
};;
// Binary Tree
class Puzzle
{
public: bool isValid(Node result[], int count, string s1, string s2, string s3)
{
int v1 = 0;
int v2 = 0;
int v3 = 0;
// Loop controlling variables
int i = 0;
int j = 0;
int multiplier = 1;
for (i = s1.size() - 1; i >= 0; i--)
{
j = 0;
while (j < count && result[j].letter != s1[i])
{
j++;
}
v1 = v1 + multiplier *result[j].value;
multiplier *= 10;
}
multiplier = 1;
for (i = s2.size() - 1; i >= 0; i--)
{
j = 0;
while (j < count && result[j].letter != s2[i])
{
j++;
}
v2 = v2 + multiplier *result[j].value;
multiplier *= 10;
}
multiplier = 1;
for (i = s3.size() - 1; i >= 0; i--)
{
j = 0;
while (j < count && result[j].letter != s3[i])
{
j++;
}
v3 = v3 + multiplier *result[j].value;
multiplier *= 10;
}
if (v3 == (v1 + v2))
{
return true;
}
else
{
return false;
}
}
// Find solution
bool permutation(int count, bool use[], Node result[], int n, string s1, string s2, string s3)
{
// Loop controlling variables
int i = 0;
int j = 0;
if (n == count - 1)
{
for (i = 0; i < 10; i++)
{
if (use[i] == false)
{
result[n].value = i;
if (this->isValid(result, count, s1, s2, s3) == true)
{
return true;
}
}
}
return false;
}
for (i = 0; i < 10; i++)
{
if (use[i] == false)
{
result[n].value = i;
use[i] = true;
if (this->permutation(count, use, result, n + 1, s1, s2, s3) == true)
{
// When get a result
return true;
}
use[i] = false;
}
}
return false;
}
// Calculate the frequency of character
void frequency(int freq[], string str)
{
int i = 0;
int len = str.size();
// Calculate character frequency of givens String *
for (i = 0; i < len; i++)
{
freq[str[i] - 'A']++;
}
}
// Cryptarithmetic handles requests to solve puzzles
void cryptarithmeticPuzzle(string s1, string s2, string s3)
{
// Use to count frequency of each character
int freq[26];
// Use to count of unique characters
int count = 0;
// Loop controlling variables
int i = 0;
int j = 0;
// Set initial frequency
for (i = 0; i < 26; i++)
{
freq[i] = 0;
}
// Count frequency of each character in a given String *( form of A-Z).
this->frequency(freq, s1);
this->frequency(freq, s2);
this->frequency(freq, s3);
// Count the number of repeating elements
for (i = 0; i < 26; i++)
{
if (freq[i] > 0)
{
// When element occurrences
count++;
}
}
if (count > 10)
{
// When string are not valid
cout << "Invalid string";
}
else
{
// Use to track numbers
bool use[10];
Node result[count];
for (i = 0, j = 0; i < 26; i++)
{
if (freq[i] > 0)
{
// visit to next node
// Set node value
result[j].letter = (char)(i + 'A');
result[j].value = 0;
j++;
}
}
// Set initial values
for (i = 0; i < count; ++i)
{
// Here zero indicate empty slot
use[i] = false;
}
if (this->permutation(count, use, result, 0, s1, s2, s3) == true)
{
cout << " Given : " << s1 << " " << s2 << " " << s3 << " \n";
cout << " Solution \n";
// Display solution
for (j = 0; j < count; j++)
{
cout << " " << result[j].letter << " = " << result[j].value;
}
}
else
{
// When no solution
cout << "No Result";
}
}
}
};
int main()
{
Puzzle task = Puzzle();
string s1 = "SUN";
string s2 = "RUN";
string s3 = "FAST";
// Test
task.cryptarithmeticPuzzle(s1, s2, s3);
return 0;
}
Output
Given : SUN RUN FAST
Solution
A = 0 F = 1 N = 2 R = 3 S = 6 T = 4 U = 8
// Include namespace system
using System;
/*
C# Program for
Cryptarithmetic puzzle
*/
// Define node which is contain letter and resultant value
public class Node
{
public char letter;
public int value;
public Node()
{
this.letter = ' ';
this.value = 0;
}
};
// Binary Tree
public class Puzzle
{
public Boolean isValid(Node[] result, int count, String s1, String s2, String s3)
{
int v1 = 0;
int v2 = 0;
int v3 = 0;
// Loop controlling variables
int i = 0;
int j = 0;
int multiplier = 1;
for (i = s1.Length - 1; i >= 0; i--)
{
j = 0;
while (j < count && result[j].letter != s1[i])
{
j++;
}
v1 = v1 + multiplier * result[j].value;
multiplier *= 10;
}
multiplier = 1;
for (i = s2.Length - 1; i >= 0; i--)
{
j = 0;
while (j < count && result[j].letter != s2[i])
{
j++;
}
v2 = v2 + multiplier * result[j].value;
multiplier *= 10;
}
multiplier = 1;
for (i = s3.Length - 1; i >= 0; i--)
{
j = 0;
while (j < count && result[j].letter != s3[i])
{
j++;
}
v3 = v3 + multiplier * result[j].value;
multiplier *= 10;
}
if (v3 == (v1 + v2))
{
return true;
}
else
{
return false;
}
}
// Find solution
public Boolean permutation(int count, Boolean[] use, Node[] result, int n, String s1, String s2, String s3)
{
// Loop controlling variable
int i = 0;
if (n == count - 1)
{
for (i = 0; i < 10; i++)
{
if (use[i] == false)
{
result[n].value = i;
if (isValid(result, count, s1, s2, s3) == true)
{
return true;
}
}
}
return false;
}
for (i = 0; i < 10; i++)
{
if (use[i] == false)
{
result[n].value = i;
use[i] = true;
if (permutation(count, use, result, n + 1, s1, s2, s3) == true)
{
// When get a result
return true;
}
use[i] = false;
}
}
return false;
}
// Calculate the frequency of character
public void frequency(int[] freq, String str)
{
int i = 0;
int len = str.Length;
// Calculate character frequency of givens String *
for (i = 0; i < len; i++)
{
freq[str[i] - 'A']++;
}
}
// Cryptarithmetic handles requests to solve puzzles
public void cryptarithmeticPuzzle(String s1, String s2, String s3)
{
// Use to count frequency of each character
int[] freq = new int[26];
// Use to count of unique characters
int count = 0;
// Loop controlling variables
int i = 0;
int j = 0;
// Set initial frequency
for (i = 0; i < 26; i++)
{
freq[i] = 0;
}
// Count frequency of each character in a given String *( form of A-Z).
frequency(freq, s1);
frequency(freq, s2);
frequency(freq, s3);
// Count the number of repeating elements
for (i = 0; i < 26; i++)
{
if (freq[i] > 0)
{
// When element occurrences
count++;
}
}
if (count > 10)
{
// When string are not valid
Console.Write("Invalid string");
}
else
{
// Use to track numbers
Boolean[] use = new Boolean[10];
Node[] result = new Node[count];
for (i = 0; i < count; i++)
{
result[i] = new Node();
}
for (i = 0, j = 0; i < 26; i++)
{
if (freq[i] > 0)
{
// visit to next node
// Set node value
result[j].letter = (char)(i + 'A');
result[j].value = 0;
j++;
}
}
// Set initial values
for (i = 0; i < count; ++i)
{
// Here zero indicate empty slot
use[i] = false;
}
if (permutation(count, use, result, 0, s1, s2, s3) == true)
{
Console.Write(" Given : " + s1 + " " + s2 + " " + s3 + " \n");
Console.Write(" Solution \n");
// Display solution
for (j = 0; j < count; j++)
{
Console.Write(" " + result[j].letter + " = " + result[j].value);
}
}
else
{
// When no solution
Console.Write("No Result");
}
}
}
public static void Main(String[] args)
{
Puzzle task = new Puzzle();
String s1 = "SUN";
String s2 = "RUN";
String s3 = "FAST";
// Test
task.cryptarithmeticPuzzle(s1, s2, s3);
}
}
Output
Given : SUN RUN FAST
Solution
A = 0 F = 1 N = 2 R = 3 S = 6 T = 4 U = 8
<?php
/*
Php Program for
Cryptarithmetic puzzle
*/
// Define node which is contain letter and resultant value
class Node
{
public $letter;
public $value;
function __construct()
{
$this->letter = ' ';
$this->value = 0;
}
};
// Binary Tree
class Puzzle
{
public function isValid( & $result, $count, $s1, $s2, $s3)
{
$v1 = 0;
$v2 = 0;
$v3 = 0;
// Loop controlling variables
$i = 0;
$j = 0;
$multiplier = 1;
for ($i = strlen($s1) - 1; $i >= 0; $i--)
{
$j = 0;
while ($j < $count && $result[$j]->letter != $s1[$i])
{
$j++;
}
$v1 = $v1 + $multiplier * $result[$j]->value;
$multiplier *= 10;
}
$multiplier = 1;
for ($i = strlen($s2) - 1; $i >= 0; $i--)
{
$j = 0;
while ($j < $count && $result[$j]->letter != $s2[$i])
{
$j++;
}
$v2 = $v2 + $multiplier * $result[$j]->value;
$multiplier *= 10;
}
$multiplier = 1;
for ($i = strlen($s3) - 1; $i >= 0; $i--)
{
$j = 0;
while ($j < $count && $result[$j]->letter != $s3[$i])
{
$j++;
}
$v3 = $v3 + $multiplier * $result[$j]->value;
$multiplier *= 10;
}
if ($v3 == ($v1 + $v2))
{
return true;
}
else
{
return false;
}
}
// Find solution
public function permutation($count, & $use, & $result, $n, $s1, $s2, $s3)
{
// Loop controlling variable
$i = 0;
if ($n == $count - 1)
{
for ($i = 0; $i < 10; $i++)
{
if ($use[$i] == false)
{
$result[$n]->value = $i;
if ($this->isValid($result, $count, $s1, $s2, $s3) == true)
{
return true;
}
}
}
return false;
}
for ($i = 0; $i < 10; $i++)
{
if ($use[$i] == false)
{
$result[$n]->value = $i;
$use[$i] = true;
if ($this->permutation($count, $use, $result, $n + 1, $s1, $s2, $s3) == true)
{
// When get a result
return true;
}
$use[$i] = false;
}
}
return false;
}
// Calculate the frequency of character
public function frequency( & $freq, $str)
{
$i = 0;
$len = strlen($str);
// Calculate character frequency of givens String *
for ($i = 0; $i < $len; $i++)
{
$freq[ord($str[$i]) - ord('A')]++;
}
}
// Cryptarithmetic handles requests to solve puzzles
public function cryptarithmeticPuzzle($s1, $s2, $s3)
{
// Use to count frequency of each character
$freq = array_fill(0, 26, 0);
// Use to count of unique characters
$count = 0;
// Loop controlling variables
$i = 0;
$j = 0;
// Count frequency of each character in a given String *( form of A-Z).
$this->frequency($freq, $s1);
$this->frequency($freq, $s2);
$this->frequency($freq, $s3);
// Count the number of repeating elements
for ($i = 0; $i < 26; $i++)
{
if ($freq[$i] > 0)
{
// When element occurrences
$count++;
}
}
if ($count > 10)
{
// When string are not valid
echo "Invalid string";
}
else
{
// Use to track numbers
$use = array_fill(0, 10, false);
$result = array_fill(0, $count, null);
for ($i = 0; $i < $count; $i++)
{
$result[$i] = new Node();
}
for ($i = 0, $j = 0; $i < 26; $i++)
{
if ($freq[$i] > 0)
{
// visit to next node
// Set node value
$result[$j]->letter = chr($i + ord('A'));
$result[$j]->value = 0;
$j++;
}
}
// Set initial values
for ($i = 0; $i < $count; ++$i)
{
// Here zero indicate empty slot
$use[$i] = false;
}
if ($this->permutation($count, $use, $result, 0, $s1, $s2, $s3) == true)
{
echo " Given : ". $s1 ." ". $s2 ." ". $s3 ." \n";
echo " Solution \n";
// Display solution
for ($j = 0; $j < $count; $j++)
{
echo " ". $result[$j]->letter ." = ". $result[$j]->value;
}
}
else
{
// When no solution
echo "No Result";
}
}
}
}
function main()
{
$task = new Puzzle();
$s1 = "SUN";
$s2 = "RUN";
$s3 = "FAST";
// Test
$task->cryptarithmeticPuzzle($s1, $s2, $s3);
}
main();
Output
Given : SUN RUN FAST
Solution
A = 0 F = 1 N = 2 R = 3 S = 6 T = 4 U = 8
/*
Node Js Program for
Cryptarithmetic puzzle
*/
// Define node which is contain letter and resultant value
class Node
{
constructor()
{
this.letter = ' ';
this.value = 0;
}
};
// Binary Tree
class Puzzle
{
isValid(result, count, s1, s2, s3)
{
var v1 = 0;
var v2 = 0;
var v3 = 0;
// Loop controlling variables
var i = 0;
var j = 0;
var multiplier = 1;
for (i = s1.length - 1; i >= 0; i--)
{
j = 0;
while (j < count && result[j].letter != s1[i])
{
j++;
}
v1 = v1 + multiplier * result[j].value;
multiplier *= 10;
}
multiplier = 1;
for (i = s2.length - 1; i >= 0; i--)
{
j = 0;
while (j < count && result[j].letter != s2[i])
{
j++;
}
v2 = v2 + multiplier * result[j].value;
multiplier *= 10;
}
multiplier = 1;
for (i = s3.length - 1; i >= 0; i--)
{
j = 0;
while (j < count && result[j].letter != s3[i])
{
j++;
}
v3 = v3 + multiplier * result[j].value;
multiplier *= 10;
}
if (v3 == (v1 + v2))
{
return true;
}
else
{
return false;
}
}
// Find solution
permutation(count, use, result, n, s1, s2, s3)
{
// Loop controlling variable
var i = 0;
if (n == count - 1)
{
for (i = 0; i < 10; i++)
{
if (use[i] == false)
{
result[n].value = i;
if (this.isValid(result, count, s1, s2, s3) == true)
{
return true;
}
}
}
return false;
}
for (i = 0; i < 10; i++)
{
if (use[i] == false)
{
result[n].value = i;
use[i] = true;
if (this.permutation(count, use, result, n + 1, s1, s2, s3) == true)
{
// When get a result
return true;
}
use[i] = false;
}
}
return false;
}
// Calculate the frequency of character
frequency(freq, str)
{
var i = 0;
var len = str.length;
// Calculate character frequency of givens String *
for (i = 0; i < len; i++)
{
freq[(str[i]).charCodeAt(0) - ('A').charCodeAt(0)]++;
}
}
// Cryptarithmetic handles requests to solve puzzles
cryptarithmeticPuzzle(s1, s2, s3)
{
// Use to count frequency of each character
var freq = Array(26).fill(0);
// Use to count of unique characters
var count = 0;
// Loop controlling variables
var i = 0;
var j = 0;
// Count frequency of each character in a given String *( form of A-Z).
this.frequency(freq, s1);
this.frequency(freq, s2);
this.frequency(freq, s3);
// Count the number of repeating elements
for (i = 0; i < 26; i++)
{
if (freq[i] > 0)
{
// When element occurrences
count++;
}
}
if (count > 10)
{
// When string are not valid
process.stdout.write("Invalid string");
}
else
{
// Use to track numbers
var use = Array(10).fill(false);
var result = Array(count).fill(null);
for (i = 0; i < count; i++)
{
result[i] = new Node();
}
for (i = 0, j = 0; i < 26; i++)
{
if (freq[i] > 0)
{
// visit to next node
// Set node value
result[j].letter = String.fromCharCode((i + ('A').charCodeAt(0)));
result[j].value = 0;
j++;
}
}
// Set initial values
for (i = 0; i < count; ++i)
{
// Here zero indicate empty slot
use[i] = false;
}
if (this.permutation(count, use, result, 0, s1, s2, s3) == true)
{
process.stdout.write(" Given : " + s1 + " " + s2 + " " + s3 + " \n");
process.stdout.write(" Solution \n");
// Display solution
for (j = 0; j < count; j++)
{
process.stdout.write(" " + result[j].letter + " = " + result[j].value);
}
}
else
{
// When no solution
process.stdout.write("No Result");
}
}
}
}
function main()
{
var task = new Puzzle();
var s1 = "SUN";
var s2 = "RUN";
var s3 = "FAST";
// Test
task.cryptarithmeticPuzzle(s1, s2, s3);
}
main();
Output
Given : SUN RUN FAST
Solution
A = 0 F = 1 N = 2 R = 3 S = 6 T = 4 U = 8
# Python 3 Program for
# Cryptarithmetic puzzle
# Define node which is contain letter and resultant value
class Node :
def __init__(self) :
self.letter = ' '
self.value = 0
# Binary Tree
class Puzzle :
def isValid(self, result, count, s1, s2, s3) :
v1 = 0
v2 = 0
v3 = 0
# Loop controlling variables
i = 0
j = 0
multiplier = 1
i = len(s1) - 1
while (i >= 0) :
j = 0
while (j < count and result[j].letter != s1[i]) :
j += 1
v1 = v1 + multiplier * result[j].value
multiplier *= 10
i -= 1
multiplier = 1
i = len(s2) - 1
while (i >= 0) :
j = 0
while (j < count and result[j].letter != s2[i]) :
j += 1
v2 = v2 + multiplier * result[j].value
multiplier *= 10
i -= 1
multiplier = 1
i = len(s3) - 1
while (i >= 0) :
j = 0
while (j < count and result[j].letter != s3[i]) :
j += 1
v3 = v3 + multiplier * result[j].value
multiplier *= 10
i -= 1
if (v3 == (v1 + v2)) :
return True
else :
return False
# Find solution
def permutation(self, count, use, result, n, s1, s2, s3) :
# Loop controlling variable
i = 0
if (n == count - 1) :
i = 0
while (i < 10) :
if (use[i] == False) :
result[n].value = i
if (self.isValid(result, count, s1, s2, s3) == True) :
return True
i += 1
return False
i = 0
while (i < 10) :
if (use[i] == False) :
result[n].value = i
use[i] = True
if (self.permutation(count, use, result, n + 1, s1, s2, s3) == True) :
# When get a result
return True
use[i] = False
i += 1
return False
# Calculate the frequency of character
def frequency(self, freq, str) :
i = 0
size = len(str)
# Calculate character frequency of givens String *
i = 0
while (i < size) :
freq[ord(str[i]) - ord('A')] += 1
i += 1
# Cryptarithmetic handles requests to solve puzzles
def cryptarithmeticPuzzle(self, s1, s2, s3) :
# Use to count frequency of each character
freq = [0] * (26)
# Use to count of unique characters
count = 0
# Loop controlling variables
i = 0
j = 0
# Count frequency of each character in a given String *( form of A-Z).
self.frequency(freq, s1)
self.frequency(freq, s2)
self.frequency(freq, s3)
# Count the number of repeating elements
i = 0
while (i < 26) :
if (freq[i] > 0) :
# When element occurrences
count += 1
i += 1
if (count > 10) :
# When string are not valid
print("Invalid string", end = "")
else :
# Use to track numbers
use = [False] * (10)
result = [None] * (count)
i = 0
while (i < count) :
result[i] = Node()
i += 1
i = 0
j = 0
while (i < 26) :
if (freq[i] > 0) :
# visit to next node
# Set node value
result[j].letter = chr((i + ord('A')))
result[j].value = 0
j += 1
i += 1
# Set initial values
i = 0
while (i < count) :
# Here zero indicate empty slot
use[i] = False
i += 1
if (self.permutation(count, use, result, 0, s1, s2, s3) == True) :
print(" Given : ", s1 ," ", s2 ," ", s3 ," ")
print(" Solution ")
# Display solution
j = 0
while (j < count) :
print(" ", result[j].letter ," = ", result[j].value, end = "")
j += 1
else :
# When no solution
print("No Result", end = "")
def main() :
task = Puzzle()
s1 = "SUN"
s2 = "RUN"
s3 = "FAST"
# Test
task.cryptarithmeticPuzzle(s1, s2, s3)
if __name__ == "__main__": main()
Output
Given : SUN RUN FAST
Solution
A = 0 F = 1 N = 2 R = 3 S = 6 T = 4 U = 8
# Ruby Program for
# Cryptarithmetic puzzle
# Define node which is contain letter and resultant value
class Node
# Define the accessor and reader of class Node
attr_reader :letter, :value
attr_accessor :letter, :value
def initialize()
self.letter = ' '
self.value = 0
end
end
# Binary Tree
class Puzzle
def isValid(result, count, s1, s2, s3)
v1 = 0
v2 = 0
v3 = 0
# Loop controlling variables
i = 0
j = 0
multiplier = 1
i = s1.length() - 1
while (i >= 0)
j = 0
while (j < count && result[j].letter != s1[i])
j += 1
end
v1 = v1 + multiplier * result[j].value
multiplier *= 10
i -= 1
end
multiplier = 1
i = s2.length() - 1
while (i >= 0)
j = 0
while (j < count && result[j].letter != s2[i])
j += 1
end
v2 = v2 + multiplier * result[j].value
multiplier *= 10
i -= 1
end
multiplier = 1
i = s3.length() - 1
while (i >= 0)
j = 0
while (j < count && result[j].letter != s3[i])
j += 1
end
v3 = v3 + multiplier * result[j].value
multiplier *= 10
i -= 1
end
if (v3 == (v1 + v2))
return true
else
return false
end
end
# Find solution
def permutation(count, use, result, n, s1, s2, s3)
# Loop controlling variable
i = 0
if (n == count - 1)
i = 0
while (i < 10)
if (use[i] == false)
result[n].value = i
if (self.isValid(result, count, s1, s2, s3) == true)
return true
end
end
i += 1
end
return false
end
i = 0
while (i < 10)
if (use[i] == false)
result[n].value = i
use[i] = true
if (self.permutation(count, use, result, n + 1, s1, s2, s3) == true)
# When get a result
return true
end
use[i] = false
end
i += 1
end
return false
end
# Calculate the frequency of character
def frequency(freq, str)
i = 0
len = str.length()
# Calculate character frequency of givens String *
i = 0
while (i < len)
freq[(str[i]).ord - ('A').ord] += 1
i += 1
end
end
# Cryptarithmetic handles requests to solve puzzles
def cryptarithmeticPuzzle(s1, s2, s3)
# Use to count frequency of each character
freq = Array.new(26) {0}
# Use to count of unique characters
count = 0
# Loop controlling variables
i = 0
j = 0
# Count frequency of each character in a given String *( form of A-Z).
self.frequency(freq, s1)
self.frequency(freq, s2)
self.frequency(freq, s3)
# Count the number of repeating elements
i = 0
while (i < 26)
if (freq[i] > 0)
# When element occurrences
count += 1
end
i += 1
end
if (count > 10)
# When string are not valid
print("Invalid string")
else
# Use to track numbers
use = Array.new(10) {false}
result = Array.new(count) {nil}
i = 0
while (i < count)
result[i] = Node.new()
i += 1
end
i = 0
j = 0
while (i < 26)
if (freq[i] > 0)
# visit to next node
# Set node value
result[j].letter = ((i + ('A').ord)).chr
result[j].value = 0
j += 1
end
i += 1
end
# Set initial values
i = 0
while (i < count)
# Here zero indicate empty slot
use[i] = false
i += 1
end
if (self.permutation(count, use, result, 0, s1, s2, s3) == true)
print(" Given : ", s1 ," ", s2 ," ", s3 ," \n")
print(" Solution \n")
# Display solution
j = 0
while (j < count)
print(" ", result[j].letter ," = ", result[j].value)
j += 1
end
else
# When no solution
print("No Result")
end
end
end
end
def main()
task = Puzzle.new()
s1 = "SUN"
s2 = "RUN"
s3 = "FAST"
# Test
task.cryptarithmeticPuzzle(s1, s2, s3)
end
main()
Output
Given : SUN RUN FAST
Solution
A = 0 F = 1 N = 2 R = 3 S = 6 T = 4 U = 8
/*
Scala Program for
Cryptarithmetic puzzle
*/
// Define node which is contain letter and resultant value
class Node(var letter: Character , var value: Int)
{
def this()
{
this(' ', 0);
}
};
// Binary Tree
class Puzzle
{
def isValid(result: Array[Node], count: Int, s1: String, s2: String, s3: String): Boolean = {
var v1: Int = 0;
var v2: Int = 0;
var v3: Int = 0;
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
var multiplier: Int = 1;
i = s1.length() - 1;
while (i >= 0)
{
j = 0;
while (j < count && result(j).letter != s1(i))
{
j += 1;
}
v1 = v1 + multiplier * result(j).value;
multiplier *= 10;
i -= 1;
}
multiplier = 1;
i = s2.length() - 1;
while (i >= 0)
{
j = 0;
while (j < count && result(j).letter != s2(i))
{
j += 1;
}
v2 = v2 + multiplier * result(j).value;
multiplier *= 10;
i -= 1;
}
multiplier = 1;
i = s3.length() - 1;
while (i >= 0)
{
j = 0;
while (j < count && result(j).letter != s3(i))
{
j += 1;
}
v3 = v3 + multiplier * result(j).value;
multiplier *= 10;
i -= 1;
}
if (v3 == (v1 + v2))
{
return true;
}
else
{
return false;
}
}
// Find solution
def permutation(count: Int, use: Array[Boolean], result: Array[Node], n: Int, s1: String, s2: String, s3: String): Boolean = {
// Loop controlling variable
var i: Int = 0;
if (n == count - 1)
{
i = 0;
while (i < 10)
{
if (use(i) == false)
{
result(n).value = i;
if (this.isValid(result, count, s1, s2, s3) == true)
{
return true;
}
}
i += 1;
}
return false;
}
i = 0;
while (i < 10)
{
if (use(i) == false)
{
result(n).value = i;
use(i) = true;
if (this.permutation(count, use, result, n + 1, s1, s2, s3) == true)
{
// When get a result
return true;
}
use(i) = false;
}
i += 1;
}
return false;
}
// Calculate the frequency of character
def frequency(freq: Array[Int], str: String): Unit = {
var i: Int = 0;
var len: Int = str.length();
// Calculate character frequency of givens String *
i = 0;
while (i < len)
{
freq(str(i) - 'A') += 1;
i += 1;
}
}
// Cryptarithmetic handles requests to solve puzzles
def cryptarithmeticPuzzle(s1: String, s2: String, s3: String): Unit = {
// Use to count frequency of each character
var freq: Array[Int] = Array.fill[Int](26)(0);
// Use to count of unique characters
var count: Int = 0;
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
// Count frequency of each character in a given String *( form of A-Z).
this.frequency(freq, s1);
this.frequency(freq, s2);
this.frequency(freq, s3);
// Count the number of repeating elements
i = 0;
while (i < 26)
{
if (freq(i) > 0)
{
// When element occurrences
count += 1;
}
i += 1;
}
if (count > 10)
{
// When string are not valid
print("Invalid string");
}
else
{
// Use to track numbers
var use: Array[Boolean] = Array.fill[Boolean](10)(false);
var result: Array[Node] = Array.fill[Node](count)(null);
i = 0;
while (i < count)
{
result(i) = new Node();
i += 1;
}
i = 0;
j = 0;
while (i < 26)
{
if (freq(i) > 0)
{
// visit to next node
// Set node value
result(j).letter = ((i + 'A')).toChar;
result(j).value = 0;
j += 1;
}
i += 1;
}
// Set initial values
i = 0;
while (i < count)
{
// Here zero indicate empty slot
use(i) = false;
i += 1;
}
if (this.permutation(count, use, result, 0, s1, s2, s3) == true)
{
print(" Given : " + s1 + " " + s2 + " " + s3 + " \n");
print(" Solution \n");
// Display solution
j = 0;
while (j < count)
{
print(" " + result(j).letter + " = " + result(j).value);
j += 1;
}
}
else
{
// When no solution
print("No Result");
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Puzzle = new Puzzle();
var s1: String = "SUN";
var s2: String = "RUN";
var s3: String = "FAST";
// Test
task.cryptarithmeticPuzzle(s1, s2, s3);
}
}
Output
Given : SUN RUN FAST
Solution
A = 0 F = 1 N = 2 R = 3 S = 6 T = 4 U = 8
/*
Swift 4 Program for
Cryptarithmetic puzzle
*/
// Define node which is contain letter and resultant value
class Node
{
var letter: Character;
var value: Int;
init()
{
self.letter = " ";
self.value = 0;
}
};
// Binary Tree
class Puzzle
{
func isValid(_ result: [Node?], _ count: Int, _ a1: String, _ a2: String, _ a3: String)->Bool
{
var v1: Int = 0;
var v2: Int = 0;
var v3: Int = 0;
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
var multiplier: Int = 1;
i = a1.count - 1;
let s1 = Array(a1);
let s2 = Array(a2);
let s3 = Array(a3);
while (i >= 0)
{
j = 0;
while (j < count && result[j]!.letter != s1[i])
{
j += 1;
}
v1 = v1 + multiplier * result[j]!.value;
multiplier *= 10;
i -= 1;
}
multiplier = 1;
i = a2.count - 1;
while (i >= 0)
{
j = 0;
while (j < count && result[j]!.letter != s2[i])
{
j += 1;
}
v2 = v2 + multiplier * result[j]!.value;
multiplier *= 10;
i -= 1;
}
multiplier = 1;
i = a3.count - 1;
while (i >= 0)
{
j = 0;
while (j < count && result[j]!.letter != s3[i])
{
j += 1;
}
v3 = v3 + multiplier * result[j]!.value;
multiplier *= 10;
i -= 1;
}
if (v3 == (v1 + v2))
{
return true;
}
else
{
return false;
}
}
// Find solution
func permutation(_ count: Int, _ use: inout[Bool], _ result: [Node? ], _ n: Int, _ s1: String, _ s2: String, _ s3: String)->Bool
{
// Loop controlling variable
var i: Int = 0;
if (n == count - 1)
{
i = 0;
while (i < 10)
{
if (use[i] == false)
{
result[n]!.value = i;
if (self.isValid(result, count, s1, s2, s3) == true)
{
return true;
}
}
i += 1;
}
return false;
}
i = 0;
while (i < 10)
{
if (use[i] == false)
{
result[n]!.value = i;
use[i] = true;
if (self.permutation(count, &use, result, n + 1, s1, s2, s3) == true)
{
// When get a result
return true;
}
use[i] = false;
}
i += 1;
}
return false;
}
// Calculate the frequency of character
func frequency(_ freq: inout[Int], _ s: String)
{
var i: Int = 0;
let len: Int = s.count;
let str = Array(s);
var index = 0;
// Calculate character frequency of givens String *
while (i < len)
{
index = Int(UnicodeScalar(String(str[i]))!.value - UnicodeScalar("A")!.value);
freq[index] += 1;
i += 1;
}
}
// Cryptarithmetic handles requests to solve puzzles
func cryptarithmeticPuzzle(_ s1: String, _ s2: String, _ s3: String)
{
// Use to count frequency of each character
var freq: [Int] = Array(repeating: 0, count: 26);
// Use to count of unique characters
var count: Int = 0;
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
// Count frequency of each character in a given String *( form of A-Z).
self.frequency(&freq, s1);
self.frequency(&freq, s2);
self.frequency(&freq, s3);
// Count the number of repeating elements
i = 0;
while (i < 26)
{
if (freq[i] > 0)
{
// When element occurrences
count += 1;
}
i += 1;
}
if (count > 10)
{
// When string are not valid
print("Invalid string", terminator: "");
}
else
{
// Use to track numbers
var use: [Bool] = Array(repeating: false, count: 10);
var result: [Node? ] = Array(repeating: nil, count: count);
i = 0;
while (i < count)
{
result[i] = Node();
i += 1;
}
i = 0;
j = 0;
while (i < 26)
{
if (freq[i] > 0)
{
// visit to next node
// Set node value
result[j]!.letter = Character(UnicodeScalar(UInt8((i + Int(UnicodeScalar("A")!.value)))));
result[j]!.value = 0;
j += 1;
}
i += 1;
}
// Set initial values
i = 0;
while (i < count)
{
// Here zero indicate empty slot
use[i] = false;
i += 1;
}
if (self.permutation(count, &use, result, 0, s1, s2, s3) == true)
{
print(" Given : ", s1 ," ", s2 ," ", s3 ," ");
print(" Solution ");
// Display solution
j = 0;
while (j < count)
{
print(" ", result[j]!.letter ," = ", result[j]!.value, terminator: "");
j += 1;
}
}
else
{
// When no solution
print("No Result", terminator: "");
}
}
}
}
func main()
{
let task: Puzzle = Puzzle();
let s1: String = "SUN";
let s2: String = "RUN";
let s3: String = "FAST";
// Test
task.cryptarithmeticPuzzle(s1, s2, s3);
}
main();
Output
Given : SUN RUN FAST
Solution
A = 0 F = 1 N = 2 R = 3 S = 6 T = 4 U = 8
/*
Kotlin Program for
Cryptarithmetic puzzle
*/
// Define node which is contain letter and resultant value
class Node
{
var letter: Char;
var value: Int;
constructor()
{
this.letter = ' ';
this.value = 0;
}
};
// Binary Tree
class Puzzle
{
fun isValid(result: Array<Node?> , count : Int, s1: String, s2: String, s3: String): Boolean
{
var v1: Int = 0;
var v2: Int = 0;
var v3: Int = 0;
// Loop controlling variables
var i: Int ;
var j: Int ;
var multiplier: Int = 1;
i = s1.count() - 1;
while (i >= 0)
{
j = 0;
while (j < count && result[j]!!.letter != s1[i])
{
j += 1;
}
v1 = v1 + multiplier * result[j]!!.value;
multiplier *= 10;
i -= 1;
}
multiplier = 1;
i = s2.count() - 1;
while (i >= 0)
{
j = 0;
while (j < count && result[j]!!.letter != s2[i])
{
j += 1;
}
v2 = v2 + multiplier * result[j]!!.value;
multiplier *= 10;
i -= 1;
}
multiplier = 1;
i = s3.count() - 1;
while (i >= 0)
{
j = 0;
while (j < count && result[j]!!.letter != s3[i])
{
j += 1;
}
v3 = v3 + multiplier * result[j]!!.value;
multiplier *= 10;
i -= 1;
}
if (v3 == (v1 + v2))
{
return true;
}
else
{
return false;
}
}
// Find solution
fun permutation(count: Int, use: Array <Boolean> , result: Array <Node?> , n : Int, s1: String, s2: String, s3: String): Boolean
{
// Loop controlling variable
var i: Int = 0;
if (n == count - 1)
{
while (i < 10)
{
if (use[i] == false)
{
result[n]!!.value = i;
if (this.isValid(result, count, s1, s2, s3) == true)
{
return true;
}
}
i += 1;
}
return false;
}
while (i < 10)
{
if (use[i] == false)
{
result[n]!!.value = i;
use[i] = true;
if (this.permutation(count, use, result, n + 1, s1, s2, s3) == true)
{
// When get a result
return true;
}
use[i] = false;
}
i += 1;
}
return false;
}
// Calculate the frequency of character
fun frequency(freq: Array <Int> , str: String): Unit
{
var i: Int = 0;
var len: Int = str.count();
// Calculate character frequency of givens String *
while (i < len)
{
freq[str[i] - 'A'] += 1;
i += 1;
}
}
// Cryptarithmetic handles requests to solve puzzles
fun cryptarithmeticPuzzle(s1: String, s2: String, s3: String): Unit
{
// Use to count frequency of each character
var freq: Array <Int> = Array(26){0};
// Use to count of unique characters
var count: Int = 0;
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
// Count frequency of each character in a given String *( form of A-Z).
this.frequency(freq, s1);
this.frequency(freq, s2);
this.frequency(freq, s3);
// Count the number of repeating elements
while (i < 26)
{
if (freq[i] > 0)
{
// When element occurrences
count += 1;
}
i += 1;
}
if (count > 10)
{
// When string are not valid
print("Invalid string");
}
else
{
// Use to track numbers
var use: Array <Boolean> = Array(10){false};
var result: Array <Node?> = Array(count){null};
i = 0;
while (i < count)
{
result[i] = Node();
i += 1;
}
i = 0;
while (i < 26)
{
if (freq[i] > 0)
{
// visit to next node
// Set node value
result[j]!!.letter = (i + 'A'.toInt()).toChar();
result[j]!!.value = 0;
j += 1;
}
i += 1;
}
// Set initial values
i = 0;
while (i < count)
{
// Here zero indicate empty slot
use[i] = false;
i += 1;
}
if (this.permutation(count, use, result, 0, s1, s2, s3) == true)
{
print(" Given : " + s1 + " " + s2 + " " + s3 + " \n");
print(" Solution \n");
// Display solution
j = 0;
while (j < count)
{
print(" " + result[j]!!.letter + " = " + result[j]!!.value);
j += 1;
}
}
else
{
// When no solution
print("No Result");
}
}
}
}
fun main(args: Array < String > ): Unit
{
var task: Puzzle = Puzzle();
var s1: String = "SUN";
var s2: String = "RUN";
var s3: String = "FAST";
// Test
task.cryptarithmeticPuzzle(s1, s2, s3);
}
Output
Given : SUN RUN FAST
Solution
A = 0 F = 1 N = 2 R = 3 S = 6 T = 4 U = 8
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment