Re: writing an "artful" algorithm

[jatwood@cvpjaws03.dhcp.cv.hp.com (John Atwood)]

John Stoneham  <captnjameskirk@moc.oohay> wrote:
>For those who like puzzles and have a little bit of free time, you may 
> <snip>
>
>This does seem like the imperative way to work out the problem, and I 
>think just about any other imperative approach would look about the 
>same, even if it used vectors or records in its representation. It would 
>still need to test individual digits and generate and test every 
>possible combination. But what about the functional approach? Would it 
>be more "artful" here? Would it even be possible to use a functional 
>approach for such a problem?


Here's a functional solution to a similar problem:
	http://www.cs.nott.ac.uk/~gmh/bib.html#countdown
	Graham Hutton. Journal of Functional Programming, 
	12(6):609-616, Cambridge University Press, November 2002.

	We systematically develop a functional program that 
	solves the countdown problem, a numbers game in 
	which the aim is to construct arithmetic expressions 
	satisfying certain constraints. Starting from a formal 
	specification of the problem, we present a simple but 
	inefficient program that solves the problem, and prove 
	that this program is correct. We then use program fusion 
	to calculate an equivalent but more efficient program, 
	which is then further improved by exploiting arithmetic 
	properties.




John