AoCG2021 Day 18: Stripping Strips

Question

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 code-golf 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)

tjjfvi · Accepted Answer · 2021-12-18 01:30:42Z

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"]

ah yes Typescript's typing system - the perfect language for AoCG ;p — lyxal, Dec 18, 2021 at 1:50

loopy walt · Accepted Answer · 2021-12-18 13:40:50Z

5

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!

edited Dec 18, 2021 at 13:40

answered Dec 18, 2021 at 9:37

loopy walt

14.3k2 gold badges8 silver badges60 bronze badges

\$\begingroup\$ i+=[x] -> i+=x,; i.pop(0) -> _,*i=i \$\endgroup\$
– pxeger
Dec 18, 2021 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, 2021 at 10:09

Add a comment |

Neil · Accepted Answer · 2021-12-18 06:01:27Z

Charcoal, 32 bytes

ＦＬθ«Ｆ✂θιＦ¬℅ＫＫ✳⊗⌕FOCκ¹ψ⊞υＬＫＡ⎚»Ｉ⌈υ

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

ＦＬθ«

Loop over each suffix.

Ｆ✂θι

Loop over the characters in the suffix.

Ｆ¬℅ＫＫ

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.

⊞υＬＫＡ

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

⎚

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

»Ｉ⌈υ

Output the maximum possible strip length found.

ovs · Accepted Answer · 2021-12-18 14:31:04Z

3

BQN, 40 35 bytes^SBCS

⌈´·{⊑/¬«∊+`<˘»⍉¬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.

edited Dec 18, 2021 at 14:31

answered Dec 18, 2021 at 12:38

ovs

56.8k3 gold badges42 silver badges150 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2021-12-18 00:37:31Z

2

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!

edited Dec 18, 2021 at 0:37

answered Dec 18, 2021 at 0:15

alephalpha

41.9k7 gold badges53 silver badges157 bronze badges

Add a comment |

pxeger · Accepted Answer · 2021-12-18 10:11:03Z

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

Ezhik · Accepted Answer · 2021-12-18 11:40:38Z

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()
}

alephalpha · Accepted Answer · 2021-12-20 01:36:41Z

2

Wolfram Language (Mathematica), 89 bytes

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

Try it online!

answered Dec 20, 2021 at 1:36

alephalpha

41.9k7 gold badges53 silver badges157 bronze badges

Add a comment |

Ajax1234 · Accepted Answer · 2021-12-18 00:50:39Z

1

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!

answered Dec 18, 2021 at 0:50

Ajax1234

5,7631 gold badge13 silver badges26 bronze badges

Add a comment |

Arnauld · Accepted Answer · 2021-12-18 15:15:25Z

1

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!

edited Dec 18, 2021 at 15:15

answered Dec 18, 2021 at 14:42

Arnauld

181k18 gold badges168 silver badges611 bronze badges

Add a comment |

lonelyelk · Accepted Answer · 2021-12-19 17:46:15Z

1

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!

edited Dec 19, 2021 at 17:46

answered Dec 18, 2021 at 18:35

lonelyelk

2411 silver badge5 bronze badges

Add a comment |

Stack Exchange Network

AoCG2021 Day 18: Stripping Strips

Test cases

11 Answers 11

TypeScript Types, 537 bytes

Ungolfed / Explanation

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

Older versions

Charcoal, 32 bytes

BQN, 40 35 bytes^SBCS

Pari/GP, 98 bytes

Python, 99 bytes

Rust, 150 bytes

Wolfram Language (Mathematica), 89 bytes

Python3, 195 bytes:

JavaScript (Node.js), 108 bytes

Ruby, 88 86 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
string
grid
or ask your own question.

Hot Network Questions

AoCG2021 Day 18: Stripping Strips

Test cases

11 Answers 11

TypeScript Types, 537 bytes

Ungolfed / Explanation

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

Older versions

Charcoal, 32 bytes

BQN, 40 35 bytesSBCS

Pari/GP, 98 bytes

Python, 99 bytes

Rust, 150 bytes

Wolfram Language (Mathematica), 89 bytes

Python3, 195 bytes:

JavaScript (Node.js), 108 bytes

Ruby, 88 86 bytes

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

BQN, 40 35 bytes^SBCS

Not the answer you're looking for? Browse other questions tagged
code-golf
string
grid
or ask your own question.