wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Each Letter Represents A Number - But Which One?
        
(Message started by: MathsForFun on Jul 13th, 2010, 1:56pm)
Title: Each Letter Represents A Number - But Which One?
Post by MathsForFun on Jul 13th, 2010, 1:56pm
Each of the integers in the range 1..26 is represented by a single letter in the range a..z. No two integers are represented by the same letter. Work out which letter represents which integer. To help you, 45 clues are provided:

1: t + a + m + y + k + n + q + z + s + r + p + i + c > o + e + d + b + j + h + g + l + w + v + f + x + u
2: c + o + q + x + w + d + u + h + g + p + l + a + j > b + z + k + t + f + m + s + n + e + y + v + i + r
3: u + l + f + c + n + a + y + h + e + t + g + x + w > r + z + i + p + o + d + k + s + b + j + v + m + q
4: t + u + n + k + x + o + p + g + e + f + r + l + h > b + s + d + w + m + y + j + q + v + c + i + a + z
5: a + o + c + q + f + r + z + u + s + t + x + j + w > n + p + b + g + k + y + i + l + d + e + h + v + m
6: d + p + a + q + v + h + n + x + g + u + m + t + w > j + i + b + r + l + s + y + c + k + o + f + z + e
7: i + y + x + s + a + p + z + o + t + h + d + k + c > e + b + j + r + u + n + g + l + m + f + w + v + q
8: o + a + s + i + z + f + x + y + m + r + b + v + c > k + d + t + n + p + w + l + j + e + q + u + g + h
9: n + z + o + f + h + p + i + q + g + a + j + k + b > r + l + w + t + x + e + c + m + u + d + v + s + y
10: g + c + d + s + i + y + e + v + l + r + t + k + m > j + h + x + n + p + f + q + w + b + o + a + u + z
11: v + d + i + y + o + m + f + c + j + s + r + b + a > l + x + k + t + p + g + w + n + z + q + u + e + h
12: v + d + y + g + o + z + c + w + i + k + h + b + e > x + a + l + u + p + f + s + r + n + t + q + j + m
13: n + d + z + h + r + v + g + i + x + o + u + e + f > a + s + k + b + w + p + l + c + m + y + t + j + q
14: r + b + z + y + s + h + x + e + q + d + i + j + p > l + g + a + v + u + n + w + o + m + k + t + f + c
15: j + m + k + w + b + y + i + x + q + c + t + s + f > l + a + g + d + v + p + u + r + z + e + h + n + o
16: w + e + u + v + k + y + n + g + m + b + s + h + a > o + c + t + i + d + z + l + j + p + r + x + q + f
17: l + v + b + m + r + y + t + u + w + x + f + q + k > c + d + n + s + o + e + j + h + i + z + g + a + p
18: h + c + w + a + s + p + z + k + v + l + t + j + r > m + b + e + q + d + n + o + i + u + y + f + x + g
19: j + f + c + y + b + i + k + q + l + m + z + v + h > p + e + n + r + x + w + o + a + t + s + g + d + u
20: l + u + q + o + y + m + v + j + k + a + c + h + g > x + d + r + p + f + e + w + t + i + z + b + s + n
21: m + b + o + y + q + v + i + j + e + z + g + n + r > c + k + s + h + p + a + l + w + t + x + u + d + f
22: v + h + j + p + i + k + s + c + l + r + y + u + d > e + b + m + n + x + t + w + f + o + q + a + g + z
23: m + w + i + c + n + g + x + f + s + z + d + v + p > u + y + q + a + l + b + k + t + j + r + e + o + h
24: a + i + l + j + z + m + b + p + d + x + o + h + y > g + u + v + c + k + r + t + q + s + w + f + e + n
25: y + x + m + q + s + j + t + h + v + z + e + b + p > w + d + f + u + r + o + g + k + i + l + c + a + n
26: j + l + r + n + g + v + p + x + y + z + o + m + h > a + e + k + d + u + b + t + c + w + f + q + s + i
27: y + a + i + n + j + x + r + f + g + p + u + o + e > l + v + q + t + d + h + m + s + k + z + w + b + c
28: a + c + d + k + p + o + m + f + e + i + r + h + b > q + z + w + t + g + y + j + v + l + u + x + n + s
29: n + b + v + l + t + e + z + o + y + d + i + q + j > f + m + c + w + h + g + a + u + x + s + k + p + r
30: l + a + h + q + d + z + r + v + m + y + u + p + c > w + g + o + t + n + s + i + k + e + f + j + x + b
31: p + h + u + s + l + r + v + x + a + y + c + d + f > e + n + b + m + w + g + t + q + i + z + j + o + k
32: b + n + k + o + i + a + q + p + g + w + z + c + f > j + d + h + l + r + m + x + e + v + u + s + t + y
33: q + y + k + b + e + t + x + l + z + i + p + h + u > r + d + g + a + f + o + j + n + w + c + v + s + m
34: a + k + p + j + r + l + h + z + s + e + x + o + t > d + w + c + b + f + g + u + y + v + q + n + m + i
35: v + z + k + s + l + h + f + g + a + r + y + u + d > j + c + o + e + i + p + w + t + x + n + b + q + m
36: p + w + z + n + b + v + q + l + g + m + e + u + t > x + f + s + d + y + a + h + k + c + j + i + r + o
37: u + y + l + d + q + e + v + z + g + m + t + c + i > a + h + k + f + n + w + b + p + s + x + j + r + o
38: y + e + l + g + i + b + m + s + u + x + f + n + a > j + v + o + r + c + w + k + t + q + z + d + p + h
39: i + v + e + k + p + h + w + b + z + m + r + t + c > n + q + s + u + y + d + l + x + g + f + o + a + j
40: k + g + s + o + f + z + x + c + n + w + d + q + h > m + u + v + j + p + i + b + l + a + r + e + y + t
41: x + h + f + u + c + v + o + g + j + e + m + t + s > a + d + l + b + i + p + z + y + q + n + k + w + r
42: s + y + o + w + a + p + d + x + f + t + k + c + g > q + u + i + j + z + r + m + h + l + v + n + e + b
43: n + s + p + x + z + k + y + g + h + v + e + m + l > b + a + d + i + w + j + q + r + f + u + c + o + t
44: c + e + z + d + r + w + j + y + l + g + i + p + t > k + u + x + v + o + a + b + h + n + s + m + q + f
45: n + c + d + m + j + y + g + q + f + w + s + e + z > x + a + h + k + b + l + u + r + v + i + o + p + t
Title: Re: Each Letter Represents A Number - But Which On
Post by towr on Jul 15th, 2010, 8:14am
I can't really seem to find an "easy" way to solve this. Anybody else have any ideas?
Title: Re: Each Letter Represents A Number - But Which On
Post by MathsForFun on Jul 15th, 2010, 8:30am

