Skip to content
This repository has been archived by the owner on Jan 6, 2024. It is now read-only.
/ aoc2021 Public archive

Solutions to & Learnings from Advent of Code 2021

adventofcode.com/2021

License

BSD-3-Clause license
7 stars 0 forks Branches Tags Activity
Star
Notifications You must be signed in to change notification settings

sroccaserra/aoc2021

BranchesTags

Repository files navigation

Note: deprecated.

See instead:

aoc2021

In this repository, I solved all 25 days for Advent of Code 2021, using mostly Python and Haskell. This was both fun and really hard for me at the end. I had to take a small break on day 24. I got back on time for day 25 and I'm really proud of that. But there is more: then, for what it's worth, I solved the first two days in 22 different languages. And took some notes along the way.

See also:

Contents:

Two problems, 22 languages

For what it's worth, I solved the first two days in 22 different languages:

  • APL
  • BQN
  • C++
  • Common Lisp
  • Elixir
  • Erlang
  • GNU Forth
  • GNU Smalltalk
  • Go
  • Haskell
  • J
  • Java
  • Kotlin
  • Lua
  • Node.js (JavaScript)
  • Python 3
  • Ruby
  • Rust
  • Scheme (Lisp)
  • Uiua
  • Uxntal
  • x86-64 Assembly (with some low level Linux IO syscalls)

Some languages I know very well, some I had to learn from scratch. So please tell me if I did it totally wrong in your favorite language. I enjoyed them all though, and the first two days propose very simple problems so it should be at least barely correct.

You can find theses solutions in the src directory, in 01.* and 02.* files. The *.in files are my input files for the problems. Please note that this is not a good naming convention for anything other than Advent of Code.

What is interesting about these first two days is that they invite you to learn how to:

  • Read some inputs
  • Process input lines with simple parsing and a simple computation
  • Create and pass around a small ad hoc data structure (for day two)
  • Print some output
  • Move the common code for generic stuff in a common file
  • Require the common file

All this forms a good starting point to learn any programming language I guess? If you know how to do that, you have everything you need to start writing useful stuff that interacts with input data, maybe comming from other programs, and pass your output to yet other programs. You also have everything you need to start automating some tests for example.

Part of the intention here is this. If you are curious about programming language X or Y, find any possible reason to write some code in it, some code where you can check the correctness. Simple Advent of Code problems are one way, there are others. A repl, or practicing TDD are other examples.

Below I tried to document some of my learnings. These are mostly notes for myself, and not all languages are documented. But I hope you can find something to enjoy here too. Cheers!

Learnings

Algorithms

Search

Linux

  • On Linux, /usr/bin/time -v ... gives the memory usage (see Maximum resident set size).

Scheme

References

Lua

Lua is a simple and very small language, which is a nice feature because it is one of the rare languages where you can read the entire doc in a reasonable time.

The downside is that the standard library is limited, there is no tuples, no sets, no class. We have to use what is provided in a creative way to emulate those.

So in a way, it can be fun to try and be creative to "use what we have" and "do what we can".

What we have is a very versatile "table" data structure, that can either be used as a 1-based array or as a hash table, and functions. And while Lua also provides "metatables", that can be used to emulate prototype-based inheritance, I found it not really useful for Advent of Code puzzles, maybe I didn't look hard enough.

Another problem is that not unlike JavaScript, Lua does not check function arity, nil value bugs can sneak in very easily deep into a program. So we have to be extra careful.

  • Lua has no set of tuples and no set, but it can be faked with tables, for exemple:
t = {}
function add(t,x,y) if not t[y] then t[y] = {} end t[y][x] = true end
function has(t,x,y) if not t[y] then t[y] = {} end return t[y][x] end
  • Lua cannot use tables or tuples as keys, but you can usually easily generate a key with string.format(), for example:
local key = string.format("%d %d %d %d", p1_pos, p1_score, p2_pos, p2_score)

  • Use t[y][x] = {} to store data based on coordinates, like adjacency lists.

  • Use table.insert(t, x) and table.remove(t) to implement an array-based stack with tables.

  • Use table.insert(t, 1, x) and table.remove(t, 1) for small queues (up to some hundred elements).

Python

