9
\$\begingroup\$

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

The story continues from AoC2018 Day 3.

But you're not Bubbler, you're Lyxal! yeah, I know.


After a long period of chaos, the Elves have finally agreed on how to cut the fabric. Unfortunately, the next day they have come up with how to utilize the leftovers - make a super long present wrapping strip. Well, if it can shrink Santa, it might be able to shrink presents as well...

The description of the strip is a string of ODCF, which happens to be the first letters of "up down left right" in Elvish (totally not this Elvish). Divide the fabric into a grid of 1cm × 1cm square cells, select a starting cell somewhere in the middle, and then move around according to the description to claim the strip.

So if the string is OOCOFFFDD, you would get this strip, starting at X:

OFFF
CO.D
.O.D
.X..

... Except that the strip the Elves gave to you is self-intersecting, so it simply doesn't work (a 1cm² fabric part doesn't magically become 2cm² - well, it's physics, at least until Santa comes).

Given the string OOCOFFFDDCCCD, the ? is where the strip self-intersects:

OFFF
CO.D
C?CD
DX..

In order to avoid the ? cell becoming a problem, you can take its substring (a contiguous part of the given string) in two ways: OOCOFFFDDC (cutting away the last 3 chars) and COFFFDDCCCD (cutting away the first 2 chars) gives, respectively,

OFFF
CO.D
.OCD
.X..

OFFF
CX.D
CCCD
D...

Among the two and all the other options, the latter of the two above is the longest possible.

Given a nonempty string of ODCF, determine the length of its longest substring out of which you can make a valid (non-self-intersecting) strip. Assume the fabric leftover is large enough to cover any valid substring of the input.

Standard rules apply. The shortest code in bytes wins.

Test cases

C -> 1
ODD -> 2 (DD)
OOCOFFFDD -> 9 (whole input)
OOCOFFFDDCCCD -> 11 (whole input minus first 2)
OOOFFDCCCDFFFDCOOO -> 12 (minus first 3 and last 3)
\$\endgroup\$

11 Answers 11

5
\$\begingroup\$

TypeScript Types, 537 bytes

//@ts-ignore
type a<T,P=0,N=[1,0][P]>=T extends[N,...infer T]?T:[...T,P];type b<T>=T extends{[K in keyof T]:{[L in keyof T]:K extends L?0:T[K]extends T[L]?T:0}[number]}[number]?never:T;type c<T>=T extends[{},...infer U]?T|c<U>:T;type d<T>=T extends[...infer U,{}]?T|d<U>:T;type e<T,K=T extends T?keyof T:0>=T extends T?[K]extends[keyof T]?T:never:0;type f<S,A=[],P=[[],[]],B=[...A,P],X=P[0],Y=P[1]>=S extends`${infer C}${infer R}`?f<R,B,{O:[X,a<Y>],D:[X,a<Y,1>],F:[a<X>,Y],C:[a<X,1>,Y]}[C]>:B;type M<T>=a<e<b<c<d<f<T>>>>>,1,{}>["length"]

Try It Online!

Ungolfed / Explanation

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

// Filters a union of tuples for those with no duplicate elements
type FilterNoDuplicates<T> =
  // Map over the union T
  T extends
    {
      // Map over the tuple T
      [K in keyof T]: {
        // Map over the tuple T
        [L in keyof T]:
          // If K != L and T[K] == T[L], return T
          K extends L ? 0 : T[K] extends T[L] ? T : 0
      }[number] 
    }[number]
      // If any returned T, omit T from the union
      ? never
      // Otherwise, keep T in the union
      : T

// Get all prefixes of T as a union (e.g. [1,2,3] -> [] | [1] | [1,2] | [1,2,3])
type Prefixes<T> = T extends [{}, ...infer U] ? T | Prefixes<U> : T

// Get all suffixes of T as a union (e.g. [1,2,3] -> [] | [3] | [2,3] | [1,2,3])
type Suffixes<T> = T extends [...infer U, {}] ? T | Suffixes<U> : T

// Filter a union of tuples, T, for those with the maximum length
type Longest<T, K = T extends T ? keyof T : 0> = T extends T ? [K] extends [keyof T] ? T : never : 0

// Convert a path like "ODCF" to its path (a list of pairs of integers, starting with (0,0))
type GetPath<
  Str,
  // The current path, not including the current position
  Path = [],
  // The current position
  Pos = [[],[]],
  // Aliases
  NewPath = [...Path, Pos],
  Pos0 = Pos[0],
  Pos1 = Pos[1]
> =
  // Get the first character of Str
  Str extends `${infer Char}${infer Rest}`
    // Recurse
    ? GetPath<
      // Set Str to Rest
      Rest,
      // Set Path to NewPath
      NewPath,
      // Update Pos based on Char
      {
        O: [Pos0, Inc<Pos1>],
        D: [Pos0, Inc<Pos1, 1>],
        F: [Inc<Pos0>, Pos1],
        C: [Inc<Pos0,1>, Pos1]
      }[Char]
    >
    // Str is empty
    : NewPath

// Convert Str to a path, find all subpaths, filter the subpaths
// for no duplicates, find the longest, return its length minus 1
type Main<Str> = Inc<Longest<FilterNoDuplicates<Prefixes<Suffixes<GetPath<Str>>>>>,1,{}>["length"]
\$\endgroup\$
1
  • 1
    \$\begingroup\$ ah yes Typescript's typing system - the perfect language for AoCG ;p \$\endgroup\$
    – lyxal
    Dec 18 '21 at 1:50
