11 Replies - 12155 Views - Last Post: 09 January 2012 - 08:32 AM

#1 janne_panne  Icon User is offline

  • WinRT Dev
  • member icon

Reputation: 429
  • View blog
  • Posts: 1,047
  • Joined: 09-June 09

Countdown Numbers round challenge

Post icon  Posted 05 January 2012 - 11:09 AM

*
POPULAR

Countdown Numbers round challenge

Introduction:
This challenge is a copy of a challenge introduced in a TV show called Countdown. The challenge is called Numbers round.

In Numbers round there is a player whose mission is to pick six cards from the table and then with those cards he has to achieve a number generated by a machine using basic operators: + - * /
There are two groups of cards on the table. In the first group there are four different cards with values 25, 50, 75 and 100. In the second group there are cards with values from 1 to 10. Usually players pick one big card and the rest five from small cards. The number they have to achieve (or get as close as possible) is from range 100-999.
One number can only be used once. Not all numbers have to be used.

The Challenge
Your challenge is to create a program which does the following:
- Picks the cards:
-- Randomly picks one card from big cards (25,50,75,100) and five cards from small cards (1-10). The small cards aren't unique, they can have the same value
- Generates a number from range 100-999
- Finds out what how to get to the generated number using the cards given and the operators +, -, *, /. Note that you aren't allowed to use integer rounding meaning that number 4/3 equals to 1.333 instead of 1. One card can be used only once. Not all cards have to be used.
- Prints out how it got to the generated number

Example #1
Big card: 25
Small cards: 5 8 1 10 6
Generated number: 452

25 - 10 = 15
15 * 5 = 75
75 - 1 = 74
74 * 6 = 444
444 + 8 = 452



Example #2
Big card: 25
Small cards: 2 6 1 9 1
Generated number: 333

25 + 1 = 26
26 + 1 = 27
27 * 2 = 54
54 * 6 = 324
324 + 9 = 333



Rewards

Joy of programming, what else would you dare to ask.

Final words

Good luck and have fun.

Remember to use Spoiler and Code tags when posting code.

Is This A Good Question/Topic? 8
  • +

Replies To: Countdown Numbers round challenge

#2 snoj  Icon User is offline

  • Married Life
  • member icon

Reputation: 84
  • View blog
  • Posts: 3,564
  • Joined: 31-March 03

Re: Countdown Numbers round challenge

Posted 05 January 2012 - 02:20 PM

My humble PowerShell contribution.

Spoiler


[edit] Had 99 instead of 999 and added a message if failed to generate a number.

This post has been edited by snoj: 05 January 2012 - 02:25 PM

Was This Post Helpful? 0
  • +
  • -

#3 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2241
  • View blog
  • Posts: 9,412
  • Joined: 29-May 08

Re: Countdown Numbers round challenge

Posted 05 January 2012 - 02:30 PM

Talk about a though one!
Do we also have to write us own evaluate function?

The search space is way bigger than you initial think it is.

- Number of ways to arrange the number (6! / (6-n)!)
multipled by
- Number of way to do the sum ( 4^ (n-1))
multipled by
- Number of ways that the parenthesis can work. 2 ^ (n-1)

But that not the end of it, as you have to take into account the different of number of used number solutions. So it actually it a summation of that function for the values 1 to 6
   6
 ∑(n) = F(n)= (4^(n-1)) * (6! / (6-n)!) * (2 ^ (n-1))
 n=1


That look a lot nice if DIC had Mathjax capabilities

Edit: I think those are the right formula, it been a while since I looked at the problem.

Then there is the 30sec time limit!

PS.

Quote

Prints out how it got to the generated number

Is a Reverse Polish Solution allowed?


Blog Post: The Bracketing Problem

My OLD attempt: Solving the Number Game
A slightly newer version

This post has been edited by AdamSpeight2008: 05 January 2012 - 02:49 PM

Was This Post Helpful? 0
  • +
  • -

#4 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2241
  • View blog
  • Posts: 9,412
  • Joined: 29-May 08

Re: Countdown Numbers round challenge

Posted 05 January 2012 - 02:54 PM

To clarify are the possible cards.
Big Uns: 100 75 50 25
Wee Uns: 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1
And that the contestant picks any 6 of those.
You have to find a solution utilizing those 6 card, and the basic math operators.
Was This Post Helpful? 0
  • +
  • -

#5 snoj  Icon User is offline

  • Married Life
  • member icon

Reputation: 84
  • View blog
  • Posts: 3,564
  • Joined: 31-March 03

