Any idea what this could mean?

Computer Science Level 5

$\begin{array} { l l l l l l l l l } & & S & T & I & R & L & I & N & G \\ +& G & A & L & L & I & P & O & L & I \\ \hline & P & R & O & T & O & S & T & A & R \\ \hline \end{array}$

In the cryptarithm above, each letter represents a unique digit.

Find the value of $\overline{\text{GALOISRATS}}$

Read an interesting note on cryptarithms here

The answer is 6512894509.

3 solutions

Raghav Vaidyanathan
Mar 13, 2015

I read @Agnishom Chattopadhyay 's note on cryptarithms before trying this problem. I initially planned to do a brute force tactic, but then switched to a genetic algorithm, to see how it works. I use C++, so not much versatility here, had to make everything from scratch.

The code below is self explanatory. If it isn't, please also take a look at the above mentioned note .

#include<fstream.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>

class indi       //Objects of this class are the individuals
    {
    char x[11];  //genetic code/DNA
    public:
    indi()
        {
        strcpy(x,"SGPTIRLNAO"); //initial DNA
        }
    void mutate() //causes random switching to genetic code
        {
            int a=(rand()%10),b=(rand()%10);
            char t=x[a];
            x[a]=x[b];
            x[b]=t;
        }
    void show() //prints DNA
        {
        cout<<x<<endl;
        }
    int retlet(char a)//returns respective digit that a letter represents
        {
        for(int i=0;i<10;i++)
            if(x[i]==a)
                return i;
        }
    };

long fitness(indi I,char c1[],int n1,char c2[],int n2,char c3[],int n3)
    {
    //used to calculate the fitness level of the DNA
    //more fitness implies better evolved
    long a=0,b=0,c=0;
    for(int i=n1-1;i>=0;i--)
        a+=pow(10,n1-i-1)*I.retlet(c1[i]);
    for(int i=n2-1;i>=0;i--)
        b+=pow(10,n2-i-1)*I.retlet(c2[i]);
    for(int i=n3-1;i>=0;i--)
        c+=pow(10,n3-i-1)*I.retlet(c3[i]);
    long f=abs((a+b)-c);
    return f;
    }

void nature() //implements natural selection
    {
    indi I[100]; //first 100 DNA
    for(int gen=0;;gen++)
        {
        long b=fitness(I[99],"STIRLING",8,"GALLIPOLI",9,"PROTOSTAR",9);int a=99;
        for(int i=0;i<100;i++)
           {
           I[i].mutate();  //random mutation
           long k=fitness(I[i],"STIRLING",8,"GALLIPOLI",9,"PROTOSTAR",9);
           if(k<b)
               {
               b=k;a=i;      //fittest DNA chosen
               }
           }
        if(b==0) //if DNA is perfect, print DNA
            {
            I[a].show();
            cout<<endl<<gen;
            break;
            }
        indi II=I[a];
        for(int i=0;i<100;i++)
           I[i]=II;     //fittest DNA of current generation is cloned 100 times
        }
    }

int main()
    {
    clrscr();
    nature();
    getch();
    return 0;
    }

@Agnishom Chattopadhyay @Aditya Raut

Raghav Vaidyanathan - 6 years, 3 months ago

I am glad to see that someone liked my ideas.

I do not see any implementation of threading here. Did your.algorithm actually work? How fast/slow was it?

Agnishom Chattopadhyay - 6 years, 3 months ago

It would be a great help if you know a way by which I can time my program. I use a borland 5.01 compiler for C++(outdated and stupid, i know).

Yes, I did not use threading or parallelization. Instead, i used sort of an aggressive form of natural selection. In each generation of 100 individuals, the best individual is chosen, and cloned 100 times(rest are discarded). Then, random mutations are induced in these 100 clones, and again the best individual is chosen, and so on. It took 1983 generations for my program to get to perfect fitness.

Raghav Vaidyanathan - 6 years, 3 months ago

@Raghav Vaidyanathan – I do not know how exactly that is done (not much of a C++ guy, here) but I think the standard approach is to use time.h and query for the time at the begining of the code and at the end and then check their difference.

Edit: I looked this up. This is what you should do:

#include <iostream.h>
#include <time.h>
using namespace std;


int main()
{
    clock_t t1,t2;
    t1=clock();
    //code goes here
    t2=clock();
   float diff = ((float)t2-(float)t1);
   float seconds = diff / CLOCKS_PER_SEC;
    cout<<diff<<endl;
    system ("pause");
    return 0;

}

The above code might contain bugs, I've not tried it. CLOCS PER SEC is a macro

Agnishom Chattopadhyay - 6 years, 3 months ago

@Agnishom Chattopadhyay – Yes, I did try that out... but I do not know if or how I can get decimal time(in milliseconds). time.h returns time in whole seconds only.

Raghav Vaidyanathan - 6 years, 3 months ago

