14
\$\begingroup\$

Inspired by this question on the puzzling stack exchange.

Rules

Given 5 stacks of 5 cards with numbers from 1 to 7, output the moves needed to empty all stacks. A move is defined as the index of a column to pull the card off of, and a move is only valid if:

  1. The stack is non-empty
  2. The value of the card at the top of the stack is exactly 1 lower or higher than the value of the last card removed from any of the stacks. Note 1 and 7 wrap.

Input

This challenge has loose input rules. You can use any format as input for the 25 numbers so long as the input is unambiguous among all possible inputs. The same token must be used for every instance of a card's representation. That is, if you use 2 to represent a 2, you must use that everywhere in your input. But you may use 2 to represent 2 and 532jv4q0fvq!@$$@VQea to represent 3 if this is somehow beneficial.

Output

The list of moves needed to empty all stacks without getting stuck. This format is also loose, but it needs to represent a list of indices, where 0 is the leftmost stack.

Your program may assume that the input provided is solvable. That is, you may have undefined behaviour in the case of unsolvable input.

Note: If the input has multiple possible solutions, outputting at least 1 valid solution is acceptable

Example/Test Case explained

Input: Representing the 5 stacks, where stack one is 5,5,3,2,6 with 5 being the top of the stack. Likewise for the other 4 stacks. Again, as stated in the question, this input format is loose and can be changed to facilitate the answer

5 5 3 2 6
2 4 1 7 7
4 2 7 1 3
2 3 3 1 4
4 6 5 5 1

Output: List of moves representing the order in which the cards are pulled off the stacks. I'll explain the result of the first 3 moves. The first 3 pops 2 off of the 4th stack (2 3 3 1 4 stack). The second 3 pops 3 off of the same stack. And then the 1 pops the 2 off of the 2nd stack. If you follow these moves on the input you will end up with empty stacks

