Basic data structures drills in Julia

By: Blog by Bogumił Kamiński

Re-posted from: https://bkamins.github.io/julialang/2023/11/10/pe215.html

Introduction

Recently I have written several posts on tips & tricks regarding the usage of Base Julia functionalities.
Today I thought of presenting a solution to a bigger problem that would feature some of the basic data structures available in Julia.

For this I have chosen to solve the Project Euler problem 215.

The post was written under Julia 1.9.2, Graphs.jl 1.9.0, and Chain.jl 0.5.0.

The problem

The Project Euler problem 215 is stated as follows:

Consider the problem of building a wall out of 2×1 and 3×1 bricks (horizontal x vertical dimensions)
such that, for extra strength, the gaps between horizontally-adjacent bricks never line up in consecutive layers,
i.e. never form a “running crack”.
There are eight ways of forming a crack-free 9×3 wall, written W(9, 3) = 8. Calculate W(32, 10).

(I encourage you to visit the source web page for a visualization.)

The solution approach

The basic approach to the solution of the problem can be done in the following steps:

  1. Compute the list of ways a single layer of the wall can be built.
  2. Compute which layers can be adjacent in the wall.
  3. Compute the number of possibilities of building the full wall.

Let us go through these steps on the 9×3 case for which we know the solution.

Compute the list of ways a single layer can be built

For the first step we define the following function:

function list_valid_layers(n::Integer)
    function build(part, len)
        if n-1 <= len + 2 <= n
            push!(valid, BitSet(part))
        end
        for i in 2:3
            if len + i < n
                push!(part, len + i)
                build(part, len + i)
                pop!(part)
            end
        end
    end

    valid = BitSet[]
    build(Int[], 0)
    return valid
end

It takes the layer length n as an input and returns a vector of possible compositions of a layer.
Note that in order to identify the composition of a layer it is enough to keep track of where
the “cracks” in the wall are. For performance we keep this information in BitSet.

The list of compositions is created recursively in the build inner functions. We first check if the
wall would be finished by adding a brick of width 2 or 3. If yes, we store a BitSet pattern of cracks
in the valid vector. If not we try to add another brick of width 2 or 3 to the wall and call the
build function recursively. Note the use of push! and pop! functions in this part of code. It allows
us to reuse a single part vector to keep track of the state of the computations.

Let us check the list of valid layers of width 9:

julia> v9 = list_valid_layers(9)
5-element Vector{BitSet}:
 BitSet([2, 4, 6])
 BitSet([2, 4, 7])
 BitSet([2, 5, 7])
 BitSet([3, 5, 7])
 BitSet([3, 6])

We see that we have 5 such ways. In one of them there are 3 bricks of with 3.
In the remaining we have a single brick of with 3 and four bricks of width 2 (giving 4 ways to build a layer).

Compute which layers can be adjacent in the wall

Two layers can be adjacent in our wall if the intersection of their cracks is empty. Let us keep track of this information
in a graph:

julia> using Graphs

julia> function build_graph(valid::Vector)
           g = Graph(length(valid))
           for i in 1:length(valid), j in i+1:length(valid)
               isempty(valid[i] ∩ valid[j]) && add_edge!(g, i, j)
           end
           return g
       end
build_graph (generic function with 1 method)

julia>

julia> g9 = build_graph(v9)
{5, 3} undirected simple Int64 graph

julia> collect(edges(g9))
3-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 4
 Edge 2 => 5
 Edge 3 => 5

We see that there are only three allowed pairs of adjacent layers:

  • [2, 4, 6] and [3, 5, 7];
  • [2, 4, 7] and [3, 6];
  • [2, 5, 7] and [3, 6].

Note that when building a graph we used a simple graph. The reason is that the adjacency relation is symmetric
(if layer i can follow layer j then the opposite is also true).

Finally note that I iterate i and j assuming 1-based indexing of valid. But this assumption is met as I
require that it is a Vector.

Compute the number of possibilities of building the full wall

What is left is computing the final number of allowed layer compositions.
Here is a function that performs this task:

function count_layers(graph::SimpleGraph, depth::Integer)
    layer_count = fill(1, nv(graph), depth)
    for k in 2:depth, i in 1:nv(graph)
        layer_count[i, k] = sum(layer_count[j, k-1] for j in neighbors(graph, i))
    end
    return layer_count
end

Note that we keep the result in a layer_count matrix. Its layer_count[i, k] entry
tells us in how many ways we can construct a wall having k layers that ends with layer i
(where i is the location of layer in the vector returned by list_valid_layers).

To get the desired result we will need to count the sum of all possibilities from the final layer:

julia> count_layers(g9, 3)
5×3 Matrix{Int64}:
 1  1  1
 1  1  2
 1  1  2
 1  1  1
 1  2  2

julia> sum(count_layers(g9, 3)[:, end])
8

We can see that the result is 8, which is the same as in the problem statement.
So, hopefully we are ready to solve the problem of computing W(32, 10).

Computation of W(32, 10)

To compute W(32, 10) we need to invoke the functions we have defined in this post in sequence.
This kind of task is a natural application of Chain.jl @chain function. So let us test it:

using Chain

@chain 32 begin
    list_valid_layers
    build_graph
    count_layers(10)
    sum(_[:, end])
end

As usual in this blog, I am not presenting the answer, to encourage you to try solving the puzzle yourself.
However, let me remark that the obtained number is relatively large, so you should carefully check if we do not hit the Int64 overflow issue.
If you are not sure what the problem could be check out my recent post, where I explain it.

Conclusions

As a conclusion let us check how long it takes to solve the problem on my laptop:

julia> @elapsed @chain 32 begin
           list_valid_layers
           build_graph
           count_layers(10)
           sum(_[:, end])
       end
0.4039108

The timing of around 0.4 seconds is not that bad, bearing in mind that we used a brute force way to solve the problem.
However, to get this timing keep in mind the following data structures that we used
(not all of them were performance bottleneck in this problem, but I think it is worth to recap them):

  • push! and pop! updates of a vector in a recursion (limiting the number of allocations we needed to make);
  • use of BitSet to keep track of the “cracks” in a layer (taking advantage of the fact that our data was small);
  • use of SimpleGraph to efficiently navigate the allowed links between walls;
  • use of a matrix to incrementally count the number of allowed options.

In all of these steps we took advantage of the fact that for loops in Julia are fast. Note that I took care
to put the code inside functions not only to have reusable components, but also to make sure that
Julia will efficiently execute the code.

Enjoy!