Re-posted from: https://bkamins.github.io/julialang/2024/05/03/pe79.html
Introduction
This week it is a holiday period in Poland so I decided to solve a puzzle.
I liked the code as it can be used to show some basic features of the Julia language.
The examples were written under Julia 1.10.1, HTTP.jl 1.10.6, and Graphs.jl 1.10.0.
The problem
I decided to use my favorite Project Euler puzzle set. This time I chose Problem 79.
Here is its statement (taken from the Project Euler website):
A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may ask for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.
The text file, keylog.txt, contains fifty successful login attempts.
Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.
The keylog.txt file can be found under this link: https://projecteuler.net/resources/documents/0079_keylog.txt.
Let us try solving the puzzle.
The solution
First we use the HTTP.jl package to get the data and pre-process it.
Start by storing the file as a string:
julia> using HTTP
julia> url = "https://projecteuler.net/resources/documents/0079_keylog.txt"
"https://projecteuler.net/resources/documents/0079_keylog.txt"
julia> str = String(HTTP.get(url).body)
"319\n680\n180\n690\n129\n620\n762\n689\n762\n318\n368\n710\n720\n710\n629\n168\n160\n689\n716\n731\n736\n729\n316\n729\n729\n710\n769\n290\n719\n680\n318\n389\n162\n289\n162\n718\n729\n319\n790\n680\n890\n362\n319\n760\n316\n729\n380\n319\n728\n716\n"
Now we want to process this string into a vector of vectors containing the digits verified by the user.
First we split the string by newlines using the split function. Next We process each line by transforming it into a vector of numbers. We use two features of Julia here. The first is the collect function, which when passed a string returns a vector of characters. The second is broadcasting. By broadcasted substraction of '0' from a vector of characters we get a vector of integers. Here is the code:
julia> v = [collect(x) .- '0' for x in split(str)]
50-element Vector{Vector{Int64}}:
[3, 1, 9]
[6, 8, 0]
[1, 8, 0]
⋮
[3, 1, 9]
[7, 2, 8]
[7, 1, 6]
Now we are ready to analyze the data. We will use a directed graph to represent it.
The directed graph will have 10 nodes. Each representing a digit. Because Julia uses
1-based indexing, node number of digit x will be x+1.
Here is the code creating the directed graph:
julia> using Graphs
julia> gr = DiGraph(10, 0)
{10, 0} directed simple Int64 graph
julia> for x in v
add_edge!(gr, x[1] + 1, x[2] + 1)
add_edge!(gr, x[2] + 1, x[3] + 1)
end
julia> gr
{10, 23} directed simple Int64 graph
Note that we have 23 relationships constraining the sequence of the numbers in the unknown password.
Let us check, for each number the number of times it is the preceeding or a following in our graph:
julia> [outdegree(gr) indegree(gr)]
10×2 Matrix{Int64}:
0 5
5 2
3 3
3 1
0 0
0 0
4 3
5 0
2 4
1 5
From this summary we see that the first node (representing digit 0) is never a source, so it can be a last digit in a pass code. Similarly eighth node (representing 7) is never a destination, so it can be a first digit. Finally, digits 4 and 5 are never neither a source or a destination, so they can be dropped.
How can we programattically find the list of nodes that can be dropped? We can simply find all nodes whose total degree is 0:
julia> to_drop = findall(==(0), degree(gr)) .- 1
2-element Vector{Int64}:
4
5
Now we are ready for a final move. Let us assume that our directed graph does not have cycles (this is a simple case, as then we can assume that each number is present exactly once in the code). In this case we can use the topological sorting to find the shortest sequence of numbers consistent with the observed data. In our case to get the topological sorting of nodes in the graph we can write:
julia> ts = topological_sort(gr)
10-element Vector{Int64}:
8
6
5
4
2
7
3
9
10
1
We did not get an error, which means that our directed graph did not have any cycles, so we are done.
What is left to get a solution is to correct the node-numbering (as we start numbering with 1 and the smallest digit is 0) and remove the numbers that are never used. As usual, I leave the final solution un-evaluated, to encourage you to run the code yourself:
setdiff(ts .- 1, to_drop)
Conclusions
I hope you enjoyed the puzzle and the solution!