🔒 Locked

Programming Challenge : Countdown

Started by dave Jul 9, 2004 at 6:23 AM 5 replies 1k views

Original Post

dave

320

dave

Jul 9, 2004 at 6:23 AM

I thought i might set a programming challenge to anyone who is interested. I was thinking the other day how interesting it would be if you could right a program that would solve the Countdown Numbers Game. It is a bit more complicated than u expect. If you're not aware of the game it goes like this: 1. 6 Numbers are chosen, usually small or big like 10 25 50 75 100 and single figure numbers. 2. A target is generated, say 347. 3. Using the following: + - / * and brackets () reach the target or get as close as possible. It would be interesting to see how people do it. Notes: ====== 1. Brackets can be used anywhere within the equation. 2. The numbers can only be used once. 3. If a two was available, u cant then square a number, or cubed etc. If you want to make an entry just post ur source code into a reply. Depending on whether people bother i will decide the winner based on method, efficiency and result. Good Luck!! regards ace

eleusive

Jul 9, 2004 at 11:27 AM

The best way to do this would probrably be dynamic programming. I would hold a 6 element array containing the closest solution to the target from 0 to 5. The code would look something like this

int solution[6][6];int numbers[6];get_input(numbers);initialize(solution);for(int len=1;len<6;len++){   for(int i=0;i<6;i++)   {       int min=INT_MAX;       int j=i+len;          //Distance apart       for(int k=i;k<j;k++)  //look for place to insert operator       {           initialize temporary variables to permute through combinations of +,-,*,/, added to solution[k]+solution[k+1][j];           calculate minimum difference between all temporary variables and the target and store it in min;           solution[j]=min;       }   }}return abs(target-solution[0][5]);

Note that the optimal substructre of the program takes care of the brackets () automatically.

[Edited by - eleusive on July 9, 2004 1:27:26 PM]

antareus

Jul 9, 2004 at 12:05 PM

Hint: The optimal solution to this program isn't written in C++.

Mulligan

111

Mulligan

Jul 9, 2004 at 1:10 PM

This is like "challenge 24" a game i would play at school. There would be a card with four numbers on it, and we had to use all the numbers in an equation to get to 24. Loved that game.

eleusive

Jul 9, 2004 at 1:56 PM

Well, even if the optimal solution to the problem cannot be coded in c++, there is still an optimal c++ solution(from the possible solutions in c++) =)

dave

Author

320

dave

Jul 9, 2004 at 2:14 PM

The wayb that i would do it would be to use Genetic Algorythms and converge upon a solution, i did a similar program.

msn12b

Jul 9, 2004 at 2:24 PM

Are you enforcing order of operations?

(EDIT): Never mind. You can do an exhaustive search of the 47185920 possibilities.

MSN

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.