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

NotAwfulTech

357 readers
1 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.

(page 3) 31 comments
sorted by: hot top controversial new old
[–] [email protected] 2 points 10 months ago (1 children)

Day 17: Clumsy Crucible

Intimidating at first, so I went shopping for christmas presents first, which engaged my brain juices.

[Language: jq]https://github.com/zogwarg/advent-of-code/blob/main/2023/jq/17-b.jq

In hindsight this is is searching for the shortest path in a graph, making sure that each square is actually two nodes, for when approached vertically or horizontally. My shcool days are distant now, and i wonder how far from optimal my implementation is ^^.

Part two was only a small edit from part one for me, and the code actually ran faster! from ~45s -> ~20s.

[–] [email protected] 2 points 10 months ago

My part b code ran slower :(

[–] [email protected] 2 points 10 months ago* (last edited 10 months ago) (2 children)

Day 18: Lavaduct Lagoon

[Language: jq]https://github.com/zogwarg/advent-of-code/blob/main/2023/jq/18-b.jq

Satisfyingly short (in lines, not in time writing) some of the longer part is hexadecimal parsing, that doesn't come natively in JQ, I started doing polygon math from part 1, and what took me the longest was properly handling the area contributed by the perimeter. (I toyed with trying very annoying things like computing the outmost vertex at each turn, which is complicated by the fact that you don't initially know which way the digger is turning, and needing previous and next point to disambiguate).

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

reduce (
  # Produce stream of the vertices, for the position of the center
  foreach (
    # From hexadecimal representation
    # Get inputs as stream of directions = ["R", 5]
    inputs | scan("#(.+)\\)") | .[0] / ""
    | map(
        if tonumber? // false then tonumber
        else {"a":10,"b":11,"c":12,"d":13,"e":14,"f":15}[.] end
      )
    | [["R","D","L","U"][.[-1]], .[:-1]]
    | .[1] |= (
      # Convert base-16 array to numeric value.
      .[0] * pow(16;4) +
      .[1] * pow(16;3) +
      .[2] * pow(16;2) +
      .[3] * 16 +
      .[4]
    )
  ) as $dir ([0,0];
    if   $dir[0] == "R" then .[0] += $dir[1]
    elif $dir[0] == "D" then .[1] += $dir[1]
    elif $dir[0] == "L" then .[0] -= $dir[1]
    elif $dir[0] == "U" then .[1] -= $dir[1]
    end
  )
  # Add up total area enclosed by path of center
  # And up the are of the perimeter, perimeter * 1/2 + 1
) as [$x, $y] ( #
  {prev: [0,0], area: 0, perimeter_area: 1  };

  # Adds positve rectangles
  # Removes negative rectangles
  .area += ( $x - .prev[0] ) * $y |

  # Either Δx or Δy is 0, so this is safe
  .perimeter_area += (($x - .prev[0]) + ($y - .prev[1]) | abs) / 2 |

  # Keep current position for next vertex
  .prev = [$x, $y]
)

# Output total area
| ( .area | abs ) + .perimeter_area

Day 19: Aplenty

[Language: jq]https://github.com/zogwarg/advent-of-code/blob/main/2023/jq/19-b.jq

Satisfyingly very well suited to JQ once you are used to the stream, foreach(init; mod; extract) and recurse(exp) [where every output item of exp as a stream is fed back into recurse] operators. It's a different way of coding but has a certain elegance IMO. This was actually quick to implement, along with re-using the treating a range as a primitive approach of the seeds-to-soil day.

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

inputs / "\n\n"

# Parse rules
| .[0] / "\n"
| .[] |= (
  scan("(.+){(.+)}")
  | .[1] |= (. / ",")
  | .[1][] |= capture("^((?<reg>.)(?<op>[^\\d]+)(?<num>\\d+):)?(?<to>[a-zA-Z]+)$")
  | ( .[1][].num | strings ) |= tonumber
  | {key: .[0], value: (.[1]) }
) | from_entries as $rules |

# Split part ranges into new ranges
def split_parts($part; $rule_seq):
  # For each rule in the sequence
  foreach $rule_seq[] as $r (
    # INIT = full range
    {f:$part};

    # OPERATE =
    # Adjust parts being sent forward to next rule
    if $r.reg == null then
      .out = [ .f , $r.to ]
    elif $r.op == "<" and .f[$r.reg][0] < $r.num then
      ([ .f[$r.reg][1], $r.num - 1] | min ) as $split |
      .out = [(.f | .[$r.reg][1] |= $split ), $r.to ] |
      .f[$r.reg][0] |= ($split + 1)
    elif $r.op == ">" and .f[$r.reg][1] > $r.num then
      ([ .f[$r.reg][0], $r.num + 1] | max ) as $split |
      .out = [(.f | .[$r.reg][0] |= $split), $r.to ]  |
      .f[$r.reg][1] |= ($split - 1)
    end;

    # EXTRACT = parts sent to other nodes
    # for recursion call
    .out | select(all(.[0][]; .[0] < .[1]))
  )
;

[ # Start with full range of possible sings in input = "in"
  [ {x:[1,4000],m:[1,4000],a:[1,4000],s:[1,4000]} , "in" ] |

  # Recusively split musical parts, into new ranges objects
  recurse(
    if .[1] == "R" or .[1] == "A" then
      # Stop recursion if "Rejected" or "Accepted"
      empty
    else
      # Recursively split
      split_parts(.[0];$rules[.[1]])
    end
    # Keep only part ranges in "Accepted" state
  ) | select(.[1] == "A") | .[0]

  # Total number if parts in each object is the product of the ranges
  | ( 1 + .x[1] - .x[0] ) *
    ( 1 + .m[1] - .m[0] ) *
    ( 1 + .a[1] - .a[0] ) *
    ( 1 + .s[1] - .s[0] )
  # Sum total number of possibly accepted musical parts
] | add

EDIT: Less-thans and greater-thans replaced by fullwidth version, because lemmy is a hungry little goblin.

load more comments (2 replies)
[–] [email protected] 2 points 11 months ago* (last edited 11 months ago) (2 children)

Day 12: Hot springs

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

  • Leaderboard completion time: 22:57
  • Personal completion time: ahahahahahahaha (at least i had fun)

Where a curse the fact I decided to use JQ and not a "real" programming language.

spoilerHad to resort to memoization, but sadly JQ isn't mega well suited to that. I had to refactor my part 1 function, to make including the "state" at every function call possible. I wish it were as easy as a @cache decorator, but i guess this way i had fun (for an arbitrary definition of "fun")

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.

[–] [email protected] 2 points 11 months ago

spoiler

Oooh I should run my code without memoization. Or just add a cache hit count.

load more comments (1 replies)
load more comments
view more: ‹ prev next ›