[3, 3, 1, 3, 1, 0, 4, 0, 4, 4, 2, 0, 2, 1, 1, 3, 2, 2, 0, 2, 3, 4, 0, 1, 4]
\$\endgroup\$
  • \$\begingroup\$ You might consider providing some test cases. \$\endgroup\$ – Expired Data Jan 28 at 18:10
  • \$\begingroup\$ @ExpiredData Sure, I'll do that. In the interim, the linked question in puzzling has a working example \$\endgroup\$ – Cruncher Jan 28 at 18:11
  • 1
    \$\begingroup\$ A bit confusing have zero based numbering for the stacks and then referring to 4th, 2nd, &c stack! :-( \$\endgroup\$ – Noodle9 Jan 28 at 20:25
  • \$\begingroup\$ May we output without any separator, e.g. 3313104044202113220234014? \$\endgroup\$ – Arnauld Jan 28 at 20:56
  • 1
    \$\begingroup\$ @JonathanAllan Oh, yeah. That's totally acceptable \$\endgroup\$ – Cruncher Jan 30 at 17:30
3
\$\begingroup\$

Jelly,  31  28 bytes

The 31 byte answer:

ṖÞZṪs5J€Ƒ
ŒṪŒ!ÇƇðœịIA%5=1ẠðƇḢZḢ

Accepts the stacks as a list of lists, [s1, s2, s3, s4, s5] where each stack has the first playable card on its left; returns a list of the 1-indexed stacks to from which to play, left to be played first.

Get a list of all ways by replacing ḢZḢ with Ḣ€€.

Since this is way too inefficient for a 5 by 5...
Try a 3 by 3 version online! (5 replaced by 3 in the code)
- this still takes ~45s and the code is \$O(n^2!)\$.

How?

ṖÞZṪs5J€Ƒ - Link 1: check each stack used in order: list [[stackIndex1, cardIndex1],...]
 Þ        - sort by:
Ṗ         -   pop (i.e. sort by stackIndex values)
  Z       - transpose -> [[1,1,1,1,1,2,2,...,4,4,5,5,5,5,5], cardIndicesSortedByStack]
   Ṫ      - tail -> cardIndicesSortedByStack
    s5    - split into chunks of five - i.e. split up by stacks
        Ƒ - invariant under?:
       €  -   for each:
      J   -     range of length (i.e. equals [[1,2,3,4,5],[1,2,3,4,5],...]?)

ŒṪŒ!ÇƇðœịIA%5=1ẠðƇḢZḢ - Main Link: list of lists of integers, M
ŒṪ                    - truthy multi-dimensional indices
  Œ!                  - all permutations
     Ƈ                - filter keep those for which:
    Ç                 -   call last Link (1) as a monad
                 Ƈ    - filter keep those for which:
      ð         ð     -   the dyadic chain - i.e. checkCardOrder(2d-indices, M)
       œị             -     multidimensional index into M (vectorises)
         I            -     deltas - i.e. [a,b,c,d,...]->[b-a,c-b,d-c,...]
          A           -     absolute values
           %5         -     mod five
             =1       -     equals one
               Ạ      -     all?
                  Ḣ   - head - i.e. first valid 2d-inices pemutation
                   Z  - transpose -> [stackIndices, cardIndices]
                    Ḣ - head -> stackIndices

           ...OR: Ḣ€€ - head each of each -> list of all such stackIndices

The 28 byte answer:

Using the rule You can use any format as input for the 25 numbers so long as the input is unambiguous among all possible inputs we may choose seven numbers such that a new dyadic function which accepts a list of such numbers and returns a list with 1s for adjacent neighbouring numbers and 0 for non-adjacent neighbouring numbers replaces the code IA%5=1. I chose the following:

^ƝẒ - list of numbers from [2,7,12,14,25,28,91] (mapping to [1,2,3,4,5,6,7])
 Ɲ  - neighbours
^   - XOR
  Ẓ - is prime?

Here is a table of the XOR results:

 ^ |  2  7 12 14 25 28 91
---+----------------------
 2 |  0  5 14 12 27 30 89
 7 |  5  0 11  9 30 27 92
12 | 14 11  0  2 21 16 87
14 | 12  9  2  0 23 18 85
25 | 27 30 21 23  0  5 66
28 | 30 27 16 18  5  0 71
91 | 89 92 87 85 66 71  0

And if we check primality:

^Ẓ |  2  7 12 14 25 28 91
---+----------------------
 2 |  0  1  0  0  0  0  1
 7 |  1  0  1  0  0  0  0
12 |  0  1  0  1  0  0  0
14 |  0  0  1  0  1  0  0
25 |  0  0  0  1  0  1  0
28 |  0  0  0  0  1  0  1
91 |  1  0  0  0  0  1  0

Here is the equivalent to the 3 by 3 version above


Many other mappings work with this code, e.g.:

[1, 2, 3, 4, 5, 6, 7] : [2, 5, 6, 13, 16, 37, 39]

or

[1, 2, 3, 4, 5, 6, 7] : [7, 12, 17, 18, 21, 32, 34]
\$\endgroup\$
  • 1
    \$\begingroup\$ Very nice, I love when people come up with a super inefficient different way of looking at the problem that nobody would ever come up with outside of code golf. We think of brute force as the naive solution, and then there's real brute force \$\endgroup\$ – Cruncher Jan 29 at 21:13
7
\$\begingroup\$

JavaScript (V8), 86 bytes

This version is similar to the other one but takes advantage of the loose input format.

The cards are expected as follows:

\$[\text{Ace}, 2, 3, 4, 5, 6, 7] = [ 16, 37, 31, 91, 44, 41, 1 ]\$

f=(a,p,o='')=>o[24]?print(o):a.map((c,i)=>(v=c.pop())&&c.push((p^v)%3?v|f(a,v,o+i):v))

Try it online!

How?

The numbers \$a_n\$ representing the card values were chosen in such a way that:

  • \$a_i \bmod 3\neq0\$ for any \$i\in[1..7]\$
  • \$(a_i \operatorname{xor} a_j)\bmod 3\neq0\$ for any \$i,j\in[1..7]\$ iff the \$i\$-th and \$j\$-th cards are consecutive

Example:

Here is what we get for an Ace (\$v=16\$):

 previous card |     p     | p xor 16 | (p xor 16) mod 3
---------------+-----------+----------+------------------
     none      | undefined |    16    |        1
      ace      |     16    |     0    |        0
       2       |     37    |    53    |        2
       3       |     31    |    15    |        0
       4       |     91    |    75    |        0
       5       |     44    |    60    |        0
       6       |     41    |    57    |        0
       7       |      1    |    17    |        2

JavaScript (V8),  105 ... 92  91 bytes

Takes input as an array of 5 columns with 1-indexed cards (Ace = 1, Two = 2, etc.). Prints all solutions as strings of 0-indexed columns.

f=(a,p,o='')=>o[24]?print(o):a.map((c,i)=>(v=c.pop())&&c.push((p-~v*6)%7%5?v:v|f(a,v,o+i)))

Try it online!

How?

Given the previous card \$p\$ and the current card \$v\$, we compute:

$$k=((p+(v+1)\times6) \bmod 7) \bmod 5$$

The cards are consecutive iff \$k=0\$.

$$ \begin{array}{c|ccccccc} &1&2&3&4&5&6&7\\ \hline 1&1&0&4&3&2&1&0\\ 2&0&1&0&4&3&2&1\\ 3&1&0&1&0&4&3&2\\ 4&2&1&0&1&0&4&3\\ 5&3&2&1&0&1&0&4\\ 6&4&3&2&1&0&1&0\\ 7&0&4&3&2&1&0&1\\ \end{array} $$

We could, in theory, use \$v+(p+1)\times 6\$ just as well. But in the JS implementation, we want the result to be NaN (falsy) if \$p\$ is undefined (first iteration), which is why the bitwise operation (-~v) may only be applied to \$v\$.

Commented

f = (                  // f is a recursive function taking:
  a,                   //   a[] = input
  p,                   //   p = previous card (initially undefined)
  o = ''               //   o = solution
) =>                   //
  o[24] ?              // if o has 25 characters:
    print(o)           //   we have a complete solution: print it
  :                    // else:
    a.map((c, i) =>    //   for each column c at position i in a[]:
      (v = c.pop())    //     pop the last card v from this column
      &&               //     abort if it's undefined
      c.push(          //     otherwise:
        (p - ~v * 6)   //       use our magic formula
        % 7 % 5 ?      //       if it's not equal to 0 or NaN:
          v            //         just push v back
        :              //       else:
          v |          //         because v belongs to the global scope,
                       //         we need to use its current value right away
          f(           //         do a recursive call to f:
            a,         //           pass a[]
            v,         //           set p = v
            o + i      //           append i to o
          )            //         end of recursive call
      )                //     end of push()
    )                  //   end of map()
\$\endgroup\$
  • \$\begingroup\$ Was it easier to print all solutions instead of just the first? \$\endgroup\$ – Cruncher Jan 28 at 18:53
  • \$\begingroup\$ @Cruncher I think so. We could return the last solution for the same byte count (all solutions are still computed) but stopping the recursion on the 1st solution would probably cost more. \$\endgroup\$ – Arnauld Jan 28 at 19:00
  • \$\begingroup\$ How on earth did you come up with that formula for determining the consecutiveness of p and v \$\endgroup\$ – Cruncher Jan 28 at 21:43
  • 1
    \$\begingroup\$ @Cruncher That would be Math.abs(p-v) in JS, which is a bit lengthy. We could use (p-v)**2 instead. But it wouldn't work for the Ace<->7 wrapping anyway. \$\endgroup\$ – Arnauld Jan 28 at 21:58
  • 2
    \$\begingroup\$ (p-v)**2%7-1 also works and saves a pair of parentheses. \$\endgroup\$ – Grimmy Jan 29 at 13:00
2
\$\begingroup\$

Jelly, 43 bytes

““”;WA;"ị@Ṫ;ɗ¥¥ⱮT>Ƈ2Ɗ$€ẎIḢAfƑʋƇ1,6Ʋ25¡2ịⱮ_3

Try it online!

A monadic link taking a list of lists of integers (representing the stacks) and returning a list of lists of integers (representing the possible sequences of moves).

Explanation (method)

Works iteratively on 1 or more lists, each of which contains the sequence of cards so far at index 1, the sequence of stacks used at index 2 and the current stacks at positions 3 through 7. As such, the stacks are 3-indexed, and get changed to 0-indexing at the end. At each iteration, all possible moves are created, and then the sequence of cards is tested to check that the differences are all either -1, -6, 1 or 6. All valid moves are kept, and the next cycle of the loop is processed.

Explanation (code)

““”;                                        | Prepend two empty lists
    W                                       | Wrap in a further list
                                  Ʋ25¡      | Repeat the following 25 times:
                     $€                     | - For each current working list:
               Ɱ    Ɗ                       |   - Using each of the following as the right argument:
                T                           |     - Truthy indices (effectively here the indices of non-empty lists)
                 >Ƈ2                        |     - Keep only those greater than 2
              ¥                             |   - ... do the following as a dyad:
     A                                      |     - Absolute (used here for the side effect of copying the list)
             ¥                              |     - Following as a dyad:
      ;"    ɗ                               |       - Concatenate to following, using zipped arguments:
        ị@                                  |         - Index into list using reversed arguments
          Ṫ                                 |         - Tail, popping from list
           ;                                |         - Concatenate (to the list index)
                       Ẏ                    | - Join outer lists together
                             ʋƇ             | - Keep those lists where the following is true:
                        I                   |   - Increments (vectorises)
                         Ḣ                  |   - Head
                          A                 |   - Absolute
                           fƑ  1,6          |   - Invariant when filtered to only contain 1s and 6s
                                      2ịⱮ   | 2nd sublist of each (i.e. the sublist containing the list indices used)
                                         _3 | Minus 3
\$\endgroup\$
1
\$\begingroup\$

Ruby, 140...121 119 bytes

->n{w=[*0..4].product;w.find{|x|5.times{|j|((n[j][x.count j]||99)-n[a=x[-1]][~-x.count(a)])**2%35==1&&w<<x+[j]};x[24]}}

Try it online!

How:

Breadth-first search:

  • initialize the solution vector with the single cards on top of the stacks. (w=[[0],[1],[2],[3],[4]])
  • for every solution in the vector, check the possible next step. For example, [0] could expand to [0,2] or [0,4]. Append these new solutions to the vector.
  • now check if the solution has 25 elements: if it does, it's complete, and we can stop.

The check could be more efficient, but since I only save the stack numbers, I have to get the cards from the stacks on every iteration. Changing the stack in a non-recursive solution is out of the question, and saving the card numbers would require more code.

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