ejolson
Posts: 12155
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code 2023

Thu Feb 01, 2024 4:49 pm

lurk101 wrote:
Wed Jan 31, 2024 11:25 pm
ejolson wrote:
Wed Jan 31, 2024 8:42 pm
Cool! How long did the build take?
don't know exactly... about 5-10 minutes. Much longer to run the self test.
Did you try the official AArch64 binary?
Didn't.

running your code I get

Code: Select all

pi@pi5:~ $ /opt/julia/usr/bin/julia -t4
               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.10.0 (2023-12-25)
 _/ |\__'_|_|_|\__'_|  |  
|__/                   |

julia> include("day21.jl")
Advent of Code 2023 Day 21 Step Counter

Part 1 There are 3733 reachable garden plots.
Part 2 On the infinite grid 617729401414635 are reachable.

Total execution time 158.801286086 seconds.

julia>
Those are the correct answers for my data set.
Since the 700 MHz Pi Zero took 9504 seconds on day 21, then

9504 / 159 = 59.8

implies the Pi 5 is almost 60 times faster than the Zero. Even though the Pi ratio is an average of very different calculations--two floating point and two integer--the quotient of 59.8 appears consistent with the previously reported 58.3 Pi ratio of the Pi 5.

viewtopic.php?p=2150327#p2150327

According to Fido it's only a coincidence the average between much faster floating point was balanced by the memory bandwidth and turned out about the same. I wonder how much of the execution time was spent collecting garbage.
Last edited by ejolson on Thu Feb 01, 2024 6:28 pm, edited 1 time in total.

ejolson
Posts: 12155
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code 2023

Thu Feb 01, 2024 5:16 pm

ejolson wrote:
Thu Feb 01, 2024 4:49 pm
Since the 700 MHz Pi Zero took 9504 seconds on day 21, then

9504 / 159 = 59.8

implies the Pi 5 is almost 60 times faster than the Zero. Even though the Pi ratio is an average of very different calculations--two floating point and two integer--the quotient of 59.8 is remarkably consistent with the previously reported 58.3 Pi ratio of the Pi 5.

viewtopic.php?p=2150327#p2150327

According to Fido it's only a coincidence the average between much faster floating point was balanced by the memory bandwidth and turned out about the same. I wonder how much of the execution time was spent collecting garbage.
Here is a run on a Pi 4B at 1500 MHz:

Code: Select all

$ julia -t4 # Pi 4B 1500 MHz
               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.6.7 (2022-07-19)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

julia> include("day21p.jl")
Advent of Code 2023 Day 21 Step Counter

Part 1 There are 3682 reachable garden plots.
Part 2 On the infinite grid 609012263058042 are reachable.

Total execution time 387.70752418 seconds.
Dividing as

388 / 159 = 2.44

seems consistent with Geekbench 6.2

Image
https://www.raspberrypi.com/news/benchm ... erry-pi-5/

which gives a quotient of 2.2 in the official blog.
Last edited by ejolson on Thu Feb 01, 2024 6:29 pm, edited 2 times in total.

ejolson
Posts: 12155
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code 2023

Thu Feb 01, 2024 6:00 pm

lurk101 wrote:
Wed Jan 31, 2024 11:25 pm
running your code I get

Code: Select all

pi@pi5:~ $ /opt/julia/usr/bin/julia -t4
               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.10.0 (2023-12-25)
 _/ |\__'_|_|_|\__'_|  |  
|__/                   |

julia> include("day21.jl")
Advent of Code 2023 Day 21 Step Counter

Part 1 There are 3733 reachable garden plots.
Part 2 On the infinite grid 617729401414635 are reachable.

Total execution time 158.801286086 seconds.
Since there are now desktop computers based on the 64-core Ampere Altra

https://www.servethehome.com/asrock-rac ... -you-want/

I decided to try the free 4-core Altra instance in the Oracle cloud.

Code: Select all

$ julia -t4  # Ampere Altra using 4 cores
               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.6.7 (2022-07-19)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

julia> include("day21p.jl")
Advent of Code 2023 Day 21 Step Counter

Part 1 There are 3682 reachable garden plots.
Part 2 On the infinite grid 609012263058042 are reachable.

Total execution time 129.909419863 seconds.
On a core-per-core basis the Altra is 22 percent faster than the Pi 5.

A microATX motherboard-processor combo costs $1500

https://www.newegg.com/p/N82E16813140134

and 64 cores are like having 16 Raspberry Pi computers; therefore, the price per virtual Pi turns out to be

1500 / 16 = 93.75

One still needs to install RAM and RAM has recently increased in price. At any rate, I find it surprising how well the Pi 5 competes on this simple price-performance metric.

ejolson
Posts: 12155
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code 2023

Sun Feb 04, 2024 7:34 am

ejolson wrote:
Thu Feb 01, 2024 4:49 pm
Since the 700 MHz Pi Zero took 9504 seconds on day 21, then

9504 / 159 = 59.8

implies the Pi 5 is almost 60 times faster than the Zero.
As there is still no Pi 5 for me, here is day 22 on the Zero.

Code: Select all

julia> include("day22.jl") # Pi Zero 700 MHz
Advent of Code 2023 Day 22 Sand Slabs

Part 1 There are 459 safe bricks
Part 2 There are 75784 bricks that fall

Total execution time 19.680736116 seconds.

julia> main()
Advent of Code 2023 Day 22 Sand Slabs

Part 1 There are 459 safe bricks
Part 2 There are 75784 bricks that fall

Total execution time 5.751008091 seconds.

julia> main()
Advent of Code 2023 Day 22 Sand Slabs

Part 1 There are 459 safe bricks
Part 2 There are 75784 bricks that fall

Total execution time 5.67593156 seconds.
It took me a while to realize the blocks in the input where not arranged in z order. After sorting, the blocks are dropped one unit at a time until they land on something. Compared to day 21 the program is quite speedy and the warmed up execution time is under the 15 second limit. As I'm again out of dog treats the dog developer refused to optimize the solution.

The Julia source code is

Code: Select all

#=  Advent of Code 2023 Day 22 Sand Slabs
    Written 2024 by Eric Olson =#

struct DoExit <: Exception
end

function gobble(s::String,m::String)::Tuple{String,Bool}
    if length(s)<length(m)
        return s,false
    end
    if s[1:length(m)]==m
        return s[length(m)+1:end],true
    end
    return s,false
end

function wskip(s::String)::String
    for i=1:length(s)
        if !isspace(s[i])
            return s[i:end]
        end
    end
    return ""
end

function vskip(data,i::Int)::Int
    while i<=length(data)&&length(data[i])==0
        i+=1
    end
    return i
end 

function getalpha(s::String)::Tuple{String,String}
    for i=1:length(s)
        if !isletter(s[i])
            return s[i:end],s[1:i-1]
        end
    end
    return "",s
end

function getint(s::String)::Tuple{String,Int64}
    n=Int64(0)
    for i=1:length(s)
        if s[i]>='0'&&s[i]<='9'
            n=n*10+Int64(s[i]-'0')
        else
            return s[i:end],n
        end
    end
    return "",n
end

mutable struct Point
    x::Int
    y::Int
    z::Int
end

mutable struct Block
    a::Point
    b::Point
    u::Set{Int}
    d::Set{Int}
    Block(a,b)=new(a,b,Set{Int}(),Set{Int}())
end

function getblock(s::String)::Block
    r=s
    s,ax=getint(s); ax+=1
    if begin s,f=gobble(s,","); !f end
        println(r,"\nCan't find comma after a.x coordinate!")
        throw(DoExit())
    end
    s,ay=getint(s); ay+=1
    if begin s,f=gobble(s,","); !f end
        println(r,"\nCan't find comma after a.y coordinate!")
        throw(DoExit())
    end
    s,az=getint(s)
    if begin s,f=gobble(s,"~"); !f end
        println(r,"\nCan't find tilde after a.z coordinate!")
        throw(DoExit())
    end
    s,bx=getint(s); bx+=1
    if begin s,f=gobble(s,","); !f end
        println(r,"\nCan't find comma after b.x coordinate!")
        throw(DoExit())
    end
    s,by=getint(s); by+=1
    if begin s,f=gobble(s,","); !f end
        println(r,"\nCan't find comma after b.y coordinate!")
        throw(DoExit())
    end
    s,bz=getint(s)
    if length(s)>0
        println(r,"\nCharacters after at end of location!")
        throw(DoExit())
        
    end
    return Block(Point(ax,ay,az),Point(bx,by,bz))
end

mutable struct Visible
    k::Int
    z::Int
end

function drop(topo::Matrix{Visible},block::Block,b::Int)::Bool
    dx=block.b.x-block.a.x
    dy=block.b.y-block.a.y
    dz=block.b.z-block.a.z
    imax=abs(dx)
    if imax<abs(dy) imax=abs(dy) end
    if imax<abs(dz) imax=abs(dz) end
    f=false
    for i=0:imax
        x=block.a.x+i*sign(dx)
        y=block.a.y+i*sign(dy)
        z=block.a.z+i*sign(dz)
        if topo[x,y].z>=z-1
            f=true
            push!(block.d,topo[x,y].k)
        end
    end
    if f
        for i=0:imax
            x=block.a.x+i*sign(dx)
            y=block.a.y+i*sign(dy)
            z=block.a.z+i*sign(dz)
            topo[x,y].k=b
            if topo[x,y].z<z 
                topo[x,y].z=z
            end
        end
    end
    return f
end

function part1(blocks::Vector{Block})::Int64
    K=length(blocks)
    disint=ones(Bool,K)
    for k=2:K
        if length(blocks[k].d)==1
            for i in blocks[k].d
                disint[i]=false
            end
        end
    end
    return sum(disint)
end

function part2(blocks::Vector{Block})::Int64
    K=length(blocks)
    function poof(k::Int,disint::Set{Int})::Int
        push!(disint,k)
        r=1
        for i in blocks[k].u
            d=setdiff(blocks[i].d,disint)
            if length(d)==0
                r+=poof(i,disint)
            end
        end
        return r
    end
    s=0
    for k=2:K
        s+=poof(k,Set{Int}())-1
    end
    return s
end

function doinit()
    data=String[]
    open("day22.txt","r") do fp
        data=readlines(fp)
    end
    M=0; N=0; K=length(data)+1
    blocks=Vector{Block}(undef,K)
    blocks[1]=Block(Point(1,1,0),Point(0,0,0))
    for k=2:K
        s=data[k-1]
        r=getblock(s)
        if M<r.a.x M=r.a.x end
        if N<r.a.y N=r.a.y end
        if M<r.b.x M=r.b.x end
        if N<r.b.y N=r.b.y end
        blocks[k]=r
    end
    blocks[1].b.x=M; blocks[1].b.y=N
    P=sortperm([blocks[k].a.z for k=1:K])
    blocks=blocks[P]
    topo=Matrix{Visible}(undef,M,N)
    for j=1:N
        for i=1:M
            topo[i,j]=Visible(1,0)
        end
    end
    for k=2:K
        while !drop(topo,blocks[k],k)
            blocks[k].a.z-=1
            blocks[k].b.z-=1
        end
        for i in blocks[k].d
            push!(blocks[i].u,k)
        end
    end
    p1=part1(blocks)
    p2=part2(blocks)
    println("Part 1 There are ",p1," safe bricks")
    println("Part 2 There are ",p2," bricks that fall")
end

function main()
    t=@elapsed try
        println("Advent of Code 2023 Day 22 Sand Slabs\n")
        doinit()
        throw(DoExit())
    catch r
        if !isa(r,DoExit)
            rethrow(r)
        end
    end
    println("\nTotal execution time ",t," seconds.")
end 

main()
Other than the inefficient way mentioned already in which the blocks are dropped, it's notable that the graph was created using indices into an array rather than pointers. Julia's built-in sets and set difference operators keep track of the edges in the graph and which blocks fall.

ejolson
Posts: 12155
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code 2023

Mon Feb 05, 2024 5:49 am

ejolson wrote:
Sun Feb 04, 2024 7:34 am
Compared to day 21 the program is quite speedy and the warmed up execution time is under the 15 second limit.
Oh no! Is part 1 of day 23 NP-complete?

https://en.wikipedia.org/wiki/Longest_path_problem

Fido's tail has been wagging all afternoon about how the QuantumBark™ accelerator currently under development is well suited for solving NP-hard Advent of code puzzles. Apparently the quantum circuits can be programmed using QBasic in place of OpenQASM.

I couldn't help it and mumbled that QBasic ran just fine under MS-DOS. Fortunately, the dog developer wasn't paying attention.

Do the slippery slopes turn the forest paths into a directed acyclic graph?
Last edited by ejolson on Tue Feb 06, 2024 4:29 am, edited 1 time in total.

ejolson
Posts: 12155
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code 2023

Tue Feb 06, 2024 4:28 am

ejolson wrote:
Mon Feb 05, 2024 5:49 am
ejolson wrote:
Sun Feb 04, 2024 7:34 am
Compared to day 21 the program is quite speedy and the warmed up execution time is under the 15 second limit.
Oh no! Is part 1 of day 23 NP-complete?

https://en.wikipedia.org/wiki/Longest_path_problem

Fido's tail has been wagging all afternoon about how the QuantumBark™ accelerator currently under development is well suited for solving NP-hard Advent of code puzzles. Apparently the quantum circuits can be programmed using QBasic in place of OpenQASM.

I couldn't help it and mumbled that QBasic ran just fine under MS-DOS. Fortunately, the dog developer wasn't paying attention.

Do the slippery slopes turn the forest paths into a directed acyclic graph?
Day 23 part 1 was indeed a directed acyclic graph so it is now solved in linear time. On the other hand, part 2 removed the slippery slopes so there may yet be a market for the QuantumBark™ accelerator. Needless to say the dog developer has become quite noisy in anticipation of a large windfall of dog treets.

I wonder if a GPU would be more economical.

ejolson
Posts: 12155
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code 2023

Tue Feb 06, 2024 5:35 am

ejolson wrote:
Tue Feb 06, 2024 4:28 am
Day 23 part 1 was indeed a directed acyclic graph so it is now solved in linear time. On the other hand, part 2 removed the slippery slopes so there may yet be a market for the QuantumBark™ accelerator. Needless to say the dog developer has become quite noisy in anticipation of a large windfall of dog treets.

I wonder if a GPU would be more economical.
Instead of an accelerator I tried a brute force search on the Pi Zero. The results were

Code: Select all

julia> include("day23.jl") # Pi Zero 700 MHz
Advent of Code 2023 Day 23 A Long Walk

Part 1 The longest slippery hike is 2310
Part 2 The surprisingly dry hike is 6738

Total execution time 450.656920577 seconds.

julia> main()
Advent of Code 2023 Day 23 A Long Walk

Part 1 The longest slippery hike is 2310
Part 2 The surprisingly dry hike is 6738

Total execution time 448.965126484 seconds.
Unsurprisingly, it's not under 15 seconds.

For reference the Julia program was

Code: Select all

#=  Advent of Code 2023 Day 23 A Long Walk
    Written 2024 by Eric Olson =#

import Base.isequal, Base.hash

struct DoExit <: Exception
end

mutable struct Edge
    k::Int
    d::Int
end
function isequal(a::Edge,b::Edge)::Bool
    return a.k==b.k&&a.d==b.d
end
function hash(a::Edge)::UInt
    return UInt(a.k)<<16|UInt(a.d)
end

mutable struct Point
    i::Int
    j::Int
end

function isequal(a::Point,b::Point)::Bool
    return a.i==b.i&&a.j==b.j
end
function hash(a::Point)::UInt
    return UInt(a.i)<<16|UInt(a.j)
end

mutable struct Vert
    p::Point
    e::Set{Edge}
    w::Int
    Vert(p::Point,e::Set{Edge})=new(p,e,0)
end

@isdefined(dirs) || const dirs=
    [Point(0,1),Point(-1,0),Point(0,-1),Point(1,0)]
@isdefined(slopes) || const slopes=['>','^','<','v']

function getgraph(data::Vector{String})::Vector{Vert}
    M=length(data); N=length(data[1])
    V=[Vert(Point(1,2),Set{Edge}())]
    ijtok=Dict{Point,Int}(V[1].p=>1)
    function look(q)::Char
        if q.i<1||q.i>M||q.j<1||q.j>N
            return '#'
        end
        return data[q.i][q.j]
    end
    function nextv(data::Vector{String},v::Vert,d::Int)
        function move(v::Vert,d::Int)::Tuple{Point,Int,Int}
            p=v.p
            dp=dirs[d]
            p=Point(p.i+dp.i,p.j+dp.j)
            c=look(p)
            if c!='.'&&c!=slopes[d]
                return p,d,0
            end
            r=(d+1)%4+1
            f=true
            function walk()::Int
                for l=1:length(dirs)
                    if l==r continue end
                    dp=dirs[l]
                    q=Point(p.i+dp.i,p.j+dp.j)
                    c=look(q)
                    if c=='#' continue
                    elseif c==slopes[l]
                        f=false
                    end
                    r=(l+1)%4+1
                    p=q
                    return l
                end
                f=false
                return 0
            end
            s=1
            while f
                d=walk()
                if d>0 s+=1 end
            end
            return p,d,s
        end
        p,d,s=move(v,d)
        if s==0 return end
        if d>0&&data[p.i][p.j]==slopes[d]
            dp=dirs[d]
            p=Point(p.i+dp.i,p.j+dp.j)
            s+=1
        end
        z=get(ijtok,p,nothing)
        if z==nothing
            push!(V,Vert(p,Set{Edge}()))
            z=length(V)
            ijtok[p]=z
        end
        push!(v.e,Edge(z,s))
        v=V[z]
        if d>0
            for l=1:4
                nextv(data,v,l)
            end
        end
        return
    end
    nextv(data,V[1],4)
    return V
end

mutable struct Node
    v::Vert
    n::Int
end

function mkpriority()
    heap=Node[]
    function enqueue(p::Node)
        push!(heap,p)
        r=length(heap)
        while true
            s=r÷2
            if s<1 break end
            if heap[s].n<=p.n break end
            heap[r]=heap[s]
            r=s
        end
        heap[r]=p
    end
    function dequeue()::Node
        if length(heap)==0
            println("Tried to remove nonexistent point!\n")
            throw(DoExit())
        end
        t=pop!(heap)
        if length(heap)==0 return t end
        p=heap[1]
        s0=1
        while true
            r0=2*s0; r1=r0+1
            if r0>length(heap) break end
            s1=r0
            if r1<=length(heap)
                if heap[r0].n>heap[r1].n
                    s1=r1
                end
            end
            if t.n<=heap[s1].n break end
            heap[s0]=heap[s1]
            s0=s1
        end
        heap[s0]=t
        return p
    end
    return enqueue,dequeue
end

function part1(V::Vector{Vert})::Int
    enq,deq=mkpriority()
    enq(Node(V[1],0))
    r=0
    while length(enq.heap)>0
        z=deq()
        r=z.v.w
        for e in z.v.e
            v=V[e.k]
            w=z.v.w+e.d
            if v.w<w
                v.w=w
                enq(Node(v,w))
            end
        end
    end
    return r
end

function meltice(V::Vector{Vert})::Int
    gend=0
    for i=2:length(V)
        if length(V[i].e)==0
            gend=i
            break
        end
    end
    if gend==0
        println("Can't find the end of the walk!")
        throw(DoExit())
    end
    for i=2:length(V)
        v=V[i]
        for e in v.e
            if e.k!=gend
                push!(V[e.k].e,Edge(i,e.d))
            end
        end
    end
    return gend
end

function part2(V::Vector{Vert})::Int
    gend=meltice(V)
    for i=1:length(V)
        V[i].w=0
    end
    function brute(k::Int,w::Int)::Int
        if k==gend
            return w
        end
        v=V[k]
        nmax=0
        for e in v.e
            if V[e.k].w==0
                V[e.k].w=w+e.d
                n=brute(e.k,w+e.d)
                if nmax<n nmax=n end
                V[e.k].w=0
            end
        end
        return nmax
    end
    return brute(1,0)
end

function doinit()
    data=String[]
    open("day23.txt","r") do fp
        data=readlines(fp)
    end
    V=getgraph(data)
    p1=part1(V)
    p2=part2(V)
    println("Part 1 The longest slippery hike is ",p1)
    println("Part 2 The surprisingly dry hike is ",p2)
end

function main()
    t=@elapsed try
        println("Advent of Code 2023 Day 23 A Long Walk\n")
        doinit()
        throw(DoExit())
    catch r
        if !isa(r,DoExit)
            rethrow(r)
        end
    end
    println("\nTotal execution time ",t," seconds.")
end 

main()
I think the slowness comes from the 37 million memory allocations which occur during the brute force search. I suspect it will significantly faster if those are eliminated.
Last edited by ejolson on Tue Feb 06, 2024 6:13 am, edited 1 time in total.

ejolson
Posts: 12155
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code 2023

Tue Feb 06, 2024 5:56 am

ejolson wrote:
Tue Feb 06, 2024 5:35 am
I think the slowness comes from the 37 million memory allocations which occur during the brute force search. I suspect it will significantly faster if those are eliminated.
Efficient Julia programs are a mystery. I removed the nesting of the brute function from inside the part2 function and obtained a factor 10 improvement in speed.

Code: Select all

julia> include("day23.jl") # Pi Zero 700 Mhz
Advent of Code 2023 Day 23 A Long Walk

Part 1 The longest slippery hike is 2310
Part 2 The surprisingly dry hike is 6738

Total execution time 52.223170457 seconds.

julia> main()
Advent of Code 2023 Day 23 A Long Walk

Part 1 The longest slippery hike is 2310
Part 2 The surprisingly dry hike is 6738

Total execution time 44.623230594 seconds.
The total number of memory allocations were reduced to about a million. Almost all of those allocations occur during part 1 with only 91 now related to the brute force search.

The improved program is

Code: Select all

#=  Advent of Code 2023 Day 23 A Long Walk
    Written 2024 by Eric Olson =#

import Base.isequal, Base.hash

struct DoExit <: Exception
end

mutable struct Edge
    k::Int
    d::Int
end
function isequal(a::Edge,b::Edge)::Bool
    return a.k==b.k&&a.d==b.d
end
function hash(a::Edge)::UInt
    return UInt(a.k)<<16|UInt(a.d)
end

mutable struct Point
    i::Int
    j::Int
end

function isequal(a::Point,b::Point)::Bool
    return a.i==b.i&&a.j==b.j
end
function hash(a::Point)::UInt
    return UInt(a.i)<<16|UInt(a.j)
end

mutable struct Vert
    p::Point
    e::Set{Edge}
    w::Int
    Vert(p::Point,e::Set{Edge})=new(p,e,0)
end

@isdefined(dirs) || const dirs=
    [Point(0,1),Point(-1,0),Point(0,-1),Point(1,0)]
@isdefined(slopes) || const slopes=['>','^','<','v']

function getgraph(data::Vector{String})::Vector{Vert}
    M=length(data); N=length(data[1])
    V=[Vert(Point(1,2),Set{Edge}()),Vert(Point(M,N-1),Set{Edge}())]
    ijtok=Dict{Point,Int}(V[1].p=>1,V[2].p=>2)
    function look(q)::Char
        if q.i<1||q.i>M||q.j<1||q.j>N
            return '#'
        end
        return data[q.i][q.j]
    end
    function nextv(data::Vector{String},v::Vert,d::Int)
        function move(v::Vert,d::Int)::Tuple{Point,Int,Int}
            p=v.p
            dp=dirs[d]
            p=Point(p.i+dp.i,p.j+dp.j)
            c=look(p)
            if c!='.'&&c!=slopes[d]
                return p,d,0
            end
            r=(d+1)%4+1
            f=true
            function walk()::Int
                for l=1:length(dirs)
                    if l==r continue end
                    dp=dirs[l]
                    q=Point(p.i+dp.i,p.j+dp.j)
                    c=look(q)
                    if c=='#' continue
                    elseif c==slopes[l]
                        f=false
                    end
                    r=(l+1)%4+1
                    p=q
                    return l
                end
                f=false
                return 0
            end
            s=1
            while f
                d=walk()
                if d>0 s+=1 end
            end
            return p,d,s
        end
        p,d,s=move(v,d)
        if s==0 return end
        if d>0&&data[p.i][p.j]==slopes[d]
            dp=dirs[d]
            p=Point(p.i+dp.i,p.j+dp.j)
            s+=1
        end
        z=get(ijtok,p,nothing)
        if z==nothing
            push!(V,Vert(p,Set{Edge}()))
            z=length(V)
            ijtok[p]=z
        end
        push!(v.e,Edge(z,s))
        v=V[z]
        if d>0
            for l=1:4
                nextv(data,v,l)
            end
        end
        return
    end
    nextv(data,V[1],4)
    return V
end

mutable struct Node
    v::Vert
    n::Int
end

function mkpriority()
    heap=Node[]
    function enqueue(p::Node)
        push!(heap,p)
        r=length(heap)
        while true
            s=r÷2
            if s<1 break end
            if heap[s].n<=p.n break end
            heap[r]=heap[s]
            r=s
        end
        heap[r]=p
    end
    function dequeue()::Node
        if length(heap)==0
            println("Tried to remove nonexistent point!\n")
            throw(DoExit())
        end
        t=pop!(heap)
        if length(heap)==0 return t end
        p=heap[1]
        s0=1
        while true
            r0=2*s0; r1=r0+1
            if r0>length(heap) break end
            s1=r0
            if r1<=length(heap)
                if heap[r0].n>heap[r1].n
                    s1=r1
                end
            end
            if t.n<=heap[s1].n break end
            heap[s0]=heap[s1]
            s0=s1
        end
        heap[s0]=t
        return p
    end
    return enqueue,dequeue
end

function part1(V::Vector{Vert})::Int
    enq,deq=mkpriority()
    enq(Node(V[1],0))
    while length(enq.heap)>0
        z=deq()
        for e in z.v.e
            v=V[e.k]
            w=z.v.w+e.d
            if v.w<w
                v.w=w
                enq(Node(v,w))
            end
        end
    end
    return V[2].w
end

function meltice(V::Vector{Vert})
    for i=2:length(V)
        v=V[i]
        for e in v.e
            if e.k!=2
                push!(V[e.k].e,Edge(i,e.d))
            end
        end
    end
end

function brute(V::Vector{Vert},k::Int,w::Int)::Int
    if k==2
        return w
    end
    v=V[k]
    nmax=0
    for e in v.e
        if V[e.k].w==0
            V[e.k].w=w+e.d
            n=brute(V,e.k,w+e.d)
            if nmax<n nmax=n end
            V[e.k].w=0
        end
    end
    return nmax
end

function part2(V::Vector{Vert})::Int
    meltice(V)
    for i=1:length(V)
        V[i].w=0
    end
    return brute(V,1,0)
end

function doinit()
    data=String[]
    open("day23.txt","r") do fp
        data=readlines(fp)
    end
    V=getgraph(data)
    p1=part1(V)
    p2=part2(V)
    println("Part 1 The longest slippery hike is ",p1)
    println("Part 2 The surprisingly dry hike is ",p2)
end

function main()
    t=@elapsed try
        println("Advent of Code 2023 Day 23 A Long Walk\n")
        doinit()
        throw(DoExit())
    catch r
        if !isa(r,DoExit)
            rethrow(r)
        end
    end
    println("\nTotal execution time ",t," seconds.")
end 

main()
The lesson I learned is recursive closures are expensive. It's possible a suitable let block or type annotation might allow the closures to achieve good performance.

ejolson
Posts: 12155
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code 2023

Wed Feb 07, 2024 4:03 am

ejolson wrote:
Tue Feb 06, 2024 5:56 am
ejolson wrote:
Tue Feb 06, 2024 5:35 am
I think the slowness comes from the 37 million memory allocations which occur during the brute force search. I suspect it will significantly faster if those are eliminated.
Efficient Julia programs are a mystery. I removed the nesting of the brute function from inside the part2 function and obtained a factor 10 improvement in speed.
Day 23 on a Pi 4B yields

Code: Select all

julia> include("day23.jl") # Pi 4B 1500 MHz
Advent of Code 2023 Day 23 A Long Walk

Part 1 The longest slippery hike is 2310
Part 2 The surprisingly dry hike is 6738

Total execution time 5.015553982 seconds.

julia> main()
Advent of Code 2023 Day 23 A Long Walk

Part 1 The longest slippery hike is 2310
Part 2 The surprisingly dry hike is 6738

Total execution time 3.98932521 seconds.

julia> main()
Advent of Code 2023 Day 23 A Long Walk

Part 1 The longest slippery hike is 2310
Part 2 The surprisingly dry hike is 6738

Total execution time 4.110047438 seconds.
Since that's under 15 seconds I'll move on to day 24 and hopefully 25 before the Advent of code turns into Lent.

ejolson
Posts: 12155
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code 2023

Wed Feb 07, 2024 7:55 am

ejolson wrote:
Wed Feb 07, 2024 4:03 am
Since that's under 15 seconds I'll move on to day 24 and hopefully 25 before the Advent of code turns into Lent.
Part 2 of day 24 turned out to be an opportunity to use high-precision floating point. This took more than 15 seconds on the Pi Zero.

Code: Select all

julia> include("day24.jl") # Pi Zero 700 MHz
Advent of Code 2023 Day 24 Never Tell Me The Odds

Part 1 Intersections in the test area are 24627
Part 2 The sum of x, y and z is 527310134398221

Total execution time 66.87435158 seconds.

julia> main()
Advent of Code 2023 Day 24 Never Tell Me The Odds

Part 1 Intersections in the test area are 24627
Part 2 The sum of x, y and z is 527310134398221

Total execution time 50.348864518 seconds.
Unfortunately, I tried the code from

https://github.com/lurk101/AoC-2023-cplusplus

and obtained

Code: Select all

$ ./lurk24 # Pi Zero 700 MHz
--- Day 24: Never Tell Me The Odds ---
part 1 - 24627
part 2 - 527310134398219
Elapsed - 50.048 ms.
I wonder if there is a way to simplify the algebra to avoid the loss of precision.

For reference, my data is

Code: Select all

