Day 1

This question is about finding the first and last “digit” which could be written as number or word and computing the sum over all input lines. My attempt with julia:

digits_lookup = Dict(
    "0" => 0, "1" => 1, "2" => 2, "3" => 3, "4" => 4,
    "5" => 5, "6" => 6, "7" => 7, "8" => 8, "9" => 9,
    "zero" => 0, "one" => 1, "two" => 2, "three" => 3,
    "four" => 4, "five" => 5, "six" => 6, "seven" => 7,
    "eight" => 8, "nine" => 9
)

function parse_number(line)
    out, digit = 0, 0
    for i in eachindex(line)
        for (k, v) in digits_lookup
            if line[i:min(i+length(k)-1, length(line))] == k
                digit = v
                break
            end
        end
        out = out > 0 ? out : digit * 10
    end
    out + digit
end
lines = readlines("input.txt")
parse_number.(lines) |> sum

Day 2

This question practices string splitting. I made use of a trick that each occurance of “red”, “blue”, and “green” in a line corresponds to a different draw, so one can easily use one regular expression to find all matches and then find the upper limit to the number of balls.

Part 1:

lines = readlines("input.txt")
function process_line(line)
    r, g, b = map(color -> max(map(m -> parse(Int, m.captures[1]), eachmatch(Regex("(\\d+) $(color)"), line))...),
                  ["red", "green", "blue"])
    (r <= 12 && g <= 13 && b <= 14)
end
map(line -> process_line(line[2]) ? line[1] : 0, enumerate(lines)) |> sum

Part 2

function process_line(line)
    r, g, b = map(color -> max(map(m -> parse(Int, m.captures[1]), eachmatch(Regex("(\\d+) $(color)"), line))...),
                  ["red", "green", "blue"])
    r * g * b
end
map(process_line, lines) |> sum

Day 3

Day 3 problem is about finding numbers that are next to special characters including diagonally, with an input like

467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..

The adjacent criteria can be described with

"""
x = (line_num, [indices...])
y = (line_num, index)
"""
function close_by(x, y)
    (lx, idx), (ly, idy) = x, y
    (abs(lx - ly) > 1) && return false
    ((idy > maximum(idx) + 1) || (idy < minimum(idx) - 1)) && return false
    return true
end

where x is a tuple that contains the line number and the string indices of each number, and y is a tuple that similarly contains the line number and an index of the special character (always has length 1).

Next we can parse the numbers and special characters in the format expected by this function with

spc = []; num = []
map(x -> map(m->push!(spc, (x[1], m[1])), findall(r"[^0-9\.]", x[2])), enumerate(lines))
map(x -> map(m->push!(num, (x[1], collect(m))), findall(r"(\d+)", x[2])), enumerate(lines))

where we have used the regex exclusion syntax [^0-9.] to exclude all dots and numbers to help us find special characters, and have used matched group notation (\d+) to find all numbers in a line.

The question asks us for the sum of all numbers that are adjacent to a special character, it can be simply calculated with

sum(num |> filter(x -> any(map(y -> close_by(x, y), spc))) .|> x -> parse(Int, lines[x[1]][x[2]]))

For part 2, it defines a concept of “gear” which is a “*” character that has exactly two numbers adjacent to it. And, the question asks us to find all gears in an input text and compute the product of two numbers for each gear, and then sum the result for all gears. This can be easily achieved with

prod = 0
for c in spc
    if lines[c[1]][c[2]] == '*'
        nums_close = num |> filter(n->close_by(n, c))
        (length(nums_close) == 2) && (prod += mapreduce(n->parse(Int, lines[n[1]][n[2]]), *, nums_close))
    end
end
prod

or, for people who like one-liner,

((spc |> filter(x -> lines[x[1]][x[2]] == '*')) .|> c -> ((num |> filter(n->close_by(n, c))) |> length) == 2 ? mapreduce(n->parse(Int, lines[n[1]][n[2]]), *, num |> filter(n->close_by(n, c))) : 0) |> sum

Day 4

Today’s question is about finding matching numbers on the card,

Card 1: 41 48 83 86 17 | 83 86  6 31 17  9 48 53
Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19
Card 3:  1 21 53 59 44 | 69 82 63 72 16 21 14  1
Card 4: 41 92 73 84 69 | 59 84 76 51 58  5 54 83
Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36
Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11

For example, in the first card, there are four matching numbers.

The first part of the question asks us to compute the score of the card which is calculated as the following: first matching number on a card gives a score of 1, any additional matches doubles the existing score. The question requires us to calculate the total score given an input list of cards.

One simple way to find common numbers amount list is through Set interaction:

"""
expr: string with numbers separated by spaces
"""
function parse_int(expr)
    strip(expr) |> x -> split(x, r"\s+") .|> x -> parse(Int, x)
end

"""
count the number of winning numbers
"""
function get_match_count(line)
    (split(line, ":")[2] |> x -> split(x, "|") .|> parse_int .|> Set) |> x -> intersect(x...) |> length
end

# get total score
(get_match_count.(lines) .|> x -> x == 0 ? 0 : 2^(x-1)) |> sum

where we defined the get_match_count function to find the total number of winning numbers based on the number of elements in the intersection between the two lists. We then use the numbers for each card to calculate the total score based on the description, which is \(2^{x-1}\) except when \(x\) is 0 which has a zero score.

For part two, instead of calculating scores, each card rewards subsequent n cards with n the number of matching numbers in the card. For example, card 1 has 4 matching numbers and will give card 2, 3, 4, 5 as reward, so now there are two copies of card 2 for example. When resolving card 2 award, we repeat the process except we have two copies of card 2 now. It accumulates throughout the card stack, and the question asks us to find the total number of cards at the end of resolving all cards. Here is my solution:

multiplier = [ones(length(lines)); zeros(10)]
for (i, line) in enumerate(lines)
    n_match = get_match_count(line)
    multiplier[i+1:i+n_match] .+= multiplier[i]
end
sum(multiplier)

where I used the multiplier to keep track of the number of card copies. The 10 additional zeros I padded to the multiplier is to ensure the multiplier[i+i:n_match] never goes out of range.

Day 5

Today’s question tests table mapping. It defines some mapping rules from various quantities such as mapping between seed and soil, mapping between soil to fertilizer, and so on, eventually to location. The rule is given like this

seeds: 79 14 55 13

seed-to-soil map:
50 98 2
52 50 48

soil-to-fertilizer map:
0 15 37
37 52 2
39 0 15

fertilizer-to-water map:
49 53 8
0 11 42
42 0 7
57 7 4

water-to-light map:
88 18 7
18 25 70

light-to-temperature map:
45 77 23
81 45 19
68 64 13

temperature-to-humidity map:
0 69 1
1 0 69

humidity-to-location map:
60 56 37
56 93 4

For part one, the question asked us to traverse the series of mapping to find the correct location for each input seed and identifies the nearest location which corresponds to then smallest location id.

First we need to work on parsing the input text:

seeds = match(r"seeds: (.*)\n", text).captures[1] |> split .|> x -> parse(Int, x)
parse_arr = cat -> match(Regex("$(cat) map:\\s*\\n((?:\\s*\\d+\\s+\\d+\\s+\\d+\\s*\\n)+)"), text).captures[1] |> split |> x -> reshape(x, 3, :) .|> x -> parse.(Int, x)
parse_map = cat -> parse_arr(cat) |> x -> map(eachcol(x)) do m
    ((m[2], m[2]+m[3]-1), (m[1], m[1]+m[3]-1))
end
mappings = parse_map.([
    "seed-to-soil", "soil-to-fertilizer", "fertilizer-to-water",
    "water-to-light", "light-to-temperature", "temperature-to-humidity",
    "humidity-to-location"
])

