[fasmg] Advent of Code 2023 w/ solutions ...

Index > Macroinstructions > [fasmg] Advent of Code 2023 w/ solutions ...

Author

Thread

bitRAKE

Joined: 21 Jul 2003
Posts: 4060
Location: vpcmpistri

bitRAKE 03 Dec 2023, 07:29

https://adventofcode.com/2023

Quote:

Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. People use them as interview prep, company training, university coursework, practice problems, a speed contest, or to challenge each other.

One should follow the story narrative for the puzzles to download the required data. I prefix files with their two digit day. This thread will contain solutions in [fasmg] syntax by me. Of course, other solutions are welcome.

Leaderboard: 3576018-bd37868f
Presently, there are 200K people solving these problems and the release falls during my sleeping hours. So, I'm not really aiming for the main leaderboard, but I've created a private fasm leaderboard - use the code above to join.

Links:

Advent of Code 2023 in x86_64 assembly, linux+gdb workflow
https://www.twitch.tv/welltypedwitch

Help with other programming languages:
https://www.reddit.com/r/adventofcode/

The first day solutions are rather trivial, Part 1:

Code:

total = 0
virtual at 0
;file '01.test.txt' ; 142
file '01.input.txt' ; 54601
state = 1 ; find first number character
repeat $, offset:0
        load c:1 from offset
        if '0' <= c & c <= '9' ; number
                last = c - '0' ; cache last number seen
                if state
                        total = total + last * 10
                        state = 0
                end if
        else if c = 10 ; UNIX style LF
                if state
                        err 'unexpected line without digits'
                else
                        total = total + last
                        state = 1
                end if
        end if

; DEBUG
;repeat 1, T:total
;       display " ",`T
;end repeat

end repeat
end virtual
repeat 1, T:total
        display 10,9,"Sum of all of the calibration values: ",`T,10
end repeat

Part 2:

Code:

total = 0
virtual at 0
;file '01.02.test.txt' ; 281
file '01.input.txt' ; 54078
state = 1 ; find first number character
repeat $, offset:0
        load c:1 from offset
        if '0' <= c & c <= '9' ; number
                last = c - '0' ; cache last number seen
                if state
                        total = total + last * 10
                        state = 0
                end if
        else if c = 10 ; UNIX style LF
                if state
                        err 'unexpected line without digits'
                else
                        total = total + last
                        state = 1
                end if
        else
                iterate <TEXT,          LEN,    VALUE>,\
                        'one',          3,      1,\
                        'two',          3,      2,\
                        'three',        5,      3,\
                        'four',         4,      4,\
                        'five',         4,      5,\
                        'six',          3,      6,\
                        'seven',        5,      7,\
                        'eight',        5,      8,\
                        'nine',         4,      9

                        if offset + LEN < $
                                load c:LEN from offset
                                if c = TEXT
                                        last = VALUE
                                        if state
                                                total = total + last * 10
                                                state = 0
                                        end if
                                        break
                                end if
                        end if
                end iterate
        end if

; DEBUG
;repeat 1, T:total
;       display " ",`T
;end repeat

end repeat
end virtual
repeat 1, T:total
        display 10,9,"Sum of all of the calibration values: ",`T,10
end repeat

... fasmg makes integrating through the file bytes simple. Nothing fancy is done to reduce code size or speed up use.

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

Last edited by bitRAKE on 03 Dec 2023, 20:14; edited 4 times in total

03 Dec 2023, 07:29

bitRAKE

Joined: 21 Jul 2003
Posts: 4060
Location: vpcmpistri

bitRAKE 03 Dec 2023, 07:37

Since all lines begin with "Game", we create a calminstruction to process the text and use comment retained mode to process semi-colons. Adding a line terminator "|" simplifies the code. Too much error checking, but it doesn't hurt.

Day 2, Part 1:

Code:

total = 0 ; 2331
retaincomments
calminstruction Game line&
        local game,count,color
        arrange line, line |
        match game : line, line
        jyes ggood
error:
        err 'game!'

red:    check count > 12
        jyes fail
        jump pass
green:  check count > 13
        jyes fail
        jump pass
blue:   check count > 14
        jyes fail
        jump pass

total:
        compute game, game
        compute total, total + game
        exit
pass:
        match |,line
        jyes total
        match =, line, line
        match =; line, line
ggood:
        match count color line, line
        jno error

        match =red, color
        jyes red
        match =green, color
        jyes green
        match =blue, color
        jyes blue
fail:
end calminstruction
include '02.input.txt'
removecomments

repeat 1, T:total
        display 10,9,"Sum of game IDs: ",`T,10
end repeat

Day 2, Part 2:

Code:

total = 0 ; 71585
retaincomments
calminstruction Game line&
        local game,count,color,R,G,B
        compute R,1
        compute G,1
        compute B,1
        arrange line, line |
        match game : line, line
        jyes ggood
error:
        err 'game!'

red:    check count > R
        jno pass
        compute R, count
        jump pass
green:  check count > G
        jno pass
        compute G, count
        jump pass
blue:   check count > B
        jno pass
        compute B, count
        jump pass

total:
        compute total, total + R*G*B
        exit
pass:
        match |,line
        jyes total
        match =, line, line
        match =; line, line
ggood:
        match count color line, line
        jno error

        match =red, color
        jyes red
        match =green, color
        jyes green
        match =blue, color
        jyes blue
fail:
end calminstruction
include '02.input.txt'
removecomments

repeat 1, T:total
        display 10,9,"Sum of game IDs: ",`T,10
end repeat

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

Last edited by bitRAKE on 03 Dec 2023, 08:36; edited 1 time in total

03 Dec 2023, 07:37

bitRAKE

Joined: 21 Jul 2003
Posts: 4060
Location: vpcmpistri

bitRAKE 03 Dec 2023, 07:47

Day 3 is a little more complex - grid processing. By padding the 2D array of characters we can write simpler processing.

Part 1:

Code:

LINE_LENGTH := 141
total = 0
virtual at 0
db LINE_LENGTH dup '.'
file '03.input.txt'
db LINE_LENGTH dup '.'

number = 0
adjacent = 0
repeat $ - 2*LINE_LENGTH, offset:LINE_LENGTH
        load c:1 from offset
        if '0' <= c & c <= '9' ; number
                number = number * 10 + c - '0'

                ; check symbol locality
                load up:3 from offset - LINE_LENGTH - 1
                load is:3 from offset - 1
                load dn:3 from offset + LINE_LENGTH - 1
                temp = (up shl 48) or (is shl 24) or dn
                while temp
                        t = temp and 0xFF
                        if t <> '.' & t <> 10 & (t < '0' | t > '9')
                                adjacent = 1
                                break
                        end if
                        temp = temp shr 8
                end while
        else ; not in number
                if adjacent
                        total = total + number
                        adjacent = 0
                end if
                number = 0
        end if
end repeat
end virtual
repeat 1, T:total
        display 10,9,"Sum of all of the part numbers in the engine schematic: ",`T,10
end repeat

Part 2: We can reference all gears by the unique asterisk offset. Using vectoring to gather variable length linkages to the offset. Finally, we total only vectors of length two:

Code:

LINE_LENGTH := 141
virtual at 0
db LINE_LENGTH dup '.'
file '03.input.txt'
db LINE_LENGTH dup '.'

number = 0
adjacent = 0
repeat $ - 2*LINE_LENGTH, offset:LINE_LENGTH
        load c:1 from offset
        if '0' <= c & c <= '9' ; number
                number = number * 10 + c - '0'

                temp = offset - LINE_LENGTH - 2
                repeat 3
                        repeat 3
                                load t:1 from temp + %
                                if t = '*'
                                        adjacent = 1
                                        vector = temp + %
                                        break
                                end if
                        end repeat
                        temp = temp + LINE_LENGTH
                end repeat
        else ; not in number
                if adjacent
                        repeat 1, _V:vector, N:number
                                V#_V equ N
                                define Vectors V#_V
                        end repeat
                        adjacent = 0
                end if
                number = 0
        end if
end repeat
end virtual

total = 0
irpv Vector, Vectors
        irpv item, Vector
                if %% = 2
                        value = item
                        indx 2
                        value = value * item
                        total = total + value
                end if
                break
        end irpv
end irpv

repeat 1, T:total/2 ; each of two numbers are linked to '*' gear symbol
        display 10,9,"Sum of all of the part numbers in the engine schematic: ",`T,10
end repeat

To the observant reader, there are some corner cases in our discussion that haven't been fully addressed. Let's delve into one such example to shed more light on these overlooked aspects.

Consider the scenario of chaining multiple gears, denoted as '1*2*3'. In our current data analysis, we've managed to capture linkages '1*2', '2*1', and '3*2'. However, we seem to have overlooked the '2*3' linkage. Adding code to capture this would have been relatively straightforward, but it was omitted.

To gather all possible linkages, one could use the formula: vector =: temp + %. This approach would allow us to collect all the linkages and then store the combined results of these vector values when they are adjacent. An interesting point to note here is also the removal of the break in our double repeat loop. On reflection, this part of the code seems to have no significant function.

Addressing this corner case would have required us to make some assumptions. The detailed explanation or exploration of such complexities is missing in our narrative, which likely explains why this scenario isn't represented in the data we're analyzing. Incorporating these considerations could provide a more comprehensive understanding and ensure that even the less obvious connections aren't overlooked.

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

03 Dec 2023, 07:47

GreaseMonkey

Joined: 06 Dec 2023
Posts: 1

GreaseMonkey 06 Dec 2023, 23:09

OK, that is a really interesting way to solve puzzles.

I've been doing a different challenge, using fasm1 on an emulated 16 MHz 386SX to really test the "should produce a solution in under 15 seconds" design guideline. As a result I've been using the assembler in a more conventional manner. So far all solutions have executed in under 1 second.

Really curious to see how you'd solve Day 5 Part 2 (feeding number ranges through multiple maps).

06 Dec 2023, 23:09

bitRAKE

Joined: 21 Jul 2003
Posts: 4060
Location: vpcmpistri

bitRAKE 25 Apr 2024, 17:18

GreaseMonkey wrote:

Really curious to see how you'd solve Day 5 Part 2 (feeding number ranges through multiple maps).

Sorry for the late reply. I injured by hand during the holiday and didn't get back to these problems. Programmatically, fasmg has several ways to solve these problems at assemble-time. Close to assembly language is the LOAD/STORE mechanism which allows virtual address spaces to be used like memory. More abstractly (which I've been stressing above), the problem data can be manipulated symbolically.

As for multi-dimensional assemble-time work, fasmg has algebraic abstractions or the symbol lookup mechanism itself can transform along a dimension. Then there is my personal favorite, building a table with ITERATE and then INDX to a specific entries.

fasmg is very fast, it's abstractions are lightweight and efficiently implemented.

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

Last edited by bitRAKE on 25 Apr 2024, 17:23; edited 1 time in total

25 Apr 2024, 17:18

bitRAKE

Joined: 21 Jul 2003
Posts: 4060
Location: vpcmpistri

bitRAKE 25 Apr 2024, 17:20

Day 4, Part 1:

Code:

; https://adventofcode.com/2023/day/4
total = 0
macro Card line&
        local wins
        match CARD : W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 | N0 N1 N2 N3 N4 N5 N6 N7 N8 N9 NA NB NC ND NE NF NG NH NI NJ NK NL NM NN NO, line
                wins = 0
                iterate NUM, N0,N1,N2,N3,N4,N5,N6,N7,N8,N9,NA,NB,NC,ND,NE,NF,NG,NH,NI,NJ,NK,NL,NM,NN,NO
                        iterate WIN, W0,W1,W2,W3,W4,W5,W6,W7,W8,W9
                                if NUM = WIN
                                        wins = wins + 1
                                        break
                                end if
                        end iterate
                end iterate
                total = total + ((1 shl wins) shr 1)
        else
                err 'unknown card!'
        end match
end macro
include '04.input.txt'
repeat 1, T:total
        display 10,9,"Total card points: ",`T,10
end repeat

Part 2:

Code:

; https://adventofcode.com/2023/day/4#part2
total = 0 ; 5329815
macro Card line&
        match CARD : W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 | N0 N1 N2 N3 N4 N5 N6 N7 N8 N9 NA NB NC ND NE NF NG NH NI NJ NK NL NM NN NO, line
                ?CARD = 0 ; track matching numbers for card #
                ?CARD.copies = 1 ; track how many of each card
                iterate NUM, N0,N1,N2,N3,N4,N5,N6,N7,N8,N9,NA,NB,NC,ND,NE,NF,NG,NH,NI,NJ,NK,NL,NM,NN,NO
                        iterate WIN, W0,W1,W2,W3,W4,W5,W6,W7,W8,W9
                                if NUM = WIN
                                        ?CARD = ?CARD + 1
                                        break
                                end if
                        end iterate
                end iterate
        else
                err 'unknown card!'
        end match
end macro
include '04.input.txt'

macro CardCopy index*
        repeat ?index, V:index+1
                ?V.copies = ?V.copies + ?index.copies
        end repeat
end macro

repeat 189 ; known cards
        total = total + ?%.copies
        CardCopy %
end repeat

repeat 1, T:total
        display 10,9,"Total scratchcards: ",`T,10
end repeat

25 Apr 2024, 17:20

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum