Day 7: The Treachery of Whales

Part 1

I think the solution to this challenge is extremely simple and is basically calculating the integer median of all values.

That is intuitively the position that will cause the least number of movements overall to get all crabs aligned.

If you think, for example, of it as a modelling problem where each crab is in an increasing x position and a y position equivalent to its given current alignment and we'd like to fit a horizontal line, the minimization will result in the median.

I suppose it will not be the average, because a single outlier (a hermit crab!! lol) could cause all crabs to have to move, whereas the median will make the hermit move alot, and the rest of the crabs move just a little.

Let's try it!

input = "16,1,2,0,4,2,7,1,2,14"

positions = input |> String.split(",") |> Enum.map(&String.to_integer/1)

[16, 1, 2, 0, 4, 2, 7, 1, 2, 14]

The median is basically the number between the middle elements of the ordered set

median = positions |> Enum.sort() |> IO.inspect() |> Enum.at(div(length(positions), 2))

positions
|> Enum.reduce(0, &(abs(&1 - median) + &2))

[0, 1, 1, 2, 2, 2, 4, 7, 14, 16]

37

puzzle_input =
  "1101,1,29,67,1102,0,1,65,1008,65,35,66,1005,66,28,1,67,65,20,4,0,1001,65,1,65,1106,0,8,99,35,67,101,99,105,32,110,39,101,115,116,32,112,97,115,32,117,110,101,32,105,110,116,99,111,100,101,32,112,114,111,103,114,97,109,10,315,1081,464,841,82,86,483,2,1163,1189,184,369,510,519,13,0,1127,899,1157,1018,3,1014,507,330,20,4,374,641,1768,773,1130,827,1132,166,217,3,460,51,767,484,109,48,143,977,790,1139,426,50,391,537,1140,478,41,1560,1457,180,814,138,338,751,1164,1088,157,1168,163,880,1477,1236,496,446,582,215,840,19,6,626,84,473,977,191,281,1166,230,643,772,985,65,290,389,409,366,1339,499,4,20,262,58,1294,1043,1625,77,284,415,220,583,110,70,639,424,273,28,669,920,1580,434,377,24,446,113,100,1040,1271,874,73,629,87,88,877,959,896,1478,377,14,409,1150,975,547,181,367,549,941,923,1175,19,293,91,1079,495,8,156,807,1423,337,544,505,694,45,968,349,472,1333,43,1339,139,383,676,105,81,0,208,397,628,1033,429,1642,1635,397,675,273,263,165,965,600,571,834,13,411,592,2,49,1706,1288,241,115,5,1046,1301,688,474,34,817,200,410,233,181,173,8,124,527,1266,238,33,482,1066,1074,381,197,139,828,45,843,133,823,265,685,463,680,958,561,101,258,339,7,578,38,176,1127,57,147,186,795,685,769,27,547,1089,252,125,1182,63,907,1300,1022,1040,613,1082,964,693,7,130,259,75,5,1172,1380,362,1203,1936,666,50,600,482,497,106,724,153,52,480,848,1216,814,156,730,20,831,441,160,81,4,750,81,537,1006,320,493,526,63,112,0,467,65,50,1228,105,121,1123,568,232,6,946,436,429,1116,309,13,1471,60,15,1143,385,34,374,140,413,24,593,97,7,127,504,221,1380,585,661,326,709,91,1323,722,256,346,43,296,5,477,356,182,476,1109,107,1137,151,1303,201,796,760,1144,51,410,694,68,49,78,32,24,781,1347,34,16,137,999,47,94,788,409,188,853,362,862,576,386,621,52,341,908,362,160,1373,1118,368,222,125,389,327,168,136,197,445,206,564,517,95,547,765,526,584,1115,150,674,312,246,33,168,266,92,535,23,442,518,145,358,531,150,174,545,1525,576,1721,5,1369,1112,787,9,1266,955,265,385,823,1129,62,1045,1682,4,157,268,449,77,340,12,401,818,28,722,232,116,41,1250,504,1448,108,748,161,42,634,975,1046,50,371,474,669,271,910,263,1091,566,35,181,29,163,652,497,1108,878,448,44,241,319,585,530,176,596,1334,2,181,63,807,53,738,851,952,502,127,983,59,0,22,1143,393,75,292,105,592,649,1709,1505,0,1,634,1815,1505,23,145,117,1286,1641,372,273,348,688,113,0,823,1829,607,89,110,30,667,997,987,354,804,766,243,211,783,76,152,401,667,477,555,280,504,252,287,448,495,59,83,353,219,112,198,174,1496,3,803,765,1166,446,1062,451,1365,778,115,381,102,3,209,236,8,87,169,145,139,1032,1702,176,525,436,73,5,35,1512,198,370,70,358,135,46,153,473,48,521,315,709,473,136,363,60,256,1048,81,1037,59,456,343,18,935,51,1329,1624,1134,189,526,578,190,1635,396,211,583,83,165,89,1073,1251,241,607,833,105,183,300,998,1849,1127,734,325,767,215,1375,326,300,228,246,1221,204,40,718,26,231,31,608,453,11,169,104,380,339,281,23,778,1023,385,251,972,47,101,779,122,471,1003,45,261,1223,493,48,92,948,1269,519,319,720,3,145,1509,24,65,219,25,687,781,465,38,554,244,99,335,55,817,13,1009,319,112,93,537,454,298,393,1217,941,673,356,142,213,140,422,11,1050,143,270,21,58,145,188,486,821,942,1,420,844,451,45,560,701,758,624,149,267,63,286,236,339,120,1145,747,1835,471,540,684,1549,204,285,0,335,387,729,81,17,162,24,25,212,64,1051,373,629,187,34,228,562,362,25,16,475,114,1092,736,1014,896,91,1516,93,210,12,432,88,411,353,638,480,418,1087,45,818,9,606,568,286,507,139,1281,1709,228,510,218,484,498,559,948,88,207,968,84,142,364,44,15,542,133,363,299,753,212,313,277,589,628,821,1481,2,59,18,125,644,324,38,704,559,387,72,36,15,231,647,57,202,1140,311,1125,538,611,192,459,1,598,310,211,406,1868,624,1126,373,369,202,373,1309,903,554,202,259,1174,254,436,997,39,513,811,28,948,434,428,426,419,167,320,748,145,447,735,1128,440,232,211,481,332,591,4,325,875,45,834,269,527,361,603,488,1071,166,1734,326,241,1434,899,738,225,240,1407,6,1197,743,850,25,136,241"

