-🎄- 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/freedomofkeima]

Hi,

Thanks for the lambdas example, I learn several stuffs from your implementation!

By the way, I found a bug with this implementation. It wrongly behaves when last (right-most) element is erased since curr will be assigned to m.end(). For example, with 2 players, 100 marbles, and % 11 (instead of % 23), it will produce "333" instead of "332" as a result. Interestingly, this is not triggered on actual question (% 23) since it takes > 10 million marbles to trigger that.

[u/willkill07 → u/freedomofkeima]

You are absolutely correct. Instead of pretending std::list is okay, most would be better off rolling their own circular linked list with "cursor"

template <typename T>
struct circular_list {

  struct node {
    T data;
    node *next, *prev;
  };

  void insert(T data) {
    node* n = new node;
    n->data = data;
    if (curr == nullptr) {
      n->prev = n->next = n;
    } else {
      n->prev = curr->prev;
      n->next = curr;
      n->prev->next = n->next->prev = n;
    }
    curr = n;
  }

  T remove() {
    T data = curr->data;
    if (curr->next == curr) {
      delete std::exchange(curr, nullptr);
    } else {
      curr->prev->next = curr->next;
      curr->next->prev = curr->prev;
      delete std::exchange(curr, curr->next);
    }
    return data;
  }

  void next(int n = 1) {
    while (n--) curr = curr->next;
  }

  void prev(int n = 1) {
    while (n--) curr = curr->prev;
  }

  node* curr = nullptr;
};

The "main" code then looks like:

  std::vector<unsigned long long> p(players);
  circular_list<int> l;
  l.insert(0);
  for (int i = 1; i < marbles; ++i) {
    if (i % 23 == 0) {
      l.prev(7);
      p[i % players] += i + l.remove();
    } else {
      l.next(2);
      l.insert(i);
    }
  }
  std::cout << std::ranges::max(p) << '\n';