Mercurial > repos > icfp2012
view src/lifter.tp @ 45:9f1ca5ba2684
Discard entries for which we can easily tell that it will be impossible for them to be better than the current best. This allows us to terminate when we cannot solve the map
author | Mike Pavone <pavone@retrodev.com> |
---|---|
date | Sun, 15 Jul 2012 17:26:25 -0700 |
parents | 0c09730c173e |
children | fbeedb3aa239 |
line wrap: on
line source
#{ pqueue <- { normalnode <- :pri val { #{ priority <- pri value <- val next <- false higherPriority? <- :other { priority > (other priority) } if:else <- :self trueblock :elseblock { trueblock: } } } head <- #{ higherPriority? <- :other {false} next <- { self } value <- { false } } #{ take <- { cur <- head head <- cur next cur value } insert:atPriority <- :val pri { node <- normalnode: pri val cur <- head last <- false while: {cur higherPriority?: node} do: { last <- cur cur <- cur next } if: last { node next!: (last next) last next!: node } else: { node next!: head head <- node } self } } } abs <- :val { if: val < 0 { 0 - val } else: { val } } distanceFrom:to <- :sx sy :dx dy { (abs: sx - dx) + (abs: sy - dy) } moveFinder <- :field { #{ curbest <- (field clone) advance: "A" playfield <- field bestMove:withMaxSteps <- :self :max{ n <- 0 states <- #[playfield] while: { if: (states length) > 0 { if: n < max { not: (curbest succeeded) } } } do: { nextstates <- #[] foreach: states :idx curstate { me <-curstate getRobot candidates <- curstate validMoves: (me x) (me y) foreach: candidates :idx move { curfield <- curstate clone curfield advance: (move cmd) if: (curfield ended) { if: (curfield score) > (curbest score) { curbest <- curfield } } else: { //check theoretical max score for current map state //discard paths that can never be better than our current best if: (curfield maxScore) > (curbest score) { nextstates append: curfield } } } } states <- nextstates n <- n + 1 } if: (curbest succeeded) { false } else: { if: (states length) > 0 { bestofcur <- states get: 0 n <- 1 while: { n < (states length) } do: { curstate <- states get: n if: ((curstate score) > (bestofcur score)) { bestofcur <- curstate } n <- n + 1 } playfield <- bestofcur true } } } } } main <- { text <- sim readFd: 0 initial <- (sim state) fromStr: text os write: 2 text os write: 2 "width: " . (string: (initial width)) . "\n" os write: 2 "height: " . (string: (initial height)) . "\n" finder <- moveFinder: initial while: { bestMove: finder withMaxSteps: 5 } do: { os write: 2 "--------iteration results-------\n" os write: 2 "Best:\n" (finder curbest) printGrid os write: 2 "Current:\n" (finder playfield) printGrid } os write: 2 "---------------\n" os write: 2 "End Best:\n" (finder curbest) printGrid } }