# Basic data structures drills in Julia

# 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 2x1 and 3x1 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 9x3 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:

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

Let us go through these steps on the 9x3 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!