Haskell

  • Data.Set can be used as a priority queue (insert and deleteFindMin are O(log n)) (see day 15).
  • flip (,) <$> [y-1..y+1] <*> [x-1..x+1] generates [(x-1, y-1), (x, y-1), (x+1, y-1) ...].
  • We can pattern guard on monads with the <- operator : validate xs (y:ys) | Just x <- lookup y brackets = validate (x:xs) ys.
  • Beware, if you want to update a count with -n Map.insertWith (-) will probably reverse the arguments. Use flip (-) or (+) k (-n).

Uxn

  • Take great care with relative addresses. #00 ,&a STR works but ,&a #00 SWP STR doesn't, because in the second case the relative address is measured from the wrong point.
  • Use STH and STHr to move values to and from the return stack
  • Use LITr to push values like #00 to the return stack

References

Resources:

Solutions:

8 bit references:

Go

References

Solutions:

Tools:

Forth

Example of defining an unnamed word and executing it:

:noname
  3 ;
.s
<1> 140266528584968  ok
execute
ok
.s
<1> 3  ok

References

C++

References

Solutions:

Rust

  • The iterator returned by into_iter may yield any of T, &T or &mut T, depending on the context.
  • The iterator returned by iter will yield &T, by convention.
  • The iterator returned by iter_mut will yield &mut T, by convention.

The argument to a for loop must implement IntoIterator. There are two different implementations of IntoIterator for Vec and &Vec. You get values for Vec and references for &Vec because that's how the iterators are defined.

impl<T> IntoIterator for Vec<T> {
    type Item = T;
    type IntoIter = IntoIter<T>
}

impl<'a, T> IntoIterator for &'a Vec<T> {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>
}

When you use a_vector inside a for..in loop, Rust will call the IntoIterator::into_iter trait method of the Vec, which takes ownership of self. Therefore you cannot use a_vector afterwards.

use std::iter::IntoIterator;

// these are equivalent
for i in a_vector { /* ... */ }
for i in IntoIterator::into_iter(a_vector) { /* ... */ }

The index operator, on the other hands, calls the Index::index trait method of the Vec, which takes self by reference. Additionally, it automatically dereferences the value, so that if the items inside the vector implement Copy, they will be copied out of the vector instead of borrowed (you need to explicitly borrow if you want a reference):

use std::ops::Index;

// these are equivalent
let x = a_vector[0];
let x = *Index::index(&a_vector, 0);

// these are equivalent
let x = &a_vector[0];
let x = Index::index(&a_vector, 0);

References

Standard doc links:

Other refs & tools:

Interesting SO questions:

GNU Smalltalk

Apparently, GNU Smalltalk classes don't call initialize methods in new (?)

The #inspect message is useful in GNU Smalltalk too, it prints the receiver's value to stdout.

Two ways to send a dynamic message to an object. Let aSelector, a symbol of the message to be sent, and anObjet, the receiver:

anObject perform: aSelector with: aValue.

or:

aMessage := Message selector: aSelector argument: aValue.
aMessage sendTo: anObject.

For example, if anObject was aSubmarine, and the selector was #forward:, aSubmarine perform: #forward: with: aValue would be equivalent to aSubmarine forward: aValue.

References

Kotlin

References

Ruby

References

x86-64 Assembly

This runs under Linux only. Please note that this is mostly ⌨️ 🐈️ code, I'm learning basics along the way.

See also: https://github.com/sroccaserra/learning-x64-assembly

Register mode: %rdi is the contents of register %rdi.

Immediate mode: $0x1234 is the value 0x1234. $localvar is the value of localvar (the address represented by the symbol localvar).

Direct Memory mode: 0x1234 is the value at address 0x1234. localvar is the value at address localvar.

Register Indirect mode: (%rbx) is the value at the address contained in %rbx.

When built with as or with gcc -nostdlib, command line arguments are passed on the stack. The number of command line arguments is at (%rsp). The address of the name of the executable is at 8(%rsp). The adress of the first command line argument is at 16(%rsp), etc.

When built with the stdlib (gcc default), the C runtime provides the _start entry point, so in our assembly code we would define a main function as entry point instead of _start.

When built with the stdlib, the command line arguments are not passed on the stack. Our main function is called with argc in %rdi, and a char** in %rsi (beware the number of indirections here, it's different than previously).

To generate position-independant code, we can use localvar(%rip) or globalvar@GOTPCREL(%rip) instead of localvar or globalvar. GOT = Global Offset Table. Instructions like movq $mystring, %rsi can become leaq mystring(%rip), %rsi.

Use objdump -SD build/01.o to explore generated code.

Using gdb:

  • Use tui reg general to show registers window
  • Use layout asm to show disassembly window
  • Use gdb --args build/01_s src/01.in to pass arguments to the debugged executable
  • Use br *_start to add a break to the start of the programm
  • Use start to start the programm
  • Use disass to see the assembly code listing
  • Use ni to execute the current instruction
  • Use print/x $rax or p/x $rax to print the contents of %rax in hex
  • Use print/x *0x7fffffffda9b to print contents of a memory address
  • Use x $rax to explore the memory pointed by %rax
  • Use x <address> to explore the contents of the address
  • Use x/4gx <address> to see the contents of the address as hex, four 8 bytes chunks
  • Use x/s <address> to see the contents of the address as null terminated string
  • Use x *<address> to explore the contents pointed to by address
(gdb) p/x $rsp
$2 = 0x7fffffffd570
(gdb) x/xg $rsp
0x7fffffffd570: 0x00007fffffffd594
(gdb) x/xg *(int**)$rsp
0x7fffffffd594: 0x0040200039333131

References

Sites:

Tools:

SO questions:

Common Lisp

  • The reader upcases symbols, so 'forward becomes FORWARD. The #'intern function does not upcase its value, so (intern "forward") becomes |forward|.
  • Inside a symbol, |-enclosed parts preserve their case. 'what|? wow |this| also works|? is |WHAT? wow THIS also works?|
  • Symbols prefixed by : are symbols from the KEYWORD package. (intern "forward" "KEYWORD") is :|forward|

References:

Tools & Libs:

Books:

Erlang

  • To pass a function defined in an escript to another function in the same script, I had to add -mode(compile).

References:

J

Notes for self, how I installed J on Linux:

How I installed the 'plot' addon:

$ sudo jconsole  # sudo is required if j is installed to /usr
   getscripts_j_ 'plot'  NB. Gives the category/module corresponding to 'plot'
   load 'pacman'  NB. Probably not required
   install 'graphics/plot'
   ...

If a verb has a noun on its left, it is executed as a dyadic verb with a left and right operand. If the verb does not have a noun on its left, it is executed as monadic with just a right operand. You must know the part of speech of the names in a sentence to understand the execution order. In the sentence result =. name1 verb2 5 you must know whether name1 is a verb, in which case verb2 is executed monadically and the result is name1(verb2(5)), or name1 is a noun, in which case verb2 is dyadic and the result is (name1 verb2 5).

J uses the names x, y, u, v, m, and n to represent arguments to verbs and other entities. You should avoid using these names for other purposes.

Convention: pass '' to a monad that doesn't need any argument.

You can ask the interpreter how it splits a line into words by using monad ;: : ;: '2 + 1 2 3'

For any verb, including user-written verbs, you can ask the interpreter the rank by typing verbname b. 0 : #: b. 0

Plotting values:

load 'plot'
plot numbers

x f&g y ↔ (g x) f (g y). For example, x %&! y is the quotient of the 'factorials' of x and y.

Verb trains as tacit functions: read them from the right, three at a time. Three verbs form a fork and become a single verb. Then repeat: read from the right, three at a time (Sierpinsky triangle?)

2: is a verb that always returns 2. 2: 4 returns 2. Usefull to introduce constants in verb trains: (#-2:) is a fork that returns the length of a list minus 2. Read it as (# - 2:).

": as a monad (Format) can turn a number into a string. datatype 2 returns integer, datatype ": 2 returns integral.

The fork where the first function is the identity, ] f g would be the S combinator. In J notation and rules, (] f g) y is y f (g y). The S combinator (with more math-like notation) is defined as: S x y z -> x z (y z). There would also be a similarity with the <*> operator in Haskell, as S is (<*>) for the ((->) r) Applicative instance (I don't really know, to be explored and confirmed).

The fork is the S' combinator, or the starling', or the phoenix bird from Haskell's Data.Aviary.Birds package. It is also the liftM2 function from the Control.Monad package!

References:

Tools:

Articles:

Solutions:

APL

When running a program from dyalogscript (Dyalog APL), to access the ]box on and ]rows on options you can (have to?) call this line (first line in example below):

(⎕NS⍬).(_←enableSALT⊣⎕CY'salt')
]box on -style=max
]rows on

