I plan on writing some articles on the Street Numbers problem, starting with the present one in which I present a rudimentary solver in Common Lisp.
I'm quite fond of using this problem in my teaching. For one thing, it has a particularly inefficient naive solution, so in the process of optimizing the algorithm, students get the thrill of seeing dramatic performance improvements. Solving it also entails getting to grips with the concept of nested iteration, often a hurdle for beginner programmers.
Street Numbers has turned up in at least one of the ACM's collegiate programming contests (ACM-ICPC), so the problem statement can be found in the contest archives. I would state it in this way:
Imagine a city where the streets are numbered 1 upwards. Funnily enough, the number of houses along any street is equal to the street's number. For instance, 27th st. has 27 houses numbered 1, 2 and so on up to 27. Try to visualize the streets with houses lined up in a row, instead of facing each other. Now here's the problem — which streets have a house such that all houses on its left add up the same as those on its right?
Eighth st. is one solution because, standing at house number 6, all house numbers on one side sum to 15 (1+2+3+4+5) as do those on the other side (7+8).
To start off, let's brute-force our way through all houses in every street in search of these sweet spots. First, some helper functions:
;; Does HOUSE on STREET pass the Street Numbers test?
(DEFUN PASS-TEST-P (STREET HOUSE)
(= (SUM-BETWEEN 1 (1- HOUSE))
(SUM-BETWEEN (1+ HOUSE) STREET)))
;; Sum of integers from LOW to HIGH, inclusive.
(DEFUN SUM-BETWEEN (LOW HIGH)
(LOOP FOR I FROM LOW TO HIGH SUMMING I))
And here's the first cut at a solver:
;; Interactively display solutions to Street Numbers.
(DEFUN SOLVE-STREET-NUMBERS ()
(LOOP FOR STREET FROM 1
DO (LOOP FOR HOUSE FROM 1 TO STREET
WHEN (PASS-TEST-P STREET HOUSE)
DO (FORMAT T "~&Street ~A, House ~A"
STREET HOUSE)
AND UNLESS (YES-OR-NO-P "~&More?")
DO (RETURN-FROM SOLVE-STREET-NUMBERS))))
In the space of a minute, it gives me just 5 solutions: (1, 1) (8, 6) (49, 35) (288, 204) and (1681, 1189). That's awfully slow.
