AoCG2021 Day 8: Delivery Corrections

Question

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. 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. Moves are always exactly one house to the north ^, south v, east >, or west <.

However sometimes the notes giving the path have a few mistakes. Your job is to write a program that figures out how to correct these mistakes. We can't know exactly what mistakes were made but we do know that no house should ever receive more than 1 present. So we will just correct paths so that no house is visited more than once.

To correct a path we substitute a step with a different step. For example >^<v can be corrected to >^>v. Since we don't want to over-correct too much we will make the minimal number of corrections we can while reaching the desired result.

Task

Given a string representing directions output the minimal number of corrections required before it visits no house more than once.

This is code-golf so answers will be scored in bytes.

Test cases

>>v>>>vvv<<<^<v : 0
>>>>>><<<<<<< : 1
^^>>vv<< : 1
><> : 1
><>< : 2
^<v>^<v> : 2
^^>>vv<^^ : 1  (suggested by Yousername)
><<^<vv>>>>^^< : 2  (suggested by tsh)

Answer 1

Python 3, 110 bytes

f=lambda a,v=[0],l=1:a and min(f(a[1:],[v[0]+1j**(ord(d)%11)]+v,l+1)+(a[0]!=d)for d in'^>v<')or(l-len({*v}))*l

Try it online!

Simply find out all valid path with same length. Seems to be \$O\left(4^n\right)\$. And it will timeout for any (not so) large inputs. Yet another mod 11 trick from previous days.

Thanks Kevin Cruijssen for -6 bytes.

Answer 2

Pari/GP, 118 bytes

s->i=#s;forvec(v=[[0,3]|k<-l=Vec(Vecsmall(s))%11],#Set(Vec(Ser([I^c|c<-l+v])/(1-x),m=#l+1))-m||i=min(i,#[1|a<-v,a]));i

Try it online!

Very slow. Loops over all the commands with the given length, filters out the correct ones, and finds the minimal Hamming distance.

Answer 3

Python3, 291 bytes:

y=lambda j,n,m:{'v':(n-1,m),'>':(n,m+1),'<':(n,m-1),'^':(n+1,m)}[j]
f=lambda p,s=(0,0),c=[(0,0)],l=[]:0 if not p else(k:=((r:=y(p[0],*s))in c))+(min(f(j+p[1:],[r,s][k],c+[[s],[]][k],l+[p[0]])for j in g)if(g:=[[''],[u for u in'v<>^'if y(u,*s)not in c]][k])else f(l.pop()+p[1:],c[-1],[r]+c,l))

A rather unelegant solution, but non-brute force, with basic backtracking.

Try it online!

Answer 4

Rust, 304 bytes

|i:&str|{fn d(v:&mut Vec<[i64;2]>,c:&[u8])->u64{b"^v<>".iter().take(c.len()*4).map(|i|{let mut x=v[v.len()-1].to_owned();x[*i as usize%3&1]+=1-(*i as i64%5&2);if v.contains(&x){u64::MAX-1}else{v.push(x);let r=(*i!=c[0])as u64+d(v,&c[1..]);v.pop();r}}).min().unwrap_or(0)}d(&mut vec![[0,0]],i.as_bytes())}

Try it online!

I really need some tricks that'd let me use closures recursively.

Nothing clever going on here, just brute forcing every possible move.

Ungolfed:

|i: &str| {
    fn deliver(visited: &mut Vec<[i64; 2]>, cmds: &[u8]) -> u64 {
        b"^v<>"
            .iter()
            .take(cmds.len() * 4) // stop if cmds is empty
            .map(|i| {
                let mut new = visited[visited.len() - 1].to_owned();
                new[*i as usize % 3 & 1] += 1 - (*i as i64 % 5 & 2); // same trick as day 1
                if visited.contains(&new) {
                    u64::MAX - 1
                } else {
                    visited.push(new);
                    let result = (*i != cmds[0]) as u64 + deliver(visited, &cmds[1..]);
                    visited.pop();
                    result
                }
            })
            .min()
            .unwrap_or(0)
    }
    deliver(&mut vec![[0, 0]], i.as_bytes())
}

Answer 5

R, 168 ... 121 bytes

Or R>=4.1, 107 bytes by replacing two function occurrences with \s.

-many bytes thanks to @Dominic van Essen and @Giuseppe.

function(s,a=combn(rep(5:8,l),l<-sum(s|1)))min(colSums(a[,apply(a,2,function(x)all(table(c(0,cumsum(1i^x)))<2))]!=s%%11))

Try it online!

More AoC than AoCG, but I'm posting to get things going here in R. The golf appeared thanks to @Dominic van Essen and @Giuseppe.

Input as a vector of character codes.

Brute force solution - generates all paths of length equal to input's length, checks which are valid (no intersections) and returns where the difference to input is minimal.

Go check also @Dominic's non-brute-force solution.

Answer 6

Ruby, 140 ... 120 bytes

->s{(0..k=s.size*4).find{|w|(0..k**w).any?{|q|z=s.bytes;w.times{z[q%k/4]=q;q/=k};([a=0i]|z.map{|x|a+=1i**x%=19})[k/4]}}}

Try it online!

Answer 7

R, 202 197 bytes

Edit: -5 bytes thanks to bug-spotting & suggestions from pajonk

f=function(s,n=0,`[`=sapply)`if`(any(s[function(x)all(table(c(0,cumsum(1i^(utf8ToInt(x)%%11))))<2)]),n,f(s[function(x)outer(1:(l=nchar(x)),c("^",">","v","<"),Vectorize(`substr<-`),x=x,sto=l)],n+1))

Try it online!

Already outgolfed by pajonk, but posting to keep things going here in R...

Non-brute-force solution, recursively makes increasing numbers of edits until a solution is found.

Answer 8

Charcoal, 80 78 bytes

≔⟦⟦⁰ω⭆Ｓ⌕^>v<ι⟧⟧θＦθ¿§ι²«Ｆ§ι¹✳⁻²⊗κ¹ＦＩ⌕ＡＫＶω⊞θ⟦⁺§ι⁰¬⁼ꧧ鲦⁰⁺§ι¹κ✂§ι²¦¹⟧⎚»⊞υ§ι⁰Ｉ⌊υ

Try it online! Link is to verbose version of code. Brute force so each extra input character slows the code down by a factor of about 3. Explanation:

≔⟦⟦⁰ω⭆Ｓ⌕^>v<ι⟧⟧θ

Start a breadth first search of all positions with the same length as the input with no corrections yet, no steps taken, and the input converted into the desired path in a nicer format for Charcoal. (Even switching to urdl input would save 5 3 bytes.)

Ｆθ

Loop over all the positions.

¿§ι²«

If there are more steps to take:

Ｆ§ι¹✳⁻²⊗κ¹

Output the steps so far on to the canvas.

ＦＩ⌕ＡＫＶω

Loop through available directions.

⊞θ⟦⁺§ι⁰¬⁼ꧧ鲦⁰⁺§ι¹κ✂§ι²¦¹⟧

Increment the number of corrections if this step wasn't the desired step, and save that with the augmented list of steps taken and suffixed list of desired steps to the search list.

⎚

Clear the canvas ready for the next position or the result.

»⊞υ§ι⁰

Otherwise, save the number of corrections.

Ｉ⌊υ

Output the minimum number of corrections needed.

Answer 9

05AB1E, 43 bytes

">^<v"©Igãʒ2Å0šÅ»®¦®¨‚sδkY0:+}DÙQ}.Lß

Brute-force approach. Generates all possible command-paths of the given input-length using the cartesian product, filters to keep paths where all visited houses are unique, calculates the Hamming difference of each remaining path with the input, and outputs the smallest one.

Try it online or verify some of the smaller inputs.

Explanation:

">^<v"            # Push string ">^<v"
      ©           # Store it in variable `®` (without popping)
       Ig         # Push the input-length
         ã        # Get the cartesian product to generate all possible paths of a
                  # length equal to the input
ʒ                 # Filter this list of paths by:
 2Å0              #  Push [0,0]
    š             #  Implicitly convert the path to a list of characters, 
                  #  and prepend the [0,0]
     Å»           #  Cumulative left-reduce:
       ®¦         #   Push `®` minus its first character: "^<v"
       ®¨         #   Push `®` minus its last character: ">^<"
         ‚        #   Pair them together: ["^<v",">^<"]
          s       #   Swap so the current character of the reduce is at the top
           δ      #   Map over the pair using this character as argument:
            k     #    Get its 0-based index (or -1 if it isn't present)
             Y0:  #   Replace the 2 with a 0
                + #   Add it to the current coordinate-pair
      }DÙQ        #  After the reduce, check if all coordinates are unique:
       D          #   Duplicate the list of integer-pairs
        Ù         #   Uniquify it
         Q        #   Check if the list of integer-pairs are still the same
}εø€Ë_O}          # After the filter, calculate the Hamming distance of each
                  # remaining path with the (implicit) input:
 ε     }          #  Map over each remaining path:
  ø               #   Create character-pairs with the (implicit) input-string at
                  #   the same positions
   €Ë_            #   For each pair: check that they are NOT the same
      O           #   Sum to get the amount of differences
        ß         # Pop and push the minimum
                  # (after which it is output implicitly as result)

