#AOC in Ocaml

1 messages · Page 1 of 1 (latest)

late rune
bleak solar
#

I'm doing this year in OCaml and I'm using an expect test workflow

kindred lynx
#

What does it mean, expect test workflow? Like, unit test stuff, or something else?

dapper dune
bleak solar
#

That's correct. First I define a test for each of the sample inputs, make sure they all pass. Then dune runtest --auto-promote will fill in the result for the actual input automatically.

late rune
#

Since we are at day 2, I wanted to share my approach to solve the first problems of day 1.
Feedback welcome:

let top_three_elves f =
  let chan = open_in f in
  let sum_list =
    In_channel.input_all chan
    |> Str.split (Str.regexp "\n\n")
    |> List.map (fun s ->
           String.split_on_char '\n' s
           |> List.filter (fun s -> s <> "")
           |> List.map int_of_string |> List.fold_left ( + ) 0)
  in
  List.sort compare sum_list |> List.rev |> function
  | a :: b :: c :: _tl -> a + b + c
  | _ -> 0
granite girder
wintry meadow
mighty mountain
#

(I've got a few helper functions in util.ml)

#

@late rune Nice solution indeed! I just realized I overdid the matching for the first 3 elements. 😄 Btw, I was surprised to see a usage of the Str module, as I've heard here and there than it was considered semi-deprecated or something like this.

late rune
#

Str.split is the only way to split on strings and not on characters, without writing your own function

#

I didn't knew about the semi-deprecation 🤔

mighty mountain
#

OCaml comes with the Str module. This module is not recommended because it is not part of the standard library, it uses global states and is not particularly fast, but its availability makes it useful when you don’t have access to anything better.

main oyster
#

Finding a string in another [fast] is not easy, the compiler devs don't really want to maintain a large stdlib

mighty mountain
#

Yeah, I get totally get it.

crisp niche
atomic vale
mighty mountain
mighty mountain
#

My solution today is quite ugly, need to spend more time with API:

open Util
open Printf

let input = lines "-"

let split_string str =
  let len = String.length str in
  let mid = len / 2 in
  let part1 = (String.sub str 0 mid) in
  let part2 = (String.sub str mid mid) in
  (part1, part2)

let overlap str1 str2 =
  String.fold_left
    (fun res c ->
      if String.contains str2 c then c::res else res)
    [] str1

let overlap3 str1 str2 str3 =
  String.fold_left
    (fun res c ->
      if (String.contains str2 c) && (String.contains str3 c) then c::res else res)
    [] str1

let score ch =
  if (int_of_char ch >= 97) then (int_of_char ch) - 96
  else (int_of_char ch) - 38

let part1 = input |> List.map split_string |> List.map (fun pair -> let (s1, s2) = pair in (overlap s1 s2)) |> List.map List.hd |> List.map score |> sum

let part2 = input |> CCList.sublists_of_len 3 |> List.map (fun triplet -> let (s1 :: s2 :: s3 :: _) = triplet in (overlap3 s1 s2 s3)) |> List.map List.hd |> List.map score |> sum

let () = printf "Part1: %d\n" part1
let () = printf "Part2: %d\n" part2
#

Probably overlap should operate on list, so it's generic in this sense and I guess I overdid the nested List.maps. 🙂

#

I'm also very curious if there's a way to let bind a list without generating warnings. E.g. in this case I know all lists have the same length, so I don't really need to match against other cases.

#

I kind of miss the ability to deconstruct data structures directly in the function definition (something like fun (s1, s2) ->, but it's not a big deal.

#

I'm definitely curious to see how people with more experience have tackled this and produced simpler code.

late rune
#

O(n^2)

#

Here is mine

let score_item s =
  match Char.code s with
  | c when c >= 97 && c <= 122 -> c - 96
  | c when c >= 65 && c <= 90 -> c - 38 (* 65 - 27 *)
  | _ -> failwith "Character out of range"

let incr_array_at array i = array.(i) <- array.(i) + 1

(* use array to store elements *)
let find_common_element s1 s2 =
  let mem_1 = Array.make (2 * 26) 0 in
  let mem_2 = Array.make (2 * 26) 0 in
  let rec loop i len =
    match i with
    | i when i = len -> () (* end of strings *)
    | i ->
        incr_array_at mem_1 (score_item s1.[i] - 1);
        incr_array_at mem_2 (score_item s2.[i] - 1);
        loop (succ i) len
  in
  loop 0 (String.length s1);
  let sum = ref 0 in
  Array.iter2i
    (fun i a b -> if a >= 1 && b >= 1 then sum := !sum + (i + 1))
    mem_1 mem_2;
  !sum

let read_n_sum f =
  let chan = open_in f in
  let rec loop_read sum =
    match In_channel.input_line chan with
    | None -> sum
    | Some s ->
        let len = String.length s in
        let s1 = String.sub s 0 (len / 2) in
        let s2 = String.sub s (len / 2) (len / 2) in
        loop_read (sum + find_common_element s1 s2)
  in
  loop_read 0
#

I had to extend the standard library to keep track of the index in iter2i

module Array = struct
  include Array

  let iter2i f a b =
    if length a <> length b then
      invalid_arg "Array.iter2: arrays must have the same length"
    else
      for i = 0 to length a - 1 do
        f i (unsafe_get a i) (unsafe_get b i)
      done
end
wintry meadow
signal flume
#

(note that I've already turned the input into a list, so the code is a little shorter than it actually would be if I was getting it from the file directly. However, the algorithms should remain the same otherwise)

dapper dune
#

(Day3) I just used Sets to avoid writing string intersection:

module CharSet = struct
  include Set.Make(Char)
  let of_string s = of_seq (String.to_seq s)
end

Clearly, turning a string into a char Seq into a CharSet is not going to win any performance records... but I am happy to use CharSet.inter twice instead of iterating over a string index

sharp osprey
mighty mountain
#

Indeed. Scanf was definitely useful in this one. Here's my solution.

# 
open Util
open Printf

let input = lines "-"

let transform_input lines =
  List.map (fun line -> Scanf.sscanf line "%d-%d,%d-%d" (fun a b c d -> (a, b), (c, d))) lines

let part1 =  transform_input input |> List.map (fun ((a, b), (c, d)) -> if ((a <= c && b >= d) || (c <= a && d >= b)) then 1 else 0) |> sum

let part2 = transform_input input |> List.map (fun ((a, b), (c, d)) -> if (Stdlib.max a c <= min b d) then 1 else 0) |> sum

let () =
  printf "Part1: %d\n" part1;
  printf "Part2: %d\n" part2
#

Probably I should have used a fold to get rid of one intermediary step, but I was too lazy to optimize anything today.

bleak solar
late rune
sharp osprey
#

Ah, had no idea you could compose them. Like that. Time to update my solution 😄

opaque brook
crisp niche
dapper dune
#

reading ASCII art as data is not my idea of a good time

sharp osprey
mighty mountain
#

@sharp osprey I really like your project structure, btw! I went for putting the solution in bin to be able to run them with dune exec, but it turned out this way it's not easy to work with dune utop. (seems it loads only library code?) This approach with the many libraries and cram-style tests seems pretty cool!

crisp niche
#

haha @dapper dune that was my first thought exactly.

mighty mountain
#

I didn't bother to parse the ASCII art, but if someone knows a good approach for something like this - please do tell.

bleak solar
#

I "zipped" the lines to make reading them easier

late rune
#

This is the only drawback of AOC I find, these unusually complicated pattern that need to be parsed

opaque brook
buoyant topaz
opaque brook
#

Yeah, that is what I ended up doing too. Tho I read the last row with the stack numbers first because I was unsure if there would be trailing spaces or not on some rows

sharp osprey
late rune
sly pine
#

Still haven't done Day 5, spent too much time tinkering with angstrom and achieved nothing Bueno

heavy drift
#

day 5 horribleness:

if it looks like I gave up trying to parse things manually and switched to regex halfway through, you'd be correct

📎 SPOILER_day5.ml
mighty mountain
#

Today again it seems that most of the complexity is going to be parsing the input. (like in Day 5)

bleak solar
#

First time this year I bring in the parser combinators

sharp osprey
bleak solar
dapper dune
#

I guess you could make it flat

#

I was limited by having begun, then abandoned, a tree representation using that 🙂

bleak solar
dapper dune
#

I had thought of building the tree structure using it while solving, and spoke before I thought of the obvious way to flatten

bleak solar
late rune
#

I'm curious to see how it looks like using parser combinators, never used them before

bleak solar
bleak solar
#

What a great day to learn how to use || the Bigarray module ||

sly pine
#

Ooh good tip!

bleak solar
#

On second thought, maybe not 🥵

sly pine
#

I did part 1 its ugly as hell 😂

bleak solar
#

Me too, both parts actually. Lots of imperative code

#

Mixed with folds

sharp osprey
bleak solar
sharp osprey
heavy drift
#

wasted time trying to put together a solution that did not use brute force: ||https://github.com/tdimhcsleumas/advent-of-code-2022/blob/main/day8/day8.ml||. ||part 1 was easier in that regard, simply considering the max height with respect to the traversed row and column||. ||part2 was trickier. At first I got distracted by considering only the most recent height in the score. My (kinda ugly) solution ended up maintaining a most recent coordinate for each height that was traversed, and then searching that 10-element array in lieu of the entire row or column to get the score||. In theory, ||they're asymptotically faster, but i have yet to actually compare||

heavy drift
sharp osprey
bleak solar
bleak solar
sharp osprey
bleak solar
sharp osprey
bleak solar
dapper dune
#

I hard coded the modulus to be appropriate for my "real input" then spent an hour trying to figure out why it wasn't working with the test data

#

when converting the item weights from int to Z.t I just had to find all the places the LSP told me weren't typechecking, it ran correctly the first time it compiled 🙂

bleak solar
sharp osprey
sly pine
#

is this the day I learn some Angstrom? [[[[[[[[[[[][][][][]]]]]]]]]]

bleak solar
#

I can highly recommend Angstrom for today

#

Just finished with no hiccups

bleak solar
sharp osprey
bleak solar
#

Somebody in a different channel suggested || parsing the input as JSON ||

dapper dune
#

that was my first thought after "you could just eval this in python"

bleak solar
sharp osprey
sharp osprey
bleak solar
#

It’s about time I start building a small AoC library, I keep repeating patterns

bleak solar
#

Part 1 done. But the runtime doesn't bode well...

sharp osprey
#

Yeah, Part 1 I got... but going to have to figure out some better pruning strategy for Part 2.

bleak solar
#

I have a solution for part 2 that works on the example, but it's still running on the real input 😄

bleak solar
#

That was tough. I needed to rewrite it for part2 but now it works.

bleak solar
sharp osprey
#

Eventually restarted from scratch -- https://github.com/hellopatrick/xmas/blob/main/2022/day16/main.ml -- ||Floyd-Warshall to find shortest path between all points. This is used to compress the graph (we can now skip all valves with 0 flow rate!) For part1, we can just DFS over this for the largest. For part2, it was fast enough to attempt to just brute-force DFS both me & the elephant, slowly reserving more and more nodes for the elephant.||

#

(that's a strange last sentence, 😅)

bleak solar
sharp osprey
bleak solar
#

I have implemented || cycle detection || but I can't reproduce the example yet 😦

bleak solar
#

Eventually I got it to work but I can't prove that my solution is correct 😅

bleak solar
#

I mean, the || cycle detection || gives me ||working cycles for both example and input || but I'm using || only (rock index, jet index) to find the cycle || and that just sounds like it shouldn't be enough

#

So either I got lucky or it's possible to prove the algorithm is correct on all inputs, and I don't know which...

sharp osprey
bleak solar
sharp osprey
bleak solar
#

I fell behind a bit

sharp osprey
#

I think most of it comes from two rules: ||There's often points at which you cannot possibly be get to your running maximum of geodes, in which case you can prune early. Also, if geode robot needs N obsidian, you only ever need N obsidian robots. You can apply this rule to all the robots to avoid going paths where you build more robots than output that can be possibly used.||

bleak solar
#

Thanks, those are some good insights. I also used || a pruning strategy for states that can't catch up with the running maximum, and that helped a lot. The only other strategy is that I "fast-forward" from a state directly to the next four timestamps where there are enough resources to build the next one of each type of robot, so I only explore a spare graph of states. ||

sharp osprey
#

Ah yeah, I should probably implement the ||fast-forward||.

bleak solar
bleak solar
sharp osprey
bleak solar
sharp osprey
bleak solar
#

I fell behind a bit, only part 1 so far. Thought about preprocessing part 2 manually too...

sharp osprey
sharp osprey
sharp osprey
bleak solar
#

Merry Christmas! I have some catching up to do, I’m still missing five stars.

bleak solar
#

Still two stars missing from last year, and only two weeks to go 😮

sly pine
#

Hello Bueno

sly pine
#

I might have time to learn Angstrom before this years starts owocat

bleak solar
#

I'm also doing AoC in OCaml again!

late rune
#

Same here !

dapper dune
#

good luck!

sly pine
#

I am learning Angstrom in anger triggered_ocaml

bleak solar
#

I also used Angstrom. Was it necessary? Probably not. Was it wise? Who knows...

#

Fell right into a trap, too!

sly pine
#

|| I am having a problem with the eightwo part, where I need to ignore wo since t is already "consumed" from eight || Would love any pointers:

This is my FIRST time using any parser whatsoever 😅

||```
module P = struct
open Angstrom

let is_whitespace = function ' ' | '\t' -> true | _ -> false
let is_digit = function '0' .. '9' -> true | _ -> false
let is_char = function 'a' .. 'z' -> true | _ -> false
let whitespace = take_while is_whitespace
let digit = take_while1 is_digit >>| Int.of_string_exn
let char = skip is_char
let p1 = string "one" *> return 1
let p2 = string "two" *> return 2
let p3 = string "three" *> return 3
let p4 = string "four" *> return 4
let p5 = string "five" *> return 5
let p6 = string "six" *> return 6
let p7 = string "seven" *> return 7
let p8 = string "eight" *> return 8
let p9 = string "nine" *> return 9

let number =
  whitespace
  *> (digit <|> p1 <|> p2 <|> p3 <|> p4 <|> p5 <|> p6 <|> p7 <|> p8 <|> p9)
  <* whitespace

let parse input =
  parse_string ~consume:All (many1 number) input |> Result.get_or_failwith

end

#

|| My idea is that if none of those criteria's are met I want to advance the parser one step and try again but I don't know how to do that 😬 ||

bleak solar
sly pine
bleak solar
sly pine
sly pine
#

I went back to R E C U R S I O N triggered_ocaml Unedited and raw, extremely noisy 😂

SPOILER_holyfuck.png
bleak solar
bleak solar
dapper dune
#

rather than that I would just reverse the list and look for slaremun (eno, owt, eerht...)

bleak solar
#

That's what I ended up doing as well. The downside is it needs two passes?

#

Then again, you could short-circuit so it's likely to be more performant still 🙂

dapper dune
#

and exploding strings is wasteful

#

yes, looking from each end lets you stop on success

#

I ended up bashing my head against angstrom's peek_string because I got the first part done in angstrom and I thought it would be an easier adaptation

#

but I feel like I don't know how to handle "junk" that I don't want to produce anything, I had to use option int and produce None for each character that wasn't a digit or start of a numeral

bleak solar
#

That sounds about right, no?

dapper dune
#

it felt like I was missing a way to say "eat the character and restart this same parser"

#

or an infinite list of "eat 0 and try p; eat 1 and try p; eat 2 and try p..."

bleak solar
#

I might give it a try with peek_string and any_char

sly pine
sly pine
bleak solar
#

I used || option along with any_char *> return None and a List.filter_map Fun.id at the end || for the junk

sly pine
#

I'll have to look at that later!

dapper dune
#

primagen is doing Advent in Ocaml at the moment

sly pine
#

Now I think of it my Angstrom solution wouldn't work: || I consumed the whole text of the word digit and wouldn't be able to spot overlapping ones! ||

signal flume
#

day one, part one

SPOILER_Screenshot_20231201_161911.png
lime mica
#

Does anyone recommend a better regexp for ocaml, I'm having issues with the lookahead

#

sadly missing out on the "eighthree" parsing to 83

# 
  let re = Str.regexp "\\(one\\|two\\|three\\|four\\|five\\|six\\|seven\\|eight\\|nine\\|[0-9]\\)" in
  let regex_matches = Str.full_split re line in
  let matches = List.map ~f:(fun match_ ->
    match match_ with
    | Str.Delim s -> Some (to_digit s)
    | Str.Text _ -> None
  ) regex_matches in 
  List.filter_opt matches
;;```
dapper dune
#

if I had to use regexps to solve this problem I would do it in forward and reverse passes

signal flume
#

(well, it looks like two because it wraps so far...)

lime mica
dapper dune
#

one of them necessarily is uniquely the first and one is uniquely the last

#

twoneight should reduce to 28

#

@kali clever, but do you need the prefixes for something I'm not seeing?

#

oh, early replacements can mangle later ones, that makes sense

#

stuck thinking linearly

lime mica
# 
let extract_digits_and_numbers line =
  let re = Str.regexp "\\(one\\|two\\|three\\|four\\|five\\|six\\|seven\\|eight\\|nine\\|[0-9]\\)" in
  let rev_re = Str.regexp "\\(eno\\|owt\\|eerht\\|ruof\\|evif\\|xis\\|neves\\|thgie\\|enin\\|[0-9]\\)" in
  let regex_matches = Str.full_split re line in
  let matches = List.map ~f:(fun match_ ->
    match match_ with
    | Str.Delim s -> Some (to_digit s)
    | Str.Text _ -> None
  ) regex_matches in
  let rev_regex_matches = Str.full_split rev_re (String.rev line) in
  let rev_matches = List.map ~f:(fun match_ ->
    match match_ with
    | Str.Delim s -> Some (to_digit (String.rev s))
    | Str.Text _ -> None
  ) rev_regex_matches in 
  let all_matches = List.append matches (List.rev rev_matches) in
  List.filter_opt all_matches
;;
#

Good call on the left to right and right to left @dapper dune

#

this is probably the ugliest code I've ever produced

dapper dune
#

what could be more beautiful than "thgie"

dapper dune
#

angstrom starting to click fr, or maybe this format is just easy to write a parser for

bleak solar
#

Agreed, the Angstrom experience was very smooth today

lime mica
#

anyone know of a good resource to learn angstrom? I'll give it a college try today

signal flume
#

day 2 part 1 solution
||```ocaml
open List let s = Scanf.sscanf let sp = String.split_on_char let i = Fun.id
let () =
In_channel.input_all stdin
|> sp '\n'
|> map (sp ':')
|> map (fun [x;y] -> s x "Game %d" i, concat_map (sp ',') @@ sp ';' y)
|> filter (fun (_,y) -> let a,b,c = fold_left (fun (a,b,c) str ->
max a (try s str " %d red" i with _ -> 0),
max b (try s str " %d green" i with _ -> 0),
max c (try s str " %d blue" i with _ -> 0)) (0,0,0) y in a <= 12 && b <= 13 && c <= 14)
|> map fst
|> fold_left (+) 0
|> print_int

#

perhaps somewhat ironically, the day 2 part 2 solution is even shorter

#

||```ocaml
open List let s = Scanf.sscanf let sp = String.split_on_char let i = Fun.id
let () =
In_channel.input_all stdin
|> sp '\n'
|> map (sp ':')
|> map (fun [_;y] -> concat_map (sp ',') @@ sp ';' y)
|> map (fun y -> let a,b,c = fold_left (fun (a,b,c) str ->
max a (try s str " %d red" i with _ -> 0),
max b (try s str " %d green" i with _ -> 0),
max c (try s str " %d blue" i with _ -> 0)) (0,0,0) y in a * b * c)
|> fold_left (+) 0
|> print_int

dapper dune
#

@lime mica I just alternated going through the json parser and reading documentation for operators I couldn't make sense of

#

it's an extremely specific view of turning a stream of characters into some kind of meaning, and because it's inside a type system you have to make sure you have a type general enough that all the parsers you want to pick between can produce the same type

#

probably a good day for taking a crack at it though

lime mica
#

Has anyone dealt with (Failure "Parsing error: : end_of_input") error in angstrom? My parser must be bugging out somehow


let eol = skip_many (choice [char '\n'; char '\r'])

let number = space *> take_while1 (function '0' .. '9' -> true | _ -> false) <* space >>| int_of_string

let color = space *> take_while1 (function 'a' .. 'z' | 'A' .. 'Z' -> true | _ -> false) <* space

let game_prefix = string "Game " *> number *> string ": " *> return ()

let color_count =
  lift2 (fun count color -> ({color = color; count})) number (char ' ' *> color)

let group = sep_by (space *> char ',' <* space) color_count

let line_parser = game_prefix *> sep_by (space *> char ';' <* space) group <* eol

let aggregate_max_counts groups =
  let table = Hashtbl.create (module String) in
  List.iter ~f:(fun group ->
      List.iter ~f:(fun {color; count} ->
          let current_count = Hashtbl.find table color |> Option.value ~default:0 in
          Hashtbl.set table ~key:color ~data:(max current_count count)
        ) group
    ) groups;
  table

let parse_line line =
  match parse_string ~consume:All line_parser line with
  | Ok groups -> aggregate_max_counts groups
  | Error msg -> failwith ("Parsing error: " ^ msg)
;;
dapper dune
#

I've been parsing lines only so I can't speak directly. I think you're consuming all the lines until EOF but your parser doesn't have any idea what to do

#

docs say to use ~consume:Prefix to not require consuming the whole thing, which might be fine for not having to deal with eof?

#

but I would guess you will only get 1 line because you're not using many or sep_by

dapper dune
#

I was able to convert my line-parser game into a parser for the whole file with this definition: let file = (sep_by1 end_of_line game) <* end_of_line <* end_of_input

#

(which worked with ~consume:All as well as ~consume:Prefix)

winter vault
#

I solved using regex - but I really want to learn angstrom now. 😄

lime mica
#

Thoughts on today? I’m still working on it after a few hours lol, ended up iterating through the grid and building some struct with the number and the coordinates attached to it

dapper dune
#

I should have made a graph originally, instead did the finicky bits for both parts with separate string twiddling algorithms

signal flume
#

my naive solution would be to ||collect every digit-coordinate pair into a seq, group sequential digits into number-coordinate pairs, turn that into a map from coordinates to numbers, collect all symbols' coordinates and then index the 8 squares around each symbol's coordinate from the map, and if it exists, then add it to an accumulator and remove it from the map (no number is touched by more than one symbol), and then sum||

#

i havent actually written it yet though

dapper dune
#

there are also no symbols on the outer edge, which was a case I bothered to handle but when I was debugging realized it couldn't be causing trouble with the input

lime mica
#

The struct I'm shooting for is: [("142",[(0,2);(1,2);...]] i.e. points with their coordinates

dapper dune
#

where is integer power in stdlib ocaml 😦

dapper dune
#

just spent literally twenty minutes debugging "I copied the carriage return character (⏎) into the answer submission"

#

the math was good the whole time 🙃

dapper dune
#

much less painful than yesterday. n.b.: I used zarith but my part 2 total was <10 million, so it is probably unnecessary

#

zarith does give you integer power though (weirdly it takes a Z.t base and an integer exponent)

lime mica
#

Does anyone know whats' the best way to check if a string in a list is contained in another list using the Core library?

For some reason it doesn't like how I'm filtering the data. I get an error:
40 | let matches = List.filter ~f:(fun x -> Core.List.mem winners x) numbers in
^^^^^^^^^^^^^^^^^^^^^^^
Error: This expression has type equal:('a -> 'a -> bool) -> bool
but an expression was expected of type bool

(*
  [get_matches] will iterate over each number in [numbers]
  and find a match in [winners] if there's a match we keep
  the number if not, we filter it out. We will return an int
  representing the score for the card.
*)
let get_score winners numbers =
  let matches = List.filter ~f:(fun x -> List.mem winners x) numbers in
  let length_matches = (List.length matches) in
  if length_matches = 0 then 0
  else Z.pow (Z.of_int 2) (length_matches - 1) |> Z.to_int
;;```
dapper dune
#

Core.List.mem takes a labeled argument equal to test for equality of elements

#

the stdlib List.mem implicitly uses polymorphic equality

#

also whenever you see fun x -> f a b c x you can just use f a b c

#

you probably want something like List.filter ~f:(List.mem ~equal:String.equal winners)

lime mica
#

worked like a charm! thank you so much

#

it's quite confusing how o'caml has so many standard libraries compared with other languages

lime mica
dapper dune
#

cpu > brain, brute force got there before I could figure out the right way to combine maps

winter vault
#

I don't grasp the idea for day problem 2 😦

dapper dune
#

2 ideas: 1. ||trace ranges to (multiple) ranges through maps|| 2. ||combine maps by case analysis||

#

unless you mean "what is to be calculated" <snip>

winter vault
#

I understood what is to be calculated - it's the efficiency that is the problem. ||I saw usage of ranges but I don't understand it yet||

dapper dune
#

Consider a single ||range of seeds|| and the seed-to-soil map. Find a way to transform that ||range into multiple "output ranges"||

#

then repeat for each map

#

it helped me to draw a picture of what a map is using 2 number lines

bleak solar
#

I could only brute force it today... not sure I want to return to it for a better solution

lime mica
#

I ended up just using the ranges and comparing each seed with > or < than start/ends

#

now I'm just burning the cpu in part 2

lime mica
#

I'd be curious to see the range implementation, I'm sure there's a more elegant solution

winter vault
#

Today's puzzle should have been day 1

late rune
late rune
#

does anyone have a solution for part 2 of day 5 that works?
Mine has a off by 1 error that I fail to understand

bleak solar
#

My off by 1 error was in the ranges and it didn't show up for the example in either parts and also not the real input in part 1

late rune
#

Thanks I just found it: <= was the sneaky error

bleak solar
quasi cloak
# late rune does anyone have a solution for part 2 of day 5 that works? Mine has a off by 1...

Seems like you already got your answer but here is one possible approach

https://github.com/steffenhaug/aoc/blob/master/2023/5/main.ml

I'm not 100% happy with it, particularly the big true/false match in the middle, but I don't really know any better way to do the edge cases

GitHub
aoc/2023/5/main.ml at master · steffenhaug/aoc

Advent of Code. Contribute to steffenhaug/aoc development by creating an account on GitHub.

rugged pebble
#

Hm, I implemented the version with one traversal of the list of map ranges by map , but your version might be better in term of overall code complexity.

quasi cloak
#

It runs pretty fast, but i also think the problem is just quite small in terms of number of intervals, so I'm not quite sure

Since i re-traverse the rules for every set its at least worse than linear, so a solution with one traversal of the map ranges could probably beat it

fervent oriole
#

for day 3 pt 2, do we need to process negative numbers?

dapper dune
#

'-' is a part that is not a gear, not a negation

#

at least that's how I interpreted it, but then none of my gears touched a number with a leading -

fervent oriole
#

managed to figure it out

#

250 ugly lines of code

bleak solar
#

Camel Cards! In OCaml of course

dapper dune
#

I'm spinning on part 2 despite using a set to minimize branching paths 😦

#

looks like there are always 6 elements so maybe i'm just wasting time

#

|| am I supposed to use MATH to find the solution instead of simulating the cycles? an outrage ||

quasi cloak
#

||thankfully it was pretty simple math :-D||

late rune
#

Today is relatively easy, heres my solution:

#

||

let get_last l = List.rev l |> List.hd
let parse input = String.split_on_char ' ' input |> List.map int_of_string

let rec map_by_two f l =
  match l with
  | hd :: mid :: tl ->
      let r = f hd mid in
      r :: map_by_two f (mid :: tl)
  | _ -> []

let madness_descent l =
  let rec descent l =
    match List.for_all (( = ) 0) l with
    | true -> 0
    | false ->
        let res = map_by_two (fun l r -> r - l) l in
        get_last res + descent res
  in
  descent l + get_last l

let solve_part_1 input =
  List.map parse input 
  |> List.map madness_descent 
  |> List.fold_left ( + ) 0

let solve_part_2 input =
  List.map parse input 
  |> List.map List.rev 
  |> List.map madness_descent
  |> List.fold_left ( + ) 0

||

lime mica
#

Anyone had luck on day 12?

#

It broke my brain thinking about the permutations with ocaml

#

I’ve enjoyed it until now, it feels like a breath of fresh air coming from python

rugged pebble
#

part 1 works with naive backtracking, part 2 works with some memoization or dynamic programming

dapper dune
#

any pointers for day 21 part 2? Thought I was clever just tracking the 2 outer layers but it's still too many points.

dire crystal
#
  • you're tracking an area. How does an area grow?
  • look for specific properties in the input regarding the starting point
dire crystal
#

(it's OK to have a look at the solutions on the aoc reddit!)

dapper dune
#

I was hoping for exactly such a clue, my instinct is to handle the most general form of the question and don't check to see if the input is "nice". I think I see the intended solution now.

dire crystal
#

The problem with pulses has the same thing