The Advent of Code 2020 is live. This is a set of programming puzzles, two each day, which can be implemented in any language you like - I chose Fortran. It starts out easy, some of the later ones are harder. I did last year’s all in Fortran, and plan to do so this year. It’s fun to see the discussion and examples where people used oddball languages (SQL!) in their solutions.
Should we set up a Fortran leaderboard?
Edit: I created a private leaderboard in case you want to make it more competitive. The code is 1058222-e9b511cc. Feel welcome to join!
2 Likes
I’m already on someone else’s private leaderboard, but it’s a fun thing to do.
I too had an O(n^3) solution to part 2 of day 1. The subreddit is full of suggestions for how to optimize (some practical, some not). The simplest for this problem was to skip cases where the first two values exceeded 2020.
When I did this last year, I had occasion to visit the subreddit for clues as to how to proceed. It’s entertaining to see what people come up with. Expect the problems to be harder as the month goes on.
1 Like
The way the private leaderboards seem to work is the first person to solve the puzzle, upon it becomes available, gets more points. In essence it means your time zone and sleeping habits are a dominant factor in the leaderboard. For the record my day 3 solution has c. 130 lines.
Yes, the earlier you solve it, the more points you get, both for private leaderboards and the global one. The subreddit has “megathread” pages for each day, where people post solutions. It doesn’t go live until at least “a significant number of people” have solved both puzzles. It tends to unlock minutes after the puzzle is put up (at least so far.)
My Fortran solution to Day 3 is 39 lines.
I just counted the second one - the first was shorter. I had to add a few lines to get the second.
Day 4, part 2… another string manipulation… I mean it is a good practice to refresh our string-skills, but it gets boring after a while. Hopefully, the next puzzles will have something new to offer. I am uploading my solutions so far to github, with the hope that others will follow as well. It would be very interesting and educational to see different approaches and technics.
You can find mine here: https://github.com/ivan-pi/adventofcode-2020
Edit: I was quite happy to learn how to use the string intrinsics, index, verify, and the new intrinsic split.
I used scan for the first time! The problems will get more complex.
1 Like
What programming language is this? Is that last line finding the missing seat by taking the difference of the product of smallest and largest seat id and the sum of all seat id’s?
My day 6 solutions made use of one of my favorite intrinsics:
popcnt
1 Like
Looks like Haskell. Any language is fine!
Here’s my Fortran solution to part 2 of Day 6. Part 1 was very similar.
program AOC06
implicit none
integer :: answers,group,total,i,ios
character(80) :: line
open (unit=1,file='input.txt', form='formatted', status='old')
total = 0
ios = 0
outer: do while (ios == 0)
group = int(Z'03FFFFFF')
inner: do
read (1,'(A)', iostat=ios) line
answers = 0
if ((ios /= 0) .or. (line == "")) exit inner
do i=1,len_trim(line)
answers = ibset(answers, ichar(line(i:i)) - ichar('a'))
end do
group = iand(group,answers)
end do inner
total = total + popcnt(group)
end do outer
print *, total
end program AOC06I also used popcnt. My program logic was similar, although perhaps less elegant…
module day6
use, intrinsic :: iso_fortran_env, only: int32
implicit none
character(len=*), parameter :: lowercase = 'abcdefghijklmnopqrstuvwxyz'
contains
subroutine process_forms(file,nyes_any,nyes_all)
character(len=*), intent(in) :: file
integer, intent(out) :: nyes_any, nyes_all
integer :: unit, err, ngroup, i, ii, npeople
character(len=100) :: buffer
logical :: eof
integer(int32) :: mask_or, mask_and, mask
open(newunit=unit,file=file,action="read",status="old")
nyes_any = 0
nyes_all = 0
ngroup = 0
npeople = 0
mask_or = 0
mask_and = 0
do
read(unit,'(A)',iostat=err) buffer
if (err < 0) eof = .true.
if (len_trim(buffer) > 0) then
npeople = npeople + 1
mask = 0
do i = 1, len_trim(buffer)
ii = index(lowercase,buffer(i:i))
if (ii > 0) mask = ibset(mask,ii-1)
end do
mask_or = ior(mask_or,mask)
if (npeople == 1) then
mask_and = mask
else
mask_and = iand(mask_and,mask)
end if
end if
if (len_trim(buffer) == 0 .or. eof) then
nyes_any = nyes_any + popcnt(mask_or)
nyes_all = nyes_all + popcnt(mask_and)
ngroup = ngroup + 1
npeople = 0
mask_or = 0
mask_and = 0
end if
if (eof) exit
end do
close(unit)
end subroutine
end module
Day 7 will be a tough one with Fortran! I am thinking of some recursive string function.
I’m working on this now. So far, I don’t need recursion, but I see in the megathread that others used it. I’m regretting deleting my “symbol table” code from last year - just recreated it.
I was able to solve part 1 with some nasty string lists…
Spoiler alert!
module day7
implicit none
type :: string
character(len=:), allocatable :: s
end type
contains
logical function contains(list,str)
type(string), intent(in) :: list(:)
type(string), intent(in) :: str
integer :: i
contains = .false.
do i = 1, size(list)
if (list(i)%s == str%s) then
contains = .true.
return
end if
end do
end function
subroutine make_unique(slist,out)
type(string), intent(in) :: slist(:)
type(string), intent(out), allocatable :: out(:)
integer :: i
out = [slist(1)]
do i = 2, size(slist)
if (contains(out,slist(i))) cycle
out = [out, slist(i)]
end do
end subroutine
recursive subroutine collect_bags(unit,search_for,ph)
integer, intent(in) :: unit
type(string), intent(inout), allocatable :: search_for(:)
integer, intent(inout) :: ph(2)
type(string) :: bag
character(len=1000) :: buffer
integer :: ic, ib, pos
integer :: i, nbags, stat
nbags = 0
do i = ph(1), ph(2)-1
stat = 0
do while (stat == 0)
read(unit,'(A)', iostat=stat) buffer
ic = index(buffer,'contain')
ib = index(buffer,search_for(i)%s,back=.true.)
! print *, "ic = ", ic, " ib = ", ib
if (ib > ic) then
nbags = nbags + 1
pos = index(buffer,' bags')
bag%s = buffer(1:pos)
search_for = [search_for, bag]
end if
end do
rewind(unit)
end do
if (nbags > 0) then
ph(1) = ph(2)
ph(2) = size(search_for) + 1
call collect_bags(unit,search_for,ph)
end if
end subroutine
end module
program main
use day7
implicit none
integer :: unit
integer :: i, ph(2)
type(string), allocatable :: string_list(:), out(:)
open(newunit=unit,file="input",action="read")
string_list = [string('shiny gold')]
ph = [1,2]
call collect_bags(unit,string_list,ph)
call make_unique(string_list(2:), out)
do i = 1, size(out)
print *, i, out(i)%s
end do
close(unit)
end program main
Day 8 was fun, another take on the “intcode” computer of 2019. I expect later days will build on this.