Berzerk!

Computer Science Level 3

$\large \begin{array} { c c c c c c c } & B& A &N & A & N & A\\ && L &E & M& O & N \\ + && &P & E &A & R\\ \hline &O & R & A & N & G & E \\ \hline \end{array}$

Figure above represents a cryptogram with each letter represents a distinct non-negative integers and each of the leading digits are non-zero, find the 6-digit integer, $\overline{ORANGE}$ .

The answer is 234067.

3 solutions

Agnishom Chattopadhyay
Apr 5, 2016

The glory of discrete optimization modelling (with minizinc)

include "globals.mzn";

var 0..9: B;
var 0..9: A;
var 0..9: N;
var 0..9: L;
var 0..9: E;
var 0..9: M;
var 0..9: O;
var 0..9: R;
var 0..9: G;
var 0..9: P;

solve satisfy;

constraint
  100000*B + 10000*A + 1000*N + 100*A + 10*N + A
  + 10000*L + 1000*E + 100*M + 10*O + N
  + 1000*P + 100*E + 10*A + R
  = 100000*O + 10000*R + 1000*A + 100*N + 10*G + E
;

constraint
  B != 0
  /\
  L != 0
  /\
  P != 0
  /\
  O != 0
;

constraint
  alldifferent([B,A,N,L,E,M,O,P,R,G])
;

output [show(100000*O + 10000*R + 1000*A + 100*N + 10*G + E)];

Woah! The syntax of minizinc looks quite easy to understand, is alldifferent() an inbuilt module?

Also what are advantages of minizinc over python?

Thanks.

Harsh Shrivastava - 5 years, 2 months ago

alldifferent is in "globals.mzn"

Python and MiniZinc serve different purposes. Python is imperative: it let's you describe an algorithm. MiniZinc is declarative: it let's you describe the problem. MiniZinc solves the problem by itself .

There are several combinatorial optimization problem which are actually hard to solve for large chunks of data. While regular programming techniques solve it to some extent, there are several involved tricks for working with larger chunks.

MiniZinc has a solver equipped with a large number of these techniques. You can checkout this course, or this for a more practical approach. You could just check the introduction videos for an overview of the idea.

You can see a large number of amazing puzzles solved that minizinc can solve in Hakan's website.

Agnishom Chattopadhyay - 5 years, 2 months ago

So basically minizinc is a language that is optimal for puzzles?

I guess(by reading its description) that minizinc can be used for selecting efficient routes for a task in real world.

Harsh Shrivastava - 5 years, 2 months ago

@Harsh Shrivastava – You can say.

I guess(by reading its description) that minizinc can be used for selecting efficient routes for a task in real world.

Yes, that is true. There are several real world optimization problems like job scheduling, resource allocation, linear programming, travelling salesman, independent set, etc which minizinc (or other equivalent solvers) would handle very well

Agnishom Chattopadhyay - 5 years, 2 months ago

Christopher Boo
Jul 19, 2016

My proudest cryptogram solver. It provides modularity and readability.

from itertools import permutations

alpha = ['B','A','N','L','E','M','O','P','R','G']

def val(digit,S):
    m = dict(zip(alpha,digit))
    v = [m[c] for c in S]
    return int("".join(v))

for L in permutations(['0','1','2','3','4','5','6','7','8','9']):
    if  val(L,"BANANA") + val(L,"LEMON") + val(L,"PEAR") == val(L,"ORANGE"):
        print val(L,"ORANGE")
        break

Paul Haynie
Jul 10, 2016

Since this is listed as a Logic problem rather than a Computer Science one, it should be possible to solve it manually, and it IS, though the process is somewhat tedious.

Numbering the columns from left to right for reference:

It is clear from Column One that O=B+1. The fact that these are consecutive numbers is a useful validity test later in the process, as the number of available unassigned values diminishes.

It is clear that since Column Two must carry a one into Column One, A+L>7. Given that L>0, this gives 56 possible (A,L) combinations.

In Column Two, given (A,L), R has a maximum of three values.

In Column Six, given (A,R), E is dependent on the value of N, and there is a small number of possible values.

In Column Three, given (N,E), P has a maximum of three values.

In Column Four, given (A,E,N), M has a maximum of three values.

This leaves three unassigned values, which must be successfully sloted into B, O and G.

A given combination might prove impossible at any stage; the actual number of cases that must be checked is in the vicinity of 200.

140404+87920+5743=234067

Moderator note:

Good explanation of how to set up the initial analysis, though it still requires quite a bit of brute force.

Berzerk!

The answer is 234067.

3 solutions

Moderator note:

0 pending reports