Re: Request for Algorithm

["Do / Ngoc Minh (ISE)" <n.do@student.canberra.edu.au>]

On Fri, 16 May 1997, Ninh Tran wrote:

> 
> Dear vnsa friends,
> 
> Can someone provide an algorithm that:
> 
> 1. Given as input, four numbers, all greater than zero,
> 2. Using four arithmetic operators +, -, *, /.
> 
> Answer yes or no if there is a way to come up with 24 using the four   
> input
> numbers and the four arithmetic operators. Each number must be used   
> exatcly
> one, and the result of one computation can be used in the next.
> 
> If the answer if Yes, print the calculation.
> 
> Examples,
> 
> 1. Input:  1,2,3,4.
>     Answer: Yes:  (1+2+3)*4
> 
> 2. Input: 2,2,2,2.
>     Answer: No.
> 
> 
> Regards,
> 
> Ninh  
> 

A simple approach is to search through the entire search space to find 
out the possible solution(s).  This can be done by induction as follows:

>From the list of n (n >= 2) numbers, we replace 2 arbitrary numbers, say a 
and b, by a new number c = f(a,b) where f is one of operators {+,-,*,/}.  
This process continues until we are left with one number which then can 
be compared with 24 in our case.

To have an idea of the search space, if let S(n) is the number of 
combinations for the list of n numbers, then from above we have:
	S(n) = 4*C(n,2)*S(n-1)		(C(n,2) = n(n-1)/2)

or	S(n) = 4^(n-1)*C(n,2)*...*C(2,2)

As in our case, S(4) = 1152 combinations.

A program can be written in Prolog (a logic language that has the 
ability to backtrack) with less than 20 lines of code.

Cheers,
Minh.