32
\$\begingroup\$

The Challenge

A simple "spy versus spy" challenge.

Write a program with the following specifications:

  1. The program may be written in any language but must not exceed 512 characters (as represented in a code block on this site).
  2. The program must accept 5 signed 32-bit integers as inputs. It can take the form of a function that accepts 5 arguments, a function that accepts a single 5-element array, or a complete program that reads 5 integers from any standard input.
  3. The program must output one signed 32-bit integer.
  4. The program must return 1 if and only if the five inputs, interpreted as a sequence, match a specific arithmetic sequence of the programmer's choosing, called the "key". The function must return 0 for all other inputs.

An arithmetic sequence has the property that each successive element of the sequence is equal to its predecessor plus some fixed constant a.

For example, 25 30 35 40 45 is an arithmetic sequence since each element of the sequence is equal to its predecessor plus 5. Likewise, 17 10 3 -4 -11 is an arithmetic sequence since each element is equal to its precessor plus -7.

The sequences 1 2 4 8 16 and 3 9 15 6 12 are not arithmetic sequences.

A key may be any arithmetic sequence of your choosing, with the sole restriction that sequences involving integer overflow are not permitted. That is, the sequence must be strictly increasing, strictly decreasing, or have all elements equal.

As an example, suppose you choose the key 98021 93880 89739 85598 81457. Your program must return 1 if the inputs (in sequence) match these five numbers, and 0 otherwise.

Please note that the means of protecting the key should be of your own novel design. Also, probabilistic solutions that may return false positives with any nonzero probability are not permitted. In particular, please do not use any standard cryptographic hashes, including library functions for standard cryptographic hashes.

The Scoring

The shortest non-cracked submission(s) per character count will be declared the winner(s).

If there's any confusion, please feel free to ask or comment.

The Counter-Challenge

All readers, including those who have submitted their own programs, are encouraged to "crack" submissions. A submission is cracked when its key is posted in the associated comments section. If a submission persists for 72 hours without being modified or cracked, it is considered "safe" and any subsequent success in cracking it will be ignored for sake of the contest.

See "Disclaimer" below for details on the updated cracking score policy.

Cracked submissions are eliminated from contention (provided they are not "safe"). They should not be edited. If a reader wishes to submit a new program, (s)he should do so in a separate answer.

The cracker(s) with the highest score(s) will be declared the winners along with the developers of the winning programs.

Please do not crack your own submission.

Best of luck. :)

Leaderboard