on 07/15/10 at 08:14:25, towr wrote:
I can't really seem to find an "easy" way to solve this. Anybody else have any ideas?

Maybe it should be in the CS forum, since I don't know of a way of solving it without a computer.

Given that, a certain "insight" makes it quick and easy. I'm keeping that insight to myself for now, because I know that once I tell, several people will solve it within an hour. I myself solved it without the insight - but it took quite a lot of programming. I sent it to a friend who is not a good programmer, and to my surprise, he solved it very quickly. His programming was poor IMO - but it solved the problem very quickly - in contrast to my own program. It was also a much, much shorter program than mine. The insight was STUNNING - I look forward to sharing it!
Title: Re: Each Letter Represents A Number - But Which On
Post by Grimbal on Jul 15th, 2010, 2:35pm
I guess that [hide] just counting how many times a letter falls on the left of the equation would roughly be proportional to how large it is.  At least if the equations were generated randomly.[/hide]
Title: Re: Each Letter Represents A Number - But Which On
Post by MathsForFun on Jul 15th, 2010, 3:10pm

on 07/15/10 at 14:35:57, Grimbal wrote:
I guess that {snip}

I thought of that. Here's a quick way to do that visually:

[hide]* copy the inequalities into Notepad++

* the monospaced font will mean that the > is on the same place on each line (you can also use replace to add extra spaces either side of the > symbol)