In the input file, the mapping rule is specified as (dest_start, src_start, range); I have converted it to a more readable format: ((src_start, src_stop), (dest_start, dest_stop)) with the parse_map function. The game rule also specifies that any numbers not covered in the specified ranges will passthrough to itself. For completeness, I will also add these dummy ranges: ((0, first), (0, first)) and ((last, inf), (last, inf)). I used inf because I don’t know the largest number in the input text and I don’t want to compute it unnecessarily:

mappings = map(mappings) do mapping
    strt = (0, minimum(mapping[i][1][1] for i in eachindex(mapping)))
    stop = (maximum(mapping[i][1][2] for i in eachindex(mapping)), Inf)
    strt[2] == 0 ? (mapping..., (stop, stop)) : ((strt, strt), mapping..., (stop, stop))
end

To apply a mapping, we simply go through the source ranges to find a match and apply the right offset to the destination range.

function apply_mapping(i, mapping)
    for m in mapping
        (m[1][1] <= i <= m[1][2]) && return m[2][1] + (i - m[1][1])
    end
    return i
end

Then we can find the “location” for each “seed” by traversing all mappings via

foldl((x, f) -> f.(x), [x -> apply_mapping(x, m) for m in mappings], init=seeds) |> minimum

and get the minimum location. This solves the first part.

In part 2 of the question, it suggests the input seeds, instead of being individual seeds, are actually pairs of numbers, with the second number specifying a range. The method that we setup in part 1 then becomes very costly because it may require us to repeatedly calculating mapping over up to 1e9 points (as in the input). It’s not prohibitive for a modern computer but unnecessary, because we could simply keep track of how intervals map to each other, i.e., how different intervals in “seeds” space map onto “locations” space. To work out the interval mapping, we first setup some useful functions that deals with intersections of intervals

has_intersect = (inter1, inter2) -> sign(inter1[2] - inter2[1]) * sign(inter1[1] - inter2[2]) <= 0
interval_intersect = (inter1, inter2) -> begin
    !has_intersect(inter1, inter2) && return nothing
    (max(inter1[1], inter2[1]), min(inter1[2], inter2[2]))
end

To map intervals in input space of map1 to output space of map2, we can use this function

function reduce_mapping(map1, map2)
    omap = []
    for m1 in map1
        for m2 in map2
            inter = interval_intersect(m1[2], m2[1])
            if !isnothing(inter)
                offset1 =  m1[1][1] - m1[2][1]
                offset2 = -m2[1][1] + m2[2][1]
                push!(omap, (inter .+ offset1, inter .+ offset2))
            end
        end
    end
    omap
end

For example, given

map1 = (((0, 50), (0, 50)), ((98, 99), (50, 51)), ((50, 97), (52, 99)), ((99, Inf), (99, Inf)))
map2 = (((15, 51), (0, 36)), ((52, 53), (37, 38)), ((0, 14), (39, 53)), ((53, Inf), (53, Inf)))

the reduced mapping is

reduce_mapping(map1, map2) = (((15, 50), (0, 35)), ((0, 14), (39, 53)), ((98, 99), (35, 36)), ((50, 51), (37, 38)), ((51, 97.0), (53, 99.0)), ((99, Inf), (99, Inf)))

We can then apply this reduction through all mappings to work out interval mappings between seed space and location space, by

omap = foldl((x, y) -> reduce_mapping(x, y), mappings)

To find out the nearest location again like in part one, we can find intersections of the input ranges to the intervals specified in the mapping and figure out how these intervals mapped to location space to identify the nearest location. The math is identical to how we compute the combined mapping in reduce_mapping, so we can reuse it with

# now seeds are pairs of numbers which we will convert to a mapping format
imap = seeds |> x -> reshape(x, 2, :) |> x -> map(eachcol(x)) do c
    ((c[1], c[1] + c[2] - 1), (c[1], c[1] + c[2] - 1))
end
reduce_mapping(imap, omap) |> m -> map(x -> x[2][1], m) |> minimum

This allows me to easily find the minimum location.

Day 6

Today’s question very straightforward, about finding number of integers of a quadratic function above a given threshold, so I will just record my solution here:

