Brain-Teaser 660: An efficient type
From The Sunday Times, 3rd March 1974 [link]
My typewriter had the standard keyboard:
row 1: QWERTYUIOP
row 2: ASDFGHJKL
row 3: ZXCVBNMuntil I was persuaded by a time-and-motion expert to have it “improved”. When it came back I found that none of the letters was in its original row, though the number of letters per row remained unchanged. The expert assured me that, once I got used to the new system, it would save hours.
I tested it on various words connected with my occupation — I am a licensed victualler — with the following results. The figures in parentheses indicate how many rows I had to use to produce the word:
BEER (1)
STOUT (1)
SHERRY (2)
WHISKY (3)
HOCK (2)
LAGER (2)
VODKA (2)
CAMPARI (2)
CIDER (3)
FLAGON (2)
SQUASH (2, but would have been 1 but for a single letter)Despite feeling a trifle MUZZY (a word which I was able to type using two rows) I persevered, next essaying CHAMBERTIN.
Which rows, in order, did I use?
This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.
[teaser660]
Frits, 
GeoffR, and 1 other are discussing. 
S2T2 
Jim Randell 9:05 am on 12 January 2021 Permalink |
We can use the [[
SubstitutedExpression]] solver from the enigma.py library to solve this puzzle. Although the program generated does not run under the standard CPython interpreter, as it exceeds the limit on statically nested blocks, but it runs fine with the PyPy interpreter, which does not have this limitation, or we can use the recently added [[--denest]] option, which generates code that is not as deeply nested, and allows the program to run under the standard Python interpreter.The following run file executes in 76ms. (Internal runtime of the generated code is 468µs).
Run: [ @replit ]
#! python3 -m enigma -rr SubstitutedExpression --distinct="" --digits="1,2,3" # no letter is in its original row --invalid="1,QWERTYUIOP" --invalid="2,ASDFGHJKL" --invalid="3,ZXCVBNM" # number of letters per row remained unchanged --code="count = multiset.from_seq" "count([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]) == {1: 10, 2: 9, 3: 7}" # rows used for each word "len({B, E, E, R}) = 1" "len({S, T, O, U, T}) = 1" "len({S, H, E, R, R, Y}) = 2" "len({W, H, I, S, K, Y}) = 3" "len({H, O, C, K}) = 2" "len({L, A, G, E, R}) = 2" "len({V, O, D, K, A}) = 2" "len({C, A, M, P, A, R, I}) = 2" "len({C, I, D, E, R}) = 3" "len({F, L, A, G, O, N}) = 2" "len({S, Q, U, A, S, H}) = 2" "len({M, U, Z, Z, Y}) = 2" # SQUASH is typed on one row, except for a single letter "sorted(count([S, Q, U, A, S, H]).values()) == [1, 5]" # answer is the rows involved in typing CHAMBERTIN --answer="(C, H, A, M, B, E, R, T, I, N)" # [optional] less verbose output --template="" # [experimental] work around static block limit --denest=-1 # apply fix for CPythonSolution: The rows involved in typing CHAMBERTIN are: 1, 3, 1, 2, 2, 2, 2, 3, 2, 1.
The new assignment of rows to keys is:
Although we can’t tell what order the keys are in on a row.
LikeLiked by 1 person
Frits 9:54 am on 12 January 2021 Permalink |
@Jim, repl.it isn’t working for this puzzle
LikeLike
Jim Randell 10:07 am on 12 January 2021 Permalink |
@Frits: Odd. It works for me if I’m logged in, but not if I try to run the repl anonymously. You have to jump through some hoops to get PyPy running in repl.it, so it is not surprising the end result is a bit fragile.
LikeLike
Frits 10:21 am on 12 January 2021 Permalink |
Yesterday I updated PyPy. I didn’t realize repl.it depended on it.
(error: Makefile:52: recipe for target ‘exec_pip’ failed). I’ll try to reinstall Pip under PyPy.
Have you already used the 64 bit PyPy nightly build?
LikeLiked by 1 person
Jim Randell 10:49 am on 12 January 2021 Permalink |
@Frits: I don’t think your local installation of PyPy will affect repl.it. I think the problem is running PyPy under repl.it (which is not directly supported). Maybe the template I used to allow you to do this only works for the owner of the repl. (You could try forking it and see if that works for you).
LikeLike
Frits 10:57 am on 12 January 2021 Permalink |
I have now installed the latest nightly build of PyPy ([PyPy 7.3.4-alpha0 with MSC v.1927 64 bit (AMD64)] on win32).
It seems to be a recent error in PyPy.
“pypy3 -m ensurepip” doesn’t give errors anymore but repl.it still fails.
LikeLike
Jim Randell 2:09 am on 13 January 2021 Permalink |
@Frits: It should be working now.
LikeLike
Frits 10:53 am on 13 January 2021 Permalink |
Thanks, it works but it takes approx 30 seconds.
The program itself takes 39ms.
LikeLike
Frits 10:14 am on 12 January 2021 Permalink |
@Jim,
If the S of SQUASH was the single letter in a different row the multiset line would not recognize it (it depends how you interpret “a single letter”).
Do you know an easy way how I can execute the run file like a normal py file in a Command Prompt (without creating a main each and every time)?
LikeLike
Jim Randell 10:41 am on 12 January 2021 Permalink |
@Frits: I would have thought if the S was on a different line then typing SQUASH would involve typing 2 letters that were on a different row. But the puzzle text is open to interpretation there. To try the other interpretation you can just remove one of the S‘s from the list on line 32 and check for a
[1, 4]allocation of letters. Fortunately it doesn’t change the answer.On Unix like operating systems the
#!line tells the OS how to execute a file, so the file just needs to be executable. (And a while ago I made a command called run, to make it even easier to run such files).Otherwise you can just run the command manually. So for this file:
Or if you haven’t put enigma.py in your
$PYTHONPATH, just put them in the same directory (or specify full paths):Alternatively you can run it from the Python shell, using the [[
enigma.run()]] function:% pypy >>>> from enigma import run >>>> run("teaser660.run") A=1 B=2 C=1 D=3 E=2 F=1 G=1 H=3 I=2 J=1 K=1 L=1 M=2 N=1 O=3 P=2 Q=3 R=2 S=3 T=3 U=3 V=1 W=2 X=1 Y=2 Z=2 (C, H, A, M, B, E, R, T, I, N) = (1, 3, 1, 2, 2, 2, 2, 3, 2, 1) [1 solution](I have [[
from enigma import *]] in my.pythonrcfile, so code from enigma.py is always available in interactive Python shells, and I don’t need to import them separately).LikeLike
Frits 11:08 am on 12 January 2021 Permalink |
@Jim, thanks.
It doesn’t work if the filetype is py but that’s OK.
LikeLike
Frits 11:05 am on 13 January 2021 Permalink |
@Jim, 4th run still takes 15 second, it doesn’t matter.
I am busy with a program to solve the puzzle without using brute force but am kind of stuck….
LikeLike
Jim Randell 6:18 pm on 13 January 2021 Permalink |
People who use the [[
SubstitutedExpression]] solver from the enigma.py library might be interested in the experimental version of enigma.py in this repl [ @repl.it ].It adds the
denestparameter to [[SubstitutedExpression]] (which available as--denestor-Xfrom the command line or in run files), that changes the way the code is generated to reduce the amount of nesting in the generated code.The upshot of this is, if you are using [[
SubstitutedExpression]] and you run foul of the"SyntaxError: too many statically nested blocks"issue, you can just use [[SubstitutedExpression(..., denest=1)]] (or add the--denestor-Xparameter to a run file or on the command line).The run file given above, with the additional
--denestparameter runs in 93ms using CPython 2.7.Assuming no problems show up in further testing, this will be rolled out in the next enigma.py update.
Update: I have rolled this out in the
2021-01-14version of enigma.py.LikeLike
Frits 7:05 pm on 13 January 2021 Permalink |
@Jim Thanks, it works.
However, –verbose=256 doesn’t seem to work properly anymore.
LikeLike
Frits 10:55 pm on 16 January 2021 Permalink |
@Jim, I don’t know if this is caused by your latest update.
from enigma import SubstitutedExpression # the alphametic puzzle p = SubstitutedExpression( [ "WXYZ = 3713", ], distinct="", digits="1,3,5,7,9", answer="W, XYZ", d2i={}, verbose=256 ) for (_, ans) in p.solve(): print(f"{ans}")No solution is given, see generated code:
[SubstitutedExpression: replacing ({WXYZ} = 3713) -> (3713 = {WXYZ})] -- [code language="python"] -- def _substituted_expression_solver1(): try: _x_ = int(3713) except NameError: raise except: raise if _x_ >= 0: _Z = _x_ % 10 if _Z != 0 and _Z != 1 and _Z != 2 and _Z != 3 and _Z != 4 and _Z != 5 and _Z != 6 and _Z != 7 and _Z != 8 and _Z != 9: _x_ //= 10 _Y = _x_ % 10 if _Y != 0 and _Y != 1 and _Y != 2 and _Y != 3 and _Y != 4 and _Y != 5 and _Y != 6 and _Y != 7 and _Y != 8 and _Y != 9: _x_ //= 10 _X = _x_ % 10 if _X != 0 and _X != 1 and _X != 2 and _X != 3 and _X != 4 and _X != 5 and _X != 6 and _X != 7 and _X != 8 and _X != 9: _x_ //= 10 _XYZ = _Z + _Y*10 + _X*100 _W = _x_ % 10 if _W != 0 and _W != 1 and _W != 2 and _W != 3 and _W != 4 and _W != 5 and _W != 6 and _W != 7 and _W != 8 and _W != 9: _x_ //= 10 if _x_ == 0: _WXYZ = _Z + _Y*10 + _X*100 + _W*1000 _r_ = (_W), (_XYZ) yield ({ 'W': _W, 'X': _X, 'Y': _Y, 'Z': _Z }, _r_)LikeLike
Jim Randell 11:08 pm on 16 January 2021 Permalink |
@Frits
The
digitsparameter should be a collection of permissible digits (not a string), e.g.:LikeLike
Frits 11:40 pm on 16 January 2021 Permalink |
Thanks, I copied it from the run version (something which I normally don’t do).
LikeLike
Frits 6:17 pm on 14 January 2021 Permalink |
Value 0b110 means letter can reside in row 1 or 2.
from itertools import combinations as comb letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" orig = ["QWERTYUIOP", "ASDFGHJKL", "ZXCVBNM"] sol = ["ACFGJKLNVX", "BEIMPRWYZ", "DHOQSTU"] # only used for printing common1 = [set("BEER"), set("STOUT")] common2 = [set("LAGER"), set("CAMPARI"), set("SHERRY"), set("HOCK"), set("VODKA"), set("FLAGON"), set("SQUASH"), set("MUZZY")] common3 = [set("WHISKY"), set("CIDER")] r = {4 : "1", 2 : "2", 1 : "3"} # row number # return 0 if all letters have been uniquely placed in a row def unsolved(): c = 0 for let in letters: c += d[let] if d[let] not in {1, 2, 4}: return c return 0 # remove <val> from letter <let> def remove(let, val, text = ""): if d[let] & val == 0: return # already removed d[let] = d[let] & (7 - val) if text != "": print(f"remove letter {let} from row {r[val]} {text}") # one row in common def cond1(s): # skip if all letters in <s> are known if all(d[x] in {1, 2, 4} for x in s): return # check if letters in <s> have only one common bit common = 7 for x in s: common &= d[x] if common in {1, 2, 4}: print(f"place letters {','.join(s)} in row {r[common]} ", end = "") print("(as they have to share 1 row)") for x in s: d[x] = common # set all letters to the same value # two rows in common def cond2(s): known = [x for x in s if d[x] in {1, 2, 4}] rows_used = set(d[x] for x in known) if len(rows_used) == 2: # we have solved letters in 2 rows # so all letters in <s> have to be in these 2 rows twoRows = sum(rows_used) missing_row = 7 - twoRows for x in s: if x in known: continue # letter can be in either one of the 2 rows? if d[x] == twoRows: continue rows_used = sorted(list(rows_used), reverse=1) text = "(letters "+ ",".join(s) +" must occur in rows " text += ", ".join(r[x] for x in rows_used) + ")" remove(x, missing_row, text) # three rows in common def cond3(s): # for each row check candidates for i in [1, 2, 4]: li = [x for x in s if d[x] & i] if len(li) == 1 and d[li[0]] != i: # one candidate for row i print(f"place letter {li[0]} in row {r[i]} (other ", end = "") print(f"letters in {','.join(s)} are not possible in row {r[i]})") d[li[0]] = i return # check if all letters in a row are known def row_full(): for i, n in enumerate([4, 2, 1]): c = 0 for let in letters: if d[let] == n: c += 1 if c == len(orig[i]): # row <i> is full so remove <i> from other candidates for let in letters: if d[let] == n: continue remove(let, n, "(already " + str(len(orig[i])) + " letters have to be in row " + r[n] +")") # check whether the number of letters in bottom 2 rows exceeds 16 def bottom2(c1 ,c2): common_letters = c1 & c2 if len(common_letters) < 2: return False known = [x for x in common_letters if d[x] in {1, 2, 4}] rows_used = list(set(d[x] for x in known)) if len(rows_used) != 1: return False bot2 = [x for x in common_letters if x != known[0] and x not in orig[0] and d[x] & d[known[0]] == 0] # different row from known # known[0] in one bottom row and <bot2> in the other bottom row? if len(bot2) > 0: # suppose <bot2> is not in top row, so <bot2> and <known> encompass # 2 rows, this means that all letters in c1 and c2 are in bottom 2 rows # check if letters in bottom 2 rows exceeds 16 (9 + 7) # count entries in 2 bottom rows if <bot2> is not in top row li = [x for x in letters if x in orig[0] or # the 10 QWERTYUIOP entries ((d[x] & 4) == 0 or # not in top row x in (c1 | c2) )] # in c1 or in c2 max = len(orig[1]) + len(orig[2]) if len(li) > max: # put QWERTY... up front notTop = {x for x in orig[0]} | {x for x in letters if d[x] & 4 == 0} # letter <bot2[0]> can not be in bottom 2 rows text = "(assuming letter " + bot2[0] + " in bottom 2 rows leads to\n" text += "letters " + ",".join(notTop | c1 | c2) text += " in bottom 2 rows (exceeding total of " + str(max) + "))" remove(bot2[0], 1, text) remove(bot2[0], 2, text) return True return False # print rows def report(li): print() for i, x in enumerate(li): for y in x: if d[y] == (1 << (2 - i)): # letter is known print(f"{y} = {d[y]:<5}", end=" ") else: print(f"{y} = {d[y]:#05b}", end=" ") print() print() d = dict() # initialize letters for x in letters: d[x] = 7 # remove original row number for each letter for i, y in enumerate(orig): for x in y: remove(x, (1 << (2-i))) prev = 0 for loop in range(99): for x in common1: cond1(x) for x in common2: cond2(x) for x in common3: cond3(x) row_full() # check if all letters in a row are known nr_unsolved = unsolved() if nr_unsolved == 0: # are we done? report(sol) squash_rows = sorted(d[x] for x in "SQUASH") if squash_rows[0] != squash_rows[1] or \ squash_rows[-1] != squash_rows[-2]: print("letters in SQUASH are all in one row but for a single letter") break report(sol) if nr_unsolved == prev: # nothing has been solved in this loop # check all combinations of words which reside on 2 rows for c1, c2 in comb(common2, 2): # check whether the number of letters in bottom 2 rows exceeds 16 if bottom2(c1, c2): break prev = nr_unsolvedLikeLike
John Crabtree 1:04 am on 15 January 2021 Permalink |
Q, W, E, R, T, Y U, I, O, P (10)
A, S, D, F, G, H, J, K, L (9)
Z, X, C, V, B, N, M (7)
BEER (1) B, E, R -> row 2
STOUT (1) S, T, O, U -> row 3
only 3 more letters can go to row 3, and from CIDER, at least one must be D or I
LAGER (2) A, G, L -> row 1
SQUASH (2*) Q, H -> row 3 (full except for D or I)
first row P, W, Y – > row 2
second row F, J, K -> row 1
HOCK (2) C -> row 1
CIDER (3) D -> row 3 (full), I -> row 2
MUZZY (2) M, Z -> row 2 (full)
third row N, X, V -> row 1
CHAMBERTIN comes from rows 1, 3, 1, 2, 2, 2, 2, 3, 2, 1
In this method WHISKY (3), VODKA (2), CAMPARI (2) and FLAGON (2) are redundant
LikeLike
Jim Randell 5:22 am on 15 January 2021 Permalink |
If I remove the WHISKY, VODKA, CAMPARI, FLAGON conditions in my program it finds 4 possible solutions. So they can’t all be redundant.
But adding just CAMPARI back in gets us back to a unique solution.
LikeLike
Frits 9:52 am on 15 January 2021 Permalink |
True, the problem lies with the CIDER (3) D …. deduction.
LikeLike
John Crabtree 3:33 pm on 15 January 2021 Permalink |
Jim and Frits, thank you. originally I used CAMPARI. In my incorrect CIDER (3) deduction I thought that E and R were in row 1. 🙂
LikeLike
GeoffR 4:13 pm on 15 January 2021 Permalink |
% A Solution in MiniZinc include "globals.mzn"; set of int: rows = 1..3; var rows: A; var rows: B; var rows: C; var rows: D; var rows: E; var rows: F; var rows: G; var rows: H; var rows: I; var rows: J; var rows: K; var rows: L; var rows: M; var rows: N; var rows: O; var rows: P; var rows: Q; var rows: R; var rows: S; var rows: T; var rows: U; var rows: V; var rows: W; var rows: X; var rows: Y; var rows: Z; % Standard keyboard layout % row1 = Q, W, E, R, T, Y, U, I, O, P (10 letters) % row2 = A, S, D, F, G, H, J, K, L (9 letters) % row3 = Z, X, C, V, B, N, M (7 letters) % 1st row letters must be in a different row constraint Q != 1 /\ W != 1 /\ E != 1 /\ R != 1 /\ T != 1 /\ Y != 1 /\ U != 1 /\ I != 1 /\ O != 1 /\ P != 1; % 2nd row letters must be in a different row constraint A != 2 /\ S != 2 /\ D != 2 /\ F != 2 /\ G != 2 /\ H != 2 /\ J != 2 /\ K != 2 /\ L != 2; % 3rd row letters must be in a different row constraint Z != 3 /\ X != 3 /\ C != 3 /\ V != 3 /\ B != 3 /\ N != 3 /\ M != 3; % Letter constraints for three new rows % New 1st row constraint count_eq ( [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], 1, 10); % New 2nd row constraint count_eq ( [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], 2, 9); % New 3rd row constraint count_eq ( [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], 3, 7); % (Rows) I had to use to produce the words % BEER(1) constraint card({B,E,E,R}) == 1; % STOUT (1) constraint card ({S,T,O,U,T}) == 1; % SHERRY (2) constraint card({S,H,E,R,R,Y}) == 2; % WHISKY (3) constraint card({W,H,I,S,K,Y}) == 3; % HOCK (2) constraint card({H,O,C,K}) == 2; % LAGER (2) constraint card( {L,A,G,E,R}) == 2; % VODKA (2) constraint card({V,O,D,K,A}) == 2; % CAMPARI (2) constraint card ({C,A,M,P,A,R,I}) == 2; % CIDER (3) constraint card ({C,I,D,E,R}) == 3; % FLAGON (2) constraint card({F,L,A,G,O,N}) == 2; % SQUASH (2, but would have been 1 but for a single letter) % There are two rows for these letters. % If four letters in 'QUASH' (i.e. missing first S out) % have a cardinality of 1, the other letter one must be % in a different row on its own. constraint (card ({U,A,S,H}) == 1 \/ card ({Q,A,S,H}) == 1 \/ card ({Q,U,S,H}) == 1 \/ card ({Q,U,A,H}) == 1 \/ card ({Q,U,A,S}) == 1); % MUZZY(2 rows) constraint card({M,U,Z,Z,Y}) == 2; output [ "CHAMBERTIN rows are " ++ show([C,H,A,M,B,E,R,T,I,N]) ++ "\n" ++ "\nLETTERS : [A, B, C, D, E, F, G, H, I, J, K, L, M]" ++ "\nROWS : " ++ show( [A, B, C, D, E, F, G, H, I, J, K, L, M]) ++ "\nLETTERS : [N, O, P, Q, R, S, T, U, V, W, X, Y, Z]" ++ "\nROWS : " ++ show([N, O, P, Q, R, S, T, U, V, W, X, Y, Z]) ++ "\n" ++ "\n" ++ "New Row 1 is [A,C,F,G,J,K,L,N,V,X] " ++ "\n" ++ "New Row 2 is [B,E,I,M,P,R,W,Y,Z] " ++ "\n" ++ "New Row 3 is [D,H,O,Q,S,T,U]" ]; % CHAMBERTIN rows are [1, 3, 1, 2, 2, 2, 2, 3, 2, 1] % LETTERS : [A, B, C, D, E, F, G, H, I, J, K, L, M] % ROWS [1, 2, 1, 3, 2, 1, 1, 3, 2, 1, 1, 1, 2] % LETTERS : [N, O, P, Q, R, S, T, U, V, W, X, Y, Z] % ROWS [1, 3, 2, 3, 2, 3, 3, 3, 1, 2, 1, 2, 2] % New rows follow from above values % New Row 1 is [A,C,F,G,J,K,L,N,V,X] % New Row 2 is [B,E,I,M,P,R,W,Y,Z] % New Row 3 is [D,H,O,Q,S,T,U] % ---------- % ==========LikeLike