233210433951170, 272655040388795, 179982504986147 @ 39, -98, 166
385274025881243, 351578921558552, 375160114124378 @ -71, -36, -9
298962016918939, 322446494312107, 293073189215975 @ 36, 8, 96
201717428991179, 262965089923292, 196011482381270 @ 92, -490, -114
247277712435905, 218345997267326, 196010243400590 @ -165, -58, -21
352675244632049, 554364732018242, 152625975899360 @ -14, -223, 247
324422391745634, 227138986518940, 108773241649847 @ -47, 91, 312
313067186829719, 462648141629189, 246008354182145 @ -32, -268, 104
248189680078635, 407471031162962, 290189220302863 @ 84, -111, 82
199505021061112, 177980659229372, 175893468794335 @ 75, 219, -136
323521328529479, 153391146336101, 520509666624452 @ 8, 190, -153
360051136858637, 298827430321256, 336098642729624 @ -33, 31, 46
367582428636269, 353752754593133, 455721090356150 @ -22, -10, -51
211477679844979, 203677879111232, 217560677966690 @ 21, -6, -258
218366027555690, 91153932623633, 169742494255475 @ 55, 516, 174
288792682769846, 151081271429165, 316680362356580 @ 29, 198, 39
400036733736580, 365852984506581, 406363416106765 @ -121, -82, -86
243674722027939, 264638195629846, 368019298840514 @ 48, -10, -195
332472697757909, 255887072597627, 449982813510170 @ -14, 72, -103
293819507985671, 365421753329232, 320423714581815 @ 40, -41, 64
183795219388603, 164835194289157, 182094814151316 @ 164, 184, 203
366382639583285, 522460208371841, 518912456550689 @ -38, -210, -150
278030923313372, 474502522717304, 278007597919598 @ 25, -273, 61
184999670575064, 304820097537788, 122671272945698 @ 173, -157, 321
265320160337191, 209979205841084, 187675399475264 @ -18, 93, 162
255003872135235, 187028804687876, 407151799392366 @ 42, 150, -202
232101686193635, 213975266196382, 240273621582836 @ -56, -16, -240
240450116917919, 291888137519462, 173873024655080 @ -126, -500, 110
272272783256099, 179409072253472, 234062260919450 @ -131, 168, -51
258328493647231, 291203717558176, 1069885971366 @ 6, -85, 583
308480795834427, 375221170112166, 191413358004718 @ -148, -344, 143
318965385523139, 449168722347464, 524505928207346 @ -77, -325, -428
315428275959716, 320608674825977, 347102330296784 @ -13, -26, -13
265804330221453, 202452363951731, 254036584668891 @ -70, 96, -68
248444418711669, 229841285103942, 226914597591080 @ -19, 10, 12
227395285887150, 257325944365101, 70101971531074 @ 15, -148, 577
224719946426892, 475040312860836, 153333865934499 @ 69, -613, 242
344114892644297, 270105569149106, 304267086374202 @ -101, 12, -7
320857919431207, 217110959414744, 196143006133728 @ -24, 111, 187
410690148490391, 362551894817732, 320880138922346 @ -121, -66, 37
315678167593799, 310902164439092, 311011187282990 @ -153, -162, -150
284162696329517, 416472913289144, 295799028470984 @ -215, -793, -340
129718901789310, 163245969554691, 216967791295737 @ 249, 188, 146
209964965625112, 191161250819537, 165388796738017 @ -25, 54, 82
497673110723211, 386499996540904, 291331122466962 @ -160, -49, 106
320457813756275, 281605309858328, 237722774472098 @ -190, -109, 15
259221111410294, 226809538368362, 251163917228960 @ -33, 33, -33
151145084542716, 130981648419475, 211580753667646 @ 231, 256, 133
239808287365644, 261920251496762, 276405310385540 @ 77, 33, 51
197726725612939, 82924950628456, 179987257304506 @ 123, 983, 5
241050954384837, 183215659641108, 354255673424906 @ 77, 157, -63
244313293798068, 247257935609159, 212779037837148 @ 41, 18, 115
65408297713475, 57213841527206, 185313960119735 @ 316, 321, 204
213464627894059, 86598732993256, 266870833653114 @ 78, 515, -185
231737597144849, 223510555290722, 213894690906560 @ 35, 32, 56
353131713528389, 301010156323777, 361300184449735 @ -122, -44, -110
210230261973787, 92476419248104, 254715385528386 @ 62, 655, -328
227008099340099, 156979790581134, 224213055692070 @ -32, 298, -161
210017680134353, 191191733968714, 160479904438100 @ 31, 88, 174
304280239427448, 321473363430832, 334898721210818 @ -9, -41, -15
267558481716839, 268029989177432, 305049430365950 @ -11, -29, -88
186217090156385, 109133442305270, 122793773229323 @ 166, 313, 308
318213640730391, 398018375578773, 495253231503708 @ 24, -58, -97
290701720322309, 305430434394176, 150675954587450 @ -82, -137, 249
196942378457994, 356313064568915, 330403621930505 @ 143, -234, -156
317630064349157, 327988113634937, 420667383465542 @ 26, 14, -19
307210663909389, 396745266168812, 269500404103700 @ -207, -519, -126
247734440322603, 211037541638632, 425633703630138 @ 57, 109, -223
404292354896369, 418044561757832, 73932436985270 @ -65, -81, 327
272425529225979, 200503642613178, 271391578599980 @ -132, 92, -186
211119943025843, 197686009410326, 183468803904458 @ 16, 32, -15
205698363151069, 152042412981382, 160956188941830 @ 69, 374, 175
157759514155969, 250333392643202, 205728726817150 @ 195, 72, 179
308391291585438, 325079994122717, 432676155319375 @ 17, -6, -76
309299635224904, 234127317978519, 219421624701989 @ -157, 20, 66
382159216227129, 382889401056097, 319693115663330 @ -198, -212, -63
218187489376571, 422566774358632, 312517190522922 @ 109, -241, -20
247545110083163, 192432035403088, 196197001106778 @ -98, 110, 37
231526899779747, 315440878619220, 226641908528446 @ 70, -124, 88
173690679890047, 145807048939104, 165415502811694 @ 275, 377, 160
198519142716261, 271107833643099, 382751271921538 @ 134, -170, -607
220936088721894, 251944246360182, 173486893674620 @ 17, -191, 135
230390644548207, 248868579304448, 211288187422422 @ -15, -147, -28
185557903379714, 200461866178385, 177146250671711 @ 273, -94, -112
290744210240235, 333443315805346, 368972996267237 @ 20, -43, -42
211078204160215, 81389178033560, 299463705825078 @ 107, 411, -124
437889692077409, 431112874926447, 380045465959360 @ -134, -130, -17
268877207746427, 204087465743720, 314922911436458 @ 41, 127, 12
199719087190451, 169213590684689, 228107271345686 @ 124, 220, -123
282380236428839, 411656091846557, 282867940696325 @ 24, -166, 62
397826856342987, 452211758080168, 330373331681146 @ -121, -199, 11
374618586912560, 252615688384091, 414701055188645 @ -53, 80, -46
213861282273674, 271929032410267, 423566291770375 @ 121, 32, -136
274481283519179, 254578847470664, 317281064015738 @ 13, 36, -33
213494888794309, 293466234266568, 228979385511382 @ 113, -49, 103
343411682019371, 404942906921480, 178038706926192 @ -140, -273, 196
192352243335947, 170795309733782, 156307732787006 @ 180, 309, 173
296188169759365, 244256411093954, 149453488908028 @ -18, 57, 251
189342492734919, 314014840719343, 122425570017245 @ 168, -332, 354
247162649115539, 105998776931752, 333214071620470 @ -62, 463, -482
207368289604003, 208550616378928, 178175262907962 @ 45, -58, 25
223109276940134, 194283940821317, 192599536479578 @ -47, 74, -39
175890421522315, 269264174469288, 334198472779386 @ 195, -59, -209
217965898959803, 229627973114324, 176383436151842 @ 16, -112, 103
115618946952539, 264179415714824, 26481777466214 @ 248, 55, 406
322922863045007, 295218163052482, 234199770059264 @ -50, -16, 120
293540216463294, 77079033898158, 331983113702637 @ 33, 281, 38
347580151826636, 552610880311787, 325500008424131 @ -19, -246, 58
169997064298997, 183812696371766, 110099209449658 @ 187, 156, 313
199191323698459, 185261515441772, 160896059282387 @ 68, 99, 66
353493761596321, 274698465927902, 301198392973368 @ -6, 69, 103
186674991963302, 211874452513883, 182967030401237 @ 231, -150, -84
242340518372339, 358344177251432, 181251080906450 @ 53, -193, 188
374043770146209, 474774304086652, 94295788089290 @ -81, -215, 321
210499382481801, 177512186318582, 184632182551292 @ -121, 234, -330
444397067199886, 233002159853181, 134288115474889 @ -111, 106, 266
306337577309473, 277387748008390, 284478350548201 @ -18, 17, 50
346716070516205, 232116346089890, 353561940487520 @ -73, 86, -46
450711584871453, 478200056201838, 284267394541492 @ -195, -238, 70
431538441846127, 451724385734838, 427283549634395 @ -96, -119, -36
219599688402249, 244730862987287, 209874941505970 @ -10, -240, -127
201313427071907, 168601630138128, 157007435499682 @ 97, 262, 200
438249143117269, 424119931464984, 298765861529975 @ -222, -209, 24
215169786915563, 201505002135480, 247795730191514 @ 124, 136, 135
370374106183235, 349924267180376, 381694662475748 @ -36, -17, 7
198274936976747, 189679389651512, 155226209680754 @ 84, 19, 167
188637865692515, 238710086408456, 187527962451662 @ 202, -345, -78
298578119394285, 159415079993552, 314518772814076 @ -129, 219, -188
262617744694139, 63095765371532, 374161116246500 @ 76, 285, 12
263920711620104, 270806325768152, 303212833144640 @ 11, -17, -53
290492632700775, 413091023502423, 485082862014038 @ -96, -430, -603
291219299932034, 206595628820447, 367604455779400 @ 19, 126, -41
260431613882226, 248229048867126, 329084622595363 @ -175, -167, -628
439102049496769, 369530307923446, 371404950446290 @ -162, -79, -31
257968558770714, 281078884795924, 298922329292961 @ 23, -37, -44
301358802493335, 205733437684346, 324809104729369 @ -40, 117, -58
201852329595883, 95473825297336, 94982116864450 @ 132, 353, 374
467684639369729, 264376256912432, 256231916787770 @ -183, 59, 121
283031177126147, 412491770424764, 186653148896594 @ 40, -123, 205
339282828623755, 243512640245882, 349445006190022 @ -28, 84, 7
282107071900583, 308553492651032, 334941273994508 @ 10, -41, -42
394544352562829, 137506031622212, 227643979610898 @ -122, 219, 145
406483682511589, 406376435436337, 262485321255614 @ -102, -106, 117
398570174321774, 464861989857797, 436669770404120 @ -53, -120, -33
277557227178647, 478655596305920, 329087019719498 @ 57, -167, 53
188098681704873, 201182913552424, 196748682285509 @ 170, 95, 96
220824434287762, 25912163965555, 46272290905758 @ 105, 416, 421
328250628245255, 206059181314970, 421991677850024 @ -134, 108, -324
318571081875635, 210542087415780, 503574925874530 @ -38, 116, -281
191806143345159, 326028987539124, 309381155794042 @ 153, -88, -23
384690549589466, 232452348649319, 511439032229471 @ -179, 72, -372
198846084039554, 216265375378557, 225156974398801 @ 133, 34, -22
185109670669244, 12706941956960, 43641783548659 @ 163, 423, 416
221105344157519, 241810380655562, 395248454330840 @ 26, -118, -882
262985831692337, 264306581492108, 233974019746148 @ -79, -115, -28
352980202408139, 481807077700748, 275698734979682 @ -52, -220, 91
245584314526803, 181910661443432, 188073598822350 @ 80, 159, 199
486424326428553, 478483299284374, 489268124278546 @ -331, -328, -307
84607269180419, 31310497114262, 102095256416750 @ 352, 438, 339
249794844265187, 413492647270280, 434505095753282 @ 31, -333, -354
253138459784132, 433721962579099, 314039773803905 @ -29, -604, -246
57063184441840, 2848723329813, 179657077519134 @ 281, 332, 221
212537612086449, 199942000207897, 231491111459510 @ 66, 76, -123
276716997669487, 321230090257675, 98214025033957 @ -88, -242, 400
217313988937643, 207066350283624, 159695593020282 @ -125, -145, 140
373039254978088, 418351417170392, 440315880352976 @ -33, -81, -45
205971263695199, 156423749157962, 235273358276780 @ 54, 372, -458
169032049328168, 191375939510495, 174714756027610 @ 319, 96, 89
241284760156765, 213633705299964, 273986496029776 @ 57, 97, 8
231523435971360, 228489578131039, 235856183447107 @ 5, -22, -82
252983542761269, 299480440400552, 285041416252730 @ 37, -65, -7
438841029654131, 411233172046176, 488186907692295 @ -116, -89, -116
476618445015599, 443378419493992, 235448704267905 @ -128, -97, 166
548515148436339, 369212112656432, 411233084497090 @ -277, -66, -64
235084601447111, 288801002347004, 254905125178070 @ -34, -323, -221
210815474330455, 183771003173272, 169093337712866 @ -25, 139, 51
223453610383232, 259282790436728, 100611635827082 @ 47, -113, 425
409903837974191, 309320061210647, 410213620779925 @ -80, 24, -26
200664501201994, 214208004490011, 170443224746393 @ 93, -140, 66
252107434605449, 108528804920758, 136069139545022 @ -17, 370, 291
343707687775007, 448008675359705, 288140729453288 @ -240, -534, -109
506078467934517, 441535791803524, 207285945417846 @ -171, -107, 191
355379228119331, 373167458767232, 479637645984386 @ -41, -66, -138
193797798537759, 201906209762360, 108370558375644 @ 158, -57, 706
193493291547483, 189753357420014, 304454307069450 @ 156, 108, -751
227264523175811, 227535163030568, 220790078350034 @ 51, 23, 40
217277712229271, 285062930429621, 291971345546024 @ 80, -152, -177
354830252462459, 132099677502728, 201376420384238 @ -32, 215, 192
185341031389468, 250460260179714, 41915697374578 @ 197, -199, 817
294648208196255, 227863682383273, 245974501368731 @ -176, 10, -60
175644806143963, 195231892463304, 162755375935978 @ 317, 41, 142
196480732288294, 201591457358128, 194254859827134 @ 143, 103, 125
531147271206795, 259617234789502, 399336989294874 @ -220, 74, -23
173328857832331, 301587043811133, 192796692515747 @ 180, -20, 186
487366811837399, 263146090734452, 462894050296310 @ -151, 76, -70
287879979651467, 381808901282290, 461197492201210 @ 52, -47, -71
93328649189759, 26248115804612, 49995133784360 @ 290, 377, 390
292553050712949, 248133729492768, 220661696957771 @ 18, 71, 156
247123755360443, 278822927710248, 126447888020746 @ 55, -13, 292
205604258593800, 320800110216493, 242202181198269 @ 131, -58, 106
207286557485215, 159193041484164, 211343065768074 @ -45, 508, -683
261011778004939, 282090662850632, 360754912762250 @ -118, -243, -594
366372507252833, 261730973147386, 313848450194648 @ -95, 46, 18
200675222189585, 213195258457802, 163113489498041 @ 70, -251, 86
229766991676604, 324420786234443, 132764846007159 @ 103, -24, 272
233197540416981, 252663735890655, 189149976637092 @ 30, -58, 131
551758591442549, 317434445725907, 414246348847160 @ -234, 14, -33
266505418321892, 210846000959996, 327070235871119 @ 19, 107, -68
415341778479239, 334137260920643, 498517411363879 @ -152, -48, -224
341243266909844, 313402743468757, 271648670050749 @ -47, -16, 88
429253377166361, 553469201787950, 476558267750136 @ -119, -264, -122
285246964184633, 406063955848160, 236170320081561 @ 22, -153, 130
227382783338389, 229593188301165, 291763979262386 @ 98, 86, 33
371393091005381, 332181332422916, 414664971173030 @ -26, 11, -11
295303657865079, 166167683087264, 226767016642262 @ 33, 177, 162
190511535560235, 9219366352168, 296515859283426 @ 156, 487, -28
320530971757025, 403540372078112, 334498243996214 @ -45, -181, -33
369733277446451, 211936845599162, 168691665080888 @ -56, 124, 228
231181433150507, 273561808328896, 306128452343458 @ 76, -22, -58
214043005397259, 203645084352092, 174825313374850 @ -12, -21, 49
227687623044354, 218571675056187, 199351922241360 @ 41, 40, 91
402517424550319, 523219204178372, 439330837837110 @ -73, -204, -58
392982884025931, 288312405947464, 441558421576890 @ -111, 20, -131
401375240184702, 221198061028482, 541978454454548 @ -115, 109, -249
460789113388994, 269555798627036, 307185128129600 @ -107, 75, 99
146557416689339, 109661508926432, 103473174943010 @ 298, 384, 396
209850871729361, 212165368167476, 162908120703152 @ -61, -259, 80
283865324628374, 286310975082482, 336187281130685 @ 37, 29, 18
363752349292959, 364338119210717, 424832473039980 @ -16, -18, -17
172177969652473, 17105875767158, 304684280315760 @ 219, 678, -236
259508908932596, 277357839909803, 259475847139790 @ 17, -34, 29
202590478447655, 179288341416660, 234590195444154 @ 136, 163, 121
235908430631009, 279316247590842, 216375695579495 @ 22, -139, 48
255033321738497, 330823756187032, 145836279008283 @ -14, -241, 262
294875061213557, 134131943755328, 259096890879686 @ 39, 211, 131
228407861241887, 230478783727664, 201594147304790 @ 19, -27, 54
293412677139998, 451626582277610, 496863056041280 @ -43, -363, -421
215706007850474, 234310175720234, 185835801829460 @ -37, -303, -61
172787440253597, 192472476831530, 116146942741745 @ 310, 81, 504
214750602238147, 195161664305320, 243432974620666 @ 15, 71, -367
195110086900331, 196922406141288, 197386318990650 @ 142, -74, -476
192828459228011, 174093542493704, 164809937334938 @ 172, 258, 70
377690397113389, 537389168721472, 490471586544400 @ -202, -521, -401
186436861369681, 155775820143126, 5978174705268 @ 161, 200, 476
213571050502796, 305021137306949, 172330565977124 @ 101, -148, 195
221845157530388, 255456728002691, 173155151010878 @ 37, -142, 157
205679143768689, 317760416420172, 87602854062535 @ 78, -709, 652
233972821255379, 305083270506712, 274805863721170 @ 25, -227, -140
235592283807893, 410990846676011, 457908691276527 @ 34, -480, -608
417252866685453, 394738457791274, 359865668946440 @ -219, -192, -96
206500202846264, 256535196755432, 135051442506500 @ 47, -481, 383
185695536952651, 191208134840648, 195546369678362 @ 215, 90, -84
210713655879539, 211225913549132, 198113362540310 @ 58, -6, -18
261292203869294, 323241101432198, 456891907896443 @ 83, 21, -50
251060694976859, 281909149925330, 358419293335055 @ 68, 17, -46
298270977956133, 349728958018374, 373151928770270 @ -229, -452, -561
364728658142934, 339476400747642, 445075099076895 @ -57, -31, -106
238259352607679, 402592303972052, 82369731900020 @ -26, -723, 522
327011202003754, 358835293546122, 371425954275210 @ -15, -59, -23
308572379501567, 326520914026184, 270233115165734 @ -211, -297, -128
189003777687369, 279146253002922, 159255565607405 @ 158, -11, 234
470070380998654, 398687409040702, 362740164193475 @ -261, -163, -66
176058988255331, 218202803327892, 229481748393706 @ 184, 89, 97
283701401834475, 286339794135400, 243383449936442 @ -19, -37, 75
322209744902375, 285151041214136, 389223801784910 @ -15, 27, -56
370122298772019, 365467524657632, 201663972146950 @ -24, -21, 199
284873297928479, 217970573267888, 100592743720150 @ 58, 123, 299
202597289456237, 252168926544368, 139168135303676 @ 135, 43, 268
230650641748533, 194871712283483, 191832975676033 @ -10, 102, 68
193383620827930, 211491476351923, 181596667035350 @ 161, -128, -51
408278509872299, 391228450735992, 334570530605610 @ -104, -88, 32
190463197800155, 274896788605448, 201892417058162 @ 194, -845, -304
217407649288665, 217873308026022, 305591970635530 @ 107, 94, -31
233541543357494, 224991057805055, 135605427238331 @ -107, -124, 348
365473205546095, 299518864347167, 310100407412513 @ -48, 24, 66
191333573404187, 145083532071008, 68084568212474 @ 170, 398, 785
501927382552429, 488197499168268, 518403565149304 @ -187, -175, -152
332536358436865, 104281909758699, 306805691121913 @ -10, 248, 70
358093525295609, 378428206009322, 256432384193190 @ -59, -90, 115
266809407954339, 256879986613912, 325844666283860 @ 48, 55, 6
325628425277326, 507254127151315, 192036788366827 @ -159, -604, 152
220086170001408, 145737699276809, 51304253922819 @ 87, 246, 488
200496566225063, 207408289481713, 147102163056478 @ 64, -212, 301
532796896719425, 517023677463188, 472763376344954 @ -423, -407, -295
358660863901069, 369116533440014, 330478204527670 @ -162, -195, -91
314424345559373, 423625375290148, 194045819512100 @ -59, -259, 174
259707879828127, 253646644874172, 219036127033214 @ -6, -11, 87
194944304770111, 207577080765677, 149627219174283 @ 144, -306, 268
227417712097544, 221143693919678, 251872268514275 @ 43, 33, -76
336409926796047, 244516283772396, 345082887082654 @ -24, 83, 13
183637429237578, 207938870704610, 326607369038005 @ 171, 105, -116
209827782077099, 199028826981160, 202030451200634 @ 88, 91, 45
209472323005991, 424563613950778, 281308224244082 @ 106, -532, -123
278630950990928, 399877095615054, 313668553591893 @ 61, -67, 80
273765578214239, 284236428842132, 191116078230050 @ -110, -175, 117
285848786770827, 241340184315272, 438909140515874 @ 56, 99, -42
249240240321872, 176846266507765, 280264883823635 @ -35, 176, -186
347784136150549, 335776861425501, 454380443557293 @ -42, -32, -128
205264221468995, 189072934063788, 218109426994198 @ 70, 106, -250
286964297738209, 232956529638962, 280081708170855 @ -58, 45, -40
in case anyone wants to experiment with rounding errors.