# parse data
data = map(l -> split(l, r"\s+")[2:end] .|> x -> parse(Int, x), readlines("input.txt")) |> stack  # part 1
# data = map(l -> (split(l, r"\s+")[2:end] |> join) |> x -> parse(Int, x), readlines("input.txt")) |> stack  # for part 2
map(eachrow(data)) do r
    t, d = r
    ceil((t+sqrt(t^2-4d))/2) - floor((t-sqrt(t^2-4d))/2) - 1
end |> prod

I did learn a good trick from this exercise, when counting numbers of integers between lower and upper, using floor(upper) - ceil(lower) + 1 is prune to error because it will fail when lower or upper are on integers so I had to add a conditional for this. A robust way to count is to use ceil(upper) - floor(lower) - 1, which I just learned from reddit.

Day 7

Today’s question is about ranking sets of cards. There are thirteen cards with ranking (descending): A, K, Q, J, T, 9, 8, 7, 6, 5, 4, 3, 2. Each hand has 5 cards, with some combination types ranking (descending):

  • Five of a kind, where all five cards have the same label: AAAAA
  • Four of a kind, where four cards have the same label and one card has a different label: AA8AA
  • Full house, where three cards have the same label, and the remaining two cards share a different label: 23332
  • Three of a kind, where three cards have the same label, and the remaining two cards are each different from any other card in the hand: TTT98
  • Two pair, where two cards share one label, two other cards share a second label, and the remaining card has a third label: 23432
  • One pair, where two cards share one label, and the other three cards have a different label from the pair and each other: A23A4
  • High card, where all cards’ labels are distinct: 23456

When two hands has the same type, it compares individual cards in the order they appear by the card order. The first part asks us to find ranking of cards and compute the total ranking * bidding. Today’s program will be in python. First parsing the file with

from pathlib import Path

lines = Path("input.txt").read_text().splitlines()

Suppose I have a hand of cards: AKAA2, how do I rank its type? The original method I came up with is to define some patterns based on the number of repeated cards and then find the ranking as its index in the list:

from collections import Counter
hand = "AKAA2"  # an example
patterns = ["11111", "1112", "122", "113", "23", "14", "5"]
card_type = patterns.index("".join(map(str, sorted(Counter(hand).values()))))

I read about a neat ranking trick from some reddit users, which I thought will be nice to record here:

card_type = max(map(hand.count, hand)) - len(set(hand))

one could check that they have the same ranking effect by comparing the ranking numbers

pattern method 1 method 2
11111 0 -4
1112 1 -2
122 2 -1
113 3 0
23 4 1
14 5 2
5 6 4

To compare hands of the same type, we can make use of the build-in comparison in python that compares list (or tuple) in order, which is exactly what we need (I also learned about it today). For example, this works in Python:

[10, 2, 2]) > [10, 2, 1]

# so are these
(3, [10, 2, 2]) > (3, [10, 2, 1])
(3, [10, 2, 1]) > (2, [10, 2, 2])

Therefore we can rank hands simply with

orders = "23456789TJQKA"
rankings = sorted((max(map(hand.count, hand)) - len(set(hand)),
                   list(map(orders.index, hand)), int(bid)) for line in lines if
                  (hand := line.split()[0]) and (bid := line.split()[1]))

then one can easily get ranking * bid as question asks

sum((i+1) * bid for i, (_, _, bid) in enumerate(rankings))

For part 2, the question introduces some special rule for Joker card that it could be used to represent any card to maximize the hand ranking when considering hand types. One could easily see that to maximize hand ranking, we would always want to replace Joker cards with the most frequently appearing card. To compensate for the increased power of Joker, its individual card ranking has becomes the smallest. So to solve part 2, we simply need to rerun part 1 with a minor correction that

hand = hand.replace("J", Counter("J").most_common()[0][0])
orders = "J23456789TQKA"

so I will not repeat. I liked today’s puzzle because it taught me a few tricks in python such as structured comparisons, and inline assignments.