Nested APLs such as APL2 allow any array to be used as an element, including scalar numbers or characters (written with quotes) as well as larger arrays. In order to include a stranded array inside another array it must be parenthesized. [...] Flat APLs impose the rule that all elements of arrays have the same type, such as all character or all numeric. [...], and it has been maintained in newer languages such as SHARP APL and J.

Although Reduce is foldr1 in nature, one can use it like foldr, where a designated starting value is modified by the rest of the values in sequence. In this case, the start value (enclosed if not a simple scalar) is attached to the right end of the vector of "modifiers", and then the entire vector is reduced.

     (⍉∘⌽↓)/2 1 2 1,⊂5 6⍴⍳30  ⍝ Trim a matrix from all four sides, by rotating the matrix after each trim
┌─────┐
│ 9 10│
│15 16│
│21 22│
└─────┘

In general, Reduce reduces one chosen axis (either implied by using the last-axis form f/ or first-axis f⌿, or explicitly by using function axis f/[x]) by evaluating each vector along the chosen axis into a scalar.

Rank: an array may have 0 or more axes or dimensions. The number of axes of an array is known as its rank. Dyalog APL supports arrays with a maximum of 15 axes.

Depth: if one or more items of an array is not a simple scalar (i.e. is another array, or a ⎕OR), the array is called a nested array. A nested array may contain items which are themselves nested arrays. The degree of nesting of an array is called its depth.

A train such as = / + could be interpreted either as the two-train (=/) +, Equals reduction atop Plus, or as a three train Equals Compress Plus. Dialects choose the first interpretation. To force the fork interpretation, we can add right atop: =⊢⍤/+. See the reference about function-operator overloading.

References:

Solutions:

Uiua

  • Use /∘ to put all array elements on the stack

References:

C#

Solutions:

How to run

To run Python solutions:

$ python3 src/01.{py,in}

To run Haskell solutions (two ways):

$ stack runhaskell src/01.hs
$ stack runhaskell src/01.{hs,in}

To run Lua solutions:

$ lua src/01.{lua,in}

To run Lua tests (requires busted, luarocks install --local busted):

$ busted -o TAP src

To run Scheme solutions:

$ scheme --libdirs src --script src/01.{ss,in}

To run uxn solutions:

$ make 01_tal

To run Elixir solutions:

$ elixir src/01.exs <src/01.in

To run Go solutions:

$ go run src/01.{go,in}

To run Forth solutions:

$ gforth src/01.{fs,in}

To run Node.js solutions:

$ node src/01.{js,in}

To run C++ solutions:

$ make 01_cpp

To run Rust solutions:

$ make 01_rs

To run GNU Smalltalk solutions:

$ make 01_st

To run Java solutions:

$ make 01_java

To run Kotlin solutions:

$ make 01_kt

To run Ruby solutions:

$ ruby src/01.{rb,in}

To run x86-64 Assembly solutions (Linux only):

$ make 01_s

To debug x86-64 Assembly solutions with gdb, you can add a halt: label in your code, and:

$ make 01_sd

To run Common Lisp solutions:

$ sbcl --script src/01.{lisp,in}

or:

$ clisp src/01.lisp -- src/01.in

To run Erlang solutions:

$ escript src/01.{erl,in}

To run J solutions:

jconsole -js "input=:'src/01.in'" "load 'src/01.ijs'" "exit''"

To run the APL solutions:

$ dyalogscript src/01.apl

To run BQN solutions:

$ bqn src/01.{bqn,in}

To run Uiua solutions (tested with Uiua 0.4.1):

$ uiua run src/01.ua

To run C# solutions (dotnet tool install -g dotnet-script):

$ dotnet-script src/01.cs

How it started

$ stack new aoc2021
$ cd aoc2021
$ rm -r app
$ rm -r test
$ rm -r Changelog.md

In package.yaml:

  • Remove "executables" section
  • Remove "tests" section
  • add hspec dependency (LTS) and -W ghc-option in "library" section
$ stack setup
$ stack build

Then write a Spec.hs file in src, and try to run it with:

$ stack runhaskell -- src/Spec.hs

Note: for this simple project, I want all the code in the src directory.

About

Solutions to & Learnings from Advent of Code 2021

adventofcode.com/2021

Topics

nodejs javascript ruby kotlin python java go rust golang scheme haskell erlang elixir lua cpp x86-64 smalltalk forth advent-of-code-2021 uxntal

Resources

Readme

License

BSD-3-Clause license
Activity

Stars

7 stars

Watchers

3 watching

Forks

0 forks
Report repository

Languages