## 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.

## Programming Challenges:110507 The Stern-Brocot Number System

Last night I was bored, and decided to tackle a Programming Challenges problem: 110507 The Stern-Brocot Number System seemed easy, and in the end it was.

However it took two attempts, due to messing up the termination logic. ie run till m and n are both 1

```    while (m != 1 && n != 1)
```

```    while (m != 1 || n != 1)
```

maybe I should have used

```    while (!(m == 1 && n == 1))
```

Gosh I dislike double negatives to loop logic.

## The Trip – 110103 in Erlang

The third of my Programming Challenges solutions is for The Trip 110103

This problem is great for making you think.  Key points are; you cannot have half cents, and you have to find the minimum money needed to balance costs to within one cent.

Here is my solution in Erlang:

```-module(thetrip).
-export([thetrip/1, test/0]).

average([H|T], Sum, Len) ->
average(T, Sum+H, Len+1);
average([], Sum, Len) ->
[Sum div Len , (Sum rem Len) > 0].

diff([H|T], Sum, Avg, Odd) when H > Avg, Odd ->
diff(T, Sum + H - Avg - 1, Avg, Odd);
diff([H|T], Sum, Avg, Odd) when H > Avg ->
diff(T, Sum + H - Avg, Avg, Odd);
diff([_|T], Sum, Avg, Odd) ->
diff(T, Sum, Avg, Odd);
diff([], Sum, _, _ ) ->
Sum.

thetrip(List) ->
Scaledup = [ trunc( X * 100 ) || X <- List],
[Avg, Odd] = average(Scaledup, 0, 0),
Diff = diff(Scaledup, 0, Avg, Odd ) / 100,
io:format("\$~.2f~n",[Diff]),
Diff.

test() ->
10.00 = thetrip([10.00, 20.00, 30.00]),
11.99 = thetrip([15.00, 15.01, 3.00, 3.01]),
14.39 = thetrip([15.00, 15.01, 3.00, 3.01, 3.01]),
19.57 = thetrip([15.00, 15.01, 3.00, 3.01, 3.02, 3.03, 3.04, 3.05, 3.06, 3.07, 3.08]),
true.

```

I really enjoyed getting my head around guard sequences and using local variables to space the code out.

## 3n + 1 in Erlang

This is my second Programming Challenges solution written in Erlang. First here.

This time I chose the first problem 3n + 1 #110101.

It is a little bit of a cheat doing it in Erlang, as the major point of the original problem is knowing the limits of your data types, and thus C’s int type is not large enough to manage the problem. I am not even sure is a int64 is large enough or if you need to drop down to your own large number type. Ether way,  Erlang does not suffer from this problem with it’s dynamic size number type.

So here is my solution:

```-module(threenplusone).
-export([three_n_plus_one_range/2,test/0]).

three_n_plus_one_range(Min, Max) ->
lists:max([threenplusone(X) || X <- lists:seq(Min, Max) ]).

threenplusone(Num) ->
threenplusone(Num, 1).

threenplusone(1, Count) -> Count;
threenplusone(Num, Count) ->
case (Num rem 2) of
1 -> threenplusone( (Num * 3) + 1, Count + 1);
0 -> threenplusone( Num div 2, Count + 1)
end.

test() ->
20 = three_n_plus_one_range(1,10),
125 = three_n_plus_one_range(100, 200),
89 = three_n_plus_one_range(201, 210),
174 = three_n_plus_one_range(900,1000),
true.```

The problem states that numbers up to 1,000,000 are known to converge to 1, so I ran the problem from 1 -> 1,000,000 and the largest number of steps is 525. This took around 10 seconds on my MacBook which I feel is performant enough.

I quite like using the lists:seq generator and the list comprehension together, but I wonder if there is a better way to-do number generation and function calling in a single line.

## Reverse And Add 110502 in Erlang

Carrying on from Cedric’s Challenge (C#, Erlang) I decided to do some of the Programming Challenges problems in Erlang, because the problems are small, but fun.

My first is Reverse And Add #110502 and here is my solution:

```-module(revandadd).
ntl(Num) ->
ntl(Num, []).
ntl(0, List) ->
List;

ntl(Num, List) ->
ntl(Num div 10, [Num rem 10]++List).

%% list to number
ltn(List) ->
ltn(List, 0).

ltn([], Num) ->
Num;
ltn([H|T], Num) ->
ltn(T, (Num*10)+H).

%% is palindrome
is_pal(Num) ->
ntl(Num) == lists:reverse(ntl(Num)).

Pal = ltn(lists:reverse(ntl(Num))) + Num,
case is_pal(Pal) of
true ->
[Count,Pal];
false ->