Welcome Guest [Log In] [Register]
Welcome to Crypto. We hope you enjoy your visit.


You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free.


Join our community!


If you're already a member please log in to your account to access all of our features:

Username:   Password:
Add Reply
Cryptarithms
Topic Started: Apr 3 2008, 04:52 PM (239 Views)
jdege Apr 3 2008, 04:52 PM Post #1
Member Avatar
Elite member
[ * * * * * ]
 The ACA has a type of problem called Cryptarithms: a mathematical cipher in which a simple arithmetic problem is run through a simple substitution, with different letters representing the different digits.

These are expressed in a single line:
Code:
 

SNAILS / BOIL = ANN; - RLBA = EBOL; - LALR = EARS; - LALR = OHBO


But this is simply an abbreviation for a multi-line problem:
Code:
 

          ANN
BOIL / SNAILS
       RLBA
       ------
        EBOL
        LALR
       ------
         EARS
         LALR
       ------
         OHBO

The problems include multiplication, long division, square and cube roots, and can be base 10, 11, or 12.

Keys should spell out a word or words, when ordered 0-9, 9-0, 1-0, or 0-1.

It's a problem that lends itself to exhaustive search. There are only 10!, 11!, or 12! possibilities.

So I wrote one.

I enter the one-line form of the problem into a textfile. I edit it so as to create the multi-line form. Then from the multi-line form, I extract a number of simple equations. These I also place in the file, marked with a ':' at the beginning of the line.
Code:
 

: A * BOIL = RLBA
: N * BOIL = LALR
: SNAI - RLBA = EBO
: EBOL - LALR = EAR
: EARS - LALR = OHBO

If the problem is base 11 or 12, I add a line containing the base, marked with a # at the beginning.

The complete file will look like:
Code:
 

SNAILS / BOIL = ANN; - RLBA = EBOL; - LALR = EARS; - LALR = OHBO

          ANN
BOIL / SNAILS
       RLBA
       ------
        EBOL
        LALR
       ------
         EARS
         LALR
       ------
         OHBO

: A * BOIL = RLBA
: N * BOIL = LALR
: SNAI - RLBA = EBO
: EBOL - LALR = EAR
: EARS - LALR = OHBO

# 10


