Skip to content

Instantly share code, notes, and snippets.

@rishabg

rishabg/dimepenny.rb

Last active September 18, 2020 16:44
Show Gist options
  • Save rishabg/18bdc35ba0a2654178a9ef5b8b6c6906 to your computer and use it in GitHub Desktop.
Save rishabg/18bdc35ba0a2654178a9ef5b8b6c6906 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
dimepenny.rb
# needs ruby > 2.6
# if we are allowed to move only 'pairs' of coins (not necessarily one coin of each type) from the ends
$possibilities = 0
def find_move(initial_input, input, output, iteration)
return nil if initial_input == input && iteration > 0
return nil if iteration > 5
$possibilities += 1
return [input] if input == output
left = find_move(initial_input, input.rotate(2), output, iteration + 1)
return [input].shift(left) unless left.nil?
right = find_move(initial_input, input.rotate(-2), output, iteration + 1)
return [input].shift(right) unless right.nil?
left || right
end
input = ['p', 'd', 'p', 'd', 'p']
output = ['p', 'p', 'p', 'd', 'd']
result = find_move(input, input, output, 0)
puts "no solution in #{$possibilities} possibilities" if result.nil?
puts result.map{|x| puts "#{x}"} unless result.nil?
########################################################
# if we are allowed to pick a consequtive dime/penny pair from anywhere and insert anywhere
$possibilities = 0
def find_move(input, output, iteration, so_far = [])
return nil if iteration > 5
puts "#{iteration} : #{input}"
$possibilities += 1
return so_far if input == output
candidates = find_candidates(input)
found = nil
candidates.each do |candidate|
res = find_move(candidate, output, iteration + 1, so_far + [candidate])
if(res != nil)
found = res
break
end
end
found
end
def find_candidates(arr)
indexes_of_change = find_indexes(arr)
options = []
indexes_of_change.each do |index|
before = arr.slice(0, index)
items = arr.slice(index, 2)
after = arr[(index+2)...]
removed_arr = (before + after)
removed_arr.length.times do |i|
options << removed_arr.dup.insert(i, *items)
end
end
options.uniq - arr
end
def find_indexes(arr)
res = []
arr.each_with_index do |v, index|
next if index == arr.length - 1
res << index if v != arr[index + 1]
end
res
end
input = ['p', 'd', 'p', 'd', 'p']
output = ['p', 'p', 'p', 'd', 'd']
result = find_move(input, output, 0)
puts "no solution in #{$possibilities} possibilities" if result.nil?
puts result.map{|x| puts "#{x}"} unless result.nil?
#["p", "d", "p", "d", "p"],
#["p", "p", "d", "d", "p"],
#["p", "d", "p", "p", "d"],
#["p", "p", "p", "d", "d"]
# OR
######################################################################
$possibilities = 0
# if we are allowed to pick a consequtive dime/penny pair from anywhere and insert anywhere
def find_move(input, output, iteration, so_far = [])
return nil if iteration > 5
puts "#{iteration} : #{input}"
$possibilities += 1
return so_far if input == output
candidates = find_candidates(input)
prob = candidates.map do |candidate|
res = find_move(candidate, output, iteration + 1, so_far + [candidate])
res&.chunk(&:itself)&.map(&:first)
end.compact
prob.sort{|x| x.length}.first
end
#find_move(input, output, 0)
def find_candidates(arr)
indexes_of_change = find_indexes(arr)
options = []
indexes_of_change.each do |index|
before = arr.slice(0, index)
items = arr.slice(index, 2)
after = arr[(index+2)...]
removed_arr = (before + after)
removed_arr.length.times do |i|
options << removed_arr.dup.insert(i, *items)
end
end
options.uniq - arr
end
def find_indexes(arr)
res = []
arr.each_with_index do |v, index|
next if index == arr.length - 1
res << index if v != arr[index + 1]
end
res
end
input = ['p', 'd', 'p', 'd', 'p']
output = ['p', 'p', 'p', 'd', 'd']
result = find_move(input, output, 0)
puts "no solution in #{$possibilities} possibilities" if result.nil?
puts result.map{|x| puts "#{x}"} unless result.nil?
#["p", "d", "p", "d", "p"],
#["p", "d", "d", "p", "p"],
#["p", "d", "p", "d", "p"],
#["p", "p", "d", "d", "p"],
#["p", "p", "d", "p", "d"],
#["p", "p", "p", "d", "d"]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment