Make your language *mostly* unusable! (Cops' thread)

Haskell, cracked by Christian Sievers

import Prelude(getLine,print)
a=a

Full program, reading two integers (including negative ones) from stdin and writing to stdout.

I've just disabled the Prelude so almost nothing is in scope, and then added a definition; further imports are syntactically invalid. I gave you getLine and print though.

Edited to add my original solution. Christian's crack was different, but exploits the same basic features (you can get a surprising amount of computation done by accessing functions that have syntactic sugar, even when you can't call anything builtin directly or even name the types involved).

import Prelude(getLine,print)
a=a
(x:l)!0=x
(x:l)!n=l!d[0..n]
d[x,y]=x
d(x:l)=d l
x^y=[x..]!y
x+y=f[0..y](x^y)(-((-x)^(-y)))
f[]x y=y
f _ x y=x
f.g= \x->f(g x)
f&0= \x->x
f&n=f.(f&d[0..n])
x*y=((+x)&y)0
x%[]=x
x%('-':s)= -(x%s)
x%(c:s)=x*10+i c%s
i c=l['1'..c]
l[]=0
l(x:s)=1+l s
main=do
 x<-getLine
 y<-getLine
 print((0%x)+(0%y))

Which probably isn't super-golfed anyway, but here it is more readibly:

import Prelude(getLine,print)
a=a

-- List indexing
(x : _) !! 0 = x
(_ : xs) !! n = xs !! (sndLast [0..n])

-- sndLast [0..n] lets us decrement a positive integer
sndLast [x, _] = x
sndLast (_ : xs) = sndLast xs

-- Pseudo-addition: right-operator must be non-negative
x +~ y = [x..] !! y

-- Generalised addition by sign-flipping if y is negative
x + y = switch [0..y] (x +~ y) (-((-x) +~ (-y)))
  where switch [] _ empty = empty   -- [0..y] is null if y is negative
        switch _ nonempty _ = nonempty

f . g = \x -> f (g x)

-- compose a function with itself N times
composeN f 0 = \x -> x
composeN f n = f . (composeN f (sndLast [0..n]))

-- multiplication is chained addition
x * y = composeN (+x) y 0

strToNat acc [] = acc
strToNat acc ('-' : cs) = -(strToNat acc cs)
strToNat acc (c : cs) = strToNat (acc * 10 + charToDigit c) cs

charToDigit c = length ['1'..c]

length [] = 0
length (_ : xs) = 1 + length xs

main = do
  x <- getLine
  y <- getLine
  print (strToNat 0 x + strToNat 0 y)

Python 2, Cracked

Implements addition as a named function

import sys
c="".join(open(__file__).read().split('\n')[4:])
if set(c)-set(' &)(,.:[]a`cdfijmonrt~')or"import"in c:sys.setrecursionlimit(1)
f=lambda\

Try it online!

What does this do?

