11
\$\begingroup\$

Background

Conway immobilizer problem is a puzzle that reads like the following:

Three positions, "left," "middle," and "right," are marked on a table. Three cards, an ace, a king, and a queen, lie face up in some or all three of the positions. If more than one card occupies a given position then only the top card is visible, and a hidden card is completely hidden; that is, if only two cards are visible then you don't know which of them conceals the missing card.

Your goal is to have the cards stacked in the left position with the ace on top, the king in the middle, and the queen on the bottom. To do this you can move one card at a time from the top of one stack to the top of another stack (which may be empty).

The problem is that you have no short-term memory, so you must design an algorithm that tells you what to do based only on what is currently visible. You can't recall what you've done in the past, and you can't count moves. An observer will tell you when you've succeeded. Can you devise a policy that will meet the goal in a bounded number of steps, regardless of the initial position?

The puzzle has got its name because it's said to have immobilized one solver in his chair for six hours.

The link above gives one possible answer (marked as spoiler for those who want to solve it by themselves):

  • If there’s an empty slot, move a card to the right (around the corner, if necessary) to fill it. Exception: If the position is king-blank-ace or king-ace-blank, place the ace on the king.
  • If all three cards are visible, move the card to the right of the queen one space to the right (again, around the corner if necessary). Exception: If the queen is on the left, place the king on the queen.

All solutions to the Immobilizer Problem (pdf) uses graph theory to show that there are 14287056546 distinct strategies that solve the problem.

Task

Given a strategy for Conway Immobilizer, determine if the strategy actually solves it, i.e. given any initial configuration, repeating the strategy will eventually place all cards into the winning state.

A strategy (the input) can be in any format that represents a set of pairs current visible state -> next move for every possible current visible state. A visible state represents what is visible on each of three slots (it can be one of A/K/Q or empty). A move consists of two values A, B which represents a move from slot A to slot B.

The input format can be e.g. a list of pairs, a hash table, or even a function, but it should not involve any external information, e.g. you cannot encode a "move" as a function that modifies the full game state (entire stacks of cards). You can use any four distinct values for A/K/Q/empty (the visible state of each slot) and three distinct values for left/middle/right (to represent a move from a slot to another).

Standard rules apply. The shortest code in bytes wins.

Test cases

Input: the solution above
Output: True

Input: the solution above, but the exception on 'K.A' is removed
       (at 'K.A', move K to the right)
Output: False ('QKA' -> 'K.A' -> 'QKA')

Input: if only one card is visible, move it to the right
       if Q and K are visible, move K on the top of Q
       if K and A are visible, move A on the top of K
       otherwise, move A to the empty slot
Output: False ('..A' where Q, K, A are stacked -> 'A.K' -> '..A')
\$\endgroup\$
4
  • \$\begingroup\$ Just to be clear, can I encode a move as a function that takes a stack of card and only move one of the top cards, without looking at the bottom cards? No external information is involved. \$\endgroup\$ May 8 '20 at 1:21
  • \$\begingroup\$ @SurculoseSputum It is not allowed to take a stack of cards, regardless of whether bottom cards are accessed or not. \$\endgroup\$
    – Bubbler
    May 8 '20 at 1:45
  • 1
    \$\begingroup\$ Is a bad solver at least guaranteed to do only legal moves? \$\endgroup\$
    – Arnauld
    May 8 '20 at 17:13
  • 1
    \$\begingroup\$ @Arnauld Yes, you can assume that. \$\endgroup\$
    – Bubbler
    May 8 '20 at 22:54
3
\$\begingroup\$

JavaScript (ES7),  229 224  213 bytes

Input: a function (the solver) expecting an array of 3 values among 'Q', 'K', 'A' or undefined for empty, and returning a move as a pair [from, to] (0-indexed)

Output: 0 or 1

f=(F,n=162)=>!n--||(g=s=>(s[k=s.join`/`]^=1)?/A,K,/.test(k)|g(s,[x,y]=F(s.map(a=>a[0])),s[y].unshift(s[x].shift())):0)([0,1,2].map(i=>s[n/3**i%3|0].push('QKAKQAAQKQAKKAQAKQ'[3*~~(n/27)+i]),s=[[],[],[]])&&s)&f(F,n)

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 120 114 bytes

≔E³³SθFφF⁼Σι³F⪪”{“±¿U+*~T”³«≔⪪λ¹λ≔E◧Iι³EΣμ⊟λλ≔⊟Φθ⬤λ⁼§μπ§∨ξ.⁰ζ≔Eλ⮌μη⊞§ηI§ζ⁴⊟§ηI§ζ³⊞υ⁺λEη⮌μ»≔⊟υθWΦυ¬№Eυ…μ³✂κ³≔⁻υιυ¬υ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for verified, nothing for failed. Explanation:

≔E³³Sθ

Read in the 33 instructions, comprising strings of 5 characters, the three visible cards and the source and destination of the move (0-indexed).

FφF⁼Σι³

Loop over all 3-digit numbers with a digit sum of 3.

F⪪”{“±¿U+*~T”³«

Loop over the permutations of AKQ by taking a compressed string of all six permutations and splitting it into substrings of length 3.

≔⪪λ¹λ≔

Split the AKQ into an array.

E◧Iι³EΣμ⊟λλ

Move the AKQ into one of three lists depending on the digits of the outer loop variable. For instance, if the variable is 111 then the resulting list is a list of lists of reverse of the array, while if it is 300 then the resulting list has the reverse of the array as its first element and two empty lists. This represents the real positions of the three cards.

≔⊟Φθ⬤λ⁼§μπ§∨ξ.⁰ζ

Calculate the visible cards and find the move for that set of cards.

≔Eλ⮌μη

Make a reversed copy of the card positions.

⊞§ηI§ζ⁴⊟§ηI§ζ³

Perform the move on the copy. The reversal, in addition to resulting in a deep copy, also allows the moved card to be popped and pushed.

⊞υ⁺λEη⮌μ

Unreverse the move result and save the cards and the move result to an empty list.

»≔⊟υθ

Remove the winning position from the list of all card positions.

WΦυ¬№Eυ…μ³✂κ³

Repeat while there are positions whose move reaches a winnable position.

≔⁻υιυ

Remove all of the now winnable positions.

¬υ

Are there no unwinnable positions left?

\$\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.