Here is my day 5 , but part 2 is way to slow. I'm still waiting for the output, but i get the feeling I will have to optimize...
Uh boy, this was quite something...:joy:
My part 2 takes 10 minutes to run, but this was still faster than me trying to come up and implement a smarter solution, so I guess I'm done?
These maps are linear transformations from Nat -> Nat, so according to math, there is way to combine those. And since they are linear, we can predict how they behave "in between", so we only need to look at the ends of each mapping. If we did this with all of them, we would have a single map seed-to-location. Using that map, we would no longer need to scan the entire seed range, we would just need to look up the critical points (whenever the mapping changes) and compare those, since we know that inside of a mapping, all values are monotonically increasing.
There is probably a very smart way of combining these maps with a bunch of math, but my idea would have been to sort them based on the middle value (so dest in the first map and src in the second map), and then look at the heads of those lists repeatedly, comparing the "ends" to generate new ranges..
https://gitlab.com/arkandos/aoc/-/blob/2023/solutions/day5.roc?ref_type=heads
Here is my new day 5 . It's super fast now, but could use some cleanup.
You don't have to transform every seed value in a range. You can just transform the start. You might have to split one seed range into sveral, when it overlaps with the transformation range.
Day 5! Runs in about 7 minutes :D https://github.com/lindskogen/advent-of-code-2023/blob/main/day05/main.roc
Here is mine: https://github.com/ostcar/aoc2023/blob/main/days/day05.roc
Part1 in 2.422ms:
XXX
Part2 in 98.236ms:
XXX
It is nice, that roc partly compiles. I implemented the type signatures and put them together like
expect
part1 exampleInput == "result"
part1 = \input ->
input
|> doSomething
|> somethingElse
doSomething : Input -> Output
somethingElse : OtherInput -> OtherOutput
Then I called roc test day05.roc and the compiler told my what to do next :)
The feature I missed today was to rename a deconstructed value. For example
[first, .. as rest ] = mylist
or
RecordOne : {first : Str, second : Str}
RecordTwo : {first : Str, second : Str}
myFunc : RecordOne, RecordTwo -> Str
myFunc = \{first as first1, second as second1}, {first as first2, second as second2} ->
...
The as keyword works in pattern matching. Would it be possible, that it would also work in the deconstructing a datastructure?
Super lazy and just brute force walking everything: https://github.com/bhansconnect/roc-aoc-2023/blob/main/day5.roc
collapse all dictionaries into 1 dictionary with more ranges
split the seed groups at the complete range boundaries
run through the smallest seed in each range
I'm really glad I'm not the only lazy soul who just waited 8 minutes for part 2 to run.https://github.com/keeslinp/AoC2023/blob/main/day5.roc
I finally took the time to grok the parser lib and I think I've got the hang of it.
if location >= source then
if location - source <= size then
Bool.true
else
Bool.false
else
Bool.false
because location >= source && location - source <= size caused underflow :disappointed: .
Also in camp brute force here with my solution . :see_no_evil:
I think I solved part 1.. but I hit a compiler bug once I wrote the final line to my solution :cry:
https://gitlab.com/AsbjornOlling/aoc2023/-/blob/main/05/main.roc
I even tested everything with expects as I built it, going bottom-up, and all the components work perfectly by themselves, so I'm pretty convinced that my solution works. It's just that my one line of top-level call panics the compiler.
thread 'main' panicked at 'Error in alias analysis: error in module ModName("UserApp"), function definition FuncName("\x07\x00\x00\x00\x05\x00\x00\x00\x0e\xa0\xc6\x8f\xe8\x93\x17N"), definition of value binding ValueId(14): expected type '((),)', found type '((), "UserApp"::"\x81\xcc+\xe5S\x0c\x05\xe0")'', crates/compiler/gen_llvm/src/llvm/build.rs:5657:19
I'm not sure what to do. I guess I'll try rewriting it in a different way, and hope to avoid the crash condition - but (what seems to be) the offending line is just a straightforward List.map call, so it's gonna be a bit obtuse.
List.walk building a chain of closures.
lol yes :rolling_on_the_floor_laughing:
That probably is somehow the root cause of the crash
Lambda sets sadly have some bugs and you are probably hitting one...but that's just a guess
funkily enough, I do that twice in my program, but the other instance worked
Ha just before beginning todays aoc, I was listening to the Software Unscripted episode with Casey Muratori,:sweat_smile:
heyy I rewrote it into something that works
..and then I found out that I had understood the task wrong :sweat_smile: typical
luckily it was just a matter of using the wrong order of (outrange, inrange, len)
I managed to solve Part 1, but not Part 2...
app "hello"
packages
{
pf : "https://github.com/roc-lang/basic-cli/releases/download/0.7.0/bkGby8jb0tmZYsy2hg1E_B2QrCgcSTxdUlHtETwm5m4.tar.br" ,
parser : "https://github.com/lukewilliamboswell/roc-parser/releases/download/0.3.0/-e3ebWWmlFPfe9fYrr2z1urfslzygbtQQsl69iH1qzQ.tar.br" ,
}
imports
[
pf . Stdout ,
pf . Task ,
"./day5-input.txt" as input : Str ,
parser . Core . { Parser , const , keep , skip , map , oneOrMore , sepBy },
parser . String . { anyCodeunit , digits , oneOf , parseStr , parseStrPartial , string },
]
provides [ main ] to pf
main =
{} <- Stdout . line "The lowest location is \(part1 input)" |> Task . await
# {} <- Stdout . line "The gear ratios are \(part2 input)" |> Task . await
Task . ok {}
part1 : Str -> Str
part1 = \ almanac ->
parsedAlmanac =
almanac
|> parseSeeds
|> almanacMap "seed-to-soil"
|> almanacMap "soil-to-fertilizer"
|> almanacMap "fertilizer-to-water"
|> almanacMap "water-to-light"
|> almanacMap "light-to-temperature"
|> almanacMap "temperature-to-humidity"
|> almanacMap "humidity-to-location"
List . min parsedAlmanac . list
|> \ result ->
when result is
Ok num -> Num . toStr num
Err _ -> "Unknown"
AlmanacList : List U64
ParsedAlmanac : { almanac : Str , list : AlmanacList }
seedParserMapper : List Nat -> List U64
seedParserMapper = \ i -> List . map i Num . toU64
seedParser : Parser ( List U8 ) ( List U64 )
seedParser =
const ( seedParserMapper )
|> skip ( string "seeds: " )
|> keep ( digits |> sepBy ( string " " ))
|> skip anyCodeunit
parseSeeds : Str -> ParsedAlmanac
parseSeeds = \ almanac ->
seeds = parseStrPartial seedParser almanac
{
almanac : almanac ,
list :
when seeds is
Ok r -> r . val
Err _ -> []
}
parseMap = \ almanac , section ->
mapValues =
Str . split almanac ( Str . concat section " map: \n " )
|> List . get 1
|> Result . withDefault ""
|> Str . split " \n\n "
|> List . get 0
|> Result . withDefault ""
Str . split mapValues " \n "
|> List . map \ lines -> Str . split lines " "
|> List . map \ lines -> List . map lines \ line -> ( Str . toU64 line |> Result . withDefault 0 )
|> List . map \ lines ->
{
destination : List . get lines 0 |> Result . withDefault ( Num . toU64 0 ) ,
source : List . get lines 1 |> Result . withDefault ( Num . toU64 0 ),
range : List . get lines 2 |> Result . withDefault ( Num . toU64 0 )
}
almanacMap : ParsedAlmanac , Str -> ParsedAlmanac
almanacMap = \ parsedAlmanac , section ->
mapper = parseMap parsedAlmanac . almanac section
list = List . map parsedAlmanac . list \ source -> ( mapLocation source mapper )
{
almanac : parsedAlmanac . almanac ,
list : list
}
mapLocation : U64 , List { destination : U64 , source : U64 , range : U64 } -> U64
mapLocation = \ source , mapper ->
location =
List . keepIf mapper \ m -> ( m . source + m . range - 1 ) >= source && source >= m . source
|> List . get 0
|> Result . withDefault { destination : source , source : source , range : 1 }
location . destination + ( source - location . source )
exampleInput =
"""
seeds: 79 14 55 13
seed-to-soil map:
50 98 2
52 50 48
soil-to-fertilizer map:
0 15 37
37 52 2
39 0 15
fertilizer-to-water map:
49 53 8
0 11 42
42 0 7
57 7 4
water-to-light map:
88 18 7
18 25 70
light-to-temperature map:
45 77 23
81 45 19
68 64 13
temperature-to-humidity map:
0 69 1
1 0 69
humidity-to-location map:
60 56 37
56 93 4
"""
|> Str . trim
debug = \ v , ctx ->
dbg
ctx
dbg
v . list
v
I think my Part 2 would work if my computer had a trillion more resources:
app "hello"
packages
{
pf : "https://github.com/roc-lang/basic-cli/releases/download/0.7.0/bkGby8jb0tmZYsy2hg1E_B2QrCgcSTxdUlHtETwm5m4.tar.br" ,
parser : "https://github.com/lukewilliamboswell/roc-parser/releases/download/0.3.0/-e3ebWWmlFPfe9fYrr2z1urfslzygbtQQsl69iH1qzQ.tar.br" ,
}
imports
[
pf . Stdout ,
pf . Task ,
"./day5-input.txt" as input : Str ,
parser . Core . { Parser , const , keep , skip , map , oneOrMore , sepBy },
parser . String . { anyCodeunit , digits , oneOf , parseStr , parseStrPartial , string },
]
provides [ main ] to pf
main =
# {} <- Stdout . line "The lowest location is \(part1 input)" |> Task . await
{} <- Stdout . line "The gear ratios are \(part2 input)" |> Task . await
Task . ok {}
part1 : Str -> Str
part1 = \ almanac ->
parsedAlmanac =
almanac
|> parseSeeds
|> almanacMap "seed-to-soil"
|> almanacMap "soil-to-fertilizer"
|> almanacMap "fertilizer-to-water"
|> almanacMap "water-to-light"
|> almanacMap "light-to-temperature"
|> almanacMap "temperature-to-humidity"
|> almanacMap "humidity-to-location"
List . min parsedAlmanac . list
|> \ result ->
when result is
Ok num -> Num . toStr num
Err _ -> "Unknown"
Seen : [ Nothing , Location U64 ]
part2 : Str -> Str
part2 = \ almanac ->
seeds = parseStrPartial seedPairParser almanac
x = when seeds is
Ok res -> res . val
Err _ -> []
first = List . first x
rest = List . dropFirst x 1
when first is
Ok ( Pair num range ) ->
solvePart2
{
almanac : almanac ,
pairs : rest ,
minSeen : NothingYet ,
currentNum : Num . toU64 num ,
currentRange : Range ( Num . toU64 range )
}
|> Num . toStr
_ -> "Unknown"
solvePart2 : { almanac : Str , pairs : List [ Pair Nat Nat ], minSeen : [ NothingYet , Seen U64 ], currentNum : U64 , currentRange : [ NextPair , Range U64 ] } -> U64
solvePart2 = \ progress ->
when progress . currentRange is
NextPair ->
dbg "NextPair"
first = List . first progress . pairs
rest = List . dropFirst progress . pairs 1
when first is
Ok ( Pair num range ) ->
solvePart2
{
almanac : progress . almanac ,
pairs : rest ,
minSeen : progress . minSeen ,
currentNum : Num . toU64 num ,
currentRange : Range ( Num . toU64 range )
}
_ ->
when progress . minSeen is
NothingYet -> 0
Seen num -> num
Range range ->
currentLocation =
{
almanac : progress . almanac ,
source : progress . currentNum
}
|> almanacMapSingle "seed-to-soil"
|> almanacMapSingle "soil-to-fertilizer"
|> almanacMapSingle "fertilizer-to-water"
|> almanacMapSingle "water-to-light"
|> almanacMapSingle "light-to-temperature"
|> almanacMapSingle "temperature-to-humidity"
|> almanacMapSingle "humidity-to-location"
|> . source
minSeen = when progress . minSeen is
NothingYet -> currentLocation
Seen s -> if currentLocation < s then currentLocation else s
solvePart2
{
almanac : progress . almanac ,
pairs : progress . pairs ,
minSeen : Seen minSeen ,
currentNum : progress . currentNum + 1 ,
currentRange : if range == 1 then NextPair else Range ( range - 1 )
}
AlmanacList : List U64
ParsedAlmanac : { almanac : Str , list : AlmanacList }
SeedPair : [ Pair Nat Nat ]
seedPairParser : Parser ( List U8 ) ( List [ Pair Nat Nat ])
seedPairParser =
pair = const ( \ x -> \ y -> Pair x y )
|> keep digits
|> skip ( string " " )
|> keep digits
seedPair : Parser _ ( List [ Pair Nat Nat ])
seedPair = pair |> sepBy ( string " " )
const ( \ i -> i )
|> skip ( string "seeds: " )
|> keep seedPair
|> skip anyCodeunit
seedParserMapper : List Nat -> List U64
seedParserMapper = \ i -> List . map i Num . toU64
seedParser : Parser ( List U8 ) ( List U64 )
seedParser =
const ( seedParserMapper )
|> skip ( string "seeds: " )
|> keep ( digits |> sepBy ( string " " ))
|> skip anyCodeunit
parseSeeds : Str -> ParsedAlmanac
parseSeeds = \ almanac ->
seeds = parseStrPartial seedParser almanac
{
almanac : almanac ,
list :
when seeds is
Ok r -> r . val
Err _ -> []
}
parseMap = \ almanac , section ->
mapValues =
Str . split almanac ( Str . concat section " map: \n " )
|> List . get 1
|> Result . withDefault ""
|> Str . split " \n\n "
|> List . get 0
|> Result . withDefault ""
Str . split mapValues " \n "
|> List . map \ lines -> Str . split lines " "
|> List . map \ lines -> List . map lines \ line -> ( Str . toU64 line |> Result . withDefault 0 )
|> List . map \ lines ->
{
destination : List . get lines 0 |> Result . withDefault ( Num . toU64 0 ) ,
source : List . get lines 1 |> Result . withDefault ( Num . toU64 0 ),
range : List . get lines 2 |> Result . withDefault ( Num . toU64 0 )
}
almanacMapSingle : { source : U64 , almanac : Str }, Str -> { source : U64 , almanac : Str }
almanacMapSingle = \ data , section ->
mapper = parseMap data . almanac section
{
almanac : data . almanac ,
source : mapLocation data . source mapper
}
almanacMap : ParsedAlmanac , Str -> ParsedAlmanac
almanacMap = \ parsedAlmanac , section ->
mapper = parseMap parsedAlmanac . almanac section
list = List . map parsedAlmanac . list \ source -> ( mapLocation source mapper )
{
almanac : parsedAlmanac . almanac ,
list : list
}
mapLocation : U64 , List { destination : U64 , source : U64 , range : U64 } -> U64
mapLocation = \ source , mapper ->
location =
List . keepIf mapper \ m -> ( m . source + m . range - 1 ) >= source && source >= m . source
|> List . get 0
|> Result . withDefault { destination : source , source : source , range : 1 }
location . destination + ( source - location . source )
exampleInput =
"""
seeds: 79 14 55 13
seed-to-soil map:
50 98 2
52 50 48
soil-to-fertilizer map:
0 15 37
37 52 2
39 0 15
fertilizer-to-water map:
49 53 8
0 11 42
42 0 7
57 7 4
water-to-light map:
88 18 7
18 25 70
light-to-temperature map:
45 77 23
81 45 19
68 64 13
temperature-to-humidity map:
0 69 1
1 0 69
humidity-to-location map:
60 56 37
56 93 4
"""
|> Str . trim
debug = \ v , ctx ->
dbg
ctx
dbg
v
v
Also brute forced this one because efficiency is boring https://gist.github.com/ayazhafiz/9adbb083f965bcad18c2b5754b00b51b
Here's my solution for both parts.https://github.com/ryanb/advent-2023-roc/blob/main/day05/main.roc
Keeping the values in ranges is key for performance on Part 2. It was just a bit tricky to split the ranges when they partially overlapped.
Despite the challenges of these, I'm enjoying Roc!
My solution: https://github.com/LoipesMas/roc-aoc2023/blob/main/5/main.roc stupid unique idea to flip the problem backwards: instead of going from seed to location, I went with locations going from 0, converting them to seeds and checking if the seed is in provided range. It's O(n) where n is your result ;] --optimized it's not even that bad! Only ~12 seconds to find location 15_880_236. Around a minute for an unoptimized build
My solution: https://github.com/timotree3/aoc2023/blob/main/roc/day5.roc
I propagated lists of ranges across the maps, splitting the ranges into multiple when partially mapped. Also, in order to apply the maps more efficiently, I sorted them and used binary search to find the relevant ranges.
My solutions for day 5: https://github.com/Ocupe/advent-of-code-2023/tree/main/day_05
My solution for part 2 took around 13 hours to finish :snail:
Last updated: Jul 06 2025 at 12:14 UTC
Fabian Schmalzried (Dec 05 2023 at 09:41):