Solving a logic puzzle using a graph. https://blog.shalvah.me/posts/solving-a-logic-puzzle

game.rb

# A man needs to get three items across a river:
#   a goose, a big bag of beans, and a fox.
#
# If left alone unsupervised with the beans, the goose will eat the beans.
# If left alone unsupervised with the goose, the fox will eat the goose.
# Only the man and one other item are all that will fit in the boat.
#
# Can the man get across the river with their goose, beans, and fox?

require 'set'

class Graph
  def initialize
    @edges = Set[]
    @connections = Hash.new { |h, k| h[k] = Set[] }
  end

  def link(a, b)
    @edges << Set[a, b]
    @connections[a] << b
    @connections[b] << a
  end

  def find_path(from:, to:, traversed: Set[from]) # (depth-first traversal)
    @connections[from].
      reject { |node| traversed.include?(node) }.
      each do |node|
      return [to] if node == to

      traversed << node
      path = find_path(from: node, to:, traversed:)

      return [node] + path if path
    end

    nil
  end

  def inspect
    @edges.map do |a_b|
      a, b = a_b.to_a
      "#{a} ----> #{b}"
    end.join("\n")
  end
end

State = Struct.new(:bank_1, :boat, :bank_2, keyword_init: true) do
  def valid?
    return false if boat.size > 2
    return false if !boat.empty? && !boat.include?(:man)

    [:bank_1, :bank_2].each do |position|
      location = self[position]
      return false if location.include?(:goose) &&
        location.include?(:fox) && !location.include?(:man)
      return false if location.include?(:beans) &&
        location.include?(:goose) && !location.include?(:man)
    end
  end

  def invalid? = !valid?

  def to_s
    print = ->(set) { set.to_a.map { _1.to_s[0].upcase }.sort.join(',') }
    "{bank_1=#{print.(bank_1)}, boat=#{print.(boat)}, bank_2=#{print.(bank_2)}}"
  end

  alias inspect to_s

  def possible_transitions
    transitions = []
    if bank_1.include?(:man)
      other_items = bank_1 - Set[:man]
      transitions << State[
        bank_1: other_items, boat: Set[:man], bank_2: bank_2.dup
      ]
      other_items.each do |item|
        transitions << State[
          bank_1: other_items - Set[item], boat: Set[:man, item], bank_2: bank_2.dup
        ]
      end
    elsif bank_2.include?(:man)
      other_items = bank_2 - Set[:man]
      transitions << State[
        bank_1: bank_1.dup, boat: Set[:man], bank_2: other_items
      ]
      other_items.each do |item|
        transitions << State[
          bank_1: bank_1.dup, boat: Set[:man, item], bank_2: other_items - Set[item]
        ]
      end
    else # man was on boat, crosses to one of the banks
        transitions << State[
          bank_1: bank_1 + boat, boat: Set[], bank_2: bank_2.dup
        ]
        transitions << State[
          bank_1: bank_1.dup, boat: Set[], bank_2: bank_2 + boat
        ]
    end

    transitions
  end
end

initial_state = State[
  bank_1: Set[:man, :goose, :beans, :fox], boat: Set[], bank_2: Set[]
]
graph = Graph.new

# Generate possible states (breadth-first traversal)
visited_states = Set[initial_state]
states_to_traverse = [initial_state]

until states_to_traverse.empty?
  states_to_traverse = states_to_traverse.flat_map do |current_state|
    current_state.possible_transitions.map do |next_state|
      next nil if next_state.invalid?

      graph.link(current_state, next_state)

      next nil if visited_states.include? next_state

      visited_states << next_state
      next_state
    end.compact
  end
end


# p visited_states.map()
# p graph

# Find a path
path = [initial_state] + graph.find_path(
  from: initial_state,
  to: State[bank_1: Set[], boat: Set[], bank_2: Set[:man, :fox, :goose, :beans]]
)

puts path.join("\n-->")