rivercrossing.go

package main

import "fmt"

const Count = 3

var Goal = State{0, 0, R, ""}

func main() {
	fmt.Println("breadthFirstSearch")
	breadthFirstSearch()
	fmt.Println("depthFirstSearch")
	depthFirstSearch()
}

func breadthFirstSearch() {
	state := State{Count, Count, L, ""}

	if state.Equals(Goal) {
		return
	}

	frontier := []State{}
	explored := map[string]bool{}
	frontier = append(frontier, state)

	stepCount := 0
	for len(frontier) > 0 {
		state, frontier = frontier[0], frontier[1:]

		children := state.Successors()

		stepCount++
		fmt.Printf("%d: %s -> \n\tchildren: %s\n\tfrontier: %s\n\texplored: %s\n", stepCount, state, children, frontier, keyArray(explored))
		if state.Equals(Goal) {
			return
		}

		for _, child := range children {
			if _, found := explored[child.String()]; !found &&
				!containsState(frontier, child) {
				frontier = append(frontier, child)
			}
		}

		explored[state.String()] = true
	}
}

func depthFirstSearch() {
	state := State{Count, Count, L, ""}

	if state.Equals(Goal) {
		return
	}

	frontier := []State{}
	explored := map[string]bool{}
	frontier = append(frontier, state)

	stepCount := 0
	for len(frontier) > 0 {
		state, frontier = frontier[len(frontier)-1], frontier[:len(frontier)-1]

		children := state.Successors()

		stepCount++
		fmt.Printf("%d: %s -> \n\tchildren: %s\n\tfrontier: %s\n\texplored: %s\n", stepCount, state, children, frontier, keyArray(explored))

		if state.Equals(Goal) {
			return
		}

		for _, child := range children {
			if _, found := explored[child.String()]; !found &&
				!containsState(frontier, child) {
				frontier = append(frontier, child)
			}
		}

		explored[state.String()] = true
	}
}

type BoatState bool

type TransitionFunc func(state State) *State

const (
	L BoatState = false
	R BoatState = true
)

type Transition int

type State struct {
	M  int
	C  int
	B  BoatState
	By string
}

func (s State) String() string {
	char := "L"
	if s.B {
		char = "R"
	}
	return fmt.Sprintf("(%2s: %d, %d, %s)", s.By, s.M, s.C, char)
}

func (state State) Successors() []State {
	states := []State{}

	for i, f := range []TransitionFunc{mm, cc, mc, m, c} {
		if s := f(state); s != nil && s.ValidState() {
			s.By = []string{"mm", "cc", "mc", "m", "c"}[i]
			states = append(states, *s)
		}
	}

	return states
}

func mm(s State) *State {
	return modState(s, 2, 0)
}

func cc(s State) *State {
	return modState(s, 0, 2)
}

func mc(s State) *State {
	return modState(s, 1, 1)
}

func m(s State) *State {
	return modState(s, 1, 0)
}

func c(s State) *State {
	return modState(s, 0, 1)
}

func modState(s State, mMod, cMod int) *State {
	if !s.B {
		mMod *= -1
		cMod *= -1
	}
	return &State{
		B: !s.B,
		M: s.M + mMod,
		C: s.C + cMod,
	}
}

func (s State) ValidState() bool {
	return s.C >= 0 && s.M >= 0 && s.C <= Count && s.M <= Count && s.C <= s.M
}

func (s State) Equals(os State) bool {
	return s.C == os.C && s.M == os.M && s.B == os.B
}

func containsState(states []State, state State) bool {
	for _, s := range states {
		if state.Equals(s) {
			return true
		}
	}
	return false
}

func keyArray(data map[string]bool) []string {
	keys := []string{}

	for key, _ := range data {
		keys = append(keys, key)
	}

	return keys
}