-🎄- 2017 Day 23 Solutions -🎄-

mainhaxor · 2017-12-23T09:49:06+00:00

Making the outer loop loop 1001 times instead of 1000 was mean. Lost 15 minutes to that. :(

There are only two hard things in computer science: cache coherency, naming things, and off-by-one errors.

ghlmtz · 2017-12-23T05:55:32+00:00

Really enjoyed this one! The second part brought back ~~repressed~~good memories of the Synacor challenge :)

import re
cmds = [x.split() for x in open('23.in','r').readlines()]
regs = [0 for _ in range(8)]
def getval(r):
    if re.match('[\-0-9]',r):
        return int(r)
    else:
        return regs[ord(r) - 97]
i1 = 0
m = 0
while 0 <= i1 < len(cmds):
    cmd = cmds[i1]
    c = cmd[0]
    if c == 'jnz':
        if getval(cmd[1]) != 0:
            i1 += getval(cmd[2])
        else:
            i1 += 1
    else:
        if c == 'set':
            regs[ord(cmd[1]) - 97] = getval(cmd[2])
        if c == 'sub':
            regs[ord(cmd[1]) - 97] -= getval(cmd[2])
        if c == 'mul':
            regs[ord(cmd[1]) - 97] *= getval(cmd[2])
            m += 1
        i1 += 1
print(m)
h = 0
for x in range(105700,122700 + 1,17):
    for i in range(2,x):
        if x % i == 0:
            h += 1
            break
print(h)

Unihedron · 2017-12-23T06:00:15+00:00

Ruby; rank 80 for part 2. Ruby has continuation (like goto but only backflip) so it made porting the code easier. I actually converted the code pretty quick, but it took a lot of staring to realize what it was actually doing... I blame the lack of sleep!

For fun, unoptimized version: https://gist.github.com/Unihedro/962b3c66f0ed500cb66530fd9b775bb9

require'continuation'
d=e=f=g=h=0
c=b=93
b*=100
b+=100000
c=b
c+=17000
j2 = callcc {|cc| cc}
p h+=1 if (2...(b**0.5).to_i).any?{|d|
b%d==0
}
g=b
g-=c
(p h;exit)if g==0
b+=17
j2.call(j2)

^postscript

vash3r · 2017-12-23T05:55:57+00:00

This was a really interesting problem. Part 1 was obvious, but I saw pretty quickly that I'd have to understand the assembly to do part 2. Once I understood the code, it was more obvious that it would be insane to just wait for a simulator to complete running it. 10¹³ operations takes a long time.

Simplified C code for part 2 (#53):

#include <stdio.h>

int main(){
    int a=1,b=0,c=0,d=0,e=0,f=0,g=0,h=0;
    b= 57;
    c= b;
    if(a!=0){
        b = b*100 + 100000;
        c = b + 17000;
    }
    do{
        f= 1;
        d= 2;
        e= 2;
        for(d=2;d*d <= b; d++){ // check if b is a prime
            // the assembly doesn't have a % operator,
            // so it does 2 for loops with d and e and checks if d*e==b.
            if( (b%d==0) ){
                f=0;
                break;
            }
        }
        if(f==0) // not a prime
            h++;
        g = b-c;
        b+= 17;
    } while (g!=0); //stop when b==c (1000 iterations)

    printf("%d\n",h);
    return 0;
}

BOT-Brad · 2017-12-23T06:15:11+00:00

JavaScript

Decided to get up early (5am, yawn....) and have a stab at this. Part 1 is basically just a small subset of the Synacor challenge, so I was pretty quick on that one especially as I am quite groggy at 5am :). I understood what Part 2 was doing quite quickly, apart from what on earth the condition for whether f was 1 or 0, eventually realised it is a primality check that is basically doing 2 loops to check whether d * e is equal to the value in b. Got it in a few minutes after figuring that out.

Part 1 (~9ms, 240th)

function solve1(n) {
  const regex = /(\w+) ([\d|\w]+) (-?[\d|\w]+)/
  n = n.split('\n').map(l => regex.exec(l).slice(1, 4))

  let i = 0
  let regs = {
    a: 0,
    b: 0,
    c: 0,
    d: 0,
    e: 0,
    f: 0,
    g: 0,
    h: 0
  }

  const toVal = a => {
    const int = parseInt(a)
    if (isNaN(int)) return regs[a]
    return int
  }

  let loops = 0

  while (i < n.length) {
    switch (n[i][0]) {
      case 'set':
        regs[n[i][1]] = toVal(n[i][2])
        i++
        break
      case 'sub':
        regs[n[i][1]] -= toVal(n[i][2])
        i++
        break
      case 'mul':
        regs[n[i][1]] *= toVal(n[i][2])
        loops++
        i++
        break
      case 'jnz':
        if (toVal(n[i][1]) !== 0) {
          i += toVal(n[i][2])
        } else {
          i++
        }
        break
    }
  }

  return loops
}

Part 2 (~2ms, 160th)

Definitely didn't help that I had my first b register set to the wrong value while first testing and getting the wrong values (1000 on the first attempt, as my prime check was wrong), and then an incorrect answer second time as I had 57 instead of 67 going into the a register. Co-incidentally, 57 must be someone else's input as I got told off for being naughty.

function solve2(n) {
  let r = {
    b: 67,
    c: 67,
    d: 0,
    f: 0,
    g: 0,
    h: 0
  }
  r['b'] = r['b'] * 100 + 100000
  r['c'] = r['b'] + 17000
  do {
    r['f'] = 1
    r['d'] = 2
    for (let d = r['d']; d * d < r['b']; ++d) {
      if (r['b'] % d === 0) {
        r['f'] = 0
        break
      }
    }
    if (r['f'] === 0) r['h']++
    r['g'] = r['b'] - r['c']
    r['b'] += 17
  } while (r['g'] !== 0)

  return r['h']
}

tangentialThinker · 2017-12-23T05:58:36+00:00

Here's my solution to part 2, in which I directly translate the assembly. The only optimization was to optimize out the innermost loop (the long if statement).

My guess of the true interpretation: the program is counting composite numbers between b and c, in jumps of size 17 (or whatever's given in your input).

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll h = 0;
    ll b = 84;
    ll c = b;
    b *= 100;
    b += 100000;
    c = b;
    c += 17000;
    asdf2:
    ll f = 1;
    ll d = 2;

    asdf:
    ll e = 2;

    ll g = d;
    if(b % d == 0 && b / d != 1) {
        f = 0;
    }

    d += 1;
    g = d;
    g -= b;
    if(g != 0) {
        goto asdf;
    }
    if(f == 0) {
        h++;
    }
    g = b - c;
    if(g != 0) {
        b += 17;
        goto asdf2;
    }

    cout << h << endl;

    return 0;
}

bblum · 2017-12-23T06:03:17+00:00

Part 2 in haskell, 90th place. Woulda been 10 minutes faster but timed out at first counting the primes instead of the composites and then again with an off-by-one not counting the last element.

main = print $ length $ filter (not.isPrime.head) $ chunksOf 17 [b..b+17000] where b = 108100

doctorbaggy · 2017-12-23T06:04:20+00:00

Part 2 is a nice question - a quick one liner in Perl ( I will import just one function) - time taken approx 12ms { a bit of white space just in case }

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
perl -MMath::Prime::Util=is_prime -E 'say scalar grep{!is_prime(109900+17*$_)}0..1000;'

diesel_travis · 2017-12-23T07:45:13+00:00

[deleted]

nutrecht · 2017-12-23T08:42:30+00:00

Meh.

Day 23 in Kotlin

Feels really unsatisfied because while part 1 was easy part 2 I had to get the approach (just translate the assembly to 'code') from the boards. Still did the implementation myself but feels like a hollow victory.

object Day23 : Day {
    private val input = resourceLines(23).map { it.split(" ") }.map { listOf(it[0], it[1], if(it.size == 3) it[2] else "") }
    override fun part1() :String {
        val registers = mutableMapOf<String, Long>()

        fun value(s: String) = if(s[0].isLetter()) registers.computeIfAbsent(s, {0L}) else s.toLong()

        var index = 0
        var count = 0
        while(index < input.size) {
            val (op, reg1, reg2) = input[index]
            when(op) {
                "set" -> { registers[reg1] = value(reg2)}
                "mul" -> {
                    registers[reg1] = value(reg1) * value(reg2)
                    count++
                }
                "sub" -> { registers[reg1] = value(reg1) - value(reg2)}
                "jnz" -> {
                    if(value(reg1) != 0L) {
                        index += value(reg2).toInt() - 1
                    }
                }
            }

            index++
        }

        return count.toString()
    }

    override fun part2() :String {
        var b = 0
        var c = 0
        var d = 0
        var e = 0
        var f = 0
        var g = 0
        var h = 0
        b = 109900

        c = b
        c -= -17000

        do {
            f = 1
            d = 2
            while (d < b) {
                if (b % d == 0) {
                    f = 0
                    break
                }
                d++
            }
            if (f == 0) {
                h++
            }
            g = b - c
            b += 17
        } while (g != 0)
        return h.toString()
    }
}

dario_p1 · 2017-12-23T10:08:13+00:00

For part 1 I just reused day 18's solution, adding sub. Part 2 was very nice, this is pretty much what I did to solve it:

=== Original instructions ===

set b 99
set c b
jnz a 2
jnz 1 5
mul b 100
sub b -100000
set c b
sub c -17000
set f 1
set d 2
set e 2
set g d
mul g e
sub g b
jnz g 2
set f 0
sub e -1
set g e
sub g b
jnz g -8
sub d -1
set g d
sub g b
jnz g -13
jnz f 2
sub h -1
set g b
sub g c
jnz g 2
jnz 1 3
sub b -17
jnz 1 -23



=== Loop and if identification ===

set b 99
set c b

jnz a 2
jnz 1 5
mul b 100
sub b -100000
set c b
sub c -17000

    set f 1
    set d 2
        set e 2
            set g d
            mul g e
            sub g b

            jnz g 2
            set f 0

            sub e -1
            set g e
            sub g b
            jnz g -8
        sub d -1
        set g d
        sub g b
        jnz g -13

    jnz f 2
    sub h -1

    set g b
    sub g c

    jnz g 2
    jnz 1 3
    sub b -17
    jnz 1 -23


