Programming Challenges Problems - Easiest to Hardest

After completing the The Stern-Brocot Number System problem the other day, I pondered which problem to solve next.

So I created a Excel spreadsheet to hold all 112 problems, and then sorted it by number of Users Solved to see the most solved puzzles.

Table below:

Number | Name | Users Submitted | Users Solved | % Users | Done
—|—|—|—|—|—|–
110101 | The 3n+1 problem | 9546 | 6059 | 63% | 1
110102 | Minesweeper | 5745 | 3781 | 66% | 1 |
110201 | Jolly Jumpers | 2882 | 2066 | 72% | 1
110103 | The Trip | 3341 | 1644 | 49% | 1
110104 | LC-Display | 2559 | 1592 | 62% | 1
110401 | Vito’s Family | 1584 | 1234 | 78% | 1
110203 | Hartals |1316 | 1189 | 90% |1
110502 | Reverse and Add | 1198 |968 | 81% | 1
110501 | Primary Arithmetic | 1187 | 908 | 76% | 1
110106 | Interpreter | 1253 | 872 | 70% | 1
110107 | Check The Check | 1077 | 739 | 69% | 1
110301 | WERTYU | 1389 | 730 | 53% | 1
110105 | Graphical Editor | 1523 | 704 | 46% | 1
110303 | Common Permutation | 1019 | 692 | 68% | 0
110901 | Bicoloring | 836 | 690 | 83% | 0
110701 | Light. More light | 923 | 667 | 72% | 1
110504 | Ones | 748 | 629 | 84% | 1
110302 | Where’s Waldorf? | 803 | 615 | 77% | 0
110108 | Australian Voting | 947 | 564 | | 60% | 1
110405 | Shoemaker’s Problem | 731 | 564 | 77% | 1
110202 | Poker Hands | 769 | 528 | 69% | 1
110404 | Longest Nap | 649 | 490 | 76% | 1
110402 | Stacks of Flapjacks | 716 | 489 | 68% | 0
110505 | A multiplication game | 595 | 488 | 82% | 0
110205 | Stack ‘em Up | 610 | 455 | 75% | 0
110608 | Steps | 510 | 437 | 86% | 0 |
110207 | Contest Scoreboard | 700 | 417 | 60% | 1
110704 | Factovisors | 690 | 412 | 60% | 0
111001 | Freckles | 554 | 401 | 72% | 0
110601 | How many Fibs? | 545 | 378 | 69% | 0
110603 | Counting | 488 | 378 | 77% | 0
111105 | Cutting Sticks | 463 | 354 | 76% | 0
110304 | Crypt Kicker II | 562 | 350 | 62% | 0
110903 | The Tourist Guide | 473 | 337 | 71% | 1
110801 | Little Bishops | 526 | 332 | 63% | -1
111301 | Dog and Gopher | 424 | 327 | 77% | 0
111201 | Ant on a Chessboard | 352 | 323 | 92% | 0
110607 | Selfdescribing Sequence | 370 | 310 | 84% | 0
110902 | Playing with Wheels | 408 | 301 | 74% | 0
110306 | File Fragmentation | 406 | 284 | 70% | 1
110507 | The Stern-Brocot Number System | 308 | 276 | 90% | 1
110703 | Euclid problem | 365 | 272 | 75% | 0
111103 | Weights and Measures | 328 | 260 | 79% | 0
110204 | Crypt Kicker | 557 | 255 | 46% | 0
110305 | Automated Jude Script | 388 | 247 | 64% | 0
110503 | The Archeologists’s Dilemma | 429 | 215 | 50% | 0
110206 | Erdos Numbers | 508 | 212 | 42% | 1
110506 | Polynomial coefficients | 240 | 210 | 88% | 0
110706 | Smith Numbers | 263 | 199 | 76% | 0
110908 | Hanoi Tower Troubles Again! | 221 | 199 | 90% | 0
111104 | Unidirectional TSP | 342 | 185 | 54% | 0
111204 | Bee Maja | 198 | 172 | 87% | 0
110403 | Bridge | 606 | 162 | 27% | 0
110805 | Tug of War | 318 | 142 | 45% | 1
110406 | CDVII | 204 | 140 | 69% | 1
110602 | How Many Pieces of Land? | 263 | 139 | 53% | 0
111102 | Distinct Subsequences | 286 | 138 | 48% | 0
111303 | The Knights Of the Round Table | 202 | 126 | 62% | 0
110606 | The Priest Mathenmatician | 219 | 121 | 55% | 0
111302 | Rope Crisis in Ropeland | 166 | 113 | 68% | 1
110604 | Expressions | 206 | 108 | 52% | 0
110407 | ShellSort | 333 | 107 | 32% | 0
110705 | Summation of Four Primes | 261 | 105 | 40% | 0
110707 | Marbles | 227 | 98 | 43% | 0
111207 | Dermuba Triangle | 117 | 96 | 82% | 0
111306 | The Largest/Smallest Box.. | 154 | 93 | 60% | 0
110408 | Football (aka Soccer) | 293 | 88 | 30% | 0
110803 | Queue | 127 | 85 | 67% | 0
110806 | Garden of Eden | 137 | 84 | 61% | 0
111006 | Tourist Guide | 165 | 83 | 50% | 0
111402 | The Cloest Pair Problem | 191 | 82 | 43% | 0
110508 | Pairsumonious Numbers | 122 | 80 | 66% | 0
110702 | Carhichael Numbers | 526 | 78 | 15% | 0
110905 | Edit Step Ladders | 173 | 74 | 43% | 0
110904 | Slash Maze | 97 | 74 | 76% | 0
110308 | Fmt | 155 | 72 | 46% | 1
111206 | (2/3/4)-D Sqr/Rects/Cubes/Boxes ? | 75 | 64 | 85% | 0
111202 | The Monocycle | 70 | 54 | 77% | 0
111003 | Fire Station | 156 | 53 | 34% | 0
111108 | Adventures in Moving - Part IV | 93 | 53 | 57% | 0
110208 | Yahtzee | 168 | 50 | 30% | 1
111308 | How Big Is It? | 79 | 48 | 61% | 1
111107 | Chopsticks | 76 | 48 | 63% | 0
110907 | From Dusk Till Dawn | 99 | 47 | 47% | 0
111401 | Herding Frosh | 83 | 44 | 53% | 0
111407 | Trees on My Island | 56 | 43 | 77% | 0
110708 | Repackaging | 62 | 37 | 60% | 0
111405 | Useless Tile Packers | 48 | 32 | 67% | 0
110804 | Servicing Stations | 121 | 30 | 25% | -1
111004 | Railroads | 59 | 27 | 46% | 0
111304 | Chocolate Chop Cookies | 41 | 27 | 66% | 0
111205 | Robbery | 37 | 25 | 68% | 0
111404 | Hotter Colder | 34 | 25 | 74% | 0
110605 | Complete Tree labeling | 51 | 23 | 45% | 0
110807 | Color Hash | 42 | 23 | 55% | 0
111208 | Airlines | 33 | 22 | 67% | 0
111307 | Is This Integration? | 150 | 21 | 14% | 0
110307 | Doublets | 301 | 20 | 7% | -1
111403 | Chainsaw Massacre | 42 | 20 | 48% | 0
111203 | Star | 43 | 16 | 37% | 0
111408 | Nice Milk | 25 | 15 | 60% | 0
111106 | Ferry Loading | 90 | 8 | 9% | 0
111005 | War | 111 | 3 | 3% | 0
111406 | Radar Tracking | 8 | 2 | 25% | 0
111305 | Birthday Cake | 89 | 1 | 1% | 0
111101 | Is Bigger Smarter? | 602 | 0 | 0% | 0
111002 | The Necklace | 252 | 0 | 0% | -1
110802 | 15-Puzzle Problem | 157 | 0 | 0% | 0
111007 | The Grand Dinner | 154 | 0 | 0% | 0
110906 | Tower of Cubes | 95 | 0 | 0% | 0
111008 | The Problem with the Problem Setter | 49 | 0 | 0% | 0
110808 | Bigger Square Please | 30 | 0 | 0% | 0

