Author |
Topic: Each Letter Represents A Number - But Which One? (Read 2878 times) |
|
MathsForFun
Full Member
Posts: 153
|
 |
Each Letter Represents A Number - But Which One?
« on: Jul 13th, 2010, 1:56pm » |
 Quote  Modify
|
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
|
|
 IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #1 on: Jul 15th, 2010, 8:14am » |
Quote Modify
|
I can't really seem to find an "easy" way to solve this. Anybody else have any ideas?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #2 on: Jul 15th, 2010, 8:30am » |
Quote Modify
|
on Jul 15th, 2010, 8:14am, 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!
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #3 on: Jul 15th, 2010, 2:35pm » |
Quote Modify
|
I guess that 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.
|
|
IP Logged |
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #4 on: Jul 15th, 2010, 3:10pm » |
Quote Modify
|
on Jul 15th, 2010, 2:35pm, Grimbal wrote:
I thought of that. Here's a quick way to do that visually:
* 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...
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #5 on: Jul 17th, 2010, 3:58am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #6 on: Aug 3rd, 2010, 9:48am » |
Quote Modify
|
Sooo... anyone have any ideas or clues?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #7 on: Aug 4th, 2010, 5:09pm » |
Quote Modify
|
on Aug 3rd, 2010, 9:48am, 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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #8 on: Aug 5th, 2010, 12:21am » |
Quote Modify
|
on Aug 4th, 2010, 5:09pm, 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.
|
| « Last Edit: Aug 5th, 2010, 12:23am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #9 on: Aug 5th, 2010, 3:41am » |
Quote Modify
|
on Aug 5th, 2010, 12:21am, 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 lists similar problems where some of the world's best programmatically solvers have been competing. One of the problems involved pancake sorting, the problem which inspired Bill Gates to the only mathematics paper he ever published. A famous contestant is Tom Rokicki who convinced the team of Spiderman 3 to lend him their computer farm to crack Rubik's cube.
Usually some form of simulated annealing is optimized for the specific problem.
|
|
IP Logged |
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #10 on: Aug 5th, 2010, 5:06am » |
Quote Modify
|
on Aug 3rd, 2010, 9:48am, 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.
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #11 on: Aug 5th, 2010, 5:51am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #12 on: Aug 5th, 2010, 7:27am » |
Quote Modify
|
on Aug 5th, 2010, 5:06am, 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 ...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #13 on: Aug 5th, 2010, 7:32am » |
Quote Modify
|
on Aug 5th, 2010, 7:27am, 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.
|
| « Last Edit: Aug 5th, 2010, 7:32am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #14 on: Aug 5th, 2010, 8:16am » |
Quote Modify
|
on Aug 5th, 2010, 7:27am, 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:
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.
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #15 on: Aug 5th, 2010, 3:53pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #16 on: Aug 5th, 2010, 4:40pm » |
Quote Modify
|
Anyway, I find
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 ]
|
|
IP Logged |
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #17 on: Aug 6th, 2010, 12:24am » |
Quote Modify
|
on Aug 5th, 2010, 4:40pm, Grimbal wrote:
Brilliant work! 
I think that is the only solution. Were you helped by the knowledge that it is possible to solve my puzzle without programming?
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #18 on: Aug 6th, 2010, 12:48am » |
Quote Modify
|
on Aug 5th, 2010, 3:53pm, 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?
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #19 on: Aug 6th, 2010, 1:36am » |
Quote Modify
|
on Aug 6th, 2010, 12:48am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #20 on: Aug 6th, 2010, 2:50am » |
Quote Modify
|
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
|
| « Last Edit: Aug 6th, 2010, 2:54am by Grimbal » |
IP Logged |
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #21 on: Aug 6th, 2010, 3:20am » |
Quote Modify
|
on Aug 6th, 2010, 2:50am, 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;
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #22 on: Aug 6th, 2010, 3:46am » |
Quote Modify
|
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.
|
| « Last Edit: Aug 6th, 2010, 4:06am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #23 on: Aug 6th, 2010, 5:21am » |
Quote Modify
|
on Aug 6th, 2010, 3:46am, 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!
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Each Letter Represents A Number - But Which On
« Reply #24 on: Aug 6th, 2010, 5:25am » |
Quote Modify
|
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.
|
| « Last Edit: Aug 7th, 2010, 6:20am by Grimbal » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print