* when you search for a letter, Notepad++ will highlight all occurrences, giving you a quick visual idea of whether there are more on the left or the right

Of course, you could also write a program to do this frequency analysis more accurately...[/hide]
Title: Re: Each Letter Represents A Number - But Which On
Post by towr on Jul 17th, 2010, 3:58am
I tried that, and tried various ways to get closer to a solution from that starting point, but it never got me anywhere.
And 26! is a bit too much to brute-force without a super computer. So that's not an option either.
I also tried adding the inequalities in various ways, which can eliminate many of the variables, but the best I got was one inequality with two letters on each side.
Title: Re: Each Letter Represents A Number - But Which On
Post by towr on Aug 3rd, 2010, 9:48am
Sooo... anyone have any ideas or clues?
Title: Re: Each Letter Represents A Number - But Which On
Post by JohanC on Aug 4th, 2010, 5:09pm

on 08/03/10 at 09:48:34, towr wrote:
Sooo... anyone have any ideas or clues?
My approach would be:
- Let P be an arbitrary assignment of values to letters
- Define a function F as the sum of the gaps of all the broken equations for a given P
- The idea would be to minimize F step-by-step by trying out little changes to P
- The simplest kind of change is just randomly switch the values of two letters; if that switch improves F, P would be updated, otherwise P stays unchanged
- Stop when either F has reached 0, or when no improvement is found for a while [i.e. when a local minimum is reached].
- Start over again with another random assignment.

Possible variants:
- Instead of random switches, try out all possible switches and take one of the best ones
- Instead of switching 2 letters, permutate 3 or more letters.

Problems with this kind of approach:
- Maybe it falls too quickly into a local minimum?
- If the problem is unsolvable, this approach cann't find out.
- If their would exist multiple solutions, this approach probably won't find all of them.
Title: Re: Each Letter Represents A Number - But Which On
Post by towr on Aug 5th, 2010, 12:21am

on 08/04/10 at 17:09:59, JohanC wrote:
Possible variants:
- Instead of random switches, try out all possible switches and take one of the best ones
- Instead of switching 2 letters, permutate 3 or more letters.
I tried that, up to five letters, but I didn't get a solution.

I didn't repeatedly restart from new random initial position though; I started from a single best guess. So maybe that's worth a shot.
Title: Re: Each Letter Represents A Number - But Which On
Post by JohanC on Aug 5th, 2010, 3:41am

on 08/05/10 at 00:21:13, towr wrote:
I tried that, up to five letters, but I didn't get a solution.

I didn't repeatedly restart from new random initial position though; I started from a single best guess. So maybe that's worth a shot.

