Cheapo Enigma machine (Cops)

15

1

For robbers' post, Cheapo Enigma machine (Robbers)

A cop's submission will consist of a program/function that accepts a single byte of data and return a single byte of data. Every possible input must produce a unique output. (In the other words, your function must be bijective)

Robbers will attempt to create the inverse function of yours using as short a code as possible. So your objective is to make your function difficult to invert.

You cannot use built-ins that have the sole purpose of hashing or encryption.

Your byte count cannot exceed 64 bytes. 0-byte solutions are not eligible for winning.

Input/Output format

8 bits (0 or 1), or a base-10 integer in range 1-256, 0-255 or -128 to 127. Can use standard I/O or file I/O. Function can also return a value as output. Input and output should belong to the same range (binary, 1-256, 0-255 or -128 to 127). The robber will also be required to use this range for input and output.

Scoring

Ratio of your byte count to that of the best robber's attempt against you. Lowest score wins.

You are eligible to win (as a cop) only if a robber has attempted to defeat you. (This robber may be you)

Example

C++, uses 0-255 range, 31 bytes

int x;
cin>>x;
cout<<(x+1)%256;

Possible robber submission in C++, 32 bytes

int f(int x)
{return x?x-1:255;}

Using the same language or a similar algorithm isn't a requirement

This gives a score of 31/32 = 0.97 to both the cop and the robber.

ghosts_in_the_code

Posted 2017-04-22T10:13:12.660

Reputation: 2 907

1What does a cop submission consist of? Language, size and full program/function code? – Arnauld – 2017-04-22T10:27:52.370

1isn't it a bit broken if the cop can just make an arbitrarily large thing? – Destructible Lemon – 2017-04-22T10:32:43.370

1This robber may be you What if I post a 64-byte cop answer that maps N to N and a robber answer that does the same thing in one byte? – Arnauld – 2017-04-22T11:04:42.947

@Arnauld Yes, cop submission consists of a single program/function. – ghosts_in_the_code – 2017-04-22T13:44:16.090

@Arnauld I already mentioned, the robber's code isn't competitive in that case; only the cop's code is. – ghosts_in_the_code – 2017-04-22T13:44:53.217

@DestructibleLemon That's why there's a limit of 64 bytes. – ghosts_in_the_code – 2017-04-22T13:49:25.887

