# jamii/icfp2010

Fetching contributors…
Cannot retrieve contributors at this time
183 lines (150 sloc) 4.86 KB
 import re import random re_wire = re.compile(r'X|[0-9]+[LR]') def l(i): return '%sL' % i def r(i): return '%sR' % i def gate(l,r): return ((l + 2*r) % 3, (2 + l*r) % 3) def sublist(xs, ys): for x,y in zip(xs,ys): if x!=y: return False return True class Circuit(object): def __init__(self): # wires is a dict of out_pin:in_pin # rev_wires is a dict of in_pin:out_pin self.wires = {} self.rev_wires = {} self.values = {} def wire(self, out_pin, in_pin): self.wires[out_pin] = in_pin self.rev_wires[in_pin] = out_pin def wire_gate(self, pos, out_pinL, out_pinR): self.wire(l(pos), out_pinL) self.wire(r(pos), out_pinR) def __repr__(self): gates = [] pos = 0 while l(pos) in self.wires and r(pos) in self.wires: gate = '%s%s0#%s%s' % ( self.rev_wires[l(pos)], self.rev_wires[r(pos)], self.wires[l(pos)], self.wires[r(pos)], ) gates.append(gate) pos += 1 return '%s:\n%s:\n%s' % (self.wires['X'], ',\n'.join(gates), self.rev_wires['X']) @staticmethod def from_string(string): circuit = Circuit() lines = string.splitlines() circuit.wire('X', re_wire.match(lines[0]).group(0)) pos = 0 for line in lines[1:-1]: wires = re_wire.findall(line) circuit.wire(wires[0], l(pos)) circuit.wire(wires[1], r(pos)) circuit.wire(l(pos), wires[2]) circuit.wire(r(pos), wires[3]) pos += 1 circuit.wire(re_wire.match(lines[-1]).group(0), 'X') return circuit def input(self, trit): self.values[self.wires['X']] = trit def step(self): pos = 0 while l(pos) in self.wires and r(pos) in self.wires: inL = self.values.get(l(pos), 0) inR = self.values.get(r(pos), 0) outL, outR = gate(inL,inR) self.values[self.wires[l(pos)]] = outL self.values[self.wires[r(pos)]] = outR pos += 1 return self.values['X'] def run(self, inputs): self.values = {} for i in inputs: self.input(i) output = self.step() yield output def random(self, n): out_pins = [l(pos) for pos in xrange(0,n)] + [r(pos) for pos in xrange(0,n)] + ['X'] in_pins = [l(pos) for pos in xrange(0,n)] + [r(pos) for pos in xrange(0,n)] + ['X'] random.shuffle(out_pins) random.shuffle(in_pins) for (in_pin, out_pin) in zip(in_pins, out_pins): self.wire(in_pin, out_pin) def add0(self, pos, in_pin): self.wire_gate(pos, in_pin, l(pos+1)) self.wire_gate(pos+1, l(pos+2), r(pos+2)) self.wire_gate(pos+2, r(pos), r(pos+1)) return (pos+3, l(pos)) def add1(self, pos, in_pin): self.wire_gate(pos, r(pos+2), r(pos+1)) self.wire_gate(pos+1, in_pin, l(pos+2)) self.wire_gate(pos+2, l(pos), r(pos)) return (pos+3, l(pos+1)) def add2(self, pos, in_pin): self.wire_gate(pos, l(pos+1), r(pos+1)) self.wire_gate(pos+1, r(pos+2), r(pos)) self.wire_gate(pos+2, in_pin, l(pos)) return (pos+3, l(pos+2)) def gate0(self, pos, in_pin): self.wire_gate(pos, in_pin, r(pos)) return (pos+1, l(pos)) def add_trit(self, pos, in_pin, trit): if trit == 0: return self.add0(pos, in_pin) if trit == 1: return self.add1(pos, in_pin) if trit == 2: return self.add2(pos, in_pin) # def add_prefix(self, pos, in_pin, trits): # fucking weird way to write this def reverse(self, req_output, input): print input output = list(self.run(input)) if output == req_output: return True elif sublist(output, req_output): for trit in [0,1,2]: input.append(trit) if self.reverse(req_output, input): return True else: input.pop() return False def prefix(trits): circuit = Circuit() pos = 0 in_pin = 'X' for trit in trits: pos, in_pin = circuit.add_trit(pos, in_pin, trit) circuit.wire('X', in_pin) return circuit from post import * import time def spamFuel(fuel): cars = car_list() cars.reverse() for car in cars: try: print car print postFuel("2416", fuel) except Exception, e: print e key = [1,1,0,2,1,2,1,0,1,1,2,1,0,1,2,2,1] minispam = [1,1,1,1,1] maxispam = [2,2,2,2,0,0,0,1] + 7 * [1,1,1] solutions = { "2416" : [1,1,1,1,1] } if __name__ == '__main__': fuel = minispam print fuel c = prefix(key + fuel) spamFuel(repr(c))