# Advent of Code 2021 - Day 7

This topic is about Day 7 of the Advent of Code 2021.

We have a private leaderboard (shared with users of the elixir forum):

The entry code is:
`370884-a6a71927`

5 Likes

This day also seems straightforward, I suppose bruteforce approach works here :

``````main(File) ->
Data = [ binary_to_integer(X) || X <- binary:split(RawData, <<",">>, [global, trim]) ],
io:format("part 1: ~p~n", [solve1(Data)]),
io:format("part 2: ~p~n", [solve2(Data)]),
ok.

solve1(Data) ->
run(fun(X) -> X end, Data).

run(FuelFun, Data) ->
lists:min([ lists:sum([ FuelFun(abs(D - N)) || D <- Data ])
|| N <- lists:seq(lists:min(Data), lists:max(Data)) ]).

solve2(Data) ->
run(fun fuel/1, Data).

fuel(X) ->
X * (1 + X) div 2.
``````
6 Likes

The first one is equivalent to finding the median, so it can theoretically be done in linear time. The second one I have also just brute-forced.

4 Likes

I used bisection for both parts: pick a pivot, compute the number of moves needed for all to align, compute the same for the adjacent positions to determine which part of all positions to use next.

For part 2 I only needed to adapt the function to compute the number of moves, the rest remained the same.

4 Likes

The first is about Manhattan distance, it’s the median. For the second, after I sorted the list I need to traverse points while fuel value is decreasing. When I get a greater fuel, previous position is the solution.

5 Likes

Was tricked into the linear time solution for the first (median) assuming brute force will be too slow for the second. Well then this time it wasn’t.

Aren’t you guys posting your solutions a bit early?

I mean, yes the leaderboard is very wonky anyway and mainly tells what timezone people live in and if they are early risers, since all tasks don’t take much time.

But shouldn’t everyone try their own solution first so why post so early?

5 Likes

In an earlier thread (day 1 or 2?), it was mentioned that it’s a reasonable assumption that the AoC threads should be avoided by those not wanting to be spoiled.

I don’t think someone who is overly competitive is going to wait for others to post their solutions first. Those just doing it for fun at their own leisure will likely avoid the thread or maybe even come here for hints if stuck.

4 Likes

I’m avoiding but people stuck might rather ask questions early on and get hints than just see a full solution here.

Regarding competitiveness: the leaderboard has little to do with coding and lots to do with willingness to set alarm clock (for me it would be 6am) and get up early (I’m a late person), or people living in convenient time zones.

There is a missed opportunity here … 24 days of AoC and 24 hours in a day would make a nice shifting through timezones pattern (except that depending on the direction. we could do only 23 or 25 puzzle days then)

5 Likes

Done. A prettier code this time. Not efficient, though.

3 Likes

Yesterday I was stuck, @peerst. I came to the thread, read only the first few words (no code) and was able to do it on my own.

3 Likes

Par1:

``````part1() ->
Bin = <<"16,1,2,0,4,2,7,1,2,14\n">>,
Data = [binary_to_integer(X) || X <- re:split(Bin, "[,/\n]+"), X /= <<>>],
lists:min(fuel(Data, Data)).

fuel([], _)       -> [];
fuel([H|T], Data) -> [lists:sum([abs(D - H) || D <- Data]) | fuel(T, Data)].
``````

Part2:

``````part2() ->
Bin = <<"16,1,2,0,4,2,7,1,2,14\n">>,
Data = [binary_to_integer(X) || X <- re:split(Bin, "[,/\n]+"), X /= <<>>],
lists:min(fuel2(lists:seq(lists:min(Data), lists:max(Data)), Data)).

fuel2([], _) ->
[];
fuel2([H|T], Data) ->
Inc = fun(X) -> X * (1 + X) div 2 end,
[lists:sum([Inc(abs(D - H)) || D <- Data]) | fuel2(T, Data)].
``````
4 Likes

for part 2 you can use the mean of the crabs’ positions instead of bruteforcing

``````-module(d7).
-export([main/0]).
-define(FILENAME, 'd7.in').

main() ->
CrabsPos   = lists:map(fun binary_to_integer/1, string:lexemes(Raw, ",\n")),
CrabsCount = length(CrabsPos),
Median     = lists:nth(round(CrabsCount/2), lists:sort(CrabsPos)),
MeanFloor  = floor(lists:sum(CrabsPos) / CrabsCount),
MeanCeil   =  ceil(lists:sum(CrabsPos) / CrabsCount),
Fuel1      =     element(1, lists:foldl(fun fuel1/2, {0, Median   }, CrabsPos)),
Fuel2      = min(element(1, lists:foldl(fun fuel2/2, {0, MeanCeil }, CrabsPos)),
element(1, lists:foldl(fun fuel2/2, {0, MeanFloor}, CrabsPos))),
{Fuel1, Fuel2}.

fuel1(Pos, {Fuel, Median}) ->
{Fuel + abs(Median-Pos), Median}.

fuel2(Pos, {Fuel, Mean}) ->
Goal = abs(Mean-Pos),
{Fuel + Goal*(Goal+1)/2, Mean}.
``````
5 Likes

I am just smug to be briefly ahead of one of my Erlang heroes, @MononcQc! (Even if only because he is using Awk instead of Erlang).

4 Likes

My first AOC problem with LFE.

``````(defmodule day7
(export (part1 0) (part2 0)))

(defun part1 ()
(lists:min
(lists:map

(defun part2 ()
(lists:min
(lists:map

(defun min_max (list)
(lists:seq (lists:min list) (lists:max list)))

(defun fuel_consumption (pos list)
(lists:sum
(lists:map
(lambda(x) (abs (- pos x)))
list)))

(defun fuel_consumption2 (pos list)
(lists:sum
(lists:map
(lambda(x) (cost (abs (- pos x))))
list)))

(defun cost (x) (* x (/ (+ x 1) 2)))

(lists:map
(lambda (x) (element 1 (string:to_integer x)))
(string:split
(string:trim
) "," 'all)))
``````

I feel like I have been assimilated by a functional cyborg 5 Likes

Congrats!

Fwiw I only had time to do the Awk version today until AWS started melting down, so that’s all I get to show:

``````func min(a,b) { return (a<b) ? a : b }
func max(a,b) { return (a>b) ? a : b }
func abs(x) { return (x<0) ? x*-1 : x }

BEGIN { FS="," }
{ for (i=1; i<=NF; i++) { l[\$i]++ } }
END {
minf=2^PREC
for (i in l) { mi=max(i, mi) }
for (i=0; i<=mi; i++) {
g=0;
for (j in l) {
d=abs(j-i);
g+=(d+1)/2*d*l[j]
}
minf=min(minf,g)
}
print minf
}
``````

I wish there was a nicer way to set the initial max value. I started with just `999999999` and cleaned it up with `2^PREC` (which is 2^53, the max float value). Also I’m a bit annoyed with having to define basic functionality like `abs()` and `min()` or `max()`.

4 Likes

Ugly code this time, I over-complicated my solution a bit. Didn’t really have to use Arrays but wanted to write the bindings. And there’s probably some way to solve this dynamically by following a gradient instead of computing all costs. But it got the answer and I am a day behind…

edit: After looking at other people’s solutions I feel a bit silly I didn’t think of checking the median / mean values first, but oh well, it worked 3 Likes