12
\$\begingroup\$

Warning: Contains minor Deltarune Chapter 1 Spoilers

Within the Forest section of the first chapter of Deltarune, there are a few puzzles that consist of entering playing-card suits in a certain order to move to the next section. Below is an example of such a puzzle:

The way to solve the puzzle is to do any of the following until the input pattern matches the required pattern: a) add a spade, b) add a diamond, c) toggle the suits of the already inputted pattern (spades goes to clubs and vice versa, hearts goes to diamonds and vice versa).

The solution to the puzzle in the picture is:

a) Add a spade

b) Add a diamond

c) Add a spade

d) Toggle suits

Here's a video version of the solving of the puzzle

A Worked Example

Say the required pattern was diamond, heart, club, spade (DHCS). We first add a heart to the input, as the first item will have to be red in some way:

D . . .

We then toggle the suits so that we have heart as the first suit.

H . . .

We then add a diamond to complete the first two suits.

H D . .

We add then add a spade.

H D S .

And invert the suits one last time.

D H C .

Finally, we add the spade and the puzzle is complete.

D H C S

Rules

  • Input can be taken as a collection (e.g list, string) of any 4 distinct values that represent the 4 suits. E.g. [4, 3, 2, 1] where 1 = spades, 2 = clubs, 3 = hearts, 4 = diamonds.
  • It is guaranteed that the input is solvable. You won't need to handle any unsolvable cases.
  • There will always be at least one item in the required pattern.
  • Output can be given as a collection (e.g list, string) of any 3 distinct values that represent the 3 possible move types. E.g [2, 3, 2, 1, 3, 1] where 1 = add spade, 2 = add diamond, 3 = toggle suits
  • There may be multiple solutions of differing length. You can output either one solution or all solutions.
  • Toggling twice in a row won't be part of any valid solution.
  • Steps in the solution(s) need to be in the right order.

Test Cases

Assuming SCHD for Spades, Clubs, Hearts and Diamonds for input. Assuming SDT for Spade, Diamond, Toggle. Assuming only one solution returned.

"CHC" => ["S", "D", "S", "T"]
"DHCS" => ["D", "T", "D", "S", "T", "S"]
"SDC" => ["S", "D", "T", "S", "T"]
"HSD" => ["D", "T", "S", "D"]
"CHS" => ["S", "D", "T", "S"]

As this is , the aim of the game is to use as few bytes as possible, as you never know what Lancer and Susie will do next.

\$\endgroup\$
5
  • \$\begingroup\$ I hope for 1 solution we are allowed to toggle twice in a row \$\endgroup\$
    – mousetail
    Jul 12 at 13:56
  • \$\begingroup\$ Can the output be a number where each digit uniquely corresponds to a move (e.g. 232131 instead of [2, 3, 2, 1, 3, 1]?) \$\endgroup\$
    – Adam
    Jul 12 at 15:25
  • \$\begingroup\$ @Adam There's something in the standard I/O saying numbers and digit lists are interchangeable. \$\endgroup\$
    – emanresu A
    Jul 12 at 20:41
  • \$\begingroup\$ I found it, thanks @emanresuA \$\endgroup\$
    – Adam
    Jul 12 at 20:54
  • 2
    \$\begingroup\$ Abuse of input format: takes input as a list of integers 0=spades, 1=diamonds, 202=clubs, 212=hearts, stringify and join everything, and remove 22s, remaining 2s are toggles. ⁻⪫Aω22. \$\endgroup\$
    – Neil
    Jul 13 at 0:15

8 Answers 8

7
\$\begingroup\$

Retina 0.8.2, 15 bytes

H
TDT
C
TST
TT

Try it online! Doesn't output minimal solutions but link is to test suite that removes redundant leading toggles for convenience. Explanation:

H
TDT

TDT inserts an H without changing the overall toggle state.

C
TST

TST inserts a C without changing the overall toggle state.

TT

Remove consecutive toggles, as they're not allowed. (Would have saved 4 bytes if they were allowed.)

\$\endgroup\$
5
\$\begingroup\$

Jelly, 11 bytes

ṁỊ;1ŒgƊḂKḣ-

Try it online!

Works as either a function or a full program. Input format is a list of numbers, 0, 1, 2, 3 for diamonds, spades, hearts, clubs respectively. Output format is a string of '0' for diamonds, '1' for spades, and a space character ' ' for a toggle. (The TIO link contains a footer which wraps the output in double quotes, so that trailing spaces are visible.)

Algorithm

Mathematical algorithm for solving this puzzle

(i.e. "ais523 has mistaken PPCG for Puzzling")

