AoCG2021 Day 1: Automated delivery frenzy

Question

Originally from caird coinheringaahing's idea, I (Bubbler) am hosting Advent of Code Golf 2021.

On each day from today (Dec 1) until Christmas (Dec 25), a challenge will be posted at UTC midnight, just like an Advent calendar. It is a free-for-all and just-have-fun-by-participation event, no leaderboards and no prizes for solving them fast or solving them in the shortest code. More details can be found in the link above.

For this year's event, the challenge ideas were drawn from the previous AoC events (2015 - 2020).

---

The story continues from AoC2015 Day 3, Part 2.

---

Santa is delivering presents to an infinite two-dimensional grid of houses. He begins by delivering a present to the house at the starting location, and then follows the commands written as a sequence of moves ^>v< (moving to the neighboring house to the north, east, south, or west respectively), delivering a present at the house after each move.

Next year, Santa brings up a Robo-Santa for faster delivery. Santa and Robo-Santa start at the same location (giving two presents to the same house), and take turns to move based on the commands.

Assume the command is ^v^v^v^v^v. Santa alone would deliver a bunch of presents to only two houses (the start and its north neighbor), but with a Robo-Santa, they would deliver presents to 11 different houses (Santa moving north 5 times and Robo-Santa moving south 5 times).

Now Santa wonders: Given a sequence of instructions, how many Santas (Santa and any Robo-Santas) are needed to deliver presents to the maximum number of houses? If two or more Robo-Santas are present, Santa and the Robo-Santas will take turns cyclically to follow the commands, everyone stopping when the commands run out (the number of commands does not have to be divisible by the number of Santas). If multiple options are available, choose the smallest number of Robo-Santas (it takes time and money to build them).

Input: A nonempty string of ^>v< instructions.

Output: The minimum number of Santas in total for maximum delivery.

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

Test cases

>>>>> -> 1
(everyone moving to the same house is surely a loss)
^v^v^v^v^v -> 2
(one additional Robo-Santa will deliver to 11 different houses, the possible maximum)
v>^>v<^< -> 5
(5 Santas will deliver to 7 distinct houses;
 1, 3, 4, or 7 Santas will deliver to 6 distinct houses
 and other choices to fewer houses)
vv>^<^^<v> -> 1
(Any of 1, 4, 6, or 7 Santas will deliver to 8 distinct houses,
 but 1 is the best choice out of them)

Answer 1

TypeScript Types, 670 bytes

// @ts-ignore
type c<T,A=[]>=(((T extends T?(t:0)=>T:0)extends infer U?(U extends U?(u:U)=>0:0)extends(v:infer V)=>0?V:0:0)extends(_:0)=>infer W?c<Exclude<T,W>,[...A,0]>:A);type i<T>=T extends[0,infer X]?X:[1,T];type d<T>=T extends[1,infer X]?X:[0,T];type m<P,C>={"^":[i<P[0]>,P[1]],v:[d<P[0]>,P[1]],"<":[P[0],i<P[1]>],">":[P[0],d<P[1]>]}[C];type n<P,C>=[P[0]|m<P[1],C>,m<P[1],C>];type s<S,I>=I extends`${infer C}${infer I}`?S extends[infer A,...infer B]?s<[...B,n<A,C>],I>:0:c<S[number][0]>;type q=[[[],[]],[[],[]]];type M<S,K=S,B=[],BN=[],N=[q]>=K extends`${infer _}${infer K}`?B extends[...s<N,S>,...infer _]?M<S,K,B,BN,[...N,q]>:M<S,K,s<N,S>,N,[...N,q]>:BN["length"]

Try it online!

Answer 2

Pari/GP, 89 bytes

s->vecsort([-#Set(Vec(Ser([I^c|c<-Vec(Vecsmall(s))%11])/(1-x^i),#s+1))|i<-[1..#s]],,1)[1]

Try it online!

The ASCII codes of <^>v are[60, 94, 62, 118], which become [5, 6, 7, 8] when modulus 11.

After that, it is the usual power series tricks:

$$(a_0+a_1x+\cdots)/(1-x^k)=a_0+a_1x+\cdots+(a_0+a_k)x^k+(a_1+a_{k+1})x^{k+1}+\cdots$$

Answer 3

Rust, 239 234 bytes

|i|{let mut r=vec![];for l in 1..i.len(){let(mut s,mut v)=(vec![0;l*2],vec![(0,0)]);for c in i.bytes(){s[c as usize%3&1]+=1-(c as i64%5&2);v.push((s[0],s[1]));s.rotate_left(2);}v.sort();v.dedup();r.push((!v.len(),l));}r.sort();r[0].1}

Try it online!

Ungolfed:

    |i| {
        let mut r = vec![];
        for l in 1..i.len() {
            let (mut s, mut v) = (vec![0; l * 2], vec![(0, 0)]);
            for c in i.bytes() {
                s[c as usize % 3 & 1] += // %3 - bit 1 flips, s[0] or s[1]
                    1 - (c as i64 % 5 & 2); // %5 - bit 2 flips, 0 or 2
                v.push((s[0], s[1]));
                s.rotate_left(2);
            }
            v.sort();
            v.dedup();
            r.push((!v.len(), l)); // dirty negation to reverse tuple sort order
        }
        r.sort();
        r[0].1
    };

History:

• -5 by removing the type annotation for i (thanks @Aiden4)

Answer 4

Python 3.8 (pre-release), 111 bytes

lambda s:(L:=range(len(s)))[-max((len({0}|{sum(1j**(ord(d)%11)for d in s[j::~i])for j in L}),~i)for i in L)[1]]

Try it online!

Use %11 trick from alephalpha's answer.

Answer 5

APL (Dyalog Unicode), 39 bytes

⊃⍒{≢∪0,∊+⍀n ⍵⍴y↑⍨n×⍵}¨⍳n←≢y←0J1*'^<v'⍳⍞

Try it online!

y←0J1*'^<v'⍳⍞: Take character input and map the characters to complex numbers, storing the resulting vector in j.

 < >   ^    v
¯1 1 0J1 0J¯1

⍳n←≢y: Store the length of y in n and create a range from 1 to n (possible number of Santas)
{ ... }¨: For each number of Santas evaluate the a function which returns the number of houses visited.
⊃⍒: The first index of the maximal value. (Indices that would sort the vector descendingly; take the first one)

For the inner function ⍵ is the number of Santas to test and the other variables are still accessible.
y↑⍨n×⍵: Pad y to length n×⍵ by appending 0's.
n ⍵⍴: Reshape into a matrix with n columns and ⍵ rows.
+⍀: Get cumulative sums of the columns.
0,∊: Flatten and prepend a 0.
≢∪: Count the number of unique values.

Answer 6

Charcoal, 43 bytes

ＦＬθ«Ｆ⊕ι«Ｊ⁰¦⁰Ｆ✂θκＬθ⊕ι✳⊗⌕^>vλ¹*»⊞υＬＫＡ⎚»Ｉ⊕⌕υ⌈υ

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

ＦＬθ«

Loop over the length of the string, representing the number of Robo-Santas.

Ｆ⊕ι«

Loop over Santa and his Robo-Santas.

Ｊ⁰¦⁰Ｆ✂θκＬθ⊕ι✳⊗⌕^>vλ¹*

Draw the route this (Robo-)Santa takes, starting at the origin. (Would be -5 bytes for input in urdl format. Interestingly giving PolygonHollow its preferred urdl format would be 39 bytes, so slightly longer.)

»⊞υＬＫＡ

Save the count of all visited houses.

⎚

Clear the canvas ready for the next possible number of Robo-Santas or to output the result.

»Ｉ⊕⌕υ⌈υ

Find how many Robo-Santas are needed for the maximum possible count and add one for Santa himself.

Answer 7

05AB1E, 37 bytes

āει8ìS"^>v<"6ÅȇD8Ê>∞₆+çNè©sr.Λ®¢}Zk>

Try it online or verify all test cases.

Explanation:

ā                # Push a list in the range [1,input-length]
 ε               # Map over each of these integers:
  ι              #  Uninterleave the (implicit) input-string into this many parts,
                 #  resulting in the route of each individual (Robo-)Santa
   8ì            #  Prepend an 8 in front of each string
     S           #  Then convert it to a flattened list of characters
      "^>v<"     #  Push string "^>v<"
            6ÅÈ  #  Push list [0,2,4,6]
               ‡ #  Transliterate all "^" to 0; ">" to 2; etc.
  D              #  Duplicate this list of digits
   8Ê            #  Check for each that it's NOT equal to 8 (0 if 8; 1 otherwise)
     >           #  Increase each by 1 (1 if 8; 2 otherwise)
  ∞              #  Push an infinite positive list: [1,2,3,...]
   ₆+            #  Add 36 to each: [37,38,39,...]
     ç           #  Convert each to a character with this codepoint:
                 #  ["%","&","'",...]
      Nè         #  Index the map-index into this list
        ©        #  Store the character in variable `®` (without popping)
  sr             #  Rearrange the three values on the stack from a,b,c to b,c,a
    .Λ           #  Use the modifiable Canvas builtin with these three arguments
      ®¢         #  Count the amount of character `®` in the Canvas-string
 }Z              # After the map: push the max (without popping the list)
   k             # Get the first (0-based) index of this max
    >            # Increase it by 1 to make it 1-based
                 # (after which it is output implicitly as result)

In-depth step-by-step explanation:

(Uses input v>^>v<^< as example.)

1) āει: the ā results in the amount of (Robo-)Santas we want to check per iteration, and the ει will map this to routes per individual (Robo-)Santa:
Try just this step online.

2) 8ìS"^>v<"6Åȇ will convert these routes to something usable by the Canvas builtin.

The Canvas Builtin uses three arguments to draw a shape:

• Length of the lines we want to draw
• Character/string to draw
• The direction to draw in, where each digit represents a certain direction:

7   0   1
  ↖ ↑ ↗
6 ← X → 2
  ↙ ↓ ↘
5   4   3

And in addition there are a couple of special directions (+×8), for which we'll only use 8 in this program. 8 will reset the Canvas starting point.

So something like ["v>^",">v<","^<"] (three (Robo-)Santa routes) will with 8ìS"^>v<"6Åȇ translate to: [8,4,2,0,8,2,4,6,8,0,6].

Try the first two steps online.

3) Using what we created in step 2 as the directions-argument, D8Ê> for our lengths-argument, and ∞₆+çNè for the character we want to draw, we use the modifiable Canvas builtin .Λ.

With the example of the three (Robo-)Santa routes above, it'll have the following three arguments:

• Lengths: [1,2,2,2,1,2,2,2,1,2,2] (1 for every 8, 2 for every actual movement)
• Character: "'"
• Directions: [8,4,2,0,8,2,4,6,8,0,6]

Step 3.1: Draw 1 character at starting point 8:

'

Step 3.2: Draw 2-1 character in direction 4/↓:

'
'

Step 3.3: Draw 2-1 character in direction 2/→:

'
''

Step 3.4: Draw 2-1 character in direction 0/↑:

''
''

Step 3.5: Draw 1 character at starting point 8 again.

Step 3.6: Draw 2-1 character in direction 2/→:

''
''

Step 3.7: Draw 2-1 character in direction 4:/↓:

''
''

Step 3.8: Draw 2-1 character in direction 6/←:

''
''

Step 3.9: Draw 1 character at starting point 8 again.

Step 3.10: Draw 2-1 character in direction 0/↑:

'
''
''

Step 3.11: Draw 2-1 character in direction 6/←:

''
 ''
 ''

The reason we draw a different character every time and also have a leading 8 to reset to the starting point, is because there isn't any way to clear the Canvas. The next iteration we use the .Λ, it'll basically continue where it left off in the previous iteration. We therefore have to do an initial reset, and we draw all the characters on top of each other, which can be seen in the TIO below:

Try the first three steps online.

See this 05AB1E tip of mine for an in-depth explanation of the Canvas builtin.

4) ®¢}: count (¢) how many distinct houses all the (Robo-)Santa have visited, by checking how many times the current character (which we've saved in variable ®) is in the resulting Canvas-string.

Try the first four steps online.

5) Zk>: now that we have the amount of houses that can be visited depending on the amount of (Robo-)Santa going around doing their routes, we can get the maximum (Z) amount of houses visited, and get the first (1-based) index of this maximum (k>) to get the lowest amount of (Robo-)Santa necessary to achieve this maximum amount of visited houses, which will be output as our result.

Answer 8

Java, 349 bytes