Penultimate standings (pending safety of Dennis' CJam 49 submission).

Secure Lockers

  1. CJam 49, Dennis
  2. CJam 62, Dennis safe
  3. CJam 91, Dennis safe
  4. Python 156, Maarten Baert safe
  5. Perl 256, chilemagic safe
  6. Java 468, Geobits safe

Unstoppable Crackers

  1. Peter Taylor [Ruby 130, Java 342, Mathematica 146*, Mathematica 72*, CJam 37]
  2. Dennis [Pyth 13, Python 86*, Lua 105*, GolfScript 116, C 239*]
  3. Martin Büttner [Javascript 125, Python 128*, Ruby 175*, Ruby 249*]
  4. Tyilo [C 459, Javascript 958*]
  5. freddieknets [Mathematica 67*]
  6. Ilmari Karonen [Python27 182*]
  7. nitrous [C 212*]

*non-compliant submission

Disclaimer (Updated 11:15 PM EST, Aug 26)

With the scoring problems finally reaching critical mass (given two thirds of the cracked submissions are thus far non-compliant), I've ranked the top crackers in terms of number of submissions cracked (primary) and total number of characters in compliant cracked submissions (secondary).

As before, the exact submissions cracked, the length of the submissions, and their compliant/non-compliant status are all marked so that readers may infer their own rankings if they believe the new official rankings are unfair.

My apologies for amending the rules this late in the game.

\$\endgroup\$
36
  • 6
    \$\begingroup\$ How are you going to verify that programs meet point 4? Do you expect people to edit their safe answers to add a proof? Are probabilistic submissions permitted on the basis of assuming that hash functions are ideal and the chance of a collision with another element of the 48-bit (according to your estimate above) space is negligible? \$\endgroup\$ Commented Aug 25, 2014 at 8:41
  • 2
    \$\begingroup\$ The scoring system seems to encourage crackers to ignore the shortest locks because they score better by cracking two long locks than two small ones. \$\endgroup\$ Commented Aug 25, 2014 at 17:37
  • 3
    \$\begingroup\$ @COTO I think the problem is that you can only get 2 cracking scores, and only the shortest. So why not wait and hope and longer one shows up? For example, Martin now has no incentive to crack my (longer) lock, since he's already cracked two shorter ones. Anyone who cracks mine will now beat him without even having to do a second one. \$\endgroup\$
    – Geobits
    Commented Aug 25, 2014 at 17:51
  • 1
    \$\begingroup\$ I think a better scoring system might be sum of total times between question and crack. That way, cracking a bunch of easy ones can be beaten, and the real reward comes from cracking the really hard ones. \$\endgroup\$
    – isaacg
    Commented Aug 25, 2014 at 21:52
  • 1
    \$\begingroup\$ I'm new to golfing, so maybe it's a stupid question, sorry for that. Why is the code length measured in characters and not in bytes? The latter is literally the memory space that a program occupies, so for me it seems more logical. Eg. the CJam answer is the shortest in characters, but when looking at its size (326 because of unicode) it isn't even in the top 5. So I wonder, is it common convention in golfing to count chars instead of bytes? \$\endgroup\$ Commented Aug 26, 2014 at 13:30

32 Answers 32

1
2
-2
\$\begingroup\$

C, 212 (Cracked)

This is the same idea as my previous submission, golfed more thoroughly, with a bug corrected that passed 0,0,0,0,0 (Thanks to Dennis for pointing out the bug). Compile with -std=c99.

#define L long long
p(L x){x=abs(x);for(L i=2;i<x;i++){if((x/i)*i==x)return 0;}return(x>1);}
f(a,b,c,d,e){char k[99];L m;sprintf(k,"%d%d%d%d%d",e,d,c,b,a);sscanf(k,"%lld",&m);
return p(a)&p(b)&p(c)&p(d)&p(e)&p(m);}
\$\endgroup\$
2
  • \$\begingroup\$ Any sequence (arithmetic or not) of negative primes will work. Two examples: -7 -37 -67 -97 -127, -157 -127 -97 -67 -37 \$\endgroup\$
    – Dennis
    Commented Aug 26, 2014 at 1:27
  • \$\begingroup\$ Yeah, my code is just riddled with bugs. The answer nitrous gave is along the lines of what I was looking for. But nice job pointing out the more obvious answers. \$\endgroup\$
    – Orby
    Commented Aug 26, 2014 at 1:32
-2
\$\begingroup\$

Python 3 (152)

Edit 2: I'm withdrawing this entry because it accepting the correct key seems to depend on hardware or version specifics, which would be unfair to crackers. On online Python 3 interpreters I tried, low-significance bits of the result differed slightly, suggesting the algorithm is sensitive to the exact hardware implementation of arithmetic.

Edit: Made a much longer target to make uniqueness likely given 160 bits of input. Unfortunately, now this target takes over half my characters. This means that this style of submission is unfortunately largely a compression contest.

def f(l,a=[0]):
 for n in l:a+=[(.8+.6j)**(n+a[-1])]
 return a[2::2]==[-0.20857691594748845+0.9907381787645837j,-0.7480510203178323-0.0856921111325014j]

Nothing systematic, just some annoying mangling with complex exponents.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Are you sure this is unique? Your hash has less than 64 bits, and the input has 160. \$\endgroup\$ Commented Aug 26, 2014 at 17:49
  • \$\begingroup\$ @MartinBüttner Oh, I see. Is it actually 160 bits or 64-lg(5)? I had understood that only arithmetic sequences needed to be considered. \$\endgroup\$
    – xnor
    Commented Aug 26, 2014 at 18:19
  • \$\begingroup\$ No, your program needs to return 0 for everything that's not an arithmetic sequence. \$\endgroup\$ Commented Aug 26, 2014 at 19:15
1
2

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.