Skip to content

Instantly share code, notes, and snippets.

@sfcgeorge
Last active January 11, 2022 09:09
Show Gist options
  • Save sfcgeorge/0e4d2977ebcdd050927c to your computer and use it in GitHub Desktop.
Save sfcgeorge/0e4d2977ebcdd050927c to your computer and use it in GitHub Desktop.
Classic river crossing problem with both Python and Ruby implementations and ASCII output.
_##_
(..)
/ ~ \
|| ||
m|||m
|||
n^n
_.
)''
/ |
,_f_)\\
((
//'___/)
\" | |
|"""|
((@))
# There is a river with a boat and a bank on each side; that's how rivers work.
# On the left bank is a farmer with their wolf, goat and a cabbage.
# The farmer keeps the peace, they're like a horse whisperer but for goats.
# If the farmer is not around then the goat will eat the cabbage,
# and the wolf will eat the goat. They must not be paired up alone.
# Only the farmer can row the boat; cabbages don't have arms.
# The boat has just 2 spaces because it's cheap, one for farmer one for object.
# The farmer may be in the boat alone but other items must not be left in alone.
# The farmer wants to get all his items to the other bank.
class WGC:
F, W, G, C = 0, 1, 2, 3
start, goal = [[F, W, G, C], [], []] , [[], [], [F, W, G, C]]
def __init__(self, state = None):
self.state = state or self.start[:]
def won(self): return self.state == self.goal
def successors(self):
for move in [[0, 1], [1, 0], [1, 2], [2, 1]]:
for possibility in self.move_source_dest(*move):
if not self.invalid(possibility): yield WGC(possibility)
def move_source_dest(self, s, d):
source_orig = self.state[s][:]
if WGC.F in source_orig: # move one
state = self.state[:]
state[s], state[d] = self.state[s][:], self.state[d][:]
state[s].remove(WGC.F)
state[d].insert(0, WGC.F)
yield state
if WGC.F in source_orig and len(source_orig) >= 2: # move two
source_orig.remove(WGC.F)
for i in range(len(source_orig)):
state = self.state[:]
state[s], state[d] = source_orig[:], self.state[d][:]
state[d] += [WGC.F, state[s].pop(i)]
state[d].sort()
yield state
def invalid(self, s):
# boat has two max
if len(s[1]) > 2: return True
for i in range(3):
# goat must not be left alone with cabbage
if WGC.G in s[i] and WGC.C in s[i] and not WGC.F in s[i]:
return True
# wolf must not be left alone with goat
if WGC.W in s[i] and WGC.G in s[i] and not WGC.F in s[i]:
return True
class Run:
history, won = [], False
def go(self, problem):
self.next(problem, 0)
return self.history
def next(self, problem, depth):
self.history.append(problem.state)
if problem.won():
self.won = True
else:
for s in problem.successors():
if not self.won:
self.history = self.history[:depth+1]
if not s.state in self.history: self.next(s, depth+1)
#for s in Run().go(WGC()): print s
class WGCPrinter:
def __init__(self, n):
with open(n) as f: self.symbols = f.read().split('\n\n')
for i in range(len(self.symbols)):
self.symbols[i] = self.symbols[i].split('\n')
self.symbols[i].reverse()
def width(self, symbol):
return max(len(s) for s in symbol)
def total_width(self):
return sum(self.width(s) +2 for s in self.symbols)
def max_height(self):
return max(len(s) for s in self.symbols)
def print_state(self, state):
lines = []
for i in range(-1, self.max_height()+1): # each row of ascii prints out
row = ""
for p in range(len(state)): # position of the state (bank, boat...)
pos = ""
g = '-' if (i == -1 or i == self.max_height()) and (p != 0 and p != len(state)-1) else ' '
for sym in state[p]: # symbol in the position (wolf, goat...)
s = self.symbols[sym]
pos += g+(s[i] if s[i:i+1] else '').ljust(self.width(s),g)+g
row += g * (self.total_width() - len(pos)) + pos
br = '/' if i == 0 else ('\\' if i == self.max_height()-1 else ('~' if i == -1 or i == self.max_height() else '|'))
bl = '\\' if i == 0 else ('/' if i == self.max_height()-1 else ('~' if i == -1 or i == self.max_height() else '|'))
if p == len(state)-2: row += br + "~("
if p == 0: row += ")~" + bl
lines.insert(0, row)
for line in lines: print line
printer = WGCPrinter('wgc_ascii.txt')
for s in Run().go(WGC()): printer.print_state(s)
# There is a river with a boat and a bank on each side; that's how rivers work.
# On the left bank is a farmer with their wolf, goat and a cabbage.
# The farmer keeps the peace, they're like a horse whisperer but for goats.
# If the farmer is not around then the goat will eat the cabbage,
# and the wolf will eat the goat. They must not be paired up alone.
# Only the farmer can row the boat; cabbages don't have arms.
# The boat has just 2 spaces because it's cheap, one for farmer one for object.
# The farmer may be in the boat alone but other items must not be left in alone.
# The farmer wants to get all his items to the other bank.
class WGC
attr_accessor :state
F, W, G, C = 0, 1, 2, 3
def initialize(state = nil)
@start, @goal = [[F, W, G, C], [], []] , [[], [], [F, W, G, C]]
@state = state || @start[0..-1]
end
def won; @state == @goal; end
def successors
[[0, 1], [1, 0], [1, 2], [2, 1]].map{ |m| move_source_dest(*m) }.flatten(1)
.reject{ |p| invalid(p) }.map{ |p| WGC.new(p) }
end
def move_source_dest(s, d)
possibilities = []
source_orig = @state[s][0..-1]
if source_orig.include?(WGC::F) # move one
state = @state[0..-1]
state[s], state[d] = @state[s][0..-1], @state[d][0..-1]
state[s].delete(WGC::F)
state[d].unshift(WGC::F)
possibilities << state
end
if source_orig.include?(WGC::F) && source_orig.size >= 2 # move two
source_orig.tap{ |o| o.delete(WGC::F) }.size.times do |i|
state = @state[0..-1]
state[s], state[d] = source_orig[0..-1], @state[d][0..-1]
state[d].push(WGC::F).push(state[s].delete_at(i)).sort!
possibilities << state
end
end
possibilities
end
def invalid(s)
# boat has two max
return true if s[1].size > 2
3.times do |i|
# goat must not be left alone with cabbage
return true if s[i].include?(WGC::G) && s[i].include?(WGC::C) &&
!s[i].include?(WGC::F)
# wolf must not be left alone with goat
return true if s[i].include?(WGC::W) && s[i].include?(WGC::G) &&
!s[i].include?(WGC::F)
end
false
end
end
class Run
def initialize; @history, @won = [], false; end
def go(problem)
onwards(problem, 0)
@history
end
def onwards(problem, depth)
@history << problem.state
unless @won = problem.won
problem.successors.each do |s|
unless @won
@history = @history[0..depth]
onwards(s, depth+1) unless @history.include?(s.state)
end
end
end
end
end
class WGCPrinter
def initialize(file)
@symbols = File.read(file).split("\n\n").map{ |s| s.split("\n").reverse() }
end
def width(symbol); symbol.map{ |line| line.size }.max; end
def total_width; @symbols.map{ |s| width(s) + 2 }.inject(&:+); end
def max_height; @symbols.map{ |s| s.size }.max; end
def print_state(state)
(-1..max_height).map do |i| # each row of ascii prints out
(0..state.size-1).map do |p| # position of the state (bank, boat...)
g = (i == -1 || i == max_height) && (p != 0 && p != state.size-1) ? '-' : ' '
pos = state[p].map do |sym| # symbol in the position (wolf, goat...)
s = @symbols[sym]
g + ((s && i!=-1 && s[i]) || '').ljust(width(s), g) + g
end.join
row = g * (total_width - pos.size) + pos
br = i==0 ? '/' : (i==max_height-1 ? '\\' : (i==-1 || i==max_height ? '~' : '|'))
bl = i==0 ? '\\' : (i==max_height-1 ? '/' : (i==-1 || i==max_height ? '~' : '|'))
row += br + "~(" if p == state.size-2
row += ")~" + bl if p == 0
row
end.join
end.reverse.each{ |l| puts l }
end
end
printer = WGCPrinter.new('wgc_ascii.txt')
Run.new.go(WGC.new).each{ |s| printer.print_state(s) }
#Run.new.go(WGC.new).each{ |s| p s }
@sfcgeorge
Copy link
Author

wcg

@ScueroInc
Copy link

nice job

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment