Day 9: Movie Theater

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • VegOwOtenks@lemmy.worldEnglish
    3·
    18 hours ago

    Futhark

    First, formatting the input with an unreadable sed script:

    formatting script 
    1i [
1,$ {
	s/^/[/
	s/$/], /
}
$i ]
$d

    Then, the actual program. main is the default entrypoint, part one is trivially solved in the preparations for part two. In part two, the faster check is to look for any point inside the current rectangle. If this can’t find any, it’ll have to check whether any edge crosses through the rectangle with a simple range check. I’m not happy with the performance, I feel like I left a lot on the table.

    As always, wonky syntax highlighting 
    import "lib/github.com/diku-dk/sorts/radix_sort"

def (&&&) 'a 'b 'c (f: a -> b) (g: a -> c) (x: a): (b, c) = (f x, g x)
def odd (x: i64): bool = x % 2 == 1

def count 'a (f: a -> bool) (xs: []a): i64
  = map (f >-> i64.bool) xs |> reduce_comm (+) 0

def coordinateFromArray (as: [2]i64): (i64, i64)
  = (as[0], as[1])

def maximum = reduce_comm i64.max i64.lowest
def minimum = reduce_comm i64.min i64.highest

def concatMap [n] 'a 'b (f: a -> ?[l].[l]b) (placeholder: b) (xs: [n]a): *[]b
  = let totalLength = reduce (+) 0 <| map (\ x -> length (f x)) xs in
    ( loop (results, offset) = (replicate totalLength placeholder, 0)
      for x in xs
      do
        let bs = f x in
        let scatterIndices = indices bs |> map (+offset) in
        (scatter results scatterIndices bs, offset + length bs)
    ).0

def rectSize (a: (i64, i64)) (b: (i64, i64)) = 
  let dx = i64.max a.0 b.0 - i64.min a.0 b.0 in
  let dy = i64.max a.1 b.1 - i64.min a.1 b.1 in
  (dx + 1) * (dy + 1)

def pair_iota (n: i64): [n](i64, i64)
  = map (\ j -> (n, j)) (iota n)

def pairs 'a (xs: []a): [](a, a)
  = concatMap pair_iota (i64.highest, i64.highest) (indices xs)
    |> map (\ (i, j) -> (xs[i], xs[j]))

def findFirst 'a (f: a -> bool) (xs: []a): a
  = ( loop (i, x) = (0, xs[0])
      while not (f x)
      do (i + 1, xs[i+1])
    ) |> (.1)

def orderedPair (p: (i64, i64)): (i64, i64) = (i64.min p.0 p.1, i64.max p.0 p.1)

def overlapsWith (a: (i64, i64)) (b: (i64, i64)): bool 
  = a.0 < b.1 && b.0 < a.1

def anyInside (points: [](i64, i64)) (rectangle: (((i64, i64), (i64, i64)), i64))
  = let (lowerX, upperX) = orderedPair (rectangle.0.0.0, rectangle.0.1.0) in
    let (lowerY, upperY) = orderedPair (rectangle.0.0.1, rectangle.0.1.1) in
    map (\ (x, y) -> lowerX < x && x < upperX && lowerY < y && y < upperY) points
    |> or

def anyIntersects (edges: []((i64, i64), (i64, i64))) (rectangle: (((i64, i64), (i64, i64)), i64)): bool
  = let rectRangeX = orderedPair (rectangle.0.0.0, rectangle.0.1.0) in
    let rectRangeY = orderedPair (rectangle.0.0.1, rectangle.0.1.1) in
    map (\ e -> 
      let edgeRangeX = orderedPair (e.0.0, e.1.0) in
      let edgeRangeY = orderedPair (e.0.1, e.1.1) in
      (edgeRangeX `overlapsWith` rectRangeX) && (edgeRangeY `overlapsWith` rectRangeY)
    ) edges
    |> or

def part2 (sortedRectangles: [](((i64, i64), (i64, i64)), i64)) (points: [](i64, i64))
  = let edges = zip points (rotate 1 points) in
    let filled = \ r -> not (anyInside points r || anyIntersects edges r) in
    findFirst filled sortedRectangles
    |> (.1)

-- benchmark
-- ==
-- input @fut-input
-- auto output

def main (coordinateArrays: [][2]i64)
  = let coordinates = map coordinateFromArray coordinateArrays in
    let rectangleCorners = pairs coordinates in
    let rectangleSizes = map (id &&& uncurry rectSize) rectangleCorners in
    let sortedRectangles = radix_sort_by_key (.1) i64.num_bits i64.get_bit rectangleSizes |> reverse in
  (sortedRectangles[0].1, part2 sortedRectangles coordinates)