ricochet robots

robots.go

package main

// NOTES:
// robot 0 is the robot with the same color as the goal
// does not ban trivial solutions
// this is just brute force with a list of previous game states

import (
	"fmt"
	"math/rand"
	"strings"
	"time"
)

const board = `
   0 1 2 3 4 5 6 7 8 9 a b c d e f
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
0 |         |           |         |
  + + + + + + + + + + + + + + + + +
1 |            x|   |x            |
  + +-+ + + + +-+ + +-+ + + + +-+ +
2 | |x                         x| |
  + + + + + + + + + + + + + + + + +
3 |                               |
  + + + + + + + + + + + + + + + + +
4 |                    x|         |
  + + + + + + +-+ + + +-+ + + + +-+
5 |            x|                 |
  +-+ + + + + + + + + + + +-+ + + +
6 |     |x                |x      |
  + + + +-+ + + +-+-+ + + + + + + +
7 |             |   |             |
  + + + + + + + + + + + + + + + + +
8 |             |   |             |
  + + + + + + + +-+-+ + + + + + + +
9 |       |x                      |
  + + + + +-+ +-+ + + + + + + + + +
a |           |x   x|             |
  +-+ + + + + + + +-+ + + + + + +-+
b |                               |
  + + + + + + + +-+ + + + + +-+ + +
c |              x|         |x    |
  + +-+ + + + + + + + + + + + + + +
d |  x|             |x            |
  + + + + + + + + + +-+ + + + +-+ +
e |      x|                    x| |
  + + + +-+ + + + + + + + + + + + +
f |         |             |       |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`

const (
	size       = 16
	maxQueue   = 1 << 24
	robotCount = 4
)

const (
	up    = (1 << iota)
	down  = (1 << iota)
	left  = (1 << iota)
	right = (1 << iota)
)

type Move struct {
	Robot     byte
	Direction byte
}

func (m Move) String() string {
	dir := ""
	switch m.Direction {
	case up:
		dir = "up"
	case down:
		dir = "down"
	case left:
		dir = "left"
	case right:
		dir = "right"
	}
	return fmt.Sprintf("%d:%s", m.Robot, dir)
}

type State struct {
	Robots [robotCount]byte
	Moves  []Move
}

// this is out here so we don't re-allocate it all the time
var queue = make([]State, maxQueue)

func index(row int, col int) byte {
	return byte(row*size + col)
}

func parse(board string) ([]byte, []byte) {
	grid := [][]byte{}
	for _, line := range strings.Split(board, "\n") {
		if strings.TrimSpace(line) == "" {
			continue
		}
		grid = append(grid, []byte(line))
	}

	walls := make([]byte, size*size)
	goals := []byte{}
	for r := 0; r < size; r++ {
		for c := 0; c < size; c++ {
			i := index(r, c)
			gc := c*2 + 3
			gr := r*2 + 2
			switch grid[gr][gc] {
			case 'x':
				goals = append(goals, i)
			case ' ':
			default:
				panic("bad board")
			}

			if grid[gr][gc+1] == '|' {
				walls[i] |= right
			}
			if grid[gr][gc-1] == '|' {
				walls[i] |= left
			}
			if grid[gr+1][gc] == '-' {
				walls[i] |= down
			}
			if grid[gr-1][gc] == '-' {
				walls[i] |= up
			}
		}
	}
	return walls, goals
}

