15
\$\begingroup\$

Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.


An Elf is hopping on a chessboard which extends infinitely in all four directions. They move like a generalized chess Knight: on each step, they move X units horizontally and Y units vertically, or Y units horizontally and X units vertically. ((X,Y) = (1,2) would give regular Knight's moves.)

The Elf plays the game "Self-trapping Elf". In this game, the Elf starts at position (0,0) and hops around. They cannot hop into any cell already hopped on, including the starting cell. The objective is to trap themselves in the fewest number of steps possible.

Task: Given the values of X and Y (0 < X < Y), output the sequence of coordinates that the Elf should visit, so that they can trap themselves in exactly 15 moves.

Standard rules apply. The shortest code in bytes wins.

Some explanation can be found in this Puzzling post. There are many ways to achieve this: (the worked out examples are for (X, Y) = (1, 2))

  • Choose any position (X) one move away from the origin (O). We will step all 8 cells reachable from X and then move into it.
. O . A .
G . . . B
. . X . .
F . . . C
. E . D .
  • For almost any pair of cells out of OABCDEFG, there is exactly one way to move from one cell to the other in 2 steps without going through X.

    The following are valid solutions to the problem:

. . . . 1 . . . .
. . . . . . . 3 .
. . . 0 . 2 . . .
. . e . . . 4 . .
d . . . f . . . 5
. . c . . . 6 . .
. . . a . 8 . . .
. b . . . . . 7 .
. . . . 9 . . . .

. 0 b 6 .
a 5 . 1 c
. . f . 7
4 9 . d 2
. e 3 8 .

The actual output for the first answer would be

[(1, 2), (2, 0), (4, 1), (3, -1), (5, -2), (3, -3), (4, -5), (2, -4),
 (1, -6), (0, -4), (-2, -5), (-1, -3), (-3, -2), (-1, -1), (1, -2)]

You may include or exclude the starting position of (0, 0).

\$\endgroup\$
6
  • \$\begingroup\$ I assume the starting position is only allowed as the 16th element? \$\endgroup\$
    – Neil
    Commented Dec 2, 2022 at 0:48
  • \$\begingroup\$ @Neil No, I meant at the start. \$\endgroup\$
    – Bubbler
    Commented Dec 2, 2022 at 0:53
  • \$\begingroup\$ It turns out that I was able to save three bytes using a different approach anyway. \$\endgroup\$
    – Neil
    Commented Dec 2, 2022 at 0:54
  • \$\begingroup\$ May I take input as a complex number and output a list of complex numbers? \$\endgroup\$
    – alephalpha
    Commented Dec 2, 2022 at 1:16
  • 1
    \$\begingroup\$ Related: The Path Of The Wildebeest; Trapped Knight Sequence. \$\endgroup\$ Commented Dec 2, 2022 at 11:52

7 Answers 7

4
\$\begingroup\$

JavaScript (ES6), 79 bytes

Expects [Y, X]. The path is hardcoded.

V=>[p=[0,0],..."763145621057234"].map(d=>p=p.map((v,k)=>v+V[d&1^k]*~-(d>>k&2)))

Try it online!

Or 78 bytes if we don't output the starting position.

Encoding

The directions are encoded with 3-bit values, using the following scheme:

 d | as binary | (dx,dy)
---+-----------+---------
 0 |   0 0 0   | (-Y,-X)
 1 |   0 0 1   | (-X,-Y)
 2 |   0 1 0   | (+Y,-X)
 3 |   0 1 1   | (+X,-Y)
 4 |   1 0 0   | (-Y,+X)
 5 |   1 0 1   | (-X,+Y)
 6 |   1 1 0   | (+Y,+X)
 7 |   1 1 1   | (+X,+Y)
       | | |
       | | +--> if set, use X for |dx| and Y for |dy|
       | |      (if cleared, do it the other way around)
       | +----> sign of dx (positive if set)
       +------> sign of dy (positive if set)

Commented

V =>                 // V[] = input vector [ Y, X ]
[ p = [0,0],         // p[] = current position, initialized to [ 0, 0 ]
  ...                //       this is also the 1st direction (zero'ish)
  "763145621057234"  // <-- = the directions for the next 15 moves
]                    //
.map(d =>            // for each direction d:
  p =                //   update the position:
    p.map((v, k) =>  //     for each coordinate v at index k:
      v +            //       add to v
      V[d & 1 ^ k] * //       either V[0] or V[1] according to bit #0
      ~-(d >> k & 2) //       multiplied by either -1 or +1
                     //       according to bit #1 or bit #2
    )                //     end of inner map()
)                    // end of outer map()
\$\endgroup\$
4
\$\begingroup\$

Jelly,  23  17 bytes

-3 by using - I really should know to use this since I actually implemented this atom! >.<
-1 altering valid move generation code.
-2 compressing in a way so as not to need valid move construction.

;N“©Ȯṅ!ı|⁺⁸’ṃs2+\

A monadic Link that accepts the pair [Y, X] and yields a list of coordinates.

Try it online! Or try it with a formatted output.

How?

;N“©Ȯṅ!ı|⁺⁸’ṃs2+\ - Link: pair of integers, [Y, X] (1 < X < Y)
 N                - negate -> [-Y, -X]
;                 - concatenate -> [-Y, -X, Y, X]
  “©Ȯṅ!ı|⁺⁸’      - base 250 number = 477042125414097387
            ṃ     - (that) base decompress ([-Y, -X, Y, X])
                    -> convert to base 4 using [-Y, -X, Y, X] as digits [1, 2, 3, 0]
             s2   - split into twos
                \ - cumulative reduce by:
               +  -   addition (vectorises)
\$\endgroup\$
4
\$\begingroup\$

Charcoal, 50 bytes

F²⊞υN≔⟦υ⮌υ⟧θ≔⁺θ±θθ≔⁺θEθEι⎇μλ±λθIΦΣEθ⟦E§θ⊖κ⁺λ§ιμι⟧κ

Attempt This Online! Link is to verbose version of code. Explanation:

F²⊞υN

Input X and Y.

≔⟦υ⮌υ⟧θ≔⁺θ±θθ≔⁺θEθEι⎇μλ±λθ

Generate all of the positions one step away from the origin.

IΦΣEθ⟦E§θ⊖κ⁺λ§ιμι⟧κ

Output the positions and in between each pair of positions also output the other position one step away from both.

If string input and complex output is acceptable, then for 38 36 bytes:

F+-F⁴⊞υ×I⪫⟦θιηj⟧ωXI1jκΦΣEυ⟦⁺ι§υ⊖κι⟧κ

Attempt This Online! Link is to verbose version of code. Explanation:

F+-F⁴⊞υ×I⪫⟦θιηj⟧ωXI1jκ

Generate all positions one step away from the origin.

ΦΣEυ⟦⁺ι§υ⊖κι⟧κ

Output the positions and in between each pair of positions also output the other position one step away from both.

\$\endgroup\$
3
\$\begingroup\$

Python NumPy, 93 bytes (@alephalpha)

lambda p:cumsum(kron([p,-p,*conj([p,-p])],[1,-1,1j,-1j])[-(r_[:14,15]^1)])
from numpy import*

Attempt This Online!

Python NumPy, 96 bytes

lambda p:cumsum(kron([p,q:=p-2*p.real,-q,-p],[1,-1,1j,-1j])[-(r_[:14,15]^1)])
from numpy import*

Attempt This Online!

Uses complex numbers.

This works essentially by hopping from the trapping square to each of the eight reachable squares and back an then swapping moves 2 and 3, 4 and 5, 6 and 7 (1-based) and so on. Unfortunately not very short.

\$\endgroup\$
2
  • \$\begingroup\$ p-2*p.real -> conj(p). \$\endgroup\$
    – alephalpha
    Commented Dec 2, 2022 at 7:36
  • \$\begingroup\$ @alephalpha Ah, I thought I was stuck on p.conjugate. Thanks! \$\endgroup\$
    – loopy walt
    Commented Dec 2, 2022 at 8:43
3
\$\begingroup\$

PARI/GP, 63 bytes

t->Vec(((u=conj(s=t/(I-x^2)%y=x^8)+s*y)*x^3-u+t)/(1-x)%y^2+u%x)

Attempt This Online!

Takes a complex number (X+Y*I) and outputs a list of complex numbers.

Implements the algorithm in @Neil's Charcoal answer using polynomial magics.

. . d . 1 . .
. . 0 . c . .
. e . . . 2 b
. . . f . . .
. 6 . . . a 3
. . 8 . 4 . .
7 . 5 . 9 . .

PARI/GP, 71 bytes

t->s=0;[s+=a|a<-[-v=I*t,t,t,v,v,-t,-u=conj(t),-v,w=I*u,u,u,-w,-w,-u,w]]

Attempt This Online!

Gives the same result as above, but the directions are hardcoded.

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

APL(Dyalog Unicode), 37 bytes SBCS

{-∘⊃⍨{,⍉↑⍵(2+/⍵)}{∊⍵,¨2⌽⌽+⍵}⍵×0j1*⍳4}

Try it on APLgolf!

Input a complex number yJx.

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

05AB1E, 20 bytes

(ì•Ct-V₂‹Sθ•sÅв2ôÅ»+

Port of @JonathanAllan's Jelly answer, so make sure to upvote him as well!

Try it online or try it online pretty-printed.

Explanation:

(            # Negate the values in the (implicit) input-pair: [-Y,-X]
 ì           # Prepend it in front of the (implicit) input-pair: [-Y,-X,Y,X]
  •Ct-V₂‹Sθ• # Push compressed integer 856559820693157436
   s         # Swap so earlier quadruplet is on top again
    Åв       # Convert 856559820693157436 to custom base [-Y,-X,Y,X],
             # which basically converts it to base 4, and indexes into the quadruplet
             # (unlike Jelly, 05AB1E uses 0-based indexing, so [-Y,-X,Y,X] → [0,1,2,3])
      2ô     # Then split this list into pairs
        Å»   # Cumulative left-reduce it, keeping all intermediate results:
          +  #  Add the values at the same positions in the pair together
             # (after which the result is output implicitly)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why •Ct-V₂‹Sθ• is 856559820693157436.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.