2020 Programming Advent

[cecograph]

Let me know what you think of day 7.

Bit of a bastard. The first part was easy enough, but the second part required a fair bit of refactoring of my Intcode computer implementation. But with that done, the solution isn't too bad (writing mutable code in Haskell isn't pretty).

unblock1 :: (STRef s (State s), Yield, Yield) -> ST s ()
unblock1 (state,MoreInput,Output n) = pushInput state n
unblock1 _ = pure ()

feedback :: V.Vector Int -> [Int] -> Maybe Int
feedback prog (setting:settings) = runST $ do
  firstState <- newSTRef =<< State 0 [setting,0] <$> V.thaw prog
  restStates <- sequence
                [ newSTRef =<< State 0 [s] <$> V.thaw prog | s <- settings ]
  let states = reverse $ firstState : restStates
  loop Nothing states =<< traverse run1 states
  where loop output _ (Halt:_) = pure output
        loop output states (y:ys) = do
          let output' =
                case y of
                  Output o -> Just o
                  _ -> output
          traverse unblock1 (zip3 states (y:ys) (ys ++ [y]))
          loop output' states =<< traverse run1 states

part2 :: IO Int
part2 = maximum . (\prog -> mapMaybe (feedback prog) (permutations [5..9]))
        <$> readProgram

My guess is that they've toned it down massively this year, probably because of complaints of last year's being too difficult.

How did you tackle day 3?

 

[Kosher Salt]

How did you tackle day 3?

Looped through line 1 segment by segment, and tested each segment of line 2 to see if intersected.

Since lines are either horizontal or vertical, if both the horizontal and vertical bounding boxes of two segments overlap, the lines intersect (this would not be the case in a scenario where the line segments could have any slope).