The Julia program was

Code: Select all

#=  Advent of Code 2023 Day 24 Never Tell Me The Odds
    Written 2024 by Eric Olson =#

struct DoExit <: Exception
end

function gobble(s::String,m::String)::Tuple{String,Bool}
    if length(s)<length(m)
        return s,false
    end
    if s[1:length(m)]==m
        return s[length(m)+1:end],true
    end
    return s,false
end

function wskip(s::String)::String
    for i=1:length(s)
        if !isspace(s[i])
            return s[i:end]
        end
    end
    return ""
end

function vskip(data,i::Int)::Int
    while i<=length(data)&&length(data[i])==0
        i+=1
    end
    return i
end 

function getalpha(s::String)::Tuple{String,String}
    for i=1:length(s)
        if !isletter(s[i])
            return s[i:end],s[1:i-1]
        end
    end
    return "",s
end

function getint(s::String)::Tuple{String,Int64}
    n=Int64(0); ε=1
    for i=1:length(s)
        if s[i]=='-'
            ε=-1
        elseif s[i]>='0'&&s[i]<='9'
            n=n*10+Int64(s[i]-'0')
        else
            return s[i:end],ε*n
        end
    end
    return "",ε*n
end

mutable struct Hail
    x::Float64
    y::Float64
    z::Float64
    dx::Float64
    dy::Float64
    dz::Float64
end

function gethail(s::String)::Hail
    r=s
    s,x=getint(wskip(s))
    if begin s,f=gobble(s,","); !f end
        println(r,"\nCan't find comma after x coordinate!")
        throw(DoExit())
    end
    s,y=getint(wskip(s))
    if begin s,f=gobble(s,","); !f end
        println(r,"\nCan't find comma after y coordinate!")
        throw(DoExit())
    end
    s,z=getint(wskip(s))
    s=wskip(s)
    if begin s,f=gobble(s,"@"); !f end
        println(r,"\nCan't find at sign after z coordinate!")
        throw(DoExit())
    end
    s,dx=getint(wskip(s))
    if begin s,f=gobble(s,","); !f end
        println(r,"\nCan't find comma after dx velocity!")
        throw(DoExit())
    end
    s,dy=getint(wskip(s))
    if begin s,f=gobble(s,","); !f end
        println(s)
        println(r,"\nCan't find comma after dy velocity!")
        throw(DoExit())
    end
    s,dz=getint(wskip(s))
    if length(s)>0
        println(r,"\nCharacters after at end of hail specifier!")
        throw(DoExit())
        
    end
    return Hail(x,y,z,dx,dy,dz)
end

function getts(l1::Hail,l2::Hail)::Tuple{Float64,Float64}
    Δ=l1.dx*l2.dy-l1.dy*l2.dx
    if abs(Δ)<1e-12
        return NaN,NaN
    else
        s=-(-l1.dx*l1.y+l1.dx*l2.y+l1.dy*l1.x-l1.dy*l2.x)/Δ
        t=-(l1.x*l2.dy-l2.x*l2.dy-l2.dx*l1.y+l2.dx*l2.y)/Δ
        return t,s
    end
end

function part1(hail::Vector{Hail})::Int
    xmin=200000000000000.0; xmax=400000000000000.0;
#    xmin=7.0; xmax=27.0
    ymin=xmin; ymax=xmax
    K=length(hail)
    c=0
    for i=1:K
        l1=hail[i]
        for j=i+1:K
            l2=hail[j]
            t,s=getts(l1,l2)
            if isnan(t) continue end
            if t>0&&s>0
                x=l1.x+l1.dx*t; y=l1.y+l1.dy*t
                x2=l2.x+l2.dx*s; y2=l2.y+l2.dy*s
                if xmin<=x&&x<=xmax&&ymin<=y&&y<=ymax
                    c+=1
                end
            end
        end
    end
    return c
end

function hailxa(l::Hail)::Tuple{Vector{BigFloat},Vector{BigFloat}}
    return [l.x,l.y,l.z],[l.dx,l.dy,l.dz]
end

