12
\$\begingroup\$

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 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)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Suggested test case: ^^>>vv<^^ (1 correction). \$\endgroup\$
    – Yousername
    Dec 8 '21 at 1:40
  • 4
    \$\begingroup\$ Suggested testcase: ><<^<vv>>>>^^< : 2. It only has one duplicate cell in the original path. But it has to be corrected by 2 modifications. \$\endgroup\$
    – tsh
    Dec 8 '21 at 2:10

12 Answers 12

7
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ I'm not entirely sure if this is correct for all cases, since it's a recursive method (it seems to work for your six test cases in the TIO though). But since it looks like you're using the recursive method primarily as a loop and you always add C at the end of v, I think you can get rid of argument c for 113 bytes. \$\endgroup\$ Dec 8 '21 at 13:54
  • \$\begingroup\$ @KevinCruijssen It should be correct. Also, v[0] is a byte shorter than v[-1]. \$\endgroup\$
    – tsh
    Dec 9 '21 at 1:37
5
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ At first I was like, "heh, neat use of hamming distance builtin..." then I looked closer and realized there is no builtin being used! \$\endgroup\$
    – Jonah
    Dec 8 '21 at 1:27
2
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ If you change y so that it returns a dictionary, and then lookup into it outside the function calls, you can save 3 bytes: Try it online! \$\endgroup\$
    – pxeger
    Dec 8 '21 at 7:56
2
\$\begingroup\$

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())
}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ duplicated() -> table()>1 \$\endgroup\$ Dec 8 '21 at 14:03
  • \$\begingroup\$ 128 bytes by using the 'no-intersection' function from my (sadly much longer) R answer... \$\endgroup\$ Dec 8 '21 at 14:45
  • \$\begingroup\$ 124 bytes using colSums... \$\endgroup\$ Dec 8 '21 at 14:51
  • \$\begingroup\$ 123 by swapping !a[]=={} to a[]!={} \$\endgroup\$
    – Giuseppe
    Dec 8 '21 at 15:41
  • 1
    \$\begingroup\$ 121 bytes by using 5:8 in the brute-force paths and so removing the -4 later. \$\endgroup\$ Dec 8 '21 at 17:24
2
\$\begingroup\$

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!

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

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ -2 bytes (including one by changing rather arbitrary 100 to 99 (also arbitrary, but cheaper)). \$\endgroup\$
    – pajonk
    Dec 9 '21 at 19:42
  • \$\begingroup\$ @pajonk - Thanks! The 100 was indeed arbitrary, but thanks to you pointing it out (and the substr...sto= suggestion) the code ended-up 3 more bytes shorter! \$\endgroup\$ Dec 9 '21 at 23:26
1
\$\begingroup\$

Charcoal, 80 78 bytes

≔⟦⟦⁰ω⭆S⌕^>v<ι⟧⟧θFθ¿§ι²«F§ι¹✳⁻²⊗κ¹FI⌕AKVω⊞θ⟦⁺§ι⁰¬⁼ꧧ鲦⁰⁺§ι¹κ✂§ι²¦¹⟧⎚»⊞υ§ι⁰I⌊υ

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:

≔⟦⟦⁰ω⭆S⌕^>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.)

Fθ

Loop over all the positions.

¿§ι²«

If there are more steps to take:

F§ι¹✳⁻²⊗κ¹

Output the steps so far on to the canvas.

FI⌕AKVω

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.

I⌊υ

Output the minimum number of corrections needed.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Does your Levenshtein difference including deletion and insertion? For example, output for ><<^<vv>>>>^^<<^<<<vvvv>>>>>>^^^^<< should be 4 (according to my calculation). But its edit distance to <<^<vv>>>>^^<<^<<<vvvv>>>>>>^^^^<<^ is 2. \$\endgroup\$
    – tsh
    Dec 8 '21 at 9:28
  • 1
    \$\begingroup\$ calculation to above two test cases \$\endgroup\$
    – tsh
    Dec 8 '21 at 9:31
  • \$\begingroup\$ @tsh Yeah, the Levenshtein difference includes deletion/insertion.. :( If <<^<vv>>>>^^<<^<<<vvvv>>>>>>^^^^<<^ is a valid path for input ><<^<vv>>>>^^<<^<<<vvvv>>>>>>^^^^<<, it'll indeed result in 2. I'll delete for now and use a manual method to only check replacement, without deletion/insertion. \$\endgroup\$ Dec 8 '21 at 11:07
  • \$\begingroup\$ @tsh Should be fixed now at the cost of 6 bytes, by manually calculating the Hamming distance instead of using the Levenshtein distance builtin. Thanks for noticing! \$\endgroup\$ Dec 8 '21 at 11:15
0
\$\begingroup\$

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!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ you don't need "%4" because 1i**b is periodical \$\endgroup\$
    – G B
    Dec 8 '21 at 19:35
  • \$\begingroup\$ Indeed, thank you! I removed it from the application but left in initial mapping. \$\endgroup\$
    – lonelyelk
    Dec 8 '21 at 20:33
  • 1
    \$\begingroup\$ You can also initialize d with i.bytes inside the loop and delete b completely. \$\endgroup\$
    – G B
    Dec 8 '21 at 20:46
0
\$\begingroup\$

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.

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

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]>
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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