Skip to content

Instantly share code, notes, and snippets.

@tkmharris
Last active January 9, 2023 19:11
Show Gist options
  • Save tkmharris/43e443bca83bb90358d0a08b134bf586 to your computer and use it in GitHub Desktop.
Save tkmharris/43e443bca83bb90358d0a08b134bf586 to your computer and use it in GitHub Desktop.
Naive solution for owst's combination lock problem using BFS
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment