Advent of Code 2021 - Day 7

part 1

part 2

2 Likes

Here is my solution:

1 Like

Easy one! :smiley:
y2021/day_07.ex

2 Likes

Not sure if this was accidentally swapped with Day 3 or something. Way too easy.

defmodule AdventOfCode.Y2021.Day07 do
  use AdventOfCode.Helpers.InputReader, year: 2021, day: 7

  def run_1, do: input!() |> parse() |> alignments() |> Enum.min()
  def run_2, do: input!() |> parse() |> alignments(&cost/1) |> Enum.min()
  def parse(data), do: data |> String.split(",") |> Enum.map(&String.to_integer/1)

  defp alignments(positions, cost_fn \\ &Function.identity/1) do
    for i <- positions do
      Enum.sum(for j <- positions, do: cost_fn.(abs(i - j)))
    end
  end

  defp cost(steps), do: (steps == 0 && 0) || div(steps * (steps + 1), 2)
end
2 Likes

There is also a Tweet sized version (Not recommended, not pleasant to look at)

Not as short as the other solutions around here, however my sleepy brain decided to implement a binary search (and also to group all of the crabs that are in the same initial position), so at least it’s faster:

Had a bit of trouble figuring out the formula for part 2 cost and didn’t want to brute force it.

# Day 7

## Deps & preparation

```elixir
Mix.install([
  {:kino, "~> 0.4.0"}
])

input = Kino.Input.textarea("Please paste your input file:")
```

## Input

```elixir
crabs =
  Kino.Input.read(input)
  |> String.split([","], trim: true)
  |> Enum.map(&String.to_integer/1)
```

## Part 1

```elixir
# fuel cost is always 1
fuel_calc = fn positions, target_pos ->
  Enum.map(positions, fn position ->
    abs(position - target_pos)
  end)
  |> Enum.sum()
end

Enum.map(Enum.min(crabs)..Enum.max(crabs), fn target ->
  fuel_calc.(crabs, target)
end)
|> Enum.min()
```

## Part 2

```elixir
# fuel cost grows by step count (1 is 1, 2 is 2)
fuel_calc = fn positions, target_pos ->
  Enum.map(positions, fn position ->
    x = abs(position - target_pos)
    div(x * (x + 1), 2)
  end)
  |> Enum.sum()
end

Enum.map(Enum.min(crabs)..Enum.max(crabs), fn target ->
  fuel_calc.(crabs, target)
end)
|> Enum.min()
```

Glad to take a break from day 4 and 5 lmao

defmodule Day7 do
  def parse(input) do
    {:ok,file} = File.read(input) 
    file |> String.split(",") |> Enum.map(&String.to_integer/1)
  end

  #Gives fuel cost needed for list l to move to position n
  def position(l,n,f,c), do: Enum.reduce(l,c,fn x,c->c+f.(abs(x-n)) end)
  
  #Gives fuel costs for every position on given list l
  def positions(l,f), do: Enum.reduce(1..(length l),[],fn x, c -> [position(l,x,f,0)|c] end)

  def part1(input), do: parse(input) |> positions(&(&1)) |> Enum.min()
  def part2(input), do: parse(input) |> positions(&(div(&1*(&1+1),2))) |> Enum.min()
end

Not proud of today’s solution :joy:
Ended up implementing binary search, using gradients of two consecutive points to figure out which part of the split to take.
Much much more complicated than many of the solutions posted today

hey, this looks so simple, that I had to try it.
Sadly, doesn’t seem to work for my inputs. Could it be that your solution only considers positions that appear in the input file? but the minimum cost might not be one of the original positions. It might be that every submarine needs to be moved

$ elixir day_7.ex
"me"
Part 1: fuel: 342730
Part 2: position: 476
Part 2: fuel: 92335207
"code-shoily"
Part 1: fuel: 342730
Part 2: fuel: 92338199
2 Likes

Yes, this is an error in my implementation, I assumed the “minimal position” will be one of the existing positions, and unfortunately for me, it worked with my input as the minimal position in my input set was also a position of a crab :confused:

A friend brought this to my attention last night and I fixed that. I should really get into the habit of trying out with test inputs even if the solution is instantly correct. Thanks for mentioning this though, I will update the code up there.

Just in case you want to run the code again, here’s the corrected link: advent_of_code/day_07.ex at master · code-shoily/advent_of_code (github.com)

(Just used a range of min and max of the positions on the outer iteration and it worked fine for all the test inputs I tried)

Here is mine:

defmodule Day7 do
  @doc """
      iex>Day7.part1("16,1,2,0,4,2,7,1,2,14")
      37
  """
  def part1(input) do
    solve(input, &Function.identity/1)
  end

  @doc """
      iex>Day7.part2("16,1,2,0,4,2,7,1,2,14")
      168
  """
  def part2(input) do
    solve(input, &Enum.sum(1..&1))
  end

  defp solve(input, increase_fun) do
    submarines = parse_input(input)
    {min, max} = Enum.min_max(submarines)

    fuel_expenses =
      for pos <- min..max do
        Enum.reduce(submarines, 0, fn submarine, total_fuel ->
          abs(submarine - pos)
          |> then(increase_fun)
          |> Kernel.+(total_fuel)
        end)
      end

    Enum.min(fuel_expenses)
  end

  defp parse_input(input) when is_binary(input) do
    input
    |> String.split(",")
    |> Enum.map(&String.to_integer/1)
  end
end

See on GitHub.

1 Like

My Day 7:

defmodule Day7 do
  def part1(input) do
    input =
      input
      |> parse()
      |> Enum.sort()

    count = Enum.count(input)
    median = Enum.at(input, div(count, 2))

    Enum.reduce(input, 0, fn elem, acc ->
      abs(elem - median) + acc
    end)
  end

  def part2(input) do
    input = parse(input)

    avg = Enum.sum(input) / Enum.count(input)

    [floor(avg), ceil(avg)]
    |> Enum.map(fn cheapest ->
      Enum.reduce(input, 0, fn elem, acc ->
        n = abs(elem - cheapest)
        acc + div(n * (n + 1), 2)
      end)
    end)
    |> Enum.min()
  end

  defp parse(input) do
    input
    |> String.split(",")
    |> Enum.map(&String.to_integer/1)
  end
end
2 Likes

I first calculated the frequencies for the input, figured it would mean fewer operations.

y2021/day-07.livemd

I did the same initially but it did not work for my input, forcing me to re-read the prompt and look at the example for part 2 more closely.
Even worse, for my part 1 I decided to just guess that the value at the midpoint of the sorted list of input had the best chance of being the right reference point and it worked for my input. Very fast, not very sound.

Solved with a genetic algorithm. :smiley:

3 Likes

That is really clever.