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

NotAwfulTech

386 readers
7 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
[email protected]
18
The official awful.systems Advent of Code 2023 thread (awful.systems)
submitted 1 year ago* (last edited 1 year ago) by [email protected] to c/[email protected]
121 comments fedilink hide all child comments
 

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 (1 children)
  1. I have contracted some kind of sinus infection, so rn I have a -20 IQ debuff.

a,bpart a: nothing to say here.

part b: Before diving into the discussion, I timed how long 1000 cycles takes to compute, and apparently, it would take 1643175 seconds or just over 19 days to compute 1 billion cycles naively. How fun!

So, how do you cut down that number? First, that number includes a sparse map representation, so you can tick that box off.

Second is intuiting that the result of performing a cycle is cyclical after a certain point. You can confirm this after you've debugged whatever implementation you have for performing cycles- run it a few times on the sample input and you'll find that the result has a cycle length of 7 after the second interaction.

Once you've got that figured out, it's a matter of implementing some kind of cycle detection and modular arithmetic to get the right answer without having to run 1000000000 cycles. For the record, mine took about 400 cycles to find the loop.

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

a,bI took a very similar approach to parts a and b, with the difference that i was too lazy to do titling in each direction, and wanted to abuse regex so Instead i always titled up and rotated, which given my method of tilting up and rotating had some satisfying cancelling of transpose operations: https://github.com/zogwarg/advent-of-code/blob/main/2023/jq/14-b.jq

# Relevant portion
# oneCycle expects an array, of array of chars (3x3 eg: [[".","#","."],[".",".","."],["O",".","#"]])
def oneCycle:
  # Tilt UP          = T . MAP(scan) . T
  # Rotate           = T . MAP(reverse)
  # Titl UP . Rotate = T . MAP(scan) . Map(reverse) | T . T = Identity
  def tilt_up_rotate:
      transpose          # Gets subgroups    # Within each group,
                         # starring with "#" # In order 1 "#", x "O", y "." 
    | map( ("#" + add) | [ scan("#[^#]*")    | ["#", scan("O"), scan("\\.")] ] | add[1:])
    | map(reverse)
  ;
  # Tilt   North,            West,           South,            East
  tilt_up_rotate | tilt_up_rotate | tilt_up_rotate | tilt_up_rotate
;

JQ does allow some nice sortcuts sometimes, again transpose is nice to have.

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

neat!I need like 25 more IQ points before I think of using a transpose in any context