positions = puzzle_input |> String.split(",") |> Enum.map(&String.to_integer/1)

median = positions |> Enum.sort() |> Enum.at(div(length(positions), 2))

positions
|> Enum.reduce(0, &(abs(&1 - median) + &2))

342534

Part 2

For part 2, the cost of moving changes linearly with distance, so median will not work, and I am not seeing an intuitive way to solve this...

moving 4 steps costs in fact (1 + 2 + 3 + 4), this is an arithmethical progression sum, which can be calculated with

$Sn = n/2[2a + (n − 1) × d]$

where,

• a = first term of arithmetic progression,
• n = number of terms in the arithmetic progression, and
• d = common difference

In our case, it can be simplified to

$Sn = \frac {n[2 + (n − 1)]} 2$

And our $n$ is actually the distance between crab $m$ current position $x_m$ and the proposed alignment position $p$.

$n = |p - x_m|$

Let's think in optimization terms...

The cost function we need to minimize is:

$\sum_{\substack{0<i<m}} \frac {(|p - x_i|)[2 + ((|p - x_i|) − 1)]} 2$

This is clearly a quadratic function of 1 free variable p, which means it might well look like a parabola with a single global minimum point (the best cost).

I can brute force it by:

1. use the median as the starting point,
2. see which way it decreases, then
3. go down until it increases again.

p = 342_534

cost =
  positions
  |> Enum.reduce(0, fn x_i, acc ->
    n = abs(p - x_i)
    acc + div(n * (2 + (n - 1)), 2)
  end)

# cost for the initial position 342534 was  58502586209944
# decrementing the position to  342533 gets 58502244150530
# incrementing the position to 342535 gives 58502928270358
# it means we need to decrement until it starts incrementing

58502586209944

defmodule Recur do
  def recur(pos, k) do
    recur(pos, k - 1, cost(pos, k))
  end

  def recur(pos, k, last_cost) do
    case cost(pos, k) do
      # we want to exit when cost starts rising
      c when c > last_cost -> last_cost
      c -> recur(pos, k - 1, c)
    end
  end

  defp cost(pos, k) do
    pos
    |> Enum.reduce(0, fn x_i, acc ->
      n = abs(k - x_i)
      acc + div(n * (2 + (n - 1)), 2)
    end)
  end
end

Recur.recur(positions, p)

94004208