Minor note: ®¦®¨‚sδkY0: will result in [[-1,0],[0,1],[1,0],[0,-1]] for >^<v respectively. So the >/< travel in the opposite direction: > travels towards the left and < towards the right. This is irrelevant for calculating the result however.

Answer 10

TypeScript Types, 450 bytes

//@ts-ignore
type a<T,A=1,B=0>=T extends[A,...infer X]?X:[B,...T];type b<S,P=[[],[]],V=0>=P extends V?0:S extends`${infer A}${infer S}`?b<S,{">":[a<P[0]>,P[1]],"<":[a<P[0],0,1>,P[1]],v:[P[0],a<P[1]>],"^":[P[0],a<P[1],0,1>]}[A],P|V>:1;type c<S,N,T="",O="v"|"^"|"<"|">">=N extends[0,...infer M]?S extends`${infer C}${infer R}`?O extends C?c<R,N,`${T}${C}`>:c<R,M,`${T}${O}`>:never:`${T}${S}`;type M<S,N=[]>=1 extends b<c<S,N>>?N["length"]:M<S,[...N,0]>

Try It Online!

Ungolfed / Explanation

// Increments a number represented where e.g. 2 is [Pos, Pos], 0 is [], and -1 is [Neg]
type Inc<T, Neg=1, Pos=0>=T extends[Neg,...infer X]?X:[Pos,...T];
// Decrements
type Dec<T>=Inc<T,0,1>

// Returns 1 if Str is valid, or 0 otherwise
// Implicitly maps over unions in Str
// Visited is a union of positions; it's initialized to 0 instead of never for byte-saving
type Check<Str, Pos = [[], []], Visisted = 0>=
  Pos extends Visisted
    // If Pos is in Visisted, return 0
    ? 0
    // Otherwise, take the first character of Str
    : Str extends `${infer Dir}${infer Rest}`
      ? Check<
        Rest,
        // Move Pos according to Dir
        {
          ">": [Inc<Pos[0]>, Pos[1]],
          "<": [Dec<Pos[0]>, Pos[1]],
          "v": [Pos[0], Inc<Pos[1]>],
          "^": [Pos[0], Dec<Pos[1]>],
        }[Dir],
        // Add Pos to Visited
        Pos | Visisted
      >
      // Str is empty; the string is valid
      : 1

// Return all strings where N characters are mutated
type MutateN<Str, N, Acc="", Chars = "v" | "^" | "<" | ">"> =
  N extends [0, ...infer M]
    // If N > 0, get the first character of Str
    ? Str extends `${infer Char}${infer Rest}`
      // Map over the Chars union:
      ? Chars extends Char
        // If this element of Chars is Char, don't mutate this character
        ? MutateN<Rest, N, `${Acc}${Char}`>
        // Otherwise, mutate this character and decrement N
        : MutateN<Rest, M, `${Acc}${Chars}`>
      // Str is empty, so we can't mutate N more characters; return never
      : never
    // Otherwise, return Acc + Str
    :`${Acc}${Str}`

type Main<Str, N=[]> =
  1 extends Check<MutateN<Str, N>>
    // If any of the strings where N chars are mutated are valid, return N
    ? N["length"]
    // Otherwise, check N + 1
    :Main<Str, [...N, 0]>

Answer 11

Ruby, 197 194 192 187 bytes

->i{c=[0]*(s=i.size);loop{*a=0i;b=i.bytes.map{|b|b%13};(c|c).map{|c|b[c/4]+=c};b.map{|b|a<<a[-1]+1i**b};a==a|a&&break;c[0]+=1;s.times{|j|c[j]/4>=s&&c[j,2]=[0,c[j+1]+1]}};c.count{|c|c!=0}}

Array c represents possible changes. Each element — one change such that c[...] / 4 is the position and c[...] % 4 is the change itself. The algorithm increments elements in the array until it finds the array that makes positions stay unique. Theoretical maximum of errors is the size of input.

Positions are represented by the array a of complex numbers. Conveniently 1i ** N represents rotation, so we can just add complex numbers and push them to the array to see the path.

The trick with b%13 as to have a rotating order of pointers («<>^v» is bad but «^>v<» is good). mod 13 makes it so that:

"<v>^".bytes.map { |b| b % 13 % 4 } == [0, 1, 2, 3]

Examples added to the TIO. Thanks to G B for help!

Try it online!

Answer 12

Wolfram Language (Mathematica), 107 bytes

-Max[Count@4/@Select[Tuples[Range@4,l=Length[s=ToCharacterCode@#~Mod~11]],0!=##&@@Accumulate[I^(s+#)]&]]+l&

Try it online!

There is a built-in for Hamming distance, but its name is HammingDistance, much longer than calculating it manually.