Skip to content

Instantly share code, notes, and snippets.

@romkatv
Last active December 31, 2019 16:48
Show Gist options
  • Save romkatv/8ef7ea27ddce1de7b1b6f9b5a41838c4 to your computer and use it in GitHub Desktop.
Save romkatv/8ef7ea27ddce1de7b1b6f9b5a41838c4 to your computer and use it in GitHub Desktop.
Advent of Code 2019
#include <stdint.h>
#include <iostream>
#include <string>
const int64_t m = 119315717514047, n=101741582076661, needle=2020;
// https://en.wikipedia.org/wiki/Exponentiation_by_squaring
const auto combine = [](auto f, int64_t unit, int64_t a, int64_t b) {
for (int64_t r = unit;; b >>= 1, a = f(a, a)) {
if (!b) return r;
if (b & 1) r = f(r, a);
}
};
static int64_t add(int64_t a, int64_t b) { return (m + (a + b) % m) % m; } // + (mod m)
static int64_t mul(int64_t a, int64_t b) { return combine(add, 0, a, b); } // * (mod m)
static int64_t pow(int64_t a, int64_t b) { return combine(mul, 1, a, b); } // ** (mod m)
int main() {
int64_t k = 1, b = 0, x;
for (std::string s; std::getline(std::cin, s);) {
if (s.find("inc") + 1) { k = mul(k, x = std::stoll(s.substr(20))); b = mul(b, x) ; }
if (s.find("cut") + 1) { b = add(b, -std::stoll(s.substr(4))) ; b = b ; }
if (s.find("new") + 1) { k = add(0, -k) ; b = add(-1, -b); }
}
x=mul(b, pow(k-1, m-2)); // compute (λ c => k*c + b)**-n and feed it needle
std::cout << add(mul(add(x, needle), pow(pow(k, m-2), n)), -x) << std::endl;
}
#!/usr/bin/env zsh
integer m=119315717514047 n=101741582076661 needle=2020
function add() { return "(($1 + $2) % m + m) % m" }
functions -M add 2
for f g in mul add pow mul; do
functions[$f]='
integer a=$1 b="$2-1" res=$1
for ((;; b >>= 1, a='$g'(a, a))); do
(( b )) || return res
(( b & 1 == 0 )) || res="'$g'(res, a)"
done'
functions -M $f 2
done
integer k=1 b=0
while read -r s; do
case $s in
*inc*) (( b = mul(b, ${s##* }) , k = mul(k, ${s##* }) ));;
*new*) (( b = add(-1, -b) , k = add(0, -k) ));;
*cut*) (( b = add(b, -1 * ${s##* }), k = k ));;
esac
done
integer x='mul(b, pow(k-1, m-2))'
echo $((add(mul(add(x, needle), pow(pow(k, m-2), n)), -x)))
#include <stdint.h>
#include <array>
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <tuple>
#include <vector>
static std::vector<int64_t> mem;
static int64_t pc, base, mode;
template <class F, int Arity, int Mode>
void run() {
std::array<int64_t, Arity> args;
auto set_arg = [&](int i, int m) {
switch (Mode / m % 10) {
case 1: args[i] = pc + i + 1 ; return;
case 0: args[i] = mem[pc + i + 1]; break;
case 2: args[i] = base + mem[pc + i + 1]; break;
}
if (mem.size() <= args[i]) mem.resize(args[i] << 1);
};
if (Arity > 0) set_arg(0, 1);
if (Arity > 1) set_arg(1, 10);
if (Arity > 2) set_arg(2, 100);
pc += Arity + 1;
std::apply([=](auto... pos) { (+*static_cast<F*>(0))(mem[pos]...); }, args);
}
template <int N = -1, int Mode = -1, class Table, class F, class... Args>
constexpr void op(Table& table, int opcode, F f, void (*)(Args...) = 0) {
if constexpr (N == -1) {
op<0, 0>(table, opcode, f, +f);
} else if constexpr (N == sizeof...(Args)) {
table[100 * Mode + opcode] = &run<F, N, Mode>;
} else {
op<N + 1, Mode * 10 + 0>(table, opcode, f, +f);
op<N + 1, Mode * 10 + 1>(table, opcode, f, +f);
op<N + 1, Mode * 10 + 2>(table, opcode, f, +f);
}
}
constexpr auto table = []() {
std::array<void(*)(), 22209> t = {};
op(t, 1, [](int64_t a, int64_t b, int64_t& r) { r = a + b ; }); // add
op(t, 2, [](int64_t a, int64_t b, int64_t& r) { r = a * b ; }); // mul
op(t, 7, [](int64_t a, int64_t b, int64_t& r) { r = a < b ; }); // lt
op(t, 8, [](int64_t a, int64_t b, int64_t& r) { r = a == b ; }); // eq
op(t, 5, [](int64_t a, int64_t b ) { pc = a ? b : pc ; }); // jnz
op(t, 6, [](int64_t a, int64_t b ) { pc = a ? pc : b ; }); // jz
op(t, 9, [](int64_t a ) { base += a ; }); // rel
op(t, 4, [](int64_t a ) { std::cout << a << '\n'; }); // out
op(t, 3, []( int64_t& r) { std::cin >> r ; }); // in
op(t, 99, []( ) { std::exit(0) ; }); // hlt
return t;
}();
int main(int argc, char** argv) {
for (std::istringstream ss(argv[1]); mem.push_back(0), ss >> mem.back(); ss.get()) {}
while (true) table[mem[pc]]();
}
#include <stdint.h>
#include <array>
#include <vector>
#include <iostream>
#include <sstream>
#include <tuple>
static std::vector<int64_t> mem;
static int64_t pc, base, mode;
template <class... Ts>
static void run(void (*op)(Ts...)) {
std::array<int64_t, sizeof...(Ts)> args;
for (int64_t i = 0; i != args.size(); mode /= 10, ++pc, ++i) {
switch (mode % 10) {
case 1: args[i] = pc ; break;
case 0: args[i] = mem[pc]; break;
case 2: args[i] = base + mem[pc]; break;
}
if (mem.size() <= args[i]) mem.resize(args[i] << 1);
}
std::apply([=](auto... pos) { op(mem[pos]...); }, args);
}
int main(int argc, char** argv) {
for (std::istringstream ss(argv[1]); mem.push_back(0), ss >> mem.back(); ss.get()) {}
while (true) {
mode = mem[pc] / 100;
switch (mem[pc++] % 100) {
case 1: run(+[](int64_t a, int64_t b, int64_t& r) { r = a + b ; }); break; // add
case 2: run(+[](int64_t a, int64_t b, int64_t& r) { r = a * b ; }); break; // mul
case 7: run(+[](int64_t a, int64_t b, int64_t& r) { r = a < b ; }); break; // lt
case 8: run(+[](int64_t a, int64_t b, int64_t& r) { r = a == b ; }); break; // eq
case 5: run(+[](int64_t a, int64_t b ) { pc = a ? b : pc ; }); break; // jnz
case 6: run(+[](int64_t a, int64_t b ) { pc = a ? pc : b ; }); break; // jz
case 9: run(+[](int64_t a ) { base += a ; }); break; // rel
case 4: run(+[](int64_t a ) { std::cout << a << '\n'; }); break; // out
case 3: run(+[]( int64_t& r) { std::cin >> r ; }); break; // in
case 99: return 0; break; // hlt
}
}
}
#!/usr/bin/env zsh -o ksh_arrays
local -a mem
local -i pc base mode REPLY
IFS=, read -rA mem <<<${1:?usage: icc.zsh <intcode>}
function argpos() {
local -i m='mode % 10'
(( mode /= 10 ))
case $m in
1) return 'pc++' ;;
0) return 'mem[pc++]' ;;
2) return 'mem[pc++] + base';;
esac
}
function fetch() { (( mem[argpos()] )) }
function store() { (( mem[argpos()]=$1 )) }
function jumpc() { (( pc += ($1) * ($2 - pc) )) }
functions -M argpos 0
functions -M fetch 0
while true; do
mode='mem[pc] / 100'
case $((mem[pc++] % 100)); in
99) exit 0 ;; # hlt
9) base+='fetch()' ;; # rel
1) store 'fetch() + fetch()' ;; # add
2) store 'fetch() * fetch()' ;; # mul
7) store 'fetch() < fetch()' ;; # lt
8) store 'fetch() == fetch()' ;; # eq
5) jumpc 'fetch() != 0' 'fetch()';; # jnz
6) jumpc 'fetch() == 0' 'fetch()';; # jz
3) read -r; store REPLY ;; # in
4) echo - $((fetch())) ;; # out
esac
done
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment