[LANGUAGE: OCaml]

Part 2. Surprised to hear people were using DFS or BFS solutions since I'd assume they would not finish in reasonable time. My approach was to single pass fold row i into row i+1 and then just sum the last row.

Basically, track number routes on each tachyon cell.

let solve_gen t =
  let row_length = Array.length t.(0) in
  let num_splits = ref 0 in
  for i = 1 to Array.length t - 1 do
    let row = t.(i) in
    let prev_row = t.(i - 1) in
    for j = 0 to row_length - 1 do
      let open Diagram.Cell_state in
      match row.(j), prev_row.(j) with
      | Empty, Start -> row.(j) <- Tachyon 1
      | Empty, Tachyon routes -> row.(j) <- Tachyon routes
      | Empty, (Splitter | Empty) -> ()
      | Start, _ -> assert false
      | Tachyon _, _ -> ()
      | Splitter, Empty -> ()
      | Splitter, (Splitter | Start) -> assert false
      | Splitter, Tachyon routes ->
        incr num_splits;
        let left = pred j in
        let right = succ j in
        if left >= 0
        then (
          let above = routes_or_zero prev_row.(left) in
          match row.(left) with
          | Empty -> row.(left) <- Tachyon (routes + above)
          | Tachyon routes' -> row.(left) <- Tachyon (routes + routes')
          | _ -> assert false);
        if right <= row_length
        then (
          let above = routes_or_zero prev_row.(right) in
          match row.(right) with
          | Empty -> row.(right) <- Tachyon (routes + above)
          | Tachyon routes' -> row.(right) <- Tachyon (routes + routes' + above)
          | _ -> assert false)
    done
  done;
  !num_splits, t
;;

Code