Wizarth's Blog

Find all occurrences of mul(#,#) in a set of strings, multiply the specified numbers, then sum the results.

The input contains several mul-like entries, that need to be ignored. This problem immediately looks like a problem for a Regular Expression.

XKCD comic about regular expressions

Naturally, being a regular expression, I did have an error in my first attempt, where I put the first + outside the first capturing group, not inside it.

# I predict Part2 will have operations other than mul
struct MulOp
    a::Int
    b::Int
end


function parse_input(src = "input.txt")
    # The input is one-or-more lines of text
    # Within that text, there will be occurrances of
    # mul(##,##)
    # There will also be many things that are close to but don't quite match the pattern.
    # This is clearly a case for regular expressions
    pattern = r"mul\(([\d]+),([\d]+)\)"
    
    results = Vector{MulOp}(undef, 0)
    # Since a newline would break the pattern, we can process the file as lines, not a single string
    for line in eachline(src)
        for match in eachmatch(pattern, line)
            a, b = match
            push!(results, MulOp(
                parse(Int, a),
                parse(Int, b)))
        end
    end

    return results
end

function main_part1()
    ops = parse_input()

    println("Results: ", sum(
        map( op -> op.a * op.b, ops)
    ))
end

main_part1()

Julia's eachmatch function really made this process simple. At first I thought I'd have to do the loop manually, but while reading the documentation on RegexpMatch I scrolled up and saw eachmatch. I should have known. The code also takes advantage of destructuring capture groups into a and b for convenience.

I used a struct to store the parsed numbers because – I suspect Part 2 is going to have non-mul operations, and being able to switch on the returned type will be useful. – Julia doesn't provide a fixed length array as part of Base (although StaticArrays is so stable it might as well be Base). – Tuple felt like overkill. – Julia is a Just-In-time compiled language, so all the options result in the same memory layout anyway.

Part 2

Find do() and don't() entries in the string. Disable mul operations after a don't, and enable again after a do. Initially mul operations are enabled.

This can be implemented by extending the Regular Expression to also match these new commands, and only performing the push! onto results when operations are enabled.

I thought it would be possible to have multiple capturing groups use the same name, as only one would ever be matching, so initially I extended the Regular Expression to use named capture groups. However, this isn't allowed, BUT there is a Branch reset group, that does the same thing for numbered groups. I've never used this feature of Regular Expressions before!

I made use of a Regular Expression Explorer while diagnosing the expression. It is really useful being able to see the Regular Expression as a hierarchy of nested operators. Without it, I would not have realized that there needs to be a single Branch reset group containing the | alternation groups.

function parse_input_part2(src = "input.txt")
    pattern = r"(?|(?:(mul)\((\d+),(\d+)\))|(?:(do)\(\))|(?:(don't)\(\)))"

    results = Vector{MulOp}(undef, 0)
    enabled = true
    for line in eachline(src)
        for match in eachmatch(pattern, line)
            # dump(match)
            op, a, b = match
            if op == "mul"
                if enabled
                    push!(results, MulOp(
                        parse(Int, a),
                        parse(Int, b)))
                end
            elseif op == "do"
                enabled = true
            elseif op == "don't"
                enabled = false
            end
        end
    end

    return results
end

function main_part2()
    ops = parse_input_part2()

    println("Part 2 Results: ", sum(
        map( op -> op.a * op.b, ops)
    ))
end

main_part2()

Thinking about viewing the Regular Expression as a hierarchy made me wonder if someone had made a Julia package to make PCRE expressions read more like Julia expressions, and I found ReadableRegex.jl. I don't think it would have helped with this problem (it doesn't look like it implements the equivalent of (?| ... )), but it would at least allow writing the expression with multiple lines and indentation.

Part 1

Given a collection of sequences of numbers, determine how many sequences meet the criteria (described as “are safe”):

  • Either
    • The sequence is increasing
    • The sequence is decreasing
  • The sequence change is at least 1 and at most 3

After grabbing the input data, it's worth noting that the sequences are not consistently sized. They vary in length between 5 and 8 numbers, and unlike Day 1, the numbers have varying numbers of digits.

I feel like parse_input could have been implemented using map on the iterables returned by eachline and eachsplit, but the for/push! combination was Good Enough™.

I couldn't find a built in Julia function to iterate over a collection performing a comparison to the previous element, so I wrote one. The first attempt was implementing all of is_increasing, then I realized it could be used with a functor, which is The Julia Way™.

The is_change_in_range test uses the chaining comparisons feature of Julia, which is really pleasant to write. It also uses the do syntax for declaring a functor, which is part of why applying a functor is The Julia Way™.


