AoCG2021 Day 15: Leapfrog Santa

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

The story continues from AoC2015 Day 3, Part 2. This challenge was kindly contributed by Wheat Wizard (Grain Ghost).

Santa is delivering presents to an infinite two-dimensional grid of houses each 1 unit apart. The delivery begins delivering a present to the house at an arbitrary starting location, and then moving along a predetermined path delivering a new present at every step of the path. The path is a list of moves made of characters:

• ^ north
• v south
• > east
• < west

At each step Santa reads the instruction and starts heading in that direction until a house which hasn't had a present delivered yet is reached. At that point a present is delivered to that house and the next instruction starts.

Given a non-empty string representing directions, output the total length of the path that Santa will take.

This is so answers will be scored in bytes.

Test cases

v^v^v^v^: 36
^>v<^>v : 10
>>>>>><<<<<<< : 19
>>>vvv<<< : 9

• May we assume input isn't empty? Dec 15, 2021 at 0:06
• @pxeger I'd say yes. Dec 15, 2021 at 0:07
• Can we take input as a list/vector of char codes? That would save bytes for many answers... Dec 15, 2021 at 5:57
• @pajonk Sorry but no. This challenge's input format is tied to AoCG days 1 and 8, so I can't change it at this point. Dec 15, 2021 at 6:03
• @KevinCruijssen "total length of the path" is the distance traveled, which equals houses visited minus 1. Dec 16, 2021 at 9:35

Python 3.8 (pre-release), 76 bytes

f=lambda o,c=0,*v:len(o)and-~f(o[(d:=c+1j**(ord(o[0])%11))not in v:],d,c,*v)


Try it online!

Charcoal, 29 bytes

≔⁰ηＦＳ«Ｐ#Ｗ℅ＫＫ«Ｍ✳⊗⌕>^<ι≦⊕η»»⎚Ｉη


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

≔⁰η


ＦＳ«


Loop over the input characters.

Ｐ#


We already delivered a present here.

Ｗ℅ＫＫ«Ｍ✳⊗⌕>^<ι≦⊕η»


Look for somewhere to deliver the next present.

»⎚Ｉη


Cler the canvas and output the final path length.

Python 2, 81 bytes

c=t=0
v=0,
for i in input():
while c in v:c+=1j**(ord(i)%11);t+=1
v+=c,
print t

Attempt This Online!

Improvable.

1j**(ord(i)%11) is a sufficient hash function to give a layout of complex numbers corresponding to some transformation of the cardinal directions ^v><.

• You don't need the first copy of ;c+=x;t+=1 because v includes c at this point anyway.
– Neil
Dec 15, 2021 at 0:20
• @Neil thanks! I just worked that out myself - I had left it in because I wasn't sure why my answer wasn't working eariler (which was because I forgot to include 0 in the initial list) Dec 15, 2021 at 0:22

R, 85 bytes

function(s,x=1){for(j in utf8ToInt(s)%%11){while(x%in%T){x=x+1i^j
F=F+1}
T=c(x,T)}
F}


Try it online!

Uses the complex number, mod 11 trick.

Ruby, 67 62 bytes

->s{*r=a=0i;s.bytes.sum{|b|1.step.find{r!=r|=[a+=1i**b%=19]}}}


Try it online!

How?

Basically the usual mod 19 (or 11 or 13) trick. Start from (0+0i), sum the distance we have to travel for each house:

1.step.find{


a is the current position, b%19 is the direction, this literally counts the steps we need to find the first house that we have not visited yet.

r!=r|=[a+=1i**b%=19]}


This is the check: a is incremented once, we add it to the list with a union operator. If the house was already in the list, the list is unchanged and the result of the comparison is false, so we have to walk another step.

JavaScript (ES6), 83 bytes

Expects a list of characters.

a=>a.map(g=c=>g[g[[x,y]]=++t,i='^>v'.indexOf(c),[x+=i%2,y+=~-i%2]]&&g(c),t=x=y=0)|t


Try it online!

JavaScript (Node.js),  81  80 bytes

Saved 1 byte thanks to @Neil

Expects a string. Uses the mod 11 trick.

s=>Buffer(s).map(g=c=>g[g[[x,y]]=++t,i=c%11-7,[x+=i%2,y+=~i%2]]&&g(c),t=x=y=0)|t


Try it online!

• I think you can subtract 7 instead of 6 which allows you to use just ~ instead of ~-.
– Neil
Dec 15, 2021 at 10:06
• @Neil Hmm, I missed the notification for your message entirely. That looks fine indeed. Thanks! Dec 15, 2021 at 15:25

05AB1E, 37 bytes