I then decided to tackle Vito’s Family and Primary Arithmetic (which in the original listing where not completed), and will write them up shortly. After that I’ll slowly work my why through the list, updating the above table as I go.

The -1 in the done column means submitted solutions, but not yet solved.

Comments:

Livar 2010-07-16 17:16:00

Can you help me figure out why my problem is not compiling in the website. Thanks a lot.

[Code deleted as it was mangled]


Simeon 2010-07-17 08:22:14

Hi Livar,

If your getting a “compiler error” message, go to the Statistics page for that problem, and then click on the submission you just entered. On that page it show the compiler error output.

That should allow you to decode the problem.

If that fails to help you, email me the code, and tell me the problem your trying to solve. simeon.pilgrim@gmail.com


Matteo Landi 2010-11-16 13:35:17

Hi Simeon,
could you please help me to figure out why my “Australian Voting” submission returns the “Time limit exceeded” message?
I can not understand if there is a bug in the algorithm/implementation, or maybe the algorithm is correct but it’s too slow (I tried a couple of solutions from other users but mine seems faster, at least with the test file I’m using).
Here are the steps of my solution:
1 count all the votes per candidate
2 find min/max number of votes per candidate
3a if min == max then all the remaining candidates have tied, and they are all winners. Then exit.
3b else if max/tot > 50 / 100 we have a single winner. Then exit.
3c find all the ballots starting with a losing candidate and shift the ballot until the head candidate is still in race for winning
4 come back to #1
This is the general idea (obviously we can avoid to count the votes at each iteration and also to shift the ballots).

