Day 8: Playground

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.world
    link
    fedilink
    English
    arrow-up
    4
    ·
    1 month ago

    Futhark

    As always, futhark does not support arbitrary inputs, so I have a sed script to transform the input to something readable.

    input transformer

    it produces a textual representation of [][3]u32, try it on your example or input :]

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

    Calculate all the distances (even the redundant ones, I had no idea on how to filter them out). Sort them, keep only the first 1000 for part 1. Keep all for part two. Initialize all boxes to be in no component. Add them to components as time goes on. When connecting two boxes already in a component. Mark all boxes in the second component as part of the first one. Stop when everything is connected.

    After improving my implementation of concatMap (preallocate the entire array), the overall performance improved greatly. My end stats are

    • Time: 7s -> 0.35s
    • Memory: 2GB -> 66MB
    Program Source

    Basic

    import "lib/github.com/diku-dk/sorts/radix_sort"
    
    type position = (u32, u32, u32)
    def positionFromArray (p: [3]u32): position
      = (p[0], p[1], p[2])
    def pair_iota (n: i64): [n](i64, i64)
      = map (\ j -> (n, j)) (iota n)
    def gaussian_sum (n: i64) = n * (n + 1) / 2
    
    def euclidean_distance (a: position) (b: position): f64
      = f64.sqrt 
        ( (f64.u32 a.0 - f64.u32 b.0) ** 2
        + (f64.u32 a.1 - f64.u32 b.1) ** 2
        + (f64.u32 a.2 - f64.u32 b.2) ** 2
        )
    
    def distance_table [n] (positions: [n]position): [n][n]f64
      = let distance_function = \ i j -> euclidean_distance positions[i] positions[j] in
        tabulate_2d n n distance_function
    
    def existsLength 'a 'b (f: a -> ?[l].[l]b) (x: a): i64
      = length (f x)
    
    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 distance_array [n] (positions: [n]position): []((i64, i64), f64)
      = let table = distance_table positions in
        let triangle_indices = concatMap pair_iota (i64.highest, i64.highest) (iota n |> drop 1) in
        map (\ (i, j) -> ((i, j), table[i, j])) triangle_indices
    
    def sort_distances (distances: []((i64, i64), f64)): []((i64, i64), f64)
      = radix_sort_float_by_key (.1) f64.num_bits f64.get_bit distances
    
    type option 'a
      = #Empty
      | #Present a
    
    def empty 'a : option a = #Empty
    
    def overrideWith (old: u16) (new: u16) (x: option u16): option u16
      = match x
          case #Empty -> #Empty
          case #Present inner -> 
            if inner == old
            then #Present new
            else #Present inner
    
    def orElse 'a (o: option a) (d: a): a
      = match o
          case #Empty -> d
          case #Present x -> x
    
    def is_present 'a (o: option a): bool
      = match o
          case #Empty -> false
          case #Present _ -> true
    
    def connect (circuits: *[](option u16)) (newCircuitId: u16) (connection: (i64, i64)): (u16, *[](option u16))
      = let circuitA = circuits[connection.0] in
        let circuitB = circuits[connection.1] in
        match (circuitA, circuitB)
          case (#Empty, #Empty) -> 
            ( newCircuitId + 1
            , scatter circuits [connection.0, connection.1] (rep (#Present newCircuitId))
            )
          case (#Present a, #Empty) -> 
            ( newCircuitId
            , scatter circuits [connection.1] [#Present a]
            )
          case (#Empty, #Present b) -> 
            ( newCircuitId
            , scatter circuits [connection.0] [#Present b]
            )
          case (#Present a, #Present b) ->
            ( newCircuitId
            , map (b `overrideWith` a) circuits
            )
    
    def countCircuit (counts: *[]u64) (o: option u16): *[]u64 
      = match o
        case #Empty -> counts 
        case #Present i -> scatter counts [i64.u16 i] [counts[i64.u16 i] + 1]
    
    def countCircuits (c: u16) (circuits: [](option u16)): *[i64.u16 c]u64
      = let circuitCounts = replicate (i64.u16 c) 0 in
        loop counts = circuitCounts
        for circuit in circuits
        do countCircuit counts circuit
    
    def exampleConnectionCount = 10i64
    def inputConnectionCount = 1000i64
    
    def part1 (positions: i64) (connectionCount: i64) (distances: []((i64, i64), f64))
      = let connections = take connectionCount distances |> map (.0) in
        let circuitMap: *[positions](option u16) = replicate positions empty in
        ( loop (circuitCount, circuits) = (0, circuitMap)
          for connection in connections
          do
            connect circuits circuitCount connection
        ) |> uncurry countCircuits 
          |> radix_sort u64.num_bits u64.get_bit
          |> reverse
          |> take 3
          |> foldl (*) 1
    
    def part2 (positionCount: i64) (distances: []((i64, i64), f64)) (positions: []position)
      = let circuitMap: *[positionCount](option u16) = replicate positionCount empty in
        ( loop (circuitCount, connectionIndex, circuits) = (0, 0, circuitMap)
          while not
            ( and (map is_present circuits)
            && and (map (== circuits[0]) circuits)
            )
          do
            let connection = distances[connectionIndex].0 in
            let (newCircuitId, circuits') = connect circuits circuitCount connection in
            (newCircuitId, connectionIndex+1, circuits')
        ).1
        |> \ i -> distances[i-1].0
        |> \ (a, b) -> positions[a].0 * positions[b].0
    
    def main [n] (position_array: [n][3]u32)
      = let positions = map positionFromArray position_array in
        let unsorted_distances = distance_array positions in
        let sorted_distances = sort_distances unsorted_distances in
        ( part1 n inputConnectionCount sorted_distances
        , part2 n sorted_distances positions
        )