15
\$\begingroup\$

This is a challenge. For the cops thread, go here.

This challenge involves two OEIS sequences chosen by the cops -- S1, S2 -- and how well those sequences can be golfed and obfuscated.

The cops are constructing code A that produces S1 and giving a number X that they claim is the best Levenshtein distance possible (in characters) to create B that produces S2.

The Robbers' Challenge

To crack a particular cop's submission, robbers must come up with a program C in the same language (and version) as that answer that produces S2(n) and is Y character changes away from A (with Y <= X). Robbers do not necessarily need to find the exact same B code that the cop (secretly) produced. The robbers' submissions must adhere to the same 0-index or 1-index as specified by the cop's submission.

If you manage this, post an answer with the solution, linking to the cop's answer, and leave a comment on the cop's answer linking back to yours.

Each cop answer can only be cracked once, and of course, you're not allowed to crack your own answer. If the cop's answer turns out to be invalid before or after being cracked, it is not counted towards the robber's score.

Winning and Scoring

Robbers are scored by (X - Y)*5 + 5 for each of their cracks, and the robber with the overall highest score wins.

Further Rules

  • You must not use any built-ins for hashing, encryption, or random number generation (even if you seed the random number generator to a fixed value).
  • Either programs or functions are allowed, but the code must not be a snippet and you must not assume a REPL environment.
  • You may take input and give output in any convenient format. The input/output methods must be the same for both sequences.
  • The definitive calculator for the Levenshtein distance for this challenge is this one on Planet Calc.
  • In addition to being a CnR challenge, this is so all usual golfing rules apply.
\$\endgroup\$

13 Answers 13

7
\$\begingroup\$

Pyke, Levenshtein distance of 1, A036487, A135628 - score 5

Crack of an entry by muddyfish

wX*e

Try it here!

The original code, X*e, squares the input, X, multiplies that by the input *, and halves then floors the result, e.

The trick is that 'X' is 56 in the base 96 representation of w, so wX yields 56, multiply that by the input then floor and halve and you get 28 times the input as needed.

\$\endgroup\$
  • \$\begingroup\$ Exactly what I had. Lasted slightly longer than I expected \$\endgroup\$ – Blue Feb 13 '17 at 18:43
  • \$\begingroup\$ As soon as I saw it I knew it was the intended solution. \$\endgroup\$ – Jonathan Allan Feb 13 '17 at 18:47
4
\$\begingroup\$

Brain-Flak, 28 bytes, Distance of 4, A002817, A090809

(({(({})[()])}{}){{({}[()])}{}})

This answer was discovered with the help of a brute-forcer, which generated 35,000 possible programs (Lot's of them were imbalanced, and thus invalid brain-flak code, but I rolled with the bug and found the answer anyway). This was around the 20 thousandth program tested, and it took around an hour to find (though I don't know exactly how long since I was away when it finished).

I kind of didn't want to post this answer yet, since I don't yet have a full understanding of how this program works. However, the answer is about to be safe so I don't want it to expire. I hope to update this answer more once I fully understand it, as well as posting the code I used to find this answer. But for now, I'll just post a partial explanation.

#Push the sum of:
(

    #The (n-1)th triangular number, and the range [1, n] (The range doesn't count towards the sum I believe)
    ({(({})[()])}{})

    #Triangulate every number on the stack
    {{({}[()])}{}}

)

This makes sense because OEIS states:

For n>0, the terms of this sequence are related to A000124 by a(n) = sum( i*A000124(i), i=0..n-1 ). [Bruno Berselli, Dec 20 2013]

And A000124 are the triangular numbers + 1. However, I don't know exactly what the forumla is, so I can't fully explain how this works.

\$\endgroup\$
3
\$\begingroup\$

Perl 6, 19 bytes, X = 1, A000045 → A000035

{(0,1,*+<*...*)[$_]}

+> in place of +< would also work.

Try it online!

How it works

infix ... is quite useful for simple recursive sequences. The (0,1,*+*...*) part of the original code, which is a shorthand for

(0, 1, -> $x, $y { $x + $y } ... *)

specifies a sequence that begins with 0 and 1, then adds items by computing the sum of the former two items of the sequence.

In contrast, (0,1,*+<*...*) uses left bit-shift (+>, right bit-shift would also work) to construct the parity sequence. Since shifting 1 zero units to the left is 1, and shifting 0 one unit to the left is 0, we get the desired alternating patterns of ones and zeroes.

\$\endgroup\$
2
\$\begingroup\$

Perl 6, 10 bytes, distance 1 - score 5

Crack of an entry by smls

*[0]o 1***

Becomes:

*[0]o 1*+*

Try It Online!

\$\endgroup\$
  • \$\begingroup\$ Good job! I didn't think of this solution, mine was a bit more tricky and actually required the *[0]o to be there. I guess that means I can come up with another challenge based on my "trick" ...:) \$\endgroup\$ – smls Feb 13 '17 at 19:58
  • \$\begingroup\$ I don't really know Perl, just saw the *** and thought it looks like it could unfold the dyadic multiplication operation, *, with the previous arguments, I really don't know what the code actually does. Feel free to edit in some explanation! \$\endgroup\$ – Jonathan Allan Feb 13 '17 at 20:01
  • 2
    \$\begingroup\$ 1*** is parsed as 1 ** *, i.e. a lambda that does "1 to the power of x". 1*+* is parsed as 1 * (+*), i.e. a lambda that does "1 multiplied by (x converted to a number)". \$\endgroup\$ – smls Feb 13 '17 at 20:12
