Mercurial > repos > icfp2013
annotate src/solver.tp @ 48:855c05c9cae1
Updated myproblems.json. Some solver fixes
author | Mike Pavone <pavone@retrodev.com> |
---|---|
date | Sun, 11 Aug 2013 04:03:51 -0700 |
parents | e795f7179456 |
children | 8409af16d6e5 |
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 { | |
126 testvals <- #[] | |
127 i <- 0 | |
128 (os srand: (os time)) | |
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 { |
44
e795f7179456
Print some timestamps of request times in solver
Mike Pavone <pavone@retrodev.com>
parents:
40
diff
changeset
|
141 start <- os time |
38 | 142 resp <- (requests evalId: progId (info allInputs)) sendWithKey: authKey |
44
e795f7179456
Print some timestamps of request times in solver
Mike Pavone <pavone@retrodev.com>
parents:
40
diff
changeset
|
143 end <- os time |
48
855c05c9cae1
Updated myproblems.json. Some solver fixes
Mike Pavone <pavone@retrodev.com>
parents:
44
diff
changeset
|
144 if: (end - start) < 4 { |
855c05c9cae1
Updated myproblems.json. Some solver fixes
Mike Pavone <pavone@retrodev.com>
parents:
44
diff
changeset
|
145 os sleep: (4 - (end - start)) |
855c05c9cae1
Updated myproblems.json. Some solver fixes
Mike Pavone <pavone@retrodev.com>
parents:
44
diff
changeset
|
146 } |
38 | 147 if: (resp status) = "ok" { |
48
855c05c9cae1
Updated myproblems.json. Some solver fixes
Mike Pavone <pavone@retrodev.com>
parents:
44
diff
changeset
|
148 print: "Start: " . (string: start) . ", End: " . (string: start) . "Duration: " . (string: end - start) . "\n" |
38 | 149 matches <- info findMatches: (resp outputs) at: 0 |
150 noSuccess <- true | |
151 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
|
152 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
|
153 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
|
154 print: info |
1cadb591eef1
Fix bug that was causing the solver to not find certain matches
Mike Pavone <pavone@retrodev.com>
parents:
38
diff
changeset
|
155 } |
38 | 156 while: { noSuccess && cur < (matches length) } do: { |
157 prog root!: (matches get: cur) | |
44
e795f7179456
Print some timestamps of request times in solver
Mike Pavone <pavone@retrodev.com>
parents:
40
diff
changeset
|
158 gstart <- os time |
38 | 159 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
|
160 gend <- os time |
48
855c05c9cae1
Updated myproblems.json. Some solver fixes
Mike Pavone <pavone@retrodev.com>
parents:
44
diff
changeset
|
161 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
|
162 if: (gend - gstart) < 4 { |
855c05c9cae1
Updated myproblems.json. Some solver fixes
Mike Pavone <pavone@retrodev.com>
parents:
44
diff
changeset
|
163 os sleep: (4 - (gend - gstart)) |
855c05c9cae1
Updated myproblems.json. Some solver fixes
Mike Pavone <pavone@retrodev.com>
parents:
44
diff
changeset
|
164 } |
38 | 165 if: (gresp status) = "win" { |
166 noSuccess <- false | |
167 } else: { | |
168 if: (gresp status) = "mismatch" { | |
169 failInput <- (gresp values) get: 0 | |
170 failOutput <- (gresp values) get: 1 | |
171 filtered <- #[] | |
172 foreach: matches :idx tree { | |
173 prog root!: tree | |
174 if: (prog run: failInput) = failOutput { | |
175 filtered append: tree | |
176 } | |
177 } | |
178 matches <- filtered | |
179 if: (matches length) = 0 { | |
180 print: "None of our programs actually matched 0x" . (hex: failOutput) ." with input 0x" . (hex: failInput) ." :(\n" | |
181 } | |
182 } else: { | |
183 print: "Got message: " . (gresp message) . ", moving on\n" | |
184 cur <- cur + 1 | |
185 } | |
186 } | |
187 } | |
188 } else: { | |
189 print: resp | |
190 } | |
191 } | |
192 | |
33 | 193 main <- :args { |
194 size <- 3 | |
195 if: (args length) > 1 { | |
196 size <- int32: (args get: 1) | |
32 | 197 } |
33 | 198 prog <- bv program |
199 if: size >= 2 { | |
200 trees <- (prog allOfSize: size) | |
201 numTests <- 0 | |
202 if: (args length) > 2 { | |
203 numTests <- int32: (args get: 2) | |
204 } | |
205 if: numTests <= 0 { | |
206 numTests <- 16 | |
207 } | |
208 if: (args length) > 3 { | |
209 ops <- (args get: 3) splitOn: "," | |
210 trees <- prog filterTrees: trees ops | |
211 } | |
212 info <- classify: prog trees numTests | |
38 | 213 if: (args length) > 5 { |
214 progId <- (args get: 4) | |
215 authKey <- (args get: 5) | |
216 | |
217 solve: progId withAuth: authKey andInfo: info andProg: prog | |
218 } else: { | |
219 print: info | |
220 } | |
32 | 221 } |
38 | 222 0 |
32 | 223 } |
224 } | |
225 } |