-
Notifications
You must be signed in to change notification settings - Fork 0
/
happy-numbers-kata.html
594 lines (511 loc) · 69.1 KB
/
happy-numbers-kata.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<link rel="manifest" href="/manifest.json" />
<link rel="icon" href="/images/icons/icon-152x152.png" />
<!-- theme-color defines the top bar color-->
<meta name="theme-color" content="#575757" />
<meta
http-equiv="X-Content-Security-Policy"
content="default-src 'self'; script-src 'report-sample' 'self' https://app.posthog.com/static/array.js https://www.googletagmanager.com/gtag/js; style-src 'report-sample' 'self' https://fonts.googleapis.com; object-src 'none'; base-uri 'self'; connect-src 'self' https://app.posthog.com; font-src 'self'; frame-src 'self'; img-src 'self'; manifest-src 'self'; media-src 'self'; report-uri https://pauldambra.report-uri.com/r/d/csp/enforce; worker-src 'self';"
/>
<!-- Add to home screen for Safari on iOS-->
<meta name="apple-mobile-web-app-capable" content="yes" />
<meta name="apple-mobile-web-app-status-bar-style" content="default" />
<meta name="apple-mobile-web-app-title" content="MiRaNo" />
<link rel="apple-touch-icon" href="/images/icons/icon-152x152.png" />
<!-- Add to home screen for Windows-->
<meta
name="msapplication-TileImage"
content="/images/icons/icon-152x152.png"
/>
<meta name="msapplication-TileColor" content="#575757" />
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
<title>Happy Numbers</title>
<link rel="canonical" href="https://pauldambra.dev/happy-numbers-kata.html" />
<meta property="og:url" content="https://pauldambra.dev/happy-numbers-kata.html" />
<meta property="og:type" content="article" />
<meta property="og:title" content="Happy Numbers" />
<meta
property="og:description"
content="The Happy Numbers Kata in Five Seconds"
/>
<meta
property="og:image"
content="https://pauldambra.dev/images/cardboard.jpg"
/>
<meta name="twitter:creator" content="@pauldambra" />
<meta property="fb:app_id" content="1029758320473951" />
<meta name="viewport" content="width=device-width" />
<meta
name="description"
content="The Happy Numbers Kata in Five Seconds"
/>
<meta property="fb:pages" content="1029758320473951" />
<link
rel="alternate"
type="application/rss+xml"
title="Mindless Rambling Nonsense"
href="https://pauldambra.dev/feed.xml"
/>
<link rel="shortcut icon" href="/favicon.ico" />
<link rel="prefetch" href="/images/cardboard.jpg" />
<link rel="stylesheet" href="/assets/css/main.css">
<link rel="stylesheet" href="/assets/css/syntax.css">
<meta name="msvalidate.01" content="54691C3C7B863CEE60F0305D6EDFF7A8" />
<meta
name="google-site-verification"
content="hLKEdujpXNQ9PSZWEcQkwxCgL2z1tWxVedeaUmttH7c"
/>
<script>
!function(t,e){var o,n,p,r;e.__SV||(window.posthog=e,e._i=[],e.init=function(i,s,a){function g(t,e){var o=e.split(".");2==o.length&&(t=t[o[0]],e=o[1]),t[e]=function(){t.push([e].concat(Array.prototype.slice.call(arguments,0)))}}(p=t.createElement("script")).type="text/javascript",p.async=!0,p.src=s.api_host.replace(".i.posthog.com","-assets.i.posthog.com")+"/static/array.js",(r=t.getElementsByTagName("script")[0]).parentNode.insertBefore(p,r);var u=e;for(void 0!==a?u=e[a]=[]:a="posthog",u.people=u.people||[],u.toString=function(t){var e="posthog";return"posthog"!==a&&(e+="."+a),t||(e+=" (stub)"),e},u.people.toString=function(){return u.toString(1)+".people (stub)"},o="capture identify alias people.set people.set_once set_config register register_once unregister opt_out_capturing has_opted_out_capturing opt_in_capturing reset isFeatureEnabled onFeatureFlags getFeatureFlag getFeatureFlagPayload reloadFeatureFlags group updateEarlyAccessFeatureEnrollment getEarlyAccessFeatures getActiveMatchingSurveys getSurveys getNextSurveyStep onSessionId setPersonProperties".split(" "),n=0;n<o.length;n++)g(u,o[n]);e._i.push([i,s,a])},e.__SV=1)}(document,window.posthog||[]);
posthog.init('phc_xcwOfYtGDcfv8619HtTWgHEfVMeTqS5YKkBsVEpy1ns',{api_host:'https://ph.pauldambra.dev', person_profiles: 'identified_only' // or 'always' to create profiles for anonymous users as well
})
</script>
</head>
<body class="flex flex-col h-screen">
<header class="flex flex-col px-8 pt-4 text-white text-xl" role="banner">
<div class="flex flex-col sm:flex-row">
<div class="no-underline hover:underline">
<a href="/">Mindless Rambling Nonsense</a>
</div>
<div class="flex-grow my-2 sm:m-0"></div>
<div class="flex justify-start items-end flex-col text-sm">
<div class="flex items-center">
<div class="mr-4">Paul D'Ambra</div>
<a href="https://github.com/pauldambra" rel="noopener">
<img
src="/images/GitHub-Mark-Light-32px.png"
alt="pauldambra on github"
width="32"
height="32"
/>
</a>
</div>
<div class="flex items-center">
<div class="mr-4">Fangler</div>
<a href="https://twitter.com/pauldambra" rel="noopener">
<img
src="/images/twitter-32.png"
alt="pauldambra on twitter"
width="32"
height="32"
/>
</a>
</div>
<div class="flex items-center">
<div class="mr-4"></div>
<a rel="me" href="https://mastodon.me.uk/@pauldambra">
</a>
</div>
</div>
</div>
<div class="flex-grow"></div>
<div
class="flex align-middle items-start px-2 py-4 text-white space-x-4 text-lg"
>
<nav role="navigation">
<a class="underline" href="/">Blog Posts</a>
<a class="underline ml-5" href="/weeknotes.html">Week Notes</a>
<a class="underline ml-5" href="/kids-games.html">Kids games</a>
</nav>
</div>
</header>
<main role="main" class="bg-white p-4 w-11/12 m-auto flex-auto flex-grow">
<script type="application/ld+json">
{
"@context":"http://schema.org",
"@type":"BlogPosting",
"headline":"Happy Numbers",
"genre":"",
"keywords":"",
"wordCount":"2950",
"url":"https://pauldambra.dev/happy-numbers-kata.html",
"datePublished":"2014-11-22",
"author":{
"@type":"Person",
"name":"Paul D'Ambra",
"sameAs":[
"https://twitter.com/pauldambra",
"https://github.com/pauldambra",
"https://plus.google.com/u/0/+PaulDAmbraPlus"
]
},
"publisher":{
"@type": "Organization",
"name": "Paul D'Ambra",
"sameAs": [
"https://twitter.com/pauldambra",
"https://github.com/pauldambra",
"https://plus.google.com/u/0/+PaulDAmbraPlus"
],
"logo": {
"@type": "ImageObject",
"contentUrl": "https://pauldambra.dev/images/logo.png",
"url": "https://pauldambra.dev"
}
},
"image":{
"@type":"ImageObject",
"contentUrl":"https://pauldambra.dev/images/cardboard.jpg",
"url":"https://pauldambra.dev",
"height":"450",
"width":"1000"
},
"mainEntityOfPage":{
"@type":"WebPage",
"@id":"https://pauldambra.dev/happy-numbers-kata.html"
},
"articleBody":"I love C# but while we're trying to beat our deployment process into submission at work I'm only really writing Ruby and Powershell. So when a few, different articles about the Happy Numbers kata turned up on my twitter feed and I found myself with a large whisky and a sleeping family I thought I'd have a go.\n\nThe Happy Numbers kata is defined as\n\n\n Choose a two-digit number (eg. 23), square each digit and add them together. \nKeep repeating this until you reach 1\nor the cycle carries on in a continuous loop.\n\n If you reach 1 then the number you started with is a “happy number”.\n\n Can you find all the happy numbers between 1 and 100?\n\n\n\n\nThere is more info on what a Happy Number is on wikipedia.\n\nThe second link above has some spoilers in. Particularly that the order of the numbers doesn't matter, and that zeroes don't matter. I did previously rediscover that the order that you add numbers doesn't matter when working on some insurance software a few years back (although it took me a while :annoyedwithselfemoticon:) so let's be kind to me and assume I'd have got there on my own if I hadn't read the article first (although it was a large whisky).\n\nAfter writing a couple of tests:\n\n[Test]\n[TestCase(31, true)]\n[TestCase(4, false)]\n[TestCase(2, false)]\npublic void CanIdentifyHappyNumber(int i, bool expected)\n{\n Assert.AreEqual(expected, i.IsAHappyNumber());\n}\n\n\nI realised that I really like Ruby's having a question mark on methods that return a boolean and miss that feature in C#.\n\nAnd that the sensible public API was a call to IsAHappyNumber directly on the integer so I could crank out a large test.\n\n// Taken from http://oeis.org/A007770\nprivate static readonly int[] HappyNumbersUpTo1000 =\n{\n 1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 91, 94, 97, 100, 103, 109, 129, 130, 133, 139,\n 167, 176, 188, 190, 192, 193, 203, 208, 219, 226, 230, 236, 239, 262, 263, 280, 291, 293, 301, 302, 310, 313,\n 319, 320, 326, 329, 331, 338, 356, 362, 365, 367, 368, 376, 379, 383, 386, 391, 392, 397, 404, 409, 440, 446,\n 464, 469, 478, 487, 490, 496, 536, 556, 563, 565, 566, 608, 617, 622, 623, 632, 635, 637, 638, 644, 649, 653,\n 655, 656, 665, 671, 673, 680, 683, 694, 700, 709, 716, 736, 739, 748, 761, 763, 784, 790, 793, 802, 806, 818,\n 820, 833, 836, 847, 860, 863, 874, 881, 888, 899, 901, 904, 907, 910, 912, 913, 921, 923, 931, 932, 937, 940,\n 946, 964, 970, 973, 989, 998, 1000\n};\n\n[Test]\npublic void CanTestAThousandNumbers()\n{\n for (var i = 0; i < 1000; i++)\n {\n Assert.AreEqual(HappyNumbersUpTo1000.Contains(i), i.IsAHappyNumber());\n }\n}\n\n\nSo, with a 1000 failing tests I could run through a few naive implementations to get to a reasonable one.\n\nusing System;\nusing System.Collections.Generic;\nusing System.Globalization;\nusing System.Linq;\n\nnamespace HappyNumbers\n{\n // Choose a two-digit number (eg. 23), square each digit and add them together. \n // Keep repeating this until you reach 1 or the cycle carries on in a continuous loop. \n // If you reach 1 then the number you started with is a “happy number”.\n public static class HappyNumbers\n {\n private static readonly Dictionary<int, HashSet<int>> NumberChain = new Dictionary<int, HashSet<int>>(); \n private static readonly Dictionary<string, bool> HappyNumberResults = new Dictionary<string, bool>();\n\n public static bool IsAHappyNumber(this int startingNumber)\n {\n var digitsToTest = startingNumber.GetDigits()\n .StripZeroes()\n .OrderedByDigit();\n\n var happyNumberKey = string.Join(\",\", digitsToTest);\n\n if (AlreadyKnowThatThisNumberIsHappy(happyNumberKey))\n {\n return HappyNumberResults[happyNumberKey];\n }\n\n GuardAgainstStrangeness(startingNumber);\n NumberChain.Add(startingNumber, new HashSet<int>{startingNumber});\n TestForHappiness(startingNumber, happyNumberKey);\n return HappyNumberResults[happyNumberKey];\n }\n\n private static void GuardAgainstStrangeness(int startingNumber)\n {\n if (NumberChain.ContainsKey(startingNumber))\n {\n throw new Exception(\n string.Format(\n \"I didn't think we could have a number ({0}) without a result that was in the number chain at this point\",\n startingNumber));\n }\n }\n\n private static bool AlreadyKnowThatThisNumberIsHappy(string happyNumberKey)\n {\n return HappyNumberResults.ContainsKey(happyNumberKey);\n }\n\n private static void TestForHappiness(int startingNumber, string happyNumberKey)\n {\n var nextInChain = startingNumber;\n while (!HappyNumberCalculationIsCompleteFor(happyNumberKey))\n {\n nextInChain = nextInChain.GetSumOfSquaredDigits();\n if (nextInChain == 1)\n {\n HappyNumberResults.Add(happyNumberKey, true);\n break;\n }\n if (TheCalculationChainHasLoopedAround(startingNumber, nextInChain))\n {\n HappyNumberResults.Add(happyNumberKey, false);\n break;\n }\n }\n }\n\n /// <summary>\n /// If the last calculated sum of the squares of the digits is already in the set of calculated numbers\n /// then this number chain has looped around\n /// </summary>\n private static bool TheCalculationChainHasLoopedAround(int startingNumber, int sumOfSquaredDigits)\n {\n var canAddToTheNumbersInThisChain = NumberChain[startingNumber].Add(sumOfSquaredDigits);\n return !canAddToTheNumbersInThisChain;\n }\n\n private static bool HappyNumberCalculationIsCompleteFor(string happyNumberKey)\n {\n return HappyNumberResults.ContainsKey(happyNumberKey);\n }\n\n private static int GetSumOfSquaredDigits(this int number)\n {\n return number.GetDigits()\n .Sum(digit => digit*digit);\n }\n\n private static IEnumerable<int> GetDigits(this int number)\n {\n return number.ToString(CultureInfo.InvariantCulture)\n .Select(digit => int.Parse(digit.ToString(CultureInfo.InvariantCulture)));\n }\n\n private static IEnumerable<int> StripZeroes(this IEnumerable<int> numbers)\n {\n return numbers.Where(digit => digit != 0);\n }\n\n private static IEnumerable<int> OrderedByDigit(this IEnumerable<int> numbers)\n {\n return numbers.OrderBy(i=>i);\n }\n }\n}\n\n\n\nOK, there's a lot going on there. First there are two dictionaries: one which keeps track of the numbers generated while processing each number processed; the other which keeps track of the results for a key describing each number (not the number be being processed).\n\nprivate static readonly Dictionary<int, HashSet<int>> NumberChain = new Dictionary<int, HashSet<int>>(); \nprivate static readonly Dictionary<string, bool> HappyNumberResults = new Dictionary<string, bool>();\n\n\nThe first dictionary is used for deciding when a number is sad - if a number is seen for a second time then either it was the start number or the process has started looping. The second dictionary is for shortcut results. That is since 123, 213, 321, 1203, 2130, 3021, etc all have the same result once we've seen 123 we can immediately return a result for all other numbers that have a single 1, 2, and 3 and any number of zeroes.\n\nThen var happyNumberKey = string.Join(\",\", digitsToTest); because two instances of int[] aren't equal based on their contents it is necessary to generate a key that from the arrays so that they can be compared when adding to the HappyNumberResults dictionary.\n\nThere are a bunch of methods to help reveal intent - mainly for this method that does the meat of the work:\nprivate static void TestForHappiness(int startingNumber, string happyNumberKey)\n{\n var nextInChain = startingNumber;\n while (!HappyNumberCalculationIsCompleteFor(happyNumberKey))\n {\n nextInChain = nextInChain.GetSumOfSquaredDigits();\n if (nextInChain == 1)\n {\n HappyNumberResults.Add(happyNumberKey, true);\n break;\n }\n if (TheCalculationChainHasLoopedAround(startingNumber, nextInChain))\n {\n HappyNumberResults.Add(happyNumberKey, false);\n break;\n }\n }\n}\n\n\nThis expresses the algorithm: take a number, get the sum of the square of its digits, test for a result, stop if you have one or do the same to that sum. I don't like the triple check of HappyNumberIsCompleteFor, nextInChain==1, and TheCalculationChainHasLoopedAround but I can't immediately see how to split that up without it being too meh.\n\nResults\nMy first naive implementation didn't order digits or strip zeroes and reached around 320,000 in five seconds. I added ordering of digits but (since I was drinking) I used an integer array as the key on the HappyNumbersResults dictionary - doh! At least when performance didn't improve I realised what I'd done.\n\nSwitching to a string key for the short-cut dictionary had, as could be expected, no impact for unordered digits but pushes the maximum reached up to around 2,000,000 for ordered digits.\n\nRemoving zeroes from the digits array didn't have much impact - presumably because calculating the square of zero isn't very expensive.\n\nCan this be improved?\nProcessing two million numbers in five seconds is pretty good but I wondered if this could be improved on with some of the fangling available in the TPL library.\n\nFirst lesson here was that I don't get the TPL at all… at all\n\nMy first attempt at parallel processing of the list meant adding the cost of starting a thread for every number (as the Happy Numbers are processed one at a time) so I added an extension method to call AreHappyNumbers on a list of integers.\n\npublic static Dictionary<int, bool> AreHappyNumbers(\n this IEnumerable<int> numbersToProcess, \n CancellationToken cancellationToken)\n{\n var numbers = numbersToProcess as int[] ?? numbersToProcess.ToArray();\n var results = new Dictionary<int, bool>(numbers.Count());\n foreach (var number in numbers)\n {\n if (cancellationToken.IsCancellationRequested)\n {\n Debug.WriteLine(\"returning before processing {0} on cancel\", number);\n return results;\n }\n results.Add(number, number.IsAHappyNumber());\n }\n return results;\n} \n\n\nThis method takes a range of numbers and a cancellation token. It then loops over the numbers calculating if they are happy and testing for cancellation before each number.\n\nAfter quite a few false starts and confusions with the TPL I ended up with the following:\n\n[Test]\npublic void ParallelRunForFiveSeconds()\n{\n var watch = Stopwatch.StartNew();\n var cancellationTokenSource = new CancellationTokenSource();\n var tasks = new List<Task<Dictionary<int, bool>>>();\n var count = 0;\n\n //without this line the whole thing runs to completion\n cancellationTokenSource.CancelAfter(5000);\n\n try\n {\n foreach (var index in Enumerable.Range(0, 10))\n {\n var cancellationToken = cancellationTokenSource.Token;\n tasks.Add(Task.Factory.StartNew(\n () => Enumerable.Range(index * 1000000, 1000000)\n .AreHappyNumbers(cancellationToken)));\n }\n\n //without timeout the stopwatch measures around 6.5 seconds\n Task.WaitAll(tasks.Cast<Task>().ToArray(), timeout: TimeSpan.FromSeconds(5));\n count = tasks.Select(t => t.Result).Sum(result => result.Count);\n }\n catch (TaskCanceledException)\n {\n Debug.WriteLine(\"task was cancelled and that's ok\");\n }\n\n Debug.WriteLine(\"watch has been running for {0} seconds\", watch.Elapsed.TotalSeconds);\n\n Debug.WriteLine(\"In five seconds the number of numbers was {0}\", count);\n}\n\n\nSo, yes that's not a test and it is probably awful TPL code but I'm pretty damn sure it doesn't run for more than 5 seconds and it calculates…\n\n<drumroll/>\n\naround SEVEN AND A HALF MILLION NUMBERS in those five seconds. Yes, they're not consecutive - but that's a pretty good improvement from two million. Such a good improvement that I'm doubting myself (although I can't see the error if there was one!)\n\nSo…\n\nI thought the Happy Numbers kata would be a little diversion for an evening but the addition of a five second limit suggested in Kevin Rutherford's post made for a really interesting challenge.\n\nI don't tend to work on problems that lead me to need to optimise as heavily as I have done here. That meant I had to think very differently about what I was doing and that's always a good thing (I think). Although it has lead to some pretty ugly code. Maybe after a little rest I'll see if I can keep the performance and make it smell less - it's definitely ended up as a ball of mud!\n\nIf anyone does grok the TPL and can point out what I've done badly or could be improved the code is on GitHub and I'd appreciate any pointers.\n\n"
}
</script>
<article>
<header class="flex flex-col border-b-black border-b-2 bg-white text-black">
<div class="heading">
<div class="date">Sat Nov 22 2014</div>
<h1 class="title leading-10 pt-2 mb-0 mt-1">Happy Numbers</h1>
</div>
<div class="meta flex-grow flex flex-row">
<div class="share-this flex self-end space-x-2">
<a
id="facebook-share-link"
class="social-share"
target="_blank"
rel="noopener"
href="https://www.facebook.com/dialog/share?app_id=305449093152216&href=https://pauldambra.dev/happy-numbers-kata.html"
>
<img
class="w-8"
src="/images/facebook-black-32.png"
alt="share on facebook"
width="32"
height="32"
/>
</a>
<a
id="twitter-share-link"
class="social-share"
target="_blank"
rel="noopener"
href="https://twitter.com/intent/tweet?text=Happy+Numbers&via=pauldambra&url=https://pauldambra.dev/happy-numbers-kata.html"
>
<img
class="w-8"
src="/images/twitter-black-32.png"
alt="share on twitter"
width="32"
height="32"
/>
</a>
</div>
<div class="more-like-this text-right content-end flex-grow">
<a
class="post-metadata"
href="/categories.html#kata"
>
in: kata
</a>
<div>
<span class="text-slate-500">
<img class="w-6 h-6 inline-block" src="/images/tag.svg" alt="tag-icon" />
<a class="no-underline hover:underline" href="/tags.html#c">
c#
</a>
</span>
<span class="text-slate-500">
<img class="w-6 h-6 inline-block" src="/images/tag.svg" alt="tag-icon" />
<a class="no-underline hover:underline" href="/tags.html#kata">
kata
</a>
</span>
<span class="text-slate-500">
<img class="w-6 h-6 inline-block" src="/images/tag.svg" alt="tag-icon" />
<a class="no-underline hover:underline" href="/tags.html#tdd">
tdd
</a>
</span>
<span class="text-slate-500">
<img class="w-6 h-6 inline-block" src="/images/tag.svg" alt="tag-icon" />
<a class="no-underline hover:underline" href="/tags.html#learning">
learning
</a>
</span>
</div>
</div>
</div>
</header>
<div class="post">
<p>I love C# but while we're trying to beat our deployment process into submission at work I'm only really writing Ruby and Powershell. So when a <a href="http://silkandspinach.net/2014/11/08/the-happy-numbers-kata/">few</a>, <a href="http://silkandspinach.net/2014/11/13/happy-numbers-again-spoilers/">different</a> <a href="http://www.ryanwgough.com/blog/happy_numbers.html">articles</a> about the Happy Numbers kata turned up on my twitter feed and I found myself with a large whisky and a sleeping family I thought I'd have a go.</p>
<p>The Happy Numbers kata is defined as</p>
<blockquote>
<p>Choose a two-digit number (eg. 23), square each digit and add them together.
Keep repeating this until you reach 1
or the cycle carries on in a continuous loop.</p>
<p>If you reach 1 then the number you started with is a “happy number”.</p>
<p>Can you find all the happy numbers between 1 and 100?</p>
</blockquote>
<!--more-->
<p>There is more info on <a href="http://en.wikipedia.org/wiki/Happy_number">what a Happy Number is on wikipedia</a>.</p>
<p>The second link <a href="http://silkandspinach.net/2014/11/13/happy-numbers-again-spoilers/">above</a> has some spoilers in. Particularly that the order of the numbers doesn't matter, and that zeroes don't matter. I did previously rediscover that the order that you add numbers doesn't matter when working on some insurance software a few years back (although it took me a while :annoyedwithselfemoticon:) so let's be kind to me and assume I'd have got there on my own if I hadn't read the article first (although it was a <em>large</em> whisky).</p>
<p>After writing a couple of tests:</p>
<div class="language-c# highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="p">[</span><span class="n">Test</span><span class="p">]</span>
<span class="p">[</span><span class="nf">TestCase</span><span class="p">(</span><span class="m">31</span><span class="p">,</span> <span class="k">true</span><span class="p">)]</span>
<span class="p">[</span><span class="nf">TestCase</span><span class="p">(</span><span class="m">4</span><span class="p">,</span> <span class="k">false</span><span class="p">)]</span>
<span class="p">[</span><span class="nf">TestCase</span><span class="p">(</span><span class="m">2</span><span class="p">,</span> <span class="k">false</span><span class="p">)]</span>
<span class="k">public</span> <span class="k">void</span> <span class="nf">CanIdentifyHappyNumber</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="kt">bool</span> <span class="n">expected</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">Assert</span><span class="p">.</span><span class="nf">AreEqual</span><span class="p">(</span><span class="n">expected</span><span class="p">,</span> <span class="n">i</span><span class="p">.</span><span class="nf">IsAHappyNumber</span><span class="p">());</span>
<span class="p">}</span>
</code></pre></div></div>
<p>I realised that I really like Ruby's having a question mark on methods that return a boolean and miss that feature in C#.</p>
<p>And that the sensible public API was a call to <code class="language-plaintext highlighter-rouge">IsAHappyNumber</code> directly on the integer so I could crank out a large test.</p>
<div class="language-c# highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="c1">// Taken from http://oeis.org/A007770</span>
<span class="k">private</span> <span class="k">static</span> <span class="k">readonly</span> <span class="kt">int</span><span class="p">[]</span> <span class="n">HappyNumbersUpTo1000</span> <span class="p">=</span>
<span class="p">{</span>
<span class="m">1</span><span class="p">,</span> <span class="m">7</span><span class="p">,</span> <span class="m">10</span><span class="p">,</span> <span class="m">13</span><span class="p">,</span> <span class="m">19</span><span class="p">,</span> <span class="m">23</span><span class="p">,</span> <span class="m">28</span><span class="p">,</span> <span class="m">31</span><span class="p">,</span> <span class="m">32</span><span class="p">,</span> <span class="m">44</span><span class="p">,</span> <span class="m">49</span><span class="p">,</span> <span class="m">68</span><span class="p">,</span> <span class="m">70</span><span class="p">,</span> <span class="m">79</span><span class="p">,</span> <span class="m">82</span><span class="p">,</span> <span class="m">86</span><span class="p">,</span> <span class="m">91</span><span class="p">,</span> <span class="m">94</span><span class="p">,</span> <span class="m">97</span><span class="p">,</span> <span class="m">100</span><span class="p">,</span> <span class="m">103</span><span class="p">,</span> <span class="m">109</span><span class="p">,</span> <span class="m">129</span><span class="p">,</span> <span class="m">130</span><span class="p">,</span> <span class="m">133</span><span class="p">,</span> <span class="m">139</span><span class="p">,</span>
<span class="m">167</span><span class="p">,</span> <span class="m">176</span><span class="p">,</span> <span class="m">188</span><span class="p">,</span> <span class="m">190</span><span class="p">,</span> <span class="m">192</span><span class="p">,</span> <span class="m">193</span><span class="p">,</span> <span class="m">203</span><span class="p">,</span> <span class="m">208</span><span class="p">,</span> <span class="m">219</span><span class="p">,</span> <span class="m">226</span><span class="p">,</span> <span class="m">230</span><span class="p">,</span> <span class="m">236</span><span class="p">,</span> <span class="m">239</span><span class="p">,</span> <span class="m">262</span><span class="p">,</span> <span class="m">263</span><span class="p">,</span> <span class="m">280</span><span class="p">,</span> <span class="m">291</span><span class="p">,</span> <span class="m">293</span><span class="p">,</span> <span class="m">301</span><span class="p">,</span> <span class="m">302</span><span class="p">,</span> <span class="m">310</span><span class="p">,</span> <span class="m">313</span><span class="p">,</span>
<span class="m">319</span><span class="p">,</span> <span class="m">320</span><span class="p">,</span> <span class="m">326</span><span class="p">,</span> <span class="m">329</span><span class="p">,</span> <span class="m">331</span><span class="p">,</span> <span class="m">338</span><span class="p">,</span> <span class="m">356</span><span class="p">,</span> <span class="m">362</span><span class="p">,</span> <span class="m">365</span><span class="p">,</span> <span class="m">367</span><span class="p">,</span> <span class="m">368</span><span class="p">,</span> <span class="m">376</span><span class="p">,</span> <span class="m">379</span><span class="p">,</span> <span class="m">383</span><span class="p">,</span> <span class="m">386</span><span class="p">,</span> <span class="m">391</span><span class="p">,</span> <span class="m">392</span><span class="p">,</span> <span class="m">397</span><span class="p">,</span> <span class="m">404</span><span class="p">,</span> <span class="m">409</span><span class="p">,</span> <span class="m">440</span><span class="p">,</span> <span class="m">446</span><span class="p">,</span>
<span class="m">464</span><span class="p">,</span> <span class="m">469</span><span class="p">,</span> <span class="m">478</span><span class="p">,</span> <span class="m">487</span><span class="p">,</span> <span class="m">490</span><span class="p">,</span> <span class="m">496</span><span class="p">,</span> <span class="m">536</span><span class="p">,</span> <span class="m">556</span><span class="p">,</span> <span class="m">563</span><span class="p">,</span> <span class="m">565</span><span class="p">,</span> <span class="m">566</span><span class="p">,</span> <span class="m">608</span><span class="p">,</span> <span class="m">617</span><span class="p">,</span> <span class="m">622</span><span class="p">,</span> <span class="m">623</span><span class="p">,</span> <span class="m">632</span><span class="p">,</span> <span class="m">635</span><span class="p">,</span> <span class="m">637</span><span class="p">,</span> <span class="m">638</span><span class="p">,</span> <span class="m">644</span><span class="p">,</span> <span class="m">649</span><span class="p">,</span> <span class="m">653</span><span class="p">,</span>
<span class="m">655</span><span class="p">,</span> <span class="m">656</span><span class="p">,</span> <span class="m">665</span><span class="p">,</span> <span class="m">671</span><span class="p">,</span> <span class="m">673</span><span class="p">,</span> <span class="m">680</span><span class="p">,</span> <span class="m">683</span><span class="p">,</span> <span class="m">694</span><span class="p">,</span> <span class="m">700</span><span class="p">,</span> <span class="m">709</span><span class="p">,</span> <span class="m">716</span><span class="p">,</span> <span class="m">736</span><span class="p">,</span> <span class="m">739</span><span class="p">,</span> <span class="m">748</span><span class="p">,</span> <span class="m">761</span><span class="p">,</span> <span class="m">763</span><span class="p">,</span> <span class="m">784</span><span class="p">,</span> <span class="m">790</span><span class="p">,</span> <span class="m">793</span><span class="p">,</span> <span class="m">802</span><span class="p">,</span> <span class="m">806</span><span class="p">,</span> <span class="m">818</span><span class="p">,</span>
<span class="m">820</span><span class="p">,</span> <span class="m">833</span><span class="p">,</span> <span class="m">836</span><span class="p">,</span> <span class="m">847</span><span class="p">,</span> <span class="m">860</span><span class="p">,</span> <span class="m">863</span><span class="p">,</span> <span class="m">874</span><span class="p">,</span> <span class="m">881</span><span class="p">,</span> <span class="m">888</span><span class="p">,</span> <span class="m">899</span><span class="p">,</span> <span class="m">901</span><span class="p">,</span> <span class="m">904</span><span class="p">,</span> <span class="m">907</span><span class="p">,</span> <span class="m">910</span><span class="p">,</span> <span class="m">912</span><span class="p">,</span> <span class="m">913</span><span class="p">,</span> <span class="m">921</span><span class="p">,</span> <span class="m">923</span><span class="p">,</span> <span class="m">931</span><span class="p">,</span> <span class="m">932</span><span class="p">,</span> <span class="m">937</span><span class="p">,</span> <span class="m">940</span><span class="p">,</span>
<span class="m">946</span><span class="p">,</span> <span class="m">964</span><span class="p">,</span> <span class="m">970</span><span class="p">,</span> <span class="m">973</span><span class="p">,</span> <span class="m">989</span><span class="p">,</span> <span class="m">998</span><span class="p">,</span> <span class="m">1000</span>
<span class="p">};</span>
<span class="p">[</span><span class="n">Test</span><span class="p">]</span>
<span class="k">public</span> <span class="k">void</span> <span class="nf">CanTestAThousandNumbers</span><span class="p">()</span>
<span class="p">{</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">var</span> <span class="n">i</span> <span class="p">=</span> <span class="m">0</span><span class="p">;</span> <span class="n">i</span> <span class="p"><</span> <span class="m">1000</span><span class="p">;</span> <span class="n">i</span><span class="p">++)</span>
<span class="p">{</span>
<span class="n">Assert</span><span class="p">.</span><span class="nf">AreEqual</span><span class="p">(</span><span class="n">HappyNumbersUpTo1000</span><span class="p">.</span><span class="nf">Contains</span><span class="p">(</span><span class="n">i</span><span class="p">),</span> <span class="n">i</span><span class="p">.</span><span class="nf">IsAHappyNumber</span><span class="p">());</span>
<span class="p">}</span>
<span class="p">}</span>
</code></pre></div></div>
<p>So, with a 1000 failing tests I could run through a few naive implementations to get to a reasonable one.</p>
<div class="language-c# highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">using</span> <span class="nn">System</span><span class="p">;</span>
<span class="k">using</span> <span class="nn">System.Collections.Generic</span><span class="p">;</span>
<span class="k">using</span> <span class="nn">System.Globalization</span><span class="p">;</span>
<span class="k">using</span> <span class="nn">System.Linq</span><span class="p">;</span>
<span class="k">namespace</span> <span class="nn">HappyNumbers</span>
<span class="p">{</span>
<span class="c1">// Choose a two-digit number (eg. 23), square each digit and add them together. </span>
<span class="c1">// Keep repeating this until you reach 1 or the cycle carries on in a continuous loop. </span>
<span class="c1">// If you reach 1 then the number you started with is a “happy number”.</span>
<span class="k">public</span> <span class="k">static</span> <span class="k">class</span> <span class="nc">HappyNumbers</span>
<span class="p">{</span>
<span class="k">private</span> <span class="k">static</span> <span class="k">readonly</span> <span class="n">Dictionary</span><span class="p"><</span><span class="kt">int</span><span class="p">,</span> <span class="n">HashSet</span><span class="p"><</span><span class="kt">int</span><span class="p">>></span> <span class="n">NumberChain</span> <span class="p">=</span> <span class="k">new</span> <span class="n">Dictionary</span><span class="p"><</span><span class="kt">int</span><span class="p">,</span> <span class="n">HashSet</span><span class="p"><</span><span class="kt">int</span><span class="p">>>();</span>
<span class="k">private</span> <span class="k">static</span> <span class="k">readonly</span> <span class="n">Dictionary</span><span class="p"><</span><span class="kt">string</span><span class="p">,</span> <span class="kt">bool</span><span class="p">></span> <span class="n">HappyNumberResults</span> <span class="p">=</span> <span class="k">new</span> <span class="n">Dictionary</span><span class="p"><</span><span class="kt">string</span><span class="p">,</span> <span class="kt">bool</span><span class="p">>();</span>
<span class="k">public</span> <span class="k">static</span> <span class="kt">bool</span> <span class="nf">IsAHappyNumber</span><span class="p">(</span><span class="k">this</span> <span class="kt">int</span> <span class="n">startingNumber</span><span class="p">)</span>
<span class="p">{</span>
<span class="kt">var</span> <span class="n">digitsToTest</span> <span class="p">=</span> <span class="n">startingNumber</span><span class="p">.</span><span class="nf">GetDigits</span><span class="p">()</span>
<span class="p">.</span><span class="nf">StripZeroes</span><span class="p">()</span>
<span class="p">.</span><span class="nf">OrderedByDigit</span><span class="p">();</span>
<span class="kt">var</span> <span class="n">happyNumberKey</span> <span class="p">=</span> <span class="kt">string</span><span class="p">.</span><span class="nf">Join</span><span class="p">(</span><span class="s">","</span><span class="p">,</span> <span class="n">digitsToTest</span><span class="p">);</span>
<span class="k">if</span> <span class="p">(</span><span class="nf">AlreadyKnowThatThisNumberIsHappy</span><span class="p">(</span><span class="n">happyNumberKey</span><span class="p">))</span>
<span class="p">{</span>
<span class="k">return</span> <span class="n">HappyNumberResults</span><span class="p">[</span><span class="n">happyNumberKey</span><span class="p">];</span>
<span class="p">}</span>
<span class="nf">GuardAgainstStrangeness</span><span class="p">(</span><span class="n">startingNumber</span><span class="p">);</span>
<span class="n">NumberChain</span><span class="p">.</span><span class="nf">Add</span><span class="p">(</span><span class="n">startingNumber</span><span class="p">,</span> <span class="k">new</span> <span class="n">HashSet</span><span class="p"><</span><span class="kt">int</span><span class="p">>{</span><span class="n">startingNumber</span><span class="p">});</span>
<span class="nf">TestForHappiness</span><span class="p">(</span><span class="n">startingNumber</span><span class="p">,</span> <span class="n">happyNumberKey</span><span class="p">);</span>
<span class="k">return</span> <span class="n">HappyNumberResults</span><span class="p">[</span><span class="n">happyNumberKey</span><span class="p">];</span>
<span class="p">}</span>
<span class="k">private</span> <span class="k">static</span> <span class="k">void</span> <span class="nf">GuardAgainstStrangeness</span><span class="p">(</span><span class="kt">int</span> <span class="n">startingNumber</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">if</span> <span class="p">(</span><span class="n">NumberChain</span><span class="p">.</span><span class="nf">ContainsKey</span><span class="p">(</span><span class="n">startingNumber</span><span class="p">))</span>
<span class="p">{</span>
<span class="k">throw</span> <span class="k">new</span> <span class="nf">Exception</span><span class="p">(</span>
<span class="kt">string</span><span class="p">.</span><span class="nf">Format</span><span class="p">(</span>
<span class="s">"I didn't think we could have a number ({0}) without a result that was in the number chain at this point"</span><span class="p">,</span>
<span class="n">startingNumber</span><span class="p">));</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="k">private</span> <span class="k">static</span> <span class="kt">bool</span> <span class="nf">AlreadyKnowThatThisNumberIsHappy</span><span class="p">(</span><span class="kt">string</span> <span class="n">happyNumberKey</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">return</span> <span class="n">HappyNumberResults</span><span class="p">.</span><span class="nf">ContainsKey</span><span class="p">(</span><span class="n">happyNumberKey</span><span class="p">);</span>
<span class="p">}</span>
<span class="k">private</span> <span class="k">static</span> <span class="k">void</span> <span class="nf">TestForHappiness</span><span class="p">(</span><span class="kt">int</span> <span class="n">startingNumber</span><span class="p">,</span> <span class="kt">string</span> <span class="n">happyNumberKey</span><span class="p">)</span>
<span class="p">{</span>
<span class="kt">var</span> <span class="n">nextInChain</span> <span class="p">=</span> <span class="n">startingNumber</span><span class="p">;</span>
<span class="k">while</span> <span class="p">(!</span><span class="nf">HappyNumberCalculationIsCompleteFor</span><span class="p">(</span><span class="n">happyNumberKey</span><span class="p">))</span>
<span class="p">{</span>
<span class="n">nextInChain</span> <span class="p">=</span> <span class="n">nextInChain</span><span class="p">.</span><span class="nf">GetSumOfSquaredDigits</span><span class="p">();</span>
<span class="k">if</span> <span class="p">(</span><span class="n">nextInChain</span> <span class="p">==</span> <span class="m">1</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">HappyNumberResults</span><span class="p">.</span><span class="nf">Add</span><span class="p">(</span><span class="n">happyNumberKey</span><span class="p">,</span> <span class="k">true</span><span class="p">);</span>
<span class="k">break</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">if</span> <span class="p">(</span><span class="nf">TheCalculationChainHasLoopedAround</span><span class="p">(</span><span class="n">startingNumber</span><span class="p">,</span> <span class="n">nextInChain</span><span class="p">))</span>
<span class="p">{</span>
<span class="n">HappyNumberResults</span><span class="p">.</span><span class="nf">Add</span><span class="p">(</span><span class="n">happyNumberKey</span><span class="p">,</span> <span class="k">false</span><span class="p">);</span>
<span class="k">break</span><span class="p">;</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="c1">/// <summary></span>
<span class="c1">/// If the last calculated sum of the squares of the digits is already in the set of calculated numbers</span>
<span class="c1">/// then this number chain has looped around</span>
<span class="c1">/// </summary></span>
<span class="k">private</span> <span class="k">static</span> <span class="kt">bool</span> <span class="nf">TheCalculationChainHasLoopedAround</span><span class="p">(</span><span class="kt">int</span> <span class="n">startingNumber</span><span class="p">,</span> <span class="kt">int</span> <span class="n">sumOfSquaredDigits</span><span class="p">)</span>
<span class="p">{</span>
<span class="kt">var</span> <span class="n">canAddToTheNumbersInThisChain</span> <span class="p">=</span> <span class="n">NumberChain</span><span class="p">[</span><span class="n">startingNumber</span><span class="p">].</span><span class="nf">Add</span><span class="p">(</span><span class="n">sumOfSquaredDigits</span><span class="p">);</span>
<span class="k">return</span> <span class="p">!</span><span class="n">canAddToTheNumbersInThisChain</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">private</span> <span class="k">static</span> <span class="kt">bool</span> <span class="nf">HappyNumberCalculationIsCompleteFor</span><span class="p">(</span><span class="kt">string</span> <span class="n">happyNumberKey</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">return</span> <span class="n">HappyNumberResults</span><span class="p">.</span><span class="nf">ContainsKey</span><span class="p">(</span><span class="n">happyNumberKey</span><span class="p">);</span>
<span class="p">}</span>
<span class="k">private</span> <span class="k">static</span> <span class="kt">int</span> <span class="nf">GetSumOfSquaredDigits</span><span class="p">(</span><span class="k">this</span> <span class="kt">int</span> <span class="n">number</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">return</span> <span class="n">number</span><span class="p">.</span><span class="nf">GetDigits</span><span class="p">()</span>
<span class="p">.</span><span class="nf">Sum</span><span class="p">(</span><span class="n">digit</span> <span class="p">=></span> <span class="n">digit</span><span class="p">*</span><span class="n">digit</span><span class="p">);</span>
<span class="p">}</span>
<span class="k">private</span> <span class="k">static</span> <span class="n">IEnumerable</span><span class="p"><</span><span class="kt">int</span><span class="p">></span> <span class="nf">GetDigits</span><span class="p">(</span><span class="k">this</span> <span class="kt">int</span> <span class="n">number</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">return</span> <span class="n">number</span><span class="p">.</span><span class="nf">ToString</span><span class="p">(</span><span class="n">CultureInfo</span><span class="p">.</span><span class="n">InvariantCulture</span><span class="p">)</span>
<span class="p">.</span><span class="nf">Select</span><span class="p">(</span><span class="n">digit</span> <span class="p">=></span> <span class="kt">int</span><span class="p">.</span><span class="nf">Parse</span><span class="p">(</span><span class="n">digit</span><span class="p">.</span><span class="nf">ToString</span><span class="p">(</span><span class="n">CultureInfo</span><span class="p">.</span><span class="n">InvariantCulture</span><span class="p">)));</span>
<span class="p">}</span>
<span class="k">private</span> <span class="k">static</span> <span class="n">IEnumerable</span><span class="p"><</span><span class="kt">int</span><span class="p">></span> <span class="nf">StripZeroes</span><span class="p">(</span><span class="k">this</span> <span class="n">IEnumerable</span><span class="p"><</span><span class="kt">int</span><span class="p">></span> <span class="n">numbers</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">return</span> <span class="n">numbers</span><span class="p">.</span><span class="nf">Where</span><span class="p">(</span><span class="n">digit</span> <span class="p">=></span> <span class="n">digit</span> <span class="p">!=</span> <span class="m">0</span><span class="p">);</span>
<span class="p">}</span>
<span class="k">private</span> <span class="k">static</span> <span class="n">IEnumerable</span><span class="p"><</span><span class="kt">int</span><span class="p">></span> <span class="nf">OrderedByDigit</span><span class="p">(</span><span class="k">this</span> <span class="n">IEnumerable</span><span class="p"><</span><span class="kt">int</span><span class="p">></span> <span class="n">numbers</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">return</span> <span class="n">numbers</span><span class="p">.</span><span class="nf">OrderBy</span><span class="p">(</span><span class="n">i</span><span class="p">=></span><span class="n">i</span><span class="p">);</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="p">}</span>
</code></pre></div></div>
<p>OK, there's a lot going on there. First there are two dictionaries: one which keeps track of the numbers generated while processing each number processed; the other which keeps track of the results for a key describing each number (not the number be being processed).</p>
<div class="language-c# highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">private</span> <span class="k">static</span> <span class="k">readonly</span> <span class="n">Dictionary</span><span class="p"><</span><span class="kt">int</span><span class="p">,</span> <span class="n">HashSet</span><span class="p"><</span><span class="kt">int</span><span class="p">>></span> <span class="n">NumberChain</span> <span class="p">=</span> <span class="k">new</span> <span class="n">Dictionary</span><span class="p"><</span><span class="kt">int</span><span class="p">,</span> <span class="n">HashSet</span><span class="p"><</span><span class="kt">int</span><span class="p">>>();</span>
<span class="k">private</span> <span class="k">static</span> <span class="k">readonly</span> <span class="n">Dictionary</span><span class="p"><</span><span class="kt">string</span><span class="p">,</span> <span class="kt">bool</span><span class="p">></span> <span class="n">HappyNumberResults</span> <span class="p">=</span> <span class="k">new</span> <span class="n">Dictionary</span><span class="p"><</span><span class="kt">string</span><span class="p">,</span> <span class="kt">bool</span><span class="p">>();</span>
</code></pre></div></div>
<p>The first dictionary is used for deciding when a number is sad - if a number is seen for a second time then either it was the start number or the process has started looping. The second dictionary is for shortcut results. That is since 123, 213, 321, 1203, 2130, 3021, etc all have the same result once we've seen 123 we can immediately return a result for all other numbers that have a single 1, 2, and 3 and any number of zeroes.</p>
<p>Then <code class="language-plaintext highlighter-rouge">var happyNumberKey = string.Join(",", digitsToTest);</code> because two instances of <code class="language-plaintext highlighter-rouge">int[]</code> aren't equal based on their contents it is necessary to generate a key that from the arrays so that they can be compared when adding to the HappyNumberResults dictionary.</p>
<p>There are a bunch of methods to help reveal intent - mainly for this method that does the meat of the work:</p>
<div class="language-c# highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">private</span> <span class="k">static</span> <span class="k">void</span> <span class="nf">TestForHappiness</span><span class="p">(</span><span class="kt">int</span> <span class="n">startingNumber</span><span class="p">,</span> <span class="kt">string</span> <span class="n">happyNumberKey</span><span class="p">)</span>
<span class="p">{</span>
<span class="kt">var</span> <span class="n">nextInChain</span> <span class="p">=</span> <span class="n">startingNumber</span><span class="p">;</span>
<span class="k">while</span> <span class="p">(!</span><span class="nf">HappyNumberCalculationIsCompleteFor</span><span class="p">(</span><span class="n">happyNumberKey</span><span class="p">))</span>
<span class="p">{</span>
<span class="n">nextInChain</span> <span class="p">=</span> <span class="n">nextInChain</span><span class="p">.</span><span class="nf">GetSumOfSquaredDigits</span><span class="p">();</span>
<span class="k">if</span> <span class="p">(</span><span class="n">nextInChain</span> <span class="p">==</span> <span class="m">1</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">HappyNumberResults</span><span class="p">.</span><span class="nf">Add</span><span class="p">(</span><span class="n">happyNumberKey</span><span class="p">,</span> <span class="k">true</span><span class="p">);</span>
<span class="k">break</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">if</span> <span class="p">(</span><span class="nf">TheCalculationChainHasLoopedAround</span><span class="p">(</span><span class="n">startingNumber</span><span class="p">,</span> <span class="n">nextInChain</span><span class="p">))</span>
<span class="p">{</span>
<span class="n">HappyNumberResults</span><span class="p">.</span><span class="nf">Add</span><span class="p">(</span><span class="n">happyNumberKey</span><span class="p">,</span> <span class="k">false</span><span class="p">);</span>
<span class="k">break</span><span class="p">;</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="p">}</span>
</code></pre></div></div>
<p>This expresses the algorithm: take a number, get the sum of the square of its digits, test for a result, stop if you have one or do the same to that sum. I don't like the triple check of <code class="language-plaintext highlighter-rouge">HappyNumberIsCompleteFor</code>, <code class="language-plaintext highlighter-rouge">nextInChain==1</code>, and <code class="language-plaintext highlighter-rouge">TheCalculationChainHasLoopedAround</code> but I can't immediately see how to split that up without it being too meh.</p>
<h1 id="results">Results</h1>
<p>My first naive implementation didn't order digits or strip zeroes and reached around 320,000 in five seconds. I added ordering of digits but (since I was drinking) I used an integer array as the key on the HappyNumbersResults dictionary - doh! At least when performance didn't improve I realised what I'd done.</p>
<p>Switching to a string key for the short-cut dictionary had, as could be expected, no impact for unordered digits but pushes the maximum reached up to around 2,000,000 for ordered digits.</p>
<p>Removing zeroes from the digits array didn't have much impact - presumably because calculating the square of zero isn't very expensive.</p>
<h1 id="can-this-be-improved">Can this be improved?</h1>
<p>Processing two million numbers in five seconds is pretty good but I wondered if this could be improved on with some of the fangling available in the <a href="http://msdn.microsoft.com/en-us/library/dd460717(v=vs.110).aspx">TPL library</a>.</p>
<p>First lesson here was that I don't get the TPL at all… <em>at all</em></p>
<p>My first attempt at parallel processing of the list meant adding the cost of starting a thread for every number (as the Happy Numbers are processed one at a time) so I added an extension method to call <code class="language-plaintext highlighter-rouge">AreHappyNumbers</code> on a list of integers.</p>
<div class="language-c# highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">public</span> <span class="k">static</span> <span class="n">Dictionary</span><span class="p"><</span><span class="kt">int</span><span class="p">,</span> <span class="kt">bool</span><span class="p">></span> <span class="nf">AreHappyNumbers</span><span class="p">(</span>
<span class="k">this</span> <span class="n">IEnumerable</span><span class="p"><</span><span class="kt">int</span><span class="p">></span> <span class="n">numbersToProcess</span><span class="p">,</span>
<span class="n">CancellationToken</span> <span class="n">cancellationToken</span><span class="p">)</span>
<span class="p">{</span>
<span class="kt">var</span> <span class="n">numbers</span> <span class="p">=</span> <span class="n">numbersToProcess</span> <span class="k">as</span> <span class="kt">int</span><span class="p">[]</span> <span class="p">??</span> <span class="n">numbersToProcess</span><span class="p">.</span><span class="nf">ToArray</span><span class="p">();</span>
<span class="kt">var</span> <span class="n">results</span> <span class="p">=</span> <span class="k">new</span> <span class="n">Dictionary</span><span class="p"><</span><span class="kt">int</span><span class="p">,</span> <span class="kt">bool</span><span class="p">>(</span><span class="n">numbers</span><span class="p">.</span><span class="nf">Count</span><span class="p">());</span>
<span class="k">foreach</span> <span class="p">(</span><span class="kt">var</span> <span class="n">number</span> <span class="k">in</span> <span class="n">numbers</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">if</span> <span class="p">(</span><span class="n">cancellationToken</span><span class="p">.</span><span class="n">IsCancellationRequested</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">Debug</span><span class="p">.</span><span class="nf">WriteLine</span><span class="p">(</span><span class="s">"returning before processing {0} on cancel"</span><span class="p">,</span> <span class="n">number</span><span class="p">);</span>
<span class="k">return</span> <span class="n">results</span><span class="p">;</span>
<span class="p">}</span>
<span class="n">results</span><span class="p">.</span><span class="nf">Add</span><span class="p">(</span><span class="n">number</span><span class="p">,</span> <span class="n">number</span><span class="p">.</span><span class="nf">IsAHappyNumber</span><span class="p">());</span>
<span class="p">}</span>
<span class="k">return</span> <span class="n">results</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div></div>
<p>This method takes a range of numbers and a cancellation token. It then loops over the numbers calculating if they are happy and testing for cancellation before each number.</p>
<p>After quite a few false starts and confusions with the TPL I ended up with the following:</p>
<div class="language-c# highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="p">[</span><span class="n">Test</span><span class="p">]</span>
<span class="k">public</span> <span class="k">void</span> <span class="nf">ParallelRunForFiveSeconds</span><span class="p">()</span>
<span class="p">{</span>
<span class="kt">var</span> <span class="n">watch</span> <span class="p">=</span> <span class="n">Stopwatch</span><span class="p">.</span><span class="nf">StartNew</span><span class="p">();</span>
<span class="kt">var</span> <span class="n">cancellationTokenSource</span> <span class="p">=</span> <span class="k">new</span> <span class="nf">CancellationTokenSource</span><span class="p">();</span>
<span class="kt">var</span> <span class="n">tasks</span> <span class="p">=</span> <span class="k">new</span> <span class="n">List</span><span class="p"><</span><span class="n">Task</span><span class="p"><</span><span class="n">Dictionary</span><span class="p"><</span><span class="kt">int</span><span class="p">,</span> <span class="kt">bool</span><span class="p">>>>();</span>
<span class="kt">var</span> <span class="n">count</span> <span class="p">=</span> <span class="m">0</span><span class="p">;</span>
<span class="c1">//without this line the whole thing runs to completion</span>
<span class="n">cancellationTokenSource</span><span class="p">.</span><span class="nf">CancelAfter</span><span class="p">(</span><span class="m">5000</span><span class="p">);</span>
<span class="k">try</span>
<span class="p">{</span>
<span class="k">foreach</span> <span class="p">(</span><span class="kt">var</span> <span class="n">index</span> <span class="k">in</span> <span class="n">Enumerable</span><span class="p">.</span><span class="nf">Range</span><span class="p">(</span><span class="m">0</span><span class="p">,</span> <span class="m">10</span><span class="p">))</span>
<span class="p">{</span>
<span class="kt">var</span> <span class="n">cancellationToken</span> <span class="p">=</span> <span class="n">cancellationTokenSource</span><span class="p">.</span><span class="n">Token</span><span class="p">;</span>
<span class="n">tasks</span><span class="p">.</span><span class="nf">Add</span><span class="p">(</span><span class="n">Task</span><span class="p">.</span><span class="n">Factory</span><span class="p">.</span><span class="nf">StartNew</span><span class="p">(</span>
<span class="p">()</span> <span class="p">=></span> <span class="n">Enumerable</span><span class="p">.</span><span class="nf">Range</span><span class="p">(</span><span class="n">index</span> <span class="p">*</span> <span class="m">1000000</span><span class="p">,</span> <span class="m">1000000</span><span class="p">)</span>
<span class="p">.</span><span class="nf">AreHappyNumbers</span><span class="p">(</span><span class="n">cancellationToken</span><span class="p">)));</span>
<span class="p">}</span>
<span class="c1">//without timeout the stopwatch measures around 6.5 seconds</span>
<span class="n">Task</span><span class="p">.</span><span class="nf">WaitAll</span><span class="p">(</span><span class="n">tasks</span><span class="p">.</span><span class="n">Cast</span><span class="p"><</span><span class="n">Task</span><span class="p">>().</span><span class="nf">ToArray</span><span class="p">(),</span> <span class="n">timeout</span><span class="p">:</span> <span class="n">TimeSpan</span><span class="p">.</span><span class="nf">FromSeconds</span><span class="p">(</span><span class="m">5</span><span class="p">));</span>
<span class="n">count</span> <span class="p">=</span> <span class="n">tasks</span><span class="p">.</span><span class="nf">Select</span><span class="p">(</span><span class="n">t</span> <span class="p">=></span> <span class="n">t</span><span class="p">.</span><span class="n">Result</span><span class="p">).</span><span class="nf">Sum</span><span class="p">(</span><span class="n">result</span> <span class="p">=></span> <span class="n">result</span><span class="p">.</span><span class="n">Count</span><span class="p">);</span>
<span class="p">}</span>
<span class="k">catch</span> <span class="p">(</span><span class="n">TaskCanceledException</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">Debug</span><span class="p">.</span><span class="nf">WriteLine</span><span class="p">(</span><span class="s">"task was cancelled and that's ok"</span><span class="p">);</span>
<span class="p">}</span>
<span class="n">Debug</span><span class="p">.</span><span class="nf">WriteLine</span><span class="p">(</span><span class="s">"watch has been running for {0} seconds"</span><span class="p">,</span> <span class="n">watch</span><span class="p">.</span><span class="n">Elapsed</span><span class="p">.</span><span class="n">TotalSeconds</span><span class="p">);</span>
<span class="n">Debug</span><span class="p">.</span><span class="nf">WriteLine</span><span class="p">(</span><span class="s">"In five seconds the number of numbers was {0}"</span><span class="p">,</span> <span class="n">count</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></div></div>
<!--alex ignore damn --->
<p>So, yes that's not a test and it is probably awful TPL code but I'm pretty damn sure it doesn't run for more than 5 seconds and it calculates…</p>
<p><code class="language-plaintext highlighter-rouge"><drumroll/></code></p>
<p>around <em>SEVEN AND A HALF MILLION NUMBERS</em> in those five seconds. Yes, they're not consecutive - but that's a pretty good improvement from two million. Such a good improvement that I'm doubting myself (although I can't see the error if there was one!)</p>
<h1 id="so">So…</h1>
<p>I thought the Happy Numbers kata would be a little diversion for an evening but the addition of a five second limit suggested <a href="http://silkandspinach.net/2014/11/08/the-happy-numbers-kata/">in Kevin Rutherford's post</a> made for a really interesting challenge.
<!--alex ignore ball --->
I don't tend to work on problems that lead me to need to optimise as heavily as I have done here. That meant I had to think very differently about what I was doing and that's always a good thing (I think). Although it has lead to some pretty ugly code. Maybe after a little rest I'll see if I can keep the performance and make it smell less - it's definitely ended up as a ball of mud!</p>
<p>If anyone does grok the TPL and can point out what I've done badly or could be improved <a href="https://github.com/pauldambra/HappyNumbersKata">the code is on GitHub</a> and I'd appreciate any pointers.</p>
</div>
<div class="mt-8">
<h1>More like this...</h1>
<div class="grid grid-cols-3 gap-4"></div>
</div>
</article>
</main>
<footer class="w-full h-4 bg-black text-white py-8 px-4">
<a class="no-underline text-white" href="https://pauldambra.dev/feed.xml">
<img class="inline w-6 h-6" src="/images/rss.svg" alt="the rss feed" />
<span>Subscribe to RSS feed</span>
</a>
</footer>
<script>
var tsl = document.getElementById("twitter-share-link");
tsl.addEventListener("click", function () {
ga("send", {
hitType: "social",
socialNetwork: "twitter",
socialAction: "tweet",
socialTarget: "https://pauldambra.dev/happy-numbers-kata.html",
});
});
var fsl = document.getElementById("facebook-share-link");
fsl.addEventListener("click", function () {
ga("send", {
hitType: "social",
socialNetwork: "facebook",
socialAction: "share",
socialTarget: "https://pauldambra.dev/happy-numbers-kata.html",
});
});
</script>
<script defer src="/register-service-worker.js"></script>
<link
href="https://fonts.googleapis.com/css?family=Khula&display=swap"
rel="stylesheet"
/>
</body>
</html>