For the purposes of helping you out a bit I'll explain what this does. This code opens the source file and checks if the remainder of the code fits the following criteria:

  • Does not contain the string import
  • Is made solely of the characters &)(,.:[]a`cdfijmonrt~

If it fails either criterion the recursion limit is set to 1 meaning that any code you write will hit the recursion limit.

There are no tricks here, I have written a solution that uses only these characters and no imports, I'm not doing anything subversive, but I will say that I think this will be pretty hard to crack.

To save you some time here is a short list of useful things you cannot do with this restriction

  • + well duh,

  • eval/exec Wasn't going to let you get away with that

  • Numbers, They might be more useful than you think

  • String literals

  • len

  • =, No assigning variables

  • >,<,==. . . I have left you with no comparisons

  • *,-,/,%,^,|,>>,<< The only operators available are ~ and &

  • __foo__, None of those fancy double underscore methods are allowed.


Python 2, Cracked

This is the fourth iteration of this answer. Each of the last answers has was cracked via reseting the recursion depth.

Implements addition as a named function

import sys
if set("".join(open(__file__).read().split('\n')[4:]))-set(' &)(,.:[]a`cdfijmonrt~'):sys.setrecursionlimit(1)
for m in sys.modules:sys.modules[m]=None
del sys;f=lambda\

Try it online!

What does this do?

For the purposes of helping you out a bit I'll explain what this does. This code opens the source file and checks if the remainder of the code is made solely of the characters &)(,.:[]a`cdfijmonrt~

If it fails the recursion limit is set to 1 meaning that any code you write will hit the recursion limit.

I've also disabled all of the modules, so you can't import anything.

There are no tricks here, I have written a solution that uses only these characters and no imports, I'm not doing anything subversive, but I will say that I think this will be pretty hard to crack.

To save you some time here is a short list of useful things you cannot do with this restriction

  • + well duh,

  • eval/exec Wasn't going to let you get away with that

  • Numbers, They might be more useful than you think

  • String literals

  • len

  • =, No assigning variables

  • >,<,==. . . I have left you with no comparisons

  • *,-,/,%,^,|,>>,<< The only operators available are ~ and &

  • __foo__, None of those fancy double underscore methods are allowed.

My solution

So now that xnor has cracked it in a way I am sufficiently satisfied with I am going to reveal my solution

r,o:(o and f(~(~r&~o)&~(r&o),int(`r`[:r&~r].join([`dict()`[r&~r],`r&~r`,`dict([(r&~r,r&~r)])`[int(`~([]in[[]])`[[]in[[]]:])],`min`[[]in[[]]],`dict()`[~(r&~r)],`r&~r`]).format(r&o),int(`~([]in[[]])`[[]in[[]]:]))))or r

Surprise, surprise its a hulking pile of gibberish. Rather than break this down I'm going to go through the process of how I made this.

I started with a pretty standard addition algorithm

r,o:(o and f(r^o,r&o<<1))or r

Then I used a bitwise trick for representing ^ with |,&,~.

r,o:(o and f((r|o)&~(r&o),r&o<<1))or r

I used another bitwise trick to get rid of the |

r,o:(o and f(~(~r&~o)&~(r&o),r&o<<1))or r

Now all thats left is the <<, shouldn't be too hard, right? Well get ready for a bumpy ride. To replace the bitshift I used strings to append a zero to the end of its binary representation

r,o:(o and f(~(~r&~o)&~(r&o),int(bin(r&o)[2:]+"0",2)))or r

This has a few problems but the primary one is using addition, so I worked around this by using a format instead

r,o:(o and f(~(~r&~o)&~(r&o),int("{}0".format(bin(r&o)[2:]),2)))or r

We are not allowed to use bin, so I used string formatting to convert to binary.

r,o:(o and f(~(~r&~o)&~(r&o),int("{0:b}0".format(r&o),2)))or r

Since string literals are forbidden I have to build the string {0:b}0 out of parts made with back ticks and join them together. 

r,o:(o and f(~(~r&~o)&~(r&o),int("".join(["{","0",":","b","}","0"]).format(r&o),2)))or r

The empty string is pretty easy, you can just do

`r`[:0]

The zeros were

`0`

and the {:} were all grabbed from dictionaries.

r,o:(o and f(~(~r&~o)&~(r&o),int("".join([`dict()`[0],`0`,`dict([(0,0)])`[2],"b",`dict()`[-1],`0`]).format(r&o),2)))or r

b seems pretty hard to get, its not in our character set, so how are we supposed to get an object that has a b in its repr? Well here's how: When you use repr on a builtin function you get something that looks like 

<built-in function name>

And thats from where we'll get our b.

r,o:(o and f(~(~r&~o)&~(r&o),int("".join([`dict()`[0],`0`,`dict([(0,0)])`[2],`min`[1],`dict()`[-1],`0`]).format(r&o),2)))or r

Now all thats left are numbers, I only need -1, 0, 1, and 2 so here's how I represented them:

-1 = ~(r&~r)
 0 = r&~r
 1 = []in[[]]
 2 = `~([]in[[]])`[[]in[[]]:]

2 could actually be a byte shorter as

```r&~r```.find(`r&~r`)

based on @Blender's suggestions in the comments, but I didn't think of this until after the fact.

So we substitute these numbers in

r,o:(o and f(~(~r&~o)&~(r&o),int(`r`[:r&~r].join([`dict()`[r&~r],`r&~r`,`dict([(r&~r,r&~r)])`[int(`~([]in[[]])`[[]in[[]]:])],`min`[[]in[[]]],`dict()`[~(r&~r)],`r&~r`]).format(r&o),int(`~([]in[[]])`[[]in[[]]:]))))or r

And thats the crack.

Tags:

Code Golf

Arithmetic

Cops And Robbers

Recent Posts