-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathadvent_of_code_2018_5.html
502 lines (463 loc) · 29.4 KB
/
advent_of_code_2018_5.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
<!DOCTYPE html>
<html>
<head>
<title>Getting started with Scheme by solving an Advent of Code 2018 challenge</title>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link type="application/atom+xml" href="/blog/feed.xml" rel="self">
<link rel="shortcut icon" type="image/ico" href="/blog/favicon.ico">
<link rel="stylesheet" type="text/css" href="main.css">
<link rel="stylesheet" href="https://unpkg.com/@highlightjs/[email protected]/styles/default.min.css">
<script src="highlight.min.js"></script>
<!-- From https://github.com/odin-lang/odin-lang.org/blob/6f48c2cfb094a42dffd34143884fa958bd9c0ba2/themes/odin/layouts/partials/head.html#L71 -->
<script src="x86asm.min.js"></script>
<script src="odin_syntax.js"></script>
<script type="module" src="search_index.js"></script>
<script type="module" src="search.js"></script>
</head>
<body>
<div id="banner">
<div id="name">
<img id="me" src="me.jpeg">
<span>Philippe Gaultier</span>
</div>
<input id="search" placeholder="🔎 Search" autocomplete=off>
<ul>
<li> <a href="/blog/body_of_work.html">Body of work</a> </li>
<li> <a href="/blog/articles-by-tag.html">Tags</a> </li>
<li> <a href="https://github.com/gaultier/resume/raw/master/Philippe_Gaultier_resume_en.pdf">
Resume
</a> </li>
<li> <a href="/blog/feed.xml">
<svg viewBox="0 0 24 24" fill="none" xmlns="http://www.w3.org/2000/svg">
<path fill-rule="evenodd" clip-rule="evenodd" d="M5.5 3.5C4.39543 3.5 3.5 4.39543 3.5 5.5V18.5C3.5 19.6046 4.39543 20.5 5.5 20.5H18.5C19.6046 20.5 20.5 19.6046 20.5 18.5V5.5C20.5 4.39543 19.6046 3.5 18.5 3.5H5.5ZM7 19C8.10457 19 9 18.1046 9 17C9 15.8954 8.10457 15 7 15C5.89543 15 5 15.8954 5 17C5 18.1046 5.89543 19 7 19ZM6.14863 10.5052C6.14863 10.0379 6.52746 9.65906 6.99478 9.65906C7.95949 9.65906 8.91476 9.84908 9.80603 10.2183C10.6973 10.5874 11.5071 11.1285 12.1893 11.8107C12.8715 12.4929 13.4126 13.3027 13.7817 14.194C14.1509 15.0852 14.3409 16.0405 14.3409 17.0052C14.3409 17.4725 13.9621 17.8514 13.4948 17.8514C13.0275 17.8514 12.6486 17.4725 12.6486 17.0052C12.6486 16.2627 12.5024 15.5275 12.2183 14.8416C11.9341 14.1556 11.5177 13.5324 10.9927 13.0073C10.4676 12.4823 9.84437 12.0659 9.15842 11.7817C8.47246 11.4976 7.73726 11.3514 6.99478 11.3514C6.52746 11.3514 6.14863 10.9725 6.14863 10.5052ZM7 5.15385C6.53268 5.15385 6.15385 5.53268 6.15385 6C6.15385 6.46732 6.53268 6.84615 7 6.84615C8.33342 6.84615 9.65379 7.10879 10.8857 7.61907C12.1176 8.12935 13.237 8.87728 14.1799 9.82015C15.1227 10.763 15.8707 11.8824 16.3809 13.1143C16.8912 14.3462 17.1538 15.6666 17.1538 17C17.1538 17.4673 17.5327 17.8462 18 17.8462C18.4673 17.8462 18.8462 17.4673 18.8462 17C18.8462 15.4443 18.5397 13.9039 17.9444 12.4667C17.3491 11.0294 16.4765 9.72352 15.3765 8.6235C14.2765 7.52349 12.9706 6.65091 11.5333 6.05558C10.0961 5.46026 8.55566 5.15385 7 5.15385Z" fill="#000000"/>
</svg>
</a> </li>
<li> <a href="https://www.linkedin.com/in/philippegaultier/">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" data-supported-dps="24x24" fill="currentColor" class="mercado-match" width="24" height="24" focusable="false">
<path d="M20.5 2h-17A1.5 1.5 0 002 3.5v17A1.5 1.5 0 003.5 22h17a1.5 1.5 0 001.5-1.5v-17A1.5 1.5 0 0020.5 2zM8 19H5v-9h3zM6.5 8.25A1.75 1.75 0 118.3 6.5a1.78 1.78 0 01-1.8 1.75zM19 19h-3v-4.74c0-1.42-.6-1.93-1.38-1.93A1.74 1.74 0 0013 14.19a.66.66 0 000 .14V19h-3v-9h2.9v1.3a3.11 3.11 0 012.7-1.4c1.55 0 3.36.86 3.36 3.66z"/>
</svg>
</a> </li>
<li> <a href="https://github.com/gaultier">
<svg height="32" aria-hidden="true" viewBox="0 0 24 24" version="1.1" width="32" data-view-component="true" class="octicon octicon-mark-github v-align-middle">
<path d="M12.5.75C6.146.75 1 5.896 1 12.25c0 5.089 3.292 9.387 7.863 10.91.575.101.79-.244.79-.546 0-.273-.014-1.178-.014-2.142-2.889.532-3.636-.704-3.866-1.35-.13-.331-.69-1.352-1.18-1.625-.402-.216-.977-.748-.014-.762.906-.014 1.553.834 1.769 1.179 1.035 1.74 2.688 1.25 3.349.948.1-.747.402-1.25.733-1.538-2.559-.287-5.232-1.279-5.232-5.678 0-1.25.445-2.285 1.178-3.09-.115-.288-.517-1.467.115-3.048 0 0 .963-.302 3.163 1.179.92-.259 1.897-.388 2.875-.388.977 0 1.955.13 2.875.388 2.2-1.495 3.162-1.179 3.162-1.179.633 1.581.23 2.76.115 3.048.733.805 1.179 1.825 1.179 3.09 0 4.413-2.688 5.39-5.247 5.678.417.36.776 1.05.776 2.128 0 1.538-.014 2.774-.014 3.162 0 .302.216.662.79.547C20.709 21.637 24 17.324 24 12.25 24 5.896 18.854.75 12.5.75Z"/>
</svg>
</a> </li>
<li> <a href="https://hachyderm.io/@pg">
<svg width="75" height="79" viewBox="0 0 75 79" fill="none" xmlns="http://www.w3.org/2000/svg">
<path d="M73.8393 17.4898C72.6973 9.00165 65.2994 2.31235 56.5296 1.01614C55.05 0.797115 49.4441 0 36.4582 0H36.3612C23.3717 0 20.585 0.797115 19.1054 1.01614C10.5798 2.27644 2.79399 8.28712 0.904997 16.8758C-0.00358524 21.1056 -0.100549 25.7949 0.0682394 30.0965C0.308852 36.2651 0.355538 42.423 0.91577 48.5665C1.30307 52.6474 1.97872 56.6957 2.93763 60.6812C4.73325 68.042 12.0019 74.1676 19.1233 76.6666C26.7478 79.2728 34.9474 79.7055 42.8039 77.9162C43.6682 77.7151 44.5217 77.4817 45.3645 77.216C47.275 76.6092 49.5123 75.9305 51.1571 74.7385C51.1797 74.7217 51.1982 74.7001 51.2112 74.6753C51.2243 74.6504 51.2316 74.6229 51.2325 74.5948V68.6416C51.2321 68.6154 51.2259 68.5896 51.2142 68.5661C51.2025 68.5426 51.1858 68.522 51.1651 68.5058C51.1444 68.4896 51.1204 68.4783 51.0948 68.4726C51.0692 68.4669 51.0426 68.467 51.0171 68.4729C45.9835 69.675 40.8254 70.2777 35.6502 70.2682C26.7439 70.2682 24.3486 66.042 23.6626 64.2826C23.1113 62.762 22.7612 61.1759 22.6212 59.5646C22.6197 59.5375 22.6247 59.5105 22.6357 59.4857C22.6466 59.4609 22.6633 59.4391 22.6843 59.422C22.7053 59.4048 22.73 59.3929 22.7565 59.3871C22.783 59.3813 22.8104 59.3818 22.8367 59.3886C27.7864 60.5826 32.8604 61.1853 37.9522 61.1839C39.1768 61.1839 40.3978 61.1839 41.6224 61.1516C46.7435 61.008 52.1411 60.7459 57.1796 59.7621C57.3053 59.7369 57.431 59.7154 57.5387 59.6831C65.4861 58.157 73.0493 53.3672 73.8178 41.2381C73.8465 40.7606 73.9184 36.2364 73.9184 35.7409C73.9219 34.0569 74.4606 23.7949 73.8393 17.4898Z" fill="url(#paint0_linear_549_34)"/>
<path d="M61.2484 27.0263V48.114H52.8916V27.6475C52.8916 23.3388 51.096 21.1413 47.4437 21.1413C43.4287 21.1413 41.4177 23.7409 41.4177 28.8755V40.0782H33.1111V28.8755C33.1111 23.7409 31.0965 21.1413 27.0815 21.1413C23.4507 21.1413 21.6371 23.3388 21.6371 27.6475V48.114H13.2839V27.0263C13.2839 22.7176 14.384 19.2946 16.5843 16.7572C18.8539 14.2258 21.8311 12.926 25.5264 12.926C29.8036 12.926 33.0357 14.5705 35.1905 17.8559L37.2698 21.346L39.3527 17.8559C41.5074 14.5705 44.7395 12.926 49.0095 12.926C52.7013 12.926 55.6784 14.2258 57.9553 16.7572C60.1531 19.2922 61.2508 22.7152 61.2484 27.0263Z" fill="white"/>
<defs>
<linearGradient id="paint0_linear_549_34" x1="37.0692" y1="0" x2="37.0692" y2="79" gradientUnits="userSpaceOnUse">
<stop stop-color="#6364FF"/>
<stop offset="1" stop-color="#563ACC"/>
</linearGradient>
</defs>
</svg>
</a> </li>
<li> <a href="https://bsky.app/profile/pgaultier.bsky.social">
<svg fill="none" viewBox="0 0 64 57" width="32" style="width: 32px; height: 28.5px;"><path fill="#0085ff" d="M13.873 3.805C21.21 9.332 29.103 20.537 32 26.55v15.882c0-.338-.13.044-.41.867-1.512 4.456-7.418 21.847-20.923 7.944-7.111-7.32-3.819-14.64 9.125-16.85-7.405 1.264-15.73-.825-18.014-9.015C1.12 23.022 0 8.51 0 6.55 0-3.268 8.579-.182 13.873 3.805ZM50.127 3.805C42.79 9.332 34.897 20.537 32 26.55v15.882c0-.338.13.044.41.867 1.512 4.456 7.418 21.847 20.923 7.944 7.111-7.32 3.819-14.64-9.125-16.85 7.405 1.264 15.73-.825 18.014-9.015C62.88 23.022 64 8.51 64 6.55c0-9.818-8.578-6.732-13.873-2.745Z"/></svg>
</a> </li>
</ul>
</div>
<div id="search-matches" hidden>
</div>
<div id="pseudo-body">
<div class="article-prelude">
<p><a href="/blog"> ⏴ Back to all articles</a></p>
<p class="publication-date">Published on 2019-09-05</p>
</div>
<div class="article-title">
<h1>Getting started with Scheme by solving an Advent of Code 2018 challenge</h1>
<div class="tags"> <a href="/blog/articles-by-tag.html#lisp" class="tag">Lisp</a> <a href="/blog/articles-by-tag.html#scheme" class="tag">Scheme</a> <a href="/blog/articles-by-tag.html#c" class="tag">C</a> <a href="/blog/articles-by-tag.html#advent-of-code" class="tag">Advent of Code</a></div>
</div>
<strong>Table of contents</strong>
<ul>
<li>
<a href="#2580162644-the-problem">The problem</a>
</li>
<li>
<a href="#3898953298-working-with-the-repl-to-iteratively-close-in-on-a-solution">Working with the REPL to iteratively close in on a solution</a>
<ul>
<li>
<a href="#3881950255-a-small-detour-pattern-matching">A small detour: pattern matching</a>
</li>
<li>
<a href="#1617151895-using-pattern-matching-to-solve-our-problem">Using pattern matching to solve our problem</a>
</li>
</ul>
</li>
<li>
<a href="#405744868-the-final-solution">The final solution</a>
</li>
<li>
<a href="#3796851539-conclusion">Conclusion</a>
</li>
</ul>
<p><em>Discussions: <a href="https://old.reddit.com/r/scheme/comments/czyr3t/getting_started_with_scheme_by_solving_an_advent/">/r/scheme</a></em></p>
<p>I started learning <a href="https://en.wikipedia.org/wiki/Scheme_(programming_language)">Scheme</a> very recently. <a href="http://wiki.call-cc.org/">Chicken Scheme</a> is a wonderful small and
performant implementation of Scheme, a programming language in the family of
LISPs.
Since I learn by doing, let's solve the <a href="https://adventofcode.com/2018/day/5">Advent of Code 2018 day 5 challenge</a> with a tiny Scheme program.
I encourage you to check out <a href="https://adventofcode.com/2018/about">Advent of
Code</a> and try to solve the challenges yourself.</p>
<p>Many people have the feeling that LISPs are slow and cryptic with all those
parentheses. I hope to show that it is in fact very approachable, easy to work
with, and even fast to run!</p>
<p>I will not go through installing Chicken Scheme and learning the basics, because
it was <a href="http://blog.klipse.tech/scheme/2016/09/11/scheme-tutorial-1.html">already done better than I can</a>.</p>
<h2 id="2580162644-the-problem">
<a class="title" href="#2580162644-the-problem">The problem</a>
<a class="hash-anchor" href="#2580162644-the-problem" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h2>
<p>We have a string looking like this: <code>AabcdZZqQ</code> which represents a chain of
chemical units. Adjacent units of the same type (i.e letter) and opposite
polarity (i.e casing) react together and disappear.
It means we want to remove adjacent characters which are the same letter and have opposite casing, e.g
<code>Aa</code> and <code>qQ</code> disappear while <code>bc</code> and <code>ZZ</code> remain. Once we are finished, we have: <code>bcdZZ</code>.</p>
<p>The final output is the number of characters in the final string, i.e, <code>5</code>.</p>
<h2 id="3898953298-working-with-the-repl-to-iteratively-close-in-on-a-solution">
<a class="title" href="#3898953298-working-with-the-repl-to-iteratively-close-in-on-a-solution">Working with the REPL to iteratively close in on a solution</a>
<a class="hash-anchor" href="#3898953298-working-with-the-repl-to-iteratively-close-in-on-a-solution" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h2>
<p>First, let's define our input, which is a string:</p>
<pre><code class="language-scheme">(define input "aAbxXBctTCz")
</code></pre>
<p>Later, we will read our input string from a file, but for now it is simpler to
just hard-code it.</p>
<p>Most functions in Scheme are immutable, meaning they do not
modify their arguments, they instead return a new item which is slightly different.</p>
<p>We could work with strings, but it turns out it is simpler to work with lists
instead in our case. We do not want to keep track of indices, risking doing off-by-one mistakes.
Also, LISPs are good at handling lists (LISP stands for LISt Processor), and
we'll that we can use pattern matching to make the code very concise. I am not
aware of pattern matching capabilities on string, so let's use lists:</p>
<pre><code class="language-scheme">(string->list input)
</code></pre>
<p>Here, the
<code>string->list</code> function just returns a list of characters for a string (in other
languages it is usually named <code>split</code>).</p>
<p>Now, we need to detect if two characters are the same latter, with opposite casing.
Let's write a <code>char-opposite-casing?</code> function to do just that. It will take 2
arguments, the letters we are inspecting, and will return a boolean.
For now, let's just make it always return true:</p>
<pre><code class="language-scheme">(define (char-opposite-casing? a b) #\t)
</code></pre>
<p>We only deal with ASCII, so it is safe to compare ASCII codes to detect casing.</p>
<p>What is the ASCII code of <code>A</code>? Let's try it by using the function <code>char->integer</code>:</p>
<pre><code class="language-scheme">(char->integer #\A)
</code></pre>
<p>What about <code>a</code>?</p>
<pre><code class="language-scheme">(char->integer #\a)
</code></pre>
<p>So there is a difference of <code>32</code> between the same ASCII letter in lowercase and
uppercase. Peeking at <code>man ascii</code> in the terminal confirms this hunch for all
letters of the alphabet.</p>
<p>So, time to implement <code>char-opposite-casing?</code>:</p>
<pre><code class="language-scheme">(define (char-case-opposite-casing? a b)
(let* ((a-code (char->integer a))
(b-code (char->integer b))
(diff (- a-code b-code)))
(= (* 32 32) (* diff diff))))
</code></pre>
<p>Let's try it with <code>a</code> and <code>A</code>:</p>
<pre><code class="language-scheme">(char-case-opposite-casing? #\a #\A)
</code></pre>
<p>And flipped:</p>
<pre><code class="language-scheme">(char-case-opposite-casing? #\A #\a)
</code></pre>
<p>And <code>A</code> and <code>b</code>:</p>
<pre><code class="language-scheme">(char-case-opposite-casing? #\A #\b)
</code></pre>
<p><code>let*</code> is used to define local bindings which are only visible in this function.
It evaluates each binding in order which means we can define <code>diff</code> in terms of
<code>a</code> and <code>b</code> (contrary to <code>let</code>).</p>
<p>We could have done without it but it makes the function more readable.</p>
<p>The only hurdle is not caring
about the sign of the difference: if the difference is <code>32</code> or <code>-32</code>, it is the
same. We could compare the absolute value, but I (arbitrarily) chose to implement it without
branches, by comparing the squared values (which swallows the signs).</p>
<hr />
<p>Now let's work on the central problem: how to remove
characters in a list, in a functional, immutable way?</p>
<p>The idea is to write a recursive function taking two arguments: an accumulator
(let's call it <code>acc</code> from now on),
which will be eventually the end result, and the input list (<code>input</code>), from which we
gradually remove items until it is empty. We can view the first list as the work
we have done, and the second list as the work to do.</p>
<p>Let's first define the function. For now, it just returns the empty list:</p>
<pre><code class="language-scheme">(define (chem-react acc input)
'())
</code></pre>
<p>At first, the accumulator is the empty list, so we will always call our function like
this:</p>
<pre><code class="language-scheme">(chem-react '() (string->list input))
</code></pre>
<p>It is import to know that most list functions do not work on the empty list in
Chicken Scheme. For example, to get the first element of a list, we use the <code>car</code> function:</p>
<pre><code class="language-scheme">(define my-list (list 1 2 3))
;; Note that this doest **not** mutate `my-list`
(car my-list)
</code></pre>
<p>But it won't work on the empty list:</p>
<pre><code class="language-scheme">(define my-list '())
(car my-list)
</code></pre>
<p>So we need to treat the case of the empty list (both for the first and the
second argument) explicitly. We could do that by using lots of <code>if</code>, but it is
more readable and concise to use pattern matching.</p>
<h3 id="3881950255-a-small-detour-pattern-matching">
<a class="title" href="#3881950255-a-small-detour-pattern-matching">A small detour: pattern matching</a>
<a class="hash-anchor" href="#3881950255-a-small-detour-pattern-matching" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h3>
<p>Scheme has a minimalist core, so we do not get pattern matching out of
the box, but we can easily add it with the package <code>matchable</code>. Let's install
it in the terminal:</p>
<pre><code class="language-sh">$ chicken-install matchable
</code></pre>
<p>Now we can import it at the top of our code:</p>
<pre><code class="language-scheme">(import matchable)
;; At this point we can refer to any function in this module `matchable`.
;; No need to prefix them either with `matchable`.
</code></pre>
<p>Let's try to match the empty list in our function, and return (as an example) a
number, e.g <code>42</code>. We also want to match the case of both lists containing one
element, and returning the sum of those 2 elements:</p>
<pre><code class="language-scheme">(define (chem-react acc input)
(match (list acc input)
[(_ ()) 42]
[((a) (b)) (+ a b)]))
(chem-react '() '()) ;; => 42
(chem-react (list 2) (list 3)) ;; => 5
</code></pre>
<p>A few interesting things here: <code>_</code> allows us to match anything, so the first
case is equivalent to checking if the second list is
empty. Additionally, we can bind variables to our patterns: we do that in the
second case, binding the first element of the first list to <code>a</code>, and the fist
element of the second list to <code>b</code>, and summing the two.</p>
<p>Note that not all possible cases are covered here, and we will get a (runtime)
error if we trigger one of them, for example with a list containing several numbers:</p>
<pre><code class="language-scheme">(chem-react (list 1 2) (list 3)) ;; => Error: (match) "no matching pattern": ()
</code></pre>
<p>Let's go ahead and match the case of a list of one or more elements (<code>(a . arest)</code>) to avoid that:</p>
<pre><code class="language-scheme">(define (chem-react acc input)
(match (list acc input)
[(_ ()) 42]
[((a) (b)) (+ a b)]
[((a . arest) (b . brest)) (* a b)]))
(chem-react (list 2 3) (list 4)) ;; => 8
</code></pre>
<p>Here we choose to (arbitrarily) return the product of the first elements of both
list, to show that pattern matching is also a way to do destructuring.</p>
<h3 id="1617151895-using-pattern-matching-to-solve-our-problem">
<a class="title" href="#1617151895-using-pattern-matching-to-solve-our-problem">Using pattern matching to solve our problem</a>
<a class="hash-anchor" href="#1617151895-using-pattern-matching-to-solve-our-problem" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h3>
<p>If the second list (the input) is empty, it means we are
finished, so we return the first list (<code>acc</code>):</p>
<pre><code class="language-scheme">(define (chem-react acc input)
(match (list acc input)
[(_ ()) acc]))
</code></pre>
<p>Our recursion will work as follows: we look at the first element of the second
list (<code>input</code>, which is the work to do), let's call it <code>b</code>, and the first element of the first
list (<code>acc</code>, the work done), let's call it <code>a</code>.</p>
<p>If <code>a</code> and <code>b</code> are the same letter of opposite casing, we 'drop' the two. Otherwise, we
add <code>b</code> to the first list, and 'continue'. 'drop' and 'continue' are put in
quotes because that is vocabulary from imperative languages such as C; we'll see
in a minute how we implement it in a functional way.</p>
<p>If the first list is empty, this is our starting case: the only thing we can do
is mark <code>b</code> as 'processed', i.e add it to the first list, and call ourselves
with the remainder of <code>input</code>. Indeed, we can only work with two characters, so
if we only have one, we cannot do much.</p>
<p>It's time to learn about a new function: <code>cons</code>. <code>cons</code> just adds an item to a list, and
returns the new list with the added item:</p>
<pre><code class="language-scheme">(define my-list (list 2 3))
;; Note: `my-list` is **not** modified
(cons 1 my-list)
</code></pre>
<p>We can now use <code>cons</code> to implement the new case:</p>
<pre><code class="language-scheme">(define (chem-react acc input)
(match (list acc input)
[(_ ()) acc]
[(() (b . brest)) (chem-react (cons b acc) brest)]))
(chem-react '() '(#\A)) ;; => (#\A)
</code></pre>
<p>This new pattern is required for the recursion to
work, but it also covers the trivial case of an input string of only one character.</p>
<p>Now, let's treat the main case: we have at least an element <code>a</code> in <code>acc</code> and at
least an element <code>b</code> in <code>input</code>. If they are the same letters of opposite casing, we
call ourselves with the remainder of <code>acc</code> and the remainder of <code>input</code>, which
is equivalent to 'drop' <code>a</code> and <code>b</code>. Otherwise, we add <code>b</code> to <code>acc</code>, and we call
ourselves with the remainder of <code>input</code>, which is the equivalent of 'continuing':</p>
<pre><code class="language-scheme">(define (chem-react acc input)
(match (list acc input)
[(_ ()) acc]
[(() (b . brest)) (chem-react (cons b acc) brest)]
[((a . arest) (b . brest)) (if (char-case-opposite-casing? a b)
(chem-react arest brest)
(chem-react (cons b acc) brest))]))
(chem-react '() (list #\A #\a #\b)) ;; => (#\b)
(chem-react '() (string->list "aAbxXBctTCz")) ;; => (#\z)
</code></pre>
<p>But wait a minute...Doesn't it look familiar? Yes, what we are doing here is a
fold (sometimes called reduce)!</p>
<p>Let's replace our custom recursion by <code>fold</code>. <code>chem-react</code> becomes the reduction
function. It becomes simpler because <code>fold</code> will not call it on the empty list,
so we only need to patter match <code>acc</code> (which is the empty list at the beginning):</p>
<pre><code class="language-scheme">(define (chem-react acc x)
(match acc
[() (cons x acc)]
[(a . arest) (if (char-case-opposite-casing? a x)
arest
(cons x acc))]))
(foldl chem-react '() input) ;; => (#\z)
</code></pre>
<p>My experience writing code in a LISP is that I usually find a solution that is
relatively big, and I start replacing parts of it with standard functions such
as <code>fold</code> and it ends up very small.</p>
<blockquote>
<p>How do I read the input from a file?</p>
</blockquote>
<p>It's quite simple: we use the modules <code>chicken.file.posix</code> and <code>chicken.io</code>:</p>
<pre><code class="language-scheme">(import chicken.file.posix
chicken.io)
(read-line (open-input-file "/Users/pgaultier/Downloads/aoc5.txt")) ;; => "a big string..."
</code></pre>
<h2 id="405744868-the-final-solution">
<a class="title" href="#405744868-the-final-solution">The final solution</a>
<a class="hash-anchor" href="#405744868-the-final-solution" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h2>
<p>Here I use the package <code>clojurian</code> (<code>chicken-install clojurian</code>) to have access
to the <code>->></code> macro which makes code more readable. It works like the pipe in the
shell. Instead of writing:</p>
<pre><code class="language-scheme">(foo (bar "foo" (baz 1 2)))
</code></pre>
<p>We write:</p>
<pre><code class="language-scheme">(->> (baz 1 2)
(bar "foo")
(foo))
</code></pre>
<p>The macro reorders the functions calls to make it flat and avoid nesting.
It is not strictly required, but I like that my code looks like a
pipeline of data transformations.</p>
<p>The final code:</p>
<pre><code class="language-scheme">(import matchable
clojurian.syntax
chicken.file.posix
chicken.io)
(define (char-case-opposite-casing? a b)
(let* ((a-code (char->integer a))
(b-code (char->integer b))
(diff (- a-code b-code)))
(= (* 32 32) (* diff diff))))
(define (chem-react acc x)
(match acc
[() (cons x acc)]
[(a . arest) (if (char-case-opposite-casing? a x)
arest
(cons x acc))]))
(->> (open-input-file "/Users/pgaultier/Downloads/aoc5.txt")
(read-line)
(string->list)
(foldl chem-react '())
(length)
(print))
</code></pre>
<blockquote>
<p>But we will get a stack overflow on a big input!</p>
</blockquote>
<p>Scheme has a nice requirement for all implementations: they must implement
tail-call optimization, which is to say that the compiler can transform our function into an
equivalent for-loop. So we won't get a stack overflow, and it will be quite
efficient in terms of memory and time.</p>
<blockquote>
<p>But we are making thousands of copies, it will be slow as hell!</p>
</blockquote>
<p>Let's benchmark it on the real input (50 000 characters), with <code>-O3</code> to enable optimizations:</p>
<p><em>Note 1: The real output of the program is not shown to avoid spoiling the final result</em></p>
<p><em>Note 2: This is a simplistic way to do benchmarking. A more correct way would
be: warming up the file cache, making many runs, averaging the results, etc.
I did exactly that and it did not change the results in a significant manner.</em></p>
<pre><code class="language-sh">$ csc aoc5.scm -o aoc5 -O3 && time ./aoc5
./aoc5 0.01s user 0.00s system 82% cpu 0.021 total
</code></pre>
<p>It takes 21 milliseconds. Not too bad for a garbage collected, functional,
immutable program.</p>
<p>Here is a hand-written C version which only does one allocation and removes
letters in place:</p>
<pre><code class="language-c">#include <errno.h>
#include <fcntl.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <unistd.h>
int main() {
int fd = open("/home/pg/Downloads/aoc2020_5.txt", O_RDONLY);
if (fd == -1)
return errno;
struct stat st = {0};
if (stat("/home/pg/Downloads/aoc2020_5.txt", &st) == -1)
return errno;
int64_t input_len = st.st_size;
char *const input = calloc(input_len, 1);
if (read(fd, input, input_len) != input_len)
return errno;
while (input[input_len - 1] == '\n' || input[input_len - 1] == ' ')
input_len--;
int64_t i = 0;
while (i < input_len) {
if (abs(input[i] - input[i + 1]) == 32) {
memmove(input + i, input + i + 2, input_len - i - 2);
input_len -= 2;
i = i > 0 ? i - 1 : 0;
} else
i++;
}
printf("`%zu`\n", input_len);
}
</code></pre>
<p>Let's benchmark it on the same input:</p>
<pre><code class="language-sh">$ cc -std=c99 -O3 -Weverything aoc5.c -march=native && time ./a.out
./a.out 0.01s user 0.00s system 86% cpu 0.012 total
</code></pre>
<p>It took 12 milliseconds. So the scheme version is very close, and takes an
acceptable amount of time.</p>
<blockquote>
<p>Can't we use strings and not lists?</p>
</blockquote>
<p>Yes, of course. However we need to be careful about how strings are implemented
and what we we do with those. Most runtimes (e.g the JVM) use immutable strings,
meaning we could end up allocating thousands of big strings, and being quite slow.</p>
<h2 id="3796851539-conclusion">
<a class="title" href="#3796851539-conclusion">Conclusion</a>
<a class="hash-anchor" href="#3796851539-conclusion" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h2>
<p>That's it, we solved the fifth Advent of Code challenge in Scheme. The solution
is under 30 lines of code, is (hopefully) simple and readable, and has a
performance close to C, while having memory safety (I had several segfaults
while doing the C version).</p>
<p>But more than that, I think the real value in LISPs is
interactive programming, instead of the classical write-compile-execute-repeat,
which is much more time consuming. It is really important to get feedback as
early as possible, and LISPs give us that.</p>
<p>I hope it gave you a glance at what Scheme can do, and stay tuned for more blog
posts about programming. I intend to post more solutions to other coding
challenges, solved with a variety of programming languages.</p>
<script src="https://unpkg.com/@highlightjs/[email protected]/languages/scheme.min.js"></script>
<p><a href="/blog"> ⏴ Back to all articles</a></p>
<blockquote id="donate">
<p>If you enjoy what you're reading, you want to support me, and can afford it: <a href="https://paypal.me/philigaultier?country.x=DE&locale.x=en_US">Support me</a>. That allows me to write more cool articles!</p>
</blockquote>
<blockquote>
<p>
This blog is <a href="https://github.com/gaultier/blog">open-source</a>!
If you find a problem, please open a Github issue.
The content of this blog as well as the code snippets are under the <a href="https://en.wikipedia.org/wiki/BSD_licenses#3-clause_license_(%22BSD_License_2.0%22,_%22Revised_BSD_License%22,_%22New_BSD_License%22,_or_%22Modified_BSD_License%22)">BSD-3 License</a> which I also usually use for all my personal projects. It's basically free for every use but you have to mention me as the original author.
</p>
</blockquote>
</div>
</body>
</html>