Thursday, July 14, 2005
Lispy or not?
I just started making Lisp versions my cop and robber entries from the ICFP contest. I am aware that because other languages I use don't have anything like Lisp's macros, I tend not to use macros in Lisp. I am trying to change that.
When I was coding my parser in ocaml, I thought it was cool to use the match statement to parse the various lines, like this:
Since I don't have match in Lisp, I wondered what would be a good way to do this in Lisp. I decided to do it with a macro. I keep a global hash table that maps keywords like "wsk\\" and "name:" to functions that handle the data for those keywords. I use a macro named defparse to create a function where instead of the name of the function, I supply the keyword name. Here is how I handle the "nod:" line for example:
One of the interesting things here is that you are seeing the function that handles the line, not just my definition of what is on the "nod:" line. In the ocaml version, I had all the keywords in one big match statement and made them call separate functions. I could have implemented the functions in the match statements but I thought it might look ugly. I like the Lisp solution here because I define the line contents and the function in one place, but it isn't all cluttered with other line definitions.
There are a couple of things going on in defparse. First, it turns the function body into a lambda expression that is mapped in the global keyword hash table. Next, it looks for parameters whose names end in # and automatically converts them from string to integer. This is what the expansion of my (defparse "nod:" ...) looks like:
Those #:G4171 and #:G4172 names are unique symbol names generated by the gensym function. A macro in Lisp is basically a function whose return value is code that will be compiled. This means that it blends in well with the language - there are a few syntactic differences having to do with quoting, but otherwise, you don't learn a separate macro language. One of the difficulties is that the macros run at compile time, so you can make use of all the functions you have defined (as far as I can tell, at least).
For the curious, here is my defparse macro:
The thing I am a bit curious about is whether this is a Lispy way to approach the problem. Would a Lisp pro nod his or her head at this, or start to gag?
When I was coding my parser in ocaml, I thought it was cool to use the match statement to parse the various lines, like this:
let parse_line line =
match Str.split (Str.regexp "[ \t]+") line with
"wsk\\" :: [] -> handle_wsk_start()
| "name:" :: name :: [] -> handle_name name
| "robber:" :: name :: [] -> handle_robber name
| "cop:" :: name :: [] -> handle_cop name
| "nod\\" :: [] -> handle_nodes_start()
| "nod:" :: name :: tag :: x :: y :: [] -> handle_node name (node_tag_of_string tag)
(int_of_string x) (int_of_string y)
Since I don't have match in Lisp, I wondered what would be a good way to do this in Lisp. I decided to do it with a macro. I keep a global hash table that maps keywords like "wsk\\" and "name:" to functions that handle the data for those keywords. I use a macro named defparse to create a function where instead of the name of the function, I supply the keyword name. Here is how I handle the "nod:" line for example:
(defparse "nod:" (name tag x# y#)
(push (make-instance 'node :name name :tag tag :x x# :y y#) *build-node-list*))
One of the interesting things here is that you are seeing the function that handles the line, not just my definition of what is on the "nod:" line. In the ocaml version, I had all the keywords in one big match statement and made them call separate functions. I could have implemented the functions in the match statements but I thought it might look ugly. I like the Lisp solution here because I define the line contents and the function in one place, but it isn't all cluttered with other line definitions.
There are a couple of things going on in defparse. First, it turns the function body into a lambda expression that is mapped in the global keyword hash table. Next, it looks for parameters whose names end in # and automatically converts them from string to integer. This is what the expansion of my (defparse "nod:" ...) looks like:
(SETF (GETHASH "nod:" *COMMAND-HANDLERS*)
(LAMBDA (NAME TAG #:G4171 #:G4172)
(LET ((|X#| (PARSE-INTEGER #:G4171)) (|Y#| (PARSE-INTEGER #:G4172)))
(PUSH (MAKE-INSTANCE 'NODE :NAME NAME :TAG TAG :X |X#| :Y |Y#|)
*BUILD-NODE-LIST*))))
Those #:G4171 and #:G4172 names are unique symbol names generated by the gensym function. A macro in Lisp is basically a function whose return value is code that will be compiled. This means that it blends in well with the language - there are a few syntactic differences having to do with quoting, but otherwise, you don't learn a separate macro language. One of the difficulties is that the macros run at compile time, so you can make use of all the functions you have defined (as far as I can tell, at least).
For the curious, here is my defparse macro:
(defmacro defparse (command param-list &body body)
(let* ((int-params (remove-if-not
#'(lambda (param)
(let ((ps (symbol-name param)))
(char= (elt ps (1- (length ps))) #\#))) param-list))
(param-map (mapcar #'(lambda (x) (cons x (gensym))) int-params))
(param-list-with-syms (mapcar
#'(lambda (param) (if (assoc param param-map) (cdr (assoc param param-map)) param))
param-list))
(let-list (mapcar #'(lambda (pg) (list (car pg) (list 'parse-integer (cdr pg)))) param-map)))
`(setf (gethash ,command *command-handlers*)
(lambda ,param-list-with-syms
(let ,let-list ,@body)))))
The thing I am a bit curious about is whether this is a Lispy way to approach the problem. Would a Lisp pro nod his or her head at this, or start to gag?
Sunday, July 10, 2005
My 2005 ICFPC Submission
My Ocaml code for the 2005 ICFP Programming Contest is now available at http://www.wutka.com/download/markwutka_icfpc.tgz
I'm sorry to say that there is only one barely informative comment. The only other comments are code that has been commented out.
One of the things I learned last night on IRC was that I can optimize some of my match statements. The parser (parser.ml) has lines like this in its match:
Apparently, I can make this a little shorter with:
Although I am happy with my choice of Ocaml for doing this project, I am not happy with my usage of Ocaml. I didn't use the "O" part of it at all - no objects. I did things as modules and it was a little cumbersome. I should have made a generic Bot class and then derived the cop and robber from that. I ended up copying too much code back and forth.
I'm sorry to say that there is only one barely informative comment. The only other comments are code that has been commented out.
One of the things I learned last night on IRC was that I can optimize some of my match statements. The parser (parser.ml) has lines like this in its match:
| "nod:" :: name :: tag :: x :: y :: [] -> handle_node name (node_tag_of_string tag)
(int_of_string x) (int_of_string y)
Apparently, I can make this a little shorter with:
| ["nod:";name;tag;x;y] -> handle_node name (node_tag_of_string tag)
(int_of_string x) (int_of_string y)
Although I am happy with my choice of Ocaml for doing this project, I am not happy with my usage of Ocaml. I didn't use the "O" part of it at all - no objects. I did things as modules and it was a little cumbersome. I should have made a generic Bot class and then derived the cop and robber from that. I ended up copying too much code back and forth.
36+7 hours of coding
I submitted my final entry for the 2005 ICFP Programming Contest and the deadline has passed, so now I feel free to share the mini diary I kept while working on the project.
June 24-27, 2005 - It Begins
Friday, 7:08 PM
I'm finally home and eating supper. The contest started 9 hours ago. I had to work today, so the best I have been able to manage is to look through the rules. I am excited to get going. Last night, I did a few tests with Chicken Scheme since I suspected I might have to do some socket code. The LiveCD the contest people put out mentioned something about game servers. Now that I see that I just read from stdin and write to stdout, I am back to Ocaml. The other thing that leads me back to Ocaml is that I will have 5 seconds to make a move each turn, I might need all the speed I can get.
Friday, 7:28 PM
I'm starting on the parser now. I will make a callback interface similar to the way SAX works to handle each message event. For nested messages like wsk, I will have callbacks for each sub-message. The callback interface will allow me to simulate the server in code later without actually having to do the full protocol.
Friday, 9:24 PM
It has been a little bumpy with Ocaml, but the problem is a disconnect between the chair and the keyboard. I am getting the parser written now. I have code to dump out the wsk structure, am trying to get it running now.
Friday, 9:54 PM
Got the basic parser running a little while ago. Now I am adding in support for all the commands the server can send. I have been on #icfpc on freenode for a while now (I am mr_pengy) and it is a blast chatting with these folks. It makes me wish we were all in one big lab.
Friday, 11:48 PM
All the parsing is coded, now I am trying to build the graphs for foot and car paths. After that I think I may go to bed.
Saturday, 12:14 AM
I decided to keep a list of foot edges and car edges in each node, so I essentially have two trees. I am going to bring in my old fibheap code and add dijkstra's algorithm so I can do shortest path computations. I want to see if I can compute the shortest path between all points in each tree. There are < 300 nodes in the graph, so that's just a few hundred thousand distances to compute. I'll have to see how long it takes. If the size of the world increases substantially, though, this will be a bad idea. Time for bed now.
Saturday, 10:02 AM
I probably slept a lot later than I should have. I finally got caught up with the ICFPC mailing list – lots of rule clarifications. Time to code.
Saturday, 11:57 AM
If I were to quit now, it wouldn't be a total loss. I was wrestling with trying to squeeze my fibheap code into this project without making it become really ugly. Then I started thinking about alternate ways to compute the distances. I worked out a way to do Dijkstra's shortest path algorithm without a priority queue. Basically, I start with distance D=0 and I iterate through each node N looking for node Nadj with distance=D. Then, I look at each node Nadj' that is an edge node of Nadj. If the distance from N to Nadj' is greater than D+1, I update the distance from N to Nadj' to be D. When I have done that for all nodes, I then repeat the procedure for all nodes with D=1 and so forth, until I do not find a node to update. On my machine, doing this calculation for all 229 nodes takes about 0.03 seconds. The max distance on foot is 29, the max distance by car is 17. This isn't bad considering the map is roughly a 15x15 grid. This is pretty exciting, even though I have yet to write a complete bot, so I am going to get started on a robber bot.
Saturday, 1:15 PM
Still reorganizing the code and making a bot interface. Still no bot, but this should make it easier to write one. There was a mention on #icfpc to look up the Floyd-Warshall shortest path algorithm, I think that's essentially what I came up with. I am pretty sure mine is O(n^3) like Floyd.
Saturday, 4:16 PM
I'm working on a robber bot. As a first try, I am having it look for banks that it can get to before the cops do, with a certain margin for error. If it can't find one, it picks another place to go. I'm writing lots of functions that should make it easier to add other behavior.
Saturday, 8:53 PM
I have a pretty dumb robber bot. He got caught after robbing one bank. It's not that my cop is smart, the robber ran right into him. The robber targeted banks that were farthest away from the cops, but didn't know how to avoid cops in its path. I have been thinking for a while about what to do about that, and my current thinking is that I need to make a new shortest path algorithm that avoids cops. Basically, before traversing an edge, see if the destination falls within some constraints (no cop within 2 spaces, for example). That would allow me to plot a short path around a cop.
Saturday, 10:13 PM
My robber just made all the way through without getting caught, and having robbed several banks. The cops are still very dumb, and the robber needs some work. His choice of banks is still determined by how far away the cops are, but not how close he is. Also, I need to make some adjustments to make sure it picks valid moves. I had a problem with that and I need to make absolutely sure it validates the move. Still, I feel good about my progress.
Saturday, 10:43 PM
I figured out where the invalid moves were coming from and made several adjustments there. I also changed the algorithm to go for the closest bank now that the distances take cop proximity into account. If it were to get surrounded right now, it wouldn't be able to pick a path because it wouldn't find nodes that are “safe”. In that case, I will make an emergency flee function. I may let it go for a “less safe” path first, then any path where there is no cop. Otherwise, stay put.
Saturday, 11:45 PM
I added the emergency flee function, so it should be able to get out of a jam. Tomorrow I have to make a better cop. I submitted an entry already just in case my machine crashes. Can't be too careful.
Sunday, 9 AM
Over breakfast, I modified the robber's calculations for cop distances to account for cops changing from foot to car. I'm leaving for Meeting for Worship shortly, won't be able to get going again until after noon.
Sunday, 4:04 PM
I have been working on the cop for a while. I tried assigning the cops a beat where they walked from bank to bank. My robber still got a ton of money. Now I am trying to compute the vicinity where the robber should be.
Sunday, 5:29 PM
I have been working on smartening up my cop. The contest rules state that in the initial tournament, your cop must win – not just come in the top 3. Because of the way the evidence collection works, that means if the other cops stumble on evidence and you aren't the one to capture the robber, you lose. This seems a little too random for me. My cop now directs the other cops to the general vicinity of the last known location of the robber, adjusting for time (“Our fugitive has been on the run for 90 minutes...”), but also within a certain minimum distance away. The idea is that my cop comes in to the actual area and snoops around. It doesn't quite work that way, but it isn't too bad. Whenever my cop smells the robber, it computes the possible locations of the robber (based on last-known location) and joins that with the locations that are exactly the smell distance away. Then it picks a random one if there are any. My cop can now occasionally beat my robber. I'm going to see what the ratio is.
Sunday, 5:42 PM
Oops! In computing how far a robber could have moved, I forgot that the robber only moves on every other turn, so the area was much too wide.
Sunday, 5:55 PM
In 20 games, the robber won 12 and my cop won 8. Also, my cop lost to the other cops in 1 out of those 8.
Sunday, 7:12 PM
I am really starting to feel tired. This has been a tough project and I am sure I won't win. I would like to be able to get through the regular season part of it, at least. I have modified the robber a little bit. Before, when it couldn't find a regular move, it would look for a “safe” move, which was a move that maximized the distance from the cops. Now, it looks at the set of those moves and tries to maximize the safe moves from that move as well. I could probably play with the logic there a little, but I will first see if that improves its performance against my current cop.
Sunday, 7:27 PM
The robber won 14 out of 20 this time. It might be just a tiny bit better than before. I started logging its searches and I have seen it get out of a jam when it has picked an emergency move, but usually when it has to do that, it gets caught.
Sunday, 10:03 PM
I submitted my updated cop & robber. My team name is “O Caml, My Caml”. I just recently put in code to look at the informs from the Mcgruff bots again and now I am starting to see how I might use Bayes theorem to predict user location. Someone mentioned Bayes on #icfpc yesterday, but I didn't know what he was getting at. I googled and found a paper on predicting customer location on a wireless network and now I am beginning to understand. Unfortunately, there are less than 12 hours left, and I know I won't be able to last all night. I don't know if I can create a smarter cop in the next few hours or not. I'll give it a try.
Sunday, 11:07 PM
I tried a few other things with probabilities, trying to incorporate Bayes theorem, but it seemed to be a little worse than my previous algorithm. Perhaps the Mcgruff bots aren't so good at estimating probabilities. It looks like I'll be sticking with what I have.
Sunday, 11:32 PM
I just sent in my final submission for the first part of the contest. Time for bed.
Monday, 2:24 AM
I was in bed with the light off when I realized that if a robber never hit a bank, my cop wouldn't find him. I switched the cop to start off in beat mode. Now I am doing some analysis on what bank a robber hits last before getting caught. So far, "60-and-blackstone" and "53-and-the-other-lake-park" lead by far. I tried eliminating 60&B already and cops won 17 out of 30 times. I am trying again with all banks allowed. Then I will try with 60&B and 53&OLP removed.
Monday, 3:44 AM
I tried a number of combinations, including picking random banks, the farthest bank, sticking with a bank until it was robbed. In the end, the best strategy was still to aim for the closest bank, but don't rob the bank at 60-and-blackstone. That should be enough right there to disqualify me from the Judge's Prize. NOW I'm going to bed.
July 9-10, 2005 - And now, The Twist
The interesting thing about this contest was that after the initial 72-hour period, there was almost a two-week lull, then they announced a change in the rules that we had 24 hours to respond to. I can't say that my response was great, but at least I submitted something.
Saturday, 10:10 AM
I am in Blacksburg, VA getting ready to come home after a week at the Friends General Conference Gathering. My dorm room at Va. Tech has an internet connection so I have just logged in to start reading the "twist" in the problem specification. UGH! Cops can be bribed! I don't know how I am going to do this. I spend the next 20 minutes looking over the requirements.
Saturday, 3:20 PM
Ceal is driving right now as I work on my program. I have just adapted my original cop and robber to the new protocol. The robber doesn't offer any bribes and the cop doesn't accept them. At least I have something.
Sunday, 12:45 AM
I have just submitted my final code. I am really tired after waking up at 6, packing the van and driving about 4 of the 7 hours of the return trip. My robber tried to bribe cops, but my cop does not take bribes. I decided to leave the cop alone. This will probably cost me the judges prize, even though I don't think I had a realistic shot at it to begin with. This has been a fun project and I hope to go back and try to add better strategy to my programs later.
June 24-27, 2005 - It Begins
Friday, 7:08 PM
I'm finally home and eating supper. The contest started 9 hours ago. I had to work today, so the best I have been able to manage is to look through the rules. I am excited to get going. Last night, I did a few tests with Chicken Scheme since I suspected I might have to do some socket code. The LiveCD the contest people put out mentioned something about game servers. Now that I see that I just read from stdin and write to stdout, I am back to Ocaml. The other thing that leads me back to Ocaml is that I will have 5 seconds to make a move each turn, I might need all the speed I can get.
Friday, 7:28 PM
I'm starting on the parser now. I will make a callback interface similar to the way SAX works to handle each message event. For nested messages like wsk, I will have callbacks for each sub-message. The callback interface will allow me to simulate the server in code later without actually having to do the full protocol.
Friday, 9:24 PM
It has been a little bumpy with Ocaml, but the problem is a disconnect between the chair and the keyboard. I am getting the parser written now. I have code to dump out the wsk structure, am trying to get it running now.
Friday, 9:54 PM
Got the basic parser running a little while ago. Now I am adding in support for all the commands the server can send. I have been on #icfpc on freenode for a while now (I am mr_pengy) and it is a blast chatting with these folks. It makes me wish we were all in one big lab.
Friday, 11:48 PM
All the parsing is coded, now I am trying to build the graphs for foot and car paths. After that I think I may go to bed.
Saturday, 12:14 AM
I decided to keep a list of foot edges and car edges in each node, so I essentially have two trees. I am going to bring in my old fibheap code and add dijkstra's algorithm so I can do shortest path computations. I want to see if I can compute the shortest path between all points in each tree. There are < 300 nodes in the graph, so that's just a few hundred thousand distances to compute. I'll have to see how long it takes. If the size of the world increases substantially, though, this will be a bad idea. Time for bed now.
Saturday, 10:02 AM
I probably slept a lot later than I should have. I finally got caught up with the ICFPC mailing list – lots of rule clarifications. Time to code.
Saturday, 11:57 AM
If I were to quit now, it wouldn't be a total loss. I was wrestling with trying to squeeze my fibheap code into this project without making it become really ugly. Then I started thinking about alternate ways to compute the distances. I worked out a way to do Dijkstra's shortest path algorithm without a priority queue. Basically, I start with distance D=0 and I iterate through each node N looking for node Nadj with distance=D. Then, I look at each node Nadj' that is an edge node of Nadj. If the distance from N to Nadj' is greater than D+1, I update the distance from N to Nadj' to be D. When I have done that for all nodes, I then repeat the procedure for all nodes with D=1 and so forth, until I do not find a node to update. On my machine, doing this calculation for all 229 nodes takes about 0.03 seconds. The max distance on foot is 29, the max distance by car is 17. This isn't bad considering the map is roughly a 15x15 grid. This is pretty exciting, even though I have yet to write a complete bot, so I am going to get started on a robber bot.
Saturday, 1:15 PM
Still reorganizing the code and making a bot interface. Still no bot, but this should make it easier to write one. There was a mention on #icfpc to look up the Floyd-Warshall shortest path algorithm, I think that's essentially what I came up with. I am pretty sure mine is O(n^3) like Floyd.
Saturday, 4:16 PM
I'm working on a robber bot. As a first try, I am having it look for banks that it can get to before the cops do, with a certain margin for error. If it can't find one, it picks another place to go. I'm writing lots of functions that should make it easier to add other behavior.
Saturday, 8:53 PM
I have a pretty dumb robber bot. He got caught after robbing one bank. It's not that my cop is smart, the robber ran right into him. The robber targeted banks that were farthest away from the cops, but didn't know how to avoid cops in its path. I have been thinking for a while about what to do about that, and my current thinking is that I need to make a new shortest path algorithm that avoids cops. Basically, before traversing an edge, see if the destination falls within some constraints (no cop within 2 spaces, for example). That would allow me to plot a short path around a cop.
Saturday, 10:13 PM
My robber just made all the way through without getting caught, and having robbed several banks. The cops are still very dumb, and the robber needs some work. His choice of banks is still determined by how far away the cops are, but not how close he is. Also, I need to make some adjustments to make sure it picks valid moves. I had a problem with that and I need to make absolutely sure it validates the move. Still, I feel good about my progress.
Saturday, 10:43 PM
I figured out where the invalid moves were coming from and made several adjustments there. I also changed the algorithm to go for the closest bank now that the distances take cop proximity into account. If it were to get surrounded right now, it wouldn't be able to pick a path because it wouldn't find nodes that are “safe”. In that case, I will make an emergency flee function. I may let it go for a “less safe” path first, then any path where there is no cop. Otherwise, stay put.
Saturday, 11:45 PM
I added the emergency flee function, so it should be able to get out of a jam. Tomorrow I have to make a better cop. I submitted an entry already just in case my machine crashes. Can't be too careful.
Sunday, 9 AM
Over breakfast, I modified the robber's calculations for cop distances to account for cops changing from foot to car. I'm leaving for Meeting for Worship shortly, won't be able to get going again until after noon.
Sunday, 4:04 PM
I have been working on the cop for a while. I tried assigning the cops a beat where they walked from bank to bank. My robber still got a ton of money. Now I am trying to compute the vicinity where the robber should be.
Sunday, 5:29 PM
I have been working on smartening up my cop. The contest rules state that in the initial tournament, your cop must win – not just come in the top 3. Because of the way the evidence collection works, that means if the other cops stumble on evidence and you aren't the one to capture the robber, you lose. This seems a little too random for me. My cop now directs the other cops to the general vicinity of the last known location of the robber, adjusting for time (“Our fugitive has been on the run for 90 minutes...”), but also within a certain minimum distance away. The idea is that my cop comes in to the actual area and snoops around. It doesn't quite work that way, but it isn't too bad. Whenever my cop smells the robber, it computes the possible locations of the robber (based on last-known location) and joins that with the locations that are exactly the smell distance away. Then it picks a random one if there are any. My cop can now occasionally beat my robber. I'm going to see what the ratio is.
Sunday, 5:42 PM
Oops! In computing how far a robber could have moved, I forgot that the robber only moves on every other turn, so the area was much too wide.
Sunday, 5:55 PM
In 20 games, the robber won 12 and my cop won 8. Also, my cop lost to the other cops in 1 out of those 8.
Sunday, 7:12 PM
I am really starting to feel tired. This has been a tough project and I am sure I won't win. I would like to be able to get through the regular season part of it, at least. I have modified the robber a little bit. Before, when it couldn't find a regular move, it would look for a “safe” move, which was a move that maximized the distance from the cops. Now, it looks at the set of those moves and tries to maximize the safe moves from that move as well. I could probably play with the logic there a little, but I will first see if that improves its performance against my current cop.
Sunday, 7:27 PM
The robber won 14 out of 20 this time. It might be just a tiny bit better than before. I started logging its searches and I have seen it get out of a jam when it has picked an emergency move, but usually when it has to do that, it gets caught.
Sunday, 10:03 PM
I submitted my updated cop & robber. My team name is “O Caml, My Caml”. I just recently put in code to look at the informs from the Mcgruff bots again and now I am starting to see how I might use Bayes theorem to predict user location. Someone mentioned Bayes on #icfpc yesterday, but I didn't know what he was getting at. I googled and found a paper on predicting customer location on a wireless network and now I am beginning to understand. Unfortunately, there are less than 12 hours left, and I know I won't be able to last all night. I don't know if I can create a smarter cop in the next few hours or not. I'll give it a try.
Sunday, 11:07 PM
I tried a few other things with probabilities, trying to incorporate Bayes theorem, but it seemed to be a little worse than my previous algorithm. Perhaps the Mcgruff bots aren't so good at estimating probabilities. It looks like I'll be sticking with what I have.
Sunday, 11:32 PM
I just sent in my final submission for the first part of the contest. Time for bed.
Monday, 2:24 AM
I was in bed with the light off when I realized that if a robber never hit a bank, my cop wouldn't find him. I switched the cop to start off in beat mode. Now I am doing some analysis on what bank a robber hits last before getting caught. So far, "60-and-blackstone" and "53-and-the-other-lake-park" lead by far. I tried eliminating 60&B already and cops won 17 out of 30 times. I am trying again with all banks allowed. Then I will try with 60&B and 53&OLP removed.
Monday, 3:44 AM
I tried a number of combinations, including picking random banks, the farthest bank, sticking with a bank until it was robbed. In the end, the best strategy was still to aim for the closest bank, but don't rob the bank at 60-and-blackstone. That should be enough right there to disqualify me from the Judge's Prize. NOW I'm going to bed.
July 9-10, 2005 - And now, The Twist
The interesting thing about this contest was that after the initial 72-hour period, there was almost a two-week lull, then they announced a change in the rules that we had 24 hours to respond to. I can't say that my response was great, but at least I submitted something.
Saturday, 10:10 AM
I am in Blacksburg, VA getting ready to come home after a week at the Friends General Conference Gathering. My dorm room at Va. Tech has an internet connection so I have just logged in to start reading the "twist" in the problem specification. UGH! Cops can be bribed! I don't know how I am going to do this. I spend the next 20 minutes looking over the requirements.
Saturday, 3:20 PM
Ceal is driving right now as I work on my program. I have just adapted my original cop and robber to the new protocol. The robber doesn't offer any bribes and the cop doesn't accept them. At least I have something.
Sunday, 12:45 AM
I have just submitted my final code. I am really tired after waking up at 6, packing the van and driving about 4 of the 7 hours of the return trip. My robber tried to bribe cops, but my cop does not take bribes. I decided to leave the cop alone. This will probably cost me the judges prize, even though I don't think I had a realistic shot at it to begin with. This has been a fun project and I hope to go back and try to add better strategy to my programs later.