2
\$\begingroup\$

Perl 6, distance 2, smls

Original:

+(*%%2)

Crack:

+(*+0%2)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Darn, again a simple solution I didn't consider... (Mine was the much more obfuscated +(^*Z%2). I guess I'm not very good at drafting these challenges. \$\endgroup\$ – smls Feb 14 '17 at 9:12
2
\$\begingroup\$

WolframAlpha, Distance 1, Greg Martin, A002378, A000537

(sum1to#of n^1)^2&

How it works

I realized that interestingly, (n*(n+1)/2)^2 is a formula for the second sequence. Since sum(1 to n) is equivalent to n*(n+1)/2, I just had to switch the * to a ^.

\$\endgroup\$
  • \$\begingroup\$ You should inform him that you have cracked his answer \$\endgroup\$ – Sriotchilism O'Zaic Feb 14 '17 at 19:11
  • \$\begingroup\$ Well spotted! :) \$\endgroup\$ – Greg Martin Feb 14 '17 at 20:21
2
\$\begingroup\$

Brain-Flak, 20 bytes, DJMcMayhem

({({})({}[()])()}{})

Try it online!

Added a ({}) at the beginning of the loop to double the value in each iteration.

\$\endgroup\$
  • \$\begingroup\$ Nice! FWIW, the 18 byte solution I had was ({(({}[()])){}}{}) \$\endgroup\$ – DJMcMayhem Feb 14 '17 at 23:07
1
\$\begingroup\$

JavaScript, Distance 4, LliwTelracs

Original:

f=x=>{return x?2*x-1+f(x-1):0}

Crack:

f=x=>{return x?2*(-0+f(x-1)):1}

Try it online!

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

JavaScript(ES6), Distance 1, Advancid

Original:

as=function(){ return 2*2**((11)*-1*~arguments[0]/11-(4-(as+[]).length%89))-(as+[]).length%7}

Crack:

as=function(){ return 0*2**((11)*-1*~arguments[0]/11-(4-(as+[]).length%89))-(as+[]).length%7}

Try it online!

or

as=function(){ return 2*1**((11)*-1*~arguments[0]/11-(4-(as+[]).length%89))-(as+[]).length%7}

Try it Online!

Somehow I was able to get it to behave differently between TIO and repl.it (absolutely no clue why 2*1^... would be equal to 0 as according to repl.it)

\$\endgroup\$
  • \$\begingroup\$ I'm too dumb, I didn't think about changing the 2 to a 0. Here is the B function: as=function(){ return 2*2**((1^1)*-1*~arguments[0]/11-(4-(as+[]).length%89))-(as+[]).length%7}. \$\endgroup\$ – user54187 Feb 14 '17 at 6:54
1
\$\begingroup\$

Javascript, 41 bytes, Distance of 3, A061313, A004526

f=x=>{return x>>1;0?x%2?f(x+1)+1:f(x/2)+1:0}

Try it online!

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

Java, Distance 4, Peech, A094683, A000290

Original:

int x{double r=1;for(int i=0;i<42;i++)r=r/2+n/r/2;int k=(int)((int)n*(float)n/Math.pow(n,(Math.sin(n)*Math.sin(n)+Math.cos(n)*Math.cos(n))/2));return n%4%2==(int)Math.log10(Math.E)/Math.log((double)'H'-'@')?(int)r:k;}

Crack:

int x{double r=1;for(int i=0;i<42;i++)r=r/2+n/r/2;int k=(int)((int)n*(float)n/Math.pow(n,(Math.sin(n)*Math.sin(n)+Math.cos(n)*Math.cos(n))/2));return n%4%1==(int)Math.log10(Math.E)/Math.log((double)'H'-'@')?(int)n*n:k;}
                                                                                                                                                          ^                                                         ^^^

returns n*n

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

Javascript, Advancid, distance of 2, A059841 and A000004

Only leaving the code behind the TIO link because it seems to be breaking the site.

Thanks to @nderscore, whose code I used to decrypt the initial code

There was some redundant code such as using !![]+[]+[] instead of !![]+[].

The addition of !+[]-(!+[]) (+1-1) initially prevented decryption.

Try it Online

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

Pyke, Levenshtein distance of 2, A008788, A007526

'SS^

Try it here!

How it works

This does mixed base conversion.

'S grabs the input n and applies, pushing [1, ..., n] on the stack. The next S takes input n and pushes the same array once more. ' seems to cause the next command to be applied to the previous top on the stack; I'm a little fuzzy on the details.

Finally, ^ applies mixed base conversion, so [1, ..., n] [1, ..., n] f computes
a(n) := [1]n + n + (n)(n-1)... + [n!]1 where the brackets indicate the place value and the number to their right the digit.

Now, a(n) = (1 + (1)(n-1) + (n-1)(n-2)(n-3) + ... + (n-1)!)n = n(a(n) + 1), which is the same recursive formula that defines a(n) in [A007526]. Since an empty sum is zero, a(0) = 0 and the base case matches as well.

\$\endgroup\$
  • \$\begingroup\$ How did you get it with so few attempts? I'm interested in your thought processes \$\endgroup\$ – Blue Feb 14 '17 at 21:26
  • \$\begingroup\$ Mixed base conversion is a rather common golfing trick. It's not the first time I used it. \$\endgroup\$ – Dennis Feb 14 '17 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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