1You may want to specify if / how the cop submission should be updated when robbers answer it. (The usual "cracked" update doesn't apply here, I guess. At least not as a unique and definitive crack.) – Arnauld – 2017-04-23T13:28:49.857

Using the same language or a similar algorithm isn't a requirement I missed that at first. Especially the part about the language should be made more prominent. – Dennis – 2017-04-24T18:19:32.840

3On second thought, you might want to remove that rule altogether. I can destroy most answers by posting a robber in Jelly. – Dennis – 2017-04-24T18:25:39.333

Can I also try to out-cop a robber submission? – flawr – 2017-04-24T19:48:35.167

Does the OP mean "injective" instead of "bijective"? – Leaky Nun – 2017-04-25T11:56:34.967

@LeakyNun if every input maps to a different output in the same range, it is bijective within that range. – fəˈnɛtɪk – 2017-04-25T12:29:06.660

@Dennis Yes, you are free to. Otherwise someone may win the challenge simply by using a language others are not familiar with, or have no interest in coding in. – ghosts_in_the_code – 2017-04-25T14:26:19.720

@flawr Yes, you can post multiple answers with multiple function mappings. If you haven't changed the mapping, you​ can edit the original answer. – ghosts_in_the_code – 2017-04-25T14:27:28.990

@Dennis Also certain functions may be missing in certain languages, making it difficult to invert the function. – ghosts_in_the_code – 2017-04-25T14:34:44.330

@LeakyNun If you have a function that from a finite set to another finite set of the same size, then bijective, injective and surjective are all equivalent. – flawr – 2017-04-25T16:10:24.217

Answers

7

Javascript, 11 8 bytes, Score: 8 / 5

x=>x^x/2

Simple implementation of gray code. Decoding usally needs a whole loop. Let's see who comes up with the smallest or even without a loop !

Christoph

Posted 2017-04-22T10:13:12.660

Reputation: 1 489

I guess x^x/4 will be harder because there shouldn't be builtins for it ... – Christoph – 2017-04-24T08:31:44.570

1Score: 8/25 – Arnauld – 2017-04-24T08:36:39.043

Score: 8/5 (Note: I don't think it should be allowed to use another language for the robber submission, but at this point, it is.) – Dennis – 2017-04-24T18:18:41.147

@Dennis I knew there would be an answer like this ;) anyway I still think the idea was good ^^ – Christoph – 2017-04-24T20:04:19.540

1How is this bijective? – Leaky Nun – 2017-04-25T11:54:58.393

1@LeakyNun Uhm not sure what kind of an answer you expect but I'll try: Gray code is an alternative form of representing a number where each consecutive number only changes in 1 bit (hammig distance is always 1). For each number there is exactly one gray encoding and one binary encoding therefore they form a bijection. E.g. 7 is 0111 in binary and 0100 in gray, the next number 8 is 1000 in binary and 1100 in gray. Gray coding is basically the edge coding of binary. – Christoph – 2017-04-25T13:56:33.873

1@LeakyNun ^ is bitwise xor, not exponentiation. Anyway it looks magic – Евгений Новиков – 2017-07-25T11:45:17.930

7

C, 64 bytes, Score 64/71 = 0.901

T[256];f(x){srand(x&&f(x-1));for(;T[x=rand()%256]++;);return x;}

Takes input in the range [0 255].

Try it online! — on TIO (using GCC), this produces:

103,198,105,115,081,255,074,236,041,205,186,171,242,251,227,070,
124,194,084,248,027,232,231,141,118,090,046,099,051,159,201,154,
102,050,013,183,049,088,163,037,093,005,023,233,094,212,178,155,
180,017,014,130,116,065,033,061,220,135,112,062,161,225,252,001,
126,151,234,107,150,143,056,092,042,176,059,175,060,024,219,002,
026,254,067,250,170,058,209,230,148,117,216,190,097,137,249,187,
168,153,015,149,177,235,241,179,239,247,000,229,202,011,203,208,
072,071,100,189,031,035,030,028,123,197,020,075,121,036,158,009,
172,016,080,021,111,034,025,125,245,127,164,019,181,078,152,224,
077,052,188,095,119,108,134,043,085,162,004,211,054,226,240,228,
079,073,253,169,008,138,010,213,068,091,243,142,076,215,045,066,
006,196,132,173,222,048,246,032,133,007,244,185,195,217,160,120,
218,106,083,144,087,238,207,096,210,053,101,063,098,128,165,089,
140,012,192,131,047,039,022,147,184,109,182,193,199,237,018,069,
057,157,174,104,122,166,055,110,003,040,139,086,145,114,129,113,
206,167,191,214,146,221,136,038,156,082,200,029,044,204,223,064

Note that on other systems, it may produce different (but still valid) output, since C does not mandate a specific rand implementation. My submission is specifically the version running on TIO (as linked).


I'm quite disappointed that I wasn't able to get a version like my original (f(x){return rand(srand(x*229))/229%256;}) to work on TIO, since I think that's much more elegant. Since that only works on Clang running on OS X, it isn't fair for the competition. This one's still pretty awkward to reverse, so that's enough I guess.

Dave

Posted 2017-04-22T10:13:12.660

Reputation: 7 519

Well..This is amusing! – Matthew Roh – 2017-04-27T13:38:50.950

Solution here, but I had a bit of a hard time with your srand(), so you'll have to decide if it's acceptable in this form.

– Appleshell – 2017-04-28T04:41:28.190

I fail to see how this program fulfills the Bijection requirement, since output is random not every input has a unique output. – Post Rock Garf Hunter – 2017-04-28T05:08:42.963

I wrote a long list of why this submission isn't worth a single upvote but in fact it boils down to this: This doesn't provide a specific mapping but the group of all mappings. It then restricts itself to a single mapping by enforcing a specific implementation on a specific platform thereby loopholing the need to deal with other languages. – Christoph – 2017-04-28T07:04:32.287

@Appleshell I found a way to fix the srand value without costing an extra byte. I can only apologise that it changes the output, but at least it's fixed on something specific now and doesn't rely on broken behaviour. Might be a little awkward for your answer since it uses 0 for x=0 and x=107 (because x=106 returns 0), and 1 for all other runs. – Dave – 2017-04-28T07:36:47.850

@WheatWizard fixed :) – Dave – 2017-04-28T07:37:47.363

@Christoph I don't think I'll convince you, but on PPGC languages are defined by their implementation, not their spec (which is why TIO provides 3 different C compiler choices), and TIO's implementation is freely available to anybody who wants to run it. That's distinct from my original answer which only worked on OSX (which isn't freely available, so I consider unacceptable; hence why I deleted it). That's not to say there was no issue at all; Appleshell noted that srand without arguments wasn't locking down the output like I thought it was, which I consider a mistake and have fixed. – Dave – 2017-04-28T07:43:55.753

2The problem is not the implementation. The problem is that it lacks what I think are all key ideas of this challenge: Finding a trival algorithm (therefore limited to 64 bytes and language independent) that is nontrival to reverse. Your submission "feels" to loophole on: Language independence, the 64 byte limit by outsourcing to an unknown implementation of a builtin (rand does not depend on the language but the local stdlib) and the hash/encryption rule. It's within PPCG's rules but certainly not what ghosts_in_the_code intended with his rules. – Christoph – 2017-04-28T08:24:56.793

@Christoph Generating random numbers doesn't violate the rule against using a hashing function, but totally agree with everything else you said. Would you recommend I edit the rules to invalidate this? And if so, what edit exactly should I make? – ghosts_in_the_code – 2017-04-28T09:18:24.843

@Dave I updated my solution for this version! :)

– Appleshell – 2017-04-28T09:31:08.030

1@ghosts_in_the_code good RNGs and hash functions are both designed to hardly be reversible. Therefore I think they should be included in that rule (even if the actual implementation might not be designed this way). Anyway I don't recommand changing the rules at this stage. – Christoph – 2017-04-28T10:54:53.353

Score 64/71 – Christoph – 2017-04-28T11:00:31.540

2

Jelly, 2/5

^H

Try it online to see the whole table.

Dennis

Posted 2017-04-22T10:13:12.660

Reputation: 196 637

1Hm, looks like @Christoph had the same idea 9 hours before me... – Dennis – 2017-04-24T17:50:39.600

2

JavaScript, 44 bytes 22/3

x=>a.sort()[x]
for(a=[],i=0;i<256;)a[i]=i++;

Uses lexicographic sort (Javascript Default) to rearrange all the numbers from 0-255

Try it online!

fəˈnɛtɪk

Posted 2017-04-22T10:13:12.660

Reputation: 4 166

122/3 - different language seems acceptable, even if a little odd. I thought I had 5, but 256 got in my way :). – Jonathan Allan – 2017-04-26T04:16:38.063

2

C (gcc), 32 27/30 bytes

Thanks to christoph for golfing 5 bytes.

f(x){x=x?f(x*5+1&255)+1:0;}

Try it online!

Bijan

Posted 2017-04-22T10:13:12.660

Reputation: 781

1Score 32/30. You might want to switch to f(x){x=x?f(x*5+1&255)+1:0;} for a score of 27/30. – Christoph – 2017-04-28T14:39:49.950

1

JavaScript, 13 bytes 13/12

x=>(x<<9)%257

Input and output are both in the range 1->256

Try it online!

fəˈnɛtɪk

Posted 2017-04-22T10:13:12.660

Reputation: 4 166

Score: 13/19 – Arnauld – 2017-04-23T14:27:47.253

Score: 13/12 – Christoph – 2017-04-25T06:45:19.527

1

Octave, 16/6

@(x)mod(x*3,256)

Try it online!

flawr

Posted 2017-04-22T10:13:12.660

Reputation: 40 560

