Liquid-sorting puzzles in APL

Table of Contents

The object of the liquid-sorting puzzle is to sort all the initially-mixed colored liquids into vials full of uniform color; the image below shows an example of the initial mixed state. You may pour any vial onto any other; this transfers the top color layer from the one vial to the other. The only conditions are: (a) the receiving vial must have room, (b) no merging unalike colors—the receiving vial be empty or topped with the same color as you're pouring.

fluids-vials-black.png

Figure 1: An example liquid-sorting puzzle

sort_moves.png

Figure 2: A sequence of liquid-pouring moves. Figure by https://arxiv.org/pdf/2202.09495

You can set up some tricky puzzles this way (in fact, it's NP-complete), and in fact it's possible to wedge the game into an unwinnable state.

A perfect storm emerged: I did not like the idea of unwinnable states and I had always thought about learning the APL programming language. So I figured this would be a perfectly unhinged opportunity to address both issues by writing an APL program to solve all liquid sorting puzzles. Here is the source code (complete explanation follows; see next section): 

top←{⍵↑⍨+/∧\⍵=⊃⍵}
vacancy←{t←top' '~⍨⍺ ⋄ (2>≢∪t,top' '~⍨⍵)×(+/' '=⍵)⌊≢t}
pour←{after←(-⍺ vacancy ⍵)⌽(⌽⍺),⍵ ⋄ (⌽(≢⍺)↑after)((≢⍺)↓after)}
{{c←{+/' '≠⍵}¨⍵ ⋄ (((↑⍸¨↓2>⌿c),'→',↑⍸¨↓2<⌿c)⍪'   '),⍵}↑⌽⍬{0=≢⍵:⍬ ⋄ p←⊃⍵ ⋄ vials←⊃p ⋄ ∧/{2>≢∪⍵}¨vials:p ⋄ (⊂vials[⍋vials])∊⍺:⍺∇1↓⍵ ⋄ intos←∘.pour⍨vials ⋄ afters←{⍵[⍋+/{+/2≠/⍵}¨⍵;]}∪↑,{v←vials ⋄ =/⍵:v ⋄ v[⍵]←⊃⍵⌷intos ⋄ v}¨⍳⍴intos ⋄ (⍺,⊂vials[⍋vials])∇(1↓⍵),{(⊂⍵),p}¨↓afters},⊂⊂⍵}'ABAB' 'BABA' '    '

What a marvelous pile of hieroglyphs! And yet it's a complete search algorithm. You hand this function the starting state of your puzzle, such as ('ABAB' 'BABA', ' ') (which represents a game of three vials stacked with colors 'A' and 'B': ABAB, BABA, and empty.) Like magic, it spits out a nicely-formatted sequence of minimal steps to solve the puzzle: 

┌→───────────────────────────┐
↓       ┌→───┐ ┌→───┐ ┌→───┐ │
│ 1 → 3 │ABAB│ │BABA│ │    │ │
│       └────┘ └────┘ └────┘ │
│       ┌→───┐ ┌→───┐ ┌→───┐ │
│ 2 → 1 │BAB │ │BABA│ │A   │ │
│       └────┘ └────┘ └────┘ │
│       ┌→───┐ ┌→───┐ ┌→───┐ │
│ 2 → 3 │BBAB│ │ABA │ │A   │ │
│   -   └────┘ └────┘ └────┘ │
│       ┌→───┐ ┌→───┐ ┌→───┐ │
│ 1 → 2 │BBAB│ │BA  │ │AA  │ │
│       └────┘ └────┘ └────┘ │
│       ┌→───┐ ┌→───┐ ┌→───┐ │
│ 1 → 3 │AB  │ │BBBA│ │AA  │ │
│       └────┘ └────┘ └────┘ │
│       ┌→───┐ ┌→───┐ ┌→───┐ │
│ 2 → 1 │B   │ │BBBA│ │AAA │ │
│       └────┘ └────┘ └────┘ │
│       ┌→───┐ ┌→───┐ ┌→───┐ │
│ 2 → 3 │BBBB│ │A   │ │AAA │ │
│       └────┘ └────┘ └────┘ │
│       ┌→───┐ ┌→───┐ ┌→───┐ │
│       │BBBB│ │    │ │AAAA│ │
│ - - - └────┘ └────┘ └────┘ │
└∊───────────────────────────┘

I find I'm charmed by APL. At first, it seems perversely cryptic. Then you discover that each symbol represents a common array manipulation such as iteration, slicing, mapping, filtering. Each row of code is a compact way to describe a sequence of array manipulations, readable at a glance once you have the descriptive vocabulary.

The shift in density reminds me a little of the contrast between spanish, english, and chinese:

Each has tradeoffs—pronunciation, density, ambiguity, and so forth. In my case, APL represents a sudden density upgrade, and it's interesting to see what you can do with it.

1. How the algorithm works

Conceptually, it's a basic breadth-first search for the shortest sequence of moves to a solved state.

  • Initialize the queue with the starting state as a singleton path. Initialize the visited set as empty. Then start the following loop:
  • Pop the first path (or return unsolvable if the queue is empty)
  • Check whether the path terminates at a winning state—every vial has at most one color in it. If so, return it and print it prettily.
  • Check whether this state has been visited before: sort the vials into canonical order and compare against the visited list. If it has, skip it and continue the loop. If it hasn't, add it to the visited list.
  • Create a matrix (i,j) of pouring vial i into vial j, skipping moves that are illegal. This is the matrix of possible child states.
  • Convert the matrix of possible child states into a list of extended paths and append those to the queue.
  • Continue the loop.

At a language level, APL opens up new ways of thinking. Here's an example of an array-manipulation way to think about the pouring subroutine:

To pour one vial onto another:

  1. Write the vials as lists like [AABC ] [ADE ], with liquid contents listed from top to bottom and padding space added at the end.
  2. Reverse the first vial and concatenate: [ CBAA|ADE ].
  3. Having pre-computed how many units of liquid can flow between the vials, cyclically rotate the concatenated list by this amount. In our case, we rotate by two, pouring the two units of A from the first vial onto the second: [ CB|AAADE]. Note that this shuffles two units of A onto the second vial, and two compensating units of empty space onto the first vial.
  4. Now if we split them apart and reverse, we get their final states: [BC ] [AAADE].

What a neat way to do that! And it's short: pour←{after←(-(⍺ vacancy ⍵))⊖((⌽⍺),⍵)⋄((⌽(≢⍺)↑after)((≢⍺)↓after))}

2. Line-by-line annotated code

  1. top←{⍵↑⍨+/∧\⍵=⊃⍵} : helper top. given a vial, return the top block of monochromatic color. So AAABC => AAA. For an empty vial, returns a list of spaces.
  2. vacancy←{t←top' '~⍨⍺ ⋄ (2>≢∪t,top' '~⍨⍵)×(+/' '=⍵)⌊≢t} : helper vacancy, binary operator returns the number of liquid units that could be transferred from vial α onto vial ⍵. It's the minimum of: free slots in ⍵, monochromatic liquid on top of α, and the amount of liquid in α (to exclude empty α).
  3. pour←{after←(-⍺ vacancy ⍵)⌽(⌽⍺),⍵ ⋄ (⌽(≢⍺)↑after)((≢⍺)↓after)} : helper pour, binary operator pours vial ⍺ onto vial ⍵, returning the resulting pair. Performs a legal-move check, then the cyclic rotation trick. If the move is illegal, the zero rotation automatically returns the vials unchanged.
  4. the actual search and pretty-print algorithm:
{{c←{+/' '≠⍵}¨⍵ ⋄ (((↑⍸¨↓2>⌿c),'→',↑⍸¨↓2<⌿c)⍪'   '),⍵}   ⍝ the pretty-printer for solution paths
↑⌽                                                       ⍝ ... applied to the solution path in the next line
⍬{                                                       ⍝ search is a binary operator. left arg is the visited set (initially empty ⍬), right arg is initial game state
    0=≢⍵:⍬ ⋄                                             ⍝ if empty queue, return empty path (failure)
    p←⊃⍵ ⋄ vials←⊃p ⋄                                    ⍝ pop the queue; call the path `p` and its final state `vials`.
    ∧/{2>≢∪⍵}¨vials:p ⋄                                  ⍝ goal check: if each vial is monochromatic or empty, we win. return the path p.
    (⊂vials[⍋vials])∊⍺:⍺∇1↓⍵ ⋄                           ⍝ visited check: canonicalize the path. if already seen, recur on the rest of the queue. (search is an anonymous recursive function) 
    intos←∘.pour⍨vials ⋄                                 ⍝ beautifully concise: compute all possible pouring moves as an outer product

    afters←{⍵[⍋+/{+/2≠/⍵}¨⍵;]}∪↑,{v←vials ⋄ =/⍵:v ⋄ v[⍵]←⊃⍵⌷intos ⋄ v}¨⍳⍴intos ⋄
                                                         ⍝ convert the moves into game states. illegal moves are no-ops, to be pruned by the visited check.

    (⍺,⊂vials[⍋vials])∇(1↓⍵),{(⊂⍵),p}¨↓afters            ⍝ recur: add current path to the visited set, add sorted children to the popped queue, and recur the search loop. 
  },⊂⊂⍵                                                  ⍝ search is a binary operator. this is its right hand side; a singleton containing the initial game state
}'ABAB' 'BABA' '    '                                    ⍝ call search-then-print on this game state.

The punchline—things am proud of include:

  1. Using an outer product ∘.pour⍨vials to pour everything into everything else
  2. The resulting matrix has "the ordered pair of vials resulting from pouring i→j at each [i,j], and so you can easily recover where to put them in the original lineup.
  3. Pouring is cyclic rotation if the vessels are put head toz head and air goes at the bottom. -(⍺ vacancy ⍵))⊖((⌽⍺),⍵)
  4. Search algorithm is a dyadic anonymous recursive function with the stack to the right and the extended set to the left.
  5. I keep track of the state sequence but not the moves; you can easily recover the moves using a pairwise comparison to see which vials became more or less full each turn.

