search

scvsoft / challenge-accepted

Juego que presentamos en la Rubyconf 2013
http://scvsoft.com/challenge-accepted
0 stars 0 forks source link

Add random cases for Challenge 3 #43

Closed tepen closed 10 years ago

tepen commented 10 years ago

Once we have a good solution for challenge 3, add some random cases as we did for the other challenges.

gianu commented 10 years ago

@tepen Maybe is a good time to change challenge 3. I mean, if we can't find a good solution maybe the problem is too complex for a challenge :tongue:

leoasis commented 10 years ago

How about the one you referenced in the solution, @tepen: http://rubyquiz.com/quiz154.html

It's widely known but so is fibonacci. Perhaps this one could be level 2 or level 3

tepen commented 10 years ago

I finally found a decent solution which I think covers all cases. The challenge is difficult because it is enough of a variation of the knapsack and the coin change problem. In the end, I followed one of the solutions for the coin problem and changed it so that it would find the biggest set instead of the smallest set (ie. give change using the minimum number of coins).

Both problems are taught in college so somebody that is studying or has just finished should know the right direction to take... but it is still a lot more challenging than the rest of the problems we have. It should be solvable by drawing a graph and finding the longest path, or with dynamic programming as in the sample solution. Maybe we can show it to some guys at SCV see if it's too hard, or we can change it as you mentioned.

leoasis commented 10 years ago

I'd just change it for something simpler. We don't want to kill the guys with math problems, just know if they can solve "fairly" complex problems quickly