This is a closed-form algorithm that produces an optimal solution directly in linear time, using mathematical properties of the puzzle rather than any sort of brute force. The basic observation is that we can split the suits into two groups, the "writable" suits diamonds and spades (which have numbers 0 or 1, i.e. return true from Jelly's builtin), and the "unwritable" suits clubs and hearts (which have numbers 2 and 3, i.e. return false from Jelly's builtin). For any two positions in the string (either the string we're trying to create or the string we're working on), it's possible to define a "writability difference" – 'same' if the two positions contain suits with the same writability, or 'different' if the two positions contain suits with different writabilities.

None of our three basic operaions change the writability difference between any two positions that already contain a card: a toggle will affect all writabilities equally and thus will not cause them to become different or cease to be different, and addition of a card won't change positions where we've already added a card. This means that whenever a card is added, it must be added in such a way that the position we're adding it to already has the correct writability difference with the other existing positions (i.e. the same writability difference as it does in the string we're aiming for), and that status will not subsequently change during the solution.

This leads to a really simple rule for determining where to put the toggle actions: performing two addition actions in a row will add two writable suits, thus the writability difference between the added suits' positions will be 'same', and placing a toggle between two addition actions will add a writable suit after an unwritable suit and thus create a writability difference of 'different'. Therefore, in any valid solution that does not contain double-toggles, toggles prior to the final card being added must appear in those, and only those, positions where the two immediately adjacent suits have a writability difference of 'different'. (After the final card, clearly a toggle is required if the final card is unwritable, but not if the final card is writable as the string will already be correct in that case.)

That immediately forces the position of every toggle action. The add-card actions are also obviously forced: a toggle action can't change a card between red and black, so to add a red card (represented with an even number), it's required to add a diamond, and to add a black card (represented with an odd number), it's required to add a spade.

Assuming that there's at least one solution, this gives a description of how to find it (and incidentally also proves that there's at most one solution that doesn't involve a double-toggle or a useless toggle at the start). In fact, there is always exactly one solution that doesn't involve a double-toggle or useless leading toggle; the above argument doesn't prove this directly but can be extended to do so.

Expressing this algorithm in Jelly

The core of the algorithm can be expressed in Jelly by looking at the list of writabilities (), and grouping it into blocks of consecutive equal writabilities (Œg). is then used to copy the shapes of the blocks onto the original list, which is reduced to a list of red (0) / black (1) using . The resulting list can then be joined on anything other than 0 or 1 in order to add the toggles (as a toggle needs to be put anywhere there's a writability difference of 'different', i.e. the writability changes, and that happens at the gaps between the blocks); joining on spaces (K) is tersest as that has a single-character builtin (even though it makes the output a little hard to read, that isn't a requirement of the question).

This doesn't, however, handle the requirement to add an extra "toggle" at the end if the last suit is unwritable. The tersest way I've found to implement this requirement is to append a 1 to the list of writabilities (;1), which (due to how works) effectively adds "a copy of the first suit but writable" to the end of the list of suits we're creating, and then remove it the added suit again at the end of the program (h-). This is a no-op if the last suit in the desired output is writable. If, however, the last suit in the desired output is unwritable, this creates a writability difference of 'different' which will lead to an extra toggle instruction being added between the last requested suit and the added suit; and when the added suit is deleted, the toggle instruction won't be. Both cases therefore end up with the desired result, with no explicit if statement needed.

Explanation

ṁỊ;1ŒgƊḂKḣ-
      Ɗ      like parentheses, surrounding the previous three builtins
 Ị           {for each suit}, 1 if the suit is 0 or 1, 0 if it's larger
  ;1         append 1
    Œg       group consecutive equal elements into sublists
ṁ            unflatten {the input}, using the same sublists in the same places
       Ḃ     {for each suit}, 1 if the suit is odd, 0 if it's even
        K    join on spaces
         ḣ-  delete the last element
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I think this idea would also work for a generalization of the puzzle, in which "toggle" becomes "cycle" and instead of pairs we have sets of n related items. in each set, only one item can be directly entered, and the others must be cycled to. \$\endgroup\$
    – Jonah
    Jul 12 at 21:54
4
\$\begingroup\$

Python, 75 bytes

f=lambda p,t=0:p and((v:=p[-1]-t)%2and v+10*f(p[:-1],t)or 5+10*f(p,~t))or 0

Attempt This Online!

The input is a list of integers, and the output is an integer where each digit read left to right represents a possible move.
For input: clubs, spades, hearts, and diamonds are 0, 1, 2 and 3 respectively.
For output moves: spades, diamonds, and toggle are 1, 3 and 5 respectively.


If a number is not a valid output format, then the answer is 76 bytes:

f=lambda p,t=0:p and((v:=p[-1]-t)%2and f(p[:-1],t)+str(v)or f(p,~t)+"5")or""

Attempt This Online!


How it works

