# AoC 2020 Day 1 — Report Repair

Link to the exercise: https://adventofcode.com/2020/day/1

Okay, we gotta find 2 numbers in the array summing to 2020 and multiply them. Easy.

We could do a brute force solution by looking at every pair and checking if it sums to 2020.

```
for a in numbers
for b in numbers
if a + b == 2020
return a * b
```

Asymptotic time complexity is *O(n ^{2})*, because for every one of

`n`

elements we iterate through all n of our elements, where `n`

is the size
of our input array.We can improve on it, but let’s get the data first.

I’m pasting the input array into my code, because I don’t care about text parsing right now.

`puzzle1Data = [1287, 1366, 1669, 1724, 1338, 1560, 1328, 1886, 1514, 1863, 1876, 1732, 1544, 1547, 1622, 1891, 1453, 1936, 178, 1398, 1454, 1482, 1585, 1625, 1748, 1888, 1723, 717, 1301, 1840, 1930, 1314, 1458, 1952, 1520, 1994, 1924, 1873, 1283, 1036, 2005, 1987, 1973, 1926, 335, 1316, 1241, 1611, 1593, 1754, 1254, 1768, 1824, 1752, 1559, 1221, 1855, 1907, 1917, 1975, 1782, 1966, 1395, 1681, 1236, 1572, 437, 1294, 1614, 1549, 1769, 1963, 1953, 1708, 1382, 1920, 1884, 1841, 1055, 1799, 1818, 1902, 1541, 1830, 1817, 1939, 1311, 1157, 1997, 1269, 2000, 1573, 1898, 1467, 1929, 1530, 1336, 1599, 1860, 1455, 1944, 1339, 1341, 1874, 1322, 1340, 1583, 1765, 1776, 1304, 1880, 1237, 1770, 1011, 1634, 1343, 1864, 1648, 1588, 933, 1839, 1245, 780, 1671, 1989, 1416, 1268, 1619, 1399, 1638, 1319, 1565, 1318, 1084, 1397, 1645, 1760, 1487, 1892, 1980, 1928, 1808, 1692, 1159, 1531, 1575, 457, 1650, 1308, 1347, 1427, 1148, 1705, 1356, 1519, 1490, 1324, 1387, 1649, 1780, 1361, 1866, 1828, 1274, 1606, 1477, 1956, 734, 1483, 1513, 1215, 1927, 1988, 1686, 1914, 1424, 968, 1949, 1999, 1296, 1615, 1446, 1698, 1959, 1983, 2010, 1984, 1859, 1838, 1680, 1134, 1529, 1552, 1764, 1981, 1862, 1430, 1793, 1901, 1909]`

Time for some Unison code. Let’s go through our elements once, and for each
`a`

look for `2020 - a`

. This should give us *O(n * lookup-time)*, where
lookup time is *O(log(n))* for balanced binary trees and *amortized/expected
O(1)* for hashmaps.

```
findTwoSummingTo2020 : List Nat -> (Nat, Nat)
findTwoSummingTo2020 numbers =
numbersSet = Set.fromList numbers
go : List Nat -> (Nat, Nat)
go = cases
[] -> -- uhh? --
head +: tail -> (0, 0) -- some implementation --
go numbers
```

We take a list of natural numbers, and return a pair of natural numbers. I forgot about handling the corner case, though. What if we don’t find anything? What if we get an empty list?

Unison has algebraic effects which he weirdly calls abilities, and there is an effect called Abort in the standard library, so I could throw an exception, but that whole algebraic effects schtick forces me to actually handle it later :/

Using `Optional`

will be easier, and probably more elegant here.

```
findTwoSummingTo2020 : List Nat -> Optional (Nat, Nat)
findTwoSummingTo2020 numbers =
numbersSet = Set.fromList numbers
go : List Nat -> Optional (Nat, Nat)
go = cases
[] -> None
head +: tail ->
x = 2020 - head
if Set.contains x numbersSet
then Some (head, x)
else go tail
go numbers
```

Banging. I added that Optional and a conditional expression, and the code starts looking proper.

