I do not see the purpose of implementing brute force for part 2. A nearly identical algorithm for part 1 will solve day 5 part 2, just extremely inefficiently.
That said, I am thinking about the problem and I don’t see what the “faster way” might look like… I was thinking work backwards through the maps, but even if you do that, there’s the leftover bin of being “unmapped” and the previous number falling through.
Brute force on a single core 5800x did it in 3 minutes, which I don’t love…
spoiler
I see you can spawn ranges, but I guess the self imposed limitation of never generating a temporary array makes that more difficult as well. I believe in this case tiem spend allocating memory for temporaries would not matter compared to how much faster you can check billions of numbers, but alas.
Despite many attempts, I can’t seem to figure out where I’m going wrong in part two of day 1. I’ve managed to obtain the calibration for each day and then add up the results, but I can’t see why the solution isn’t correct.
First I create an array with the first position of each string (‘one’, ‘two’, …) then I replace in order:
program aoc_01b
use mod_utils
implicit none
integer:: f, ios, i, j, k
character:: c, calibration(2)
integer:: total
logical:: b_exit
integer:: pos(10) ! Posición de cada palabra letra en la línea de entrada
character(len=5), dimension(9):: num = ["one","two", "three", "four", &
"five", "six", "seven", "eight", "nine"]
character(len=80):: line, line_original
total = 0
calibration = "__"
open(newunit=f, file="in/01.txt", iostat=ios, access="sequential")
read(f, "(a)", iostat=ios) line_original
line = trim(line_original)
linea: do
replace: do
b_exit = .true.
! Find the first position of each number in the input line
busca: do i=1, size(num)
pos(i) = str_find(trim(num(i)), line)
if (pos(i) .ne. -1) b_exit = .false.
end do busca
if (b_exit) exit replace
! Discover what number is in the first position.
! j: the first position
! k: the entry in the array num(k)
! Example: The first position corresponds to num(k) that is in position j."
j = len(line)
first_pos: do i=1, size(num)
if (pos(i) .le. 0) cycle
if (pos(i) .lt. j) then
j = pos(i)
k = i
end if
end do first_pos
line = str_replace(trim(num(k)), num2str(k), line)
end do replace
! Process each line character by character.
caracter: do i=1, len(trim(line))
call regular_character(line(i:i), calibration)
end do caracter
! Sum total
total = total + ichar(calibration(1))*10-480
total = total + ichar(calibration(2))-48
write (*,"(a50, 2a, i6)") line_original, calibration, total
calibration = "__"
! Read other line or exit
read(f, "(a)", iostat=ios) line_original
line = trim(line_original)
if (ios .lt. 0) exit linea
end do linea
close(f)
print *, "TOTAL", total
! No es 57340
contains
subroutine regular_character(c, calibration)
implicit none
character, intent(in) :: c
character, intent(out):: calibration(2)
select case(ichar(c))
case (48:57) ! Is a digit
if (calibration(1) .eq. "_") then
calibration(1) = c
calibration(2) = c
else
calibration(2) = c
end if
end select
end subroutine
end program aoc_01b
I’m afraid, I know how to get the calibration numbers, but my problem is that my total is no the correct answer, so I am looking for the problem in the upper text file whose second column are calibrations and last one the total
Day 7 is a more familiar problem. Very similar to poker except “easier to play while riding a camel” - meaning no patterns (therefore no flush or straight flush) and the sequence of each hand matters.
Now, I don’t know about you, but the original poker (which is a “harder” problem to solve than Day7) was some kind of “unofficial homework” in my first programming class. No tutor ever asked to implement a program to evaluate a poker hand (only boring problems as homework - not necessarily easy, but boring). Nevertheless many students took the “poker challenge”, ignoring their actual homework.
I do remember at least a Pascal, Fortran 77, and even a… Basic implementation being written in the lab. And vaguely remember the algorithm I thought it was convenient to solve it - which is, of course, a spoiler.
Day 7 I like a lot more than 6. I thought I had a pretty decent method for part 1, but it appears this is not complete enough to easily extend for part 2…
For day 10 part 2, I just took the easy way out and used the locpt routine that originally came from the NSWC Mathematics Subroutine Library, written in the early 1990s. Worked like a charm in about 1.5 sec.
program t
integer, parameter :: n = 10
character(1) :: space(n, n)
open(newunit=i,file='aoc.txt')
read(i,"(10a)",end=1) space
1 print "(10a)", SPACE
end program
(works with gfortran but am not sure it’s 100% general)
This reminds me that it would be nice to have a one-stop-shop library for basic computational geometry in Modern Fortran, e.g. for calculating intersections, point-in-polygon, clipping, convex hulls, Voronoi diagrams etc. Extensive libraries are available in other languages and so a partial port may be the best way to go. Some of these routines would benefit from the parallelization features available in Modern Fortran. I could certainly make use of these but am not competent enough to write them.
It gave me flash backs to 2022 day 17, when you had to simulate a trillion tetris pieces for part 2. I didn’t know it back then, but now I know that the trick is to assume that eventually, a periodic cycle will begin where the pattern returns to the same state as an earlier step.
For Day 16, I fully overengineered it by solving it with a Lattice Boltzmann type Method!
I didn’t encounter the same issues with infinite loops that others have, but it’s not super fast. Part 2 especially takes a long time (~14 seconds). Perhaps I’m doing something silly that is keeping the performance down. Is there someway to get FPM to set -march=native? Or does it do that already? Does FPM work with OpenMP?
I had a really hard time reading the input. Kept segfaulting or just being wrong. Finally had to use an exact number of characters to read to get what I wanted. I/O in fortran is just…difficult if you don’t do it a lot.
I’d appreciate any input on how to make this solution faster/better/more fortranic! (github link)