5
\$\begingroup\$

Python 3.8 (pre-release) 106, 103 (@pxeger), 96 (@ovs), 89, 84 bytes

lambda s,*i,x=0:max(len(i:=[x,*i[:[*i,x:=x+1j**"CDF".find(j)].index(x)]])for j in s)

Try it online!

Older versions

lambda s,i=[0],x=0:max(len(i:=[x:=x+1j**"CDF".find(j)]+i[:(i+[x]).index(x)])for j in s)-1

Try it online!

lambda s,i=[0],x=0:max(len(i:=i[(x:=x+1j**"CDF".find(j))in i and-~i.index(x):]+[x])for j in s)-1

Try it online!

x=m=0;i=[]
for j in input():
 i+=x,;x+=1j**"CDF".find(j)
 while x in i:_,*i=i
 m=max(m,len(i))
print(m)

Try it online!

x=m=0;i=[]
for j in input():
 i+=[x];x+=1j**"CDF".find(j)
 while x in i:i.pop(0)
 m=max(m,len(i))
print(m)

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ i+=[x] -> i+=x,; i.pop(0) -> _,*i=i \$\endgroup\$
    – pxeger
    Dec 18 '21 at 9:46
  • \$\begingroup\$ while x in i:_,*i=i can be rewritten as i=i[x in i and-~i.index(x):], which is longer, but with throwing a lot of Python 3.8 at it gets to 99 bytes (And 96 as a lambda function) \$\endgroup\$
    – ovs
    Dec 18 '21 at 10:09
3
\$\begingroup\$

Charcoal, 32 bytes

FLθ«F✂θιF¬℅KK✳⊗⌕FOCκ¹ψ⊞υLKA⎚»I⌈υ

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

FLθ«

Loop over each suffix.

F✂θι

Loop over the characters in the suffix.

F¬℅KK

Stop if the strip self-intersects.

✳⊗⌕FOCκ¹

Mark the current cell as part of the strip and move to where the next cell should be.

ψ

Ensure that the final cell is not part of the strip. This will remove the wrong cell if the strip self-intersected but only the count matters.

⊞υLKA

Record the number of cells marked as part of the strip.

Clear the canvas ready for the next suffix or to output the result.

»I⌈υ

Output the maximum possible strip length found.

\$\endgroup\$
3
\$\begingroup\$

BQN, 40 35 bytesSBCS

⌈´·{⊑/¬«∊+`<˘»⍉¬4|31‿37|⌜9×@-𝕩∾@}¨↓

Run online!

BQN doesn't support complex numbers yet, which means the directions have to be encoded as tuples by <˘⍉¬4|31‿37|⌜9×@-𝕩:

⟨ 'O' ⟨ ¯1 0 ⟩ ⟩ ⟨ 'D' ⟨ 1 0 ⟩ ⟩ ⟨ 'C' ⟨ 0 ¯1 ⟩ ⟩ ⟨ 'F' ⟨ 0 1 ⟩ ⟩

We iterate over the suffixes , and get the length of the longest unique prefix of each. The maximum of that is the result.

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

Pari/GP, 98 bytes

s->vecmax([vecmin([#[1|k<-[j..p=#s+a=0],p*=a+=I^(Vecsmall(s)[k]%69)]+j-i|j<-[i..#s]])|i<-[1..#s]])

Try it online!

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

Python, 99 bytes

f=lambda a,B=1,c=0,*v:a>""and max(B*f(a[1:]),~f(a[1:],0,r:=c+1j**'OCD'.find(a[0]),*v,c)*~-(r in v))

Attempt This Online!

Tricks:

  • a>"" is the same as bool(a), since strings are compared lexicographically, and can be used as a recursive base-case because it returns 0 when a is empty, unlike simply a and
  • a>"" is a sufficient base-case to prevent infinite recursion, which allows shorter conditionals later on because they're allowed to be strictly evaluated (mostly using *, and the fact that the output is always positive so we can happily pass 0 to max)
  • ~X*~-Y = -~X*-~-Y = (1+X)*(1-Y) = (1+X)*(not Y)
  • With the help of the flag variable B, I combine the loops searching for the shortest substring into one recursive function
\$\endgroup\$
2
\$\begingroup\$

Rust, 150 bytes

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

Try it online!

Ungolfed:

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

Python3, 195 bytes:

f=lambda d,x,y:{'O':(x+1,y),'C':(x,y-1),'D':(x-1,y),'F':(x,y+1)}[d]
g=lambda s,p=(0,0),q=[]:0 if not s or(n:=f(s[0],*p))in q else g(s[1:],n,q+[p])+1
r=lambda x:max(g(x[i:])for i in range(len(x)))

Try it online!

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

JavaScript (Node.js), 108 bytes

f=a=>Math.max(a&&f(a.slice(1)),Buffer(a).some(g=c=>g[g[[x,y]]=[x+=(c=c%13%5-2)%2,y+=~c%2]]||!++t,t=x=y=0),t)

Try it online!

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

Ruby, 88 86 bytes

->s{*l=z=0;s.chars.map{|c|l<<z+=1i**"OCDF".index(c);_,*l=l while l!=l|l;l.size}.max-1}

Try it online!

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

Wolfram Language (Mathematica), 89 bytes

Max[s=Subsequences;Length/@Select[s[I^ToCharacterCode@#~Mod~69],FreeQ[Tr/@Rest@s@#,0]&]]&

Try it online!

\$\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.