Skip to content

Instantly share code, notes, and snippets.

@hayatoito
Created July 16, 2012 15:46
Show Gist options
  • Save hayatoito/3123427 to your computer and use it in GitHub Desktop.
Save hayatoito/3123427 to your computer and use it in GitHub Desktop.
hayato @ ICFP Programming Contest 2012
package icfp2012
import scala.io.Source
import scala.collection.mutable
import my.util.logging.Logger
import sun.misc.Signal
import sun.misc.SignalHandler
object Main extends App {
import sun.misc.SignalHandler
import sun.misc.Signal
import io.Source
val source = Source.stdin
val mapData = source.getLines.mkString("\n")
val (parameter, state) = Reader.readBoard(mapData)
val bot = SABot()
Signal.handle(new Signal("INT"), new SignalIntHandler)
class SignalIntHandler extends SignalHandler {
def handle(sig: Signal) {
val moves = bot.bestMoves
println(Core.dumpMoves(moves))
sys.exit(0)
}
}
val moves = bot.run(parameter, state)
println(Core.dumpMoves(moves))
}
case class Position(x: Int, y: Int) {
def manhattanDistanceTo(other: Position): Int = math.abs(other.x - x) + math.abs(other.y - y)
def nextPositions: List[Position] = List(Position(x - 1, y), Position(x + 1, y), Position(x, y - 1), Position(x, y + 1))
def to(next: Position): Move = {
if (x + 1 == next.x) Right
else if (x - 1 == next.x) Left
else if (y + 1 == next.y) Up
else if (y - 1 == next.y) Down
else if (this == next) Wait
else throw new GameException()
}
}
abstract class Move
case object Up extends Move
case object Down extends Move
case object Right extends Move
case object Left extends Move
case object Abort extends Move
case object Wait extends Move
case object Sci extends Move
object Core {
val log = Logger[this.type]
var shoudDebug = false
type Board = Seq[Seq[Char]]
def updated(map: Board, x: Int, y: Int, c: Char): Board = {
map.updated(x, map(x).updated(y, c))
}
val SPACE = ' '
val ROBOT = 'R'
val ROCK = '*'
val WALL = '#'
val LIFT = 'L'
val EARTH = '.'
val LAMBDA = '\\'
val BEARD = 'W'
val RAZOR = '!'
val HIGH_ROCK = '@'
def isTrampoline(c: Char) = 'A' <= c && c <= 'I'
def isTarget(c: Char) = '1' <= c && c <= '9'
def dumpMap(map: Board): String = {
val X = map.size
val Y = map(0).size
(for {
y <- (1 until (Y - 1)).reverse
x <- 1 until X - 1
} yield (if (x == X - 2) map(x)(y) + "\n" else map(x)(y))
).mkString("")
}
def toMoves(moves: String): List[Move] = {
(for (move <- moves) yield move match {
case 'U' => Up
case 'D' => Down
case 'L' => Left
case 'R' => Right
case 'W' => Wait
case 'A' => Abort
case 'S' => Sci
case _ => throw new GameException()
}).toList
}
def dumpMoves(moves: List[Move]): String = {
moves.map(_ match {
case Up => "U"
case Down => "D"
case Left => "L"
case Right => "R"
case Abort => "A"
case Wait => "W"
case Sci => "S"
}).mkString
}
def rocklike(c: Char) = c == ROCK || c == HIGH_ROCK || walllike(c)
def walllike(c: Char) = c == WALL || c == LIFT
def normalize(oldMap: Board): Board = {
var map = oldMap
val X = map.size
val Y = map(0).size
def highestRock: Int = {
for {
y <- (1 until (Y - 1)).reverse
x <- 1 until X - 1
if (map(x)(y) == ROCK || map(x)(y) == HIGH_ROCK)
} return y
-1
}
val highY = highestRock
if (highY != -1) {
for {
y <- (highY + 1) until Y - 1
x <- 1 until X - 1
if (map(x)(y) == EARTH)
} map = updated(map, x, y, SPACE)
}
// if (map != oldMap) {
// println("Remove Earth:\n" + dumpMap(oldMap))
// println("Done:\n" + dumpMap(map))
// }
// Move unmovable rocks to WALL.
// #*#
// #
//?**?
//#### -> No - Rock Slide. # See the bellow.
// ***
// ###
// ->
// *#*
// ###
for {
y <- 1 until Y - 1
x <- 1 until X - 1
if (map(x)(y) == ROCK) // TODO HighRock
if (rocklike(map(x - 1)(y)) && rocklike(map(x)(y)) && rocklike(map(x + 1)(y)) &&
walllike(map(x - 1)(y - 1)) && walllike(map(x)(y - 1)) && walllike(map(x + 1)(y - 1)))
} {
// println("Conveting:\n" + dumpMap(map))
map = updated(map, x, y, WALL)
// println("Conveted:\n" + dumpMap(map))
}
if (map != oldMap)
normalize(map)
else
map
}
}
sealed abstract class Condition
case object NormalCondition extends Condition
case object AbortCondition extends Condition
case object WinningCondition extends Condition
case object LosingCondition extends Condition
case class State(map: Seq[Seq[Char]] = null, robot: Position = null,
lambda: Int = 0, steps: Int=0, inWater: Int = 0, razors: Int = 0,
condition: Condition = NormalCondition) {
def X = map.size
def Y = map(0).size
def dump: String = {
List(Core.dumpMap(map), "score: " + evalScore, condition).mkString("\n")
}
def evalScore: Int = condition match {
case NormalCondition => lambda * 50 - steps
case AbortCondition => lambda * 50 - steps
case WinningCondition => lambda * 75 - steps
case LosingCondition => lambda * 25 - steps
}
def score = evalScore
}
class GameException extends Exception
case class Trampoline(c: Char)
case class Target(c: Char)
case class Parameter (X: Int, Y: Int, lambda: Int = 0, water: Int = 0, flooding: Int = 0, waterproof: Int = 10,
trampolinePosition: mutable.Map[Trampoline, Position] = mutable.Map.empty[Trampoline, Position],
targetPosition: mutable.Map[Target, Position] = mutable.Map.empty[Target, Position],
trampolineToTarget: mutable.Map[Trampoline, Target] = mutable.Map.empty[Trampoline, Target],
targetToTrampolines: mutable.Map[Target, List[Trampoline]] = mutable.Map.empty[Target, List[Trampoline]],
growth: Int = 25) {
val log = Core.log
}
case class Simulator(parameter: Parameter) {
import Core._
val log = Logger[this.type]
var X = parameter.X
var Y = parameter.Y
def simulate(state: State, moves: List[Move]): State = {
log.debug("Strting simulation: " + parameter)
simulateMoves(state, moves)
}
def simulate(state: State, moves: String): State = simulate(state, toMoves(moves))
def simulateMoves(state: State, moves: List[Move]): State = {
debug(state, moves)
state.condition match {
case NormalCondition => moves match {
case move :: tail => simulateMoves(simulateMove(state, move), tail)
case Nil => state
}
case _ => {
// if (!moves.isEmpty)
// log.error("move remains: " + moves)
state
}
}
}
def updateMap(state: State): State = {
var map = state.map
var newmap = map
var crash = false
for {
y <- 1 until (Y - 1)
x <- 1 until (X - 1)
c = map(x)(y)
if (c == ROCK || c == HIGH_ROCK)
} {
if (map(x)(y - 1) == SPACE) {
newmap = updated(newmap, x, y, SPACE)
newmap = updated(newmap, x, y - 1, c)
if (map(x)(y - 2) == ROBOT)
crash = true
else if (c == HIGH_ROCK && (map(x)(y-2) != SPACE))
newmap = updated(newmap, x, y - 1, LAMBDA)
} else if (map(x)(y - 1) == ROCK || map(x)(y - 1) == HIGH_ROCK) {
if (map(x + 1)(y) == SPACE && map(x + 1)(y - 1) == SPACE) {
newmap = updated(newmap, x, y, SPACE)
newmap = updated(newmap, x + 1, y - 1, c)
if (map(x + 1)(y - 2) == ROBOT)
crash = true
else if (c == HIGH_ROCK && (map(x + 1)(y - 2) != SPACE))
newmap = updated(newmap, x + 1, y - 1, LAMBDA)
} else if (map(x - 1)(y) == SPACE && map(x - 1)(y - 1) == SPACE) {
newmap = updated(newmap, x, y, SPACE)
newmap = updated(newmap, x - 1, y - 1, c)
if (map(x - 1)(y - 2) == ROBOT)
crash = true
else if (c == HIGH_ROCK && (map(x - 1)(y - 2) != SPACE))
newmap = updated(newmap, x + 1, y - 1, LAMBDA)
}
} else if (map(x)(y - 1) == LAMBDA && map(x + 1)(y) == SPACE && map(x + 1)(y - 1) == SPACE) {
newmap = updated(newmap, x, y, SPACE)
newmap = updated(newmap, x + 1, y - 1, c)
if (map(x + 1)(y - 2) == ROBOT)
crash = true
else if (c == HIGH_ROCK && (map(x + 1)(y - 2) != SPACE))
newmap = updated(newmap, x + 1, y - 1, LAMBDA)
}
}
if (map != newmap) {
newmap = normalize(newmap)
}
if (crash)
state.copy(map=newmap, condition=LosingCondition)
else
waterCheck(growBeard(state.copy(map=newmap)))
}
def growBeard(state: State): State = {
if (state.steps % parameter.growth == 0) {
val map = state.map
var newmap = map
for {
y <- 1 until (Y - 1)
x <- 1 until (X - 1)
if (map(x)(y) == BEARD)
nx <- (x - 1) to (x + 1)
ny <- (y - 1) to (y + 1)
if (newmap(nx)(ny) == SPACE)
} newmap = updated(newmap, nx, ny, BEARD)
state.copy(map=newmap)
} else {
state
}
}
def waterCheck(state: State): State = {
// log.info(">>> waterCheck: state:\n" + state.dump)
val waterLevel = parameter.water +
(if (parameter.flooding != 0) state.steps / parameter.flooding
else 0)
if (state.robot.y <= waterLevel)
if (state.inWater == parameter.waterproof)
state.copy(condition=LosingCondition)
else
state.copy(inWater=state.inWater + 1)
else
state.copy(inWater=0)
}
def moveRobot(state: State, newRobot: Position, move: Move): State = {
val map = state.map
var newmap = state.map
val nx = newRobot.x
val ny = newRobot.y
map(nx)(ny) match {
case SPACE => {
newmap = updated(newmap, nx, ny, ROBOT)
newmap = updated(newmap, state.robot.x, state.robot.y, SPACE)
updateMap(state.copy(map=newmap, robot=newRobot))
}
case EARTH => {
newmap = updated(newmap, nx, ny, ROBOT)
newmap = updated(newmap, state.robot.x, state.robot.y, SPACE)
updateMap(state.copy(map=newmap, robot=newRobot))
}
case RAZOR => {
newmap = updated(newmap, nx, ny, ROBOT)
newmap = updated(newmap, state.robot.x, state.robot.y, SPACE)
updateMap(state.copy(map=newmap, robot=newRobot, razors=state.razors + 1))
}
case LAMBDA => {
newmap = updated(newmap, nx, ny, ROBOT)
newmap = updated(newmap, state.robot.x, state.robot.y, SPACE)
updateMap(state.copy(map=newmap, robot=newRobot, lambda=state.lambda + 1))
}
case LIFT => {
if (state.lambda == parameter.lambda) {
newmap = updated(newmap, nx, ny, ROBOT)
newmap = updated(newmap, state.robot.x, state.robot.y, SPACE)
state.copy(map=newmap, condition=WinningCondition, robot=newRobot)
} else
updateMap(state)
}
case ROCK => move match {
case Right => {
if (map(nx + 1)(ny) == SPACE) {
newmap = updated(newmap, nx, ny, ROBOT)
newmap = updated(newmap, state.robot.x, state.robot.y, SPACE)
newmap = updated(newmap, nx + 1, ny, ROCK)
updateMap(state.copy(map=newmap, robot=newRobot))
} else
updateMap(state)
}
case Left => {
if (map(nx - 1)(ny) == SPACE) {
newmap = updated(newmap, nx, ny, ROBOT)
newmap = updated(newmap, state.robot.x, state.robot.y, SPACE)
newmap = updated(newmap, nx - 1, ny, ROCK)
updateMap(state.copy(map=newmap, robot=newRobot))
} else
updateMap(state)
}
case _ => updateMap(state)
}
case WALL => updateMap(state)
case BEARD => updateMap(state)
case c if isTrampoline(c) => {
val trampoline = Trampoline(c)
val target = parameter.trampolineToTarget(trampoline)
var targetPosition = parameter.targetPosition(target)
newmap = updated(newmap, targetPosition.x, targetPosition.y, ROBOT)
newmap = updated(newmap, state.robot.x, state.robot.y, SPACE)
for (trampoline <- parameter.targetToTrampolines(target)) {
val pos = parameter.trampolinePosition(trampoline)
newmap = updated(newmap, pos.x, pos.y, SPACE)
}
updateMap(state.copy(map=newmap, robot=targetPosition))
}
case c if isTarget(c) => updateMap(state)
case _ => throw new GameException()
}
}
def useRazor(state: State): State = {
if (state.razors == 0)
updateMap(state)
else {
val map = state.map
var newmap = state.map
for {
nx <- (state.robot.x - 1) to (state.robot.x + 1)
ny <- (state.robot.y - 1) to (state.robot.y + 1)
if (map(nx)(ny) == BEARD)
} newmap = updated(newmap, nx, ny, SPACE)
updateMap(state.copy(map=newmap, razors=state.razors - 1))
}
}
def simulateMove(state: State, move: Move): State = {
// log.info(">>> simulateMove: state:\n" + state.dump + "\nMove: " + move)
state.condition match {
case AbortCondition => state
case WinningCondition => state
case LosingCondition => state
case NormalCondition => {
val robot = state.robot
val newstate = state.copy(steps=state.steps + 1)
move match {
case Up => moveRobot(newstate, robot.copy(y=robot.y + 1), move)
case Down => moveRobot(newstate, robot.copy(y=robot.y - 1), move)
case Left => moveRobot(newstate, robot.copy(x=robot.x - 1), move)
case Right => moveRobot(newstate, robot.copy(x=robot.x + 1), move)
case Abort => state.copy(condition=AbortCondition)
case Wait => updateMap(newstate)
case Sci => useRazor(newstate)
}
}
}
}
def debug(state: State, moves: List[Move]) {
log.debug("state:\n" + state.dump)
log.debug("moves: " + dumpMoves(moves))
}
}
object Reader {
import Core._
def readBoard(str: String): Tuple2[Parameter, State] = {
val log = Logger[this.type]
val lines = str.split("\n")
var (mapLines, parameterLines) = lines.span(!_.isEmpty)
mapLines.foreach { line => log.debug("map: " + line) }
parameterLines.foreach { line => log.debug("parameter: " + line) }
mapLines = mapLines.reverse
val X = mapLines.map(_.size).max + 2
val Y = mapLines.size + 2
var parameter = Parameter(X=X, Y=Y)
val map = IndexedSeq.tabulate[Char](X, Y)((x, y) => {
if (x == 0 || x == X - 1) WALL
else if (y == 0 || y == Y - 1) WALL
else if (x - 1 < mapLines(y - 1).size) mapLines(y - 1)(x - 1)
else SPACE
})
var robot: Position = null
for (x <- 0 until X) {
for (y <- 0 until Y) {
map(x)(y) match {
case ROBOT => {
robot = Position(x, y)
}
case LAMBDA => parameter = parameter.copy(lambda=parameter.lambda + 1)
case HIGH_ROCK => parameter = parameter.copy(lambda=parameter.lambda + 1)
case c if isTrampoline(c) => parameter.trampolinePosition(Trampoline(c)) = Position(x, y)
case c if isTarget(c) => parameter.targetPosition(Target(c)) = Position(x, y)
case _ => Unit
}
}
}
var razors = 0
for {
line <- parameterLines
trimmed = line.trim
if !trimmed.isEmpty
array = trimmed.split(SPACE)
if array.size != 0
} array(0) match {
case "Water" => parameter = parameter.copy(water=array(1).toInt)
case "Flooding" => parameter = parameter.copy(flooding=array(1).toInt)
case "Waterproof" => parameter = parameter.copy(waterproof=array(1).toInt)
case "Trampoline" => {
assert(array.size == 4)
assert(array(1).length == 1)
val trampoline = Trampoline(array(1)(0))
assert(array(2) == "targets")
assert(array(3).length == 1)
val target = Target(array(3)(0))
parameter.trampolineToTarget(trampoline) = target
if (parameter.targetToTrampolines.contains(target))
parameter.targetToTrampolines(target) = trampoline :: parameter.targetToTrampolines(target)
else
parameter.targetToTrampolines(target) = List(trampoline)
}
case "Growth" => parameter = parameter.copy(growth=array(1).toInt)
case "Razors" => razors=array(1).toInt
}
assert(parameter.growth > 0)
Tuple2(parameter, State(map=normalize(map), robot=robot, razors=razors))
}
}
abstract class Bot {
val log = Logger[this.type]
def run(parameter: Parameter, state: State): List[Move]
var bestMoves: List[Move] = Nil
def path2moves(path: List[Position]): List[Move] = path match {
case Nil => Nil
case head :: Nil => Nil
case head :: next :: tail => head.to(next) :: path2moves(next :: tail)
}
val moveCommands = List(Up, Down, Left, Right)
}
case class SABot(maxIteration: Int = 10000000) extends Bot {
import Core._
override def run(parameter: Parameter, state: State): List[Move] = {
val simulator = Simulator(parameter)
val start = state.robot
var iteration = 0
val StopSearch = -100000000
def hScore(parameter: Parameter, state: State): Int = state.condition match {
case WinningCondition => 0
case LosingCondition => 0
case AbortCondition => 0
case NormalCondition => calulucateHScore(parameter, state)
}
def calulucateHScore(parameter: Parameter, state: State): Int = {
val start = state.robot
val map = state.map
val X = state.X
val Y = state.Y
val lambdaRemains = parameter.lambda - state.lambda
val maxDistance = X + Y
def passMaybe(pos: Position): Boolean = {
val c = map(pos.x)(pos.y)
// Todo: More huelistic.
!walllike(c) || c == LIFT
}
case class Node(pos: Position, distance: Int)
def distanceToObjectsScore: Int = {
val visited = mutable.Set.empty[Position]
val queue = mutable.Queue.empty[Node]
var distanceToLambdas = List.empty[Int]
var distanceToInterestings = List.empty[Int]
queue += Node(start, 0)
visited += start
while (queue.nonEmpty) {
val Node(pos, dist) = queue.dequeue()
val c = map(pos.x)(pos.y)
(if (isTrampoline(c)) {
val trampoline = Trampoline(c)
val target = parameter.trampolineToTarget(trampoline)
val next = parameter.targetPosition(target)
List(next)
} else {
pos.nextPositions
}).filter(passMaybe).foreach(next => {
if (!visited.contains(next)) {
visited += next
queue += Node(next, dist + 1)
// TODO(hayato): Handle lift separately???
val nextC = map(next.x)(next.y)
if (nextC == LAMBDA || nextC == LIFT || nextC == HIGH_ROCK)
distanceToLambdas = dist :: distanceToLambdas
}
})
}
if (distanceToLambdas.isEmpty)
return StopSearch
if (lambdaRemains + 1 != distanceToLambdas.size) {
// Penalty to unreachable lambada or lift.
// println("Unreachable")
// println("state: \n" + state.dump)
// println("lambda: " + distanceToLambdas)
return -10000
}
// TODO(hayato): Improve. Increase score if the number of remaining lambda is small.
var score = distanceToLambdas.map(d => (50 - d).max(0)).sum
// Like Simulate Annulate...?
// score = score * math.max(300 - iteration, 100) / 100
// score += distanceToInterestings.map(d => (10 - d).max(0)).sum
score
}
distanceToObjectsScore
}
def nextDestinationChadidates(state: State): List[List[Move]] = {
sealed abstract class SearchMode
object ConsumeSpace extends SearchMode
object ConsumeEarth extends SearchMode
object Start extends SearchMode
object Reached extends SearchMode
case class Node(pos: Position, mode: SearchMode, moves: List[Move]) {
def key: Key = Key(pos, mode)
}
case class Key(pos: Position, mode: SearchMode)
val map = state.map
var candidates: List[List[Move]] = Nil
val visited = mutable.Set.empty[Key]
val queue = mutable.Queue.empty[Node]
val startPos = state.robot
val start = Node(state.robot, Start, Nil)
queue += start
visited += start.key
def addIf(node: Node) {
if (!visited.contains(node.key)) {
queue += node
visited += node.key
}
}
def supportsRock(pos: Position): Boolean = {
map(pos.x)(pos.y + 1) == ROCK || map(pos.x - 1)(pos.y) == ROCK || map(pos.x + 1)(pos.y) == ROCK
}
def addCandidate(movesReversed: List[Move]) { candidates = movesReversed.reverse :: candidates }
while (queue.nonEmpty) {
val Node(pos, mode, moves) = queue.dequeue()
pos.nextPositions.filterNot(_ == startPos).foreach(nextPos => {
val move = pos.to(nextPos)
val c = map(nextPos.x)(nextPos.y)
(mode, c) match {
case (Start, SPACE) => addIf(Node(nextPos, ConsumeSpace, move :: moves))
case (Start, EARTH) => {
if (supportsRock(nextPos))
addCandidate(move :: moves)
else
addIf(Node(nextPos, ConsumeEarth, move :: moves))
}
case (ConsumeSpace, SPACE) => addIf(Node(nextPos, ConsumeSpace, move :: moves))
case (ConsumeEarth, EARTH) => {
if (supportsRock(nextPos))
addCandidate(move :: moves)
else
addIf(Node(nextPos, ConsumeEarth, move :: moves))
}
case (_, WALL) => Unit
// Todo: Only we can push rock.
// case (_, ROCK) => Unit
case (_, nextC) => addCandidate(move :: moves)
}
})
}
candidates
}
case class Key(map: Board)
// Todo: Emphasis h on the first ...
case class Node(state: State, score: Int, h: Int, moves: List[Move]) extends Ordered[Node] {
override def compare(other: Node) = {
if (score + h < other.score + other.h) -1
else if (score + h > other.score + other.h) 1
else 0
}
def key: Key = Key(map=state.map)
def dump: String = "state:\n" + state.dump + "\nScore:\n" + score + "\nhScore:\n" + h + "\nmoves:\n" + dumpMoves(moves).reverse
}
// TODO(hayato): Fix it.
def canMove(pos: Position, state: State): Boolean = true
val startNode = Node(state, state.score, hScore(parameter, state), Nil)
// val visited = mutable.Set.empty[Key]
val visited = mutable.Map.empty[Key, Int]
val queue = mutable.PriorityQueue.empty[Node]
queue += startNode
visited(startNode.key) = startNode.score
bestMoves = Nil
var bestScore = 0
while (queue.nonEmpty && iteration < maxIteration) {
iteration += 1
val node = queue.dequeue()
val Node(state, score, h, moves) = node
if (score > bestScore) {
// println("iteration: " + iteration)
// println("Best Score Found:" + score)
// println("queue.size:" + queue.size)
bestScore = score
bestMoves = moves
}
// if (iteration % 1000 == 0) {
// println("iteration: " + iteration)
// println("node: \n" + node.dump)
// }
var candidates = nextDestinationChadidates(state)
// println("candidates " + candidates.map(dumpMoves(_)))
candidates.foreach(nextMoves => {
val nextState = simulator.simulateMoves(state, nextMoves)
// Todo: Omit caluculate hscore. Order is wrong.
val nextHScore = hScore(parameter, nextState)
val nextNode = Node(nextState, nextState.score, nextHScore, moves ::: nextMoves)
nextHScore match {
case StopSearch => Unit
case _ => visited.get(nextNode.key) match {
case Some(previousScore) => {
if (nextNode.score > previousScore) {
queue += nextNode
visited(nextNode.key) = nextNode.score
}
}
case None => {
queue += nextNode
visited(nextNode.key) = nextNode.score
}
}
}
})
}
bestMoves
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment