Advent of Code 2023

Humor
42

I agree that speed is typically not a concern for these types of problems, it’s always an algorithm thing and the harder problems get is again as you say - often a math or algorithms concept I just don’t know.

However, I think it’s still a good idea to write fun codes and other types of exercises as you would “for real,” since at the end of the day people often will perform how they practice. For me that means I try to avoid things like functions returning anything larger than scalar values, especially if called in a loop. Stopping early, single routes to return, avoiding repeating work, and encapsulation for repeated tasks are all other elements I try to stick with.

43

Yes, split is a must! Maybe somebody should add that to Fortran. :slight_smile:

The small library (somewhat quick and dirty) that I have used every year is here: https://github.com/jacobwilliams/AoC-2023/blob/master/src/aoc_utilities.f90 It definitely makes things easier to have these, especially when competing against those using other languages where this kind of stuff is built in.

2 Likes
44

If Fortran had an actual built in string type and associated utilities, as well as built in vector and hash map support, there would be almost nothing holding it back from being an extremely easy to learn + convenient to use general-purpose language.

In trying to solve more typical “a computer would be better to do this problem, let’s code it up” questions, these are the top 3 things I run in to every time. Vectors could even come off, as allocatable with reallocate on assignment is close enough most of the time. No hash maps is a pain for many classes of problem though.

2 Likes
45

I’m tempted to use stdlib for this exact reason. The first couple of days were not that bad but as things get harder using fpm libraries might be the only practical way.

46

That’s a good idea, let’s stop polluting this one.

Just a last thought before :grinning: :

The problem is that, for example, we consider that a student learning engineering must have some knowledge of programming and of the way machines work, even if its future domain is not software. Firstly they can use simulation or computing software in their domain and should have a basic understanding of the way it works, secondly they must have a common vocabulary with colleagues that are more involved in those arts. How to do that in this new era? (a real question for me, not a desperate one :grinning:)

47

I must be missing something about day 3, part 2. I had a pretty good solution to part 1: pad the entire input file with '.', check surrounding characters of any number string searching for non-numeric, non . symbols. Part 2 kind of exploded though, I don’t know what the pattern is other than somewhat unique logic for each of the 8 characters surrounding “a gear” (*).

48

Solving Day 2 with derived data types

For day 2 I played with derived data types

type set_t
    integer :: r, g, b
end type set_t

type game_t
    integer :: id
    type(set_t), allocatable :: sets(:)
end type game_t

I don’t want to go into too much detail how I parsed the input, but I want to highlight how convenient it was to add the code for part 2:

game_power = maxval(game%sets%r) * maxval(game%sets%g) * maxval(game%sets%b)

How Python and Rust would handle this

I wanted to see how this specific part compares to Python and Rust and asked ChatGPT how one would achieve this there:

ChatGPT's answer

To perform similar operations in Python and Rust as you do in Fortran with derived data types and arrays, you will need to use slightly different approaches in each language, as they have different paradigms and syntax.

Python

In Python, you would typically define a class to represent the derived data type, similar to a struct in Fortran. Python’s class system is more flexible and allows for methods to be included with the data.

Let’s define the equivalent structures in Python:

class Set:
    def __init__(self, r, g, b):
        self.r = r
        self.g = b
        self.b = b

class Game:
    def __init__(self):
        self.id = None
        self.sets = []

To calculate game_power, you would use list comprehensions or functional programming constructs like map:

game = Game()
# Assuming you've filled game.sets with Set instances

max_r = max(set_.r for set_ in game.sets)
max_g = max(set_.g for set_ in game.sets)
max_b = max(set_.b for set_ in game.sets)

game_power = max_r * max_g * max_b

Rust

In Rust, which is a system programming language with a focus on safety and performance, you would use structs and associated methods.

Here’s how you could define the equivalent structures in Rust:

struct Set {
    r: i32,
    g: i32,
    b: i32,
}

struct Game {
    id: i32,
    sets: Vec<Set>,
}

To compute game_power, you would iterate over the sets vector, extracting the maximum values for each color component:

impl Game {
    fn calculate_power(&self) -> i32 {
        let max_r = self.sets.iter().map(|s| s.r).max().unwrap_or(0);
        let max_g = self.sets.iter().map(|s| s.g).max().unwrap_or(0);
        let max_b = self.sets.iter().map(|s| s.b).max().unwrap_or(0);

        max_r * max_g * max_b
    }
}

In this example, unwrap_or(0) is used to handle the case where the sets vector might be empty. Rust’s approach is more explicit in handling potential errors or edge cases, which is a characteristic of its design focusing on safety.

Each language offers its own idiomatic ways to handle these kinds of operations, tailored to their respective paradigms and design philosophies.

Final thoughts

Maybe there’s a better way for either Python or Rust. If you know one, please let me know.
Up to this point, I think the most elegant code with the best readability is Fortran.

49

I don’t think Day 4 is harder than Day 3, in fact I think the opposite is true (somewhat “easier” parsing.)

If I understand well, faster execution time is the goal, not code elegance (which, can’t be measured with numbers anyway.) So, since we are dealing with a few milliseconds here, I am guessing that, if someone wants to win, they need to avoid too much structured code. They need to save as many processor cycles as possible, and help the compiler producing faster executables (since that’s all it matters.) Or they can just trust the compiler will do its job as efficiently, so they can work freely with multiple procedure calls, derived types, etc, as needed.

50

The competition is actually for who can produce the correct answer with the shortest time after problem release. Runtime doesn’t matter if it takes 5 hours for the solution to be posted.

That said I don’t personally care to race anyone. I’m not using any parsing library, automatic input downloading, or helpful IDE extensions that seem necessary for these <2 minute times.

I’m also not sitting on their website at midnight waiting for the day to roll over.

1 Like
51

Ok, that makes more sense. But then again, who lives at the “correct” timezone wins. Or who doesn’t have to take the kids at school, or walk the dogs at the “wrong” time… Or who uses the best auto input downloading etc, even. But who on Earth will basically cheat that way, and for what? To win… such a competition? Anyway, it’s for the fun of it, so who cares.

52

My day 3 code ended up being a kludge. I took the liberty of encoding the dimensions in advance and just using brute-force. Not particularly proud of the code…

Spoiler Alert - Day 3 
program day3

implicit none
!integer, parameter :: M = 10
integer, parameter :: M = 140
character(len=M) :: rows(M), cm(M), pm(M)
integer :: fu, i, n, t, j
integer :: tl, tu, rl, ru
integer :: col, ns, ne, psum, pnum

integer :: z(1000000), k, gii, gjj
integer :: zi(1000000), zj(1000000)
integer :: gi(1000000), gj(1000000), gsum
logical :: zb(1000000)

!open(newunit=fu,file="day3_test.txt",status='old')
open(newunit=fu,file="day3_input.txt",status='old')

read(fu,'(A140)') (rows(i), i=1,M) 
close(fu)

cm = repeat('F',M)

do i = 1, size(rows)
    print *, rows(i), ' ', cm(i)
end do

! Mask punctuation symbols
do i = 1, size(rows)
    n = 0
    do
        t = next_punct(rows(i)(n+1:))
        if (t > 0) cm(i)(n+t:n+t) = 'T'
        n = n + t
        if (t == 0) exit
    end do
end do 

print *, "Punctuations masks, DONE!"

pm = repeat('N',M)

! Part mask 
do i = 1, size(rows)
    n = 0
    rl = max(1,i-1)
    ru = min(M,i+1)
    do
        t = scan(cm(i)(n+1:),'T')
        if (t > 0) then
            tl = max(1,n+t-1)
            tu = min(M,n+t+1)
            do j = rl, ru
                pm(j)(tl:tu) = 'PPP'
            end do
        end if
        n = n + t
        if (t == 0) exit
    end do 
end do

print *, "Part masks, DONE!"

k = 0
psum = 0
do i = 1, size(rows)
    col = 0
    print *, "ROW ", i
    print *, rows(i)
    do
        ns = scan(rows(i)(col+1:),'0123456789')
        ne = verify(rows(i)(col+ns:),'0123456789')
        if (ns > 0) then
            tl = col+ns
            tu = merge(col+ns+ne-2,len(rows(i)),ne > 0)
            !print *, rows(i)(tl:tu)
            if (any([((pm(i)(j:j) == 'P'),j=tl,tu)])) then
                print *, rows(i)(tl:tu), " is a part"
                read(rows(i)(tl:tu),*) pnum
                psum = psum + pnum

                if (gears_nearby(i,tl,tu,gii,gjj)) then
                    k = k + 1
                    z(k) = pnum
                    zi(k) = i
                    zj(k) = tl
                    gi(k) = gii
                    gj(k) = gjj
                end if
            else
                print *, rows(i)(tl:tu), " is not a part"
            end if
        end if
        col = min(col + ns + ne - 2, M)
        if (ns == 0 .or. ne == 0) exit
    end do
    !if (i == 16) stop
end do

print *, "Part number scanning, DONE!"

write(*,*)

do i = 1, size(rows)
    print *, rows(i), ' ', cm(i), ' ', pm(i)
end do

write(*,*)
write(*,*) "Sum of part numbers = ", psum

!
! Find gear number ratio
!
print *, "Numbers and gears"
zb = .false.
do i = 1, k
    print *, z(i), zi(i), zj(i), gi(i), gj(i)
end do