When the search space is too large for (an optimized) exhaustive search, randomized approaches seem to be the only working approach. So, random starting position, and random steps. Sometimes backward steps are used to overstep local minima.
Al Zimmermann's Programming Contests site (http://www.azspcs.net/) lists similar problems where some of the world's best programmatically solvers have been competing. One of the problems involved pancake sorting (http://en.wikipedia.org/wiki/Pancake_sorting), the problem which inspired Bill Gates to the only mathematics paper he ever published. A famous contestant is Tom Rokicki (http://tomas.rokicki.com/) who convinced the team of Spiderman 3 to lend him their computer farm to crack Rubik's cube (http://www.springerlink.com/content/q088143tn805k124/).

Usually some form of simulated annealing (http://en.wikipedia.org/wiki/Simulated_annealing) is optimized for the specific problem.
Title: Re: Each Letter Represents A Number - But Which On
Post by MathsForFun on Aug 5th, 2010, 5:06am

on 08/03/10 at 09:48:34, towr wrote:
Sooo... anyone have any ideas or clues?

Here's a challenge: if someone posts a different puzzle in the same format (I will be checking that it's not a clone of my puzzle!), I will attempt to solve it WITHOUT PROGRAMMING. If I can do so, I will show the steps taken.
Title: Re: Each Letter Represents A Number - But Which On
Post by Grimbal on Aug 5th, 2010, 5:51am
l + n + e + z + v + w + o + h + y + u + m + s + a > t + c + d + g + j + p + i + x + r + q + f + b + k
n + y + g + r + w + e + z + a + d + b + t + p + x > u + i + c + o + h + l + q + v + m + j + f + s + k
p + n + t + f + u + k + v + h + y + e + d + s + x > o + w + b + r + q + i + m + g + l + a + z + j + c
u + o + j + s + c + w + h + a + f + p + g + t + q > i + e + z + x + m + v + y + b + r + k + l + n + d
b + g + v + q + r + m + x + p + h + w + f + o + c > s + j + u + l + d + e + y + n + t + z + i + a + k
k + n + q + u + a + m + e + t + g + y + w + c + j > i + v + h + r + s + p + o + f + z + l + b + x + d
u + k + b + q + w + a + x + o + f + i + e + z + y > l + j + g + m + n + d + s + v + p + t + r + h + c
y + c + w + d + e + g + j + i + t + x + n + o + s > q + u + l + b + v + k + h + p + m + z + a + f + r
f + j + x + m + n + u + k + o + z + a + s + b + r > i + l + v + p + q + d + g + t + w + c + e + h + y
x + e + v + h + i + b + j + k + g + m + a + l + n > u + c + w + o + r + z + y + d + p + s + t + f + q
z + l + h + v + w + c + o + x + b + j + f + t + r > y + m + a + e + k + n + p + s + q + g + i + d + u
i + h + f + c + n + w + a + o + x + m + r + e + g > s + k + z + p + u + t + y + q + d + l + b + j + v
v + h + b + j + p + q + e + k + w + f + g + x + c > d + s + n + z + y + i + m + a + r + u + l + t + o
c + u + l + q + z + o + x + p + y + h + j + w + f > a + e + b + n + k + t + d + g + m + r + i + v + s
v + c + a + f + k + i + u + w + n + y + h + x + j > l + b + o + e + d + r + p + t + z + m + g + s + q
f + p + i + k + v + m + u + e + s + w + a + c + b > j + d + y + g + t + q + o + h + r + l + n + z + x
s + d + b + a + t + e + m + c + p + g + l + n + w > o + q + v + h + u + j + y + z + r + i + k + x + f
o + g + u + c + b + d + j + f + k + r + s + t + n > e + p + a + y + i + q + h + w + l + z + x + m + v
z + j + i + h + a + m + b + s + t + u + w + g + v > x + n + l + f + o + q + d + y + r + e + k + c + p
g + i + s + q + c + w + t + o + v + r + z + j + u > e + l + d + a + y + b + k + x + p + m + n + f + h
w + i + j + e + n + x + o + l + u + y + a + v + g > q + c + r + s + k + b + f + m + h + d + z + t + p
j + v + h + z + s + b + f + n + y + r + u + x + a > g + m + l + c + q + o + p + w + e + i + t + k + d
e + k + h + c + j + x + s + y + d + f + z + t + n > l + w + m + i + o + r + v + g + a + q + b + p + u
f + x + w + c + d + z + h + v + b + g + m + j + o > q + i + k + e + a + s + y + p + t + l + n + r + u
f + u + v + x + t + z + d + l + q + k + y + w + e > i + a + m + s + j + b + n + c + h + r + p + o + g
s + p + k + j + t + e + f + w + o + a + l + r + c > d + n + v + z + x + g + h + q + m + u + b + i + y
p + g + i + w + u + d + b + t + j + h + e + k + n > q + s + a + l + v + z + r + x + y + f + m + c + o
t + f + a + x + r + h + u + e + k + w + o + c + z > l + p + v + d + s + m + i + q + j + g + y + b + n
s + g + v + f + a + e + q + l + m + o + c + b + x > w + d + y + j + p + n + i + t + h + u + r + z + k
h + z + r + m + s + g + x + i + f + n + j + k + t > p + l + v + q + c + y + b + u + o + a + w + d + e
p + r + f + u + t + j + g + l + w + c + n + b + s > q + v + o + h + y + k + i + m + a + e + z + d + x
e + g + n + f + k + o + u + m + y + b + x + w + q > l + j + i + s + h + t + d + c + p + z + v + r + a
x + p + a + e + v + l + i + j + u + r + h + f + t > b + m + k + g + y + z + o + c + s + q + w + d + n
z + s + n + l + g + e + y + r + j + m + q + w + o > p + f + b + x + h + v + i + d + a + t + c + k + u
p + h + y + o + t + k + f + e + i + s + c + w + b > d + u + v + l + j + n + x + r + z + m + g + q + a
i + v + q + h + z + b + w + l + c + a + g + f + s > o + m + n + r + u + y + x + t + e + d + p + k + j
z + h + p + j + a + y + u + c + s + k + g + x + n > t + r + q + m + e + l + d + w + i + o + f + b + v
x + w + o + m + q + p + y + s + v + g + e + h + t > b + n + k + z + a + d + j + l + r + f + u + c + i
e + f + g + x + m + o + h + y + c + v + n + k + j > w + q + t + s + i + u + a + r + b + z + p + l + d
d + e + m + p + n + o + w + l + h + q + t + u + r > v + z + j + i + y + f + b + s + x + c + g + a + k
x + q + a + m + k + n + v + g + e + f + c + t + p > h + s + i + d + w + u + r + b + z + o + y + j + l
d + w + m + a + i + x + e + y + k + c + p + n + h > t + f + q + l + v + z + r + g + j + o + u + s + b
w + l + x + f + q + n + s + d + e + k + r + z + i > u + j + p + v + t + m + b + y + a + h + c + g + o
e + l + p + x + m + y + o + t + k + r + v + f + c > a + w + b + j + g + q + d + h + n + z + i + s + u
e + g + i + w + k + d + m + a + s + z + n + t + u > b + v + o + c + q + p + j + f + y + r + h + x + l
Title: Re: Each Letter Represents A Number - But Which On
Post by JohanC on Aug 5th, 2010, 7:27am

on 08/05/10 at 05:06:38, MathsForFun wrote:
... I will be checking that it's not a clone of my puzzle! ...
Checking whether a list of equations is a permutation both of the letters and in the order of the equations looks even more complicated than the original problem ...
Title: Re: Each Letter Represents A Number - But Which On
Post by towr on Aug 5th, 2010, 7:32am

on 08/05/10 at 07:27:01, JohanC wrote:
Checking whether a list of equations is a permutation both of the letters and in the order of the equations looks even more complicated than the original problem ...
There are some heuristics you could use. For example how often a variable occurs on the left and right side. (Thus doing away with the order of inequalities.) I don't think it's actually as big a problem.
Title: Re: Each Letter Represents A Number - But Which On
Post by MathsForFun on Aug 5th, 2010, 8:16am

on 08/05/10 at 07:27:01, JohanC wrote:
Checking whether a list of equations is a permutation both of the letters and in the order of the equations looks even more complicated than the original problem ...

Grimbal's puzzle is not a clone of my own (see hidden text below if you want to know why). So far, the method I am trying to solve it without programming is not working at all. Sorry everyone - I thought I had a good idea. I will work with it a bit more to see if I can get anywhere. My program had no difficulty whatsoever in solving it, though. First three solutions shown below:

[hide]a = 10
b = 5
c = 20
d = 2
e = 24
f = 22
g = 19
h = 12
i = 1
j = 11
k = 21
l = 7
m = 15
n = 23
o = 4
p = 9
q = 6
r = 8
s = 13
t = 16
u = 25
v = 18
w = 26
x = 14
y = 3
z = 17

a = 10
b = 1
c = 9
d = 6
e = 20
f = 22
g = 26
h = 23
i = 2
j = 3
k = 18
l = 8
m = 12
n = 21
o = 17
p = 11
q = 4
r = 7
s = 13
t = 14
u = 24
v = 19
w = 25
x = 16
y = 5
z = 15

a = 4
b = 9
c = 10
d = 1
e = 25
f = 26
g = 19
h = 23
i = 14
j = 13
k = 2
l = 7
m = 18
n = 16
o = 11
p = 6
q = 3
r = 8
s = 24
t = 21
u = 17
v = 5
w = 20
x = 22
y = 15
z = 12

The reason I know that this puzzle is not a clone of my own is that my program is only able to find one solution to mine.[/hide]
Title: Re: Each Letter Represents A Number - But Which On
Post by Grimbal on Aug 5th, 2010, 3:53pm
I assigned a random value to the digits, created 45 random permutations and, split it in 2 groups of 13 and put the largest sum at the left.

I obviously haven't checked for unicity.  I thought 45 equations for 26 variables + the restriction that it must be a permutations should be enough. Maybe I should have tried to keep only tight inequalities to make it harder to meet.
Title: Re: Each Letter Represents A Number - But Which On
Post by Grimbal on Aug 5th, 2010, 4:40pm
Anyway, I find
[hide]a..z = [ 11, 1, 2, 6, 15, 20, 10, 23, 25, 5, 4, 19, 16, 7, 24, 17, 21, 12, 22, 13, 9, 14, 26, 3, 18, 8 ][/hide]
Title: Re: Each Letter Represents A Number - But Which On
Post by MathsForFun on Aug 6th, 2010, 12:24am

on 08/05/10 at 16:40:35, Grimbal wrote:
Anyway, I find...

Brilliant work!  8)