s->{var p=new HashSet<String>();for(int i=s.length();i>0;i--){for(int j=0;j<i;j++){int x=0,y=0;p.add(i+","+x+","+y);for(int k=j;k<s.length();k+=i){int c=s.charAt(k)%11;var t=c==6?y++:(c==7?x++:(c==8?y--:x--));p.add(i+","+x+","+y);}}}int[]n=new int[s.length()];p.stream().map(a->a.substring(0,a.indexOf(','))).map(Integer::parseInt).forEach(i->n[i-1]++);int m=0,i=0;for(;i<n.length;i++){m=n[i]>n[m]?i:m;}return m+1;}

Try it online.

Explanation:

    s -> {
            var p = new HashSet<String>();                                  // using Hash-Set for built in distinct elements
            int h = s.length(), i = h, j, x, y, k, c, n[] = new int[h];     // setting up variables
            for (; i > 0; i--)                                              // loop for possible Santas
                for (j = 0; (k = j++) < i;)                                 // loop every Santa
                    for (p.add(i + ",0," + (x = y = 0)); k < h; k += i) {   // add starting position and loop Santa over moves
                        c = (c = s.charAt(k) % 11) == 6 ? y++ : c == 7 ? x++ : c == 8 ? y-- : x--;
                        p.add(i + "," + x + "," + y);                       // change position and add it
                    }
            for (p.stream()                                                 //
                    .map(a -> a.substring(0, a.indexOf(44)))                // only look at Santas number for each house
                    .map(Integer::parseInt)                                 //
                    .forEach(I -> n[I - 1]++); h-- > 0;)                    // add visited Houses together
                i = n[h] > n[i] ? h : i;                                    // finding the index of the greatest element
            return -~i;                                                     // negate and bit-flip
        }

Improvements:

• -37 bytes: Using var where possible and changing switch-case statement to tenary operators
• -1 byte: treating chars as int and using alephalpha's modulo-trick
• -2 bytes: spaces
• -66 bytes: thanks to ceilingcat (learned some java magic I wasn't aware of)

What I learned (as I never coded a challenge befor nor golfed code):

• Java is a horrible language to golf (but I'm not good enough in other languages... so ¯\(ツ)/¯ )
• I am far to slow to be competetiv in this AoCG-thing...

Answer 9

Python, 134 bytes

k,*t,x=input(),1
for _ in k:
    p=[0]*x;q={0}
    for c in k:n=p.pop(0)+1j**(ord(c)%11);p+=n,;q|={n}
    t+=(-len(q),x),;x+=1
print(min(t)[1])

Attempt This Online!

-21 bytes by stealing alephalpha's codepoint mapping trick.
-11 bytes thanks to pxeger

Answer 10

Ruby, 121 ... 93 bytes

->s{a=0;q=s.bytes;q.map{[-((*w=[0i]*a+=1)|q.map{|y|w.rotate![0]+=1i**y%=19}).size,a]}.min[1]}

Try it online!

Answer 11

Wolfram Language (Mathematica), 98 bytes

-5 bytes thanks to @att.

Ordering[i=1;s=I^ToCharacterCode@#~Mod~11;0Union@@Accumulate@Partition[s,i,i++,{i,1},0]-i&/@s,-1]&

Try it online!

Answer 12

J, 44 bytes

1+0{[:\:[:([:#@~.@,+/\)"2-@#\]\0j1^'>^<v'&i.

Try it online!

-3 after stealing a trick from ovs's APL answer. Explanation is similar to ovs's.

My other attempt used key rather than column sums for simulating the multiple robots:

1+0{[:\:[:#@~.@,"2(#\|/#\)+/\/."#.0j1^'>^<v'&i.

Answer 13

BQN, 56 bytes

{1+⊑⍒((∾⟜-1∾≠𝕩)⊏˜">v<"⊐𝕩)⊸{≠⍷∾{+`0∾𝕩}¨𝕨⊔˜(≠𝕨)⥊↕𝕩}¨1+↕≠𝕩}

Try It!

BQN is the Language of The Month for December!

Answer 14

Jelly, 19 bytes

O%11sJµZı*Ż€ÄFQL)MḢ

A monadic Link accepting a list of characters which yields an integer, the optimal number of Santas.

Try it online!

Answer 15

Clojure, 259 bytes

(let[s(read-line)](print(first(reduce(fn[[a b][c d]](if(< b d)[c d][a b]))(for[i(range 1(inc(count s)))][i(count(set(mapcat #(reductions(fn[[x y]m](case m\^[x(dec y)]\>[(inc x)y]\v[x(inc y)]\<[(dec x)y]))[0 0]%)(for[j(range i)](take-nth i(drop j s))))))])))))

Try it online!

Ungolfed:

(let [s (read-line)]
  (print
   (first
    (reduce
     (fn [[a b] [c d]] (if (< b d) [c d] [a b]))
     (for [i (range 1 (inc (count s)))]
       [i (count
           (set
            (mapcat
             #(reductions
               (fn [[x y] m]
                 (case m
                   \^ [x (dec y)]
                   \> [(inc x) y]
                   \v [x (inc y)]
                   \< [(dec x) y]))
               [0 0] %)
             (for [j (range i)]
               (take-nth i (drop j s))))))])))))

Commented, slightly longer version using threading:

(let [s (read-line)]
  (->>
   (for [i (range 1 (inc (count s)))]  ; Create a list of number of houses covered by 1..n (Robo-)Santas (n = length of instruction):
     [i (->>                           ;  for example, for ">>>>>" => ([1 6] [2 4] [3 3] [4 3] [5 2])
         (for [j (range i)]            ;  - split commands for i (Robo-)Santas:
           (take-nth i (drop j s)))    ;    for example, for "^v^v^v^v^v" with 2 (Robo-Santas) => ((\^ \^ \^ \^ \^) (\v \v \v \v \v))
         (mapcat                       ;  - provide a list of all houses covered with a command (splitted to commands for each (Robo)-Santa):
          #(reductions                 ;    for example, for "^v^v^v^v^v" with 2 (Robo-Santas) => ([0 0] [0 -1] [0 -2] [0 -3] [0 -4] [0 -5] [0 0] [0 1] [0 2] [0 3] [0 4] [0 5])
            (fn [[x y] m]              ;      - given a house of position [x y] and move command m:
              (case m \^ [x (dec y)]   ;         move to [x y-1]
                      \> [(inc x) y]   ;         move to [x+1 y]
                      \v [x (inc y)]   ;         move to [x y+1]
                      \< [(dec x) y])) ;         move to [x-1 y]
            [0 0] %))                  ;      - start from house [0 0] and work moves from there
         set                           ;  - convert the list to a set to remove duplicate houses
         count)])                      ;  - count number of houses in the set
   (reduce                             ; From the list created above, pick the best option
    (fn [[a b] [c d]]                  ;  for example, for ">>>>>", the list ([1 6] [2 4] [3 3] [4 3] [5 2]) => [1 6]
      (if (< b d) [c d] [a b])))       ;  - compare number of houses, returning first if the number is same (less (Robo-)Santas is better)
   first                               ; Extract number of (Robo-)Santas from the best option
   print))

Answer 16

JavaScript (ES6), 130 bytes

Expects an array of characters.

This is using reduce() ... because why not.

a=>a.reduce(r=>(n++,v=new Set(a.map(o=(c,i)=>o[i%=n]=~~o[i]+({'>':1,'<':-1,v:q=a.length}[c]||-q))).add(0).size)>m?(m=v,n):r,n=m=0)

Try it online!

Commented

a =>                          // a[] = array of characters
a.reduce(r =>                 // reduce a[] using r as the accumulator:
  (                           //
    n++,                      //   increment n
    v = new Set(              //   define v as the size of this set:
      a.map(o = (c, i) =>     //     for each char. c at position c in a[]:
        o[i %= n] =           //       reduce i modulo n
          ~~o[i] + (          //       coerce o[i] to an integer and add:
            { '>': 1,         //         +1 if c = '>'
              '<': -1,        //         -1 if c = '<'
              v: q = a.length //         +a.length if c = 'v'
            }[c]              //
            || -q             //         -a.length if c = '^'
          )                   //
      )                       //     end of map()
    )                         //   end of Set()
    .add(0)                   //   add the starting position 0
    .size                     //   get the final size of the set
  ) > m ?                     //   if v is greater than m:
    (m = v, n)                //     update m to v and r to n
  :                           //   else:
    r,                        //     leave r unchanged
  n = m = 0                   //   start with r = n = m = 0
)                             // end of reduce()

Answer 17

R, 134 bytes

function(v)which.max(Map(function(x)sum(unique(c(0,unlist(Map(function(i)cumsum(d[y==i]),y<-1:x))))|T),seq(d<-1i^(utf8ToInt(v)%%11))))

Try it online!