gsum = 0
do i = 1, k
    if (zb(i)) cycle
    do j = i+1, k
        if (gi(i) == gi(j) .and. gj(i) == gj(j)) then
            print *, "Found gears: ", z(i), z(j)
            gsum = gsum + z(i) * z(j)
            zb(i) = .true.
            zb(j) = .true.
            exit
        end if
    end do
end do
print *, "Gear sum = ", gsum

contains

    function next_punct(str)
        character(len=*), intent(in) :: str
        integer :: next_punct
        next_punct = verify(str,'0123456789.')
    end function

    logical function gears_nearby(i,tl,tu,gi,gj)
        integer, intent(in) :: i, tl, tu
        integer, intent(out) :: gi, gj
        integer :: ii, jj

        gears_nearby = .false.

        do ii = i-1,i+1
            do jj = tl-1, tu + 1

                if (ii < 1 .or. ii > M) cycle
                if (jj < 1 .or. jj > M) cycle

                if (rows(ii)(jj:jj) == '*') then
                    gears_nearby = .true.
                    gi = ii
                    gj = jj
                    return
                end if
            end do
        end do

    end function

end program
53

In contrast to day 2, where I found parsing to be the most difficult part, on day 4, formatted input worked like a charm (especially if you fix the dimensions in advance).

For part 1, I came with this two-liner:

nwin = [(count([(any(tw(j,i) == tm(:,i)),j=1,nw)]), i = 1, nc)]
print *, "TOTAL POINTS = ", sum(pack(2**(nwin-1),mask=nwin > 0))
54

Yes, Day 4 is tailor-made for Fortran’s advanced array support.

little spoiler

! And the power of pack / unpack is often underestimated.

1 Like
55

On Day 1, Part 2 involved a string search for the words one , two , three , four , five , six , seven , eight , and nine.

Personally, I ended up using a table of words and a linear search using the Fortran index function, but it would have been nice to implement the Aho-Corasick algorithm and build a state machine. In fact Aho & Corasick used FORTRAN in their original work:

Aho, A. V., & Corasick, M. J. (1975). Efficient string matching: an aid to bibliographic search: Communications of the ACM: Vol 18, No 6

1 Like
56

I did the same, and index was the obvious choice for searching. By the way AI didn’t use index at all in a very similar problem I tested some time ago. Instead, it picked a way less sophisticated method with loops (which worked, at least.) When I gave it a tip, “using index will make this easier” it said “yes, you are right” but failed to give a working code many times in a row.

Don’t you think that would be a little… overkill? :laughing:

57

Well yes, strictly speaking it is only Algorithm 1 which is needed (pattern matching), and I’m doubtful it would be faster than the linear search. But it’s a good excuse to learn something new.

I already assembled the goto function, failure function, and output function by hand:

image
image603×755 49.9 KB

Failure function:

i    |  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 
f(i) |  0 30 25  0  0  1  0  0 25 25  0  1  0  0  0  0
     |
i    | 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 
f(i) | 25  0  0  0 25  0 25 30  0  0  0  0  4  0  0 30 25

Output function:

 i   output(i)
---------------
 3   "one"
 6   "two"
10   "three"
14   "four"
17   "five"
20   "six"
24   "seven"
29   "eight"
33   "nine"

I still have to figure out how to convert it to Fortran.

58

I am curious where you used pack/unpack. My solution was a pretty simple n**2 loop for part 1, and during that I stored the number of matches per card, so part 2 was just blasting through that and adding the numbers up. Advent-of-Code-2023/src/day_04.f90 at master · dacarnazzola/Advent-of-Code-2023 · GitHub

59

@ivanpribec used pack above in his two-liner. Basically he took advantage of its mask argument. I almost missed that one in my implementation, trying a where statement first. My comment was more of a reminder to myself because It’s not the first time I almost forgot pack could help. And I don’t think I am the only one. If I were to guess, I’d say pack is probably the less used array feature in Fortran.

Perfomance-wise, I don’t think your loop implementation is any different, but I always go for one- or a-few-liners instead of loops, for the sake of code “elegance”. This is a habit I got from Scilab, where it isn’t a matter of elegance but crucial instead: avoiding loops can make the code orders of magnitude faster. In Fortran, where the code is compiled instead of being interpreted, I doubt it makes the code any faster. But when the language gives you the tools, I like to get them in good use. Besides, there is the bragging factor, “look, I made it shorter”. :laughing:

Jokes aside, Shapiro & Teukolsky have a great comment about that, explaining why making one-liners is not necessarily a good thing. In this case, however, I think it makes the code as “elegant” as it gets.

60

I find part2 of Day5 very interesting in terms of keeping the runtime as low as possible.

1 Like
61

For day 5, I did A “brute force” one using OpenMP that still only takes about a minute on my machine. And then a much faster one that takes less than a sec.

1 Like