8
$\begingroup$

A magician by the name of Jason carries a deck of cards with him everywhere he goes. He has a game where you can say any phrase and a specific card will correspond with that phrase. The goal of the game is to find out what rule is being used to choose the card that matches the phrase.

The deck is in the order shown, with the Ace of Spades being the first card and the Ace of Hearts being the last card:

enter image description here image courtesy of sites.google.com/site/erfarmer/premo

Here are some example phrases with the correct card in bold, and that card's number in the deck in bold parenthesis.

This phrase will be the eight of spades. Eight of Spades (8)

Bond. James Bond. Eight of Hearts (45)

Houston, we have a problem. Eight of Hearts (45)

Doughnut. Nine of Hearts (44)

Donut. Eight of Diamonds (21)

United States. Four of Diamonds (17)

Canada. Seven of Clubs (33)

Jason, can you just tell me how you are doing this? Two of Hearts (51)

I won't tell anybody! Seven of Clubs (33)

Yes. Queen of Clubs (28)

No. Three of Diamonds (16)

To clarify a bit, the whole magician story of Jason isn't relevant to figuring out how the number is calculated, I just wanted to give it a story so I could make sequels of different card-styled puzzles if this is popular. In addition, I used a Lua script to produce these results so I will provide an obfuscated version of that Lua script so you may try your own phrases and verify the ones that are here. You can try to de-obfuscate the script to find the solution, but I think it would be more difficult than just figuring it out.

Capitalization, punctuation, and anything other than a letter does not matter for finding the answer and is stripped. The case of the letter does not matter.

If you'd like to verify and test your own phrases, the script can be found here (Lua 5.2) http://pastebin.com/4BXrH9jw 32-bit
http://pastebin.com/3e5NKm7L 64-bit
Usage is simple; feed your phrase as the first argument of the program and you will get a card out. Thanks to moonbutt74 for compiling the 64-bit verison, and to 2012rcampion for identifying where the issue was that was preventing this from running on some systems.


Hint 1:

If you know the method, you can calculate short phrases mentally and medium phrases with the help of a pen and paper.



Hint 2:

Huey Lewis and the News might tell you that one of the steps is pretty hip.

$\endgroup$
  • 1
    $\begingroup$ @moonbutt74 I am on Windows and have Lua installed, so I created a file called card_puzzle.lua and then go like this in my command prompt: lua card_puzzle.lua "Phrase goes here." $\endgroup$ – ChipperNickel Sep 5 '15 at 0:58
  • $\begingroup$ This is an intriguing question, I haven't figured it out yet. $\endgroup$ – Sam Weaver Sep 5 '15 at 2:51
  • $\begingroup$ @SamWeaver I just noticed a bug in the obfuscated code, and I'm not sure if you were even using the script as assistance, but if you were I'd like you to check the new pastebin link I put up, the old one was giving incorrect answers for some phrases. $\endgroup$ – ChipperNickel Sep 5 '15 at 3:04
  • $\begingroup$ I don't know why but I really like how this question was posed. Time to reverse engineer? =) $\endgroup$ – Hackiisan Sep 5 '15 at 7:12
  • 3
    $\begingroup$ "anything other than a lowercase letter does not matter" do you mean we should skip the uppercase letters (e.g. first letters of lines)? $\endgroup$ – Jet Sep 5 '15 at 12:07
5
$\begingroup$

  1. Set the value of each letter to its position in the alphabet, i.e. $a=1, b=2, \ldots, z=26$
  2. Count the number of vowels (a,e,i,o,u) in the phrase. Let's call this $V_{\text{num}}$
  3. Count the total number of letters in the phrase. Let's call this $L_{\text{num}}$
  4. Let the value of the first letter in the sentence be $L$.
  5. Use this formula:

    $$\text{Card} = (V_{\text{num}}\times V_{\text{num}}\times L+L_{\text{num}}) \bmod 52$$


PS: Actually more accurate is:

$$\text{Card} = (([V_{\text{num}}\times V_{\text{num}}\times L+L_{\text{num}}]-1) \bmod 52) + 1$$

but I used the first expression just for clarity

