This is about the seventh day (for 2024) of the annual programming challenge Advent of Code.
The Task
In this challenge’s first part we’re presented with lists of numbers in the form:
3267: 81 40 27or, to put it in mathematical fashion:
x: a(1) a(2) … a(n)
The question is:
Can we combine these numbers a(i) by addition or multiplication in a fashion that will lead to the result x?
However, the normal rules of arithmetics (namely operator precedence: multiplication before addition) don’t apply here, but the equation is evaluated strictly from left to right as in (I write the multiplication here as × not as · for legibility):
(((a(1)[+×]a(2)) [+×] a(3)) [+×] a(4)) [+×] a(5)
In our example (81 + 40) × 27 = 3267
Yes, that works. But: How do we get the right combination of operators?
The idea
Let’s assume, we don’t know yet the correct operators, so we’re presented with a possibly unsolvable equation:
(81 [+×] 40) [+×] 27 = 3267
When we start, we’ve got two possiblities:
(81 [+×] 40) × 27 = 3267 and (81 [+×] 40) + 27 = 3267
which are equivalent to
(81 [+×] 40) = 3267 / 27 = 121
and
(81 [+×] 40) = 3267 - 27 = 3240
This reduces a problem with 1 equation with 2 operators to two equations with only 1 operator each.
You can note already that if 27 wasn’t a divisor of 3267, we don’t need to bother any further with the first equation, as it could never lead to the desired result, which is nice as multiplications and divisions are computational far more expensive than additions and substractions and, most importantly, we don’t need to pursue this path any longer.
In our case, we see that 81 + 40 = 121 and 81 × 40 = 3240, but we can break up our search after we found a solution.
However: We now have the basic idea for our algorithm. We reduce the complexity of the equations until being down to just one operator.
If neither a+b = x nor a×b = x, there is no solution.
If you’re not interested in the actual code, you don’t need to read any further. You’ve got the idea, but if you want to understand it, be my guest to continue.
As actual puzzle we’re presented with a long list of equations in the style as above, and we have to sum up the results of the equations which actually have a solution.
It should be noted that this algorithm is blazing fast. It solved both tasks in just 15ms, and that in Perl, which is a slow language. In C or Rust, you would probably get an execution time of under 1ms.
The code
So, here is the code, which we will examine in detail:
The first line #!/usr/bin/perl, the shebang, always starting with #! followed by the path to the executable, tells the command shell where to find the appropriate program to interpret the code.
The programming language Perl is installed by default on any Linux, BSD and MacOS system. In Windows, you would need to install it (search for ActivePerl in the search engine of your choice).
In the second line my $sum = 0;, we declare the variable $sum where we want to sum up the results of the valid equations.
In Perl, variable names are preceded by sigils: $ means, a variable is a scalar, a simple variable, like numbers or strings. @ means, it is an array of scalars, i.e. an ordered list indexed from 0 to the length of the list – 1.
We initialise the sum with 0. This is good practice, but not strictly necessary.
In the next line while(<>) { … }, we find something truly Perl specific and very nice for lazy programmers (e.g. me). The diamond operator <> will grab any file name given on the command line, open the file, read it line by line, store the line in the implicit loop variable $_ return true until it has finished reading the file, then return false and close the file.
The typical usecase would be invoking a program on the shell:
./program.pl data.txt
The next command chomp chops the line ending (newline on Linux, carriage-return + newline on Windows) of the string stored in $_.
s/:// replaces the : sign in $_ with nothing. This is a typical notation for regular expressions. If you’re familiar with the command libe tool sed, you won’t be surprised.
split without any parameters splits the string $_ in a list of values, which have been previously separated by whitespace (e.g. spaces or tabs), and returns that list. We store our list of numbers in the variable @a. Remember the sigils, I spoke about earlier?
We now stuff that list into the function solves which will return 0 if the list has no solution, or the result of the equation, otherwise.
We sum up the results for each line of the input data in the variable $sum and print the result after completing the while loop.
The “solves” Function
In Perl, functions are declared with the keyword sub (memnotic for subroutine). They can be declared anywhere in the code, as before execution the run-time compiler reads the whole program.
A subroutine in Perl takes all arguments and stores them in the special array @_.
Within a subroutine, the command shift without arguments takes the first element off the array @_ and returns it. We store it in the variable $e (e is for Ergebnis, the German word for result).
Remember that the first value in the list is the result of the equation, we have to return if the equation has a solution.
The first case, we consider is the one where we have only one operator (i.e. only 2 numbers left).
The condition if(@_ == 2) { … } might look odd to you, as @_ is a list, but if one of the sides of the == operator is a number, @array returns the length of the array, not the array itself.
return $e if
$_[0] + $_[1] == $e || $_[0] * $_[1] == $e;
is just shorthand notation for
if($_[0] + $_[1] == $e || $_[0] * $_[1] == $e) {
return $e }
You probably already familiar with the logical or ||, so I won’t talk about it here. $_[0] and $_[1] are the first two (here only) remaining numbers in the array @_. Note, how the sigil changes, as the elements are not lists, but scalars.
If neither of the conditions are true, we just return 0.
That was the case of solves with just one operator to determine.
We now need to look at the case with more numbers. Remember above? We need to look at the last number of the list.
The command pop without arguments in a subroutine pops off the last element of the list @_ and returns it. We store the result in the variable $f for further use.
First thing we need to know is, if $f is a divisor of $e.
We check this by calculating my $g = $e/$f and comparing it to its integer part int($g).
The very last command is a succession of ternary operators condition ? this : that , which evaluates to this if the condition is true and to that, if it is false.
What’s inside the different expressions, should be understandable now. The only thing important to know is: In Perl the value 0 is interpreted as false, whilst every other number is interpreted as true.
The Second Part
For the second part, we get another operator to choose from, the concatenation. In that case the equation 1234: 12 34 would also be valid.
In terms of the algorithm nothing really changes, we just have to add another operator and we get this program, which I will not explain in detail, as it doesn’t add much in terms of understanding, but here’s the code:
The only notable parts are:
In Perl string concatenation is done with the dot operator . , string comparison with the eq operator, not ==.
In Perl, context matters all the time. You can switch seemlessly from numbers to strings and vice versa, the operator tells the language, as what an expression is to understand, you hardly ever need explicit conversions.
The substring function substr works this way:
substr(string, start, length) and returns the portion of string of length length starting with the character at position start.
substr(s, -n) returns the last n characters.
You can find and download the full code here.
Leave a Reply