Quest 1: Scales, Bags and a Bit of a Mess

  • 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
  • VegOwOtenksOP
    link
    fedilink
    English
    arrow-up
    2
    ·
    15 days ago

    Futhark + sed

    Futhark can read only number and array types from stdin, the input data is often a non-starter. Therefore, I often massage it into the right format using sed.

    Sed Script
    s/[: ]/,/g
    s/[rgbs]/0/g
    s/[RGBS]/1/g
    1s/^/[ [/
    2,$s/^/, [/
    s/$/]/
    s/,\([01]\)/,0b\1/g
    
    $a]
    

    This formats everything nicely, e.g. the example for part 1:

    2456:rrrrrr ggGgGG bbbbBB
    7689:rrRrrr ggGggg bbbBBB
    3145:rrRrRr gggGgg bbbbBB
    6710:rrrRRr ggGGGg bbBBbB
    

    is transformed into this:

    [ [2456,0b000000,0b001011,0b000011]
    , [7689,0b001000,0b001000,0b000111]
    , [3145,0b001010,0b000100,0b000011]
    , [6710,0b000110,0b001110,0b001101]
    ]
    
    Futhark Solution
    entry part1 (colors: [][4]i32) =
      let isGreenDominant c = c.g > c.r && c.g > c.b
      in colors
         |> map (\array -> (array[0], {r = array[1], g = array[2], b = array[3]}))
         |> filter ((.1) >-> isGreenDominant)
         |> map (.0)
         |> i32.sum
    
    type Optional 'a = #absent | #present a
    
    def map_optional 'a 'b (f: a -> b) (this: Optional a) : Optional b =
      match this
      case #absent -> #absent
      case #present a -> #present (f a)
    
    def optional_is_present 'a (this: Optional a) : bool =
      match this
      case #absent -> false
      case _ -> true
    
    def unwrap_optional 'a (this: Optional a) : a =
      match this
      case #absent -> assert (("unwrap_optional: #absent", false).1) ([][1])
      case #present a -> a
    
    def bind_optional 'a 'b (f: a -> Optional b) (this: Optional a) : Optional b =
      match this
      case #absent -> #absent
      case #present a -> f a
    
    def maximum_by 'a (gte: a -> a -> bool) (as: []a) : Optional a =
      let choose (this: Optional a) (other: Optional a) =
        match (this, other)
        case (#absent, o) -> o
        case (t, #absent) -> t
        case (#present t, #present o) -> #present (if o `gte` t then o else t)
      in reduce choose #absent (map (\a -> #present a) as)
    
    type ShineColor = {r: i32, g: i32, b: i32, s: i32}
    
    def array2ShineColor (array: [5]i32) : (i32, ShineColor) = (array[0], {r = array[1], g = array[2], b = array[3], s = array[4]})
    
    def on f g a b = f (g a) (g b)
    
    entry part2 (colors: [][5]i32) =
      let gte (this: ShineColor) (other: ShineColor): bool =
        let colorSum c = c.r + c.g + c.b
        in this.s > other.s || (this.s == other.s && colorSum this <= colorSum other)
      in colors
         |> map array2ShineColor
         |> maximum_by (gte `on` (.1))
         |> unwrap_optional
         |> (.0)
    
    type Shininess = #matte | #shiny
    type DominantColor = #red | #green | #blue
    
    def filterMap 'a 'b [n] (f: a -> Optional b) (as: [n]a) : []b =
      as
      |> map f
      |> filter optional_is_present
      |> map unwrap_optional
    
    def categorize_shininess (s: i32) : Optional Shininess =
      if s <= 30 then #present #matte else if s >= 33 then #present #shiny else #absent
    
    def categorize_color (color: ShineColor) : Optional DominantColor =
      if color.r > color.g && color.r > color.b
      then #present #red
      else if color.g > color.r && color.g > color.b
      then #present #green
      else if color.b > color.r && color.b > color.g
      then #present #blue
      else #absent
    
    def categorize ((value, color): (i32, ShineColor)) : Optional (i32, (DominantColor, Shininess)) =
      categorize_shininess color.s
      |> bind_optional (\s -> map_optional (\c -> (c, s)) (categorize_color color))
      |> map_optional (\g -> (value, g))
    
    -- >>> category_index (#red, #shiny)
    -- 3
    
    def category_index ((c, s): (DominantColor, Shininess)) : i64 =
      (+) (match c
           case #red -> 0
           case #green -> 1
           case #blue ->
             2)
          (match s
           case #matte -> 0
           case #shiny -> 3)
    
    def (&&&) f g x = (f x, g x)
    def sum2d (a, b) (c, d) : (i32, i32) = (a + c, b + d)
    
    entry part3 (colors: [][5]i32) =
      colors
      |> map array2ShineColor
      |> filterMap categorize
      |> map ((.1) >-> category_index &&& ((.0) &&& const 1))
      |> unzip
      |> uncurry (hist sum2d (0, 0) 6)
      |> maximum_by ((>=) `on` (.1))
      |> unwrap_optional
      |> (.0)
    

    I had hoped that the input might get big enough for optimization purposes, but the calculations are likely too simple.

  • andioop@programming.dev
    link
    fedilink
    English
    arrow-up
    2
    ·
    15 days ago

    Melody Made of Code

    Scales

    I was expecting more CDEs and do re mis than I got. Thanks for letting me know this exists though!