AoCG2021 Day 6: Taxicab in a triangular city

Question

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

Related to AoC2016 Day 1, Part 1.

---

You're airdropped near Easter Bunny Headquarters in a city somewhere. "Near", unfortunately, is as close as you can get - the instructions on the Easter Bunny Recruiting Document the Elves intercepted start here, and nobody had time to work them out further.

The Document indicates that you should start at the given coordinates (where you just landed) and face North East. Then, follow the provided sequence: turn right 60 degrees, then walk forward the given number of blocks, ending at a new intersection.

"What, 60 degrees?" You think, and you look around. Then you realize the city is not quite like what you imagine; the streets in this city form a triangular grid.

Anyway, there's no time to follow such ridiculous instructions on foot, though, so you take a moment and work out the destination. Given that you can only walk on the street grid of the city, how far is the shortest path to the destination?

For example, if the instructions are [1, 1, 0, 2], it means to:

• Turn right 60 degrees and move 1 block forward
• Turn right 60 degrees and move 1 block forward
• Turn right 60 degrees and stay in place
• Turn right 60 degrees and move 2 blocks forward

In the end, you end up at just 1 block west of the start.

Input: A (possibly empty) list of non-negative integers. If you encounter a 0, it means to turn right 60 degrees but stay in place.

Output: A non-negative integer indicating how far away the destination is from the current position, measured in triangular taxicab distance.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

[] -> 0
[1, 1, 1] -> 2
[1, 1, 0, 2] -> 1
[1, 2, 0, 0, 0, 2, 1] -> 4
[1, 2, 3, 4] -> 6

Answer 1

Python 2, 62 bytes

p=q=0
for i in input():p,q=i+p-q,p
print max(0,p,q)-min(0,p,q)

Try it online!

62 bytes version suggested by loopy walt

---

Python 2, 64 bytes

p=q=0
for i in input():p,q=i-q,p+q
print max(p,q,p+q,-p,-q,-p-q)

Try it online!

-3 bytes by Arnauld and xnor.

---

Python 2, 94 bytes

a=input()
p,q,r=[sum(a[i::6])-sum(a[i+3::6])for i in[0,1,2]]
print max(map(abs,[p-r,q+r,p+q]))

Try it online!

Answer 2

Pari/GP, 49 bytes

a->p=q=0;[[p,q]=[i-q,p+q]|i<-a];normlp([p,q,p+q])

Try it online!

A port of @tsh's answer. Make sure to upvote that answer as well!

---

Pari/GP, 53 bytes

a->vecmin([normlp(Pol(a)*x^i%(x^2-x+1),1)|i<-[0..2]])

Try it online!

If we see the city as the complex plane, then the instructions \$[a,b,c,\dots]\$ will end up at the point \$a+b\ x+c\ x^2+\cdots\$, where \$x={(-1)}^{1/3}=\frac{1}{2}+\frac{\sqrt{3}}{2}i\$ is a root of the equation \$x^2-x+1=0\$. So we can convert the input into a polynomial with variable \$x\$, and mod \$x^2-x+1\$. This gives the destination in the form \$a+b\ x\$.

normlp(...,1) is the usual taxicab distance: normlp(a+b*x,1)=abs(a)+abs(b). If the destination lies in the first or the fourth sextant of the plane (i.e., \$a+b\ x\$ where \$a,b>0\$ or \$a,b<0\$), this already gives the correct result. In other cases we need to rotate the destination by 60° or 120°. 60° rotation is just multiplying by \$x\$, 120° is multiplying by \$x^2\$. We try all possible rotations and take the smallest taxicab distance.

Answer 3

R, 62 bytes

function(x,p=0){for(i in x)p=p+i-(F=F+p);max(abs(c(p,F,p+F)))}

Try it online!

Approach based on xnor's comment on tsh's answer.

Answer 4

JavaScript (ES6), 90 bytes

