Advent of Code 2019

Advent of Code 2019.md

A few of my Advent of Code 2019 solutions.

Full repo: https://github.com/romkatv/advent-of-code-2019.

day-22-2.cc

#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;
}

day-22-2.zsh

#!/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)))

icc-fast.cc

#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]]();
}

icc.cc

#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
    }
  }
}

icc.zsh

#!/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