function part2(hail::Vector{Hail})::Int64
    K=length(hail)
    x=zeros(BigFloat,3); a=zeros(BigFloat,3)
    function JkDJk(h::Hail)::Tuple{BigFloat,Vector{BigFloat}}
        fJ(dx,da)=dx'*dx-(dx'*da)^2/(da'*da)
        fdxJ(dx,da)=2*(dx-(dx'*da)*da/(da'*da))
        fdaJ(dx,da)=2*(-(dx'*da)*dx/(da'*da)+(dx'*da)^2*da/(da'*da)^2)
        lx,la=hailxa(h);
        dx=x-lx; da=a-la
        Jk=fJ(dx,da); DJk=[fdxJ(dx,da); fdaJ(dx,da)]
        return Jk,DJk
    end
    J=Vector{BigFloat}(undef,K)
    DJ=Matrix{BigFloat}(undef,K,6)
    for i=1:1000
        for k=1:K
            J[k],DJ[k,:]=JkDJk(hail[k])
        end
        η=-DJ\J
        x+=η[1:3]; a+=η[4:6]
        if sqrt(J'*J)<1e-10 break end
    end
    return Int64(round(x[1]+x[2]+x[3]))
end

function doinit()
    data=String[]
    open("day24.txt","r") do fp
        data=readlines(fp)
    end
    hail=Vector{Hail}(undef,length(data))
    for i=1:length(data)
        hail[i]=gethail(data[i])
    end
    p1=part1(hail)
    p2=part2(hail)
    println("Part 1 Intersections in the test area are ",p1)
    println("Part 2 The sum of x, y and z is ",p2)
end

function main()
    t=@elapsed try
        println("Advent of Code 2023 Day 24 Never Tell Me The Odds\n")
        doinit()
        throw(DoExit())
    catch r
        if !isa(r,DoExit)
            rethrow(r)
        end
    end
    println("\nTotal execution time ",t," seconds.")
end 

main()
The solution for part 2 minimizes
    J.png
    J.png (13.42 KiB) Viewed 748 times
      summed over all hailstones using the Gauss-Newton algorithm

      https://en.wikipedia.org/wiki/Gauss%E2% ... _algorithm

      Given the simplistic way I coded J there was too much loss of precision. Fortunately, Fido was in favor of testing Julia's built-in BigFloat datatype on the Pi Zero.

      lurk101
      Posts: 2552
      Joined: Mon Jan 27, 2020 2:35 pm
      Location: Cumming, GA (US)

      Re: Advent of Code 2023

      Thu Feb 08, 2024 2:19 pm

      For day 24 part2 I assumed that calculating with 3 judiciously picked hailstones with different velocities should be good enough. It worked with my data, does it not give the right answer for yours?

      ejolson
      Posts: 12155
      Joined: Tue Mar 18, 2014 11:47 am

      Re: Advent of Code 2023

      Thu Feb 08, 2024 4:48 pm

      lurk101 wrote:
      Thu Feb 08, 2024 2:19 pm
      For day 24 part2 I assumed that calculating with 3 judiciously picked hailstones with different velocities should be good enough. It worked with my data, does it not give the right answer for yours?
      It's off by two, likely due to rounding error. My strategy was to guess a trajectory for the rock, compute the closest the rock comes to each of the hailstones and then sum the squares of those distances. The puzzle then becomes a nonlinear least squares problem that can be solved using, for example, Gauss-Newton.

      I also had rounding difficulties. The test data worked fine but I had to switch to big floats to get the star. Julia made that easy because left division \ just worked for big float matrices.

      I could use GMP in C and then write my own matrix QR factorisation routine. I think the Chinese remainder theorem, which Fido insists on calling the Aryabarka algorithm, was the expected solution technique.

      lurk101
      Posts: 2552
      Joined: Mon Jan 27, 2020 2:35 pm
      Location: Cumming, GA (US)

      Re: Advent of Code 2023

      Thu Feb 08, 2024 8:35 pm

      No need for GMP. C++23 has float128_t.

      Using your data:

      Code: Select all

      pi@pi5:~/AoC-2023-cplusplus/day24 $ g++ -O3 -std=c++23 day24.cpp 
      pi@pi5:~/AoC-2023-cplusplus/day24 $ ./a.out 
      --- Day 24: Never Tell Me The Odds ---
      part 1 - 24627
      part 2 - 527310134398221
      Elapsed - 22.326 ms.

      ejolson
      Posts: 12155
      Joined: Tue Mar 18, 2014 11:47 am

      Re: Advent of Code 2023

      Fri Feb 09, 2024 5:08 am

      lurk101 wrote:
      Thu Feb 08, 2024 8:35 pm
      No need for GMP. C++23 has float128_t.

      Using your data:

      Code: Select all

      pi@pi5:~/AoC-2023-cplusplus/day24 $ g++ -O3 -std=c++23 day24.cpp 
      pi@pi5:~/AoC-2023-cplusplus/day24 $ ./a.out 
      --- Day 24: Never Tell Me The Odds ---
      part 1 - 24627
      part 2 - 527310134398221
      Elapsed - 22.326 ms.
      Woohoo! Day 24 is working for my data! Does it run on the Pico?

      I finished my solution to the day 25 puzzle today.

      Code: Select all

      julia> include("day25.jl") # Pi Zero 700 MHz
      Advent of Code 2023 Day 25 Snowverload
      
      Part 1 The product of the two groups is 567606
      
      Total execution time 52.94287787 seconds.
      
      julia> main()
      Advent of Code 2023 Day 25 Snowverload
      
      Part 1 The product of the two groups is 567606
      
      Total execution time 48.092444726 seconds.
      
      julia> main()
      Advent of Code 2023 Day 25 Snowverload
      
      Part 1 The product of the two groups is 567606
      
      Total execution time 48.938123044 seconds.
      
      Though it doesn't meet the 15 seconds cutoff, it did finish before Lent.

      After ruling out an exhaustive snipping of all possible combinations of three wires, the dog developer suggested treating the components as vertices in a graph and the wires as edges. Since it is known that the minimal cut is unique and equal three one can check if the maximum flow between a fixed vertex and each of the other vertices is greater than three. Then place those vertices for which it is in one group and the rest in the other.

      The Julia code is

      Code: Select all

      #=  Advent of Code 2023 Day 25 Snowverload
          Written 2024 by Eric Olson =#
      
      struct DoExit <: Exception
      end
      
      import Base.isequal, Base.hash
      
      function gobble(s::String,m::String)::Tuple{String,Bool}
          if length(s)<length(m)
              return s,false
          end
          if s[1:length(m)]==m
              return s[length(m)+1:end],true
          end
          return s,false
      end
      
      function wskip(s::String)::String
          for i=1:length(s)
              if !isspace(s[i])
                  return s[i:end]
              end
          end
          return ""
      end
      
      function vskip(data,i::Int)::Int
          while i<=length(data)&&length(data[i])==0
              i+=1
          end
          return i
      end 
      
      function getalpha(s::String)::Tuple{String,String}
          for i=1:length(s)
              if !isletter(s[i])
                  return s[i:end],s[1:i-1]
              end
          end
          return "",s
      end
      
      function getint(s::String)::Tuple{String,Int64}
          n=Int64(0); ε=1
          for i=1:length(s)
              if s[i]=='-'
                  ε=-1
              elseif s[i]>='0'&&s[i]<='9'
                  n=n*10+Int64(s[i]-'0')
              else
                  return s[i:end],ε*n
              end
          end
          return "",ε*n
      end
      
      mutable struct Edog
          a::String
          d::Int
          f::Int
          Edog(a,d)=new(a,d,0)
      end
      function isequal(x::Edog,y::Edog)::Bool
          return x.a==y.a
      end
      function hash(x::Edog)::UInt
          return hash(x.a)
      end
      
      mutable struct Wire
          c::String
          e::Vector{Edog}
      end
      
      function getwire(s::String)::Wire
          r=s
          s,c=getalpha(s)
          s,f=gobble(s,": ")
          if f!=true
              println(r,"\nMissing component separator!")
              throw(DoExit())
          end
          e=Vector{Edog}()
          while length(s)>0
              s,z=getalpha(s)
              push!(e,Edog(z,0))
              s=wskip(s)
          end
          return Wire(c,e)
      end
      
      mutable struct Node
          w::Wire
          n::Int
      end
      
      function mkpriority()::Tuple{Function,Function}
          heap=Node[]
          function enqueue(p::Node)
              push!(heap,p)
              r=length(heap)
              while true
                  s=r÷2
                  if s<1 break end
                  if heap[s].n<=p.n break end
                  heap[r]=heap[s]
                  r=s
              end
              heap[r]=p
          end
          function dequeue()::Node
              if length(heap)==0
                  println("Tried to remove nonexistent point!\n")
                  throw(DoExit())
              end
              t=pop!(heap)
              if length(heap)==0 return t end
              p=heap[1]
              s0=1
              while true
                  r0=2*s0; r1=r0+1
                  if r0>length(heap) break end
                  s1=r0
                  if r1<=length(heap)
                      if heap[r0].n>heap[r1].n
                          s1=r1
                      end
                  end
                  if t.n<=heap[s1].n break end
                  heap[s0]=heap[s1]
                  s0=s1
              end
              heap[s0]=t
              return p
          end
          return enqueue,dequeue
      end
      
      function clearflow(wire::Vector{Wire})::Nothing
          for i=1:length(wire)
              for e in wire[i].e
                  e.f=0
              end
          end
      end
      
      function addflow(wire::Vector{Wire},a::Int,b::Int)::Vector{Int}
          K=length(wire)
          enc,deq=mkpriority()
          g=Vector{Int}(undef,K)
          g.=typemax(Int)
          g[b]=0
          enc(Node(wire[b],0))
          while length(enc.heap)>0
              v=deq()
              n=v.n+1
              for e in v.w.e
                  if e.f>-1&&g[e.d]>n
                      g[e.d]=n
                      enc(Node(wire[e.d],n))
                  end
              end
          end
          function trace()::Vector{Int}
              k=a
              if g[a]==typemax(Int)
                  return []
              end
              n=g[a]-1
              p=[k]
              for i=1:2*K
                  for e in wire[k].e
                      if e.f<1&&g[e.d]==n
                          push!(p,e.d)
                          e.f+=1
                          for er in wire[e.d].e
                              if er.d==k
                                  er.f-=1
                                  break
                              end
                          end
                          if e.d==b
                              return p
                          end
                          k=e.d
                          n-=1
                      end
                  end
              end
              println("Unable to trace path from $a to $(b)!")
              throw(DoExit())
          end
          p=trace()
          return p
      end
      
      function part1(wire::Vector{Wire})::Int
          K=length(wire)
          a=1
          g=[a]
          for b=1:K
              if a==b continue end
              clearflow(wire)
              p=addflow(wire,a,b)
              p=addflow(wire,a,b)
              p=addflow(wire,a,b)
              p=addflow(wire,a,b)
              if length(p)>0
                  push!(g,b)
              end
          end
          return length(g)*(K-length(g))
      end
      
      function doinit()
          data=String[]
          open("day25.txt","r") do fp
              data=readlines(fp)
          end
          wmap=Dict{String,Int}()
          wire=Vector{Wire}(undef,length(data))
          for i=1:length(data)
              wire[i]=getwire(data[i])
              wmap[wire[i].c]=i
          end
          function fwire(w::Vector{Edog},c::String)::Bool
              for e in w
                  if e.a==c
                      return true
                  end
              end
              return false
          end
          for i=1:length(wire)
              for e in wire[i].e
                  k=get(wmap,e.a,nothing)
                  if k==nothing
                      push!(wire,Wire(e.a,Vector{Edog}()))
                      k=length(wire)
                      wmap[wire[k].c]=k
                  end
                  if !fwire(wire[k].e,wire[i].c)
                      push!(wire[k].e,Edog(wire[i].c,0))
                  end
              end
          end
          for i=1:length(wire)
              for e in wire[i].e
                  e.d=wmap[e.a]
              end
          end
          p1=part1(wire)
          println("Part 1 The product of the two groups is ",p1)
      end
      
      function main()::Nothing
          t=@elapsed try
              println("Advent of Code 2023 Day 25 Snowverload\n")
              doinit()
              throw(DoExit())
          catch r
              if !isa(r,DoExit)
                  rethrow(r)
              end
          end
          println("\nTotal execution time ",t," seconds.")
      end 
      
      main()
      
      I originally used sets to store the edges but it ran 50 percent slower.

      The code took a surprisingly long time to debug, likely because Fido computed the minimal path backwards b to a but then traced forwards a to b when updating the flow. In the end I think the signs are reversed from the usual convention.

      lurk101
      Posts: 2552
      Joined: Mon Jan 27, 2020 2:35 pm
      Location: Cumming, GA (US)

      Re: Advent of Code 2023

      Fri Feb 09, 2024 12:45 pm

      ejolson wrote:
      Fri Feb 09, 2024 5:08 am
      Day 24 is working for my data! Does it run on the Pico?
      float128_t is introduced in g++14. Best I can get for Pico is g++13.2

      Return to “Teaching and learning resources”