First parse with regex to make into a list
#+begin_src emacs-lisp :results none
  (require 'dash)
  (with-temp-buffer
      (insert-file-contents "input")
      (goto-char (point-min))
      (replace-regexp "\\([a-z]+\\),?" "\"\\1\"")
      (goto-char (point-min))
      (insert "(setq avail '(")
      (end-of-line)
      (insert ") patterns '(")
      (goto-char (point-max))
      (insert "))")

      (eval-buffer))

#+end_src

Here we define a caching advice; this implementation works under the
assumption that the original function accepts one string as a
parameter
#+begin_src emacs-lisp :results none
  (setq cache nil)

  (defun cached (fun r)
    (if (assoc-string r cache) (cdr (assoc-string r cache))
      (let ((result (funcall fun r)))
        (push (cons r result) cache)
        result)))
#+end_src

Here we recur down the tree obtained by splitting with all possible
prefixes.  This is for part 1
#+begin_src emacs-lisp
  (defun suffixes (word)
    (--map (substring word (length it)) (--filter (string-prefix-p it word) avail)))

  (defun possible-p (word)
    (or (string= "" word)
        (-any #'possible-p (suffixes word))))

  (advice-add #'possible-p :around 'cached)

  (length (-filter #'possible-p patterns))
#+end_src

#+RESULTS:
: 226

This is for part 2;
#+begin_src emacs-lisp
  (defun suffixes (word)
    (--map (substring word (length it)) (--filter (string-prefix-p it word) avail)))

  (defun possible-arrangements (word)
    (if (string= "" word) 1
      (-sum (-map #'possible-arrangements (suffixes word)))))

  (advice-add #'possible-arrangements :around #'cached)

  (-sum (-map #'possible-arrangements patterns))
#+end_src

#+RESULTS:
: 601201576113503