I think that is the only solution. Were you helped by the knowledge that it is possible to solve my puzzle without programming?
Title: Re: Each Letter Represents A Number - But Which On
Post by MathsForFun on Aug 6th, 2010, 12:48am

on 08/05/10 at 15:53:43, Grimbal wrote:
I obviously haven't checked for unicity.

Tsk tsk: http://en.wiktionary.org/wiki/unicity ;)


Quote:
Maybe I should have tried to keep only tight inequalities to make it harder to meet.

I think that the above thought is probably what cracked it for you. Ironically, I actually found the opposite - that when I tightened the inequalities to prevent solution by left-right counting, I needed more inequalities - not fewer.

I also think that my puzzle has the above unique solution with only the first 39 inequalities - but with fewer inequalities, solutions are much more difficult to find (until you get to the point where there are large numbers of solutions - which there are to Grimbal's puzzle, for example).

Regarding generalised solution methods, why did nobody see similarities with Sudoku? The basic methodology of my original program can be found at http://en.wikipedia.org/wiki/Algorithmics_of_sudoku . Shall I tell you the brilliancy that my friend spotted that speeds up the search by sevaral orders of magnitude, or shall I let you guess?
Title: Re: Each Letter Represents A Number - But Which On
Post by towr on Aug 6th, 2010, 1:36am

on 08/06/10 at 00:48:58, MathsForFun wrote:
Regarding generalised solution methods, why did nobody see similarities with Sudoku?
I still see no similarities with sudoku.


Quote:
Shall I tell you the brilliancy that my friend spotted that speeds up the search by sevaral orders of magnitude, or shall I let you guess?
Just tell, it's not like I'm likely to find it on my own after all this time.
Title: Re: Each Letter Represents A Number - But Which On
Post by Grimbal on Aug 6th, 2010, 2:50am
I solved it by just ignoring it is a permutation.  I solved it with real numbers.  I only need to rescale the solution at the end.  This makes it actually less related to sudoku.


PS:
http://en.wikipedia.org/wiki/Unicity
says: "Unicity" may also mean uniqueness. For the cryptographic meaning, see Unicity distance.
So it is not completely wrong.  But to tell you the whole story, when I said it, it was because of
http://fr.wiktionary.org/wiki/unicit%C3%A9
Title: Re: Each Letter Represents A Number - But Which On
Post by MathsForFun on Aug 6th, 2010, 3:20am

on 08/06/10 at 02:50:23, Grimbal wrote:
I solved it by just ignoring it is a permutation.  I solved it with real numbers.

That is the big insight that my friend had! In the case of my puzzle, the super-simple LP Solve model appended will solve it instantaneously. For less linear-programming friendly versions of this problem, it might be slow - but this can be resolved just by adding extra info (e.g. the limits of each variable, the total sum, the other limits of each expression etc) - it is usually the case in linear programming that extra information leads to faster resolution. My own program is actually MUCH more complex than the LP model shown - but when I incorporated the knowledge that permutation work is not required, it found solutions something like 100x faster (it also checks that a solution is valid, while the simple model shown below could, in theory, give an invalid answer, and it also incorporates features to find multiple solutions, which would be tricky using the simple model shown below).


Quote:
I only need to rescale the solution at the end.  This makes it actually less related to sudoku.

Hmmmm - have you read the whole of the sudoku algorithms article I linked previously in detail?

I still think that I may be able to solve yours without programming: my basic method is to convert expressions (left or right hand side of an inequality) into equations by guessing at their values, solving groups of them as simultaneous equations, and then refining the values of the guesses. In the case of my puzzle, this will deliver the solution on a plate, because each left hand side is equal to 176, and each right hand side is equal to 175. In the case of your puzzle, I haven't yet made any progress - but I will try it some more when time permits. If I find a way, I will post it here.

Appendix: LP Solve Model

min: ;

t + a + m + y + k + n + q + z + s + r + p + i + c >= 176;
o + e + d + b + j + h + g + l + w + v + f + x + u <= 175;
c + o + q + x + w + d + u + h + g + p + l + a + j >= 176;
b + z + k + t + f + m + s + n + e + y + v + i + r <= 175;
.
.
.
n + s + p + x + z + k + y + g + h + v + e + m + l >= 176;
b + a + d + i + w + j + q + r + f + u + c + o + t <= 175;
c + e + z + d + r + w + j + y + l + g + i + p + t >= 176;
k + u + x + v + o + a + b + h + n + s + m + q + f <= 175;

int 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;
Title: Re: Each Letter Represents A Number - But Which On
Post by towr on Aug 6th, 2010, 3:46am
There is no reason why the left hand side should be 176 and the right side 175. That solution seems to work only because you hit a lucky break. If you know that the difference between the two sides is always the same, you could just do Gaussian elimination, and just 23 "inequalities" should be enough.
And likewise I don't see how solving it with real numbers would give a solution in general. There should be plenty of possible real solutions in the 26-dimensional piece of space delineated by the hyperplanes that scale to something other than the correct solution.

Meh. Maybe I'm just a sore loser. But at least I know why I can't find a solution in any reasonable time.
Title: Re: Each Letter Represents A Number - But Which On
Post by MathsForFun on Aug 6th, 2010, 5:21am

on 08/06/10 at 03:46:29, towr wrote:
There is no reason why the left hand side should be 176 and the right side 175. That solution seems to work only because you hit a lucky break.

As I'm sure you will know, the fixed values for the 90 expressions given were deliberate policy on my part to minimise the risk of the previously discussed counting method working. The program I wrote to set the puzzle was instructed to make a random selection of 13 letters (just like Grimbal's puzzle writing program did), but to reject them if they did not sum to 176.