Here's the unminimized code:
def f(p,t=0):
  if p:
    if (v:=p[-1]-t)%2:# true if (t=0 & p=1,3) or (t=-1 & p=0,2)
      return f(p[:-1],t)*10+v
    else:
      return f(p,~t)*10+5 # 5 is arbitrarily chosen
  else:
    return 0

It's a recursive function that works from the end of the list to the beginning. t is a toggle flag -- it's -1 when the output will become either a heart or a club, and 0 when the output will be either a spade or a diamond. We append toggles until the end value and toggle bit have different odd-ness/even-ness, then append the associated move (spade if end value is spade/club, diamond if it's diamond/heart).


-1 byte from @math junkie

\$\endgroup\$
3
  • \$\begingroup\$ Actually, since this is a recursive function that calls itself by name, does that mean that the name of the function has to be included in the byte count? \$\endgroup\$
    – Adam
    Jul 12 at 15:52
  • 1
    \$\begingroup\$ Yes, you need to include the function name. See this meta post \$\endgroup\$ Jul 12 at 17:06
  • 1
    \$\begingroup\$ You can remove the space after the 2 :) \$\endgroup\$ Jul 12 at 17:21
4
\$\begingroup\$

Charcoal, 20 bytes

⁻⪫⪪⪫⪪SH¦TDT¦C¦TST¦TT

Try it online! Link is to verbose version of code. Explanation:

     S                  Input string
    ⪪ H                 Split on `H`
   ⪫    TDT             Join with `TDT`
  ⪪         C           Split on `C`
 ⪫            TST       Join with `TST`
⁻                 TT    Remove all `TT` substrings
                        Implicitly print
\$\endgroup\$
1
  • \$\begingroup\$ Nice observation. \$\endgroup\$
    – Jonah
    Jul 12 at 21:02
3
\$\begingroup\$

Rust, 149 126 bytes

|t:&[u8]|t.iter().rev().scan(false,|b,&k|Some(if(k<2)^*b{vec![k&5]}else{*b=!*b;vec![k&5,2]})).fold(vec![],|a,b|[b,a].concat())

Verify All Test Cases

\$\endgroup\$
1
  • \$\begingroup\$ I'm going to say that solutions have to be in the right order. Sorry about that \$\endgroup\$
    – lyxal
    Jul 12 at 14:43
2
\$\begingroup\$

JavaScript (Node.js), 70 64 bytes

-6 thanks to Arnauld

f=(x,y=x.pop())=>y%2?[...f(x),y]:++y?[...f(x.map(z=>z^1)),y,4]:x

A recursive solution, which I believe also finds the optimal solution. Uses 0 through 3 for clubs, spades, hearts, and diamonds, and uses 4 for toggle, and 1 and 3 to add the respective cards.

Try it online!

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

Vyxal, 11 bytes

vṅ1JĠ•∷vṅṄṪ

Try it Online!

Port of Jelly, so go upvote that.

This should be 9 bytes: https://github.com/Vyxal/Vyxal/issues/1285

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 18 16 11 (or 4) bytes

4ƵK:5ƵU:11K

-5 bytes porting @Neil's Retina answer, with integers as I/O

Inputs 2345 for DSHC respectively; outputs 123 for TDS respectively.

Try it online or verify all test cases.

Or 4 bytes with @Neil's convenient input-format: inputs as a list with 0 1 202 212 for S D C H respectively; outputs a string with 0 1 2 for DST respectively.

J22K

Try it online or verify all test cases.

Original 18 16 bytes approach:

₂…)˜(ªÞæ.Δ».V)˜Q

Inputs -6 -2 2 6 for C H D S respectively; outputs 2 6 )˜( for D S T respectively.

Try it online or verify all test cases.

Explanation:

   :              # Replace
4                 # all 4
 ƵK               # with 121
       :          # Then replace
    5             # all 5
     ƵU           # with 131
          K       # Then remove
        11        # all 11
                  # (after which the result is output implicitly)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why ƵK is 121 and ƵU is 131.

₂                 # Push 26
 …)˜(             # Push string ")˜("
     ª            # Convert the 26 to [2,6], and append the string: ["2","6",")˜("]
      Þ           # Cycle it indefinitely: ["2","6",")˜(","2","6",")˜(","2",...]
       æ          # Get the powerset of this infinite list
        .Δ        # Find the first result which is truthy for:
          »       #  Join the list with newline delimiter to a single string
           .V     #  Evaluate and execute it as 05AB1E code:
                  #   `2`: Push a 2
                  #   `6`: Push a 6
                  #   `)˜(`: Wrap stack into a list; flatten; negate each
             )˜   #  Wrap the stack into a list and flatten
               Q  #  Check if it's equal to the (implicit) input-list
                  # (after which the found result is output implicitly)
\$\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.