Once you know that segments [x1, y1]-[x2, y2] and [x3, y3]-[x4, y4] intersect, their intersection can be found by taking the arrays [x1, x2, x3, x4] and [y1, y2, y3, y4], sorting them, and taking the middle 2 elements from each as the new x and y ranges, [x5, y5]-[x6, y6]. If the x values (x5 and x6) are identical and the y values (y5 and y6) are also identical, the intersection is a point; otherwise one pair of coordinates will be identical (because it's still a horizontal or vertical segment) and it's two points with the segment between them. If the two segments were perpendicular, they'll intersect at a point; if they're parallel, the intersection will be a segment, but this distinction really isn't significant when calculating the intersection as I just described.

If the intersection was a segment I just assumed that one of its two endpoints would be the closest point, although in hindsight, if the segment was crossing one of the axes, that would not be correct for the Manhattan distance, since the point on the axis would be closer to the origin than either of the segment's endpoints (or indeed any other point on the segment). Luckily that scenario didn't come up (in fact, I think all of the intersections turned out to be points, not segments).

Anyway, I pushed all of the intersection points into an array (which would've included the two endpoints of any segment intersections if there had been any), along with the distance value (which differed from part 1 to part 2), and sorted by distance to get the nearest segment to the origin.

 

[awoo]

I would participate but I don't find these challenges particularly interesting and I'm quite busy at the moment. And im stupid and might unintentionally dox myself. I used to do CodeForces and Project Euler stuff that I was ok but never very good at. The leaderboards are filled with Chinese and Russian coders who have been training competition programming since middle school while I was playing with TI BASIC on my calculator.

 

[cecograph]

Looped through line 1 segment by segment, and tested each segment of line 2 to see if intersected.

Since lines are either horizontal or vertical, if both the horizontal and vertical bounding boxes of two segments overlap, the lines intersect (this would not be the case in a scenario where the line segments could have any slope).

Once you know that segments [x1, y1]-[x2, y2] and [x3, y3]-[x4, y4] intersect, their intersection can be found by taking the arrays [x1, x2, x3, x4] and [y1, y2, y3, y4], sorting them, and taking the middle 2 elements from each as the new x and y ranges, [x5, y5]-[x6, y6]. If the x values (x5 and x6) are identical and the y values (y5 and y6) are also identical, the intersection is a point; otherwise one pair of coordinates will be identical (because it's still a horizontal or vertical segment) and it's two points with the segment between them. If the two segments were perpendicular, they'll intersect at a point; if they're parallel, the intersection will be a segment, but this distinction really isn't significant when calculating the intersection as I just described.

If the intersection was a segment I just assumed that one of its two endpoints would be the closest point, although in hindsight, if the segment was crossing one of the axes, that would not be correct for the Manhattan distance, since the point on the axis would be closer to the origin than either of the segment's endpoints (or indeed any other point on the segment). Luckily that scenario didn't come up (in fact, I think all of the intersections turned out to be points, not segments).

Anyway, I pushed all of the intersection points into an array (which would've included the two endpoints of any segment intersections if there had been any), along with the distance value (which differed from part 1 to part 2), and sorted by distance to get the nearest segment to the origin.

Ah thanks for the details! Is there much extra work computing the distance value for part 2?

I initially tried a slow and naive approach: translate every line into a list of its points. For part 1, shove the point lists into two sets, intersect them, and then take the closest element. For part 2, build two maps from each point in the path to its distance along that path, intersect them combining with addition, and take the smallest element. I can get that down to just

minimum . M.elems . foldl1 (M.intersectionWith (+)) . fmap (M.fromList . (`zip` [1..]) . drawAll)

the only non standard library function there is my "drawAll", which turns the input into the list of points visited in order. As a bonus, this code works for any number of input paths.

It's not fast. It takes 1s to complete both parts. I also tried a more sensible solution where I compute intersection points from line segments, and that one runs 60 times faster. But it's 30 lines longer, and nowhere near as pretty, so I'm sticking to the slow implementation.

 

[Considered HARMful]

Fuck these cunts for not mentioning in the 13th task that the numbers are guaranteed to be prime.

 

[stares at error messages]

Day 7.
I'm not sure if I'm missing part 2 or not.

Spoiler: Code

#!/usr/bin/guile -s
!#

(use-modules
 (ice-9 regex))

(define (print a)
  (display a)
  (newline))

(define problem-text
  "light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.")

(define bags
;; (print
 (eval-string
  (string-append
   "'("
   (regexp-substitute/global
    #f
    "([a-z]) ([a-z])"
    (regexp-substitute/global
     #f
     "[0-9]"
     (regexp-substitute/global
      #f
      "bags?"
      (regexp-substitute/global
       #f
       "^\|\n"
       (regexp-substitute/global
    #f
    " bags?, "
    (regexp-substitute/global
     #f
     "bags?)"
     (regexp-substitute/global
      #f
      "contain"
      (regexp-substitute/global
       #f
       "\\."
       (regexp-substitute/global
        #f
        "contain no other bags"
        problem-text
        'pre "#f" 'post)
       'pre ")" 'post)
      'pre "(" 'post)
     'pre "))" 'post)
    'pre ") (" 'post)
       'pre "(" 'post)
      'pre "" 'post)
     'pre "" 'post)
    'pre 1 "-" 2 'post)
   ")")))

(define loop-n-search
  (let ((return '())
    (results '()))
    (for-each (lambda (b)
        (set! results (cons (car b) results))
        (for-each (lambda (s)
                (when s
                  ;; (print s)
                  (if (member 'shiny-gold s)
                  (set! return (cons results return))
                  (set! results (cons (car s) results )))))
              (cdr b)))
          bags)
    (car return)))

(define (unique x)
  (let ((seen '()))
    (set! seen (cons (car x) seen))
    (map
     (lambda (k)
       (when (not (member k seen))
     (set! seen (cons k seen))))
     x)
    seen))

(define right-bags (unique loop-n-search))

(print "Day 7")
(print right-bags)
(format #t
    "There are ~a colours of bag that eventually contain at least one gold bag.\n"
    (length right-bags))

 

[Kosher Salt]

Ah thanks for the details! Is there much extra work computing the distance value for part 2?

Not especially; you just have to keep a running total of the distance along each wire as you iterate through its segments. Whenever an intersection is found, the distance is the sum of the distances along each wire so far, including the distance from the end of each wire's previous segment (the first point of the current segment) to the actual point of intersection (whose location you've now calculated).

 

[cecograph]

Fuck these cunts for not mentioning in the 13th task that the numbers are guaranteed to be prime.

My solution just assumes that they're relatively prime. It is indeed pretty bullshit for them not to state this.

For part 2, if you had bus ids 4 and 6, then there's no way to get the second to appear 1 minute after the first.

Day 7.
I'm not sure if I'm missing part 2 or not.

Did you download the program input and submit a solution? You won't get the problem statement of part 2 until you fill in the answer form for part 1.

Not especially; you just have to keep a running total of the distance along each wire as you iterate through its segments. Whenever an intersection is found, the distance is the sum of the distances along each wire so far, including the distance from the end of each wire's previous segment (the first point of the current segment) to the actual point of intersection (whose location you've now calculated).

Yeah, I was finding it a bit ugly to have all the extra bookkeeping, but now I've had a fresh look, I can get a decently clean and fast solution.

Your thoughts on 7?

 

[Kosher Salt]

Your thoughts on 7?

Day 7? The bags were given as "can contain," but I looped through all of the bags and added a "can be contained in" array for each. Then for part 1, I started with shiny gold bag's "can be contained in" array, then iterated through and took each bag and appended its "can be contained in" to the end of the working array, minus any duplicates. Working from the start of the array to the end, adding more to the end, eventually reaches a solution where the last bag either can't be contained in anything else or its "can be contained in" array only contains colors that were already in the array, so no more bags are added and the program terminates. The length of the array is the number of bags that can eventually contain a shiny gold bag.

For part 2 I can't remember if I used recursion or just another array like part 1, but either way it's fairly simple; you have 1 shiny gold bag, you multiply its contents by its count (1) and then you have to iterate through those. So if it contains 2 of another bag, you'd multiply that bag's contents by 2, and add them to your list. Eventually you always get to a bag that doesn't contain anything (if you were visualizing this as a tree, it'd be a leaf node in the graph), so the program eventually terminates.

It wasn't particularly difficult, but it was so ridiculous.

edit: part 2 of today (day 13) was BS. It wasn't a programming problem as much as it required a calculation that I don't know how to do. I wrote code that spat out a big equation and then fucked off to Wolfram-Alpha and solved it that way. Fuck that.

 

[cecograph]

Day 7?

Sorry, I meant of 2019.

It wasn't particularly difficult, but it was so ridiculous.

I didn't mind it. Its dependency graph traversal and search, which is pretty common stuff, just rephrased in a silly scenario. That's par for the course for the advent problems.

edit: part 2 of today (day 13) was BS. It wasn't a programming problem as much as it required a calculation that I don't know how to do. I wrote code that spat out a big equation and then fucked off to Wolfram-Alpha and solved it that way. Fuck that.

Yeah, it's mostly just a matter of whether you recognise the problem or not. If the numbers provided are relatively prime, then it's exactly equivalent to the setup of the

Spoiler

Chinese Remainder Theorem

 

[Considered HARMful]

Your thoughts on 7?

Easy graph problem. For the A part build a transposed unweighted graph, B part - weighted graph. Apply DFS.

[EDIT]
Sorry, I didn't catch you were asking re: 2019AoC. I love the assembly-related tasks in the AoC and sometimes even manage to slip into leaderboards with them.

edit: part 2 of today (day 13) was BS. It wasn't a programming problem as much as it required a calculation that I don't know how to do. I wrote code that spat out a big equation and then fucked off to Wolfram-Alpha and solved it that way. Fuck that.

The most BS part was not stating the prime (or even coprime, as @cecograph said) property of the numbers. Then you effectively have to apply some CRT (Chinese Remainder Theorem), modular inverse and other numbertheoretic fuckery I learned to dislike while at the Uni.

 

[Kosher Salt]

Sorry, I meant of 2019.

Like you said, fairly beastly. Required a bunch of refactoring to the intcode computer (especially for part 2, since that required saving the states of 5 different intcode computers and allowing them to stop to wait for input and restart when needed the next time through the loop).

But really, I just spent much longer than I'll admit to spending trying to debug an infinite loop that I assumed was caused by refactoring the intcode computer, that actually ended up just being that I'd accidentally used the same loop variable in two nested loops.

It's honestly probably reached the point where I should just refactor the intcode computer into a proper class. Right now it's just an execute function that takes an array of integers as its argument (and assumes, or creates, other properties for the machine's state... IP, input/output queues, etc.). Javascript's pretty lenient about types, so creating noninteger indexes in array variables is perfectly okay, if... well, it's not exactly proper, but it works.

 

[stares at error messages]

You won't get the problem statement of part 2 until you fill in the answer form for part 1.

I didn't realize you needed an account to get part 2. Thanks.

 

[Kosher Salt]

Today (day 14) was kind of rude, considering that Javascript's bitwise only works with 32 bit integers. I had to split off the top 4 bits and do all of the bitwise operations in two steps (high and low).

Also, for some reason my solution for 2019 day 11 part 2 is printing this:

 ###  #### #### ###   ##  #### #### ###   
#  # #    #    #  # #  # #    #    #  #   
#  # ###  ###  #  # #    ###  ###  ###    
 ###  #    #    ###  #    #    #    #  #  
 # #  #    #    #    #  # #    #    #  # 
#  # #    #### #     ##  #    #### ###

I'm not sure whether there's something wrong with my solution, or if it's the given intcode that's producing the wrong output. It's pretty easy to figure out what the correct answer should be, but still, that's odd.

 

[Considered HARMful]

Today (day 14) was kind of rude, considering that Javascript's bitwise only works with 32 bit integers. I had to split off the top 4 bits and do all of the bitwise operations in two steps (high and low).

Here's a nickel, get yourself a real programming language.

 

[Kosher Salt]

Day 15 prompted a rather interesting dive into Javascript's objects, arrays (incl. typed arrays), and the performance (not) of the in keyword.

The final result was that my fastest solution took an average of around 0.8 seconds to get the 30 millionth number. Also, don't use in. Just don't.

Also, don't create a Map object, put some fraction of 30 million things in it, trash your reference to it, run garbage collection, and then try to do a heap snapshot to try to figure out why its memory wasn't being released. That heap snapshot brought the browser to its knees. I'm convinced there must be a bug in Chrome's memory management system; trashing the reference and then running garbage collection freed the memory for every other structure that I tried using.

edit: it does release the Map's memory when it's defined inside a function and the function returns without any lingering references to it, though.

 

[cecograph]

I'm not sure whether there's something wrong with my solution, or if it's the given intcode that's producing the wrong output. It's pretty easy to figure out what the correct answer should be, but still, that's odd.

All my bugs were in the painter. I think a bug in the intcode interpreter would have been spotted earlier. I got this output:

.#..#.####..##..####.#..#.###..#....###....
.#..#....#.#..#.#....#.#..#..#.#....#..#...
.#..#...#..#..#.###..##...###..#....#..#...
.#..#..#...####.#....#.#..#..#.#....###....
.#..#.#....#..#.#....#.#..#..#.#....#......
..##..####.#..#.####.#..#.###..####.#......

But day 9 of 2019 made me go back and refactor the interpreter. I'd assumed that it was going to need a mutable array for the memory, but at Day 9, we're told that the memory is of arbitrary size. So I went back and rewrote it using an immutable map, and didn't notice any performance problems. It makes for a much more Haskell friendly solution.

Day 15 of 2020 made me reintroduce those mutable arrays, unboxed for good measure.

Can you post your javascript solution? I'd like to benchmark in nodejs and compare to my Haskell on my laptop.

 

[Kosher Salt]

I'd assumed that it was going to need a mutable array for the memory, but at Day 9, we're told that the memory is of arbitrary size. So I went back and rewrote it using an immutable map, and didn't notice any performance problems. It makes for a much more Haskell friendly solution.

One nice thing about Javascript, or not so nice if you're into strong typing, is that it doesn't really care about stuff like that. If an array needs to get bigger, it just does.

Can you post your javascript solution? I'd like to benchmark in nodejs and compare to my Haskell on my laptop.

Sure. Sent to you in a PM.

 

[cecograph]

One nice thing about Javascript, or not so nice if you're into strong typing, is that it doesn't really care about stuff like that. If an array needs to get bigger, it just does.

Javascript arrays look like a pretty exotic datatype to me, but I don't see why you couldn't have something like it in any other language, even Haskell (though it'd have to have a statically known element type).

Sure. Sent to you in a PM.

Cheers. The Haskell's only 0.1s faster on my machine.

 

[cecograph]

The example in day 17 confused the crap out of me. It would have been nice if they'd mentioned that they were recentering with each cycle.

I didn't get a very fast solution to part 2, and I'd be interested in the performance of your JS solution @Kosher Salt.

I naively used a map from vectors represented as lists of ints, which meant that I could solve both parts together and then just pick the number of dimensions.

EDIT: Got a faster solution now. Does part 2 in around 0.3s, and it can get a result for 5 dimensions in <10s.