Quote:
And likewise I don't see how solving it with real numbers would give a solution in general.

I agree. That appears to be analogous to my solution of guessing values for expressions. That may work for Grimbal's puzzle - but if it does, it will certainly not be as easy as it would be for my puzzle.


Quote:
Maybe I'm just a sore loser.

Speaking for myself, if someone else had already solved the puzzle, and I wanted to solve it myself, I would go ahead and post my own solution anyway. I might even borrow someone else's insights! On one occasion, it took me a week to solve a problem - working quite intensively - and I just updated the forum (not this one - a different one) on progress as I went. A nice relaxed attitude - but probably one which will guarantee that I will never be an uberpuzzler!  ;)
Title: Re: Each Letter Represents A Number - But Which On
Post by Grimbal on Aug 6th, 2010, 5:25am
As it happens, the original problem has always an excess of 1.  I also felt cheated when I saw that.

More precisely, my method was exactly as MathsForFun described, starting with an estimate based on the left and right count and then making small adjustments (in steps of .1) in the direction that improves the worst unsatisfied inequality.

I was hoping to just find a good starting point for the next step and expected I'd have to search for actual permutations close to that solution, but since the excess is always 1, it converged automatically to the exact all-integer solution.

I also though of optimization under constraint*, but I don't know of any library right now so I would have had to find one and learn how to use it.

