this post was submitted on 01 Dec 2023
18 points (100.0% liked)

NotAwfulTech

386 readers
8 users here now

a community for posting cool tech news you don’t want to sneer at

non-awfulness of tech is not required or else we wouldn’t have any posts

founded 1 year ago
MODERATORS
 

Rules: no spoilers.

The other rules are made up as we go along.

Share code by link to a forge, home page, pastebin (Eric Wastl has one here) or code section in a comment.

you are viewing a single comment's thread
view the rest of the comments
[–] [email protected] 3 points 1 year ago* (last edited 1 year ago) (2 children)

Day 5: If You Give A Seed A Fertilizer

https://adventofcode.com/2023/day/5

Leaderboard completion time: 26m37s, so it's the toughest problem this year so far.

[–] [email protected] 4 points 1 year ago* (last edited 1 year ago) (2 children)

I liked the slight trickiness of part 2, that the naive implementation would never complete in time.

As always doing a JQ implementation:

Part 1

#!/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.

Part 2

#!/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.

Replaced less-than (and greater-than for symmetry) symbols with full-width version, since lemmy apparently doesn't handle them well within a code block: replacing less than with <

[–] [email protected] 3 points 1 year ago

Part 2 is a classic AoC move, where suddenly the problem space becomes much larger.

[–] [email protected] 2 points 1 year ago (1 children)

JQ looks like magic. So short! So clean! What's the catch?

[–] [email protected] 3 points 1 year ago (1 children)

The main catch is it would often be faster to use a "real" programming langage ^^, both in writing the code, and in execution time for some loop heavy examples: equivalent code that completes say in 1 second in python, completing in 1 minute in jq. Also missing a way to call native libraries, to do stuff like say "md5" (relevant) in past years advents-of-code.

That being said i like the general "pipe", map-reduce feel of the language. Like bash one-liners It can make for very terse implementations. I like to add comments, and indentation to make it readable though.

[–] [email protected] 1 points 1 year ago

Thanks for the insight!

[–] [email protected] 1 points 1 year ago* (last edited 1 year ago)

I have to punt on part 2 for now, generally shitty day precludes fun coding.

Update done, nothing special

https://github.com/gustafe/aoc2023/blob/main/d05-If-You-Give-A-Seed-A-Fertilizer.pl