3. Original algorithm draft

The original draft of this algorithm had a few mistakes: it didn't forbid pouring from a vial to itself, violating conservation of liquid. And the "fail if the queue is empty" condition was misformatted. 

singleton←{1↓1,⊂⍵}
top←{0=⍴⍵:⍵⋄⊃(⍵⊂⍨1,2≠/⍵)}
vacancy←{(2>≢∪' '~⍨((top ⍺),(top ⍵)))×((+/(' '≠⍺))⌊(+/(' '=⍵))⌊(≢top ⍺))}
pour←{after←(-(⍺ vacancy ⍵))⊖((⌽⍺),⍵)⋄((⌽(≢⍺)↑after)((≢⍺)↓after))}
{{(((↑⍸¨(↓⍣1)2>⌿{≢' '~⍨⍵}¨⍵),('→',↑⍸¨(↓⍣1)2<⌿{≢' '~⍨⍵}¨⍵))⍪(' ' ' ' ' ')),⍵}↑⌽(⍬{0≡⍴⍵:⍬ ⋄ p←⊃⍵ ⋄ vials←⊃p⋄∧/{2>≢∪⍵}¨vials: p ⋄ (⊂{⍵[⍋⍵]} vials)∊⍺ : ⍺∇(1↓⍵) ⋄ intos←∘.pour⍨vials⋄afters ← {⍵[(⍋+/{+/2≠/⍵}¨⍵);]} ∪↑((⍴vials)*2)⍴{v←vials ⋄ v[⍵]←⊃(⍵⌷intos)⋄v}¨(⍳⍴intos)⋄ news←{(⊂((1↓⍴⍵)⍴⍵)),p}¨ (⊂⍤⊢⌺1⊢afters) ⋄   (⍺,(⊂{⍵[⍋⍵]}vials))∇({⍵[⍸{⍵≡∪⍵}¨⍵]}((1↓⍵),news)) } singleton⊂⍵)}('ABAB' 'BABA' '    ')

Date: 2023/June/03

Author: Dylan Holmes

Created: 2026-10-02 Fri 13:22

Validate