NB. long molecule http://adventofcode.com/day/19

t=: cutLF CR-.~fread {:ARGV NB. array of input lines

subs=: (' '&cut@>) (+./@('=>'&E.@>) # ]) t NB. those with '=>'
form=: ,>((40&<@#@>) # ]) t NB. the one very long (>40)

subst=: 3 : 0 NB. substitute in str from pos length len to new str
  'str pos len new'=.y
  (pos {. str), new, (pos+len) }. str
)

conv=: 4 : 0 NB. apply all substitutions from y to form x, giving set of forms
 res=.0$<''
 for_s. y do.
   'old xxx new'=. s
   for_p. old I.@E. x do. NB. for all substrings old in x
     res=.res, <subst x;p;(#old);new
   end.
 end.
 res
)

echo # ~. form conv subs

leads=: 4 : 0 NB. all subs out of y which could result into form x
  NB. return array of pairs (sub-index-in-subs(y), pos-in-string(x))
  res=.0$<0 0
  for_s. y do.
    'old xxx new'=. s
    for_p. new I.@E. x do.
      res=.res, <s_index,p
    end.
  end.
  res
)

doit=: 4 : 0 NB. x - depth
  'form subs'=.y
  for_ip. form leads subs do. NB. for all candidate pairs
    'idx pos'=. >ip
    'old xxx new'=. idx{subs
    newform=. subst form;pos;(#new);old
    if. 1=#newform do. if. (,'e')-:newform do. >:x return. end. end.
    if. n=. (>:x) doit newform;<subs do. n return. end.
  end.
  0
)

echo 0 doit form;<subs

exit 0