Codegolf - Aocg2021, День 18: Раздевание

Часть Появление Кодекса Гольфа 2021 событие. Подробности смотрите в связанном мета-сообщении.

История продолжается с AoC2018, день 3.

Но ты не Бабблер, ты Ликсал! да, я знаю.

---

После долгого периода хаоса эльфы наконец договорились, как разрезать ткань. К сожалению, на следующий день они придумали, как использовать остатки — сделать очень длинную ленту для упаковки подарков. Что ж, если он может уменьшить Санту, возможно, он сможет уменьшить и подарки...

Описание полосы представляет собой строку

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

, which happens to be the first letters of "up down left right" in Elvish (totally not этот эльфийский). Разделите ткань на сетку из квадратных ячеек размером 1 см × 1 см, выберите начальную ячейку где-то посередине, а затем перемещайтесь согласно описанию, чтобы забрать полоску.

Итак, если строка ODCF , you would get this strip, starting at X:

OFFF CO.D .OCD .X.. OFFF CX.D CCCD D...

... За исключением того, что полоска, которую вам дали Эльфы, является самопересекающейся, поэтому она просто не работает (деталь ткани площадью 1 см² волшебным образом не становится 2 см² - ну, это физика, по крайней мере, пока не придет Санта).

Учитывая строку COFFFDDCCCD , the OOCOFFFDDC это место самопересечения полосы:

?

Во избежание OFFF CO.D C?CD DX.. cell becoming a problem, you can take its substring (a contiguous part of the given string) in two ways: ? (отрезая последние 3 символа) и OOCOFFFDDCCCD (cutting away the first 2 chars) gives, respectively,

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

Среди этих двух и всех остальных вариантов последний из двух выше является самым длинным.

Дана непустая строка OOCOFFFDD , 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.

Применяются стандартные правила. Выигрывает самый короткий код в байтах.

Тестовые случаи

ODCF

#код-гольф #код-гольф #строка #сетка

Типы TypeScript, 537 байт

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

Попробуйте онлайн!

Негольфед / Объяснение

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

||answer||

Python 3.8 (предварительная версия) 106, 103 (@pxeger), 96 (@ovs), 89, 84 байта

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

Попробуйте онлайн!

Старые версии

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

Попробуйте онлайн!

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

Попробуйте онлайн!

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

Попробуйте онлайн!

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

Попробуйте онлайн!

Древесный уголь, 32 байта

B

Попробуйте онлайн! Ссылка на подробную версию кода. Объяснение:

(1+X)*(not Y)

Прокрутите каждый суффикс.

(1+X)*(1-Y)

Перебирайте символы в суффиксе.

-~X*-~-Y

Остановитесь, если полоска самопересекается.

~X*~-Y

Отметьте текущую ячейку как часть полосы и перейдите туда, где должна быть следующая ячейка.

max

Убедитесь, что последняя ячейка не является частью полосы. Это позволит удалить неправильную ячейку, если полоса самопересечена, но имеет значение только количество.

0

Запишите количество клеток, отмеченных как часть полоски.

*

Очистите холст, чтобы подготовить следующий суффикс или вывести результат.

a>""

Выведите найденную максимально возможную длину полосы.

БКН, 40 35 байт^СБКС

a and

Беги онлайн!

BQN пока не поддерживает комплексные числа, а это означает, что направления необходимо кодировать как кортежи с помощью a :

0

Перебираем суффиксы bool(a) , and get the length of the longest unique prefix of each. The maximum of that is the result.

Париж/GP, 98 байт

a>""

Попробуйте онлайн!

Питон, 99 байт

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

Попробуйте это онлайн!

Трюки:

• ↓ is the same as ⟨ 'O' ⟨ ¯1 0 ⟩ ⟩ ⟨ 'D' ⟨ 1 0 ⟩ ⟩ ⟨ 'C' ⟨ 0 ¯1 ⟩ ⟩ ⟨ 'F' ⟨ 0 1 ⟩ ⟩ , поскольку строки сравниваются лексикографически и могут использоваться как рекурсивный базовый вариант, поскольку возвращают <˘⍉¬4|31‿37|⌜9×@-??? when ⌈´·{⊑/¬«∊+`<˘»⍉¬4|31‿37|⌜9×@-???∾@}¨↓ пусто, в отличие от просто »Ｉ⌈υ
• ⎚ 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 ⊞υＬＫＡ и тот факт, что результат всегда положителен, поэтому мы можем с радостью пройти ψ to ✳⊗⌕FOCκ¹ )
• Ｆ¬℅ＫＫ = Ｆ✂θι = ＦＬθ« = ＦＬθ«Ｆ✂θιＦ¬℅ＫＫ✳⊗⌕FOCκ¹ψ⊞υＬＫＡ⎚»Ｉ⌈υ
• С помощью переменной флага 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) , I combine the loops searching for the shortest substring into one recursive function

Ржавчина, 150 байт

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)

Попробуйте онлайн!

Не в гольфе:

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 ||answer||

Язык Wolfram (Математика), 89 байт

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

Попробуйте онлайн!

Python3, 195 байт:

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

Попробуйте онлайн!

JavaScript (Node.js), 108 байт

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

Попробуйте онлайн!

Руби, 88 86 байт

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

Попробуйте онлайн!