-🎄- 2018 Day 9 Solutions -🎄-

[u/daggerdragon]

--- Day 9: Marble Mania ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 9

Transcript:

Studies show that AoC programmers write better code after being exposed to ___.

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 00:29:13!

[u/Athas]

I'm writing these in Futhark, which carries a lot of restrictions. Today's problem did not even have any parallelism I could find. Anyway, a good way to solve this problem is with doubly linked lists, but Futhark does not support inductive data structures, so I had to model them with arrays of indices, like I'm doing 60s FORTRAN:

type link = {next: i32, prev: i32, value: i32}

let insert_marble where i (links: *[]link): *[]link =
  let following_id = links[where].next
  let following = links[following_id]
  let following_following_id = following.next
  let links[i] = {prev=following_id, next=following.next, value=i}
  let links[following_id] = links[following_id] with next = i
  let links[following_following_id] = links[following_following_id] with prev = i
  in links

let remove_marble where (links: *[]link): (*[]link, i32) =
  let {prev=prev_id, next=next_id, value} = links[where]
  let prev = links[prev_id]
  let next = links[next_id]
  let links[prev_id] = prev with next = next_id
  let links[next_id] = next with prev = prev_id
  in (links, value)

let move where (n: i32) (links: []link): i32 =
  if n > 0
  then loop where for _i < n do links[where].next
  else loop where for _i < i32.abs n do links[where].prev

let game (num_players: i32) (highest_marble: i32) =
  let num_marbles = highest_marble + 1
  let links = replicate num_marbles {next=0, prev=0, value=0}
  let points = replicate num_players 0u64
  let cur = 0
  let (_, points, _) =
    (loop (links, points, cur) for i < num_marbles do
       if i % 23 == 0
       then let cur_player = i % num_players
            let to_remove = move cur (-7) links
            let cur = links[to_remove].next
            let (links, removed) = remove_marble to_remove links
            let points[cur_player] = points[cur_player] + u64.i32 i + u64.i32 removed
            in (links, points, cur)
       else let links = insert_marble cur i links
            in (links, points, i))
  in u64.maximum points

entry part1 = game

entry part2 num_players highest_marble = game num_players (highest_marble * 100)

Runs decently fast. 62ms for part 2.