1Ýˆv¯θ1ÝÂ‚D(«yÇ11%è©[+Ðˆ»¯€»s¢#®]¯g<


Explanation:

Uses a combination of generating [[0,1],[1,0],[0,-1],[-1,0]] that I've also used in my 05AB1E answer here and @alephalpha's modulo-11 trick from the AoCG2021 Day 1 challenge for indexing into it.

1Ýˆ                   # Add starting position [0,1] to the global_array
# (where we start is irrelevant, and [0,1] is shorter to
# push than [0,0])
v                  # Loop over the characters of the (implicit) input-string:
¯θ                #  Push the last coordinate of the global_array
1Ý              #  Push [0,1]
Â             #  Bifurcate it (short for Duplicate & Reverse copy): [1,0]
‚            #  Pair them together: [[0,1],[1,0]]
D(          #  Duplicate, and negate it: [[0,-1],[-1,0]]
«         #  Merge the lists together: [[0,1],[1,0],[0,-1],[-1,0]]
yÇ      #  Push the codepoint of the character
11%   #  Modulo-11 (5,6,7,8 for <^>v respectively)
è  #  Use it to 0-based modulair index into it
#  ([1,0],[0,-1],[-1,0],[0,1] for <^>v respectively†)
© #  Store this pair in variable ® (without popping)
[                 #  Start an inner infinite loop:
+                #   Add the top pair to the coordinate
Ð               #   Triplicate it
ˆ              #   Pop one, and add it to the global_array
»             #   Pop another, and join it with newline delimiter
¯            #   Push the global_array
€»          #   Join each coordinate with newline delimiter as well
s         #   Swap them on the stack
¢        #   Count this coordinate in the global_array*
#       #   If it's just 1: stop the infinite loop
®      #   (Else, when it's more than 1) Push the ®-pair again
]                  # After both loops
¯g                # Push the length of the global_array
<               # Decrease it by 1, because the PATH between coordinates is
# 1 lower than the amount of coordinates
# (after which the result is output implicitly)


: As you can see, the modular indexing into the pairs causes all four arrows to travel in the opposite direction, but just like the starting position, this is irrelevant for calculating the final result.
*: The count, indexOf, and contains builtins doesn't work when we want to check a list inside a list of lists, hence the join by newlines before we use the count.

Rust, 145 138 bytes

|i:&str|i.bytes().scan((vec![],[0,0]),|(v,p),c|{while{v.push(*p);p[c as usize%3&1]+=1-(c%5&2)as i64;v.contains(&p)}{}Some(v.len())}).max()


Try it online!

Same trick as as days 1 and 8.

Python3, 78 bytes

f=lambda n,c=[0]:len(n)and-~f(n[(j:=c[-1]+1j**(ord(n[0])%11))not in c:],c+[j])


Try it online!

• By switching to tracking position with a complex number rather than a 2-tuple of coordinates, and using the 1j**(ord(c)%11) trick from my answer, you can get 78 bytes: Attempt This Online Dec 15, 2021 at 2:12
• @pxeger Thank you, updated Dec 15, 2021 at 2:22

TypeScript Types, 276 bytes

//@ts-ignore
type a<T,P=0,N=1>=T extends[N,...infer T]?T:[...T,P];type M<I,P=[[],[]],N=[],V=0>=I extends${infer C}${infer R}?{"^":[P[0],a<P[1]>],v:[P[0],a<P[1],1,0>],">":[a<P[0]>,P[1]],"<":[a<P[0],1,0>,P[1]]}[C]extends infer Q?M<Q extends V?I:R,Q,[...N,0],V|P>:0:N["length"]


Try It Online!

Ungolfed / Explanation

// Increment an integer stored as e.g. [Pos, Pos] for 2, [Neg, Neg, Neg] for -3, and [] for 0
// Invoked as Inc<T> to increment, or Inc<T, 1, 0> to decrement
type Inc<T, Pos = 0, Neg = 1> = T extends [Neg, ...infer T] ? T : [...T, Pos]

type Main<
Instructions,
Pos = [[], []]
PathLength = [],
Visited = 0
> =
// Get the first character of Instructions
Instructions extends ${infer Char}${infer Rest}
// Store the new position in NewPos
? {
"^": [Pos[0], Inc<Pos[1]>],
v : [Pos[0], Inc<Pos[1], 1, 0 /* Dec */>],
">": [Inc<Pos[0]>, Pos[1]],
"<": [Inc<Pos[0], 1, 0 /* Dec */>, Pos[1]],
}[Char] extends infer NewPos
?
Main<
// If NewPos is not in Visited, set Instructions to Rest
NewPos extends Visited ? Instructions : Rest,
// Update Pos
NewPos,
// Add one to PathLength
[...PathLength, 0],
// Add Pos to NewPos
Visited | Pos,
>
: 0
// Instructions is empty
: PathLength["length"]


Pari/GP, 89 bytes

s->a=[p=c=0];[a=setunion(a,[while(c++;setsearch(a,p+=I^d),)+p])|d<-Vec(Vecsmall(s))%11];c


Try it online!

Wolfram Language (Mathematica), 79 bytes

(a[d=p=0]=0Clear@a;(a@p=0While[a[p+=#]<++d])&/@(I^ToCharacterCode@#~Mod~11);d)&


Try it online!