This assignment is due Thursday, 10 February at 5pm.
For this assignment, you will build a program that does A* search for a route finding problem. You will also add optimizations to a really dumb program that solves cryptarithmetic problems.
Implement a program that finds routes between towns in the map of CA desert towns using A* search.
The file map-data.scm contains distances for road segments between towns, as well as the (x,y) location of each town. All numbers are in units of miles. The (x,y) positions are relative to an arbitrary coordinate system centered on LA. (Isn't that the center of the universe?)
The (x,y) positions were rounded to the nearest 10 miles, i.e. plus or minus 5 miles from the correct position. Computing straight-line distance between two cities using the obvious formula will give you an ok estimate of the distance. However, it is not guaranteed to be an underestimate of the road distance, as required by a completely correct implementation of A*. You must figure out how to modify the straight-line distance formula to get an underestimate.
You may find it easiest to first implement a breadth-first search (i.e. completely ignoring the distance and position information), and then modify this code into your A* algorithm.
Solving cryptarithmetic problems is a standard example of a constraint satisfaction problem. The file dumb-crypt.scm contains a relatively stupid cryptarithmetic solver. It is just smart enough to search the entire space of possibilities, ensure that no two letters are given the same value, and that leading digits of cryptarithmetic problems are not zero. (I checked with Art Benjamin and that last constraint is standard.)
The code file also defines nine cryptarithmetic problems for testing. (If you have any other favorites, please send them to cs-151-l.) The stupid solver program can solve the first three problems relatively fast. The fourth problem requires examining 638495 states: this will complete on turing if you wait a bit and don't mind being the top CPU consumer. The later problems probably won't finish in an acceptable amount of time. (Don't be too nasty to turing.)
Your job is to modify this program so that it examines fewer states, using techniques such as those discussed in the January 31st lecture. The stupid algorithm prints the number of states examined: you should try to minimize that number. Add as many optimizations as you can. Don't feel constrained by the optimizations discussed in class: if you can think of other ways to reduce the amount of search, feel free to add them. Just make sure that your optimizations are correct, i.e. they do not prevent the algorithm from examining states that might end up being the solution.
When you add each optimization, set up a global variable which allows you to easily toggle the optimization on and off. (You can use as a model the variable *debugging-on* in the stupid algorithm.) Test your algorithm with different combinations of optimizations and give me a report on how each optimization affects the performance of the algorithm. (Think of this as a lab science experiment.)
As with the previous assignment, start by implementing small utility functions that can be separately tested. For example, in the A* problem, first implement the functions required to estimate distances between cities and lengths of paths.
Check out the functions insert and sort-list, in the scheme-extensions handout. Using them is substantially easier than writing your own sorting functions!
The last input to insert and sort-list is a "comparison function." This must be a function that takes two input values, returns a boolean, and determines an order on the set of input values. You can use the name of a pre-existing function (e.g. <) or you can use the operator lambda to write an ad-hoc, nameless function. For example, the second example below sorts its input list based on the second element of each pair.
(sort-list '(1 -20 23 20 43 -2 102) <)
(sort-list '((a 1) (m 7) (r -2) (x -15) (p 0))
(lambda (x y) (>= (cadr x) (cadr y))))
If you believe your program's in an infinite loop, both ctrl-d and ctrl-c may be useful in attempting to break the loop and get a prompt back.
The stupid cryptanalysis program contains several example of the map operation. I found that map and recursion were very useful in writing this code, more so than do loops.
Notice that global variables traditionally have names that start and end with asterisks.
You should turn in a hardcopy of your code and a separate written description of what your code does and how it works, as for assignment #1. You should also submit a copy of your code using cs151submit.
In addition to obvious things (e.g. examples of input and output), your written description should address:
This page is maintained by Margaret Fleck.