Logical Solutions - 2

G H I + J K L M N O \begin{array}{ccccccc} & & G & H & I \\ + & & J & K & L \\ \hline & & M & N & O \\ \end{array}

The above represents a cryptogram such that each letter represents a distinct single digit non-negative integer. Find the number of solutions of the above cryptogram.

Note: G G and J J are non-zero.

Also see Part 1


The answer is 1088.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

5 solutions

The legendary minizinc to the rescue:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
include "globals.mzn";

int: n = 9;

array[1..9] of var 0..n: A;

solve satisfy;

constraint
  100*A[1] + 10*A[2] + A[3]
  + 100*A[4] + 10*A[5] + A[6]
  = 100*A[7] + 10*A[8] + A[9]
;

constraint
  A[1] != 0
  /\
  A[4] != 0
  /\
  A[7] != 0
;

constraint
  alldifferent(A)
;

output [show(A)];

Generate all solutions and count them

Holy god, @Agnishom Chattopadhyay , how many languages do you know, mate?

Soumava Pal - 5 years, 2 months ago

Log in to reply

Haha! I have been programming for a long time, so I have come across a several languages. Now, I mainly code in C++ and python but I have tried to learn/written non-significant programs in PHP, FORTRAN, BASIC, Haskell, Perl, javascript, Mathematica, Maxima, etc too. (By the way, I am writing an wiki on lambda calculus now, which is kind of a language)

This language is MiniZinc. It lets you talk to the MiniZinc solver, which is an awesome tool for discrete optimization . I tried to learn it too, but I am not very good at this.

Agnishom Chattopadhyay - 5 years, 2 months ago

Log in to reply

The lambda calculus stuff is pretty interesting. I will make sure I read the wiki.

Talking to the solver.... Sounds somewhat like Prolog. :D

Soumava Pal - 5 years, 2 months ago

Log in to reply

@Soumava Pal Yes, it let's you do that kind of stuff. Like filling a magic square or a sudoku, or linear programming, the knapsack problem, etc

Agnishom Chattopadhyay - 5 years, 2 months ago

Log in to reply

@Agnishom Chattopadhyay Wow... That definitely is exciting. :D

Soumava Pal - 5 years, 2 months ago

Implementation of Cryptogram

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;

int main(){
int g,h,i,j,k,l,m,n,o;
long long shell,elf,sale,rest;
long long bill=0;

g=1; h=0; i=0; j=1; k=0;
while(g<10)  {
    while(h<10){
        while(i<10){
            while(j<10){
                while(k<10){
                    for(l=0;l<10;l++){
                        for(m=1;m<10;m++){
                            for(n=0;n<10;n++){
                                for(o=0;o<10;o++){
if((g!=h) && (g!=i) && (g!=j) && (g!=k) && (g!=l) && (g!=m) && (g!=n) && (g!=o) &&
   (h!=i) && (h!=j) && (h!=k) && (h!=l) && (h!=m) && (h!=n) && (h!=o) &&
   (i!=j) && (i!=k) && (i!=l) && (i!=m) && (i!=o) && (i!=n) && 
   (j!=k) && (j!=l) && (j!=m) && (j!=n) && (j!=o) && 
   (k!=l) && (k!=m) && (k!=n) && (k!=o) && 
   (l!=m) && (l!=n) && (l!=o) && 
   (m!=o) && (m!=n) && 
   (n!=o)
   ){
                        shell=g*100+h*10+i; elf=j*100+k*10+l; sale=m*100+n*10+o;
                        if((shell+elf)==sale) bill++;
                                }
                                }
                    }
                    }
                }
                k++;}
            j++;k=0;}
        i++;j=1;}
    h++;i=0;}
g++;h=0;}   

cout<<bill<<endl;

}

Hi can you please tell me where I have gone wrong? I found all the permutations of '123456789' and then split each permutation into three equal parts. I then iterated over these checking whether the first two parts were equal to the third. I got an answer of 321 321 ; where have I gone wrong? Thanks :)

Michael Ng - 5 years, 6 months ago

Log in to reply

Non-negative integers. But then again you should get 336 with positive integers, not 321, not sure why you got 321.

Vishnu Bhagyanath - 5 years, 2 months ago
Arjen Vreugdenhil
Apr 12, 2016

A traditional approach in Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
        int N = 0;
        int f[] = new int[10];

        for (int x = 102; x < 500; x++)
            for (int y = x+1, z = x+y; z <= 987; y++, z++) {
                for (int i = 0; i < 10; i++) f[i] = 0;
                f[x % 10]++; f[(x/10)%10]++; f[(x/100)%10]++;
                f[y % 10]++; f[(y/10)%10]++; f[(y/100)%10]++;
                f[z % 10]++; f[(z/10)%10]++; f[(z/100)%10]++;

                boolean ok = true;
                for (int i = 0; i < 10 && ok; i++)
                    if (f[i] > 1) ok = false;

                if (ok) N+=2;
            }

        System.out.println(N);

Note the optimization: for every A B C + D E F = G H I ABC + DEF = GHI we have D E F + A B C = G H I DEF + ABC = GHI , and that is necessarily a different solution. Therefore we only generate solutions with A B C < D E F ABC < DEF and count them double.

I used python to solve this as well as permutations from itertools:

1
2
3
4
5
6
7
8
count=0
for g,h,i,j,k,l,m,n,o in permutations('0123456789',9):
  if '0' in (g,j):
    continue
  if int(g+h+i)+int(j+k+l)==int(m+n+o):
    count+=1

print(count)

include <stdio.h>

include <stdlib.h>

int main()

{ int a,b,c,d,e,f,g,h,k,l,m,n,x=0;

for(a=1;a<=9;a++)

{

    for(b=0;b<=9;b++)

    {
        for(c=0;c<=9;c++)

        {
            if(c!=a && c!=b && b!=a)

            {

               d=100*a+10*b+c;

            for(e=1;e<=9;e++)
{

    for(f=0;f<=9;f++)

    {

        for(g=0;g<=9;g++)
        {

            if(g!=f && g!=e && f!=e && e!=a && e!=b && e!=c && f!=a && f!=b && f!=c && g!=a && g!=b && g!=c)
            {
                h=100*e+10*f+g;
                if(h+d<1000 && h!=d)
                {
                    k=h+d;
                    l=k%10;m=(k/10)%10;n=(k/100)%10;
                    if(l!=a && l!=b && l!=c && l!=e && l!=f && l!=g && m!=a && m!=b && m!=c && m!=e && m!=f && m!=g && n!=a && n!=b && n!=c && n!=e && n!=f && n!=g && l!=m && l!=n && m!=n)
                    {
                        x++;
                    printf("%d\n+\n%d\n=\n%d\n\n",h,d,h+d);
                    }
                }
            }

        }


    }
}
        }
        }
    }
}
printf("Total values=%d",x);

}

I seriously don't know how to get it correctly formatted..

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...