11
\$\begingroup\$

Fast and Golfiest Robbers 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 choose problems from LeetCode, a competitive coding platform, and solve them with code as efficient and short as possible. Now you, as the robber, will try to golf up their code, without sacrificing code efficiency. That is, the time complexity of your code must be smaller or equal to the cop code's complexity. You must also use the same language as the cop. Here's the link to the Cops Thread. Note that for the robbers, golfiness matters most! However, if your time complexity is lower than the cop code and shorter than theirs, your score will be 2.718 times the original!

Your answer post should include the following:

  1. A link to the cop post you cracked.

  2. Your code, its length in bytes.

  3. The UTC time of your post.

  4. The time complexity of your code (must be smaller or equal to the cop code's complexity).

You should also edit the cop post to say "Cracked" and add a link to your post.

Your score is the percentage reduction of the code length in bytes compared to the cop code (with the 2.718 times efficiency bonus if you got it), rounded to the nearest integer! Edit: Sorry, it seems unbalanced now so I have to nerf the robbers. The robbers' score will be divided by 4.

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

Leaderboard (Periodically updated. Please note that I rank individual answers instead of answerers to encourage quality over quantity.):

  1. 9 points: ATOI String to Integer by The Thonnu
  2. 5 points: Concatenated Words by CursorCoercer
  3. 4 Points: Longest Substring Without Repeating Characters by CursorCoercer
Improve this question
\$\endgroup\$

11 Answers 11

Reset to default
3
\$\begingroup\$

Python, 84 bytes (35.4% reduction), cracks ATOI string to integer

lambda s:min(max(L:=-2**31,int([*re.findall("^ *([+-]?\d+)",s),0][0])),~L)
import re

Attempt This Online!

  • UTC: 09:28 (updated 09:38)
  • Same time complexity as the cops' answer I think.
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ I know it's already cracked, but you can golf 2 more bytes with t:=-2**31 and ~t: attempt this online. \$\endgroup\$
    – Kevin Cruijssen
    Commented Jul 20, 2023 at 9:38
  • \$\begingroup\$ @KevinCruijssen I was literally about to edit that in lol! \$\endgroup\$
    – The Thonnu
    Commented Jul 20, 2023 at 9:38
  • 1
    \$\begingroup\$ Two souls one thought, I guess. ;) \$\endgroup\$
    – Kevin Cruijssen
    Commented Jul 20, 2023 at 9:39
3
\$\begingroup\$

C (GCC), 44 bytes (6.4% reduction), cracks Removing Stars From a String

i;f(char*s){for(i=0;s[i-=*s++-42?0:2]=*s;);}

Attempt This Online!

-2 bytes thanks to c-- (original cop).

I think this involves undefined behavior. I'm not exactly sure. But it works in the exact compiler version.

It doesn't work for empty strings, but the specification says 1 <= s.length <= 105.

  • UTC: 2023-07-20 18:38:43Z; 2023-07-21 03:55:34Z
  • Time complexity \$O(n)\$ (same as cops' answer)
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ very nice, you can even declare i outside the function for -2 bytes. Also, there's definitely UB in the unsequenced access and modification to s \$\endgroup\$
    – c--
    Commented Jul 20, 2023 at 19:51
2
\$\begingroup\$

Python, 44 bytes (6.4% reduction), cracks Reverse words in a string

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

Attempt This Online!

  • UTC: 14:04 (updated 14:18)
  • Time complexity \$O(n)\$ (same as cops' answer)
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Python, 145 bytes (18% reduction), cracks Concatenated Words

lambda z:[i for i in z if any(q&z==q for q in g(i,0))]
def g(a,b=1):
 if b:yield{a}
 for i in range(1,len(a)):
  for j in g(a[i:]):yield{a[:i]}|j

Attempt This Online!

  • UTC: 14:39
  • Time complexity \$O(n)\$ (same as the cops')
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Python 3, 125 bytes (13% reduction), cracks Longest Substring Without Repeating Characters

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

Try it online!

  • UTC: 18:40
  • Time complexity \$O(n)\$ (same as cops')
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Go, 168 bytes (2.9% reduction), cracks Count and Say

import."fmt"
func g(n int)string{s:="1"
for;n>1;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!

  • Time: 2023-07-20 21:46:57Z
  • Time complexity (same as cops' answer)
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Python 3, 112 bytes (5% reduction), cracks Simplify Path, 2023-07-20 18:02 UTC

Just some minor golfs like realizing elif isn't needed and tweaking the string used to construct the final output. -1 by The Thonnu

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

Try it online!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 112 \$\endgroup\$
    – The Thonnu
    Commented Jul 20, 2023 at 18:31
2
\$\begingroup\$

Python, 122 bytes (1.6% reduction), cracks Edit Distance

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

A bit of a cheap crack.

Time: 2023-07-25 02:11:18Z

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ May be cheap, but nice work all the same. Turns out there's two more bytes to be saved in that little area too TIO \$\endgroup\$
    – CursorCoercer
    Commented Jul 25, 2023 at 18:33
  • \$\begingroup\$ If we switch to a later version of Python, we can save 4 more bytes by dropping the parens around the 2 walruses. \$\endgroup\$
    – SuperStormer
    Commented Jul 25, 2023 at 23:31
2
\$\begingroup\$

><> (Fish), 171 bytes (3.9% reduction), cracks Generate Parentheses

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

Hover over any symbol to see what it does

In plaintext:

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

Try it

  • Time: 2023-07-26 14:58:41Z (updated 15:42:38)
  • Time complexity \$O(n!)\$ (same as cops' answer)

control flow

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

C (GCC), 66 bytes (7.04% reduction), cracks Sum of Scores for buit strings

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

Attempt This Online!

Based on This C tip from G B

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ I was hoping to see a proper golf, it's on me for leaving it open to that \$\endgroup\$
    – c--
    Commented Jul 21, 2023 at 14:42
  • \$\begingroup\$ @c-- Sorry about that, especially after you nicely let me save a byte before cracking my other answer \$\endgroup\$
    – mousetail 'he-him'
    Commented Jul 21, 2023 at 14:44
  • \$\begingroup\$ no worries, no need to be so gracious about it :p \$\endgroup\$
    – c--
    Commented Jul 21, 2023 at 15:15
1
\$\begingroup\$

Rust, 184 bytes (4.6% reduction), cracks Generate Parentheses

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

Attempt This Online!

  • Time: 2023-07-21 05:06:39Z
  • Time complexity \$O(n!)\$ (same as cops' answer)
Improve this answer
\$\endgroup\$
0

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.