func draw(s State, walls []byte, goal byte) {
	fmt.Println("   0 1 2 3 4 5 6 7 8 9 a b c d e f")
	for r := 0; r < size; r++ {
		fmt.Printf("  +")
		for c := 0; c < size; c++ {
			if walls[index(r, c)]&up == up {
				fmt.Printf("-")
			} else {
				fmt.Printf(" ")
			}
			fmt.Printf("+")
		}
		fmt.Printf("\n")

		fmt.Printf("%x ", r)
		for c := 0; c < size; c++ {
			if walls[index(r, c)]&left == left {
				fmt.Printf("|")
			} else {
				fmt.Printf(" ")
			}

			occupied := false
			for robot, pos := range s.Robots {
				if index(r, c) == pos {
					if occupied {
						// make sure we don't have two robots on the same spot
						panic("double robo")
					}
					fmt.Printf("%d", robot)
					occupied = true
				}
			}

			if !occupied {
				if index(r, c) == goal {
					fmt.Printf("x")
				} else {
					fmt.Printf(" ")
				}
			}

			if c == size-1 {
				if walls[index(r, c)]&right == right {
					fmt.Printf("|")
				} else {
					fmt.Printf(" ")
				}
			}
		}
		fmt.Printf("\n")

		if r == size-1 {
			fmt.Printf("  +")
			for c := 0; c < size; c++ {
				if walls[index(r, c)]&down == down {
					fmt.Printf("-")
				} else {
					fmt.Printf(" ")
				}
				fmt.Printf("+")
			}
			fmt.Printf("\n")
		}
	}
	fmt.Printf("\n")
}

func move(s State, walls []byte, robot byte, dir byte) State {
	pos := s.Robots[robot]

	delta := 0
	switch dir {
	case up:
		delta = -size
	case down:
		delta = size
	case left:
		delta = -1
	case right:
		delta = 1
	}

Move:
	for {
		for otherRobot, otherRobotPos := range s.Robots {
			if robot == byte(otherRobot) {
				continue
			}

			if pos == otherRobotPos {
				// hit another robot, backup a square
				pos -= byte(delta)
				break Move
			}
		}

		if walls[pos]&dir == dir {
			break Move
		}

		pos += byte(delta)
	}

	robots := s.Robots
	robots[robot] = pos
	moves := make([]Move, len(s.Moves)+1)
	copy(moves, s.Moves)
	moves[len(moves)-1] = Move{Robot: robot, Direction: dir}

	return State{
		Robots: robots,
		Moves:  moves,
	}
}

func replay(is State, es State, walls []byte, goal byte) {
	s := is
	for _, m := range es.Moves {
		s = move(s, walls, m.Robot, m.Direction)
		fmt.Println(m)
		draw(s, walls, goal)
	}

	for _, m := range es.Moves {
		fmt.Println(m)
	}

	fmt.Printf("moves=%d\n", len(es.Moves))
}

func explore(initialState State, walls []byte, goal byte) bool {
	seen := map[[robotCount]byte]bool{}
	start := 0
	end := 1

	queue[0] = initialState
	seen[initialState.Robots] = true

	for end < len(queue) {
		state := queue[start]

		// move each robot in each direction
		for r := byte(0); r < robotCount; r++ {
			for _, d := range []byte{up, down, left, right} {
				newState := move(state, walls, r, d)

				if seen[newState.Robots] {
					continue
				}

				seen[newState.Robots] = true
				queue[end] = newState
				end++

				if newState.Robots[0] == goal {
					replay(initialState, newState, walls, goal)
					return true
				}
			}
		}

		start++
	}

	return false
}

func main() {
	rand.Seed(time.Now().UTC().UnixNano())

	// parse the game board to setup global walls and goals
	walls, goals := parse(board)

	for {
		// randomize robot locations
		initialState := State{}

		i := 0
	FindLocation:
		for {
			r := byte(rand.Intn(size * size))
			// don't put any robots on a goal
			for _, g := range goals {
				if r == g {
					continue FindLocation
				}
			}
			// don't put any robots in the middle
			if r == 0x77 || r == 0x78 || r == 0x87 || r == 0x88 {
				continue FindLocation
			}

			// no robot-on-robot
			for j := 0; j < i; j++ {
				if r == initialState.Robots[j] {
					continue FindLocation
				}
			}
			initialState.Robots[i] = r
			i++

			if i >= robotCount {
				break
			}
		}

		// pick a random goal
		goal := goals[rand.Intn(len(goals))]
		fmt.Println("new layout:")
		draw(initialState, walls, goal)

		// look for a solution
		if explore(initialState, walls, goal) {
			fmt.Println("found a solution\n")
		} else {
			panic("didn't find solution")
		}
	}
}