$\endgroup$
  • $\begingroup$ how does mod 52 work? $\endgroup$ – moonbutt74 Sep 6 '15 at 15:18
  • 2
    $\begingroup$ @moonbutt74 It's a modular division - to wrap around the preceding value if bigger then 52. I.e. if the result is 57 modular division to 52 gives you 5 (if count from 1 of course). $\endgroup$ – kamenf Sep 6 '15 at 15:27
  • 1
    $\begingroup$ @moonbutt74 It is the same way you add 5 hours to 10 o'clock - wrap it circularly and it is 3. The two expressions (with and without +1 and -1) differ in that how modulus is calculated - in computers counting starts from 0, so 52 cards are actually indexed 0,1,..51 and (52 mod 52) is actually 1; so if you use computers for this expression and start numbering letters from 1 you have to first subtract 1 before modulus calculation and then add 1 to have indexed cards from 1 to 52. $\endgroup$ – kamenf Sep 6 '15 at 17:44
  • 1
    $\begingroup$ @moonbutt74 And for the last question: in the way you calculate it you do not need to add 1. So 7 is the result. And yes, you have to count total number of occurrences of any vowel, for ex. in "simple phrase" the number of vowels is 4. $\endgroup$ – kamenf Sep 6 '15 at 17:58
  • 1
    $\begingroup$ The easiest way to explain modulus is that it's the "remainder" when you do very simple and basic division. When you say 7 divided by three is 2 remainder 1, that means 7 modulus 3 is 1. $\endgroup$ – Kingrames Sep 9 '15 at 12:54
5
$\begingroup$

The Lua code snippets in the question simply import a string consisting of a long sequence of escapes, and then run the imported object. Treating the string as a binary file, we get something like:

0000000: 1b4c 7561 5100 0104 0404 0800 0000 0000 .LuaQ...........
0000010: 0000 0000 0000 0000 0000 0213 0601 0000 ................
...

The first 12 bytes are the header to compiled Lua bytecode. That means that our first step is to:

Step 1: Write a Lua Decompiler

I wasn't really satisfied with the existing tools for manipulating Lua bytecode, plus I love to learn new languages, so I wrote my own parser in Mathematica.

This took quite a while, since the documentation is not that great: I had only the source code and this document to guide me. However, it was made easier by the fact that Lua's VM operates on a very high level, has very few instructions, and uses a stack-based register scheme.

Although my code handles both version 5.1 and 5.2, the way closures are handled in 5.1 is slightly easier to understand, so that's the version that I chose to analyze.

Step 2: Analyze the Bytecode

Once the parser was written, this part actually went pretty fast. ChipperNickel hinted that large sections of the code had no effect on the output. Even before parsing the bytecode you can tell that math.random is used (global function names are stored as strings in the constants table) even though we know that the output is deterministic.

We start looking at the end of the instructions section of the top-level function:

249 GETGLOBAL 11 50                R11 = global("print")
250 MOVE      12 9 0               R12 = R9
251 CALL      11 2 1               R11(R12)
252 MOVE      11 4 0               R11 = R4
253 GETGLOBAL 12 51                R12 = global("io")
254 GETTABLE  12 12 308            R12 = R12["write"]
255 GETTABLE  13 10 9              R13 = R10[R9]
256 LOADK     14 53                R14 = " ("
257 MOVE      15 9 0               R15 = R9
258 LOADK     16 54                R16 = ")"
259 CONCAT    13 13 16             R13 = R13 .. R14 .. R15 .. R16
260 CALL      11 3 1               R11(R12, R13)
261 RETURN    0 1 0                return 

Eliminating the intermediate assignments, we end up with:

print(R9)
R4(io.write, R10[R9] .. " (" .. R9 .. ")")
return 

This matches the output format of the program perfectly (right down to the missing \n):

1
Ace of Spades (1)

Assuming that the function in R4 actually calls io.write and that this is not a red herring, we now know that R9 is the number of the card and R10 is a table containing a list of card names as strings. We just need to find out how R9 is calculated and what order the cards are placed in R10.


However, I'll first take a quick detour to inspect the function in R4, just to make sure we have everything right. R4 is last set here:

61  CLOSURE   4 3                  R4 = closure(KPROTO3, R4, ...)

