about summary refs log tree commit diff homepage
path: root/blog/advent.md
blob: 1d02f8a373f83836a20f12c68c4d204d4432833b (plain) (blame)
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
+++
rss = "Doing Advent of Code in a new programming language each day"
date = Date(2022, 12, 26)
tags = ["fun", "exp"]
+++

# Advent of Programming Languages

Earlier this year I enrolled in a master's programme[^master] at [UNIST]
and joined the Programming Languages and Software Engineering lab (PLaSE) as
a student researcher.  The stipend covers the school fees and living expenses,
and I'm given *an* academic freedom to choose what to work on and take risks.
I will review the life here in detail in another post, but (SPOILER ALERT!)
overall I'm quite content with it.

That being said, PLaSE is new and small, we only do research
on software engineering and don't do its name justice.  Because of that,
in the first year here I decided to do each day of [Advent of Code][^2021]
in a language I'd never used in competitive programming (CP) before.

![Pitbull holding the globe, captioned: Mr. Worldwide](/assets/mr-worldwide.jpg)

Here was my blacklist going in, chronologically: Pascal, Python,
Scheme, C, C++, Common Lisp, Lua, Raku, Go, Rust and Zig.  I am only
proficient in over half of the listed languages, but dura lex, sed lex,
I'd already had my CP first time with the rest.

To try any new language, all I have to do is dropping into an ephemeral shell
with its implementation using `nix-shell` or `guix shell` without the fear
of bloating up my systems.  I'm running [NixOS on my laptop](/blog/butter)
with [nixpkgs] being one of the largest downstream repositories, including
everything but the kitchen sink.  On the work desktop, I installed Guix System
which has a decent [set of packages][gnu] and [nix service][gnix]
in case something is missing.  Every update, I run [garbage] [collection]
and get rid of all unnecessary software, i.e. those not [declared][guix]
[in my config][nix].

## Day One

The first day should have been the warm up so I challenged myself
with using POSIX utilities.  This is a bit irony though as the majority
of my time spent outside of [*the* editor][Vim] or a web browser
is inside a ([Bourn-again][Born Again]) shell.

The [problem][p01] was indeed simple, involving only [finding the maxima
among the sums of newline-separated numbers][s01].  I used [sed]\(1p)
to turn the input into [dc]\(1) eypressions, and [sort]\(1p) and [tail]\(1p)
for picking the largest sum.  Probably the most interesting part
was that the summation was reusable to [grade an assignment] for a course
I was a teaching assistant for.

## Day Two

The [second problem][p02] didn't ramp up much in difficulty.
It only called for some rather [simple arithmetic][s02],
and the input format's regularity convinced me to finally give [Hare] a try.

For just a taste, Hare is boring in a good way.  I was excited
for the tagged union of [error which can include and propagate
any debugging information][error], but unfortunately it wasn't needed
for programs of such complexity (nor that errors are ever handled in CP).
I'm looking forward to a chance to write more Hare in the future.

## Day Three

The [task for day 3][p03] was literally day $1 + 2$ in scope.
I went for another *better C* that is [Nim].  My first impression with it
wasn't positive: Nim insists on considering each source file as a module
and does not allow hyphens in identifier name, so [filenames mustn't have
any hyphen][hyphen] either.  This had led me to piping the source code
to `nim c -` and executing `~/.cache/nim/stdinfile_d/stdinfile` to keep
my solution naming convention.  `nim r -` wouldn't have worked either
since the convention also consists of reading the input from stdin.

On the bright side, [uniform function call syntax][UFCS], identifier
case-(and underscore-)insensitivity and optional parentheses allowed me
to [dodge parentheses in calls and camelCasing altogether][s03].
Although I *love* Lisp and don't have any problem with brackets,
I think their placement in ALGOL style hurts the readability
of nested calls and [camelCase is just objectively bad][camelCase],
pun[^obj] unintended.

## Day Four

The [forth problem][p04] wasn't any harder, only requiring
[simple logic operations and summation][s04].  To save time,
I opted for [Julia], which I was kinda sorta familiar with
in building this site (at the time this is published at least).
Like Nim, it has higher-order functions and a (reference) compiler
capable of producing fast binaries.

## Day Five

