Exploring MAGIC
Vector 9:2, page 16
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 16
Introduction¶
Thanks to Bill McLean for suggesting an interesting game in July’s Education Vector, Vector Vol.9 No.1. In the game of MAGIC a randomly generated matrix of 0s and 1s is displayed, and the player is asked to select from a standard set of matrices (also 0s or 1s). The selected matrix is used to complement the values in the original matrix. The aim is to end up with the target matrix, a matrix of 1s with a lone 0 in the middle.
Bill presented a program that lets the user play MAGIC, and he finished by inviting an APL algorithm that solves MAGIC puzzles.
I wanted to use direct definition to express my ideas, and the problem also suggested the use of nested arrays, so I used APL*PLUS II with a direct definition handler I developed a few years ago.
I had great fun programming my thoughts, the results of which I submit for your consideration. I don’t pretend that this flow-of-consciousness coding style has resulted in either a definitive or a concise solution, but it does demonstrate that direct definition can be used to explore ideas very rapidly, without interruptions caused by the superfluous syntax of traditional function definition methods. A global index origin of zero (⎕IO←0) is used throughout.
Representing MAGIC Boxes and Keys¶
The nine boxes, which I have renumbered 0-8, are as follows:
1 1 0 1 1 1 0 1 1
1 1 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0
0 1 2
1 0 0 0 1 0 0 0 1
1 0 0 1 1 1 0 0 1
1 0 0 0 1 0 0 0 1
3 4 5
0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 1 1
1 1 0 1 1 1 0 1 1
6 7 8
A short MAGIC game can be summarised by the following sequence, which begins with a random initial box, and ends with the winning target box. The numbers between the boxes are the key numbers required to effect the transitions:
First we need to be able to enter the binary representation of each of the nine keys. The following functions do that:
boxes012: 3 3 3⍴'1'='110110000111000000011011000'
boxes345: 3 3 3⍴'1'='100100100010111010001001001'
boxes678: 3 3 3⍴'1'='000110110000000111000011011'
These are examples of niladic directly defined functions; they do not take any arguments, but return constant results. The nine boxes can be structured into a vector of nine matrices as follows:
boxes: ↑¨↓↓boxes012⍪boxes345⍪boxes678
boxes
1 1 0 1 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 1 1 1 0 1 1
Although we could deal with binary matrices directly, I have chosen to use a different representation, namely the decimal value of the nine-bit number that represents the matrix. (This is discussed further in Appendix A.) We will need two utilities for converting between the forms:
The omega symbol represents the function right argument. Now we can represent every state as an integer scalar from 0 through 511. Let’s convert the winning state matrix into a decimal value:
We can convert the integer values to binary matrices when we want to perform the complementing operation which is at the heart of this game:
stateComp: bd (db ⍺)≠(db ⍵)
123 stateComp 42
81
db¨123 42 81
0 0 1 0 0 0 0 0 1
1 1 1 1 0 1 0 1 0
0 1 1 0 1 0 0 0 1
A function that returns the decimal value of the box represented by each key number will be useful:
Generating the State Table¶
Now we can generate the state table for this system. It has one row per input state, and one column per selected key. Each cell in the result contains the target state reached by applying each key to the corresponding input state. The state table is easily constructed by applying the stateComp function between all combinations of input state and key number:
You may not have noticed the delay just then, but the above expression took 12 seconds to execute on a 33Mhz 486. To speed things up a bit, we can write a cover function:
This uses the three segment form of direct definition. If the middle segment, the condition segment, evaluates to 1 then the right segment is executed. On the other hand, if the condition segment evaluates to 0 then the left segment is executed.
The ⍝/G= is a little trick that tells the direct definition handler to leave the named variable as global (the handler normally localises all variables to the left of an assignment arrow).
Although StateTa is technically a global variable, it is not referred to elsewhere. It is actually being used to emulate "state memory", a kind of name scope which is not available in APL, where the function remembers the value of the variable from the previous time it was called. From now on, executions of this function will result in an immediate response.
Now we can search the state table for any state we are interested in, returning the input states (row numbers) of the state table that lead to the argument state:
statesFrom: where stateTable∨.∊⍵
where: ⍵/⍳⍴⍵ : 2=⎕nc'⍺' : ⍵/⍺
statesFrom win
47 95 203 311 341 422 473 488 500
The dyadic form of the where utility will be used later. The alpha in the definition of where represents the function’s left argument, if supplied.
Generating the State Transition Vector¶
Our algorithm will be to use statesFrom to trace backwards from the winning state, through each prior state, until all 512 states have been accounted for. On the way we can build a vector of state vectors, which will be as long as the longest minimal winning sequence.
So we must now build on statesFrom as follows:
stepBack: (statesFrom first ⍵) without flatten ⍵
without: ⍺~⍵
first: ⊃⍵
flatten: ⊃,/⍵ : 0∊⍴⍵ : ⍳0
stepBack win
47 95 203 311 341 422 473 488 500
Notice that stepBack assumes that its argument is a vector of vectors, the growing vector of state vectors that will be our result. The without utility is used to ensure that any states we have already visited are not duplicated in the result, and so avoids a potentially infinite loop in the recursive function that we must now grit our teeth and write. Here it is:
When stepBack has visited every state, it returns an empty result, and this is the terminating condition for the traceBack function. Until this condition is met, the function will continue to append enclosed vectors of states to the left end of the result. Let us "burn in" the expression that computes the complete set of state transitions, from the winning state to the earliest state, into a function, and then with mounting excitement try it:
That took 9 seconds to run, so before looking at the result, we can use the same technique as before to hide the delay:
stateTrans: StateTr←stateTrans∆ : 2=⎕nc'StateTr' : StateTr ⍝/G=StateTr
⍴¨stateTrans
1 9 36 84 126 126 84 36 9 1
Each item of this 10 element vector contains states in a single "pool". To play a successful game of MAGIC it is necessary to select a key which moves us from a given state pool into the next one to the right, until we reach the target. We can see that the longest possible game involves nine transitions, from a single state in the starting pool, to a single state in the final pool. The distribution of states in the transition vector is symmetrical, which is to be expected from the commutative nature of the complementing (not-equals) function.
There is only room to view a fragment of the state transition vector here:
table: ((⍴⍵),1)⍴⍵
12 80↑⍕ table¨stateTrans
186 0 7 18 3 1 2 19 47 495
98 27 23 6 4 8 22 95
140 43 24 9 5 13 25 203
161 46 28 12 10 17 40 311
189 54 29 16 11 20 52 341
243 73 41 21 14 30 68 422
266 84 44 26 15 32 88 473
378 94 45 31 34 37 102 488
414 101 48 33 35 51 105 500
121 49 36 38 56 113
139 53 42 39 61 130
151 69 50 58 67 135
We can look at the bit patterns for the first and last states:
It is also possible to verify that every possible state is represented exactly once in the state transitions vector:
Generating the Key Transition Vector¶
The question remains, which keys do we need to press to effect the transition from one state pool to the next? This depends on the input and target states. We have to find the column number in the state table that contains the target state in a row corresponding to the input state:
This last expression produces an empty result because it is not possible to get from state 186 to state 1 in a single transition (see the state transition vector fragment above). Using states in contiguous state pools should give us a result:
The function will work for vector arguments, returning for each state in the left argument a vector of key numbers that will move us into the state pool on the right:
This tells us that state 0 needs key 5 to gives us one of the states in the right argument (we don’t know or care which), and that state 98 can get there via any of the keys 5, 7 or 8.
We can apply this function between a pair of state pools using APL’s reduction operator:
table ⊃keyBetweenStates/stateTrans[1 2]
0 1 2 3 5 6 7 8
0 1 3 4 5 6 7 8
0 1 2 3 4 5 7 8
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 8
0 1 2 3 4 6 7 8
1 2 3 4 5 6 7 8
0 2 3 4 5 6 7 8
0 1 2 4 5 6 7 8
Notice that there is only one "wrong" key you can select for each state in pool 1. Similarly we can find that there are only two wrong keys that can be pressed to move from pool 2 to pool 3:
To find the key numbers that can be used to effect all of the state transitions, we must apply the function between each contiguous pair of vectors in the state transition vector, as follows:
keyTrans∆: keyBetweenStates/9 2⍴(1 8 1/1 2 1)/stateTrans
keyTrans: KeyTr←keyTrans∆,⊂,⊂⍳0 : 2=⎕nc'KeyTr' : KeyTr ⍝/G=KeyTr
The expression in brackets duplicates each vector in stateTrans except for the first and last. The reshape turns the argument into a 2-column matrix, each row being a pair of contiguous state pools. These two expressions are here left ungeneralised for clarity. Users with APL systems that include a dyadic N-wise reduction operator could code this more directly. A final empty element is catenated onto the result in the keyTrans cover function in order to make it conform with the stateTrans vector.
We can pair each state transition vector with its corresponding key transition vector, and compactly display them using fmtTrans.
There is only room here for a few rows of the first 6 elements of the result:
↑12↑↓DEB⍕6↑fmtTrans
186 012345678 0 01235678 7 0123568 18 345678 3 12457 1 0134
98 01345678 27 0123567 23 024678 6 01347 4 1245
140 01234578 43 0134678 24 124578 9 34567 5 1678
161 01234567 46 1245678 28 012356 12 02467 10 0578
189 01234568 54 0123578 29 013478 16 02468 11 0246
243 01234678 73 0123678 41 124568 21 34568 14 3456
266 12345678 84 0134578 44 013468 26 01348 15 2378
378 02345678 94 0245678 45 012357 31 12458 34 2367
414 01245678 101 0134568 48 013467 33 02478 35 3458
121 0134567 49 012358 36 34578 38 0248
139 0123458 53 124567 42 01235 39 0567
151 0123457 69 024567 50 12456 58 0247
DEB is a utility function that deletes extraneous blank columns. It was copied from the APL*PLUS II distributed workspace ASMFNS. Notice that the number of "correct" keys we can select is always the same in any given state pool, and decreases by one in subsequent state pools. We can incidentally compute the total number of correct possible moves in each state pool by multiplying the number of states in the pool by the number of keys that can be pressed to move us into the next pool:
Solving MAGIC Puzzles¶
A function to generate the key numbers that must be selected for a given state is:
keysAfterState: keyTrans pickWith (stateTrans pickIndex ⍵)
pickWith: ⍵⊃⍺
pickIndex: (⍺ find ⍵),(⍺ pickWith ⍺ find ⍵)⍳⍵
find: where ⍵∊¨⍺
keysAfterState 186
0 1 2 3 4 5 6 7 8
keysAfterState 42
0 1 2 3 5
keysAfterState 500
8
We don’t really care what state we get into when we select a key, so long as it’s getting us into the next state pool, one step nearer to the target. So when we have a choice of key, let us arbitrarily agree to use the one with the lowest key:
The pickOne function could be modified to pick a different key, as required. Now we can trace forward through the state transitions, computing a key that will get us into the next state pool. It will be more useful to develop a function that returns two numbers, a key number and a target state, given an input state:
afterState: ⍵ afterKey keyAfterState ⍵
afterKey: ⍵,⍺ stateComp key ⍵
186 afterKey 0
0 266
afterState 186
0 266
By tracing forward through the transitions vectors we can generate the key number/state pair for every transition, starting from a given state:
traceFromState: traceForw ⊂afterState ⍵ : win=⍵ : ⍳0
traceForw: traceForw ⍵ appendr afterState final ⍵ : win=final ⍵ : ⍵
appendr: ⍺,⊂⍵
final: last flatten ⍵
last: ⊃⌽,⍵
traceFromState 186
0 266 1 202 2 18 3 310 4 396 5 453 6 499 7 500 8 495
We can write a formatting utility to make this result look a little more presentable:
fmtKeyState: table (first ⍵)(db key first ⍵)(db last ⍵)
fmtKeyStates:(⊂table('')(db ⍵)),fmtKeyState¨traceFromState ⍵
fmtKeyStates 32
0 5 6
0 0 0 1 1 0 0 0 1 0 0 0
1 0 0 1 1 0 0 0 1 1 1 0
0 0 0 0 0 0 0 0 1 1 1 0
1 1 0 1 1 1 1 1 1
0 1 0 0 1 1 1 0 1
0 0 0 0 0 1 1 1 1
The first row of the result contains key numbers, the second contains input states, and the third contains target states achieved by the corresponding key presses. The leftmost box in the second row is the initial state, 32 in this case. The final box in the last row is the winning target state.
A more compact form of display is required to show the longest winning line:
show: fmt¨¨(⊂⊂db ⍵),fmtKeyState¨traceFromState ⍵
show 186
010 0 1 2 3 4 5 6 7 8
111
010 110 111 011 100 010 001 000 000 000
110 000 011 100 111 001 110 000 011
000 000 000 100 010 001 110 111 011
100 011 000 100 110 111 111 111 111
001 001 010 110 001 000 110 110 101
010 010 010 110 100 101 011 100 111
Notice that you can get there by pressing each key once, in the order 0 to 8. We can write a function to apply a series of keys to an initial state:
applyKeys: ≠\db¨⍺,key¨⍵
186 applyKeys 0 1 2
0 1 0 1 0 0 0 1 1 0 0 0
1 1 1 0 0 1 0 0 1 0 1 0
0 1 0 0 1 0 0 1 0 0 1 0
and then use it to actually play MAGIC, and verify that the solution is correct for any starting state:
checkSolution: fmt¨⍵ applyKeys first¨traceFromState ⍵
checkSolution 186
010 100 011 000 100 110 111 111 111 111
111 001 001 010 110 001 000 110 110 101
010 010 010 010 110 100 101 011 100 111
Having finished this exercise, I am left with the feeling that there is probably a very simple way of knowing what key to press from any given state, but it eludes me at the moment…
Appendix A — Representation of State¶
It is possible to retain the 3 by 3 binary matrix representation of MAGIC states throughout the computations, rather than use the scalar decimal value, as described above. As far as the code is concerned this would make the conversion utilities bd and db unnecessary, and in turn the stateComp function as well. The stateTable function could then use a not-equals outer product directly, which would speed up the calculation of the state table.
However, the state table would now also dramatically increase in size. From an 18k integer matrix to a very nasty 165k matrix of enclosures. Furthermore, the current algorithm is made simpler because the state matrix is self-indexable, that is, the rows of the state matrix can be indexed by the decimal representation of any state within the state matrix.
Appendix B — Alphabetic Function Listing by Category¶
Generating the State Table¶
stateComp : bd (db ⍺)≠(db ⍵)
stateTable : StateTa←stateTable∆ : 2=⎕nc'StateTa' : StateTa
⍝/G=StateTa
stateTable∆: (⍳512)∘.stateComp key ⍳9
Generating the State Transition Vector¶
stateTrans : StateTr←stateTrans∆ : 2=⎕nc'StateTr' : StateTr
⍝/G=StateTr
stateTrans∆: traceBack ,⊂,win
stepBack : (statesFrom first ⍵) without flatten ⍵
traceBack : traceBack ⍵ appendl stepBack ⍵ : 0∊⍴stepBack ⍵ : ⍵
statesFrom : where stateTable∨.∊⍵
Generating the Key Transition Vector¶
keyBetweenStates: where¨↓stateTable[⍺;]∊⍵
keyTrans : KeyTr←keyTrans∆,⊂,⊂⍳0 : 2=⎕nc'KeyTr' : KeyTr
⍝/G=KeyTr
keyTrans∆ : keyBetweenStates/9 2⍴(1 8 1/1 2 1)/stateTrans
Solving MAGIC puzzles¶
afterKey : ⍵,⍺ stateComp key ⍵
afterState : ⍵ afterKey keyAfterState ⍵
applyKeys : ≠\db¨⍺,key¨⍵
keyAfterState : pickOne keysAfterState ⍵
keysAfterState: keyTrans pickWith (stateTrans pickIndex ⍵)
traceForw : traceForw ⍵ appendr afterState final ⍵ : win=final ⍵ : ⍵
traceFromState: traceForw ⊂afterState ⍵ : win=⍵ : ⍳0
General Utilities in this Application¶
appendl : (⊂⍵),⍺
appendr : ⍺,⊂⍵
final : last flatten ⍵
find : where ⍵∊¨⍺
first : ⊃⍵
flatten : ⊃,/⍵ : 0∊⍴⍵ : ⍳0
fmt : 1 0⍕⍵
last : ⊃⌽,⍵
pickIndex: (⍺ find ⍵),(⍺ pickWith ⍺ find ⍵)⍳⍵
pickWith : ⍵⊃⍺
sort : ⍵[⍋⍵]
table : ((⍴⍵),1)⍴⍵
where : ⍵/⍳⍴⍵ : 2=⎕nc'⍺' : ⍵/⍺
without : ⍺~⍵
Application Utilities¶
bd : 2⊥,⍵
boxes : ↑¨↓↓boxes012⍪boxes345⍪boxes678
boxes012 : 3 3 3⍴'1'='110110000111000000011011000'
boxes345 : 3 3 3⍴'1'='100100100010111010001001001'
boxes678 : 3 3 3⍴'1'='000110110000000111000011011'
db : 3 3⍴(9⍴2)⊤⍵
checkSolution: fmt¨⍵ applyKeys first¨traceFromState ⍵
fmtKeyState : table (first ⍵)(db key first ⍵)(db last ⍵)
fmtKeyStates : (⊂table('')(db ⍵)),fmtKeyState¨traceFromState ⍵
fmtTrans : stateTrans pair¨keyTrans
key : bd¨boxes[⍵]
pair : ⍺,fmt¨table ⍵
pickOne : ⊃⍵
show : fmt¨¨(⊂⊂db ⍵),fmtKeyState¨traceFromState ⍵
win : bd 3 3⍴'1'='111101111'