#!/usr/bin/env python3

import sys


def replace_ins(gate, gates, inp):
    g0, f, g1 = gate.split(' ')
    if g0 in inp and g1 in inp: return inp[g0] + ' ' + f + ' ' + inp[g1]
    elif g0[0] not in ['x', 'y'] and g1[0] in ['x', 'y']:
        return '(' + replace_ins(gates[g0], gates, inp) + ')' + ' ' + f + ' ' + inp[g1]
    elif g0[0] in ['x', 'y'] and g1[0] not in ['x', 'y']:
        return inp[g0] + ' ' + f + ' ' + '(' + replace_ins(gates[g1], gates, inp) + ')'
    else:
        return '(' + replace_ins(gates[g0], gates, inp) + ')' + ' ' + f + ' ' + '(' + replace_ins(gates[g1], gates, inp) + ')'


if __name__ == '__main__':
    values, gates = open(sys.argv[1]).read().split('\n\n')
    ins = {v.split(': ')[0]: v.split(': ')[1] for v in values.split('\n')}
    gates = {g.split(' -> ')[1]: g.split(' -> ')[0].lower().replace('xor', '^') for g in gates.split('\n')[:-1]}
    out = {}
    for g in gates.keys():
        exec('out[g] = ' + replace_ins(gates[g], gates, ins))
    
    # for g in gates.keys():
    #     g0, f, g1 = gates[g].split(' ')
    #     print(g, g0, f, g1)
    #     print(out[g])

    # challenge 1
    res1 = 0
    for (o,v) in sorted(out.items(),key=lambda x: x[0],reverse=True):
        if o.startswith('z'): res1 = (res1 << 1) | v
    print(f"challenge 1:\n{res1}\n")

    # challenge 2, empiric solution
    x, y = 0, 0
    for bit in [int(v) for (o,v) in sorted(ins.items(),key=lambda x: x[0],reverse=True) if o.startswith('x')]:
        x = (x << 1) | bit
    for bit in [int(v) for (o,v) in sorted(ins.items(),key=lambda x: x[0],reverse=True) if o.startswith('y')]:
        y = (y << 1) | bit

    res2 = ','.join(sorted(['dkr', 'z05', 'z15', 'htp', 'ggk', 'rhv', 'hhh', 'z20']))
    print(f"challenge 2:\n{res2}")