This obviously doesn’t work. It doesn’t typecheck, because Unison doesn’t
know what `-`

means.

Really nice error message, my new friend.

Unison has at least three types for numbers

`Int`

— signed 64-bit integer`Nat`

— unsigned 64-bit integer`Float`

— 64-bit floating point

Which are WAY better names than `long long`

, `unsigned long long`

and
`double`

. I didn’t code in C for years, and I’m still salty. Still, I kinda
prefer Rust’s `u64`

, but I digress.

There’s no implicit coercion in Unison, so my set of `Nat`

ural numbers and
subtraction aren’t the best friends (`Nat.-`

returns `Int`

). Let’s turn it
all into signed integers. Figuring this out took me more than I want to
admit, but Unison wanted me to add a plus sign in front of every positive
number. Signed integers… oh…

```
puzzle1Data = List.map Nat.toInt listOfNaturalNumbersFromBefore
findTwoSummingTo2020 : List Int -> Optional (Int, Int)
findTwoSummingTo2020 numbers =
numbersSet = Set.fromList numbers
go : List Int -> Optional (Int, Int)
go = cases
[] -> None
head +: tail ->
x = +2020 - head
if Set.contains x numbersSet
then Some (head, x)
else go tail
go numbers
```

This worked. Now what’s left is only multiplying the two numbers I’ve found. The code before was quite readable, so I’ll make the next function point-free 🤣

```
solve : List Int -> Optional Int
solve = Optional.map (uncurry (Int.*)) . findTwoSummingTo2020
```

`>`

starts watch expression which is conveniently printed by Unison Codebase
Manager on save.

`> solve puzzle1Data`

Sweet. Advent’s website confirmed my result, and gave me the second part of
the task. Before I get to it, I want to make my code more *unisony*.

It seems to me that Unison is one languages-for-engineering. Tests and documentation are first-class citizens in the language.

Here’s how I wrote the docs. You can read more about it at https://www.unisonweb.org/docs/documentation.

```
findTwoSummingTo2020.doc = [:
`@findTwoSummingTo2020 numbers` finds two elements of numbers list
summing to 2020.
Here's a typical example:
@[source] findTwoSummingTo2020.examples.ex1
⧩
@[evaluate] findTwoSummingTo2020.examples.ex1
`@findTwoSummingTo2020 []` is equal to None.
Asymptotic time complexity is ϴ(nlogn) or amortized ϴ(n) depending on
Unison's builtin Map implementation (balanced tree or hashmap).
:]
```

And these are my tests:

```
test> findTwoSummingTo2020.tests.one =
check (
findTwoSummingTo2020 [+2000, +1995, +25, +1234] == Some (+1995, +25)
)
test> solve1.tests.one = check (solve1 puzzle1Data == Some +691771)
```

Okay, part two of the puzzle. Now we have to find three numbers summing to 2020. I don’t have any new, smarter idea, so I’ll just build on top of my existing solution.

```
findTwoSummingToX : List Int -> Set Int -> Int -> Optional (Int, Int)
findTwoSummingToX numbers numbersSet sum =
go : List Int -> Optional (Int, Int)
go = cases
[] -> None
head +: tail ->
x = sum - head
if Set.contains x numbersSet
then Some (head, x)
else go tail
go numbers
findThreeSummingToX : List Int -> Set Int -> Int -> Optional (Int, Int, Int)
findThreeSummingToX numbers numbersSet sum =
findTwo = findTwoSummingToX numbers numbersSet
cons = Optional.map . Tuple.Cons
List.foldl (acc val ->
let
use Int -
diff = sum - val
if isSome acc then acc else (cons val (findTwo diff))
) None numbers
solve2 numbers =
match findThreeSummingToX numbers (Set.fromList numbers) +2020 with
Some (a, b, c) -> Some ((a, b, c), a * b * c)
None -> None
> solve2 puzzleData
```

Here it is. I’m quite impressed with this language.

Did you, the human reading this, take part in the Advent of Code? Have you tried any new language? Let me know!