rugyoga

Advent of Code 2024 - Day 9

Not the prettiest but it works

rugyoga/aoc2023/blob/main/lib/2024/9.ex

import AOC

aoc 2024, 9 do
  def p1(input) do
     rle = common(input)
     total_runs = rle |> Enum.filter(&is_tuple/1) |> Enum.map(&elem(&1, 1)) |> Enum.sum
     fill_gaps(rle, Enum.reverse(rle), total_runs)
     |> take(total_runs)
     |> checksum(0)
     |> Enum.sum()
  end

  def fill_gaps([], _, _), do: []
  def fill_gaps(_, _, runs) when runs <= 0, do: []
  def fill_gaps([{x, n} | rle], elr, runs), do: [{x, n} | fill_gaps(rle, elr, runs-n)]
  def fill_gaps([gap | rle], [{y, m} | elr], runs) do
    gap = min(gap, runs)
    cond do
      gap == 0 -> fill_gaps(rle, [{y, m} | elr], runs)
      gap  > m -> [{y, m} | fill_gaps([gap - m | rle], elr, runs-m)]

This file has been truncated. show original

30 comments

#advent-of-code #2024

19 1176 30

2025-01-01 17:51:39 UTC

Most Liked

lud

Yes I thought it would be slow because for part 2 I modify the free blocks list not only at the head, but lower in the linked list.

But I guess while slow, linked lists are highly optimized in Erlang.

I’d suggest you run my solution on your machine though. I know that @bjorng uses the time reported by mix test for instance. I use :timer.tc in my helper commands so it’s going to report lower times.

Post #23

bjorng

Erlang Core Team

It took me a long time to find an off-by-one error in part 2. The combined runtime for both parts is 0.4 seconds.

github.com

bjorng/advent-of-code/blob/main/2024/day09/lib/day09.ex

defmodule Day09 do
  def part1(input) do
    map = parse(input)
    first = 0
    {last,_} = Enum.max(map)
    move(map, first, last)
    |> Enum.sort
    |> Enum.flat_map(fn {_, {items, _}} -> items end)
    |> checksum
  end

  defp move(map, first, last) when last <= first, do: map
  defp move(map, first, last) do
    case map do
      %{^last => {items, _}} ->
        {map, first} = Map.delete(map, last)
        |> insert(first, items, length(items))
        move(map, first, last - 1)
    end
  end

This file has been truncated. show original

Post #3

billylanchantin

Glad it helped! I’ll also recommend @bjorng’s solution (or anyone else who used a map instead of a list to track state). Map-based solutions often end up being more performant. I’m trying to write really terse solutions this year so I end up sacrificing speed for LOC.

Post #18

lud

My solution takes 11 seconds adventofcode/lib/solutions/2024/day09.ex at main · lud/adventofcode · GitHub

I have an entry in the disk (a map) for each block. I will see if I can keep all contiguous file parts as a single map entry.

Post #5

sevenseacat

Author of Ash Framework

No. The example ends with 402 so there’s 4 eights, 0 gap, and 2 nines.

What does your code here advent_of_code/lib/2024/day_9/Part1.ex at master · jarlah/advent_of_code · GitHub do if n2 is zero?

Your 90909 example is also wrong - it should be 000000000111111111222222222. The description says:

A disk map like 90909 would represent three nine-block files in a row (with no free space between them).

Post #9

Where Next?

View thread on forum (has 30 responses!)

advent-of-code

2024

Home Learning Resources>Coding Challenges

#advent-of-code #2024

19 1178 30

Last post

Advent of Code 2024 - Day 9

rugyoga

Advent of Code 2024 - Day 9

Most Liked

lud

bjorng

billylanchantin

lud

sevenseacat

Where Next?

Popular in Challenges

Advent of Code - Day 12

Advent of Code - Day 1

Advent of Code 2022 - Day 8

Advent of Code 2023 - Day 6

Advent of Code 2022 - Day 5

Advent of Code 2019 - Day 2

Advent of Code 2021 - Day 7

Advent of Code 2024 - Day 5

Advent of Code 2021 - Day 10

Advent of Code 2019 - Day 6

Other popular topics

Ecto: Validating belongs_to association is not nil?

Removing spaces and characters from string

Typespecs - best way to spec keyword lists?

(Postgrex.Error) ERROR 42804 (datatype_mismatch): column "" cannot be cast automatically to type integer

How to convert map to string (separated with ,)

Anonymous functions with multiple body

Put/update deep inside nested maps (and auto-create intermediate keys)

Docker run Error loading shared library libstdc++.so.6 and libgcc_s.so.1

Kaffy - a quick and flexible admin interface for phoenix applications

How To Implement if...else if...else condition

Learning Resources>Coding Challenges

Latest on Elixir Forum

Sponsor Spotlight

Our Sponsors

Categories:

Sub Categories:

Forums

Our Sponsors

We're in Beta