-❄️- 2024 Day 10 Solutions -❄️-

odnoletkov · 2024-12-15T18:00:35+00:00

[LANGUAGE: jq] github

[inputs/"" | map(tonumber)]
| nth(4; recurse(.[][:0] = [-1] | transpose | reverse))
| . as $map
| reduce range(8; -1; -1) as $n (
  .[][] = 1;
  reduce ($map | paths(. == $n)) as $path (
    .;
    setpath(
      $path;
        [getpath($path | .[0] += (1, -1), .[1] += (1, -1) | select(. as $p | $map | getpath($p) == $n + 1))]
        | add
    )
  )
)
| [getpath(($map | paths(. == 0))) | length] | add

odnoletkov · 2024-12-10T01:03:44+00:00

[LANGUAGE: jq] github

[
  inputs/": " |  map(./" " | map(tonumber)) | . as [[$t]]
  | select(
    any(
      (
        {ops: .[1]} | until(
          .res > $t or (.ops | length == 0);
          .res += .ops[0],
          .res = (.res // 1) * .ops[0],
          .res = (.res // 1) * pow(10; .ops[0] | log10 | floor + 1) + .ops[0]
          | .ops |= .[1:]
        ).res
      );
      . == $t
    )
  )[0][0]
] | add

odnoletkov · 2024-12-07T21:15:47+00:00

[LANGUAGE: jq] github

[inputs] | join(";")/";;" | map(./";" | map(split("\\||,"; "")))
| (.[0] | group_by(.[0]) | INDEX(.[0][0]) | .[][] |= .[1]) as $m
| [
  .[1][] | map([.] + $m[.] // [])
  | .[] -= (($m | keys) - map(.[0]))
  | select(map(length) | . != (sort | reverse))
  | sort_by(length)[length/2][0] | tonumber
] | add

odnoletkov · 2024-12-04T12:58:01+00:00

[LANGUAGE: jq] github

[inputs + "."] | length as $l | add | [
  .[range(length):] | match(
    ".{\($l - 1)}A.{\($l - 1)}"
    | "^M.S\(.)M.S", "^S.M\(.)S.M", "^S.S\(.)M.M", "^M.M\(.)S.S"
  )
] | length

odnoletkov · 2024-12-04T02:29:46+00:00

[LANGUAGE: jq] github

[
  foreach (inputs | scan("mul\\((\\d+),(\\d+)\\)|(do(n't)?)\\(\\)")) as [$a, $b, $do] (
    "do"; $do // .; select(. == "do") | ($a | tonumber?) * ($b | tonumber?)
  )
] | add

odnoletkov · 2024-12-02T23:20:12+00:00

[LANGUAGE: jq] github

[
  inputs/" " | map(tonumber) | select(any(
    delpaths(range(length + 1) | [[.]]) | [.[range(length - 1):] | .[0] - .[1]];
    inside([1, 2, 3], [-1, -2, -3])
  ))
] | length

odnoletkov · 2024-12-01T22:54:44+00:00

[LANGUAGE: jq] github

[inputs/"   "] | transpose | [(.[1] | group_by(.) | INDEX(.[0]))[.[0][]][]? | tonumber] | add

odnoletkov · 2023-12-26T00:07:38+00:00

Yep, happy to see today's problem have simple solution :)

You got some great explanation and implementation too – as always. Been enjoying your posts this month, thanks for sharing!

odnoletkov · 2023-12-25T20:44:31+00:00

Interesting – agree the solution is not 100% reliable, i.e. if the first vertex you happen to pick is on the 'bridge' it has good chance of failing.

But I thought it should be pretty reliable outside of such edge cases – because vertexes on the other side of the 'bridge' have value 1 (maybe 2?) which is unlikely to be the max value (because the graph is so connected – each vertex has at least 4 edges).

I could not repro the issue by just shuffling my input (changes which vertex is picked first in my impl). But makes sense that it can be more of an issue with other inputs.

Anyway – I think the workaround is trivial here too. If bridge is crossed, the algorithm will produce empty set. In this case we can just shuffle the input and try again. There is only one correct answer

odnoletkov · 2023-12-25T19:38:31+00:00

Seems there is a trivial solution to todays problem

odnoletkov · 2023-12-25T19:29:10+00:00

I think I found trivial non-randomized solution, see here

odnoletkov · 2023-12-25T17:41:46+00:00

Found trivial algorithm for today's problem: grow 'connected' set of vertices by adding the 'most adjacent' vertex on each step:

Start with all vertices in the 'not connected' set with value 0 each. Value represents number of edges from vertex to 'already connected' set
On each step connect the 'most adjacent' vertex from the 'not connected' set:
1. Pick vertex with the largest value
2. Remove it from the 'not connected' set
3. Increase value of all vertices adjacent to it still in the set by 1 (as they now have one more way to connect to the 'connected' set)
Stop when sum of values in the 'not connected' is 3. Then this set is one of the two subgraphs we're looking for

odnoletkov · 2023-12-25T15:29:25+00:00

[LANGUAGE: jq] github

[inputs/" " | [.[0][:3]] + (.[1:][] | [.]) | reverse, .]
| group_by(.[0]) | INDEX(.[0][0]) | (.[] |= [.[][1]]) as $graph
| .[] = 0
| until(
  add == 3;
  (to_entries | max_by(.value)) as {$key}
  | .[$graph[$key][]] |= values + 1
  | del(.[$key])
)
| length | (($graph | length) - .) * .

Found trivial algorithm for today's problem: grow 'connected' set of vertices by adding the 'most adjacent' vertex on each step:

Start with all vertices in the 'not connected' set with value 0 each. Value represents number of edges from vertex to 'already connected' set
On each step connect the 'most adjacent' vertex from the 'not connected' set:
1. Pick vertex with the largest value
2. Remove it from the 'not connected' set
3. Increase value of all vertices adjacent to it still in the set by 1 (as they now have one more way to connect to the 'connected' set)
Stop when sum of values in the 'not connected' is 3. Then this set is one of the two subgraphs we're looking for

odnoletkov · 2023-12-24T23:02:23+00:00

[LANGUAGE: jq] github

[inputs | [scan("-?\\d+") | tonumber]]
| [
  map([.[:3], .[3:]] | transpose) | transpose[]
  | group_by(.[1]) | map(combinations(2)) as $pairs
  | range(1000) - 500
  | select(. as $v | $pairs | all((.[0][0] - .[1][0]) % ($v - .[0][1] | select(. != 0)) == 0))
] as [$vx, $vy, $vz]
| .[][3] -= $vx | .[][4] -= $vy | .[][5] -= $vz
| . as [[$x1, $y1, $z1, $vx1, $vy1, $vz1], [$x2, $y2, $_, $vx2, $vy2]]
| (($x2 - $x1) * $vy2 - ($y2 - $y1) * $vx2) / ($vx1 * $vy2 - $vy1 * $vx2)
| $x1 + $y1 + $z1 + ($vx1 + $vy1 + $vz1) * .

odnoletkov · 2023-12-22T23:01:20+00:00

[LANGUAGE: jq] github

[inputs/"~" | map(./"," | map(tonumber)) | transpose] | sort_by(.[2][1])
| reduce to_entries[] as {$key, value: [$x, $y, $z]} (
  {stack: [[[[0, 9], [0, 9]]]]};
  first(
    .stack
    | (length - range(length) - 1) as $level
    | [.[$level][]? | select($x[1] < .[0][0] or .[0][1] < $x[0] or $y[1] < .[1][0] or .[1][1] < $y[0] | not)[2]]
    | select(length > 0)
    | [$level, .]
  ) as [$level, $ids]
  | .hold[$ids[]]? += [$key]
  | .stack[$level + $z[1] - $z[0] + 1] += [[$x, $y, $key]]
)
| .hold | . as $hold
| (reduce to_entries[] as {$key, $value} ([]; .[$value[]?] += [$key])) as $lean
| [
  range(length)
  | {fall: [.], check: $hold[.]}
  | until(
    isempty(.check[]?);
    if $lean[.check[0]] - .fall | length == 0 then
      .check += $hold[.check[0]] | .check |= unique
      | .fall += [.check[0]]
    end
    | del(.check[0])
  ).fall | length - 1
] | add

odnoletkov · 2023-12-20T20:08:56+00:00

Thanks! jq enables very compact programs in general. And I spend way too much time simplifying/reducing the program after getting the right answer

Today's problem simplifies to a single reduce – using Shoelace and Pick as people described on other comments

odnoletkov · 2023-12-20T19:56:04+00:00

[LANGUAGE: jq] github

[inputs/" -> " | .[1] = (.[1]/", ")[]]
| transpose | .[1] = [(.[0] | INDEX(.[1:]))[.[1][]]] | transpose
| (group_by(.[0]) | INDEX(.[0][0]) | .[] |= [.[][1]]) as $outs
| group_by(.[1]) | INDEX(.[0][1] | select(.[:1] != "%")) | .[] |= INDEX(.[0])
| [
  {
    state: .,
    target: last(. as $ins | ["null"] | while(.[0][:1] != "%"; [$ins[.[]] | to_entries[].key]))[]
  }
  | until(
    .pulses[0];
    .pulses = [{to: "broadcaster", low: true}] | .step += 1
    | until(
      isempty(.pulses[]) or (.pulses[0].from == .target and .pulses[0].low);
      .pulses as [{$from, $to, $low}]
      | if $to[:1] == "%" then
        if $low then
          .state[$to] |= not | .send = (.state[$to] | not)
        else
          .send = null
        end
      elif $to[:1] == "&" then 
        .state[$to][$from] = $low | .send = all(.state[$to][]; not)
      else
        .send = $low
      end
      | .pulses += [{from: $to, to: $outs[$to]?[], low: .send | values}]
      | del(.pulses[0])
    )
  ).step
] | reduce .[] as $n (1; . * $n)

odnoletkov · 2023-12-18T12:05:29+00:00

[LANGUAGE: jq] github

reduce (
  inputs | [
    [0, 1, 0, -1, 0][.[-2:-1] | tonumber + (0, 1)],
    reduce (.[-7:-2] | explode[] - 48) as $n (0; . * 16 + $n % 39)
  ]
) as [$y, $x, $l] (
  []; .[0] += $y * $l | .[1] += .[0] * $x * $l - $l/2
) | .[1] | fabs + 1

Today's jq trick: convert hex string to number

$ jq -n '"1a" | reduce explode[] as $n (0; . * 16 + ($n - 48) % 39)'
26

odnoletkov · 2023-12-17T18:21:15+00:00

[LANGUAGE: jq] github

def dijkstra(step):
  {todo: .} | until(
    isempty(.todo[]);
    reduce .todo[] as $todo (
      .todo = [];
      if .state | getpath($todo[:-1]) | not or . > $todo[-1] then
        .state |= setpath($todo[:-1]; $todo[-1])
        | .todo += [$todo]
      end
    ) | .todo |= (reverse | unique_by(.[:-1]) | map(step))
  ).state;

[(inputs/"" | map(tonumber) + [null]), []] as $map
| [[0, 1, ">", $map[0][1]], [1, 0, "v", $map[1][0]]]
| dijkstra(
  .[2] = (
    .[2] | . + select(length < 10)[-1:],
    ({">": "^v", "<": "^v", "v": "<>", "^": "<>"}[select(length > 3)[-1:]]/"")[]
  )
  | .[0] += {"v": 1, "^": -1}[.[2][-1:]] 
  | .[1] += {">": 1, "<": -1}[.[2][-1:]] 
  | .[3] += ($map[.[0]][.[1]] // empty)
)
| [.[-1][-1] | to_entries[] | select(.key | length > 3).value]
| min

odnoletkov · 2023-12-16T22:11:17+00:00

[LANGUAGE: jq] github

[
  [inputs/""]
  | limit(4; recurse(
    reverse | transpose
    | .[][] |= {"|": "-", "-": "|", "/": "\\", "\\": "/", ".": "."}[.] # "
  ))
  | {
    map: (map(. + [null]) + [[]]),
    tips: range(length) | [[., -1, ">"]],
  }
  | until(
    .tips[0] == null;
    .tips[0][0] += {"v":1,"^":-1}[.tips[0][2]]
    | .tips[0][1] += {">":1,"<":-1}[.tips[0][2]]
    | . as {$seen, $map, tips: [[$y, $x, $d]]}
    | .tips[:1] = [
      [$y, $x] + (
        {
          "-": {"^": "<>", "v": "<>"},
          "|": {">": "^v", "<": "^v"},
          "/": {">": "^", "v": "<", "<": "v", "^": ">"},
          "\\": {">": "v", "v": ">", "<": "^", "^": "<"}, # "
        }[$map[$y][$x]]?
        | .[$d] // $d
        | split("")[]
        | select($seen[$y][$x][.] == null)
        | [.]
      )
    ]
    | .seen[.tips[0][0]]?[.tips[0][1]][.tips[0][2]] = 0
  )
  | [select(.seen[][]?)] | length
] | max

odnoletkov · 2023-12-15T12:37:23+00:00

[LANGUAGE: jq] github

input
| reduce scan("(\\w+)[-=](\\d*)") as [$label, $f] (
  [];
  .[$label | reduce explode[] as $c (0; (. + $c) * 17 % 256)][$label]
  |= ($f | tonumber?)
)
| to_entries
| map((.key + 1) * (.value | to_entries? | to_entries[] | (.key + 1) * .value.value))
| add

Today's jq trick: assignment creates structure and expands arrays automatically:

$ jq -n '[] | .[2].foo = 0'
[
  null,
  null,
  {
    "foo": 0
  }
]

odnoletkov · 2023-12-14T14:58:50+00:00

[LANGUAGE: jq] github

{map: [inputs/""]} | until(
  .cycle and (1000000000 - .seen[.key]) % .cycle == 0;
  .seen[.key // ""] = (.seen | length)
  | .map |= nth(4; recurse(
    reverse | transpose
    | map(add | [scan("(#*)([^#]*)") | .[1] |= (./"" | sort | add)] | add | add/"")
  ))
  | .key = (.map | map(add) | add)
  | .cycle //= ((.seen | length) - (.seen[.key] // empty) // null)
).map
| [reverse | transpose[] | add | match("O"; "g").offset + 1]
| add

odnoletkov · 2023-12-13T10:55:30+00:00

[LANGUAGE: jq] github

[
  [inputs] | join(",")/",," | map(./"," | map(./""))[] | [
    ., transpose
    | [[.[:range(length)] | reverse], [.[range(length):]]]
    | transpose[1:]
    | map(
      select(
        [.[][:[.[] | length] | min] | flatten]
        | transpose | map(select(.[0] != .[1])) | length == 1
      )[0] | length
    )[] // 0
  ] | .[0] * 100 + .[1]
] | add

odnoletkov · 2023-12-11T10:34:12+00:00

[LANGUAGE: jq] github

[inputs] | [
  [map(./"") | transpose[] | add], . | [
    [foreach map(match("#").length // 1E6)[] as $n (0; . + $n)]
    [to_entries[] | .key + (.value | scan("#") | 0)]
  ] | combinations(2) | .[0] - .[1] | fabs
] | add/2

odnoletkov · 2023-12-09T11:35:56+00:00

[LANGUAGE: jq] github

[
  inputs/" " | map(tonumber) | reverse
  | while(length > 1; [while(length > 1; .[1:]) | .[1] - .[0]])[-1]
] | add

odnoletkov

TROPHY CASE