Programming Challenge

File: prehistoric-owl1.jpg (53KB, 432x435px) Image search: [Google]

53KB, 432x435px

Quick! Write a solver for this mutagen puzzle or the cloned prehistoric owl will pluck out your eyes!

import re

data = [
'exit1 rd jv if vd wu r5 jj j9 rc j7 xs dw km',
'ovid3 j7 wu if xs jj -f5 -km -xu -dw',
'echo3 if rd xs xu km -jv -va -nj -dw -j9',
'echo2 km rd rc wu jv sb gs -uo -r5 -xs',
'echo4 dw sb uo r5 vd xs -gs -xu',
'soli1 if jv j9 r5 -dw -nj -rd',
'soli2 jv uo xs nj',
'ovid2 xu dw jj j9 rc gs -nj',
'io3   if r5 km vd xu -jj -va',
'io2   jj sb j7 uo',
'heli3 va sb rd vd -r5',
'heli2 rd dw km -nj -gs -sb',
'echo1 gs dw wu nj -km',
'heli1 j7 rc -jj -if -nj -uo',
'io1   nj wu jj',
'ovid1 rd jv if xu vd'
]

data = [re.split(r'\s+', d.lower()) for d in data]
target = data[0][1:]

The first word in each data-string is the name of the mutagen (exit1, ovid3, echo3, ...).

Starting from an empty sequence, reproduce the target sequence of the exit1 mutagen from the other mutagens to kill the owl:

['rd', 'jv', 'if', 'vd', 'wu', 'r5', 'jj', 'j9', 'rc', 'j7', 'xs', 'dw', 'km']

You are not allowed to use the exit1 mutagen.

Applying a mutagen appends its new and unprefixed dna strings to the previous sequence. Strings already present in the sequence are NOT added again. Then the dna strings prefixed by "-" are removed.
So a mutagen adds its unprefixed dna strings and removes the ones prefixed by "-".

For instance, applying ovid1 and then echo3 to an empty sequence gives these results:

[] # empty
['rd', 'jv', 'if', 'xu', 'vd'] # after ovid1
['rd', 'if', 'xu', 'vd', 'xs', 'km'] # then after echo3

Write a program that finds which mutagens to apply in which order to reproduce the target sequence (exit1) und use it to solve the puzzle. Your program should finish within 30 seconds, but it's possible to write one that finishes within 1.