Mercurial > repos > icfp2012

annotate src/lifter.tp @ 45:9f1ca5ba2684

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
3
bb29dcd46cbf Put dummy code in placeholder source files. Create makefile.
Mike Pavone <pavone@retrodev.com>
parents: 0
diff changeset
1 #{
39
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
2 pqueue <- {
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
3 normalnode <- :pri val {
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
4 #{
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
5 priority <- pri
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
6 value <- val
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
7 next <- false
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
8 higherPriority? <- :other {
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
9 priority > (other priority)
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
10 }
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
11 if:else <- :self trueblock :elseblock {
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
12 trueblock:
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
13 }
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
14 }
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
15 }
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
16 head <- #{
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
17 higherPriority? <- :other {false}
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
18 next <- { self }
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
19 value <- { false }
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
20 }
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
21 #{
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
22 take <- {
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
23 cur <- head
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
24 head <- cur next
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
25 cur value
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
26 }
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
27 insert:atPriority <- :val pri {
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
28 node <- normalnode: pri val
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
29 cur <- head
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
30 last <- false
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
31 while: {cur higherPriority?: node} do: {
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
32 last <- cur
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
33 cur <- cur next
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
34 }
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
35 if: last {
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
36 node next!: (last next)
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
37 last next!: node
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
38 } else: {
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
39 node next!: head
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
40 head <- node
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
41 }
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
42 self
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
43 }
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
44 }
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
45 }
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
46
31
f7a1daaec925 Use dictionary
Mike Pavone <pavone@retrodev.com>
parents: 28
diff changeset
47 abs <- :val {
f7a1daaec925 Use dictionary
Mike Pavone <pavone@retrodev.com>
parents: 28
diff changeset
48 if: val < 0 { 0 - val } else: { val }
f7a1daaec925 Use dictionary
Mike Pavone <pavone@retrodev.com>
parents: 28
diff changeset
49 }
f7a1daaec925 Use dictionary
Mike Pavone <pavone@retrodev.com>
parents: 28
diff changeset
50
f7a1daaec925 Use dictionary
Mike Pavone <pavone@retrodev.com>
parents: 28
diff changeset
51 distanceFrom:to <- :sx sy :dx dy {
f7a1daaec925 Use dictionary
Mike Pavone <pavone@retrodev.com>
parents: 28
diff changeset
52 (abs: sx - dx) + (abs: sy - dy)
f7a1daaec925 Use dictionary
Mike Pavone <pavone@retrodev.com>
parents: 28
diff changeset
53 }
f7a1daaec925 Use dictionary
Mike Pavone <pavone@retrodev.com>
parents: 28
diff changeset
54
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
55 moveFinder <- :field {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
56 #{
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
57 curbest <- (field clone) advance: "A"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
58 playfield <- field
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
59 bestMove:withMaxSteps <- :self :max{
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
60 n <- 0
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
61 states <- #[playfield]
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
62 while: { if: (states length) > 0 { if: n < max { not: (curbest succeeded) } } } do: {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
63 nextstates <- #[]
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
64 foreach: states :idx curstate {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
65 me <-curstate getRobot
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
66 candidates <- curstate validMoves: (me x) (me y)
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
67 foreach: candidates :idx move {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
68 curfield <- curstate clone
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
69 curfield advance: (move cmd)
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
70 if: (curfield ended) {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
71 if: (curfield score) > (curbest score) {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
72 curbest <- curfield
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
73 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
74 } else: {
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
Mike Pavone <pavone@retrodev.com>
parents: 44
diff changeset
75 //check theoretical max score for current map state
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
Mike Pavone <pavone@retrodev.com>
parents: 44
diff changeset
76 //discard paths that can never be better than our current best
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
Mike Pavone <pavone@retrodev.com>
parents: 44
diff changeset
77 if: (curfield maxScore) > (curbest score) {
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
Mike Pavone <pavone@retrodev.com>
parents: 44
diff changeset
78 nextstates append: curfield
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
Mike Pavone <pavone@retrodev.com>
parents: 44
diff changeset
79 }
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
80 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
81 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
82 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
83 states <- nextstates
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
84 n <- n + 1
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
85 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
86 if: (curbest succeeded) {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
87 false
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
88 } else: {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
89 if: (states length) > 0 {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
90 bestofcur <- states get: 0
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
91 n <- 1
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
92 while: { n < (states length) } do: {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
93 curstate <- states get: n
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
94 if: ((curstate score) > (bestofcur score)) {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
95 bestofcur <- curstate
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
96 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
97 n <- n + 1
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
98 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
99 playfield <- bestofcur
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
100 true
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
101 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
102 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
103 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
104 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
105 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
106
3
bb29dcd46cbf Put dummy code in placeholder source files. Create makefile.
Mike Pavone <pavone@retrodev.com>
parents: 0
diff changeset
107 main <- {
20
50a456168c25 Split readFd out of readFile for use in lifter. Add code to read map from stdin to lifter using code in sim
Mike Pavone <pavone@retrodev.com>
parents: 3
diff changeset
108 text <- sim readFd: 0
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
109 initial <- (sim state) fromStr: text
20
50a456168c25 Split readFd out of readFile for use in lifter. Add code to read map from stdin to lifter using code in sim
Mike Pavone <pavone@retrodev.com>
parents: 3
diff changeset
110 os write: 2 text
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
111 os write: 2 "width: " . (string: (initial width)) . "\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
112 os write: 2 "height: " . (string: (initial height)) . "\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
113
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
114 finder <- moveFinder: initial
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
115 while: { bestMove: finder withMaxSteps: 5 } do: {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
116 os write: 2 "--------iteration results-------\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
117 os write: 2 "Best:\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
118 (finder curbest) printGrid
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
119 os write: 2 "Current:\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
120 (finder playfield) printGrid
39
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
121 }
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
122 os write: 2 "---------------\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
123 os write: 2 "End Best:\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
124 (finder curbest) printGrid
3
bb29dcd46cbf Put dummy code in placeholder source files. Create makefile.
Mike Pavone <pavone@retrodev.com>
parents: 0
diff changeset
125 }
bb29dcd46cbf Put dummy code in placeholder source files. Create makefile.
Mike Pavone <pavone@retrodev.com>
parents: 0
diff changeset
126 }