Then I run my little program. It will read the line beginning with '#' to set the numeric base. It will read all the lines beginning with ':', and parse them to create the equations that need to be checked for each possible key (using a very simple parsing function - but it doesn't need to be more sophisticated).

It will then identify the letters in the ciphertext, and then run through all the possible permutations, checking each to see if it results in all of the equations evaluate to true. If they do, it prints the key.

Code:
 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>

void print(const char *v, const int size)
{
   if (v != 0)
   {
       for (int i = 0; i < size; i++)
       {
           printf("%c", v[i] );
       }

       printf("\n");
   }
}


struct Equation
{
   char leftOpr[128];
   char opd;
   char rightOpr[128];
   char result[128];
};

struct Equation equations[64];
int numEquations = 0;  

int base = 10;

void doSub(char *dest, char *orig, char *permutation)
{
   strcpy(dest, orig);

   for (int i=0; i<base; i++)
   {
       int n = strlen(dest);
       for (int j=0; j<n; j++)
       {
           if (isalpha(dest[j]) && dest[j] == permutation[i])
           {
               if (i >= 10)
                   dest[j] = 'a' + i - 10;
               else
                   dest[j] = '0' + i;
           }
       }
   }
}


bool testEquation(char *permutation, Equation equation)
{
   char leftOprStr[128];
   doSub(leftOprStr, equation.leftOpr, permutation);
   int leftOpr = strtol(leftOprStr, NULL, base);

   char rightOprStr[128];
   doSub(rightOprStr, equation.rightOpr, permutation);
   int rightOpr = strtol(rightOprStr, NULL, base);

   char resultStr[128];
   doSub(resultStr, equation.result, permutation);
   int result = strtol(resultStr, NULL, base);
   int calculated;

   switch (equation.opd)
   {
   case '+':
       calculated = leftOpr + rightOpr;
       break;

   case '-':
       calculated = leftOpr - rightOpr;
       break;

   case '*':
       calculated = leftOpr * rightOpr;
       break;

   case '/':
       calculated = leftOpr / rightOpr;
       break;

   case '=':
       calculated = leftOpr;
       break;

   default:
       calculated = -1;
       break;
   }

   return (calculated == result);
}


void test(char *permutation, int n)
{
   bool passed = true;
   
   for (int i=0; i<numEquations; i++)
   {
       if (!testEquation(permutation, equations[i]))
       {
           passed = false;
           break;
       }
   }

   if (passed)
       print(permutation, n);
}

void permute(char *v, const int start, const int n)
{  
   if (start == n-1)
   {
       test(v, n);
   }
   else
   {
       for (int i = start; i < n; i++)
       {
           int tmp = v[i];
     
           v[i] = v[start];
           v[start] = tmp;
           permute(v, start+1, n);
           v[start] = v[i];
           v[i] = tmp;
       }
   }
}

main(int argc, char *argv[])
{
   FILE *fp;

   switch (argc)
   {
   case 1:
       fp = stdin;
       break;
   
   case 2:
       fp = fopen(argv[1], "r");
       if (!fp)
       {
           fprintf(stderr, "Cannot open file \"%s\" for reading: %s",
               argv[1], strerror(errno));
           // fall-thru
       }
       else
           break;

   default:
       fprintf(stderr, "USAGE: cryptarithm [<file>]\n");
       return EXIT_FAILURE;
   }

   char buffer[1024];

   while (fgets(buffer, 1024, fp))
   {
       if (buffer[0] == ':')
       {
           int n = numEquations++;
           sscanf(buffer, ": %s %c %s = %s\n",
                   equations[n].leftOpr,
                   &equations[n].opd,
                   equations[n].rightOpr,
                   equations[n].result);
       }
       else if (buffer[0] == '#')
       {
           sscanf(buffer, "# %d\n", &base);
       }
   }

   bool letters[26];
   for (int c='A'; c<='Z'; c++)
       letters[c-'A'] = false;

   for (int i=0; i<numEquations; i++)
   {
       for (int j=0; j<strlen(equations[i].leftOpr); j++)
       {
           int c = equations[i].leftOpr[j];
           letters[toupper(c)-'A'] = true;
       }
 
       for (int j=0; j<strlen(equations[i].rightOpr); j++)
       {
           int c = equations[i].rightOpr[j];
           letters[toupper(c)-'A'] = true;
       }
 
       for (int j=0; j<strlen(equations[i].result); j++)
       {
           int c = equations[i].result[j];
           letters[toupper(c)-'A'] = true;
       }
   }

   char characters[37];
   int numCharacters = 0;

   for (int i=0; i<26&&numCharacters<base; i++)
   {
       if (letters[i])
           characters[numCharacters++] = 'A'+i;
   }

   for (int i=0; i<26&&numCharacters<base; i++)
   {
       if (!letters[i])
           characters[numCharacters++] = 'A'+i;
   }
   
   characters[base] = '\0';

   permute(characters, 0, numCharacters);

   return EXIT_SUCCESS;
}



On my own desktop, the above program running on the above file takes 35 seconds to produce the key "HOBNAILERS", which since this was a problem with a 0-9 key order, is the solution. If it had been a problem with a 9-0 key order, I'd have had to reverse the letters to get the solution. Or if it had been a 1-0 or 0-1 key order, I'd have had to move the first letter to the last spot, or moved the first letter and then reversed them.

Thinking about it, it'd be pretty easy to modify the program to output the keys in a specified order, instead of always in 0-9. But this was meant to be a quick-and-dirty solution to a particular problem, not a production program, so just as I found it easier to manipulate the input to produce easily-parsed equations, it's easy enough to reorder the output into the desired form.

If I do go back and revisit this, I will probably add a way of specifying particular values for selected letters. It's often obvious, for example, that a given letter must represent a 0 or a 1. And if I could set them, when I can see them, I could remove them from the set being permuted. It'd not make much of a difference to the base-10 problems. But for the base-11 and base-12 problems, it could make things quite a bit faster.

Because if base-10 takes 35 seconds on my computer, base-11 would take >6 minutes and base-12 would take >1 hour.
When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl.
Online Profile Quote Post Goto Top
 
Revelation Apr 11 2008, 04:38 PM Post #2
Member Avatar
Administrator
[ * * * * * ]
 That's a nice puzzle. I'm sure I've seen simplified forms of this in a puzzle book.

Your application is nice too! Wouldn't want to do that cipher manually :P

Quote:
 
If I do go back and revisit this, I will probably add a way of specifying particular values for selected letters. It's often obvious, for example, that a given letter must represent a 0 or a 1. And if I could set them, when I can see them, I could remove them from the set being permuted. It'd not make much of a difference to the base-10 problems. But for the base-11 and base-12 problems, it could make things quite a bit faster.


That's a good idea. And if you'd really want to go through with this, I'd add educated guesses too. Like saying that B is probably 6, so the permutation of B starts with B being 6.
RRRREJMEEEEEPVKLWENFNVJKEEEEEAOLKAFKLXCFZAASDJXZTTTTTTTLSIOWJXMOKLAFJNNKFNXN
RAGRBAQEMHIGDJVDSEOXVIYCELFHWLELJFIENXLRATALSJFSLCYTKLASJDKMHGOVOKAJDNMNUITN
RRRRLJVEEEEECLYVYHNVPFTAEEEEEMWLMEIRNGLARWJAKJDFLWNTIERJMIPQWOTZEOCXKNUBNXCN
RJIRPOWEANFUSNCZVDVZNMSFEKLOEPZLDKDJWSAAAAAAAOERHJCTNCKFRIMVKSOFOMKMANREWNBN
RZUDRGXEEEEENFQIDVLQNCKNEEEEEDGLLLLLLAWIOSNCDARLODMTOEJXMILDFJROTKJSDNLVCZNN
Offline Profile Quote Post Goto Top
 
jdege Apr 11 2008, 09:26 PM Post #3
Member Avatar
Elite member
[ * * * * * ]
Revelation
Apr 11 2008, 10:38 AM
Quote:
 
If I do go back and revisit this, I will probably add a way of specifying particular values for selected letters. It's often obvious, for example, that a given letter must represent a 0 or a 1. And if I could set them, when I can see them, I could remove them from the set being permuted. It'd not make much of a difference to the base-10 problems. But for the base-11 and base-12 problems, it could make things quite a bit faster.


That's a good idea. And if you'd really want to go through with this, I'd add educated guesses too. Like saying that B is probably 6, so the permutation of B starts with B being 6.

Yep.

If you can guess it down to where you're searching for nine or fewer digits, the search is near-instantaneous, so WAGS can be done interactively.
When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl.
Online Profile Quote Post Goto Top
 
1 user reading this topic (1 Guest and 0 Anonymous)
« Previous Topic · General · Next Topic »
Add Reply