Skip to content

Instantly share code, notes, and snippets.

@akimboyko
Created February 9, 2014 06:47
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save akimboyko/8895355 to your computer and use it in GitHub Desktop.
Save akimboyko/8895355 to your computer and use it in GitHub Desktop.

Toy Problem: Missionaries and Cannibals

Description

On one bank of a river are three missionaries (black triangles) and three cannibals (red circles). There is one boat available that can hold up to two people and that they would like to use to cross the river. If the cannibals ever outnumber the missionaries on either of the river’s banks, the missionaries will get eaten. How can the boat be used to safely carry all the missionaries and cannibals across the river?

Task

Try to implement the general search algorithm just described. You can use LIFO and FIFO as queuing strategies to determine the order in which nodes are explored. These two strategies are known as depth-first and breadth-first search respectively. Be careful, depth-first search may descend down infinite branches, so best implement a depth cut-off. Then, extend your implementation with a hash table that stores all the nodes found so far. Print out a trace of the states the algorithm finds (in the order they are discovered) and see how much of the search space each algorithm explores.

Source

Artificial Intelligence Planning course

namespace MissionariesAndCanibals
module MissionariesAndCanibals =
// A state-transition system is a 4-tuple Σ=(S, A, E, γ)
let nM = 3
// S = {s1, s2, …} is a finite or recursively enumerable set of states
type Characters =
| Nobody
| Missionaries of int
| Canibals of int
| MissionariesAndCanibals of int * int
override x.ToString() =
match x with
| Nobody -> "nobody"
| Missionaries(1) -> "missionary"
| Missionaries(m) -> "missionaries"
| Canibals(1) -> "canibal"
| Canibals(m) -> "canibals"
| MissionariesAndCanibals(1, 1) -> "missionary and canibal"
| MissionariesAndCanibals(1, c) -> "missionary and canibals"
| MissionariesAndCanibals(m, 1) -> "missionaries and canibal"
| MissionariesAndCanibals(m, c) -> "missionaries and canibals"
type RiverBank =
| Left
| Right
override x.ToString() =
match x with
| Left -> "left bank"
| Right -> "right bank"
let private isSafe(characters: Characters) =
match characters with
| Nobody -> true
| Missionaries(_) -> true
| Canibals(_) -> true
| MissionariesAndCanibals(m, c) -> m >= c
type State(bank: RiverBank, characters: Characters) =
member x.Bank = bank
member x.Characters = characters
member x.IsStateAllowed() = isSafe(characters)
member x.OppositeBank() =
let oppositeBank =
match bank with
| Left -> Right
| Right -> Left
let oppositeBankCharacters =
match characters with
| Nobody -> MissionariesAndCanibals(nM, nM)
| Missionaries(m)
when m < nM -> MissionariesAndCanibals(nM - m, nM)
| Missionaries(m)
when m = nM -> Canibals(nM)
| Canibals(c)
when c < nM -> MissionariesAndCanibals(nM, nM - c)
| Canibals(c)
when c = nM -> Missionaries(nM)
| MissionariesAndCanibals(m, c)
when m = nM && c = nM -> Nobody
| MissionariesAndCanibals(m, c)
when m = nM && c < nM -> Canibals(nM - c)
| MissionariesAndCanibals(m, c)
when m < nM && c = nM -> Missionaries(nM - m)
| MissionariesAndCanibals(m, c)
when m < nM && c < nM -> MissionariesAndCanibals(nM - m, nM - c)
| _ -> raise (System.ArgumentException("Invalid state"))
new State(oppositeBank, oppositeBankCharacters)
override x.ToString() =
sprintf "%O with %O" bank characters
override x.Equals(yobj) =
match yobj with
| :? State as y -> (x.Bank = y.Bank) && (x.Characters = y.Characters)
| _ -> false
override x.GetHashCode() = (hash x.Bank) ^^^ (hash x.Characters)
interface System.IComparable with
member x.CompareTo yobj =
match yobj with
| :? State as y -> compare (x.Bank, x.Characters) (y.Bank, y.Characters)
| _ -> invalidArg "yobj" "cannot compare values of different types"
let InitialState = new State(Left, MissionariesAndCanibals(nM, nM))
// A = {a1, a2, …} is a finite or recursively enumerable set of actions
type BoatTransfer =
| Transfer of Characters
let BoatTransfers =
[
Transfer(Canibals(1));
Transfer(Canibals(2));
Transfer(Missionaries(1));
Transfer(Missionaries(2));
Transfer(MissionariesAndCanibals(1, 1));
]
let private convert(characters: Characters) =
match characters with
| Nobody -> (0, 0)
| Missionaries(m) -> (m, 0)
| Canibals(c) -> (0, c)
| MissionariesAndCanibals(m, c) -> (m, c)
let private convertBack(m: int, c: int) =
match (m, c) with
| (m, 0) when m > 0 -> Missionaries(m)
| (0, c) when c > 0 -> Canibals(c)
| (m, c) when m > 0 && c > 0 -> MissionariesAndCanibals(m, c)
| _ -> Nobody
let private sub(characters: Characters, move: BoatTransfer) =
let (sm, sc) = convert(characters)
let (tm, tc) = match move with | Transfer(characters) -> convert(characters)
convertBack(sm - tm, sc - tc)
let private add(characters: Characters, move: BoatTransfer) =
let (sm, sc) = convert(characters)
let (tm, tc) = match move with | Transfer(characters) -> convert(characters)
convertBack(sm + tm, sc + tc)
let private allowed(characters: Characters, move: BoatTransfer) =
let (sm, sc) = convert(characters)
let (tm, tc) = match move with | Transfer(characters) -> convert(characters)
(sm >= tm) && (sc >= tc) && isSafe(sub(characters, move))
let AllowedMoves(state: State) =
let oppositeSide = state.OppositeBank()
BoatTransfers |>
Seq.filter(fun transfer -> allowed(state.Characters, transfer)) |>
Seq.filter(fun transfer -> isSafe(sub(state.Characters, transfer))) |>
Seq.filter(fun transfer -> isSafe(add(oppositeSide.Characters, transfer)))
let ApplyTransfer(state: State, transfer: BoatTransfer) =
let oppositeSide = state.OppositeBank()
new State(oppositeSide.Bank, add(oppositeSide.Characters, transfer))
let FollowingStates(state: State) =
let oppositeSide = state.OppositeBank()
AllowedMoves(state) |>
Seq.map(fun transfer -> ApplyTransfer(state, transfer))
[<CustomEquality; CustomComparison>]
type History =
| Start
| CurrentState of int * State * History
override x.Equals yobj =
match x with
| Start ->
match yobj with
| :? History as y ->
match y with
| Start -> true
| CurrentState(_, _, _) -> false
| _ -> false
| CurrentState(xGen, xState, _) ->
match yobj with
| :? History as y ->
match y with
| Start -> false
| CurrentState(yGen, yState, _) -> xGen = yGen && xState = yState
| _ -> false
override x.ToString() =
match x with
| Start -> "start"
| CurrentState(gen, state, _) -> sprintf "generation %d with state %O" gen state
override x.GetHashCode() =
match x with
| Start -> -1
| CurrentState(gen, state, _) -> gen ^^^ hash state
interface System.IComparable with
member x.CompareTo(yobj) =
match x with
| Start ->
match yobj with
| :? History as y ->
match y with
| Start -> 0
| CurrentState(_, _, _) -> -1
| _ -> invalidArg "yobj" "cannot compare values of different types"
| CurrentState(xGen, xState, _) ->
match yobj with
| :? History as y ->
match y with
| Start -> -1
| CurrentState(yGen, yState, _) -> compare xGen yGen
| _ -> invalidArg "yobj" "cannot compare values of different types"
// E = {e1, e2, …} is a finite or recursively enumerable set of events
let IsGoalState(state: State) =
match state.Characters with
| MissionariesAndCanibals(m, c) when m = nM && c = nM -> state.Bank = Right
| _ -> false
// γ: S×(A∪E)→2^S is a state transition function
open FSharpx.Collections
open Microsoft.FSharp.Collections
let Run() =
let rec run(priorityQueue, visitedStates: Set<State>) =
let (history, priorityQueue) = PriorityQueue.pop priorityQueue
let (CurrentState(gen, currentState, _)) = history
if IsGoalState(currentState) then
history
else
let visitedStates = visitedStates.Add(currentState)
let followingStates =
FollowingStates(currentState) |>
Seq.filter(fun state -> not(visitedStates.Contains(state))) |>
Seq.toList
let priorityQueue =
List.fold
(fun priorityQueue nextState ->
PriorityQueue.insert (CurrentState(gen + 1, nextState, history)) priorityQueue)
priorityQueue followingStates
run(priorityQueue, visitedStates)
let priorityQueue = PriorityQueue.empty false
let start = CurrentState(0, InitialState, Start)
let priorityQueue = PriorityQueue.insert start priorityQueue
let visitedStates = new Set<State>([ ])
run(priorityQueue, visitedStates)
namespace MissionariesAndCanibals
module MissionariesAndCanibalsProperties =
open Xunit
open FsUnit.Xunit
open FsCheck
open MissionariesAndCanibals
let ``Initial state is valid`` () =
InitialState.IsStateAllowed()
let ``Number of missionaries should be greater or equal to canibals `` (bank: RiverBank, characters: Characters) =
let state = new State(bank, characters)
let expectedState =
match characters with
| Nobody -> true
| Missionaries(m) -> true
| Canibals(_) -> true
| MissionariesAndCanibals(m, c) -> m >= c
state.IsStateAllowed() = expectedState
let ``Opposite state has opposite bank`` (bank: RiverBank, characters: Characters) =
let state = new State(bank, characters)
let oppositeState = state.OppositeBank()
state.Bank <> oppositeState.Bank
let private numberOfMissionariesOnThisBank(state: State) =
match state.Characters with
| Nobody -> 0
| Missionaries(m) -> m
| Canibals(_) -> 0
| MissionariesAndCanibals(m, _) -> m
let private numberOfCanibalsOnThisBank(state: State) =
match state.Characters with
| Nobody -> 0
| Missionaries(_) -> 0
| Canibals(c) -> c
| MissionariesAndCanibals(_, c) -> c
let private numberOfCharactersOnThisBank(state: State) =
numberOfMissionariesOnThisBank(state) + numberOfCanibalsOnThisBank(state)
let ``Number of missionaries on both banks is constant`` (bank: RiverBank, characters: Characters) =
let state = new State(bank, characters)
let oppositeState = state.OppositeBank()
numberOfMissionariesOnThisBank(state) + numberOfMissionariesOnThisBank(oppositeState) = 3
let ``Number of canibals on both banks is constant`` (bank: RiverBank, characters: Characters) =
let state = new State(bank, characters)
let oppositeState = state.OppositeBank()
numberOfCanibalsOnThisBank(state) + numberOfCanibalsOnThisBank(oppositeState) = 3
let ``Number of missionaries and canibals on both banks is constant`` (bank: RiverBank, characters: Characters) =
let state = new State(bank, characters)
let oppositeState = state.OppositeBank()
numberOfCharactersOnThisBank(state) + numberOfCharactersOnThisBank(oppositeState) = 6
let ``Only state with everyone on right bank is goal state`` (bank: RiverBank, characters: Characters) =
let state = new State(bank, characters)
let isGoalState =
bank = Right &&
numberOfMissionariesOnThisBank(state) = 3 &&
numberOfCanibalsOnThisBank(state) = 3
IsGoalState(state) = isGoalState
let ``Allowed moves results in both banks to be in allowed state`` (bank: RiverBank, characters: Characters) =
let state = new State(bank, characters)
let followingStates = FollowingStates(state)
let allFollowingStatesAreAllowed =
followingStates |>
Seq.forall(fun followingState -> followingState.IsStateAllowed())
let allOppositeToFollowingStatesAreAllowed =
followingStates |>
Seq.map(fun followingState -> followingState.OppositeBank()) |>
Seq.forall(fun oppotiteBank -> oppotiteBank.IsStateAllowed())
allFollowingStatesAreAllowed && allFollowingStatesAreAllowed
let private convertStateToNumberOfCharacters(state: State) =
(numberOfMissionariesOnThisBank(state), numberOfCanibalsOnThisBank(state))
let private convertMoveToNumberOfCharacters(transfer: BoatTransfer) =
match transfer with
| Transfer(Nobody) -> (0, 0)
| Transfer(Missionaries(m)) -> (m, 0)
| Transfer(Canibals(c)) -> (0, c)
| Transfer(MissionariesAndCanibals(m, c)) -> (m, c)
let ``All skipped moves results in unallowed state on either bank`` (bank: RiverBank, characters: Characters) =
let state = new State(bank, characters)
let allowedMoves = AllowedMoves(state)
let forbiddenMoves =
BoatTransfers |>
Seq.filter(fun transfer ->
not(allowedMoves |> Seq.exists(fun allowedTransfer ->
transfer = allowedTransfer) ) )
let (sm, sc) = convertStateToNumberOfCharacters(state)
forbiddenMoves |>
Seq.map(fun forbidden -> convertMoveToNumberOfCharacters(forbidden)) |>
Seq.forall(fun (tm, tc) ->
((tm > sm) || (tc > sc)) ||
(sm - tm < sc - tc) ||
(3 - sm + tm < 3 - sc + tc))
let private riverBankGen =
Gen.oneof [
gen { return Left };
gen { return Right };
]
let private nCharacters = Gen.elements [ 1 .. 3 ]
let private charactersGen =
Gen.oneof [
gen { return Nobody };
Gen.map Missionaries nCharacters;
Gen.map Canibals nCharacters;
Gen.map MissionariesAndCanibals (Gen.two nCharacters);
]
let private riverBankStates =
Gen.map2 (fun rb ch -> (rb, ch)) riverBankGen charactersGen
[<Fact>]
let ``Prove states`` () =
Check.VerboseThrowOnFailure ``Initial state is valid``
Check.VerboseThrowOnFailure (Prop.forAll (Arb.fromGen riverBankStates)
``Number of missionaries should be greater or equal to canibals ``)
Check.VerboseThrowOnFailure (Prop.forAll (Arb.fromGen riverBankStates)
``Opposite state has opposite bank``)
Check.VerboseThrowOnFailure (Prop.forAll (Arb.fromGen riverBankStates)
``Number of missionaries on both banks is constant``)
Check.VerboseThrowOnFailure (Prop.forAll (Arb.fromGen riverBankStates)
``Number of canibals on both banks is constant``)
Check.VerboseThrowOnFailure (Prop.forAll (Arb.fromGen riverBankStates)
``Number of missionaries and canibals on both banks is constant``)
Check.VerboseThrowOnFailure (Prop.forAll (Arb.fromGen riverBankStates)
``Only state with everyone on right bank is goal state``)
Check.VerboseThrowOnFailure (Prop.forAll (Arb.fromGen riverBankStates)
``Allowed moves results in both banks to be in allowed state``)
Check.VerboseThrowOnFailure (Prop.forAll (Arb.fromGen riverBankStates)
``All skipped moves results in unallowed state on either bank``)
namespace MissionariesAndCanibals
module MissionariesAndCanibalsTests =
open System.Linq
open Xunit
open FsUnit.Xunit
open MissionariesAndCanibals
[<Fact>]
let ``Initial state is allowed`` () =
InitialState.IsStateAllowed() |>
should be True
[<Fact>]
let ``Only canibals is allowed state`` () =
(new State(Left, Canibals(1))).IsStateAllowed() |>
should be True
[<Fact>]
let ``Only misionaries is allowed state`` () =
(new State(Left, Missionaries(2))).IsStateAllowed() |>
should be True
[<Fact>]
let ``More misionaries then canibals is allowed state`` () =
(new State(Left, MissionariesAndCanibals(2, 1))).IsStateAllowed() |>
should be True
[<Fact>]
let ``As many misionaries as canibals is allowed state`` () =
(new State(Left, MissionariesAndCanibals(1, 1))).IsStateAllowed() |>
should be True
[<Fact>]
let ``Less misionaries then canibals is not allowed state`` () =
(new State(Left, MissionariesAndCanibals(1, 2))).IsStateAllowed() |>
should be False
[<Fact>]
let ``Nobody on a bank is allowed state`` () =
(new State(Left, Nobody)).IsStateAllowed() |>
should be True
[<Fact>]
let ``There is nobody on right bank on initial state`` () =
let expectedOppositeBank = new State(Right, Nobody)
InitialState.OppositeBank() |>
should equal expectedOppositeBank
[<Fact>]
let ``Opposite to bank with all missionaries is bank with all canibals`` () =
let allMissionaries = new State(Right, Missionaries(3))
let allCanibals = new State(Left, Canibals(3))
allMissionaries.OppositeBank() |>
should equal allCanibals
[<Fact>]
let ``Opposite to bank with all missionaries and two canibals is bank with one canibal`` () =
let allMissionariesAndTwoCanicals = new State(Right, MissionariesAndCanibals(3, 2))
let oneCanibal = new State(Left, Canibals(1))
allMissionariesAndTwoCanicals.OppositeBank() |>
should equal oneCanibal
[<Fact>]
let ``Opposite to bank with one canibal is bank with all missionaries and two canibals `` () =
let oneCanibal = new State(Right, Canibals(1))
let allMissionariesAndTwoCanicals = new State(Left, MissionariesAndCanibals(3, 2))
oneCanibal.OppositeBank() |>
should equal allMissionariesAndTwoCanicals
[<Fact>]
let ``There are three moved from initial state`` () =
let possibleMoves = AllowedMoves(InitialState)
possibleMoves.Count() |> should equal 3
possibleMoves |> should contain (Transfer(Canibals(1)))
possibleMoves |> should contain (Transfer(Canibals(2)))
possibleMoves |> should contain (Transfer(MissionariesAndCanibals(1, 1)))
[<Fact>]
let ``There is no allowed moves from bank where there is nobody`` () =
let possibleMoves = AllowedMoves(State(Left, Nobody))
possibleMoves.Count() |> should equal 0
[<Fact>]
let ``There is only one allowed moves from bank where there is one canibal`` () =
let possibleMoves = AllowedMoves(State(Left, Canibals(1)))
possibleMoves.Count() |> should equal 1
possibleMoves |> should contain (Transfer(Canibals(1)))
[<Fact>]
let ``There are three followed states from initial state`` () =
let possibleMoves = FollowingStates(InitialState)
possibleMoves.Count() |> should equal 3
possibleMoves |> should contain (new State(Right, Canibals(1)))
possibleMoves |> should contain (new State(Right, Canibals(2)))
possibleMoves |> should contain (new State(Right, MissionariesAndCanibals(1, 1)))
[<Fact>]
let ``There is no allowed followed states from bank where there is nobody`` () =
let possibleMoves = FollowingStates(State(Left, Nobody))
possibleMoves.Count() |> should equal 0
[<Fact>]
let ``There is only one allowed followed state from bank where there is one canibal`` () =
let possibleMoves = FollowingStates(State(Left, Canibals(1)))
possibleMoves.Count() |> should equal 1
possibleMoves |> should contain (new State(Right, MissionariesAndCanibals(3, 3)))
[<Fact>]
let ``State with everyone on right bank is goal state`` () =
let everyoneOnRightBank = new State(Right, MissionariesAndCanibals(3, 3))
IsGoalState(everyoneOnRightBank) |> should be True
[<Fact>]
let ``Initial state is not goal state`` () =
IsGoalState(InitialState) |> should be False
[<Fact>]
let ``State with all misionaries and two canibals on right bank is not goal state`` () =
let allMissionariesAndTwoCanibalsOnRightBank = new State(Right, MissionariesAndCanibals(3, 2))
IsGoalState(allMissionariesAndTwoCanibalsOnRightBank) |> should be False
open FSharpx.Collections
[<Fact>]
let ``Get element with smallest generation from PriorityQueue`` () =
let first = CurrentState(0, InitialState, Start)
let secondC1 = CurrentState(1, new State(Right, Canibals(1)), first)
let secondC2 = CurrentState(1, new State(Right, Canibals(2)), first)
let secondM1C1 = CurrentState(1, new State(Right, MissionariesAndCanibals(1, 1)), first)
let thirdM3C2 = CurrentState(2, new State(Right, MissionariesAndCanibals(1, 1)), first)
let priorityQueue = PriorityQueue.empty false
let priorityQueue = PriorityQueue.insert first priorityQueue
let priorityQueue = PriorityQueue.insert secondC1 priorityQueue
let priorityQueue = PriorityQueue.insert secondC2 priorityQueue
let priorityQueue = PriorityQueue.insert secondM1C1 priorityQueue
let priorityQueue = PriorityQueue.insert thirdM3C2 priorityQueue
let (nextElement, priorityQueue) = PriorityQueue.pop priorityQueue
nextElement |> should equal first
let (nextElement, priorityQueue) = PriorityQueue.pop priorityQueue
nextElement |> should equal secondM1C1
let (nextElement, priorityQueue) = PriorityQueue.pop priorityQueue
nextElement |> should equal secondC2
let (nextElement, priorityQueue) = PriorityQueue.pop priorityQueue
nextElement |> should equal secondC1
let (nextElement, priorityQueue) = PriorityQueue.pop priorityQueue
nextElement |> should equal thirdM3C2
PriorityQueue.isEmpty priorityQueue |> should be True
[<Fact>]
let ``Get goal state after processing from initial state`` () =
let goal = Run()
match goal with
| CurrentState(_, goalState, _) ->
let expectedGoalState = new State(Right, MissionariesAndCanibals(3, 3))
goalState |> should equal expectedGoalState
| _ -> "this should not be" |> should be EmptyString
[<Fact>]
let ``Get goal state after 11 steps`` () =
let goal = Run()
match goal with
| CurrentState(11, _, _) -> ()
| _ -> "this should not be" |> should be EmptyString
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment