Thursday, February 07, 2008

Scheme For Enlightenment Part Thirteen - Eliminate Redundant Specification

Since the C version did not redundantly list paired states, this is an experiment to do this in scheme. Refer to part eleven for the support code.

#!/usr/bin/guile -s
!#
;;; Color the New England states in 4 colors.
(load "amb.scm")

(define (choose-color)
(amb 'red 'green 'blue 'white))

(define (color-new-england) ; Choose colors for each state.
(let ((me (choose-color)) ; MainE
(ma (choose-color)) ; MAssachuesetts
(ct (choose-color)) ; ConnecticuT
(ri (choose-color)) ; Rhode Island
(nh (choose-color)) ; New Hampshire
(vt (choose-color))) ; VermonT

;; Construct the adjacency list for each state:
;; the states' name, its color, the list of its neighbors' colors.
(let ((Connecticut (list 'Connecticut ct (list ri)))
(Maine (list 'Maine me (list nh)))
(Massachuesetts (list 'Massachuesetts ma (list ct)))
(NewHampshire (list 'NewHampshire nh (list ma vt)))
(RhodeIsland (list 'RhodeIsland ri (list ma)))
(Vermont (list 'Vermont vt (list ma))))

(let ((states (list Connecticut Maine Massachuesetts
NewHampshire RhodeIsland Vermont)))

;; A state's color can't be the same as any of its neighbors.
(for-each (lambda (c)
(assert (not (memq (cadr c)
(caddr c)))))
states)

;; Output the color assignment.
(for-each (lambda (c)
(display (car c))
(display " ")
(display (cadr c))
(newline))
states)))))

(color-new-england) ; run the function to find an answer.


This generates the same answer, but only marginally quicker, if at all. The startup time for Guile dominates, the any time saved is difficult to measure. So i made this same modification to a version with 15 east coast states. This also produced the same answer. And it produced a slow down of a factor of 1.02. The modification was trivial. It isn't a change to the algorithm, just the data. Removing the over specification of the problem led to getting an answer a little slower. Chances are, the order in which the decision tree was searched was altered. That lead to the same answer, but only after a few more failures were considered.

It's too bad. I was hoping for a small speed up. My idea was that less work would have to be done for each decision. Oh well.

1 comment:

Stephen said...

My machine had been crunching on coloring 18 states. It ran for 145 CPU days. It didn't finish. I had to reboot. But i was able to check it's run time beforehand. Since 17 states only took an hour or so, i rechecked the code. There was a bug. It wasn't ever going to find a solution. I fixed it, and it ran in 6.2 hours. That's more like it. Though it could easily have taken much longer.

Question to ponder. Let's say Joe has a 1 GHz CPU. Suzan has a 2 GHz CPU. Which one will finish an infinite loop faster?