My work mates did this in python. Instead of doing matrix-vector multiplications, you can raise the matrix to the power of ndays (with matrix-matrix multiplications), which can be done very efficiently for 256 days. You’ll end up with an matrix which calculates in one single step how a population will evolve in 256 days.
1 Like
I thought about this too, but since you have to propagate for 79 and 255 timesteps for problem 1 and 2, respectively, calculating the matrices efficiently is kind of messy because they are uneven powers. If you do, you can actually calculate those matrices in Fortran at compile time and really use a single step at runtime. For Python however, I’m not convinced that you actually save time by doing matrix-matrix rather than matrix-vector operations, especially at this system size for a single population.
He used numpy and said it got faster doing it that way.
m = matrix_power(m, days)
fishTimer = m.dot(fishTimer)
It should be 256 timesteps, because the input data is for day 0 so you have to simulate 256 (or 80) days. The reason why you have one day less is because your pop is declared to start at 1 and not at 0, which already “simulates” the first day. Besides of that, you could simulate one day more than asked for and then only count fishes with timers < 8. Then you’ll end up with the population of the previous day.
Today’s second task was a tough one…
My strategy was to first count the segments per digit. After this you end up with two groups of three digits (5 segments: 2,3,5 and 6 segments: 0,6,9). To distinguish them I looked for segments which are different in each one of the group. For the group with 5 segments you can identify them by segment b and e (original order). Both segments can be identified by counting the occurrences of the different segments. Both b and e segments have a unique number of occurrences in the digits from 0 to 9. Distinguishing the second group is a bit more tricky, because you need to find segment c or d to identify 6 and 0. Both segments don’t have a unique number of occurrences, therefore I additionally compared the segments which have 8 occurrences (a and c) with the segments from the digit 1 to get segment c.
All in all a complicated solution. I hope someone found a more simple approach who can present it here.
1 Like
what I did is compare overlaps bewteen uncertained characters.
Firstly,sort strings array according to len_trim(str), and array idx
1,2,3,10 map to [1,7,4,8],(certained map )
4,5,6 map to [2,3,5], (uncertained map)
7,8,9 map to [0,6,9], (uncertained map)
- compare 1 with [2,3,5],and the overlaps are [1,2,1],so 3 is unique
- compare 4 with [2,3,5],and the overlaps are [2,3,3],so 2 is unique
- compare 1 with [0,6,9],and the overlaps are [2,1,2],so 6 is unique
- compare 4 with [0,6,9],and the overlaps are [3,3,4],so 9 is unique
these are all maps between strings array and number
in which overlap means
1 Like
On GitHub some repos have topics such as aoc-2021 and aoc-2021-in-<language>, for example aoc-2021-in-kotlin. I suggest that people doing Advent of Code in Fortran add the topic aoc-2021-in-fortran .
3 Likes
Yep, just gonna take my silver star on Day 8 and go to sleep. Not a good one to try to squeeze in before bed time.
Since I didn’t map the segment letters to integers, I ended up using VERIFY, SCAN, and INDEX several times each in my hacky non-solution to part 2. Also used vector subscript on a character array for the first time, e.g., candidates([1,5,7])(j:j) = 'x'. Hopefully never again.
I’ll be interested to see if anyone’s solution to Day 10 isn’t based on stacks.
Well, I implemented an overkill solution with an impure elemental recursive subroutine. Basicly this is almost the same as a stack, but implicit.
How did the others solve day9? Did you started at the local minima with an recursion or did you started with every point and searched the next minimum?
I simulated the smoke by starting with smoke(:,:) = 1 (padded) and then I transported the values to a lower point in the height_map in 8 iterations, so the values accumulated in the minima
2 Likes
I went with minima location and recursively coloring a mask.
Padding the input indeed saved a lot of trouble, however by allocating with shape (0:n+1, 0:n+1), I had to think twice when creating the interface for the recursive subroutine.
For day 10, I pruned the input from matching groups and than matched against the remaining characters. Neither Fortran nor a stack were involved, just some awk. Since this approach was a bit destructive to the input I had to create a backup to still solve part 2 ;).
2 Likes
For Day 10, I effectively created a recursive descent parser in Fortran. For part 1, when I detected a non-matching character, I scored it and then returned from all the levels. For part 2, if I had reached the end of line but was still nested, I added in the score of the closing character I was looking for. Then at the end sorted the array of non-zero scores. Had to bump to 64-bit integers for this one.
2 Likes
Day 11 was pretty easy. FINDLOC (with MASK!) and ALL to the rescue. Part 2 was just adding a couple of lines to Part 1.
I wanted to go that route, but I couldn’t figure out how to make FINDLOC locate positions >= 9, rather than just == 9. I guess either there’s some way of bookkeeping that makes that irrelevant?
I stumbled a lot on the control flow for my main loop until I realized that a goto was the solution I wanted.
Day 11 Part 1
subroutine part1
integer :: energy(0:11,0:11), i, j, t, flashes
logical :: flashed(0:11,0:11)
open (100, file='data\input_day11.txt', status='old')
do i = 1, 10
read (100, '(10i1)') energy(1:10,i)
end do
close(100)
flashes = 0
do t = 1, 100
flashed = .false.
energy([0,11],:) = -huge(1)
energy(:,[0,11]) = -huge(1)
energy(1:10,1:10) = energy(1:10,1:10) + 1
777 continue
do i = 1, 10
do j = 1, 10
if (energy(i,j) > 9 .and. .not.flashed(i,j)) then
flashed(i,j) = .true.
energy(i-1:i+1,j-1:j+1) = energy(i-1:i+1,j-1:j+1) + 1
goto 777
end if
end do
end do
where (flashed) energy = 0
flashes = flashes + count(flashed)
end do
print *, flashes
end subroutine part1
The keys here are:
- Add 1 to all the octopi and check for a value of 10 with FINDLOC
- Process each of the found 10s, set them to zero and propagate the energy one surrounding area at a time, making sure to not increment if that octopus already flashed
- Keep a mask of octopi that haven’t flashed yet, set each flasher’s entry to false as you get to it
- Repeat FINDLOC until no more 10s are seen
2 Likes
Today I find I am hampered by the lack of a general computer science education. (When I was in college, there was no CS undergraduate program.) Techniques familiar to younger whippersnappers are things I’ve only heard the names of. I had a vague idea of what I was supposed to be doing but had to go to the Subreddit for a hint as to the approach.
Still working on it. Those fancy-pants languages with all of this graphing stuff built in make it too easy.
2 Likes
It would be great if every member of the Fortran committee did Advent of Code in Fortran every year, and compared the solutions of Python, Julia, and Swift. That would definitely show some areas where Fortran could be improved. I am certainly jealous when I see how succinct some of them are compared to what we can do in Fortran. 
3 Likes
The only one of these that has given me significant grief was Day 8 part 2. I ended up:
Treating it as a sort of substitution-cypher cracking problem. The plaintext is cfacdegacdfgbcdfabdfgabdefgacfabcdefgabcdfg (which are the letters for 0-9). By just counting the letters in the ciphertext (the left side of each row in the file) you can immediately get b, e, and f since those each have a unique number of occurrences in the plaintext). Then you can get the other four by process of elimination. But the code I wrote to do this is the most convoluted thing imaginable. haha!
The issue I see here is that the succinctness you mention is largely due to libraries, not language design. I’d be interested in thoughts as to how some of these languages amass significant libraries and Fortran hasn’t. I’ll repeat my oft-said statement that Fortran language design would go a lot faster if more members got involved in the process instead of just throwing stones from afar.
3 Likes