Eggs aren't veg

Computer Science Level 5

If every letter corresponds a unique digit in decimal system and $\overline{TOM}+\overline{GIVES} = \overline{MOST}+ \overline{TIME}$ Find the value of $\overline{EGG}+ \overline{IS} + \overline{VEG}$

Details and assumptions :

$\bullet$ If $(A,B,C,D) =(1,2,3,4)$ , then $\overline{BAD} = 214$ .

$\bullet$ Everything is in decimal representation and every letter corresponds to one unique digit. That is why this has exactly one solution.

Everything that i shared on brilliant

Image Credit: Wikimedia Genetic Algorithm by Yearofthedragon

The answer is 1324.

4 solutions

Aditya Raut
Mar 15, 2015

The program will print the solution 2 times, because we are using 8 integers out of 10 so the $2!$ permutations will give the solution 2 times, but anyway, the solution is unique, answer $\boxed{1324}$

for i in permutations('0123456789'):
    x=''.join(i)
    [E,G,I,M,O,S,T,V]=list(x)[:8]
    if int(T+O+M)+int(G+I+V+E+S)==int(M+O+S+T)+ int(T+I+M+E) :
        print int(E+G+G)+int(I+S)+int(V+E+G)

1324
1324
>>>

@Raghav Vaidyanathan and @Agnishom Chattopadhyay , my programming friends....

Aditya Raut - 6 years, 3 months ago

$\text{"0123456789"="OGSIVMaaET"}$

Your python code takes 23 seconds to run on my computer.

I actually extended my genetic algorithm from the previous problem to adapt into this. Works well under a second, every time. When I first saw that there were two undefined digits, I thought there might be multiple solutions. My algorithm cannot find both simultaneously. But then I assumed that you must have taken care of that. And I was right. Good job. I have been posting a few programming problems lately, try those if you are interested.

Raghav Vaidyanathan - 6 years, 3 months ago

That's so amazing, I'm gonna try and learn genetic programming right now ! (Time is not issue for me now, I could've waited for 1 hour if that did give answer :P LOL)

Aditya Raut - 6 years, 3 months ago

Anonymous1 Assassin
Feb 1, 2021

This is the most efficient solution so far:

from itertools import permutations

for t,o,m,g,i,v,e,s in permutations('0123456789',8):
  if int(t+o+m)+int(g+i+v+e+s)==int(m+o+s+t)+int(t+i+m+e):
    print(int(e+g+g)+int(i+s)+int(v+e+g))

Resha Dwika Hefni Al-Fahsi
Oct 2, 2017

Using C++ implement the Genetic Algorithm easily after read article from Agnishom Chattopadhyay

#include <bits/stdc++.h>

#define POPULATION 100
#define INDEX_MUTATION 3

std::string F = "TOM";
std::string S = "GIVES";
std::string Rx = "MOST";
std::string Ry = "TIME";

typedef struct Chromosome{

    std::string gene;

    int doSearch(char x){
        int ret;
        bool found = false;
        int index = 0;
        while(!found){
            if(gene[index] == x){
                ret = index;
                found = true;
            }
            index++;
        }
        return ret;
    }

    Chromosome() : gene("__EGIMOSTV") {}

    void printGene(){
        std::cout<<gene<<std::endl;
    }

    int geneValue(char x){
        int ret;
        ret = doSearch(x);
        return ret;
    }

    void mutate(){       
            std::random_device rdx;
            std::random_device rdy;
            std::mt19937 genx(rdx());
            std::mt19937 geny(rdy());
            std::uniform_int_distribution<int> rgx(0,9);
            std::uniform_int_distribution<int> rgy(0,9);
            int x, y;

            for(int i=0; i<INDEX_MUTATION; i++){
                x = rgx(genx);
                y = rgy(geny);
                std::swap(gene[x],gene[y]);
            }

    }

} Chromosome;

long fitness(Chromosome c){
    long f = 0, s = 0, rx = 0, ry = 0, r = 0;
    long ret = 0;
    int fsize = F.length();
    int ssize = S.length();
    int rxsize = Rx.length();
    int rysize = Ry.length();

    for(int i=0; i<fsize; i++) {

        long tempf = c.geneValue(F[i]);
        f+=tempf;
        f*=10;

    }

    f/=10;

    for(int i=0; i<ssize; i++) {
        long temps = c.geneValue(S[i]);
        s+=temps;
        s*=10;
    }

    s/=10;

    for(int i=0; i<rxsize; i++) {
        long temprx = c.geneValue(Rx[i]);
        rx+=temprx;
        rx*=10;
    }

    rx/=10;

    for(int i=0; i<rysize; i++) {
        long tempry = c.geneValue(Ry[i]);
        ry+=tempry;
        ry*=10;
    }

    ry/=10;

    r = rx + ry;

    ret = abs(f+s-r);

    return ret;
}


void natural_selection(){

    int generation = 0;
    // initialize population
    std::vector<Chromosome> population;
    population.resize(POPULATION);

    while(1){

        // find fitness population:
        long best = fitness(population[0]);
        int bestIndex = 0;

        for(int i=0; i<POPULATION; i++){

            // mutation! : 
            population[i].mutate();

            // search the best from fitness function! :
            long candidate = fitness(population[i]);
            if(candidate<best){
                best = candidate;
                bestIndex = i;
            } 
        }

         // best candidate found!
         if(best == 0){
            std::cout<<"Best Candidate: ";
            population[bestIndex].printGene();
            std::cout<<"Generation: "<<generation<<std::endl;
            break;
        }

        // best candidate so far :
        Chromosome candidateBest = population[bestIndex];
        for(int i=0; i<POPULATION; i++) population[i] = candidateBest;

        generation++;
    }
}

int main(){

    // do the Genetic Algorithm:
    natural_selection();

}

Chew-Seong Cheong
Apr 1, 2015

I used Python coding which is similar to [Aditya Raut]. The second line "x=' '.join(i)" may not be necessary. The answer is $\boxed{1324}$ .

 from itertools import permutations
 for a in permutations("0123456789", 8):
        T = a[0]
        O = a[1]
        M = a[2]
        G = a[3]
        I = a[4]
        V = a[5]
        E = a[6]
        S = a[7]
        if T != "0" and G != "0" and E != "0" and I != "0" and V != "0":
            if int(T+O+M)+int(G+I+V+E+S)==int(M+O+S+T)+int(T+I+M+E):
                print T,O,M,G,I,V,E,S
                print int(E+G+G)+int(I+S)+int(V+E+G)

Eggs aren't veg

Image Credit: Wikimedia Genetic Algorithm by Yearofthedragon

The answer is 1324.

4 solutions

0 pending reports