edit:
* What I meant is Linear programming, which optimizes a given cost function under linear constraints.
Title: Re: Each Letter Represents A Number - But Which On
Post by MathsForFun on Aug 6th, 2010, 5:52am

on 08/06/10 at 05:25:04, Grimbal wrote:
As it happens, the original problem has always an excess of 1.  I also felt cheated when I saw that.

Sorry about that. At the time I posted the puzzle, it didn't occur to me that I had created this vulnerability. I only realised when JohanC's post caused me to think again about solution methods.

I would point out that I am not alone in making such a mistake - history is littered with mathematicians who thought they were making a cipher stronger when in fact they were making it weaker (the reflection wheel in the Enigma machine is an obvious example). Also, I give myself credit for correctly guessing that counting would be the first line of attack!


Quote:
I also though of optimization under constraint, but I don't know of any library right now so I would have had to find one and learn how to use it.

With a good setup, it could probably be done with a spreadsheet solver.
Title: Re: Each Letter Represents A Number - But Which On
Post by towr on Aug 6th, 2010, 6:09am

on 08/06/10 at 05:25:04, Grimbal wrote:
I also though of optimization under constraint, but I don't know of any library right now so I would have had to find one and learn how to use it.
I've had swi-prolog's constraint library have a go at it, but after two hours it still had nothing. Maybe my computer isn't fast enough. (Well, it definitely isn't, in general.)
Title: Re: Each Letter Represents A Number - But Which On
Post by JohanC on Aug 6th, 2010, 9:50am
Still wondering...