function parse_input(src = "input.txt")
    sequences = Vector{Vector{Int}}(undef, 0)
    for line in eachline(src)
        sequence = Vector{Int}(undef, 0)
        for digits in eachsplit(line)
            push!(sequence, parse(Int, digits))
        end
        push!(sequences, sequence)
    end

    sequences
end

# Compare each element of a sequence with the previous element
# If the comparison function returns false, return false immediately
# Otherwise return true
function compare_sequence_elements(f, seq)
    @assert length(seq) > 1

    prev = seq[begin]
    for cur in seq[begin+1:end]
        if(!f(prev, cur))
            return false
        end
        prev = cur
    end
    return true
end

is_increasing(seq) = compare_sequence_elements(<, seq)
is_decreasing(seq) = compare_sequence_elements(>, seq)
function is_change_in_range(seq, min_change = 1, max_change = 3) 
    compare_sequence_elements(seq) do prev, cur
        diff = abs(prev - cur)
        return min_change <= diff <= max_change
    end
end

is_safe(seq) = (is_increasing(seq) || is_decreasing(seq)) && is_change_in_range(seq)

function main_part1()
    coll = parse_input()

    println("Safe reports:", count(is_safe, coll))
end

main_part1()

Part 2

This continues Part 1 by adding another condition under which a sequence can be considered “safe”, named the “Problem Dampener”.

If removing a single element from the sequence makes it pass the conditions, then it should be considered “safe”.

is_safe_with_dampener makes use of Julia's great index range handling. begin and end make accessing the heads & tails of collections concise, and the code takes advantage of Julia's behavior of returning an empty collection if you provide a second index that is less than the first (without specifying a negative step).

I also like that because the code uses eachindex, it doesn't care if the sequence is 1 indexed (the Julia default), or some other starting point. By using prevind and nextind, the code doesn't assume the sequence is using linear indexing. During compilation, these all get substituted with what is appropriate for the sequence, so there's no performance overhead for writing more generic code.

function is_safe_with_dampener(seq)
    if is_safe(seq)
        return true
    end
    # Test the sequence, removing an element
    # If any subsequence returns true, return true
    for ind in eachindex(seq)
        subseq = vcat(seq[begin:prevind(seq,ind)], seq[nextind(seq,ind):end])
        if is_safe(subseq)
            return true
        end
    end

    return false
end

function main_part2()
    coll = parse_input()

    println("Safe reports (with dampener):", count(is_safe_with_dampener, coll))
end

main_part2()

#AdventOfCode #JuliaLang

I decided to do the Advent of Code in Julia, as a way of getting back into coding for fun.

Part 1

Given two lists of numbers, work out the distance between each entry in the list (after sorting the lists), then sum the distances to determine the “similarity”.

This is the first time I've written Julia code since 2023-09 , so it involved a lot of referring to the documentation, and it's not really taking advantage of any Julia language specific features (like all code blocks automatically returning their last value).

# Get the distance between two lists, after sorting them
function list_distances(lhs, rhs)
    lhs_sorted = sort(lhs)
    rhs_sorted = sort(rhs)

    return map(lhs_sorted, rhs_sorted) do left, right
        return abs(left - right)
    end
end

function parse_input(src = "input.txt")
    # Format of src
    # #####   #####\n
    lhs = Vector{Int}(undef, 0)
    rhs = Vector{Int}(undef, 0)
    for line in eachline(src) 
        lhs_substr = line[1:5]
        rhs_substr = line[9:13]
        l = parse(Int, lhs_substr; base=10)
        r = parse(Int, rhs_substr; base=10)

        push!(lhs, l)
        push!(rhs, r)
    end
    return lhs, rhs
end

function main_part1()
    lhs, rhs = parse_input()

    list_dist = list_distances(lhs, rhs)

    total_dist = sum(list_dist)

    println("Total dist: ", total_dist)
end

main_part1()

Part 2

For each entry in a list, determine how often it appears in a second list, then multiply the entry by that frequency – then sum these factors.

For this one, I was a bit more warmed up and got a bit more concise in my Julia-isms. The algorithm used is just brute force, but it's Good Enough™ for this purpose.

Re-using parse_input from Part 1.


function main_part2()
    lhs, rhs = parse_input()

    lhs_frequency = map(lhs) do l
        count(==(l), rhs)
    end

    similarity = lhs .* lhs_frequency

    println("Total similarity: ", sum(similarity))
end

main_part2()

#AdventOfCode #JuliaLang

Since I've revived the wizarth.com.au domain, I'm going to try blogging again.

I'm testing the WriteFreely software for hosting the blog. It's a single executable service (compiled Go) and supports ActivityPub.