18
\$\begingroup\$

Fast and Golfiest Cops Thread

Welcome to the first season of Fast and Golfiest, a cops-and-robbers challenge! I designed this challenge to encourage competitive coding for efficiency (fastest algorithm) to become more popular on the site.

The rules are simple. The cops must choose a problem from LeetCode, the prestigious competitive programming platform, and independently solve it with code that is as efficient and as short as possible. The problem must be of "medium" or "hard" difficulty (no easy stuff!). Also, according to the theme of this season, it must be related to strings! Note that for the cops, efficiency matters most, and you do not need to spend too much efforts trying to golf up the code painstakingly.

Your answer post should include the following:

  1. The problem you chose, and the link to it on LeetCode.

  2. Your code, its length in bytes, and the language you used.

  3. The UTC time of your post.

  4. The time complexity of your code.

The robbers will then try to golf up the cops' code without sacrificing time complexity. Here's the link to the Robbers' Thread.

Your score is the amount of 5 minute intervals in the amount of time it remains uncracked, rounded to the nearest integer!

If you have any advices please let me know in the comments so that this challenge series could be improved. Thanks in advance!

Leaderboard: It seems that I seriously need to fix the scoring system :-( Leaderboard disactivated for this season.

\$\endgroup\$
11
  • 3
    \$\begingroup\$ All leetcode questions about strings: leetcode.com/tag/string \$\endgroup\$ Jul 20, 2023 at 8:37
  • 1
    \$\begingroup\$ It's strongly implied but perhaps should be stated outright that the robber has to use the same language as the cop for a given post. \$\endgroup\$
    – Noodle9
    Jul 20, 2023 at 11:21
  • 3
    \$\begingroup\$ "Note that for the cops, efficiency matters most, and you do not need to spend too much efforts trying to golf up the code painstakingly." the rules as they currently are don't match that - if you find the shortest code for some problem (ignoring time complexity) than it couldn't be cracked and you'd get infinite score. Even if you allow robbers to use longer code if it's more efficient, there's a strong incentive to golf your code as much as possible. \$\endgroup\$ Jul 20, 2023 at 13:45
  • \$\begingroup\$ @CommandMaster Thanks for pointing that out. All I wanna say is that the cops should value efficiency, and although code golfing is of course important, it should not be, for instance, a reason for some one to back up from participating ;-) \$\endgroup\$ Jul 20, 2023 at 14:42
  • 4
    \$\begingroup\$ @noodleman Also, the goal is not to win. The scores are for fun and the true purpose is to learn and practice. \$\endgroup\$ Jul 20, 2023 at 14:55

15 Answers 15

4
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Cracked \$\endgroup\$ Jul 20, 2023 at 14:40
  • \$\begingroup\$ 7 points under new system ;-) \$\endgroup\$ Jul 20, 2023 at 14:45
4
\$\begingroup\$

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.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Your TIO contains 132 bytes instead of 122 (which I assume is a typo in your answer)? And I know the challenge for the Robbers is to golf you code, but removing those two no-op spaces would be kinda lame, so I would suggest removing them (they're at 1 else and 31 if). :) PS: if you switch to language Python 3.8 on TIO, you can add some test cases to your TIO-link. \$\endgroup\$ Jul 20, 2023 at 9:16
  • \$\begingroup\$ @KevinCruijssen fixed + I don’t think 1else is valid. Edit: 1else is valid. \$\endgroup\$ Jul 20, 2023 at 9:21
  • 1
    \$\begingroup\$ "O(n) or worse" really isn't a good enough title if people are going to try to improve your score. Please calculate your exact complexity. You are giving yourself an unfair advantage \$\endgroup\$
    – mousetail
    Jul 20, 2023 at 9:26
  • 2
    \$\begingroup\$ Cracked \$\endgroup\$
    – The Thonnu
    Jul 20, 2023 at 9:28
  • \$\begingroup\$ Successfully exploited FGITW phenomenon! \$\endgroup\$ Jul 20, 2023 at 14:04
4
\$\begingroup\$

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

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

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

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

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~$<

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

enter image description here

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!();
    }
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Thanks for the non-formatted version! \$\endgroup\$
    – The Thonnu
    Jul 21, 2023 at 12:51
  • 1
    \$\begingroup\$ Kind of a late submission, but cracked \$\endgroup\$
    – c--
    Jul 26, 2023 at 15:01
  • \$\begingroup\$ This is strangely glitchy on google chrome. Why are the URLs https://$? \$\endgroup\$ Aug 29, 2023 at 19:05
3
\$\begingroup\$

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)}'
\$\endgroup\$
3
  • \$\begingroup\$ x and x not in'..' can be x not in'..', feels like a cheap golf though \$\endgroup\$
    – c--
    Jul 20, 2023 at 17:03
  • \$\begingroup\$ @TheThonnu not in allows it to check for both . and ... Anyways, cracked \$\endgroup\$
    – Value Ink
    Jul 20, 2023 at 18:04
  • \$\begingroup\$ @ValueInk oh yeah, forgot about that. \$\endgroup\$
    – The Thonnu
    Jul 20, 2023 at 18:29
3
\$\begingroup\$

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)

\$\endgroup\$
2
  • \$\begingroup\$ You can remove the comma in c={0,} \$\endgroup\$
    – The Thonnu
    Jul 20, 2023 at 18:35
  • 1
    \$\begingroup\$ Cracked \$\endgroup\$ Jul 20, 2023 at 18:41
3
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ i.sstatic.net/btqDX.png fails on a testcase \$\endgroup\$ Jul 21, 2023 at 21:24
  • \$\begingroup\$ @SuperStormer Good catch, I had min(d) where I should have had d[-1]. If the challenge were still going I suppose I should reset the time, but as it is I'm not sure it matters. \$\endgroup\$ Jul 24, 2023 at 14:05
  • \$\begingroup\$ Cracked \$\endgroup\$ Jul 25, 2023 at 2:14
2
\$\begingroup\$

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

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Cracked \$\endgroup\$
    – The Thonnu
    Jul 20, 2023 at 14:05
  • \$\begingroup\$ Remember to add UTC time ;-) \$\endgroup\$ Jul 20, 2023 at 14:47
  • \$\begingroup\$ @ShiranYuan You can hover over the posted time to see the time in UTC \$\endgroup\$
    – mousetail
    Jul 20, 2023 at 14:49
  • \$\begingroup\$ @mousetail Nope. Not on my side :-( \$\endgroup\$ Jul 20, 2023 at 14:50
2
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ Cracked \$\endgroup\$
    – c--
    Jul 20, 2023 at 21:48
  • \$\begingroup\$ This is definitely not \$O(n^2)\$. Even the length of the output is exponential with a base of Conway’s constant. \$\endgroup\$ Jul 21, 2023 at 1:57
2
\$\begingroup\$

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

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

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.

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

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

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

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

\$\endgroup\$
3
  • \$\begingroup\$ @AndersKaseorg Fixed, and timer reset \$\endgroup\$
    – mousetail
    Jul 21, 2023 at 4:19
  • 1
    \$\begingroup\$ Cracked, it felt kinda cheap, I'll see if I can find a real golf tommorrow \$\endgroup\$
    – c--
    Jul 21, 2023 at 5:07
  • \$\begingroup\$ The time complexity is \$O(4^n n^{-1/2})\$. \$\endgroup\$ Jul 21, 2023 at 17:10
1
\$\begingroup\$

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

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

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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