lemon-project-template-glpk

comparison deps/glpk/examples/crypto.mod @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:db35d35d7f22
1 /* CRYPTO, a crypto-arithmetic puzzle */
2
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
4
5 /* This problem comes from the newsgroup rec.puzzle.
6 The numbers from 1 to 26 are assigned to the letters of the alphabet.
7 The numbers beside each word are the total of the values assigned to
8 the letters in the word (e.g. for LYRE: L, Y, R, E might be to equal
9 5, 9, 20 and 13, or any other combination that add up to 47).
10 Find the value of each letter under the equations:
11
12 BALLET 45 GLEE 66 POLKA 59 SONG 61
13 CELLO 43 JAZZ 58 QUARTET 50 SOPRANO 82
14 CONCERT 74 LYRE 47 SAXOPHONE 134 THEME 72
15 FLUTE 30 OBOE 53 SCALE 51 VIOLIN 100
16 FUGUE 50 OPERA 65 SOLO 37 WALTZ 34
17
18 Solution:
19 A, B,C, D, E,F, G, H, I, J, K,L,M, N, O, P,Q, R, S,T,U, V,W, X, Y, Z
20 5,13,9,16,20,4,24,21,25,17,23,2,8,12,10,19,7,11,15,3,1,26,6,22,14,18
21
22 Reference:
23 Koalog Constraint Solver <http://www.koalog.com/php/jcs.php>,
24 Simple problems, the crypto-arithmetic puzzle ALPHACIPHER. */
25
26 set LETTERS :=
27 { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
28 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'
29 };
30 /* set of letters */
31
32 set VALUES := 1..card(LETTERS);
33 /* set of values assigned to the letters */
34
35 set WORDS;
36 /* set of words */
37
38 param total{word in WORDS};
39 /* total[word] is the total of the values assigned to the letters in
40 the word */
41
42 var x{i in LETTERS, j in VALUES}, binary;
43 /* x[i,j] = 1 means that letter i is assigned value j */
44
45 s.t. phi{i in LETTERS}: sum{j in VALUES} x[i,j] = 1;
46
47 s.t. psi{j in VALUES}: sum{i in LETTERS} x[i,j] = 1;
48
49 s.t. eqn{word in WORDS}: sum{k in 1..length(word), j in VALUES}
50 j * x[substr(word,k,1), j] = total[word];
51
52 solve;
53
54 printf{i in LETTERS} " %s", i;
55 printf "\n";
56
57 printf{i in LETTERS} " %2d", sum{j in VALUES} j * x[i,j];
58 printf "\n";
59
60 data;
61
62 param : WORDS : total :=
63 BALLET 45
64 CELLO 43
65 CONCERT 74
66 FLUTE 30
67 FUGUE 50
68 GLEE 66
69 JAZZ 58
70 LYRE 47
71 OBOE 53
72 OPERA 65
73 POLKA 59
74 QUARTET 50
75 SAXOPHONE 134
76 SCALE 51
77 SOLO 37
78 SONG 61
79 SOPRANO 82
80 THEME 72
81 VIOLIN 100
82 WALTZ 34 ;
83
84 end;