Re: Countdown Numbers round challenge

Posted 05 January 2012 - 02:58 PM

View PostAdamSpeight2008, on 05 January 2012 - 03:54 PM, said:

To clarify are the possible cards.
Big Uns: 100 75 50 25
Wee Uns: 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1
And that the contestant picks any 6 of those.
You have to find a solution utilizing those 6 card, and the basic math operators.

So only two ten cards?

*goes back to rework code
Was This Post Helpful? 0
  • +
  • -

#6 prog_insanity  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 28-December 11

Re: Countdown Numbers round challenge

Posted 05 January 2012 - 04:10 PM

Does the program get to pick their values out of the 1-10 pool, or are those 5 cards randomly assigned?
Was This Post Helpful? 0
  • +
  • -

#7 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2241
  • View blog
  • Posts: 9,412
  • Joined: 29-May 08

Re: Countdown Numbers round challenge

Posted 05 January 2012 - 04:58 PM

Example Puzzle

Cards: 75 50 2 3 8 7
Target: 812

Ok, 30 secs on the clock.
Spoiler

This post has been edited by AdamSpeight2008: 05 January 2012 - 04:58 PM

Was This Post Helpful? 0
  • +
  • -

#8 RexGrammer  Icon User is offline

  • Coding Dynamo
  • member icon

Reputation: 181
  • View blog
  • Posts: 777
  • Joined: 27-October 11

Re: Countdown Numbers round challenge

Posted 05 January 2012 - 05:13 PM

WARNING: Very Long Code Inside
Spoiler


I won't explain the algorithm since it's very long, and I'm tired. It really bruteforces a solution (since I haven't got anything smarter). It's basically a deep recursion algorithm.

Found the inspiration out of Daniel Tebbutt's algorithm on this subject. Since I couldn't think of anything smart on my own, I started searching through the internet for help. Found his algorithm from which I drew inspiration and ideas.

This post has been edited by RexGrammer: 08 January 2012 - 02:53 PM

Was This Post Helpful? 0
  • +
  • -

#9 janne_panne  Icon User is offline

  • WinRT Dev
  • member icon

Reputation: 429
  • View blog
  • Posts: 1,047
  • Joined: 09-June 09

Re: Countdown Numbers round challenge

Posted 07 January 2012 - 06:47 AM

Nice to see some submissions here already. :)
I'll try your C# submissions on my computer when I have time. I'll also think about the next challenge. I'll try to make it non-mathematic because math challenges can be frustrating if you can't figure out a good algorithm and always just go for a brute force, like me :P

@prog_insanity:
They are randomly picked

@AdamSpeight2008:
Thanks for clarifying the possible cards.

Here is my version:
Spoiler

Was This Post Helpful? 0
  • +
  • -

#10 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2241
  • View blog
  • Posts: 9,412
  • Joined: 29-May 08

Re: Countdown Numbers round challenge

Posted 07 January 2012 - 01:35 PM

It could be also six small numbers, it is any 6 from the set of card.
eg 4 Big + 2 Small
3 Big + 3 Small
2 Big + 4 Small
1 Big + 5 Small
0 Big + 6 Small
Was This Post Helpful? 0
  • +
  • -

#11 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2241
  • View blog
  • Posts: 9,412
  • Joined: 29-May 08

Re: Countdown Numbers round challenge

Posted 08 January 2012 - 08:45 PM

You can find my Solver entry, in my following blog post covering it.

Countdown Number Puzzle Solver


Just to note it is using the stricter rule used in the game show.

- Only Integer results and intermediate result.
- No Negative or Zero intermediate.
Requires .net 4.0 Client Profile

This post has been edited by AdamSpeight2008: 08 January 2012 - 08:53 PM

Was This Post Helpful? 0
  • +
  • -

#12 Robin19  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 267
  • View blog
  • Posts: 547
  • Joined: 07-July 10

Re: Countdown Numbers round challenge

Posted 09 January 2012 - 08:32 AM

I did mine using the rules I interpreted first, without looking at anyone's posts. It uses recursion to find the answer. It can easily be modified to select any 6 cards. Right now it only selects one large and five small cards.

Equation Class - Holds the cards that are used, the operations, and calculates the mathematical results.
Spoiler


Player Class - holds the cards, knows the goal number, brute forces (using recursion) to find an equation that equals the goal
Spoiler


Game Class - Generates the random cards (one big from a set, 5 cards 1-10 with any repeats), creates a player, and tells the player to play
Spoiler


Program class just needs to create a new game, tell it to play, and display the game.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1