Return to Answer

HPR, written in Python 3 (Cracked by TheNumberOne)

HPR, written in Python 3 (Cracked by TheNumberOne)

HPR, written in Python 3 (Cracked by @TheNumberOne)

import sys def parse(prog): "Parse a prefix of a string into an AST. Return it and the remaining input." ret = [] while prog: if prog[0] in "#!": sub1, prog1 = parse(prog[2:]) sub2, prog2 = parse(prog1[1:]) ret += [prog[0],sub1,sub2] prog = prog2 elif prog[0] == ')': prog = prog[1:] break else: ret += [prog[0]] prog = prog[1:] return ret, prog def intp(ast, L_env, N_env): "Interpret the AST on an environment, return the resulting environment." ptr = 0 while ptr < len(ast): cmd = ast[ptr] if cmd == '*': N_env = N_env | set(L[0] for L in L_env if L) L_env = set(L[1:] for L in L_env) ptr += 1 elif cmd == '-': N_env = set(N-1 for N in N_env if N>0) ptr += 1 elif cmd == '$': L_env = set(L[1:]+L[:1] for L in L_env) ptr += 1 elif cmd == '!': # Speed optimization cond = ast[ptr+2] if cond == ['#', ast[ptr+1], []]: L_next, N_next = intp(ast[ptr+1], L_env, N_env) while L_next != L_env or N_next != N_env: L_env, N_env = L_next, N_next L_next, N_next = intp(ast[ptr+1], L_env, N_env) else: while True: L_test, N_test = intp(cond, L_env, N_env) if not L_test and not N_test: break L_env, N_env = intp(ast[ptr+1], L_env, N_env) ptr += 3 elif cmd == '#': L_env1, N_env1 = intp(ast[ptr+1], L_env, N_env) L_env2, N_env2 = intp(ast[ptr+2], L_env, N_env) L_env = L_env1 ^ L_env2 N_env = N_env1 ^ N_env2 ptr += 3 elif cmd == '?': print(L_env | N_env) ptr += 1 else: ptr += 1 return L_env, N_env def main(p, L): "Run the program on the input, return the output." # Parse the input list L = ''.join(c for c in L if c in "01") while "00" in L: L = L.replace("00","0") L = [-2] + [i for i in range(len(L)-1) if L[i:i+2] == "10"] L = tuple(b-a-1 for (a,b) in zip(L, L[1:])) # Parse the program ast = parse(p)[0] L_env, N_env = intp(ast, set([L]), set()) return '1'*(len(L_env) + len(N_env)) if __name__ == "__main__": filename = sys.argv[1] f = open(filename, 'r') prog = f.read() f.close() L = input() print(main(prog, L)) 

HPR, written in Python 3 (Cracked by TheNumberOne)

import sys def parse(prog): "Parse a prefix of a string into an AST. Return it and the remaining input." ret = [] while prog: if prog[0] in "#!": sub1, prog1 = parse(prog[2:]) sub2, prog2 = parse(prog1[1:]) ret += [prog[0],sub1,sub2] prog = prog2 elif prog[0] == ')': prog = prog[1:] break else: ret += [prog[0]] prog = prog[1:] return ret, prog def intp(ast, L_env, N_env): "Interpret the AST on an environment, return the resulting environment." ptr = 0 while ptr < len(ast): cmd = ast[ptr] if cmd == '*': N_env = N_env | set(L[0] for L in L_env if L) L_env = set(L[1:] for L in L_env) ptr += 1 elif cmd == '-': N_env = set(N-1 for N in N_env if N>0) ptr += 1 elif cmd == '$': L_env = set(L[1:]+L[:1] for L in L_env) ptr += 1 elif cmd == '!': # Speed optimization cond = ast[ptr+2] if cond == ['#', ast[ptr+1], []]: L_next, N_next = intp(ast[ptr+1], L_env, N_env) while L_next != L_env or N_next != N_env: L_env, N_env = L_next, N_next L_next, N_next = intp(ast[ptr+1], L_env, N_env) else: while True: L_test, N_test = intp(cond, L_env, N_env) if not L_test and not N_test: break L_env, N_env = intp(ast[ptr+1], L_env, N_env) ptr += 3 elif cmd == '#': L_env1, N_env1 = intp(ast[ptr+1], L_env, N_env) L_env2, N_env2 = intp(ast[ptr+2], L_env, N_env) L_env = L_env1 ^ L_env2 N_env = N_env1 ^ N_env2 ptr += 3 elif cmd == '?': print(L_env | N_env) ptr += 1 else: ptr += 1 return L_env, N_env def main(p, L): "Run the program on the input, return the output." # Parse the input list L = ''.join(c for c in L if c in "01") while "00" in L: L = L.replace("00","0") L = [-2] + [i for i in range(len(L)-1) if L[i:i+2] == "10"] L = tuple(b-a-1 for (a,b) in zip(L, L[1:])) # Parse the program ast = parse(p)[0] L_env, N_env = intp(ast, set([L]), set()) return '1'*(len(L_env) + len(N_env)) if __name__ == "__main__": filename = sys.argv[1] f = open(filename, 'r') prog = f.read() f.close() L = input() print(main(prog, L)) 

My solution

My reference solution is 484 bytes long, so quite short compared to TheNumberOne's 3271-byte program. This is most likely because of the sophisticated and awesome macro system TheNumberOne developed for programming in HPR. The main idea in both our programs is similar:

1. Find out how to produce the maximum element of a list.
2. To remove the maximum element, rotate the list until the first element equals the maximum, then pop it.
3. Remove the maximum twice, then print the new maximum element.

However, as far as I can tell, the exact implementation details are quite different. Here's my solution:

!($)(!(-)(#(-)())#(!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())#(-)(#(!(-)(#(-)()))()))(*)#(!(-)(#(-)()))())*!(-)(#(-)())!($)(!(-)(#(-)())#(!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())#(-)(#(!(-)(#(-)()))()))(*)#(!(-)(#(-)()))())*!(-)(#(-)())!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())-#(!(-)(#(-)()))() 

And here's the commented Python program that produces it (nothing fancy here, just basic string manipulation to get rid of all the repetition):

# No numbers in the environment no_nums = "#(-)()" # No non-empty lists in the environment no_lists = "#(*)()" # Remove all numbers from the environment del_nums = "!(-)(" + no_nums + ")" # Remove all lists from the environment del_lists = "#(" + del_nums + ")()" # Splat the list to the environment: # pop the list until it's empty and delete the empty list, # then take symmetric difference with all numbers removed splat = "#(!(*)(" + no_lists + ")" + del_lists + ")(" + del_nums + ")" # Put into the environment all numbers up to list maximum: # decrement and splat until a fixed point is reached. # Without the speed optimization, this is very slow if the list elements are large. splat_upto = "!(-" + splat + ")(#(-" + splat + ")())" # Copy maximum element to environment: # take all elements up to maximum, # then take symmetric difference of decrement and list deletion copy_max = splat_upto + "#(-)(" + del_lists + ")" # Delete maximum element from list: # rotate until first element is maximal, then pop and delete it del_max = "!($)(" + del_nums + "#(" + copy_max + ")(*)" + del_lists + ")*" + del_nums # Full program: # remove the maximum twice, then produce all numbers up to maximum, # then decrement and remove lists. The environment will contain exactly # the integers from 0 to third largest - 1, and their number is printed. main = del_max + del_max + splat_upto + "-" + del_lists print(main) 

HPR, written in Python 3

HPR, written in Python 3 (Cracked by @TheNumberOne)