The [next day's task][p05] was finally a breath of fresh air
with [matrix parsing and LIFO (literal) stacks][s05].  It begged
for a regular expression parser,[^re] hence I mined a tiny bit of Ruby
for the task.  Ruby had been designed to be an object-oriented Perl,
and expectedly it feels very similar to Raku.  To an extend, I was also
able to avoid ALGOL-style call do quite a [Lisp impression].

When I was looking for a second language to learn after the peak
of my CP *career* in middle school, I was choosing between those
with garbage-collection that are most popularly used in [free software]
at the time, namely Perl, Python and Ruby.  Perl was ruled out due to my fear
of [sigils] and I picked up Python as I didn't want to be a [weeaboo].
Sometimes I wonder how my side projects would have turned out to be
had I chosen differently.

## Day Six

The [sixth problem][p06] essentially asked for maintaining a finite queue
of English letters until it is distinct.  The most efficient way to do this
is employing bit shifting for the FIFO and a bit set for the letters.
[I implemented that][s06] literally in the [Better C] subset of [D].

Although the language is around my age and influenced the big names
like modern C++, Swift and Zig,[^cmp] its documentation is pretty underwhelming
and inconsistent.  For instance, the 128-bit integer type `cent` is documented
as a [basic data type], however it only exists in the [core.int128] library
with more cumbersome usage (and doesn't work with `dmd -betterC`).

Like with Nim, D compilers also don't allow hyphens in source filenames,
so I had to pipe the code to `dmd -of=a.out -` (the executable name
would be randomized otherwise).

## Day Seven

On the first [Wednesday] of the month of celebration, the [problem][p07]
was parsing `cd` and `ls`-like invocation and output to reconstruct
a directory tree and do, uh, tree stuff.  [Janet]'s [PEG module]
was much more [delightful][s07] for parsing than regular expression
on steroids like Raku's [grammar].

Writing imperative S-expressions felt dirty, though it's IMHO
a quite better take than Lua, understandably as it was originally
a redesign of [Fennel].

## Day Eight

The [eighth problem][p08] could be efficiently solved via dynamic programming
on multidimensional arrays so I [used][s08] Fortran for array programming.
There's not much to say other than that it werkt and, ah yea, dynamic allocation
didn't seem worth the effort so I ended up hardcoding the sizes.

## Day Nine

The [ninth task][p09] was about sparse matrix transformation.
Naturally I used hash table in Tcl for this purpose
and the [solution][s09] was straightforward enough.
I am planning on extending a video game's level configuration
to be programmable and the top contenders are now Lua/Fennel,
Janet and Tcl.  No idea when I'll get to it, but I'mma keep ya posted.

## Day Ten

On [day 10][p10], I needed to build a less-than-basic[^egg] calculator.
I thought using AWK would spice things up a bit, but it actually simplified
the [solution][s10].  Instead of having to read and parse each operation,
the script is executed for each input line, even allowing interleaving
matching.  Therefore, the behavior specification could be followed closely
without any significant effort on adapting the logic for the language.

I used to think of AWK as just a more verbose sed(1).
I was wrong and am glad that I was.  I guess AWK can come in
pretty handy for similar real-world usages, such as log processing
or moderately complex transformation of textual data.

## May Day

[Oops!… I did it again.][^2021]  If you thought because I published this
right after Christmas it must be a complete advent journal, I have played you
for absolute fools!  The later problems were increasingly parsing heavy,
and while I still had languages I wanted to try, none left was designed
for text processing.  I was also busy in meatspace at the time thus I couldn't
find the time to write byte-level parsers in languages I didn't know.

I didn't try really hard nor got really far, but [in the end]
maybe the [real treasure] was the experiences I had along the way.
I suppose the [contact hypothesis] *might* be true, at least
in this context[;] my prejudice against many languages had been
cleared away even after surface-level interactions.  You should probably
also give it a try, who knows, it could be much [gay]er than you'd expect!

[^master]: No, I have not been given any slave.
[^2021]: I know, last year I already quit citing how janky later problems were.
[^obj]: camelCase was popularized by mainstream object oriented languages.
[^re]: Not really, reading byte-by-byte would also work, just less cool.
[^cmp]: I feel underachieved now.
[^egg]: No eggs were harmed in the making of the solution.

[UNIST]: https://unist.ac.kr
[Advent of Code]: https://adventofcode.com
[nixpkgs]: https://search.nixos.org/packages
[gnu]: https://packages.guix.gnu.org
[gnix]: https://trong.loang.net/~cnx/dotfiles/tree/guix/system.scm?id=b53f96565b8c#n51
[garbage]: https://nixos.org/manual/nix/stable/command-ref/nix-collect-garbage.html
[collection]: https://guix.gnu.org/manual/en/html_node/Invoking-guix-gc.html
[guix]: https://trong.loang.net/~cnx/dotfiles/tree/guix
[nix]: https://trong.loang.net/~cnx/dotfiles/tree/nix

[Vim]: https://www.vim.org
[Born Again]: https://www.youtube.com/watch?v=k5E6CExu204

[p01]: https://adventofcode.com/2022/day/1
[s01]: https://trong.loang.net/~cnx/cp/commit/ff0bb53c15dd
[sed]: https://pubs.opengroup.org/onlinepubs/9699919799/utilities/sed.html
[dc]: https://linux.die.net/man/1/dc
[sort]: https://pubs.opengroup.org/onlinepubs/9699919799/utilities/sort.html
[tail]: https://pubs.opengroup.org/onlinepubs/9699919799/utilities/tail.html
[grade an assignment]: https://larkspur.one/notice/AQALVP69wAiotsVmgC

[p02]: https://adventofcode.com/2022/day/2
[s02]: https://trong.loang.net/~cnx/cp/commit/ada3a69b15ff
[Hare]: https://harelang.org
[error]: https://harelang.org/tutorials/introduction/#defining-new-error-types

[p03]: https://adventofcode.com/2022/day/3
[s03]: https://trong.loang.net/~cnx/cp/commit/eeb9a45346a8
[Nim]: https://nim-lang.org
[hyphen]: https://forum.nim-lang.org/t/5024
[UFCS]: https://en.wikipedia.org/wiki/Uniform_Function_Call_Syntax
[camelCase]: http://www.cs.kent.edu/~jmaletic/papers/ICPC2010-CamelCaseUnderScoreClouds.pdf

[p04]: https://adventofcode.com/2022/day/4
[s04]: https://trong.loang.net/~cnx/cp/commit/8941f621840f
[Julia]: https://julialang.org

[p05]: https://adventofcode.com/2022/day/5
[s05]: https://trong.loang.net/~cnx/cp/commit/aa7616140a8b
[Lisp impression]: https://www.codesections.com/blog/raku-lisp-impression
[free software]: https://www.gnu.org/philosophy/free-sw.html
[sigils]: https://raku-advent.blog/2022/12/20/sigils
[weeaboo]: https://en.wikipedia.org/wiki/Japanophilia#21st_century

[p06]: https://adventofcode.com/2022/day/6
[s06]: https://trong.loang.net/~cnx/cp/commit/f82f0b1a08f1
[Better C]: https://dlang.org/spec/betterc.html
[D]: https://dlang.org
[basic data type]: https://dlang.org/spec/type.html#basic-data-types
[core.int128]: https://dlang.org/phobos/core_int128.html

[Wednesday]: https://vine.co/v/iM0HnpBebd0
[p07]: https://adventofcode.com/2022/day/7
[Janet]: https://janet-lang.org
[PEG module]: https://janet-lang.org/docs/peg.html
[s07]: https://trong.loang.net/~cnx/cp/commit/38d8920c7d7c
[grammar]: https://docs.raku.org/language/grammars
[Fennel]: https://fennel-lang.org

[p08]: https://adventofcode.com/2022/day/8
[s08]: https://trong.loang.net/~cnx/cp/commit/f8b0528d933f

[p09]: https://adventofcode.com/2022/day/9
[s09]: https://trong.loang.net/~cnx/cp/commit/cde44cdda55d

[p10]: https://adventofcode.com/2022/day/10
[s10]: https://trong.loang.net/~cnx/cp/commit/5e4395eab495

[Oops!… I did it again.]: https://en.wikipedia.org/wiki/Oops!..._I_Did_It_Again_(album)
[in the end]: https://www.youtube.com/watch?v=eVTXPUF4Oz4
[real treasure]: https://www.youtube.com/watch?v=l7r-R61W1DQ
[contact hypothesis]: https://en.wikipedia.org/wiki/Contact_hypothesis
[;]: https://www.youtube.com/watch?v=M94ii6MVilw
[gay]: https://en.wiktionary.org/wiki/gay#Middle_English