Thus we're looking for the third function prototype. The header of the third function lists two input parameters (matching what we've seen) and no upvalues (which is good because it won't depend on other registers manipulated during program execution). It also occupied lines 51-58 of the source code (starting and ending line numbers are not stripped with the rest of the debugging information) so we know it's relatively short. Here is the entire instruction listing for the function:

0  NEWTABLE  2 0 0                R2 = {}
1  LOADK     3 0                  R3 = 1.
2  GETGLOBAL 4 1                  R4 = global("math")
3  GETTABLE  4 4 258              R4 = R4["random"]
4  LOADK     5 3                  R5 = 20.
5  LOADK     6 4                  R6 = 50.
6  CALL      4 3 2                R4 = R4(R5, R6)
7  LOADK     5 0                  R5 = 1.
8  FORPREP   3 8                  R3 -= R5; PC += 8
9  LEN       7 2 0                R7 = len(R2)
10 ADD       7 7 256              R7 = R7 + 1.
11 GETGLOBAL 8 1                  R8 = global("math")
12 GETTABLE  8 8 258              R8 = R8["random"]
13 LOADK     9 5                  R9 = 10.
14 LOADK     10 3                 R10 = 20.
15 CALL      8 3 2                R8 = R8(R9, R10)
16 SETTABLE  2 7 8                R2[R7] = R8
17 FORLOOP   3 9                  R3 += R5; if(R3 <?= R4) { R6 = R3; PC += -9 }
18 LEN       3 2 0                R3 = len(R2)
19 ADD       3 3 256              R3 = R3 + 1.
20 SETTABLE  2 3 0                R2[R3] = R0
21 LEN       3 2 0                R3 = len(R2)
22 GETTABLE  3 2 3                R3 = R2[R3]
23 MOVE      4 1 0                R4 = R1
24 TAILCALL  3 2 0                return R3(R4)
25 RETURN    3 0 0                return R3, ...
26 RETURN    0 1 0                return 

Note that a function call treats the stack as empty except for the input arguments, so we start off with R0 as io.write and R1 as the output string.

First I'll note that R2 contains a list and is not reassigned throughout the function.

Lines 18-20 append io.write to the end of the list. Lines 21 and 22 then extract that element back out of the list. Finally, line 24 calls io.write(R1), which is what we suspected the output was in the first place. This means we can disregard the rest of the function.


Now we are looking for where R10 is populated and R9 is calculated. Going back a little in the top-level function we see:

120 NEWTABLE  10 0 0               R10 = {}
121 GETGLOBAL 11 26                R11 = global("table")
122 GETTABLE  11 11 283            R11 = R11["insert"]
123 MOVE      12 10 0              R12 = R10
124 LOADK     13 28                R13 = "Ace of Spades"
125 CALL      11 3 1               R11(R12, R13)
126 LOADK     11 25                R11 = 2.
127 LOADK     12 29                R12 = 10.
128 LOADK     13 14                R13 = 1.
129 FORPREP   11 7                 R11 -= R13; PC += 7
130 GETGLOBAL 15 26                R15 = global("table")
131 GETTABLE  15 15 283            R15 = R15["insert"]
132 MOVE      16 10 0              R16 = R10
133 MOVE      17 14 0              R17 = R14
134 LOADK     18 30                R18 = " of Spades"
135 CONCAT    17 17 18             R17 = R17 <> R18
136 CALL      15 3 1               R15(R16, R17)
137 FORLOOP   11 8                 R11 += R13; if(R11 <?= R12) { R14 = R11; PC += -8 }
138 GETGLOBAL 11 26                R11 = global("table")
139 GETTABLE  11 11 283            R11 = R11["insert"]
140 MOVE      12 10 0              R12 = R10
141 LOADK     13 31                R13 = "Jack of Spades"
142 CALL      11 3 1               R11(R12, R13)
143 GETGLOBAL 11 26                R11 = global("table")
144 GETTABLE  11 11 283            R11 = R11["insert"]
145 MOVE      12 10 0              R12 = R10
146 LOADK     13 32                R13 = "Queen of Spades"
147 CALL      11 3 1               R11(R12, R13)
148 GETGLOBAL 11 26                R11 = global("table")
149 GETTABLE  11 11 283            R11 = R11["insert"]
150 MOVE      12 10 0              R12 = R10
151 LOADK     13 33                R13 = "King of Spades"
152 CALL      11 3 1               R11(R12, R13)
153 GETGLOBAL 11 26                R11 = global("table")
154 GETTABLE  11 11 283            R11 = R11["insert"]
155 MOVE      12 10 0              R12 = R10
156 LOADK     13 34                R13 = "Ace of Diamonds"
157 CALL      11 3 1               R11(R12, R13)

Without doing a detailed analysis of this code I can see that we're creating an empty list in R10, and then appending (with table.insert) cards names in ascending order, with the ace first. The suit order is Spades, Diamonds, Clubs, Hearts. (Personally I would have made a doubly-nested loop, indexing into a list of suit names in the outer loop. This has the advantage of tightening up the source code while further obfuscating the bytecode.)


Looking back at the instruction just before the previous segment, we see an assignment to R9:

111 GETGLOBAL 9 15                 R9 = global("string")
112 GETTABLE  9 9 280              R9 = R9["len"]
113 GETGLOBAL 10 12                R10 = global("input")
114 CALL      9 2 2                R9 = R9(R10)
115 ADD       8 8 9                R8 = R8 + R9
116 MOVE      9 4 0                R9 = R4
117 MOVE      10 3 0               R10 = R3
118 MOVE      11 8 0               R11 = R8
119 CALL      9 3 2                R9 = R9(R10, R11)

We're calling R9 as a function, but we can see from instruction 116 that it's just our old friend KPROTO3 as R4 again. Thus we can simplify the listing to just:

R9 = R3(R8 + string.len(input))

R3 was last set in instruction 60:

60  CLOSURE   3 2                  R3 = closure(KPROTO2, R3, ...)

Thus we must dive into the functions again.


The header for function 2 states that it takes one argument and has no upvalues. However, it occupies a whole 17 lines of source code. Here are the instructions (remember the argument is in R0):

0  ADD       0 0 256              R0 = R0 + 25.
1  ADD       0 0 257              R0 = R0 + 1.
2  SUB       0 0 258              R0 = R0 - 26.
3  GETGLOBAL 1 3                  R1 = global("math")
4  GETTABLE  1 1 260              R1 = R1["floor"]
5  MOVE      2 0 0                R2 = R0
6  CALL      1 2 2                R1 = R1(R2)
7  MOVE      0 1 0                R0 = R1
8  NEWTABLE  1 0 0                R1 = {}
9  LOADK     2 1                  R2 = 1.
10 GETGLOBAL 3 3                  R3 = global("math")
11 GETTABLE  3 3 261              R3 = R3["random"]
12 LOADK     4 6                  R4 = 250.
13 LOADK     5 7                  R5 = 999.
14 CALL      3 3 2                R3 = R3(R4, R5)
15 LOADK     4 1                  R4 = 1.
16 FORPREP   2 6                  R2 -= R4; PC += 6
17 GETGLOBAL 6 3                  R6 = global("math")
18 GETTABLE  6 6 261              R6 = R6["random"]
19 LOADK     7 8                  R7 = 0.
20 LOADK     8 7                  R8 = 999.
21 CALL      6 3 2                R6 = R6(R7, R8)
22 SETTABLE  1 5 6                R1[R5] = R6
23 FORLOOP   2 7                  R2 += R4; if(R2 <?= R3) { R5 = R2; PC += -7 }
24 LEN       2 1 0                R2 = len(R1)
25 ADD       2 2 257              R2 = R2 + 1.
26 SETTABLE  1 2 0                R1[R2] = R0
27 LOADNIL   0 0 0                R0 = nil
28 LEN       2 1 0                R2 = len(R1)
29 GETTABLE  2 1 2                R2 = R1[R2]
30 MOD       2 2 265              R2 = R2 % 52.
31 EQ        0 2 264              if(R2 == 0.) PC++
32 JMP       0 3                  PC += 3
33 LOADK     2 9                  R2 = 52.
34 RETURN    2 2 0                return R2
35 JMP       0 4                  PC += 4
36 LEN       2 1 0                R2 = len(R1)
37 GETTABLE  2 1 2                R2 = R1[R2]
38 MOD       2 2 265              R2 = R2 % 52.
39 RETURN    2 2 0                return R2
40 RETURN    0 1 0                return 

It's blatantly obvious from the first three instructions that Lua does not use an optimizing compiler. We'll treat those as a noop.

Now we go backwards, just as before. Note that there are two return statements amid a bunch of jumps. Parsing that code (instructions 28-40) nets us:

R2 = R1[len(R1)] % 52
if R2 == 0 then
    return 52
else
    return R1[len(R1)] % 52
end

This just returns the last element of the list R1 modulo 52, using the smallest positive number as the representative of each equivalence class.

However, note that in instructions 24-26, R0 is appended to R1. This means that we can simplify the code even further:

if R0 % 52 == 0 then
    return 52
else
    return R0 % 52
end

Since the result of this function is used to index into a list of 52 elements (the list of card names), the effect of this function is to treat the list as cyclic.


Returning to the top-level function we just need to figure out what R8 is set to. Tracing the code back I notice that at instruction 61, the entire stack consists only of function handles (excepting R0 which is not subsequently used):

1   CLOSURE   1 0                  R1 = closure(KPROTO0, R1, ...)
...
3   CLOSURE   2 1                  R2 = closure(KPROTO1, R2, ...)
...
60  CLOSURE   3 2                  R3 = closure(KPROTO2, R3, ...)
61  CLOSURE   4 3                  R4 = closure(KPROTO3, R4, ...)

Thus we can go forward from this point. I'll analyze the following instructions in sections:

62  GETGLOBAL 5 13                 R5 = global("arg")
63  GETTABLE  5 5 270              R5 = R5[1.]
64  SETGLOBAL 5 12                 global("input") = R5

Here we just set input = arg[1].

65  GETGLOBAL 5 15                 R5 = global("string")
66  GETTABLE  5 5 272              R5 = R5["lower"]
67  GETGLOBAL 6 12                 R6 = global("input")
68  CALL      5 2 2                R5 = R5(R6)
69  SETGLOBAL 5 12                 global("input") = R5

Here we set input = string.lower(input).

70  GETGLOBAL 5 12                 R5 = global("input")
71  SELF      5 5 273              R6 = R5; R5 = R5["gsub"]
72  LOADK     7 18                 R7 = "%L"
73  LOADK     8 19                 R8 = ""
74  CALL      5 4 2                R5 = R5(R6, R7, R8)
75  SETGLOBAL 5 12                 global("input") = R5

Equivalent to input = input.gsub(input, "%L", ""). This replaces all non-lowercase letters with the empty string.

76  LOADK     5 20                 R5 = 0.

Initialize R5 to zero. (It will be a counter later on in the code.)

77  GETGLOBAL 6 15                 R6 = global("string")
78  GETTABLE  6 6 277              R6 = R6["sub"]
79  GETGLOBAL 7 12                 R7 = global("input")
80  LOADK     8 14                 R8 = 1.
81  LOADK     9 14                 R9 = 1.
82  CALL      6 4 2                R6 = R6(R7, R8, R9)

Here we do R6 = string.sub(input, 1, 1) to store the first letter of the string in R6.

83  GETGLOBAL 7 15                 R7 = global("string")
84  GETTABLE  7 7 278              R7 = R7["byte"]
85  MOVE      8 6 0                R8 = R6
86  CALL      7 2 2                R7 = R7(R8)
87  SUB       7 7 279              R7 = R7 - 96.

Now we calculate R7 = string.byte(R6) - 96. This gets the number of the first letter of the string (starting at 1 for a).

88  LOADK     8 20                 R8 = 0.
89  LOADK     9 14                 R9 = 1.
90  GETGLOBAL 10 15                R10 = global("string")
91  GETTABLE  10 10 280            R10 = R10["len"]
92  GETGLOBAL 11 12                R11 = global("input")
93  CALL      10 2 2               R10 = R10(R11)
94  LOADK     11 14                R11 = 1.

Here we set up for a for-loop. These lines are equivalent to:

R8  = 0
R9  = 1
R10 = string.len(input)
R11 = 1

Now on to the for-loop itself:

95  FORPREP   9 12                 R9 -= R11; PC += 12
96  MOVE      13 4 0               R13 = R4
97  MOVE      14 2 0               R14 = R2
98  GETGLOBAL 15 15                R15 = global("string")
99  GETTABLE  15 15 277            R15 = R15["sub"]
100 GETGLOBAL 16 12                R16 = global("input")
101 MOVE      17 12 0              R17 = R12
102 MOVE      18 12 0              R18 = R12
103 CALL      15 4 0               R15, ... = R15(R16, R17, R18)
104 CALL      13 0 2               R13 = R13(R14, ...)
105 TEST      13 0 0               if(R13) PC++
106 JMP       0 1                  PC += 1
107 ADD       5 5 270              R5 = R5 + 1.
108 FORLOOP   9 13                 R9 += R11; if(R9 <?= R10) { R12 = R9; PC += -13 }

Note that the for-loop keeps four state registers: the starting index, ending index, and step are stored in R9-R11, and the loop variable (I'll use i) is stored in R12. We can simplify to:

for i = 1, string.len(input), 1 do
    R13 = R4(R2, string.sub(input, i, i))
    if R13 do
        R5++
    end
end

Remembering what KPROTO3 (R4) does, we can simplify further to:

for i = 1, string.len(input), 1 do
    if R2(string.sub(input, i, i)) do
        R5++
    end
end

Thus we call KPROTO1 (R2) on all of the letters in the string and increment R5 if the result is truthy.

Finally a calculation:

109 POW       5 5 281              R5 = R5 ** 2.
110 MUL       8 5 7                R8 = R5 * R7

With this, we have almost everything we need. The final card number is, mod 52, the number of truthy letters in the string, squared, times the value of the first letter, plus the number of letters in the string.


The only step left is to look at function 1. Unfortunately both functions 0 and 1 have a closure on R0, a list. Function 0 is very simple, just appending its argument minus ten to the list.

Function 1 is also rather straightforward:

0  LOADBOOL  1 0 0                R1 = False
1  LOADK     2 0                  R2 = 1.
2  GETUPVAL  3 0 0                R3 = U0
3  LEN       3 3 0                R3 = length(R3)
4  LOADK     4 0                  R4 = 1.
5  FORPREP   2 9                  R2 -= R4; PC += 9
6  GETGLOBAL 6 1                  R6 = global("string")
7  GETTABLE  6 6 258              R6 = R6["byte"]
8  MOVE      7 0 0                R7 = R0
9  CALL      6 2 2                R6 = R6(R7)
10 GETUPVAL  7 0 0                R7 = U0
11 GETTABLE  7 7 5                R7 = R7[R5]
12 EQ        0 6 7                if(R6 == R7) PC++
13 JMP       0 1                  PC += 1
14 LOADBOOL  1 1 0                R1 = True
15 FORLOOP   2 10                 R2 += R4; if(R2 <?= R3) { R5 = R2; PC += -10 }
16 RETURN    1 2 0                return R1
17 RETURN    0 1 0                return 

It simply checks if the character code of the first character of its argument is present in R0 (referred to here as U0, the first upvalue).


Now we need to understand what values R0 is initialized with. Instructions 5 through 59 are all sequences like:

5 MOVE      3 1 0                R3 = R1
6 LOADK     4 0                  R4 = 107.
7 CALL      3 2 1                R3(R4)

This sequence appends 107 (minus 10) to the list R0. In addition to a bunch of junk values (junk because they're larger than the max value of a byte), the following important values are appended:

107 - 10 =  97 = 'a'
111 - 10 = 101 = 'e'
115 - 10 = 105 = 'i'
121 - 10 = 111 = 'o'
127 - 10 = 117 = 'u'

Thus, KPROTO2 considers string truthy if they start with vowels.

Step 3: Put It All Together

Although no question was explicitly stated, the implicit question is what procedure does Jason use to map phrases to cards? My answer is:

Jason counts the number of vowels in the phrase, then squares it. Then he multiplies that number by the position in the alphabet (a is 1, z is 26) of the phrase's first letter. Then he adds the number of letters in the phrase.
Then, starting with the deck in order, Jason moves the top card to the bottom a number of times equal to the number he calculated. Then he chooses the bottom card.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.