https://projecteuler.net/problem=490

frogs.rb

require 'set'

class Set
  def to_csv
    self.reduce("") do |accum, el|
      accum << ",#{el}"; accum
    end[1..-1]
  end
end

class Frogs
  attr_reader :seen_csv, :stone, :num_stones

  def self.solve(num_stones)
    Frogs.new("1", 1, num_stones).num_paths
  end

  def self.cache
    @cache ||= {}
  end

  def self.reset_cache
    @cache = {}
  end

  def cache_paths(paths)
    self.class.cache[to_s] = paths
  end

  # We represent the problem's state as a csv of sorted stone numbers,
  # the current stone position, and the total number of stones
  def initialize(seen_csv, stone, num_stones)
    @seen_csv, @stone, @num_stones = seen_csv, stone, num_stones
  end

  def seen
    @seen ||= SortedSet.new(seen_csv.split(",").map(&:to_i))
  end

  def seen?(move)
    seen.include?(move)
  end

  def all_moves
    [-3, -2, -1, 1, 2, 3].map { |offset| stone + offset }
  end

  def in_bounds?(stone)
    stone > 0 && stone <= num_stones
  end

  def legal_moves
    all_moves.select { |move| in_bounds?(move) && !seen?(move) }
  end

  def to_s
    "#{seen.to_csv}|#{stone}"
  end

  def cached_num_paths
    self.class.cache[to_s]
  end

  def find_num_paths
    # base case - done with search
    return 1 if seen.size == num_stones && stone == num_stones

    old_stone = stone

    legal_moves.reduce(0) do |paths, move|
      # make move
      seen.add(move)
      @stone = move

      paths += num_paths

      # unmake move
      seen.delete(move)
      @stone = old_stone

      paths
    end
  end

  def num_paths
    cached = cached_num_paths
    return cached if cached

    paths = find_num_paths
    cache_paths(paths)

    paths
  end
end

frogs2.rb

# Paths matrix structure:
# col 1 is solution to frog problem starting at stone 1
# col 2 is solution starting at stone 2
# col 3 is solution starting at stone 3

# By examining cases we can draw the recursive formulae (f = col1, g = col2, h = col3)
# f(n + 3) = f(n + 2) + g(n + 2) + h(n + 2)
# g(n + 3) = g(n) + f(n + 1) + f(n) + f(n - 1) + f(n - 2) + g(n + 1) + g(n - 1)
# h(n + 3) = h(n) + 2f(n) + 2f(n - 1) + f(n - 2) - f(n - 4) + g(n) + g(n - 2)
# These correspond to the matrix nodes below

class Array
  def sum
    reduce(0, :+)
  end
end

class Frogs
  START_NUM_STONES = 8

  PATHS_MATRIX = [
    [1,   0,  0],
    [1,   0,  0],
    [2,   2,  0],
    [6,   4,  4],
    [14,  8,  6],
    [28,  17, 11],
    [56,  37, 25]
  ]

  MatNode = Struct.new(:row, :col, :weight)

  SECOND_NODES = [
    MatNode.new(5, 0, 1),
    MatNode.new(5, 1, 1),
    MatNode.new(4, 0, 1),
    MatNode.new(4, 1, 1),
    MatNode.new(3, 0, 1),
    MatNode.new(3, 1, 1),
    MatNode.new(2, 0, 1)
  ]

  THIRD_NODES = [
    MatNode.new(4, 2, 1),
    MatNode.new(4, 0, 2),
    MatNode.new(3, 0, 2),
    MatNode.new(2, 0, 1),
    MatNode.new(0, 0, -1),
    MatNode.new(4, 1, 1),
    MatNode.new(2, 1, 1)
  ]

  def self.solve(num_stones)
    Frogs.new(num_stones).find_num_paths
  end

  attr_reader :num_stones, :paths_matrix

  def initialize(num_stones)
    @num_stones, @paths_matrix = num_stones, PATHS_MATRIX.dup
  end

  def next_first
    paths_matrix.last.sum
  end

  def sum_mat_nodes(nodes)
    nodes.map do |node|
      paths_matrix[node.row][node.col] * node.weight
    end.sum
  end

  def next_second
    sum_mat_nodes(SECOND_NODES)
  end

  def next_third
    sum_mat_nodes(THIRD_NODES)
  end

  def next_row
    [next_first, next_second, next_third]
  end

  def next_level
    paths_matrix.push(next_row)
    paths_matrix.shift
  end

  def find_num_paths
    level = START_NUM_STONES

    while level < num_stones
      next_level
      level += 1
    end

    paths_matrix[6][0]
  end
end