a=>a.map(n=>b+=n*~-(s="1221")[a+=n*~-s[d%6],++d%6],a=b=d=0)|(A=Math.abs)(a)+A(b)+A(a-b)>>1

Try it online!

---

JavaScript (ES6), 63 bytes

Using the optimization suggested by xnor on tsh' answer.

a=>a.map(n=>[p,q]=[n-q,p+q],p=q=0)|Math.max(p,q,p+q,-p,-q,-p-q)

Try it online!

Answer 5

Charcoal, 37 28 26 bytes

Ｆ³⊞υ⁰ＦＡ≔⟦⊟υ⁻ι§υ⁰⁺ι⊟υ⟧υＩ⌈↔υ

Try it online! Link is to verbose version of code. Explanation: Now another port of @tsh's original Python answer (the subsequent golfs don't apply to Charcoal).

Ｆ³⊞υ⁰

Start with an array of three zeros.

ＦＡ

Loop over the input movements.

≔⟦⊟υ⁻ι§υ⁰⁺ι⊟υ⟧υ

Update the array (note that the values are in reverse order from @tsh's version, allowing two of the values to be popped from the array, saving a byte).

Ｉ⌈↔υ

Output the maximum absolute value.

Alternative formulation, also 26 bytes, based on @GB's idea that the original array only needs a single zero and cyclic indexing will expand it to three values:

⊞υ⁰ＦＡ≔⟦⁺ι§υ¹⁻ι§υ²§υ⁰⟧υＩ⌈↔υ

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

⊞υ⁰

Push a zero to the predefined empty list.

ＦＡ

Loop over the input movements.

≔⟦⁺ι§υ¹⁻ι§υ²§υ⁰⟧υ

Update the list (this is back to the original order from @tsh's original Python answer).

Ｉ⌈↔υ

Output the maximum absolute value.

Previous 28-byte canvas-based answer using @Arnauld's adjusted square coordinates:

ＦＬθＭ§θι✳÷×⁴ι³≔⊘Σ↔⟦ⅈⅉ⁺ⅈⅉ⟧η⎚Ｉη

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

ＦＬθ

Loop over each step.

Ｍ§θι✳÷×⁴ι³

Make a movement in each direction in turn, but skipping northwest and southeast.

≔⊘Σ↔⟦ⅈⅉ⁺ⅈⅉ⟧η

Calculate the final distance as half the sum of the absolute values of the two coordinates and their sum.

⎚Ｉη

Reset the cursor and output the distance.

Answer 6

Ruby, 58 bytes

->l{l.reduce(0){|s,x|[x+s[1],x-s[2],s[0]]}.map(&:abs).max}

Try it online!

Port of tsh's answer to Ruby

Starting with [0,0,0] encoded as (0), the first iteration of reduce will transform it automatically.

Answer 7

05AB1E, 16 14 bytes

0ÐIv(2Fy+Š])Äà

Port of @tsh' top Python answer.
-1 byte thanks to @Neil, which also allowed a second byte to be saved

Try it online or verify all test cases.

Explanation:

0Ð            # Push three 0s, let's call these a,b,c
  I           # Push the input-list
   v          # Pop and loop over each item `y`:
    (         #  Negate the top item
     2F       #  Loop 2 times:
       y+     #   Add the current integer `y` to the top
         Š    #   Tripleswap x,y,z to z,x,y
              #  (after this inner loop, a,b,c is y+b,y-c,a)
   ]          # Close both loops
    )         # Wrap all three values into a list
     Ä        # Get the absolute values of each
      à       # Pop and push the maximum

Answer 8

MathGolf, 14 13 bytes

0∙êô,\ì+\?ß±╙

Port of @tsh' top Python answer.

Try it online.

Explanation:"

