Generate Parenthesis, ><> (Fish), 178 bytes, \$O(n!)\$, Cracked by C--

Time: 2023-07-21 12:35:24Z

^{Hover over any symbol to see what it does. If this appears glitched unformulated version below.}

Try it

If the "fancy" formatting above doesn't display for you, a version without formatting:

i>:?v~l2,b2.
10-1<.02}}
:?v~{{l2,06.
v \&'('o:2*[{1+}]$:
\:?v~$}}&1-b2.
')'/.31-1o
>:?v;
1+&\&:2*[{1-:}]?v:@l1-2,&:&-1+=?v$
{{&>:?v~}}50ao./~0}]
.61-1&>1-&:2*[{/>1{{69!.<96{{1~$<

If my Interpreter is too slow for you, TIO link

Not super well golfed, relying on people being too intimidated by fish.

How this works

The standard recursive version doesn't work well for fish because:

• It doesn't have functions
• There is no easy way to copy an array
• The only array type thing you have is the stack and there is only one of them

I came up with a completely different approach that does not involve recursion at all, and uses O(n) memory.

We note that, for a number of parenthesis N, we can place opening parenthesis on fixed places then just dynamically decide where to place the closing one that matches it. We can use this to encode a given configuration as the distance between each opening and the corresponding closing parenthesis (+1 for technical reasons)

(())()() = 2, 1, 1, 1
((()())) = 3, 2, 1, 1
(((()))) = 4, 3, 2, 1
()()(()) = 1, 1, 2, 1

Now all we need to find is an algorithm that can, from one set of numbers, figure out the "next" valid configuration.

Rendering

The render loop works as follows: We store next to each number an extra 0. This 0 represents the number of closing parenthesis that need to be drawn after that number. Now, when we for example need to render a parenthesis with a distance of 1, we increment the value in the stack at 2 * 1. In this case it will be the closing parenthesis for the same number. Then after printing the ( we can print N ) characters depending on the value stored.

All of this means we can avoid any kind of recursion.

Incrementing

The incrementing logic is harder, but we can re-use the information from the closing parenthesis from the render stage. First, we try to increment the order of the last opening brace. If this makes us extend past the edge of the set, we skip and go to the next one. This part is easy.

An harder part is making sure the area we enclode does not partially intersect any other pair. There couldn't be any pairs to the right since they have all been reset to 1, but there could be intersecting pairs to the left. For this purpose, we check the closing parenthesis again. We subtract one closing parenthesis from N steps to the front. If they are now zero, we can safely increment past the boudary. Otherwise, we must again reset and try the next pair to the left.

If we have found a opening that can be incremented, we must reset the rest of the ")" counters to 0, then can render and continue. If we have reached the leftmost brace and it also can't be incremented, we have tried all sets and we can safely exit.

Approximately the same algorithm in Rust

|x|{
    let mut z=vec![(1,0);x];
    loop{
        for i in 0..x{
            print!("(");
            let closing_index = z[i].0 + i - 1;
            z[closing_index].1+=1;
            print!("{}",")".repeat(z[i].1));
        }
        let mut done=false;
        for i in 0..x{
            let closing_index =z[i].0 + i - 1;
            z[closing_index].1-=1;
            if !done && !(i + z[i].0 >= x || z[closing_index].1> 0) {
                z[i].0+=1;
                done=true;
            }
        }
        if !done {
            return;
        } 
        println!();
    }
}

Edit Distance, Python 3.8 (pre-release), 124 bytes, \$O(mn)\$ complexity, cracked by SuperStormer

(I won't bother trying to score since I had to edit my answer and the scoring system was flawed)

lambda a,b:(d:=range(len(b)+1),[d:=[x:=d[(j:=0)]+1]+[x:=min(x+1,d[(j:=j+1)]+1,d[j-1]+(i!=k))for k in b]for i in a])and d[-1]

Try it online!

Ya like walrus operators?

Complexity is \$O(mn)\$ where m,n are the lengths of the two input strings.
Time: 2023-07-20 16:18:22Z

Sum of Scores of Built Strings, C (GCC), 71 bytes, \$O(n^2)\$ complexity, Cracked by mousetail, 93 points

f(s,l,i)char*s;{for(i=0;s[i]&&s[l+i]==s[i];++i);return l?i+f(s,l-1):i;}

Attempt This Online!

Time: 2023-07-20 21:33:27Z

Python, 47 bytes, Spiral Matrix, O((m+n)mn)

f=lambda x:x and[*x[0]]+f([*zip(*x[1:])][::-1])

Given an m x n matrix, return all elements of the matrix in spiral order.

Time: 2023-07-21 08:54:05Z

Generate Parenthesis, Rust, 193 bytes, \$O(n!)\$ Cracked by C--, 1 point

• C-- generously helped me save 1 point before cracking it in an actually significant way

fn f(z:i32)->Vec<String>{if z<1{vec![format!("")]}else{(0..z).flat_map(|i|->Vec<_>{let(a,b)=(f(i),f(z-i-1));a.iter().flat_map(|c|b.iter().map(move|d|format!("({c})")+d)).collect()}).collect()}}

Attempt This Online!

Time: 2023-07-21 05:01:42Z

Python, 48 bytes, Count Number of Distinct Integers After Reverse Operations, O(nd)

lambda x:len({*x}|{int(str(c)[::-1])for c in x})

You are given an array nums consisting of positive integers.

You have to take each integer in the array, reverse its digits, and add it to the end of the array. You should apply this operation to the original integers in nums.

Return the number of distinct integers in the final array.

Time complexity is O(nd) where n is the number of elements in the input, and d is the number of digits in the largest number.

Time of post: 2023-07-21 08:21:19Z

Count and Say, Go, 173 bytes, \$O(n^2)?\$, 2023-07-20 21:22:03 UTC

Cracked by C--, score 5

import."fmt"
func g(n int)string{s:="1"
for N:=1;N<n;N++{c,o,f,k:=1,"",rune(s[0]),s[1:]+"_"
for _,r:=range k{if r==f{c++}else{o+=Sprintf("%d%c",c,f);f,c=r,1}}
s=o}
return s}

Attempt This Online!

A slight modification of my Say What You Can See answer. Enjoy Golang!

Ruby, 184 bytes, Substring with Concatenation of All Words

->s,d{l,*r=d.size*z=d[0].size
c={};d.map{|w|c[w]=d.count w}
0.step(z-1){|i|j=i;b=Hash.new 0
(r<<j-l if c.all?{|w,v|v==b[w]}
b[s[j-l,z]]-=1if j>=l
b[s[j,z]]+=1
j+=z)while j<s.size+l}
r}

Try it online!

Complexity should be \$O(mn)\$ where \$m\$ is the number of unique words (relevant for a testcase on LeetCode where the words list has multiple copies of "a") and \$n\$ is the length of the string.

Current time is 2023-07-21 00:04 UTC

Removing Stars From a String, C (GCC), 47 bytes, \$O(n)\$ complexity, Cracked by jimmy23013, 25 points

f(char*s){for(char*p=s;*s-42?*p++=*s:p--;s++);}

Attempt This Online!

Time: 2023-07-20 16:36:08Z

Repeated String Match, 48 bytes, Excel, 20:08 UTC, O(n)

=IFNA(XMATCH(0,0*FIND(B1,REPT(A1,ROW(A:A)))),-1)

Inputs: a and b in cells A1 and B1 respectively.

Python 3, 144 bytes, Longest Substring Without Repeating Characters, O(N), Time: 2023-07-20 17:17:27Z.

83 min = 17 points

Cracked by CursorCoercer (125 bytes)

def f(s):
 m=x=y=0;c={0,}
 while y<len(s):
  if s[y]in c:
   while s[x]!=s[y]:x+=1
   x+=1;c={*s[x:y]}
  c.add(s[y]);y+=1;m=max(m,y-x)
 return m

Try it online!

Runs in O(N) because python sets have lookup/add of O(1). Using lists could decrease the byte count but would technically increase the runtime to O(N^2)

Simplify Path, 119 Bytes, Python 3, \$O(n)\$, 16:20 UTC (cracked by Value Ink, 20 points)

def f(p):
    s=[]
    for x in p.split('/'):
        if x=='..'and s:s.pop()
        elif x and x not in'..':s+=[x]
    return f'/{"/".join(s)}'

ATOI string to integer, 130 Bytes, Python 3 (IDLE), probably \$O(n)\$ or worse, 9:10 am UTC (it's DST in uk), Cracked in 18 min, so 0 points :( 4 points under new system :)

lambda x:a if-2**31<(a:=int(re.match(r" *((\+|-)?(\d*))",x).groups(1)[0]or 0))<2**31-1else-2**31if-2**31>=a else 2**31-1
import re

Don't Try It Online!, it doesn't work there.

Concatenated Words, Python, 177 bytes, \$O(n)\$ time assuming input is a set where \$n\$ is the number of words, Cracked by Cursor Coercer, 7 points

This is \$O(2^L)\$ where \$L\$ is the length of each word but I don't define N that way. It's almost as if asymptotic complexity is isn't a total unambiguous ordering for arbitrary problems.

lambda z:[i for i in z if any(all(i[a:b]in z and i[a:b]!=i for a,b in q)for q in g(0,len(i)))]
def g(a,b):
 yield[(a,b)]
 for i in range(a+1,b):
  for j in g(i,b):yield[(a,i)]+j

Attempt This Online!

time: 2023-07-20 14:02:05Z

Reverse words in string, Python, 47 bytes, \$O(n)\$ complexity, Cracked by The Thonnu, 6 point

lambda g:print(*map(str.strip,g.split()[::-1]))

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Time: 2023-07-20 13:35:51Z