Naive solution for owst's combination lock problem using BFS

lock_problem_bfs.rb

# frozen_string_literal: true

# Lock Problem
#   * We're given a 4-digit combination lock and a known correct unlock code.
#   * The allowed moves are to rotate any dial, or any two, three or four
#     adjacent dials by one place in either direction.
#   * We're looking for an efficient algorithm that returns the least number
#     of "moves" required to get to the unlock code. We'd also like the path.
#   * e.g.
#     - It takes 5 moves to get from [1,2,3,4] to [6,6,6,6].
#     - A path acheiving this is:
#       [[1,2,3,4], [2,2,3,4], [3,3,3,4], [4,4,4,4], [5,5,5,5], [6,6,6,6]].
#   * The solution below uses breadth-first search.

require 'benchmark'

module LockProblem
  
  def self.solve(start, target)
    raise ArgumentError.new unless LockCombination.valid?(start)
    raise ArgumentError.new unless LockCombination.valid?(target)

    start = LockCombination.new(start)
    target = LockCombination.new(target)
    LockProblemSolver.new(start).solve(target)
  end

  ALL_COMBINATIONS = ('0000'..'9999').map { |digit_string| digit_string.chars.map(&:to_i) }

  def self.benchmark(ntrials=100)
    times = []
    (1..ntrials).each do |trial|
      puts "Trial #{trial}/#{ntrials}..."
      
      start = ALL_COMBINATIONS.sample
      target = ALL_COMBINATIONS.sample
      
      time = Benchmark.measure { self.solve(start, target) }
      times << time.total
    end
    puts '-----------'
    puts "Complete" 
    puts "#{ntrials} solves in #{times.sum}"
    puts "average solve time: #{times.sum / ntrials}"
  end

  # class describing a lock combination and its neighbours
  class LockCombination

    ALLOWED_DIAL_MOVE_COMBINATIONS = [
      [0], [1], [2], [3],
      [0, 1], [1, 2], [2, 3],
      [0, 1, 2], [1, 2, 3],
      [0, 1, 2, 3]
    ]
  
    attr_reader :digits
  
    def initialize(digits)
      raise ArgumentError.new unless self.class.valid?(digits)
  
      @digits = digits
    end
  
    def to_s
      digits.map(&:to_s).join
    end
    
    def eql?(other)
      @digits == other.digits
    end
    alias == eql?

    # important that combinations with the same digits hash to the same value
    # otherwise this takes forever
    def hash
      @digits.hash
    end
  
    def increase_digits(dial_combination)
      raise ArgumentError unless ALLOWED_DIAL_MOVE_COMBINATIONS.include?(dial_combination)
  
      @digits.map.with_index do |digit, index|
        dial_combination.include?(index) ? ((digit + 1) % 10) : digit
      end
    end
  
    def decrease_digits(dial_combination)
      raise ArgumentError unless ALLOWED_DIAL_MOVE_COMBINATIONS.include?(dial_combination)
  
      @digits.map.with_index do |digit, index|
        dial_combination.include?(index) ? ((digit - 1) % 10) : digit
      end
    end
  
    def neighbours
      neighbours = []
      ALLOWED_DIAL_MOVE_COMBINATIONS.each do |dial_combination|
        neighbours << increase_digits(dial_combination)
        neighbours << decrease_digits(dial_combination)
      end
      neighbours.map { |combination| LockCombination.new(combination) }
    end
  
    def self.valid?(digits)
      digits.is_a?(Array) &&
      (digits.length == 4) &&
      digits.all? { |digit| digit.is_a?(Integer) && digit.between?(0, 9) }
    end
  end

  class LockProblemSolver
  
    def initialize(start)
      @start = start
      @waiting = Queue.new(@start)
      @visited = {@start => [@start.to_s]}
    end
    
    # solves with a simple BFS of the graph whose nodes are lock combinations
    # and where nodes are joined if they differ by a valid combination move
    def solve(target)
      while !@waiting.empty?
        
        current = @waiting.dequeue
        if current == target
          path = @visited[current]
          return path, path.length - 1
        end
  
        current.neighbours.each do |neighbour|
          if !@visited[neighbour]
            path = @visited[current] + [neighbour.to_s]
            @visited[neighbour] = path
            @waiting.enqueue(neighbour)
          end 
        end
      end
    end

    private

    # simple queue class; probably there's a library for this
    class Queue
      def initialize(value=nil)
        if value.is_a?(Array)
          @waiting = value 
        elsif value 
          @waiting = [value]
        else
          @waiting = []
        end
      end
  
      def enqueue(item)
        @waiting << item
      end
    
      def dequeue
        @waiting.shift
      end
  
      def empty?
        @waiting.empty?
      end
    end
  end
end

# Uncomment the lines below to run a sample solve
# start = [1,2,3,4]
# target = [9,8,7,6]
# p LockProblem.solve(start, target)
# should print [["1234", "2234", "3234", "4334", "5434", "6544", "7654", "8765", "9876"], 8]

# Uncomment the line below to benchmark the solver over 100 random solves
LockProblem.benchmark