Further cleaned up version: https://github.com/zogwarg/advent-of-code/blob/main/2023/jq/12-b.jq

Also lost a fair amount of time not not noticing that the sequence should be joined with "?" not with "". (that'll teach me to always run on the example before the full input, when execution time is super long).

Execution time: 17m10s (without memoization a single row was taking multiple minutes, and there's 1000 rows ^^...)

EDIT: see massive improvement by running in parallel in reply.

I substituted the rows/columns, with multiplication by the expansion rate if they were all numbers. And then for each galaxy pair do a running sum by going “down” the “right” and adding the distance for each row and column crossed.

https://github.com/zogwarg/advent-of-code/blob/main/2023/jq/11-b.jq

transpose is nice to have in that approach.

#!/usr/bin/env jq -n -R -f
[
  # For each line, get numbers eg: [ [1,2,3] ]
  inputs / " " | map(tonumber) | [ . ] |

  # Until latest row is all zeroes
  until (.[-1] | [ .[] == 0] | all;
   . += [
     # Add next row, where for element(i) = prev(i+1) - prev(i)
     [ .[-1][1:] , .[-1][0:-1] ] | transpose | map(.[0] - .[1])
    ]
  )
  # Get extrapolated previous element for first row
  |  [ .[][0] ] | reverse | reduce .[] as $i (0; $i - . )
]

# Output sum of extapolations for all lines
| add

I'm pretty sure you could make this one line and unreadable ^^.

#!/usr/bin/env jq -n -R -f

# Get LR instructions
( input / "" | map(if . == "L" then 0 else 1 end )) as $LR |
( $LR | length ) as $l |

# Make map {"AAA":["BBB","CCC"], ...}
(
  [
    inputs | select(.!= "") | [ scan("[A-Z]{3}") ] | {(.[0]): .[1:]}
  ] | add
) as $map |

# List primes for GCM test / factorization
[
  2, 3, 5, 7, 11, 13, 17, 19,
  23, 29, 31, 37, 41, 43, 47,
  53, 59, 61, 67, 71, 73, 79,
  83, 89, 97
] as $primes |

reduce (
  $map | keys[] | select(test("..A")) | { s: 0, i: 0, c: .} |

  # For each "..A" starting position
  # Produce visited [ "KEY", pos mod $l ], until loop is detected
  until (.i as $i | .[.c] // [] | contains([$i]);
    .s as $s | .i as $i | .c as $c        |
    $map[$c][$LR[$i]] as $next            | # Get next KEY
    .[$c] = (( .[$c] // [ $s ] ) + [$i] ) | # Append ( .s ≡ $l ) to array for KEY (first = .s non mod)
    .s = ( $s + 1 )  | .i = (.s % $l )    | # Update cursors, for next iteration
    .c = $next
  )
  | .[.c][0] as $start_loop_idx | (.s - $start_loop_idx) as $loop_size
  | [ to_entries[] | select(.key[-1:] == "Z") ]
  | if (
      length != 1                                           # Only one ..Z per loop
      or ( .[0].value[0] != $loop_size )                    # First ..Z idx = loop size
      or ( [ .[0].value[0] / $l ] | inside($primes) | not ) # loop_size = ( prime x $l )
      or ( .[0].value[0] / $l  > $l )                       # GCM(loop_sizes) = $l
    ) then "Input does not fit expected pattern" | halt_error else
      # Under these conditions, synched positions of ..Zs happen at:
      # LCM = Π(loop_size_i / GCM) * GCM

      # loop_size_i / GCM
      .[0].value[0] / $l
    end
) as $i (1; . * $i)

# Output LCM = first step where, all ghosts are on "..Z" nodes
| . * $l

#!/usr/bin/env jq -n -R -f

# Get seeds
input | [ match("\\d+"; "g").string | tonumber ] as $seeds |

# Collect maps
reduce inputs as $line ({};
  if $line == "" then
    .
  elif $line | test(":") then
    .k = ( $line / " " | .[0] )
  else
    .[.k] += [[ $line | match("\\d+"; "g").string | tonumber ]]
  end
)

# For each map, apply transformation to all seeds.
# seed -＞ ... -＞ location
| reduce ( to_entries[] | select(.key != "k") .value) as $map ({s:$seeds};
  .s[] |= (
    # Only attempt transform if element is in one of the ranges
    [ . as $e | $map[] | select(. as  [$d,$s,$l] | $e ＞= $s and $e ＜ $s + $l) ] as $range |
    if ($range | length ) ＞ 0 then
      $range[0] as [$d,$s] |
      . - $s + $d
    else
      .
    end
  )
)

# Get lowest location
| .s | min

Some comments:

• A nice use of input first to get the seeds, then inputs to get remaining lines.

#!/usr/bin/env jq -n -R -f

# Utility function
def group_of($n):
  ( length / $n ) as $l |
  . as $arr |
  range($l) | $arr[.*$n:.*$n+$n]
;

# Get all seed ranges
input | [ match("\\d+"; "g").string | tonumber ] | [group_of(2)] as $seeds |

# Collect maps
reduce inputs as $line ({};
  if $line == "" then
    .
  elif $line | test(":") then
    .k = ( $line / " " | .[0] )
  else
    .[.k] += [[ $line | match("\\d+"; "g").string | tonumber ]]
  end
)

# For each map, apply transformation to all seeds ranges.
# Producing new seed ranges if applicable
# seed -＞ ... -＞ location
| reduce (to_entries[] | select(.key != "k") .value) as $map ({s:$seeds};
  .s |= [
    # Only attempt transform if seed range and map range instersect
    .[] | [.[0], add, .[1] ] as [$ea, $eb, $el] | [
      $map[] | select(.[1:] | [.[0], add ] as [$sa,$sb] |
        ( $ea ＞= $sa and $ea ＜ $sb ) or
        ( $eb ＞= $sa and $eb ＜ $sb ) or
        ( $sa ＞= $ea and $sa ＜ $eb )
      )
    ] as $range |
    if $range | length ＞ 0 then
      $range[0] as [$d,$s,$l] |
      # ( only end ) inside map range
      if $ea ＜ $s and $eb ＜ $s + $l then
        [$ea, $s - $ea], [$d, $eb - $s ]
      # ( both start, end ) outside map range
      elif $ea ＜ $s then
        [$ea, $s - $ea], [$d, $l], [ $s + $l, $eb ]
      # ( only start ) inside map range
      elif $eb ＞ $s + $l then
        [$ea + $d - $s, $l - $ea + $s ], [$s + $l, $eb - $s - $l]
      # ( both start, end ) inside map range
      else
        [$ea + $d - $s , $el]
      end
    else
      .
    end
  ]
)

# Get lowest location
| [.s[][0]] | min

Some comments:

• Since iterating across all seeds naively would take forever, iterating over seed ranges instead.
• It's nice that JQ can neatly produce extra elements: [1,2,3] | [ .[] | if . == 2 then . * 10 + 1 , . * 10 + 2 else . end ] -> [1, 21, 22, 3]
• There is probably a more compact way of expressing all the conditions and produced outputs.

#!/usr/bin/env jq -n -R -f
[
  inputs
  # Split winning numbers | card
  | split(" | ")
  # Get numbers, remove game id
  | .[] |= [ match("\\d+"; "g").string | tonumber ] | .[0] |= .[1:]
  # Get score for each line
  | .[1] - (.[1] - .[0]) | length | select(. > 0) | pow(2; . - 1)
]

# Output total score sum
| add

Very suited to JQ, extra trick learned using: [ match("\\d+"; "g").string | tonumber ] as a parse all ints in line.

#!/usr/bin/env jq -n -R -f
[
  inputs
  # Split winning numbers | card
  | split(" | ")
  # Get numbers, remove game id
  | .[] |= [ match("\\d+"; "g").string | tonumber ] | .[0] |= .[1:]
  # Set number of cards to 1, and further cards count
  | .[1] - (.[1] - .[0]) | [ 1, length ]
]

| { cards: ., i: 0, l: length } | until (.i == .l;
  # Get number for current card
  .cards[.i][0] as $num
  # Increase range of futher cards, by current number
  | .cards[.i + range(.cards[.i][1]) + 1 ][0] += $num
  | .i += 1
)

# Output total sum of cards
| [ .cards[][0] ] | add

Not too much of an edit compared to part one, being able to easily do operations on range of indices is convenient.

#!/usr/bin/env jq -n -R -f

# Get and reduce every "pretty" line
reduce inputs as $line (
  0;
  # Add extracted number
  . + ( $line / "" | [ .[] | tonumber? ] | [first * 10 , last] | add )
)

#!/usr/bin/env jq -n -R -f

# Define string to num value map
{
  "one":   1,  "1": 1,
  "two":   2,  "2": 2,
  "three": 3,  "3": 3,
  "four":  4,  "4": 4,
  "five":  5,  "5": 5,
  "six":   6,  "6": 6,
  "seven": 7,  "7": 7,
  "eight": 8,  "8": 8,
  "nine":  9,  "9": 9
} as $to_num |

# Get and reduce every "pretty" line
reduce inputs as $line (
  0;
  . + (
    $line |
    # Try two capture two numbers
    capture("(^.*?(?(one|two|three|four|five|six|seven|eight|nine|[1-9])).*(?(one|two|three|four|five|six|seven|eight|nine|[1-9])).*?$)?") |
    # If no capture, get one number twice
    if .f == "" then $line | capture("^.*?(?(one|two|three|four|five|six|seven|eight|nine|[1-9]))") | .l = .f else . end |
    # Add extracted number
    $to_num[.f] * 10 + $to_num[.l]
  )
)

#!/usr/bin/env jq -n -R -f

# For each game: Is 12 red cubes, 13 green cubes, and 14 blue cubes possible ?
# Line Format =
# Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green
[
  # Splitting input game id and content
  inputs / ": " |
  # Saving id
  (.[0] / " " | .[1] | tonumber ) as $id |
  # Parsing game
  .[1] / "; " | [
    .[] / ", " | [ .[] / " " | {(.[1]): .[0] | tonumber} ] | add |
    # Is given sample possible ?
    .red <= 12 and .green <= 13 and .blue <= 14
  ] |
  # If all samples possible, return id, else 0
  if all then $id else 0 end
] |

# Return sum of all possible game ids
add

#!/usr/bin/env jq -n -R -f

# Line Format =
# Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green
[
  # Splitting input game id and content
  inputs / ": " |
  # Parsing game
  .[1] / "; " |
    [ .[] / ", " | [ .[] / " " | {(.[1]): .[0] | tonumber} ] | add ] |
    # Getting minimum required mumber for each color,
    # and computing the power
    {
      r: ([.[].red]   | max),
      g: ([.[].green] | max),
      b: ([.[].blue]  | max)
    } | .r * .g * .b
] |

# Return sum of all powers
add

#!/usr/bin/env jq -n -R -f

# Getting input with padding, and padded width
[ "." + inputs + "." ] as $inputs | ( $inputs[0] | length ) as $w |

# Working with flattened string, convert all symbols to '#'
[
  ([range($w) | "."]|join("")), # Padding
  $inputs[],
  ([range($w) | "."]|join(""))  # Padding
] | join("") | gsub("[^0-9.]";"#") as $inputs |

reduce (
  # Get all indices for symbols, in box pattern around symbols
  $inputs | indices("#")[] |
  . - $w -1  , . - $w , . - $w + 1 ,
  . - 1      , empty  , . + 1      ,
  . + $w - 1 , . + $w , . + $w + 1
) as $i (
  # Numbers containes bounding indices,
  # of numbers bordering symbols
  {numbers: []};

  # Test if current index isn't included in any found number
  def new_number($i): [ .numbers[] | .[0] <= $i and $i <= .[1] ] | any | not ;
  # Make "number" as bounding indices, by extending left and right
  def make_number($i):
    {a: $i, b: ($i+1 )}
      | until( $inputs[.a:.b] | test("^[^0-9]"); .a -= 1 )
      | until( $inputs[.a:.b] | test("[^0-9]$"); .b += 1 )
      | [ .a +1 , .b -1 ]
  ;

  # Add numbers if bordering symbol and new
  if ($inputs[$i:$i+1] | test("[0-9]")) and new_number($i) then .numbers += [ make_number($i) ] else . end
) |

# Output sum of all found numbers
[ .numbers[] | $inputs[.[0]:.[1]] | tonumber ] | add

#!/usr/bin/env jq -n -R -f

# Getting input with padding, and padded width
[ "." + inputs + "." ] as $inputs | ( $inputs[0] | length ) as $w |

# Working with flattened string, only keep gear '*' symbols
[
  ([range($w) | "."]|join("")), # Padding
  $inputs[],
  ([range($w) | "."]|join(""))  # Padding
] | join("") | gsub("[^0-9*]";".") as $inputs |

# Iterate over index positions of all gears
reduce ($inputs | indices("*")[]) as $i (
  0;
  # Re-use part-1 functions
  def new_number($i):
    [ .numbers[] | .[0] <= $i and $i <= .[1] ] | any | not
  ;
  def make_number($i):
    {a: $i, b: ($i+1 )}
      | until( $inputs[.a:.b] | test("^[^0-9]"); .a -= 1 )
      | until( $inputs[.a:.b] | test("[^0-9]$"); .b += 1 )
      | [ .a +1 , .b -1 ]
  ;
  # Reset and add numbers for each "box" ids
  def add_numbers($box_idx):
    reduce $box_idx[] as $i ({numbers:[]};
      if ($inputs[$i:$i+1] | test("[0-9]")) and new_number($i) then
        .numbers += [ make_number($i) ]
      else
        .
      end
    )
  ;
  add_numbers([
    $i - $w -1 , $i - $w , $i -$w + 1 ,
    $i - 1     , empty   , $i + 1     ,
    $i + $w - 1, $i + $w , $i + $w + 1
  ]).numbers as $numbers |

  if $numbers | length == 2 then
    # Add product if exactly two bordering numbers
    . += ( $numbers | map($inputs[.[0]:.[1]]|tonumber) | .[0] * .[1] )
  else
    .
  end
)