0∙            # Push three 0s, let's call these a,b,c
  ê           # Push the inputs as integer-list
   ô          # Foreach over these integers,
              # using 6 characters as inner code-block:
              #  (implicitly push the current loop-integer, let's call this y)
    ,         #  Subtract the second item from the top: y-c
     \        #  Swap the top two values on the stack
      ì+      #  Add the loop-integer `y`: b+y
        \?    #  Swap back, and tripleswap: a,y-c,b+y to b+y,y-c,a
          ß   # After the loop, wrap the three values into a list
           ±  # Get the absolute value of each
            ╙ # Pop and leave the maximum
              # (after which the entire stack is output implicitly as result)

Answer 9

Rust, 101 bytes

|i|{let mut p=(0,0);for n in i{p=(n-p.1,p.0+p.1)}let(p,q)=p;vec![p,q,p+q,-p,-q,-p-q].drain(..).max()}

Try it online!

Port of @tsh's answer as well.

error[E0658]: destructuring assignments are unstable >:(

Answer 10

Python 3, 94, 90 bytes

def f(I):
 a=b=c=0
 for i in I:a,b,c=2*i-b,-i-c,-i-a
 return max(map(abs,(a-b,b-c,c-a)))/3

Try it online!

Old version

Uses barycentr-ish coordinates. Not 100% sure this is correct even though it passes all tests.

P.S.: I notice now that this is quite similar to @tsh's earlier answer.

P.P.S.: I've given up on this one; @tsh seems unbeatable.

Answer 11

TypeScript Types, 397 bytes

//@ts-ignore
type a<T,K=keyof T>=T extends T?keyof T extends K?T:never:0;type b<T,P,N>=T extends[N,...infer T]?T:[P,...T];type c<U,L=a<U>>=[...L,...a<U extends U?L extends U?never:U:0>]extends[{},{},...infer X]?X["length"]:0;type M<A,T=[],U=[],V=[],F=0,B=1,N=[]>=A extends[infer Z,...infer C]?Z extends N["length"]?M<C,U,V,T,B,F>:M<A,b<T,F,B>,b<U,B,F>,V,F,B,[...N,0]>:c<[...T,1]|[...U,2]|[...V,3]>

Try It Online!

Ungolfed / Explanation

// Filters a union of tuples for those with the shortest length
type Shortest<T, K = keyof T> = T extends T? keyof T extends K ? T : never : 0

// Increments numbers where e.g. 2 is represented as [Pos, Pos], 0 as [], and -3 as [Neg, Neg, Neg]
type Inc<T, Pos, Neg> =
  T extends [Neg, ...infer T]
    // If T is negative, remove one Neg from it
    ? T
    // Otherwise, add one Pos to T
    : [Pos, ...T]

type Main<Instructions, X = [], Y = [], Z = [], Pos=0, Neg=1, Travelled=[]> =
  Instructions extends [infer Distance, ...infer InstructionsTail]
    // If Instructions is non-empty
    ? Distance extends Travelled["length"]
      // If we've travelled the full distance of this instruction,
      // cycle XYZ, swap Neg & Pos (to reverse the sign of travel), and recurse
      ? Main<InstructionsTail, Y, Z, X, Neg, Pos>
      // Otherwise, increment X, decrement Y, and add one to Travelled
      : Main<Instructions, Inc<X, Pos, Neg>, Inc<Y, Neg, Pos>, Z, Pos, Neg, [...Travelled, 0]>
    // Otherwise, return the taxicab distance to our current position
    : Taxicab<[...X, 1] | [...Y, 2] | [...Z,3]>

// U will be passed in as [...X,1]|[...Y,2]|[...Z,3], so as to prevent merging in the union
type Taxicab<U, S = Shortest<U>> =
  // Concat the shortest with the second shortest and return their length - 2
  [...S, ...Shortest<U extends U ? S extends U ? never : U : 0>] extends [{}, {}, ...infer X] ? X["length"] : 0

Answer 12

Wolfram Language (Mathematica), 49 bytes

Max@Abs@{s=Fold[{#2-#[[2]],Tr@#}&,{0,0},#],Tr@s}&

Try it online!

A port of @tsh's answer. Make sure to upvote that answer as well!