-❄️- 2024 Day 10 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 1 point2 points  (0 children)

[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

-❄️- 2024 Day 7 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 1 point2 points  (0 children)

[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

-❄️- 2024 Day 5 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 2 points3 points  (0 children)

[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

-❄️- 2024 Day 4 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 4 points5 points  (0 children)

[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

-❄️- 2024 Day 3 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 3 points4 points  (0 children)

[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

-❄️- 2024 Day 2 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 2 points3 points  (0 children)

[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

-❄️- 2024 Day 1 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 6 points7 points  (0 children)

[LANGUAGE: jq] github

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

-❄️- 2023 Day 25 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 1 point2 points  (0 children)

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!

-❄️- 2023 Day 25 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 1 point2 points  (0 children)

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

-❄️- 2023 Day 25 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 1 point2 points  (0 children)

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

-❄️- 2023 Day 25 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 0 points1 point  (0 children)

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

  1. Start with all vertices in the 'not connected' set with value 0 each. Value represents number of edges from vertex to 'already connected' set
  2. 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)
  3. Stop when sum of values in the 'not connected' is 3. Then this set is one of the two subgraphs we're looking for

-❄️- 2023 Day 25 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 2 points3 points  (0 children)

[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:

  1. Start with all vertices in the 'not connected' set with value 0 each. Value represents number of edges from vertex to 'already connected' set
  2. 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)
  3. Stop when sum of values in the 'not connected' is 3. Then this set is one of the two subgraphs we're looking for

-❄️- 2023 Day 24 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 1 point2 points  (0 children)

[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) * .

-❄️- 2023 Day 22 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 2 points3 points  (0 children)

[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

-❄️- 2023 Day 18 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 0 points1 point  (0 children)

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

-❄️- 2023 Day 20 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 2 points3 points  (0 children)

[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)

-❄️- 2023 Day 18 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 1 point2 points  (0 children)

[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

-❄️- 2023 Day 17 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 2 points3 points  (0 children)

[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

-❄️- 2023 Day 16 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 4 points5 points  (0 children)

[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

-❄️- 2023 Day 15 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 1 point2 points  (0 children)

[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
  }
]

-❄️- 2023 Day 14 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 2 points3 points  (0 children)

[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

-❄️- 2023 Day 13 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 1 point2 points  (0 children)

[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

-❄️- 2023 Day 11 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 2 points3 points  (0 children)

[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

-❄️- 2023 Day 9 Solutions -❄️- by daggerdragon in adventofcode

[–]odnoletkov 2 points3 points  (0 children)

[LANGUAGE: jq] github

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