1Score: 16/6 (Note: I don't think it should be allowed to use another language for the robber submission, but at this point, it is.) – Dennis – 2017-04-24T18:42:33.363

1It would also be interesting to know whether I can try to beat your robber submission by making another cop (again using Jelly or MATL too) – flawr – 2017-04-24T19:49:24.887

1

Javascript, 11/8 bytes

x=>x**5%257

Domain/range is 1 through 256.

histocrat

Posted 2017-04-22T10:13:12.660

Reputation: 20 600

Hm, is Javascript bad with large number exponents? This works in Ruby: https://repl.it/HXvZ/0

– histocrat – 2017-04-24T19:00:34.517

JavaScript only has double-precision floats, so anything with more than ~53 bits cannot be represented exactly. x**3 and x**5 should work. – Dennis – 2017-04-24T19:02:08.947

Well, serves me right for assuming. I'll change languages. – histocrat – 2017-04-24T19:03:39.403

Or do Dennis's suggestion, given the rules favoring terser languages. :) Thank you! – histocrat – 2017-04-24T19:05:24.700

Unfortunately, the rules are a bit broken at the moment, and I would be allowed to invert this with another language. Precisely because of the precision limit, this will be rather verbose to invert using JS. – Dennis – 2017-04-24T19:08:19.417

Score: 11/8 – Dennis – 2017-04-24T20:34:49.380

1

Javascript, 27/29 bytes

x=>x-6?x*95%127+x*98%131:65

Edit: Range/Domain is 1..256. Generated via brute force, more or less.

histocrat

Posted 2017-04-22T10:13:12.660

Reputation: 20 600

Sadly it's bijective but not in range [0,256): the value of 130 is never outputted but a value of 256 is (which doesn't fit a 8 bit int). – Christoph – 2017-04-25T06:27:26.273

Score 27 / 29. I like it ! – Christoph – 2017-04-25T06:28:54.350

1Thanks! The rules allow me to specify a range of [1,256], and it's bijective on that range. – histocrat – 2017-04-25T13:01:04.137

1

Java, 35 bytes

int a(int v){return (v*v+v)%512/2;}

Domain/Range are 0-255

Targz

Posted 2017-04-22T10:13:12.660

Reputation: 77

Score: 35/7 – Dennis – 2017-04-27T17:08:15.810

1

Ruby, 23 bytes

->x{('228'*x).to_i%257}

Range and domain is 0..255. Concatenate 228 to itself x times, then take the result modulo 257 (0 maps to 0). 228 is the first magic number after 9 that works for this range (gives distinct values that don't include 256).

histocrat

Posted 2017-04-22T10:13:12.660

Reputation: 20 600

0

Python 3, 32 bytes 32/23

V=lambda x:((3+x)%16)*16+x//16

Domain/Range is 0-255.

Flips the first four bytes with the last four, and adds a three to the first bytes.

Magenta

Posted 2017-04-22T10:13:12.660

Reputation: 1 322

1Score 32 / 23 – Christoph – 2017-04-26T10:57:04.933

0

Python 3, 55 bytes

y=lambda x,i=3:x if i==0 else pow(3,y(5*x,i-1),257)-1

Domain/Range is 0-255.

Magenta

Posted 2017-04-22T10:13:12.660

Reputation: 1 322

0

brainfuck, 37/11

,+++++[>+++++++<-]>++[<+++++++++>-]<.

Try it online!

Not very good but range of 0-255

Christopher

Posted 2017-04-22T10:13:12.660

Reputation: 3 428

Score: 37/11 – Dennis – 2017-04-27T16:40:39.627

@Dennis Nice job! I should not use such a bytey language. – Christopher – 2017-04-27T21:43:44.250

3By the way, censoring language names isn't a good idea. Yes, this particular languages has an ordinary and childish name, but everyone knows what the asterisk stands for, and it cannot be found by the search engine in its current form. – Dennis – 2017-04-27T21:46:30.580

@Dennis finally fixed that – Christopher – 2017-05-28T20:05:20.263

0

Mathematica, 13 bytes

Mod[#^7,257]&

Uses the range [1..256], although it's equally valid on the range [0..255]. To see the entire table, copy/paste one of the following lines of code into the Wolfram sandbox:

Array[ Mod[#^7,257]&, 256]   (for a list of values in order)
Array[ Rule[#,Mod[#^7,257]]&, 256]   (for a list of input-output rules)

Greg Martin

Posted 2017-04-22T10:13:12.660

Reputation: 13 940