Some fun implementing a graph search algorithm

missionaries.go

package main

import (
  "fmt"
)

/*
Problem formulation

initial state: 3 missionaries and 3 cannibals on one side

goal: move missionaries and cannibals to other side without leaving missionaries outnumbered by cannibals

cost: number of boat trips

Result:
  without memoization: 11753 steps
  with    memoization: 29 steps (graph search)
*/


const (
  Left = iota
  Right = iota
)

type Node struct{
  state *State
  parent *Node
  depth int
}

type State struct{
  side1H int // Humans on side 1
  side1C int // Cannibals on side 1
  side2H int // Humans on side 2
  side2C int // Cannibals on side 2
  boatDir int // Left or Right
}

func main() {
  graphSearch()
}

func graphSearch() {
  closed := map[string]bool{} // This includes states already analyzed

  initialState := &State{ 3, 3, 0, 0, Left}

  initialNode := Node{ initialState, nil, 0 }

  fringe := []Node{initialNode}
  i := 0
  for {
    i++
    if len(fringe) == 0 {
      fmt.Println("No solution")
      return
    }

    node := fringe[0]
    fringe = fringe[1:]

    if goalTest(node.state) {
      fmt.Println(i)
      printResult(node)
      return
    }

    key := stateKey(node.state)

    if _, ok := closed[key]; !ok {
        closed[key] = true
        fringe = append(fringe, successors(&node)...)
    }
  }
}

func goalTest(state *State) bool {
  return state.side2H == 3 && state.side2C == 3
}

func successors(node *Node) []Node {
  nodes := []Node{}

  side1H := node.state.side1H
  side1C := node.state.side1C
  side2H := node.state.side2H
  side2C := node.state.side2C

  tryState := func(state *State) {
    if validState(state) {
      nodes = append(nodes, makeNode(node, state))
    }
  }

  if node.state.boatDir == Left {
    // Humans
    tryState(&State{side1H-1, side1C, side2H+1, side2C, Right})
    tryState(&State{side1H-2, side1C, side2H+2, side2C, Right})

    // Cannibals
    tryState(&State{side1H, side1C-1, side2H, side2C+1, Right})
    tryState(&State{side1H, side1C-2, side2H, side2C+2, Right})

    // Cannibal and human
    tryState(&State{side1H-1, side1C-1, side2H+1, side2C+1, Right})
  } else {
    // Humans
    tryState(&State{side1H+1, side1C, side2H-1, side2C, Left})
    tryState(&State{side1H+2, side1C, side2H-2, side2C, Left})

    // Cannibals
    tryState(&State{side1H, side1C+1, side2H, side2C-1, Left})
    tryState(&State{side1H, side1C+2, side2H, side2C-2, Left})

    // Cannibal and human
    tryState(&State{side1H+1, side1C+1, side2H-1, side2C-1, Left})
  }

  return nodes
}

func validState(state *State) bool {
  return state.side1H <= 3 &&
         state.side1C <= 3 &&
         state.side2H <= 3 &&
         state.side2C <= 3 &&
         (state.side1H == 0 || state.side1H >= state.side1C) &&
         (state.side2H == 0 || state.side2H >= state.side2C)
}

func makeNode(parent *Node, state *State) Node {
  return Node{
    state,
    parent,
    parent.depth + 1,
  }
}

func stateKey(state *State) string {
  return fmt.Sprintf("%d%d%d%d%d", state.side1H, state.side1C, state.side2H, state.side2C, state.boatDir)
}

func printResult(node Node) {
  fmt.Println("Depth: ", node.depth)
  fmt.Println("")

  nodes := []Node{}
  for {
    nodes = append(nodes, node)

    if node.depth == 0 { break }
    node = *node.parent
  }

  for i := len(nodes)-1; i >= 0; i-- {
    fmt.Println(nodes[i].state)
  }
}