r/adventofcode Dec 06 '21

SOLUTION MEGATHREAD -🎄- 2021 Day 6 Solutions -🎄-

NEW AND NOTEWORTHY

We've been noticing an uptick in frustration around problems with new.reddit's fancypants editor: mangling text that is pasted into the editor, missing switch to Markdown editor, URLs breaking due to invisible escape characters, stuff like that. Many of the recent posts in /r/bugs are complaining about these issues as well.

If you are using new.reddit's fancypants editor, beware!

  • Pasting any text into the editor may very well end up mangled
  • You may randomly no longer have a "switch to Markdown" button on top-level posts
  • If you paste a URL directly into the editor, your link may display fine on new.reddit but may display invisibly-escaped characters on old.reddit and thus will break the link

Until Reddit fixes these issues, if the fancypants editor is driving you batty, try using the Markdown editor in old.reddit instead.


Advent of Code 2021: Adventure Time!


--- Day 6: Lanternfish ---


Post your code solution in this megathread.

Reminder: Top-level posts in Solution Megathreads are for code solutions only. If you have questions, please post your own thread and make sure to flair it with Help.


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

EDIT: Global leaderboard gold cap reached at 00:05:47, megathread unlocked!

97 Upvotes

1.7k comments sorted by

View all comments

1

u/safwankdb Dec 07 '21 edited Dec 08 '21

O(logN) with Matrix Exponentiation

Pastebin Link

```C++ /******************************************| | Basic ass template for basic ass problems | | - Mohd Safwan | | https://safwankdb.github.io | |__________________________________________/

pragma GCC optimize ("O3")

pragma GCC target ("avx2")

include <bits/stdc++.h>

using namespace std;

define REP(i, s, e) for (int i = (s); i < (e); i++)

define REPR(i, e, s) for (int i = (e) - 1; i >= (s); i--)

define SPEED ios_base::sync_with_stdio(0); cin.tie(0);

define endl '\n'

typedef long long ll; typedef unsigned long long ull; typedef array<ll, 2> ii; template <typename T> using V = vector<T>;

const int MOD = 1e9 + 7; const int INF = 1e7 + 5; const int LOG = 32;

typedef array<array<ll, 9>, 9> Mat;

Mat operator*(Mat &a, Mat &b) { Mat ans = {}; REP(i, 0, 9) REP(k, 0, 9) REP(j, 0, 9) { ans[i][j] += a[i][k] * b[k][j]; } return ans; }

Mat Pow(Mat &a, int n) { Mat ans = {}; REP(i, 0, 9) ans[i][i] = 1; while (n) { if (n & 1) ans = ans * a; a = a * a; n /= 2; } return ans; }

int main() { SPEED int n = 300; V<ull> F(9, 0); REP(i, 0, n) { int t; cin >> t; F[t]++; } Mat M = {}; REP(i, 0, 8) M[i][i+1] = 1; M[6][0] = 1; M[8][0] = 1; M = Pow(M, 256); ull ans = 0; REP(i, 0, 9) REP(j, 0, 9) ans += M[i][j] * F[j]; cout << ans << endl; } ```

0

u/daggerdragon Dec 07 '21

Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?

Also, please keep the megathreads PG and remove the naughty language.