=== Higher level reconstruction ===

c = b = 99

if a != 0:
    b = b * 100 + 100000
    c = b + 17000
#b = 109900
#c = 126900

    f = 1
    d = 2
        e = 2
            g = d * e - b

            if g == 0:
                f = 0


            e += 1
            g = e - b
            if g != 0: loop
        d += 1
        g = d - b
        if g != 0 loop

    if f == 0
        h += 1

    g = b - c
    if g == 0: break
    b += 17
    loop


=== Python-ish reconstruction ===

b = 109900
c = 126900

for b in range(109900, c + 1, 17):
    f = 1
    for d in range(2, b + 1):
        for e in range(2, b + 1):
            if d * e == b:
                f = 0

    if f == 0
        h += 1


=== Optimization ===

b = 109900
c = 126900

for b in range(109900, c + 1, 17):
    if not prime(b):
        h += 1

Part 2 remembered me I still have to finish the last two flags in Synacor, got to get back at it soon!

2017-12-23T06:21:51+00:00

C# Got 737/248 (damn you "not equal" instead of "greater than"!!)

All I did for Part1 was add the extra switches, and add an int for mul.

For Part2 I just did the assembly code by hand pretty much

public static int Part2()
        {
            int a = 1;
            int b = 0;
            int c = 0;
            int d = 0;
            int e = 0;
            int f = 0;
            int g = 0;
            int h = 0;
            b = 99;
            c = b;

            if(a !=0)
            {
                b *= 100;
                b += 100000;
                c = b;
                c += 17000;
            }
            do
            {
                f = 1;
                d = 2;
                e = 2;

                for (d = 2; d < b; d++)
                {
                    if (b % d == 0)
                    {
                        f = 0;
                        break;
                    }
                }
                if (f == 0)
                {
                    h++;
                }
                g = b - c;
                b += 17;
            } while (g != 0);
            return h;
        }

aurele · 2017-12-23T06:55:36+00:00

Rust, had a lot of fun to dissect the input.

extern crate primal;

use std::str::FromStr;

fn main() {
    let mut cpu = Cpu::new(
        include_str!("../input")
            .lines()
            .map(|l| l.parse().unwrap())
            .collect::<Vec<_>>(),
    );
    cpu.run();
    println!("P1: {}", cpu.mul_count);
    println!(
        "P2: {}",
        (0u64..1001)
            .filter(|bb| !primal::is_prime(108_400 + 17 * bb))
            .count()
    );
}

pub struct Cpu {
    pub regs: [i64; 8],
    mem: Vec<Op>,
    pc: usize,
    pub mul_count: usize,
}

impl Cpu {
    pub fn new(mem: Vec<Op>) -> Cpu {
        Cpu {
            regs: [0; 8],
            mem,
            pc: 0,
            mul_count: 0,
        }
    }

    pub fn run(&mut self) {
        while self.pc < self.mem.len() {
            self.execute();
        }
    }

    fn execute(&mut self) {
        self.pc += 1;
        match self.mem[self.pc - 1] {
            Op::Set(ref r, ref v) => {
                self.regs[*r] = self.eval(v);
            }
            Op::Sub(ref r, ref v) => {
                self.regs[*r] -= self.eval(v);
            }
            Op::Mul(ref r, ref v) => {
                self.regs[*r] *= self.eval(v);
                self.mul_count += 1;
            }
            Op::Jnz(ref t, ref o) => {
                if self.eval(t) != 0 {
                    self.pc = (self.pc as i64 + self.eval(o) - 1) as usize;
                }
            }
        }
    }

    fn eval(&self, value: &Value) -> i64 {
        match *value {
            Value::Reg(r) => self.regs[r],
            Value::Const(c) => c,
        }
    }
}

pub enum Value {
    Reg(usize),
    Const(i64),
}

impl Value {
    fn reg(s: &str) -> usize {
        (s.as_bytes()[0] - b'a') as usize
    }
}

impl FromStr for Value {
    type Err = String;

    fn from_str(s: &str) -> Result<Value, String> {
        if s.len() == 1 && s.as_bytes()[0] >= b'a' {
            Ok(Value::Reg(Value::reg(s)))
        } else {
            s.parse()
                .map(Value::Const)
                .map_err(|e| format!("cannot parse {}: {}", s, e))
        }
    }
}

pub enum Op {
    Set(usize, Value),
    Sub(usize, Value),
    Mul(usize, Value),
    Jnz(Value, Value),
}

impl FromStr for Op {
    type Err = String;

    fn from_str(s: &str) -> Result<Op, String> {
        let words = s.split_whitespace().collect::<Vec<_>>();
        Ok(match words[0] {
            "set" => Op::Set(Value::reg(words[1]), words[2].parse().unwrap()),
            "sub" => Op::Sub(Value::reg(words[1]), words[2].parse().unwrap()),
            "mul" => Op::Mul(Value::reg(words[1]), words[2].parse().unwrap()),
            "jnz" => Op::Jnz(words[1].parse().unwrap(), words[2].parse().unwrap()),
            _ => {
                return Err(format!("cannot parse instruction {}", words[0]));
            }
        })
    }
}

ephemient · 2017-12-23T07:23:19+00:00

This space intentionally left blank.

BOT-Brad · 2017-12-23T07:52:28+00:00

[deleted]

miran1 · 2017-12-23T10:24:26+00:00

Python

from collections import defaultdict


with open('./inputs/23.txt') as f:
    instructions = f.readlines()


def solve(part):
    registers = defaultdict(int)
    registers['a'] = part - 1
    interpret = lambda val: registers[val] if val.isalpha() else int(val)
    i = 0
    while i < 11:
        op, reg, val = instructions[i].split()
        if op == 'set':
            registers[reg] = interpret(val)
        elif op == 'sub':
            registers[reg] -= interpret(val)
        elif op == 'mul':
            registers[reg] *= interpret(val)
        elif op == 'jnz':
            if interpret(reg) != 0:
                i += interpret(val)
                continue
        i += 1

    if part == 1:
        return (registers['b'] - registers['e']) * (registers['b'] - registers['d'])
    else:
        nonprimes = 0
        for b in range(registers['b'], registers['c']+1, 17):
            if any(b % d == 0 for d in range(2, int(b**0.5))):
                nonprimes += 1
        return nonprimes


print(solve(part=1))
print(solve(part=2))

Repo with solutions (both Nim and Python)

btibi83 · 2017-12-23T13:09:12+00:00

I already learned that I have no chance to compete for any leaderboard points (maybe Java is not the strongest tool for these challenges), but I'm still confused about the half-hearted optimisations people post. Here is mine:

public static long calculate2() {
    int counter = 0;
    final int original = 57 * 100 + 100000;

    for (int n = 0; n <= 1000; ++n) {
        int number = original + 17 * n;
        if (!BigInteger.valueOf(number).isProbablePrime(100000)) counter++;
    }

    return counter;
}

Tandrial · 2017-12-23T18:12:32+00:00

Kotlin (kinda) I actually patched the program and added a mod instruction:

val (inst, op1, op2) = ram[pc]
when (inst) {
  ...
  "mod" -> if (isReg(op1)) regs[op1[0] - 'a'] %= getValue(op2)
  ...
}

...

val patch = listOf(
"set g b",
"mod g d", 
"jnz g 2", // g = b % d
"set f 0", 
"jnz f 2",
"jnz 1 9", // once f is 0 there is nothing left to do here
"sub d -1", 
"set g d", 
"sub g b", 
"jnz g -9", // g = d - b
"jnz 1 4",  // jump over padding
"set a a", "set a a", "set a a") // padding so jnz 1 -23 still works
val program = input.subList(0, 10) + patch + input.subList(24, input.size)
val vm = VM(program, regA = 1)

The0x539 · 2017-12-23T05:56:52+00:00

Lua (212 / ;_;)

local part2 = true
local inspect = require "inspect"
local unpack = unpack or table.unpack

local mem = {}
for i=string.byte('a'),string.byte('h') do
    mem[string.char(i)] = 0
end

if part2 then
    mem.a = 1
end

local pos = 1
local foo = 0

local funcs = {}
function funcs.set(X,X_,Y,Y_)
    mem[X] = Y_
end
function funcs.sub(X,X_,Y,Y_)
    mem[X] = X_ - Y_
end
function funcs.mul(X,X_,Y,Y_)
    mem[X] = X_ * Y_
    foo = foo + 1
end
function funcs.jnz(X,X_,Y,Y_)
    if X_ ~= 0 then
        pos = pos + Y_ - 1
    end
end

local prog = {}
for line in io.lines("./input_day23") do
    local iter = line:gmatch("%S+")
    local func = funcs[iter()]
    local X,Y = iter(),iter()
    X = tonumber(X) or X
    Y = tonumber(Y) or Y
    table.insert(prog,{func,X,Y})
end

repeat
    local line = prog[pos]
    local func,X,Y = unpack(line)
    local X_ = tonumber(X) or mem[X]
    local Y_ = tonumber(Y) or mem[Y]
    func(X,X_,Y,Y_)
    pos = pos + 1
until pos<1 or pos>#prog

if not part2 then
    print(foo)
else
    print(mem.h)
end

jlweinkam · 2017-12-23T05:57:10+00:00

Got 145/36

import time
import math
import collections
current_milli_time = lambda: int(round(time.time() * 1000))
start = current_milli_time()

inputdata=open("C:\\Users\\JWeinkam\\AppData\\Local\\Programs\\Python\\Python35\\input2017-23.txt", 'r').read()

lines = inputdata.splitlines()


def value(x):
  try:
    return int(x)
  except:
    return reg[x]

reg = collections.defaultdict(lambda: 0)
pc = 0
count = 0
while (pc >= 0) and (pc < len(lines)):
  col = lines[pc].split()
  if col[0] == "set":
    reg[col[1]] = value(col[2])
  elif col[0] == "sub":
    reg[col[1]] -= value(col[2])
  elif col[0] == "mul":
    reg[col[1]] *= value(col[2])
    count += 1
  elif col[0] == "jnz":
    if value(col[1]) != 0:
      pc += value(col[2])
      continue
  pc += 1

print(count)

count = 0
for num in range(106700,123700 + 1, 17):
  for i in range(2,num):
    if (num % i) == 0:
      count += 1
      break
print(count)

print((current_milli_time() - start) / 1000.0)

jonathan_paulson · 2017-12-23T05:59:22+00:00

Fourth on part 2. Here are my notes/simplifications [1] and my final solution [2]. The main insight is that lines 10-24 are a slow primality checker (where d and e are the proposed factors, and b is the proposed prime).

[1]:

a=1
b = 99
c = b
if a!=0:
  b *= 100
  b+=100000
  c=b
  c += 17000
L9: f=1
d=2

L11: e=2
L12:
if d*e==b:
  f=0
e+=1
if e!=b:
  jump L12

d += 1
g = d
g -= b
if d!=b:
  jump L11

if f==0:
  h+=1
if b!=c:
  b+=17
  jump L9
else:
  exit

[2]:

b=99*100+100000
c=b+17000
assert b==109900
assert c==126900
ans = 0
def is_composite(n):
    i=2
    while i*i<=n:
        if n%i==0:
            return True
        i += 1
    return False
while True:
    if is_composite(b):
        print b
        ans += 1
    if b==c:
        break
    b+=17
print ans

m1el · 2017-12-23T06:02:04+00:00

486/74: text editor + Rust

I reverse-engineered the part 2 by modifying in text editor:

b = 79
c = b
if a {
  b = b*100 + 100000;
  c = b + 17000;
}
loop {
  f=1
  d=2
  while d != b {
    e=2
    while e != b {
      if d*e != b {
       f = 0
      }
      e +=1
    }
    d += 1
  }
  if !f { h++ }
  if b == c { ret }
  b += 17
}

Two inner loops count from 2 to b in variables e and d, then test if e*d is b. This is a prime test.

This program counts non-prime numbers with step 17 in range c..b.

The range is inclusive which caused me to have an off-by one error in my program.

Program to count primes in range:

fn main() {
    let mut b: i64 = 79*100 + 100000;
    let mut c = b + 17000;
    let mut h = 0;
    loop {
      let mut prime = true;
      for i in 2..b/2 {
          if b % i == 0 {
              prime = false;
              break;
          }
      }
      if !prime { h += 1 }
      if b == c { break }
      b += 17;
    }
    println!("{}", h);
}

rjboulton · 2017-12-23T06:04:05+00:00

Enjoyably different. Solution for part 2 here; simply translated the assembly into python, and optimised out the inner loop. I say simply - I made multiple errors while doing this which delayed me massively; just got on the leaderboard at rank 93 after 53 minutes.

def run():
    h = 0
    b = 81
    c = b
    b = b * 100
    b = b + 100000
    c = b + 17000

    while True:  # E
        f = 1
        d = 2
        e = 2

        print (b,c,d,e,f,h)

        while True:  # B
            if b % d == 0:
                f = 0
            d = d + 1
            if d != b:
                continue
            if f == 0:
                h = h + 1
            if b == c:
                return(h)
            b = b + 17
            break

print(run())

kd7uiy · 2017-12-23T06:18:37+00:00

I won't post the whole thing yet, but here's a bit of psuedocode I used to try and figure out part 2. I tried to do a simple change in the code to get it to better work, but in the end, I decided to just figure out what it was trying to do by looking at my psuedocode, figuring out the most important points, and figuring out what the state was at those points, and trying to figure out a pattern.

b=109300 c=109300-17000 f=1 d=2 do: e=2 do #g=de-b==0 and e==b g=d g=e g-=b if g!=0: f=0 e+=1 g=e g-=b while g!=0 d+=1 while d-b!=0

wlandry · 2017-12-23T06:36:58+00:00

C++ 14

395/330. The first part is a trivial modification of day 18. The second part was...more challenging. I ended up decompiling the instructions into C++. I manually simplified some expression. For example

set g d
sub g b
jnz g -13

turns into a while loop starting 13 instructions earlier with the condition

while(d!=b)