The trick with real numbers wouldn't always solve the general problem when real inequalities are involved, I suppose. It might get attrackted to an optimal real solution which is not easily converted back to integers.

MathsFF, which soduko-solver approach did you use? Would you eventually get all solutions to Grimbals puzzle?
Or are you using constraint programming, which I also feel wouldn't always find the solution.

The wiki page mentions a stochastic search, similar to the one I proposed. Did somebody try something like that?
Title: Re: Each Letter Represents A Number - But Which On
Post by MathsForFun on Aug 6th, 2010, 10:43am

on 08/06/10 at 09:50:15, JohanC wrote:
MathsFF, which soduko-solver approach did you use?

Integer programming. I once wrote a brute-force sudoku solver, but a friend pointed out that while it had no trouble with "normal" puzzles with, say, 30 clues, it could not manage "difficult" ones with, say 18 clues (more details on difficult sudoku puzzles in the previously linked wikipedia article), so I wrote a second one based on integer programming, and it can solve any sudoku puzzle without difficulty.


Quote:
Would you eventually get all solutions to Grimbals puzzle?

Yes - it would (it might be a slow process, though, because Grimbal's puzzle appears to have a large number of solutions - but it would find them many orders of magnitude more quickly than brute force).
Title: Re: Each Letter Represents A Number - But Which On
Post by towr on Aug 6th, 2010, 2:28pm

on 08/06/10 at 09:50:15, JohanC wrote:
Or are you using constraint programming, which I also feel wouldn't always find the solution.
As I understand it, constraint programming would always find the solutions, but it may take very, very long. It uses the constraints to limit the search space, but does search everywhere there might be a solution afaik.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board