@Raghav Vaidyanathan – Check the update of the last comment

Agnishom Chattopadhyay - 6 years, 3 months ago

@Agnishom Chattopadhyay – I did, and it worked after i tweaked it a bit.

Since my algorithm is aggressive, the runtime depends on the randomisation seedvalue. But the code works under a second in almost all times I have re run it.

Raghav Vaidyanathan - 6 years, 3 months ago

@Raghav Vaidyanathan – Okay, that isvery good.

Agnishom Chattopadhyay - 6 years, 3 months ago

@Agnishom Chattopadhyay – Thanks a lot!

Raghav Vaidyanathan - 6 years, 3 months ago

I really do think that IS a bigg solution, and also, I don't know the language you used, but seems like it's something innovative, so cheers... See my python solution downstairs, though it's bad while assigning the values to letters, after that I've used one nice concept of making strings into integers and integers into strings... As I don't understand above, can you tell me in simple words what is such a concept you've utilised (So that I can use it from now on, bcoz you are really a cool guy as it seems)

Aditya Raut - 6 years, 3 months ago

See the note referred in the problem. :)

Agnishom Chattopadhyay - 6 years, 3 months ago

The note explains it much better than I can. And I did see your python solution, it was good. In fact, I used it to solve the WRONG+WRONG=RIGHT question. I do not know python, all I did was copy paste your code into the GUI and then edit it a bit to give me what I needed. Hope you like the concept of genetic algorithm. Have fun! Thanks.

Raghav Vaidyanathan - 6 years, 3 months ago

@Raghav Vaidyanathan – Alright, I read that note and it's cool, but there's one issue ,that paste bin thing linked at the end says the paste has been removed, I really wanted to see one example of python implementation, that'd be great .. @Agnishom Chattopadhyay , plz do something...

Aditya Raut - 6 years, 3 months ago

@Aditya Raut – @Aditya Raut : Can you open this link: http://pastebin.com/84tttH4W

Agnishom Chattopadhyay - 6 years, 3 months ago

@Agnishom Chattopadhyay – Can you please check if you have other stuff in your pastebin account that other people can see? @Agnishom Chattopadhyay

Raghav Vaidyanathan - 6 years, 3 months ago

@Raghav Vaidyanathan – What kind o other stuff?

Agnishom Chattopadhyay - 6 years, 2 months ago

@Agnishom Chattopadhyay – Idk... sth personal?

Raghav Vaidyanathan - 6 years, 2 months ago

Aditya Raut
Mar 10, 2015

Very Easy python solution, using strings. First assign the 10 digits to the 10 variables, for that I used permutations. Then it's cakewalk! See this :-

>>> from itertools import permutations
>>>
>>>for i in permutations('0123456789'):
    str = ''.join(i)
    [A,G,I,L,N,O,P,R,S,T]=list(str)
    if int(G+A+L+L+I+P+O+L+I)+int(S+T+I+R+L+I+N+G)==int(P+R+O+T+O+S+T+A+R):
        print int(G+A+L+O+I+S+R+A+T+S)

>>> 6512894509

So, the answer is $\boxed{6512894509}$

The brute force solution... not bad

Agnishom Chattopadhyay - 6 years, 3 months ago

I just solved one more problem of this type, it was ' WRONG+WRONG=RIGHT' ... There, the answer I got by above program was 2*ans, because total variables are 8 and values possible are 10... so 2! times more ans.... So cool it felt after noticing that.....

Aditya Raut - 6 years, 3 months ago

Did you ever try implementing the permutations utility yourself?

Agnishom Chattopadhyay - 6 years, 3 months ago

@Agnishom Chattopadhyay – What exactly do you mean to ask? Is it "Did you try to write a program that gives permutations"? Or is it "Where did you come to know about the permutations tool" ? I don't understand...

Aditya Raut - 6 years, 3 months ago

@Raghav Vaidyanathan , @Agnishom Chattopadhyay , @Pranjal Jain , @Brock Brown

$\color{#D61F06}{\text{This solution has been edited, please look again.}}$

Guys, see this cool reduction I found in this brute force solution.... The way I input the variables has been made shorter (If you remember previously there was 1 line for assigning each variable), now the variables are easily obtained by comparing with the list!

Used this trick in the following problems, all are the same type...

here ,

here

and things got wayyy shorter!

Aditya Raut - 5 years, 10 months ago

Anonymous1 Assassin
Feb 1, 2021

This is the shortest and the most efficient solution for this problem:

from itertools import permutations

for s,t,i,r,l,n,g,a,p,o in permutations('0123456789',10):
  if int(s+t+i+r+l+i+n+g)+int(g+a+l+l+i+p+o+l+i)==int(p+r+o+t+o+s+t+a+r):
    print(g+a+l+o+i+s+r+a+t+s)

1	`6512894509`

Any idea what this could mean?

The answer is 6512894509.

3 solutions

0 pending reports