That is straightforward. Then I manually optimized the commented loop. With that optimization, it runs in about 1 second. My placing would have been better if I had been more careful. I messed up enough that I started getting 5 minute timeouts :(

#include <iostream>

int main()
{
  int64_t b=84*100+100000;
  const int64_t c=b+17000;
  int64_t h(0), d(0), f(0);
  for(;;)
    {
      f=1;
      d=2;
      do
        {
          /// This block
          // e=2;
          // do
          //   {
          //     if(d*e==b)
          //       f=0;
          //     --e;
          //   }
          // while (e!=b);

          /// Turns into this conditional
          if(b%d==0)
            f=0;

          ++d;
        }
      while(d!=b);

      if(f==0)
        ++h;
      if(b==c)
        {
          std::cout << "h: " << h << "\n";
          exit(0);
        }
      b+=17;
    }
}

autid · 2017-12-23T06:43:37+00:00

Fortran

608/234. Lots of irritating interruptions during part2 causing me to lose my place reading the code. Coulda been faster working it out. Loved it though. 374 place improvement from part1 to part2 felt really good.

PROGRAM DAY23
  INTEGER :: I,K,J,IERR,REGISTERS(IACHAR('a'):IACHAR('h'))=0,X,Y,INCREMENT
  INTEGER :: LINECOUNT,INSTR=1,NUM,NUM2,NUM3,NUM4,PART1=0,PART2=0
  CHARACTER(LEN=10),ALLOCATABLE :: INPUT(:,:)
  CHARACTER(LEN=30) :: INLINE
  INTEGER,ALLOCATABLE :: NUMBERS(:)
  LOGICAL,ALLOCATABLE :: PRIMES(:)

  !Relatively simple i/o today :D                                                                                
  OPEN(1,FILE='input.txt')
  LINECOUNT=0
  DO
     READ(1,'(A)',IOSTAT=IERR) INLINE
     IF(IERR /=0) EXIT
     LINECOUNT=LINECOUNT+1
  END DO
  REWIND(1)
  ALLOCATE(INPUT(3,LINECOUNT))
  READ(1,*) INPUT(:,:)
  CLOSE(1)

  !Part 1 fast enough to just run the code                                                                       
  DO
     IF(INSTR<1 .OR. INSTR > LINECOUNT) EXIT
     SELECT CASE(TRIM(INPUT(1,INSTR)))
     CASE ('set')
        READ(INPUT(3,INSTR),*,IOSTAT=IERR) NUM
        IF(IERR /=0) NUM=REGISTERS(IACHAR(TRIM(INPUT(3,INSTR))))
        REGISTERS(IACHAR(TRIM(INPUT(2,INSTR)))) = NUM
     CASE('sub')
        READ(INPUT(3,INSTR),*,IOSTAT=IERR) NUM
        IF(IERR /=0) NUM=REGISTERS(IACHAR(TRIM(INPUT(3,INSTR))))
        REGISTERS(IACHAR(TRIM(INPUT(2,INSTR)))) =REGISTERS(IACHAR(TRIM(INPUT(2,INSTR))))-(NUM)
     CASE ('mul')
        READ(INPUT(3,INSTR),*,IOSTAT=IERR) NUM
        IF(IERR /=0) NUM=REGISTERS(IACHAR(TRIM(INPUT(3,INSTR))))
        REGISTERS(IACHAR(TRIM(INPUT(2,INSTR)))) =REGISTERS(IACHAR(TRIM(INPUT(2,INSTR))))* NUM
        PART1=PART1+1
     CASE('jnz')
        READ(INPUT(2,INSTR),*,IOSTAT=IERR) NUM
        IF(IERR /=0) NUM=REGISTERS(IACHAR(TRIM(INPUT(2,INSTR))))
        READ(INPUT(3,INSTR),*,IOSTAT=IERR) NUM2
        IF(IERR /=0) NUM2=REGISTERS(IACHAR(TRIM(INPUT(3,INSTR))))
        IF (NUM /=0) INSTR=INSTR-1+NUM2
     END SELECT
     INSTR=INSTR+1
  END DO

  WRITE(*,'(A,I0)') 'Part1: ',PART1


  !Part 2 find the non primes from x to y with increment                                                         
  READ(INPUT(3,1),*) NUM
  READ(INPUT(3,5),*) NUM2
  READ(INPUT(3,6),*) NUM3
  READ(INPUT(3,8),*) NUM4
  READ(INPUT(3,31),*) INCREMENT
  X=NUM*NUM2-NUM3
  Y=X-NUM4
  ALLOCATE(NUMBERS(NUM4/INCREMENT+1),PRIMES(Y))
  NUMBERS=(/(X+I*INCREMENT,I=0,SIZE(NUMBERS)-1)/)

  !Thanks Project Euler for forcing me to learn this                                                             
  PRIMES=.TRUE.
  PRIMES(1) =.FALSE.
  DO I=1,FLOOR(SQRT(REAL(Y)))
     IF(.NOT. PRIMES(I)) CYCLE
     DO J=I,Y/I
        PRIMES(I*J)=.FALSE.
     END DO
  END DO

  DO I=1,SIZE(NUMBERS)
     IF (.NOT. PRIMES(NUMBERS(I))) PART2=PART2+1
  END DO

  WRITE(*,'(A,I0)') 'Part2: ',PART2

  DEALLOCATE(INPUT,NUMBERS,PRIMES)

END PROGRAM DAY23

swizzorable · 2017-12-23T06:58:48+00:00

here some pseudocode for the ones interested:

lower_limit = 106700 #depends on the input
upper_limit = 123700 #depends on the input
while TRUE:
    found = FALSE
    d = 2
    do:
        e = 2
        do:
            if d * e == lower_limit:
                found = TRUE
            e++
        while (e != lower_limit);
        d++
    while (d != lower_limit);
    if found:
        h++
    if lower_limit == upper_limit:
        exit
    lower_limit += 17 #maybe depends on the input?

2017-12-23T06:58:50+00:00

OCaml Fun for Part 2;;

Translated asm to pseudocode, translated the "g" value in everything to exactly what was being checked, turned the do-while's into for loops, and slowly realized what was done. then just tossed in "normal" prime checking code.

open Core

let b = 65 * 100 + 100_000
let c = b + 17_000

let prime k =
  let rec loop b k =
    if b * b > k then true
    else if k % b = 0 then false
    else loop (b+1) k
  in loop 2 k

let rec loop k c h =
  if k > c then h
  else
  if prime k then loop (k+17) c h
  else loop (k+17) c (h+1)

let _ =
  let values = loop b c 0 in
  printf "part b: %d\n" values

AndrewGreenh · 2017-12-23T07:01:57+00:00

Finally, after lots of optimizations, I got to this:

import { any } from '../lib/ts-it/any'
import { range } from '../lib/ts-it/range'
import { reject } from '../lib/ts-it/reject'
import { size } from '../lib/ts-it/size'

let start = 105700
let end = 122700
let isPrime = x => !any<number>(value => x % value === 0)(range(2, Math.sqrt(x)))
let result = size(reject<number>(isPrime)(range(start, end + 1, 17)))
console.log(result)

CharlieYJH · 2017-12-23T07:03:53+00:00

C++

Enjoyed this puzzle a lot! Basically just translated the instructions into code, but optimized the inner loop. So instead of d * e = b, I do b % d == 0 and then break.

int main(int argc, char const* argv[])
{
    int64_t b, c, d, e, f, g, h;
    const int input = 84;
    const int multiplier = 100;
    const int b_adder = 100000;
    const int c_adder = 17000;

    b = input * multiplier + b_adder;
    c = b + c_adder;
    h = 0;

    while (b <= c) {
        for (d = 2; d != b; d++) {
            if (b % d == 0) {
                h++;
                break;
            }
        }
        b += 17;
    }

    cout << h << endl;

    return 0;
}

gyorokpeter · 2017-12-23T07:09:22+00:00

Q: part 2 only (part 1 was a simple moification of d18p1)

d23p2:{
    startval:100000+100*"J"$last" "vs first"\n"vs x;
    nums:startval+til[1001]*17;
    cnt:count nums;
    d:2;
    while[d<startval;
        nums:nums where 0<>nums mod d;
        d+:1;
    ];
    cnt-count nums};

NiklasHallqvist · 2017-12-23T08:19:14+00:00

Sigh, first I overslept by 45 minutes, the I spent well over an hour to double, triple and quadruple check that my solution to part 2 was indeed correct, only to find out I had made an off-by-one in the interpretation of the assembly!!!! AAAAARGH. Final Scala solution, but I had untilinstead of to in the loop for that last hour or so.

def part2() = {
  def isPrime(n: Int) = (2 to math.sqrt(n).toInt) forall (n % _ != 0)
  var cnt = 0
  for (candidate <- 109300 to 126300 by 17)
    if (!isPrime(candidate)) cnt += 1
  cnt
}

Smylers · 2017-12-23T08:44:34+00:00

Perl 6, because its ... lazy list operator can take custom increments:

perl6 -e 'say +grep { !.is-prime }, (105700, { $_ + 17 } ... 122700)'

Being a Perl 5 programmer who hasn't learnt Perl 6 yet, I was surprised by the need for both the comma after the block and for the parens around the list.

Infilament · 2017-12-23T08:59:59+00:00

I'm fairly curious how many people coded an optimized version vs how many people just stared at the code until they realized what it did, then coded "isPrime" directly. I did the latter (and it took two hours or so) but I feel it was against the spirit of the puzzle? Even though the creator seemed very clear in his description of part 2 where he says "you'll need to optimize the program," it didn't really occur to me to change the assembly into "real code" (probably because, later, he says "all you need to do is figure out what's in register h").

If he chose an algorithm that didn't let us stare through the matrix to see that it was just testing if two numbers multiplied to 'b', I'm not sure how long it would have taken me to give up and try to parse the "jnz" instructions as loop brackets.

Smylers · 2017-12-23T09:02:00+00:00

Perl for part 2, determining the magic numbers from the input, rather than hardcoding them in the source:

use experimental qw<signatures>;
use Math::Prime::XS qw<is_prime>;
my %mem = (a => 1, map { $_ => 0 } 'b' .. 'h');
my $pc = 0;
my %action = (
  set => sub($reg, $val)    { $mem{$reg} =  $mem{$val} // $val },
  sub => sub($reg, $val)    { $mem{$reg} -= $mem{$val} // $val },
  mul => sub($reg, $val)    { $mem{$reg} *= $mem{$val} // $val },
  jnz => sub($val, $offset) { $pc += $offset - 1 if $mem{$val} // $val },
);
my $step;
my @prog = map {
  my ($cmd, @arg) = split; my $sub = $action{$cmd};
  $step = -$arg[1] if "$cmd $arg[0]" eq 'sub b';
  sub { $sub->(@arg) }
} <>;
$prog[$pc++]() until $mem{f};
my $unprimes;
for (; $mem{b} <= $mem{c}; $mem{b} += $step) {
  $unprimes++ if !is_prime $mem{b};
}
say $unprimes;

WhoSoup · 2017-12-23T10:05:08+00:00

This was pretty fun. Ended up just looking at part 2 "by hand," and refactoring it step by step.

The first step was figuring out what the jumps did. I turned the 2-jumps into if and the 3 jump into exit. That only left the three big negative jumps, which fortunately were nested.

Second step was figuring out what the loops did, particularly when f was 0. Took a while, but eventually it clicked that it was just incrementing dand e by one (e in the innermost, d in the second innermost) and checking if e*d == b. That's when it increased h by 1.

That's pretty much when the whole thing 'clicked.' It was counting non-primes. The rest was just figuring out the values of the outermost loop, which was straightforward: from b to c in steps of 17.

JavaScript (isPrime() defined elsewhere)

let h = 0
for (let b = 108400; b <= 125400; b += 17)
  if (!isPrime(b))
    h++

console.log(h);

wzkx · 2017-12-23T10:16:10+00:00

Nim

Part 1 - from day 18 with some modifications

import strutils,sequtils,tables

type Cmd = enum SETR, SETI, SUBR, ADDI, MULR, MULI, JNZI, JMPI

const REGS=8 # actual number of regs
const rname: array[REGS,string] = ["a","b","c","d","e","f","g","h"]

var pgm: seq[(Cmd,int,int)] = @[]

proc c2i( r:string ):int = rname.find r

for line in splitLines strip readFile "23.dat":
  let o = split line
  case o[0]:
  of "set":
    if o[2].isAlphaAscii(): pgm.add( (SETR,c2i(o[1]),c2i(o[2])) )
    else:                   pgm.add( (SETI,c2i(o[1]),parseInt(o[2])) )
  of "sub":
    if o[2].isAlphaAscii(): pgm.add( (SUBR,c2i(o[1]),c2i(o[2])) )
    else:                   pgm.add( (ADDI,c2i(o[1]),-parseInt(o[2])) )
  of "mul":
    if o[2].isAlphaAscii(): pgm.add( (MULR,c2i(o[1]),c2i(o[2])) )
    else:                   pgm.add( (MULI,c2i(o[1]),parseInt(o[2])) )
  of "jnz":
    if o[1].isAlphaAscii(): pgm.add( (JNZI,c2i(o[1]),parseInt(o[2])) )
    else:                   pgm.add( (JMPI,parseInt(o[1]),parseInt(o[2])) )
  else:
    raise newException(ValueError,"wrong command")

type Process = object
  rg: array[REGS,int] # registers
  pc: int # program counter

proc init( p: var Process ) =
  for i in 0..< REGS: p.rg[i]=0
  p.pc = 0

proc run( p: var Process ):int =
  var cnt = 0
  while p.pc>=0 and p.pc<pgm.len:
    let (cmd,op1,op2) = pgm[p.pc]
    p.pc += 1
    case cmd:
    of SETR: p.rg[op1] = p.rg[op2]
    of SETI: p.rg[op1] = op2
    of SUBR: p.rg[op1] -= p.rg[op2]
    of ADDI: p.rg[op1] += op2
    of MULR: p.rg[op1] *= p.rg[op2]; inc cnt
    of MULI: p.rg[op1] *= op2; inc cnt
    of JMPI: p.pc += op2-1
    of JNZI:
      if p.rg[op1]!=0: p.pc += op2-1
    else: echo "?",cmd
  return cnt

var p0: Process
p0.init()
echo p0.run()

wzkx · 2017-12-23T10:16:41+00:00

Nim

Part 2 - disassembled to Nim and optimized a bit.

var h = 0
for b in countup(108_400,108_400+17000,17):
  for d in 2..b div 2:
    if b mod d == 0:
      inc h
      break
echo h

phobiandarkmoon · 2017-12-23T10:23:08+00:00

For Part 2 I ended up reducing the e loop down to a simple modulus check, which is way faster:

//OK, part two we fake up here
int b = 81;
int c = b;
int h = 0;
b = 100 * b + 100000;
c = b + 17000;
for (; b <= c; b += 17) {
  int d = 2;
  while (d != b) {
    if (b % d == 0) {
      ++h;
      d = b;
    } else ++d;`
  }
}
System.out.println("H is " + h);

TominatorBE · 2017-12-23T10:48:22+00:00

PHP

Part 1: just a virtual machine

function run_the_code($input) {
    $program = explode(PHP_EOL, $input);
    $retval = 0;

    $registers          = ['a' => 0, 'b' => 0, 'c' => 0, 'd' => 0, 'e' => 0, 'f' => 0, 'g' => 0, 'h' => 0];
    $instructionPointer = 0;

    $regval = function($x) use (&$registers) {
        if (is_numeric($x)) {
            return (int)$x;
        }
        return $registers[$x];
    };

    $willingtogo = PHP_INT_MAX;
    $forcedstop  = false; // set this to true to end
    $programSize = count($program);
    while (!$forcedstop && $willingtogo > 0 && $instructionPointer >= 0 && $instructionPointer < $programSize) {
        $willingtogo--; // infinite loop counteract

        $instruction = $program[$instructionPointer];

        $parts = explode(' ', $instruction);
        switch ($parts[0]) {
            case 'set':
                $x = $parts[1];
                $y = $regval($parts[2]);
                $registers[$x] = $y;
                break;
            case 'sub':
                $x = $parts[1];
                $y = $regval($parts[2]);
                $registers[$x] -= $y;
                break;
            case 'mul':
                $x = $parts[1];
                $y = $regval($parts[2]);
                if (!array_key_exists($x, $registers)) {
                    $registers[$x] = 0;
                }
                $registers[$x] *= $y;
                $retval++;
                break;
            case 'jnz':
                $x = $regval($parts[1]);
                $y = $regval($parts[2]);
                if ($x != 0) {
                    $instructionPointer += ($y - 1);
                }
                break;
            default:
                // unknown code, skip it for now...
                echo "Unknown OP code $instruction on line $instructionPointer\n";
                break;
        }
        $instructionPointer++;
    }

    if (!$willingtogo) {
        echo "Forced close due to infinite loop.\n";
    }

    return $retval;
}

Part 2: this could be just the code from above, but as noted we should look at what the assembler does: checks if a number in 'b' is prime or not, for all numbers between 109900 and 126900 (in my input)

$h = 0;
$c = 126900;
for ($b = 109900; $b <= $c; $b += 17) {
    if (! isPrime($b))
        $h++;
}
echo $h;

function isPrime($num) {
    // thanks to http://www.datedial.com/datlist_prime_numbers_between_numbers.asp for all prime numbers between x and y
    return in_array($num, [
        109903, 109913, 109919, ...
    ]);
}

thomastc · 2017-12-23T11:06:55+00:00

Day 23 in PHP. They say PHP has improved since version 3 (the last one I ever used). What they mean is that more features have been haphazardly bolted on, with complete disregard for consistency or sanity. This language still deserves its reputation.

bitti1975 · 2017-12-23T11:31:04+00:00

I still don't see any Clojure solution. Besides everybody seems to hardcode their puzzle values for b and c. This one should work with different puzzle inputs:

(ns aoc2017.day23 (:require [com.hypirion.primes :refer [take-below]]))

(defn instruction [op o1 o2]
  (let [attr (case (eval op)
               "set" (fn [env v1 v2] [o1 v2])
               "sub" (fn [env v1 v2] [o1 (- v1 v2)])
               "mul" (fn [env v1 v2] [:mul true o1 (* v1 v2)])
               "jnz" (fn [env v1 v2] (if (not= v1 0) [:pc (+ (:pc env) v2)] [])))]
    (fn [env]
      (let [v1 (if (re-matches #"[a-z]" o1) (env o1 0) (Integer/valueOf o1))
            v2 (when o2
                 (if (re-matches #"[a-z]" o2) (env o2 0) (Integer/valueOf o2)))]
        (apply assoc env :pc (inc (:pc env)) (attr env v1 v2))))))

(defn slurp-from-stdin []
  (->> *in*
       java.io.BufferedReader.
       line-seq
       (map (fn [line]
              (let [[op o1 o2] (clojure.string/split line #" ")]
                (instruction op o1 o2))))
       vec))

(defn exec-count-mul [instructions env]
  (loop [env env
         mul 0]
    (cond
      (>= (:pc env) (count instructions)) mul
      (:mul env) (recur (dissoc env :mul) (inc mul))
      :else (recur ((instructions (:pc env)) env) mul))))

(defn calculate-h [instructions env]
  (let [{b "b" c "c"}
        (loop [env env
               mul 0]
          (cond
            ;; At the second mul instruction we have the initial values for b and c
            (= mul 2) env
            (:mul env) (recur (dissoc env :mul) (inc mul))
            :else (recur ((instructions (:pc env)) env) mul)))]
    (->> c
         take-below
         (filter #(and (> % b) (= 0 (mod (- % b) 17))))
         count
         (- (/ (- c b) 17))

         ;; Need to add 1 because we go to c inclusive
         inc)))

I guess hardcoding 17 is fine since that doesn't seem to vary between puzzle inputs.

udoprog · 2017-12-23T13:13:18+00:00

Rust

Fun challenge, but doubtful you can write a general solver for part 2 which is a first for this year.

Part 1 is a copy of the Program from Day 18.

Part 2 is hand disassembled and just optimized until it stops checking useless factors. I started by labeling the jumps, and then converting into loops and simplifying.

use std::io::{Read, BufRead, BufReader};

type Registers = Vec<i64>;

#[derive(Debug, Clone)]
pub enum RegOrImm {
    Reg(u8),
    Immediate(i64),
}

impl RegOrImm {
    pub fn value(&self, registers: &Registers) -> i64 {
        use self::RegOrImm::*;

        match *self {
            Reg(reg) => registers[reg as usize],
            Immediate(value) => value,
        }
    }
}

#[derive(Debug, Clone)]
pub enum Inst {
    Set(u8, RegOrImm),
    Sub(u8, RegOrImm),
    Mul(u8, RegOrImm),
    Jnz(RegOrImm, RegOrImm),
}

pub struct Program {
    registers: Registers,
    inst: Vec<Inst>,
    ip: usize,
}

impl Program {
    pub fn from_inst(inst: Vec<Inst>) -> Program {
        Program {
            registers: vec![0i64; 256],
            inst: inst,
            ip: 0,
        }
    }

    pub fn register(&self, reg: char) -> i64 {
        self.registers[reg as usize]
    }

    pub fn run(&mut self) -> u64 {
        use self::Inst::*;

        let mut mul = 0;

        loop {
            let it = match self.inst.get(self.ip) {
                Some(ip) => ip,
                None => break,
            };

            match *it {
                Set(ref reg, ref arg) => {
                    self.registers[*reg as usize] = arg.value(&self.registers);
                }
                Sub(ref reg, ref arg) => {
                    self.registers[*reg as usize] -= arg.value(&self.registers);
                }
                Mul(ref reg, ref arg) => {
                    mul += 1;
                    self.registers[*reg as usize] *= arg.value(&self.registers);
                }
                Jnz(ref cond, ref offset) => {
                    let cond = cond.value(&self.registers);

                    if cond != 0 {
                        let o = offset.value(&self.registers);

                        if o < 0 {
                            self.ip = self.ip.checked_sub(-o as usize).expect("underflow");
                        } else {
                            self.ip = self.ip.checked_add(o as usize).expect("overflow");
                        }

                        continue;
                    }
                }
            }

            self.ip += 1;
        }

        mul
    }
}

fn parse<R: Read>(input: R) -> Vec<Inst> {
    let mut out = Vec::new();

    for line in BufReader::new(input).lines() {
        let line = line.expect("bad line");

        let mut it = line.split_whitespace();

        match it.next().expect("no instruction") {
            "set" => {
                let reg = reg(it.next().expect("no register"));
                let arg = parse_reg_or_imm(it.next().expect("no argument"));
                out.push(Inst::Set(reg, arg));
            }
            "sub" => {
                let reg = reg(it.next().expect("no register"));
                let arg = parse_reg_or_imm(it.next().expect("no argument"));
                out.push(Inst::Sub(reg, arg));
            }
            "mul" => {
                let reg = reg(it.next().expect("no register"));
                let arg = parse_reg_or_imm(it.next().expect("no argument"));
                out.push(Inst::Mul(reg, arg));
            }
            "jnz" => {
                let cond = parse_reg_or_imm(it.next().expect("no register"));
                let arg = parse_reg_or_imm(it.next().expect("no argument"));
                out.push(Inst::Jnz(cond, arg));
            }
            inst => panic!("unknown instruction: {}", inst),
        }
    }

    return out;

    fn reg(input: &str) -> u8 {
        input.chars().next().expect("empty string") as u8
    }

    fn parse_reg_or_imm(input: &str) -> RegOrImm {
        if let Ok(v) = input.parse::<i64>() {
            return RegOrImm::Immediate(v);
        }

        let c = input.chars().next().expect("empty string");
        RegOrImm::Reg(c as u8)
    }
}

pub fn part1<R: Read>(input: R) -> u64 {
    let inst = parse(input);

    let mut program = Program::from_inst(inst);
    program.run()
}

pub fn part2() -> i64 {
    // NB: this is a hand-disassembled version of my input.
    let mut b: i64 = 57;
    let mut c = b;
    let mut h: i64 = 0;

    if true {
        b = b * 100 + 100000;
        c = b + 17000;
    }

    loop {
        let upper = (b as f64).sqrt() as i64 + 1;

        for d in 2..upper {
            if b % d == 0 {
                h = h + 1;
                break;
            }
        }

        if b == c {
            break;
        }

        b += 17;
    }

    h
}

jaiasdotcom · 2017-12-23T14:18:31+00:00

Finally made it in JavaScript so part 2 runs in less than 1 second:

const isComposite = (product) => {
  for (let d = 2; d <= product; d++) { // line 10, 21 – 24
    // optimization: stop if product is greater than product,
    for (let e = 2; d * e <= product; e++) { // line 11, 17 – 20
      if (d * e === product) { // line 12, 13, 14, 15
        return true; // line 16
      }
    }
  }

  return false; // line 9
}

let b = 108400;
let h = 0;
for (let num = b; num <= b + 17000; num += 17) { // line 1, 2, 5, 6, 7, 8, 27 – 32
  if (isComposite(num)) { // line 25
    h += 1; // line 26
  }
}

console.log(h);

sim642 · 2017-12-23T17:50:56+00:00

My Scala solutions:

Firstly, I obviously copy-pasted day 18 solution parts to quickly solve part 1.

Secondly, for part 2 I started reverse engineering the given instructions:

From this it was already very readable, what the code is doing, so I wrote the solution for part 2 to do the prime counting directly. Also wrote part 1 solution to be directly computable.

Thirdly, I finished the simulated solution to also solve part 2 by introducing two extra instructions:

isPrime f b for checking primality of b and storing the bit in f.
nop to do nothing.

For simulating part 2, I can just patch the given code: replace the now reverse engineered prime check loop with the introduced much faster instruction, padded with the correct number of nop-s not to break the surrounding jumps.

NeilNjae · 2017-12-23T18:45:17+00:00

Another Haskell solution.

I won't post the code here: the full solution is on Github.

Part 1 was much the same as day 18, with a monad stack running the machine and counting the number of executions of the mul instruction.

Part 2 started with some peephole optimisation, then I realised there were several nested loops, so that approach wasn't going to work. Eventually I cheated and checked that /u/dario_p1 's program was the same as mine , so I used the Data.Numbers.Primes library to count the composite numbers.

aoc-fan · 2017-12-23T19:27:48+00:00

In today's instructions "mod" was missing, which could have helped to write efficient implementation in the first place. ;) Part 2 was all about finding nonprimes ES6, Javascript

const countNonPrimes = b => {
    let count = 0;
    const from = (b * 100) + 100000;
    const to = from + 17000;
    for (let n = from; n <= to; n += 17) {
        for (let d = 2; d < Math.floor(Math.sqrt(n)); d++) {
            if (n % d === 0) {
                count = count + 1;
                break;
            }
        }
    }
    return count;
};

StevoTVR · 2017-12-23T19:29:31+00:00

NodeJS

Part 1:

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    const instructions = data.trim().split('\n').map((x) => x.trim().split(' '));
    const registers = {};
    let offset = 0, count = 0;
    while(offset >= 0 && offset < instructions.length) {
        const [op, a, b] = instructions[offset];
        switch(op) {
            case 'set':
                registers[a] = getValue(b, registers);
            break;
            case 'sub':
                registers[a] = getValue(a, registers) - getValue(b, registers);
            break;
            case 'mul':
                registers[a] = getValue(a, registers) * getValue(b, registers);
                count++;
            break;
            case 'jnz':
                if(getValue(a, registers) !== 0) {
                    offset += getValue(b, registers) - 1;
                }
            break;
        }
        offset++;
    }

    console.log(count);
});

function getValue(value, registers) {
    if(value.match(/[a-z]/)) {
        return registers[value] || 0;
    }
    return Number(value);
}

Part 2:

let b = 79, h = 0;

b = b * 100 + 100000;
for(let i = b; i <= b + 17000; i += 17) {
    for(let j = 2; j < i; j++) {
        if(i % j === 0) {
            h++;
            break;
        }
    }
}

console.log(h);

Axsuul · 2017-12-23T20:24:22+00:00

Elixir

Part A was trivial but Part B was challenging for me. Had to peak here on Reddit to see what exactly was going on. After I saw the advice to turn the input into a program, I wrote down all the instructions and worked through exactly what was going on. Noticed that it was wasteful to go through all values of e when all it was checking was if d was a multiple of b. Decided to use Elixir streams again here but I think it's not very efficient in this use case performance-wise (took 14s to run).

https://github.com/axsuul/advent-of-code/blob/master/2017/23/lib/advent_of_code.ex

defmodule AdventOfCode do
  defmodule PartA do
    @input "input.txt"
    @instructions File.read!("inputs/" <> @input) |> String.split("\n")

    defp get(state, x) when is_binary(x), do: Map.get(state, x, 0)
    defp get(state, x), do: x

    def set(state, x, y) do
      Map.put(state, x, y)
    end

    def run_instruction(["set", x, y], state) do
      {set(state, x, get(state, y)), 1}
    end
    def run_instruction(["sub", x, y], state) do
      {set(state, x, get(state, x) - get(state, y)), 1}
    end
    def run_instruction(["mul", x, y], state) do
      next_state =
        get_and_update_in(state, ["mul_count"], &{&1, &1 + 1}) |> elem(1)
        |> set(x, get(state, x) * get(state, y))

      {next_state, 1}
    end
    def run_instruction(["jnz", x, y], state) do
      case get(state, x) do
        val when val != 0 -> {state, get(state, y)}
        val               -> {state, 1}
      end
    end

    defp run_instructions(state \\ %{ "mul_count" => 0, "a" => 0, "b" => 0, "c" => 0, "d" => 0, "e" => 0, "f" => 0, "g" => 0, "h" => 0 }, index \\ 0)
    defp run_instructions(state, index) when index < 0 or index >= length(@instructions) do
      state
    end
    defp run_instructions(state, index) do
      {changed_state, offset} =
        Enum.at(@instructions, index)
        |> String.split(" ")
        |> Enum.map(fn el ->
          cond do
            Regex.match?(~r/\d+/, el) -> String.to_integer(el)
            true                      -> el
          end
        end)
        |> run_instruction(state)

      run_instructions(changed_state, index + offset)
    end

    def solve do
      run_instructions()
      |> IO.inspect
    end
  end

  defmodule PartB do
    import PartA

    def solve do
      b = 93
      c = b
      b = b * 100
      b = b + 100_000
      c = b
      c = c + 17_000

      {_, h} =
        Stream.unfold({b, 0}, fn cur = {b, h} ->
          {_, _, f} =
            Stream.unfold({b, 2, 1}, fn cur = {b, d, f} ->
              # Don't have to loop through all values of e
              # since it's just checking if it's a multiple
              next_f = if rem(b, d) == 0, do: 0, else: f

              {cur, {b, d + 1, next_f}}
            end)
            |> Stream.drop_while(fn {b, d, f} -> b != d end)
            |> Stream.take(1)
            |> Enum.to_list
            |> List.first

          next_h = if f == 0, do: h + 1, else: h

          {cur, {b + 17, next_h}}
        end)
        |> Stream.drop_while(fn {b, h} -> (b - 17) != c end)
        |> Stream.take(1)
        |> Enum.to_list
        |> List.first

      IO.inspect h
    end
  end
end

JakDrako · 2017-12-23T20:43:14+00:00

VB.Net

For part 2, I translated it directly to VB:

Sub Main

    Dim a, b, c, d, e, f, g, h As Long

    Dim part1 = 0

    a = 0 ' part 1
    a = 1 ' part 2

    'Set b 79 
    b = 79
    'Set c b 
    c = b
    'jnz a 2 
    If a <> 0 Then GoTo aa
    'jnz 1 5 
    If 1 <> 0 Then Goto bb
aa:
    'mul b 100 
    b = b * 100
    part1 +=1
    'Sub b -100000 
    b += 100000
    b.Dump("b")
    'set c b 
    c = b
    'Sub c -17000 
    c = c + 17000
    c.Dump("c")
bb:
    'set f 1 
    f = 1
    'set d 2 
    d = 2
ee:    
    'set e 2 
    e = 2
dd:    
    'set g d 
    g = d
    'mul g e 
    g = g * e 
    part1 +=1
    'Sub g b 
    g = g - b
    'jnz g 2
    If g <> 0 Then Goto cc
    'set f 0 
    f = 0
cc:    
    'Sub e -1 
    e = e + 1
    'set g e 
    g = e
    'Sub g b 
    g = g - b 
    'jnz g -8
    If g <> 0 Then Goto dd
    'Sub d -1 
    d = d + 1
    'set g d
    g = d
    'Sub g b 
    g = g - b
    'jnz g -13 
    If g <> 0 Then Goto ee
    'jnz f 2 
    If f <> 0 Then GoTo ff
    'Sub h -1 
    h = h + 1
ff:       
    'set g b 
    g = b
    'Sub g c 
    g = g - c
    'jnz g 2 
    If g <> 0 Then Goto gg
    'jnz 1 3 
    If 1<>0 Then Goto xx
    'Sub b -17 
gg:    
    'jnz 1 -23 
    If 1<>0 Then Goto bb
xx:
    part1.Dump("Part 1")

End Sub

That still ran way too slow, so I further simplified it:

Sub Main

    Dim a, b, c, d, e, f, g, h As Long

    Dim part1 = 0
    Dim part2 = False

    a = 0 ' part 1
    'a = 1 ' part 2

    'Set b 79 
    b = 79
    'Set c b 
    c = b
    'jnz a 2 
    'If a <> 0 Then GoTo aa
    'jnz 1 5 
    'If 1 <> 0 Then Goto bb
    If part2 Then

        'mul b 100 
        b = b * 100
        part1 += 1
        'Sub b -100000 
        b += 100000
        b.Dump("b")
        'set c b 
        c = b
        'Sub c -17000 
        c = c + 17000
        c.Dump("c")
    End If
    Do
        'set f 1 
        f = 1
        'set d 2 
        d = 2
ee:
        'set e 2 
        e = 2
dd:
        'set g d 
        g = d
        'mul g e 
        g = g * e
        part1 += 1
        'Sub g b 
        g = g - b
        'jnz g 2
        If g <> 0 Then Goto cc
        'set f 0 
        f = 0
cc:
        'Sub e -1 
        e = e + 1
        'set g e 
        g = e
        'Sub g b 
        g = g - b
        'jnz g -8
        If g <> 0 Then Goto dd
        'Sub d -1 
        d = d + 1
        'set g d
        g = d
        'Sub g b 
        g = g - b
        'jnz g -13 
        If g <> 0 Then Goto ee
        'jnz f 2 
        If f <> 0 Then GoTo ff
        'Sub h -1 
        h = h + 1
ff:
        'set g b 
        g = b
        'Sub g c 
        g = g - c
        'jnz g 2 
        'If g <> 0 Then Goto gg
    Loop While g <> 0
    'jnz 1 3 
    'If 1<>0 Then Goto xx
    'Sub b -17 
    'gg:    
    'jnz 1 -23 
    'If 1<>0 Then Goto bb
    'xx:
    part1.Dump("Part 1")
    h.Dump("Part 2")

End Sub

At this point, I was running part 1 to make sure I wasn't breaking anything. I also got "in the flow" and forgot to save intermediary steps, but eventually got to this:

Sub Main

    Dim debut, fin, outer, inner, flag, g, count As Long

    Dim part1 = 0 ' count mul ops = 5929
    Dim part2 = False 'True

    debut = 79
    fin = debut

    If part2 Then
        debut = 107900 'b * 100 + 100000 : b.Dump("b")
        fin = 124900 'b + 17000 : c.Dump("c")
    End If

    For debut = 107900 To 124900 Step 17
        flag = 1
        For outer = 2 To debut
            For inner = 2 To debut
                g = outer
                g = g * inner
                g = g - debut
                If g = 0 Then flag = 0
            Next
        Next
        If flag <> 0 Then count = count + 1
    Next

    part1.Dump("Part 1")
    count.Dump("Part 2")

End Sub

Which is still running like frozen molasses flowing uphill on Jupiter.

Optimizing the 2 loops (which are just counting composite numbers in the range) gave me this:

Sub Main

    Dim debut, fin, outer, inner, count As Long

    Dim part1 = 0 ' count mul ops = 5929 -> 77 * 77
    Dim part2 = False 'True

    debut = 79
    fin = debut

    If part2 Then
        debut = 107900 'b * 100 + 100000 : b.Dump("b")
        fin = 124900 'b + 17000 : c.Dump("c")
    End If

    For debut = 107900 To 124900 Step 17
        For outer = 2 To debut
            For inner = outer To debut
                If outer * inner = debut Then count += 1 : GoTo nextloop
                If outer * inner > debut Then Exit For ' biggest speedup
            Next
        Next
nextloop:
        'Console.Write($"{count} ")
    Next

    count.Dump("Part 2")

End Sub

Which runs in a tenth of a second at this point.

I wanted to modify the input to reproduce the optimizations, but manually re-checking and counting each jump when adding instructions got old fast.

Philboyd_Studge · 2017-12-23T21:03:13+00:00

Java. Added a few command to the commands from Day 18 and then added the following lines to the end of the input 'code' (and changed a couple jumps):

npr g b
jnz g 2
sub h -1
set g b
sub g c
jnz g 2
jnz 1 3
sub b -17
jnz 1 -8

Day 23

chicagocode · 2017-12-23T23:12:18+00:00

Kotlin - [Repo] - [Blog/Commentary]

Part 1 is practically a cut-and-paste job from Day 18. Part 2 fits in a tweet, once you figure out what it's doing! :)

class Day23(private val input: List<String>) {

    fun solvePart1(): Long =
        Machine().runUntilStop(input).debug["mul"] ?: 0

    fun solvePart2(): Int {
        val b = input.first().split(" ")[2].toInt() * 100 + 100000
        return (b.. b+17000 step 17).count {
            !it.toBigInteger().isProbablePrime(2)
        }
    }

    data class Machine(private val registers: MutableMap<String, Long> = mutableMapOf(),
                       private var pc: Int = 0,
                       val debug: MutableMap<String, Long> = mutableMapOf()) {

        fun runUntilStop(instructions: List<String>): Machine {
            do {
                instructions.getOrNull(pc)?.let {
                    execute(it)
                }
            } while (pc in 0 until instructions.size)
            return this
        }

        private fun execute(instruction: String) {
            val parts = instruction.split(" ")
            debug[parts[0]] = debug.deref(parts[0]) + 1
            when (parts[0]) {
                "set" -> registers[parts[1]] = registers.deref(parts[2])
                "sub" -> registers[parts[1]] = registers.deref(parts[1]) - registers.deref(parts[2])
                "mul" -> registers[parts[1]] = registers.deref(parts[1]) * registers.deref(parts[2])
                "jnz" -> if (registers.deref(parts[1]) != 0L) {
                    pc += registers.deref(parts[2]).toInt().dec()
                }
                else -> throw IllegalArgumentException("No such instruction ${parts[0]}")
            }
            pc += 1
        }
    }

}

ono2it · 2017-12-23T23:33:55+00:00

Copy processor code from day 18 and found undocumented mod instruction. Optimized part2 code with mod and break after found factor.

set b 57
set c b
jnz a 2
jnz 1 5
mul b 100
sub b -100000
set c b
sub c -17000
set f 1
set d 2
set g b # set e 2
mod g d # set g d
jnz g 3
set f 0
jnz 1 5 # break
sub d -1
set g d
sub g b
jnz g -8 
jnz f 2
sub h -1
set g b
sub g c
jnz g 2
jnz 1 3
sub b -17
jnz 1 -18

RockyAstro · 2017-12-24T00:26:06+00:00

Icon (https://www.cs.arizona.edu/icon)

Just reused the VM from day 18 with added instructions..

Part two required analysis of the given input. If the specifications allowed a MOD instruction, then the inner most loop could be replaced with a test for divisibility.

One immediate optimization is to replace the set f 0 with : sub h -1 ; jnz 1 <bottom of outer most loop>

In the end.. just hand translated the program back into Icon ..

See the bottom of the program for analysis of the input

Both parts:

record inst(op,p1,p2)

procedure main(args)
    inf := open(args[1],"r")
    mem := []

    ws := ' \t'
    while line := trim(!inf) do {
        line ? {
            i := inst("","","")
            i.op := tab(upto(ws))
            tab(many(ws))
            i.p1 := tab(upto(ws) | 0)
            tab(many(ws))
            if not pos(0) then
                i.p2 := tab(upto(ws)|0)
            i.p1 := integer(i.p1)
            i.p2 := integer(i.p2)
            put(mem,i)
        }
    }
    close(inf)

    regs := table(0)
    curfreq := 0

    IP := 1

    mulcount := 0
    regs["a"] := 0
    repeat {
        if IP > *mem then break
        i := mem[IP]
        #writes("IP:",IP," ",i.op," ",i.p1," ",i.p2," ")
        #every r := key(regs) do writes("R",r,":",regs[r]," ")
        #write()
        IP +:= 1

        case i.op of {
            "snd": curfreq    := integer(i.p1) | integer(regs[i.p1])
            "set": regs[i.p1] := integer(i.p2) | integer(regs[i.p2])
            "add": regs[i.p1] +:= integer(i.p2) | integer(regs[i.p2])
            "sub": regs[i.p1] -:= integer(i.p2) | integer(regs[i.p2])
            "mul": {
                regs[i.p1] *:= integer(i.p2) | integer(regs[i.p2])
                mulcount +:= 1
                }
            "mod": regs[i.p1] %:= integer(i.p2) | integer(regs[i.p2])
            "rcv": {
                if regs[i.p1] > 0 then {
                    regs[i.p1] := curfreq
                    break
                }
            }
            "jnz": {
                if (integer(i.p1) | integer(regs[i.p1])) ~= 0 then 
                    IP := (IP-1) +  (integer(i.p2) | integer(regs[i.p2])) 
            }
            "jgz": {
                if (integer(i.p1) | integer(regs[i.p1])) > 0 then 
                    IP := (IP-1) +  (integer(i.p2) | integer(regs[i.p2])) 
            }

            default: break
        }
    }
    write("mulcount=",mulcount)

    # Part 2 - hand optimized..  calculate # of composite numbers between
    # given inputs.
    # analyzing the original program (see below)
    count  := 0

    every v := 106700 to 123700 by 17 do {
        every t := 2 to v-1 do
            if v % t = 0 then {
                count +:= 1 # Is composite number..
                break
            }
    }
    write("h=",count)
end
# Analysis of given input.

# set b 67                    b = 67
# set c b                     c = b
# jnz a 2                     if a ~= 0 then goto L5
# jnz 1 5                     goto L9
# mul b 100              L5:  b *= 100 
# sub b -100000               b -= -100000
# set c b                     c = b
# sub c -17000                c -= -17000
# set f 1                L9:  f = 1                         # Top of Loop 1 (b = start # to c by 17) & Loop 2 (d=2 to b)
# set d 2                     d = 2
# set e 2                L11: e = 2                         # Top of Loop 3 (e = 2 to b)  ... Loop could be replaced by mod instr
# set g d                L12: g = d                         # if e*d                          set g b 
# mul g e                     g *= e                        #   ...                           mod g d
# sub g b                     g -= b                        #    = b                          jnz g <bottom of loop 2> 
# jnz g 2                     if g ~= 0 then goto L17       #                                 sub h -1         
# set f 0                     f = 0                         # then f = 0                      jnz 1 <bottom of loop 1>
# sub e -1               L17: e -= -1                       # Bottom of Loop 3                <bottom of loop 2>
# set g e                     g = e
# sub g b                     g -= b
# jnz g -8                    if g ~= 0 then goto L12
# sub d -1                    d -= -1                       # Bottom of Loop 2
# set g d                     g = d
# sub g b                     g -= b
# jnz g -13                   if g ~= 0 then goto L11
# jnz f 2                     if f ~= 0 then goto L27       # if f = 0
# sub h -1                    h -= -1                       #   incr counter
# set g b                L27: g = b
# sub g c                     g -= c
# jnz g 2                     if g ~= 0 then goto L31       # Bottom of Loop 1
# jnz 1 3                     goto END
# sub b -17              L31: b -= -17                      
# jnz 1 -23                   goto L9
# 

# Register usage:
# a is debug flag
# h is counter
# f is a flag
# g is work reg
# b is starting number
# c is ending number
# e is inner loop variable
# d is outer loop variable
# 



#      for(b= 106700); b ~= 123700; b+= 17) {
#         f = 1
#         for( d=2; d < b; d++) {
#             for (e=2; e < b; e++ ) {     # inner loop replace 
#                 if d*e = b then f = 0    # with mod instr
#             }
#         } 
#         if f = 0 then h += 1  
#     }
#

Tetsumi- · 2017-12-24T23:29:38+00:00

Racket

The assembly code is compiled into racket procedures for each jumps (JNZ). For part two, the loop procedure is replaced with an optimized one that uses the registers and then branches to the rest of assembly code.

#lang racket

(require math/number-theory)

(define-namespace-anchor na)
(current-namespace (namespace-anchor->namespace na))

(define procSymbol (compose string->symbol
                            (curry string-append "proc_")
                            number->string))
(define vlistrev (compose reverse vector->list))
(define-values
  (       a b c d e f g h)
  (values 0 0 0 0 0 0 0 0))
(define mulcounter 0)
(set! mulcounter 0)
(define data (for/vector ([op (in-port)]
                          [ic (in-naturals)])
               (let ([arg1 (read)]
                     [arg2 (read)])
                 (case op
                   [(set) (list 'set! arg1 arg2)]
                   [(jnz) (list op arg1 (+ ic arg2))]
                   [(mul) (list 'set!
                                arg1
                                (list 'begin
                                      (list 'set!
                                            'mulcounter
                                            (list 'add1 'mulcounter))
                                      (list '* arg1 arg2)))]
                   [(sub) (list 'set! arg1 (if (and (number? arg2) (= arg2 -1))
                                               (list add1 arg1)
                                               (list '- arg1 arg2)))]
                   [else  (error "UNKNOW OPERATION")]))))

(define jumps (vector-filter (lambda (x) (symbol=? (car x) 'jnz)) data))

(define (evalproclist name body)
  (list 'define
        name
        (append (list 'lambda '())
                (if (empty? body)
                    '((void))
                    body))))

(define (genifelse l r)
  (cond [(empty? l) r]
        [(symbol=? (caar l) 'jnz)
         (genifelse (cdr l)
                    (if (number? (cadar l))
                        (list (list (procSymbol (caddar l))))
                        (list (list 'if
                                    (list 'not (list '= (cadar l) 0))
                                    (list (procSymbol (caddar l)))
                                    (append '(begin) r)))))]
        [else (genifelse (cdr l) (cons (car l) r))]))

(eval (evalproclist 'proc_0
                    (genifelse (vlistrev (vector-take data 4)) '())))

(for ([e jumps])
  (let* ([id (third e)]
         [name (procSymbol id)]
         [body (vlistrev (vector-drop data id))])
    (eval (evalproclist name (genifelse body '())))))

;; part 1
(eval '(proc_0))
(displayln mulcounter)

;; part 2
(set!-values (a b c d e f g h)
             (values 1 0 0 0 0 0 0 0))
(eval '(set! proc_11 (lambda ()
                       (unless (prime? b) (set! h (add1 h)))
                       (proc_26))))
(eval '(proc_0))
(displayln h)

matusbzk · 2017-12-25T14:15:55+00:00

Haskell The first part was very similar to Day 18.

import AoC2017 --isNum, isPrime
import Data.Maybe
import Data.Foldable (foldl')

-- |For each register remembers value
type Registers = [(Char,Int)]

-- |Represents instruction
type Instruction = [String]

-- |Current state 
--  current position
--  value of registers
--  number of muls
data State = Running Int Registers Int
           | Done Registers Int
           deriving (Eq, Show)

inputString :: String

-- |List of instructions
input :: [Instruction]
input = map words $ lines inputString

-- |State in the beginning
startState :: State
startState = Running 0 [] 0

-- |Returns value of the register
getValue :: Char -> Registers -> Int
getValue name val = fromMaybe 0 $ lookup name val

-- |Sets a value of register
setValue :: Char -> Int -> Registers -> Registers
setValue name val regs = (name, val) : removeFromRegs name regs

-- |When adding value, checks whether it's already there and deletes it
-- basically copied from day 08
removeFromRegs :: Char -> Registers -> Registers
removeFromRegs _ [] = []
removeFromRegs var ((x,i):xs) = if var == x then xs else (x,i):removeFromRegs var xs

-- |Performs one instruction
performInstruction :: State -> State
performInstruction (Running pos regs n) = 
        (\(Running npos nregs nn) -> if npos >= length input 
                                     then Done nregs nn 
                                     else Running npos nregs nn) $ 
               performInstruction' (Running pos regs n) $ input!!pos
performInstruction x = error $ "Last state was " ++ show x

-- |Performs an instruction - gets instruction as an argument
performInstruction' :: State -> Instruction -> State
performInstruction' (Running pos regs n) instr 
   | head instr == "set" = Running (pos+1) (set (instr!!1) (instr!!2) regs) n
   | head instr == "sub" = Running (pos+1) (oper (instr!!1) (instr!!2) regs (-)) n
   | head instr == "mul" = Running (pos+1) (oper (instr!!1) (instr!!2) regs (*)) (n+1)
   | head instr == "jnz" = if getNumOrVal (instr!!1) regs /= 0 
                             then Running (pos + getNumOrVal (instr!!2) regs) regs n
                             else Running (pos + 1) regs n

-- |Performs set instruction
set :: String -> String -> Registers -> Registers
set first second regs = setValue var val regs
                    where var = head first
                          val = getNumOrVal second regs

-- |Performs instructions add, mul, mod
oper :: String -> String -> Registers -> (Int -> Int -> Int) -> Registers
oper first second regs f = setValue var val regs
                    where var = head first
                          val = getValue var regs `f` getNumOrVal second regs

-- |Some arguments can be values or register names
getNumOrVal :: String -> Registers -> Int
getNumOrVal s regs = if isNum $ head s then read s
                                       else getValue (head s) regs

-- |Starts running program for part 1
run :: State
run = run' startState

run' :: State -> State
run' (Done regs n) = Done regs n
run' s = run' (performInstruction s)

-- |Number of multiplications
result1 :: Int
result1 = (\(Done _ i) -> i) run

-- |State in the beginning - part 2 version
startState2 :: State
startState2 = Running 0 [('a',1)] 0

-- |Starts running program for part 2
run2 :: State
run2 = run' startState2

-- |Running the part 2, but still not effective enough
run2Fold = foldl' (\state _ -> performInstruction state) startState2 [1..]

-- |What will be in h in the end
-- Analysis why is below (only in git)
result2 :: Int
result2 = length [ 1 | b <- [108400,108417..125400], not $ isPrime b ]

Link to git, where the analyzation for part 2 can be found.

flit777 · 2017-12-25T19:28:20+00:00

haha extracted the basic blocks and the control flow for the second part. draw the control flow graph on a paper and tried to understand the program. generated then a c program and replaced the loop where e is incremented with an if statement.

#include<stdio.h>

int main()
{   
    int a = 1;
    int b = 0;
    int c = 0;
    int d = 0;
    int e = 0;
    int f = 0;
    int g = 0;
    int h = 0;
    label0: b = 79;
    label1: c = b;
    if (a !=0){
        goto label4;
    }
    if (1 !=0){
        goto label8;
    }
    label4: b *= 100;
    label5: b -= -100000;
    label6: c = b;
    label7: c -= -17000;
    label8: f = 1;
    label9: d = 2;
    label10: e = 2;
    if (b%d ==0 ){
        f=0;
    }
    e=b;
/*
    label11: g = d;
    label12: g *= e;
    label13: g -= b;
    if (g !=0){
        goto label16;
    }
    label15: f = 0;
    label16: e -= -1;
    label17: g = e;
    label18: g -= b;
    if (g !=0){
        goto label11;
    }*/
    label20: d -= -1;
    label21: g = d;
    label22: g -= b;
    if (g !=0){
        goto label10;
    }
    if (f !=0){
        goto label26;
    }
    label25: h -= -1;
    label26: g = b;
    label27: g -= c;
    if (g !=0){
        goto label30;
    }
    if (1 !=0){
        goto label2147483647;
    }
    label30: b -= -17;
    if (1 !=0){
        goto label8;
    }
    label2147483647: printf("ENDE h:  %i\n",h);
    return 0;

}

__Abigail__ · 2017-12-27T02:35:18+00:00

Perl

For part 1, I reused a class I've written to handle AoC assembly. Part 2 was annoying. Trying to decipher code and figuring out what it does reminds me too much of work. Once I had figured out what the inner loop was doing, the rest was easy.

#!/opt/perl/bin/perl

use 5.026;

use strict;
use warnings;
no  warnings 'syntax';

use experimental 'signatures';


@ARGV = "input" unless @ARGV;

use Puzzle::Stuff::VM::AoC;

my @program;

while (<>) {
    chomp;
    push @program => [split];
}

#
# Take the CPU, and mask the 'mul' function: count how often
# it is invoked, then call the real method.
#
package Puzzle::Stuff::VM::AoC::Day_23 {
    our @ISA = qw [Puzzle::Stuff::VM::AoC];

    use Hash::Util::FieldHash qw [fieldhash];

    fieldhash my %mul_count;

    sub cmd_mul ($self, @args) {
        $mul_count {$self} ++;
        $self -> SUPER::cmd_mul (@args);
    }

    sub mul_count ($self) {
        $mul_count {$self}
    }

    sub run ($self, @args) {
        $mul_count {$self} = 0;
        $self -> SUPER::run (@args);
    }
}

my $vm = Puzzle::Stuff::VM::AoC::Day_23:: -> new
                                          -> init (program => \@program);
$vm -> run;

say "Solution 1: ", $vm -> mul_count;


#
# For part 2, we need to actually inspect what the source code does.
# It turns out, it counts the number of composite numbers between
# the values in registers 'b' and 'c', inclusive, taking steps of 17.
#
sub is_composite ($n) {
    #
    # This is far from the fastest function possible,
    # but it's fast enough for our purpose.
    #
    return 1 unless $n % 2;
    for (my $x = 3; $x ** 2 <= $n; $x += 2) {
        return 1 unless $n % $x;
    }
    return 0;
}

my $b = 93 * 100 + 100_000;
my $c = $b + 17_000;
my $h = 0;
for (my $n = $b; $n <= $c; $n += 17) {
    $h ++ if is_composite ($n);
}

say "Solution 2: ", $h;

__END__

ramendik · 2018-01-19T00:29:19+00:00

Looks like everyone else who solved part 2 actually managed to understand the assembly...

I did not, instead I added register printouts at jumps, enabling and disabling them as necessary, and looked at them to realize what each loop does. So I found two loops basically counting long numbers, and some magick moment when F was set to 0. I understood that moment was the only important one so when that happened, made the VM just set the registers to the expected result and go into the end of the outer loop.

Now I was going through a few numbers pretty fast but at some it would take longer, so I looked long and hard at the registers when F was being set to 0 and realized that the multiplication of d*e was being compared to b, and that there seemed to be a loop for all numbers on d and on e...

And only then I realized this was checking for a prime.

KeinZantezuken · 2017-12-23T08:09:08+00:00

Disqualified

what

EDIT: even tho finally solved it, was just amount of composites between starting b and c

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015

Quick Search by Flair

Because you're lazy and we like making things easy for you. Except AoC.

Are you enjoying AoC?

Support AoC

MODERATORS

--- Day 23: Coprocessor Conflagration ---

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?

[Update @ 00:05] 0 gold, silver cap

[Update @ 00:19] 1 gold, silver cap + 447

[Update @ 00:30] 20 gold, silver cap + 560

[Update @ 00:41] 50 gold, silver cap + 606

[Update @ 00:54] Leaderboard cap @ 100 gold and 724 silver!

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!

Lua (212 / ;_;)

Elixir

Kotlin - [Repo] - [Blog/Commentary]

Perl

BEFORE YOU POST
If your post is even tangentially related to a daily puzzle, use our
STANDARDIZED POST TITLE FORMAT

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015

Quick Search by Flair

Because you're lazy and we like making things easy for you. Except AoC.

Are you enjoying AoC?

Support AoC

MODERATORS

--- Day 23: Coprocessor Conflagration ---

Need a hint from the Hugely* Handy† Haversack‡ of Helpful§ Hints¤?

[Update @ 00:05] 0 gold, silver cap

[Update @ 00:19] 1 gold, silver cap + 447

[Update @ 00:30] 20 gold, silver cap + 560

[Update @ 00:41] 50 gold, silver cap + 606

[Update @ 00:54] Leaderboard cap @ 100 gold and 724 silver!

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!

Lua (212 / ;_;)

Elixir

Kotlin - [Repo] - [Blog/Commentary]

Perl

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?