[Edit: removed link to code]

Thanks in advance.

Regards,
Matteo


Simeon 2010-11-16 20:40:18

Hi Matteo,

Just had a quick look, and it seems like your doing the right things, compared to what my code was doing.

Your time-out will be from running too long.

I had to submit twice on this one, due to constructing a std::list inside the counting loop, but you don’t seem to use anything like that.

My only thought would be is at the very end when removing losing candidates you look for -1 people, yet wouldn’t people eliminated last time still be -1, thus are you double count/processing them?

If this is of no help, I’ll take a closer look tomorrow sometime…

Simeon


Matteo Landi 2010-11-17 02:36:18

Hi Simeon,
as you said, I look for candidates who scored -1. But if you look at it carefully, you will notice that I check, for each ballot, if the number of votes associated with the first *actual* preference (votes[ballots[i][indices[i]]]) is equal to -1; if I’m right, this should not be a waste of time, but feel free to correct me (please do it ;-) ).
Thanks for your attention.

Regards,
Matteo


Simeon 2010-11-17 09:40:02

I believe you, was just skimming the code and looking for anything that looked ‘odd’.


Simeon 2010-11-17 10:45:58

Ok, so here’s some help, using this data:

1
4
A
B
C
D
1 2 3 4
1 2 3 4
2 1 3 4
2 1 3 4
3 4 1 2

you should get the answer “A”, now copy’n’paste the 5 lines of voting 200 times (giving 1000 votes) and run your code. You will get the same answer A, as the voting distribution is the same.

My code finished sub second, your code is still running after 5 minutes on my development PC.

Thus your doing something too much, try smaller data sizes until you find the problem.

Simeon


Matteo Landi 2010-11-17 14:40:47

I think I’ve found the bug.
I itialize the `min’ variable to a wrong value(number of candidates minus one instead of number of ballots minus one): this makes the program enter in an infinite loop. That’s why I got that LTE message.
As soon as Programmin-Challenges comes back on-line, I’ll try the fixed solution.
Thank you so much for the help.

Regards,
Matteo