Mercurial > repos > icfp2013
annotate src/solver.tp @ 56:f864792a1b17
Improve prefiltering in program generator. Make solver use similar logic to driver when run standalone.
| author | Mike Pavone <pavone@retrodev.com> |
|---|---|
| date | Sun, 11 Aug 2013 14:11:47 -0700 |
| parents | f4399a22a704 |
| children | c50f0fb9a717 |
| rev | line source |
|---|---|
| 33 | 1 { |
| 2 _classifNode <- :vals prog startIdx child? { | |
| 3 if: startIdx < (vals length) { | |
| 4 _dict <- dict linear | |
| 5 _const <- #[] | |
| 6 _first <- false | |
| 7 _hasFirst? <- false | |
| 8 _val <- vals get: startIdx | |
| 9 #{ | |
| 10 input <- { _val } | |
| 11 valmap <- { _dict } | |
| 38 | 12 allInputs <- { vals } |
| 33 | 13 constantProgs <- { _const } |
| 14 append <- :tree { | |
| 15 if: child? && (tree constant?) { | |
| 16 _const append: tree | |
| 17 } else: { | |
| 18 if: (_dict length) > 0 { | |
| 19 prog root!: tree | |
| 20 res <- prog run: _val | |
| 21 node <- _dict get: res elseSet: { | |
| 22 _classifNode: vals prog startIdx + 1 true | |
| 23 } | |
| 24 node append: tree | |
| 25 } else: { | |
| 26 if: _hasFirst? { | |
| 27 prog root!: _first | |
| 28 res <- prog run: _val | |
| 29 node <- _classifNode: vals prog startIdx + 1 true | |
| 30 _dict set: res node | |
| 31 node append: _first | |
| 32 append: tree | |
| 33 } else: { | |
| 34 _first <- tree | |
| 35 _hasFirst? <- true | |
| 36 } | |
| 37 } | |
| 38 } | |
| 39 } | |
| 40 length <- { | |
| 41 len <- _dict length | |
| 42 if: len = 0 && _hasFirst? { | |
| 43 len <- 1 | |
| 44 } | |
| 38 | 45 len + (_const length) |
| 33 | 46 } |
| 47 printwithIndent <- :indent { | |
| 48 print: indent . "Input: " . (hex: _val) . "\n" | |
| 49 nextindent <- indent . " " | |
| 50 if: (_const length) > 0 { | |
| 51 print: indent . "Constants:\n" | |
| 52 foreach: _const :idx val { | |
| 53 print: nextindent . (string: val) . "\n" | |
| 54 } | |
| 55 } | |
| 56 if: (_dict length) > 0 { | |
| 57 foreach: _dict :key val { | |
| 58 print: indent . (hex: key) . " ->\n" | |
| 59 val printwithIndent: nextindent | |
| 60 } | |
| 61 } else: { | |
| 62 if: _hasFirst? { | |
| 63 print: nextindent . (string: _first) . "\n" | |
| 64 } | |
| 65 } | |
| 66 } | |
| 67 print <- { | |
| 68 printwithIndent: "" | |
| 69 } | |
| 38 | 70 findMatches:at <- :outputs :startIdx { |
| 71 outVal <- outputs get: startIdx | |
| 72 sub <- _dict get: outVal withDefault: #{ | |
| 73 length <- { 0 } | |
| 74 } | |
| 75 res <- #[] | |
| 76 if: (sub length) > 0 { | |
| 77 res <- sub findMatches: outputs at: (startIdx + 1) | |
| 78 cps <- sub constantProgs | |
| 79 if: (cps length) > 0 { | |
| 80 isConstant <- true | |
| 81 cur <- 0 | |
| 82 while: { isConstant && cur < (cps length)} do: { | |
| 83 isConstant <- outVal = (outputs get: cur) | |
| 84 cur <- cur + 1 | |
| 85 } | |
| 86 if: isConstant { | |
| 87 foreach: cps :idx tree { | |
| 88 res append: cps | |
| 89 } | |
| 90 } | |
| 91 } | |
|
40
1cadb591eef1
Fix bug that was causing the solver to not find certain matches
Mike Pavone <pavone@retrodev.com>
parents:
38
diff
changeset
|
92 } else: { |
|
1cadb591eef1
Fix bug that was causing the solver to not find certain matches
Mike Pavone <pavone@retrodev.com>
parents:
38
diff
changeset
|
93 if: _hasFirst? { |
|
1cadb591eef1
Fix bug that was causing the solver to not find certain matches
Mike Pavone <pavone@retrodev.com>
parents:
38
diff
changeset
|
94 res append: _first |
|
1cadb591eef1
Fix bug that was causing the solver to not find certain matches
Mike Pavone <pavone@retrodev.com>
parents:
38
diff
changeset
|
95 } |
| 38 | 96 } |
| 97 res | |
| 98 } | |
| 33 | 99 } |
| 100 } else: { | |
| 101 _arr <- #[] | |
| 102 #{ | |
| 103 append <- :tree { | |
| 104 _arr append: tree | |
| 105 } | |
| 106 length <- { _arr length } | |
| 38 | 107 constantProgs <- { #[] } |
| 33 | 108 printwithIndent <- :indent { |
| 109 print: indent . "No more values for these:\n" | |
| 110 indent <- indent . " " | |
| 111 foreach: _arr :idx val { | |
| 112 print: indent . (string: val) . "\n" | |
| 113 } | |
| 114 } | |
| 115 print <- { | |
| 116 printwithIndent: "" | |
| 117 } | |
| 38 | 118 findMatches:at <- :outputs :startIdx { |
| 119 _arr | |
| 120 } | |
| 32 | 121 } |
| 122 } | |
| 123 } | |
| 33 | 124 #{ |
| 125 classify <- :prog trees numTests { | |
|
50
f4399a22a704
Fix crash from calling srand during module initialization
Mike Pavone <pavone@retrodev.com>
parents:
49
diff
changeset
|
126 (os srand: (os time)) |
| 33 | 127 testvals <- #[] |
| 128 i <- 0 | |
| 129 while: {i < numTests} do: { | |
| 130 i <- i + 1 | |
| 131 testvals append: (uint64: (os rand64)) | |
| 132 } | |
| 133 root <- _classifNode: testvals prog 0 false | |
| 134 foreach: trees :idx tree { | |
| 135 root append: tree | |
| 136 } | |
| 137 root | |
| 32 | 138 } |
| 33 | 139 |
| 38 | 140 solve:withAuth:andInfo:andProg <- :progId :authKey :info :prog { |
|
49
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
141 statusCode <- 429 |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
142 resp <- false |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
143 start <- 0 |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
144 end <- 0 |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
145 while: { statusCode = 429} do: { |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
146 start <- os time |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
147 resp <- (requests evalId: progId (info allInputs)) sendWithKey: authKey |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
148 end <- os time |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
149 if: (resp status) = "ok" { |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
150 statusCode <- 200 |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
151 if: (end - start) < 4 { |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
152 os sleep: (4 - (end - start)) |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
153 } |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
154 } else: { |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
155 statusCode <- resp httpCode |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
156 if: statusCode = 429 { |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
157 print: "API is pissed, waiting 20 seconds...\n" |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
158 os sleep: 20 |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
159 } |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
160 } |
|
48
855c05c9cae1
Updated myproblems.json. Some solver fixes
Mike Pavone <pavone@retrodev.com>
parents:
44
diff
changeset
|
161 } |
| 38 | 162 if: (resp status) = "ok" { |
|
48
855c05c9cae1
Updated myproblems.json. Some solver fixes
Mike Pavone <pavone@retrodev.com>
parents:
44
diff
changeset
|
163 print: "Start: " . (string: start) . ", End: " . (string: start) . "Duration: " . (string: end - start) . "\n" |
| 38 | 164 matches <- info findMatches: (resp outputs) at: 0 |
| 165 noSuccess <- true | |
| 166 cur <- 0 | |
|
40
1cadb591eef1
Fix bug that was causing the solver to not find certain matches
Mike Pavone <pavone@retrodev.com>
parents:
38
diff
changeset
|
167 if: (matches length) = 0 { |
|
1cadb591eef1
Fix bug that was causing the solver to not find certain matches
Mike Pavone <pavone@retrodev.com>
parents:
38
diff
changeset
|
168 print: "No matches? :(\n" |
|
1cadb591eef1
Fix bug that was causing the solver to not find certain matches
Mike Pavone <pavone@retrodev.com>
parents:
38
diff
changeset
|
169 print: info |
|
1cadb591eef1
Fix bug that was causing the solver to not find certain matches
Mike Pavone <pavone@retrodev.com>
parents:
38
diff
changeset
|
170 } |
| 38 | 171 while: { noSuccess && cur < (matches length) } do: { |
| 172 prog root!: (matches get: cur) | |
|
44
e795f7179456
Print some timestamps of request times in solver
Mike Pavone <pavone@retrodev.com>
parents:
40
diff
changeset
|
173 gstart <- os time |
| 38 | 174 gresp <- (requests guess: progId (string: prog)) sendWithKey: authKey |
|
44
e795f7179456
Print some timestamps of request times in solver
Mike Pavone <pavone@retrodev.com>
parents:
40
diff
changeset
|
175 gend <- os time |
|
48
855c05c9cae1
Updated myproblems.json. Some solver fixes
Mike Pavone <pavone@retrodev.com>
parents:
44
diff
changeset
|
176 print: "Start: " . (string: gstart) . ", End: " . (string: gend) . "Duration: " . (string: gend - gstart) . "\n" |
|
855c05c9cae1
Updated myproblems.json. Some solver fixes
Mike Pavone <pavone@retrodev.com>
parents:
44
diff
changeset
|
177 if: (gend - gstart) < 4 { |
|
855c05c9cae1
Updated myproblems.json. Some solver fixes
Mike Pavone <pavone@retrodev.com>
parents:
44
diff
changeset
|
178 os sleep: (4 - (gend - gstart)) |
|
855c05c9cae1
Updated myproblems.json. Some solver fixes
Mike Pavone <pavone@retrodev.com>
parents:
44
diff
changeset
|
179 } |
| 38 | 180 if: (gresp status) = "win" { |
| 181 noSuccess <- false | |
| 182 } else: { | |
| 183 if: (gresp status) = "mismatch" { | |
| 184 failInput <- (gresp values) get: 0 | |
| 185 failOutput <- (gresp values) get: 1 | |
| 186 filtered <- #[] | |
| 187 foreach: matches :idx tree { | |
| 188 prog root!: tree | |
| 189 if: (prog run: failInput) = failOutput { | |
| 190 filtered append: tree | |
| 191 } | |
| 192 } | |
|
50
f4399a22a704
Fix crash from calling srand during module initialization
Mike Pavone <pavone@retrodev.com>
parents:
49
diff
changeset
|
193 print: "Mismatch: went from " . (matches length) . " to " . (filtered length) . "\n" |
| 38 | 194 matches <- filtered |
| 195 if: (matches length) = 0 { | |
| 196 print: "None of our programs actually matched 0x" . (hex: failOutput) ." with input 0x" . (hex: failInput) ." :(\n" | |
| 197 } | |
| 198 } else: { | |
|
49
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
199 if: (gresp httpCode) = 429 { |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
200 print: "API is pissed, waiting 20 seconds...\n" |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
201 os sleep: 20 |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
202 } else: { |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
203 print: "Got message: " . (gresp message) . ", moving on\n" |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
204 cur <- cur + 1 |
|
8409af16d6e5
Sleep for 20 seconds when we receive a 429 response
Mike Pavone <pavone@retrodev.com>
parents:
48
diff
changeset
|
205 } |
| 38 | 206 } |
| 207 } | |
| 208 } | |
| 209 } else: { | |
| 210 print: resp | |
| 211 } | |
| 212 } | |
| 213 | |
| 33 | 214 main <- :args { |
| 215 size <- 3 | |
| 216 if: (args length) > 1 { | |
| 217 size <- int32: (args get: 1) | |
| 32 | 218 } |
| 33 | 219 prog <- bv program |
| 220 if: size >= 2 { | |
| 221 numTests <- 0 | |
| 222 if: (args length) > 2 { | |
| 223 numTests <- int32: (args get: 2) | |
| 224 } | |
| 225 if: numTests <= 0 { | |
| 226 numTests <- 16 | |
| 227 } | |
|
56
f864792a1b17
Improve prefiltering in program generator. Make solver use similar logic to driver when run standalone.
Mike Pavone <pavone@retrodev.com>
parents:
50
diff
changeset
|
228 trees <- #[] |
|
f864792a1b17
Improve prefiltering in program generator. Make solver use similar logic to driver when run standalone.
Mike Pavone <pavone@retrodev.com>
parents:
50
diff
changeset
|
229 |
| 33 | 230 if: (args length) > 3 { |
| 231 ops <- (args get: 3) splitOn: "," | |
|
56
f864792a1b17
Improve prefiltering in program generator. Make solver use similar logic to driver when run standalone.
Mike Pavone <pavone@retrodev.com>
parents:
50
diff
changeset
|
232 if: size < 10 { |
|
f864792a1b17
Improve prefiltering in program generator. Make solver use similar logic to driver when run standalone.
Mike Pavone <pavone@retrodev.com>
parents:
50
diff
changeset
|
233 trees <- prog filterTrees: (prog allOfSize: size) ops |
|
f864792a1b17
Improve prefiltering in program generator. Make solver use similar logic to driver when run standalone.
Mike Pavone <pavone@retrodev.com>
parents:
50
diff
changeset
|
234 } else: { |
|
f864792a1b17
Improve prefiltering in program generator. Make solver use similar logic to driver when run standalone.
Mike Pavone <pavone@retrodev.com>
parents:
50
diff
changeset
|
235 print: "Generating programs for operators: " . (ops fold: "" with: :acc el { acc . el }) . "\n" |
|
f864792a1b17
Improve prefiltering in program generator. Make solver use similar logic to driver when run standalone.
Mike Pavone <pavone@retrodev.com>
parents:
50
diff
changeset
|
236 trees <- prog allOfSize: size withOps: ops |
|
f864792a1b17
Improve prefiltering in program generator. Make solver use similar logic to driver when run standalone.
Mike Pavone <pavone@retrodev.com>
parents:
50
diff
changeset
|
237 print: "Generated " . (string: (trees length)) . " programs\n" |
|
f864792a1b17
Improve prefiltering in program generator. Make solver use similar logic to driver when run standalone.
Mike Pavone <pavone@retrodev.com>
parents:
50
diff
changeset
|
238 trees <- prog filterTrees: trees ops |
|
f864792a1b17
Improve prefiltering in program generator. Make solver use similar logic to driver when run standalone.
Mike Pavone <pavone@retrodev.com>
parents:
50
diff
changeset
|
239 } |
|
f864792a1b17
Improve prefiltering in program generator. Make solver use similar logic to driver when run standalone.
Mike Pavone <pavone@retrodev.com>
parents:
50
diff
changeset
|
240 } else: { |
|
f864792a1b17
Improve prefiltering in program generator. Make solver use similar logic to driver when run standalone.
Mike Pavone <pavone@retrodev.com>
parents:
50
diff
changeset
|
241 trees <- (prog allOfSize: size) |
| 33 | 242 } |
|
56
f864792a1b17
Improve prefiltering in program generator. Make solver use similar logic to driver when run standalone.
Mike Pavone <pavone@retrodev.com>
parents:
50
diff
changeset
|
243 print: "Running classifier on " . (string: (trees length)) . " programs\n" |
| 33 | 244 info <- classify: prog trees numTests |
| 38 | 245 if: (args length) > 5 { |
| 246 progId <- (args get: 4) | |
| 247 authKey <- (args get: 5) | |
| 248 | |
| 249 solve: progId withAuth: authKey andInfo: info andProg: prog | |
| 250 } else: { | |
| 251 print: info | |
| 252 } | |
| 32 | 253 } |
| 38 | 254 0 |
| 32 | 255 } |
| 256 } | |
| 257 } |