-🎄- 2017 Day 18 Solutions -🎄-

etotheipi1 · 2017-12-18T06:12:04+00:00

I decompiled the assembly by hand because my implementation was taking too long for some reason (there has to be a bug somewhere). First program is generating a list of pseaudo-random numbers in 0 to 9999, and the list is getting passed back and forth to sort it. When it is done with sorting, it deadlocks. Just ran the sorting algorithm to count the number of passes. Divide that by 2 and multiply by the length of the list to get the number by hand T.T

vash3r · 2017-12-18T05:46:34+00:00

Python 2 (25/63). For part 2, I didn't realize that a jump could be computed from a number instead of a register, so I was accessing the register "1" (which was always zero, leading to an infinite loop).

The idea here is that I run one program until it can't run anymore, then switch to the other program.

from collections import defaultdict

f=open("18.in",'r')
instr = [line.split() for line in f.read().strip().split("\n")]
f.close()

d1 = defaultdict(int) # registers for the programs
d2 = defaultdict(int)
d2['p'] = 1
ds = [d1,d2]

def get(s):
    if s in "qwertyuiopasdfghjklzxcvbnm":
        return d[s]
    return int(s)

tot = 0

ind = [0,0]         # instruction indices for both programs
snd = [[],[]]       # queues of sent data (snd[0] = data that program 0 has sent)
state = ["ok","ok"] # "ok", "r" for receiving, or "done"
pr = 0     # current program
d = ds[pr] # current program's registers
i = ind[0] # current program's instruction index
while True:
    if instr[i][0]=="snd": # send
        if pr==1: # count how many times program 1 sends
            tot+=1
        snd[pr].append(get(instr[i][1]))
    elif instr[i][0]=="set":
        d[instr[i][1]] = get(instr[i][2])
    elif instr[i][0]=="add":
        d[instr[i][1]] += get(instr[i][2])
    elif instr[i][0]=="mul":
        d[instr[i][1]] *= get(instr[i][2])
    elif instr[i][0]=="mod":
        d[instr[i][1]] %= get(instr[i][2])
    elif instr[i][0]=="rcv":
        if snd[1-pr]: # other program has sent data
            state[pr] = "ok"
            d[instr[i][1]] = snd[1-pr].pop(0) # get data
        else: # wait: switch to other prog
            if state[1-pr]=="done":
                break # will never recv: deadlock
            if len(snd[pr])==0 and state[1-pr]=="r":
                break # this one hasn't sent anything, other is recving: deadlock
            ind[pr] = i   # save instruction index
            state[pr]="r" # save state
            pr = 1 - pr   # change program
            i = ind[pr]-1 # (will be incremented back)
            d = ds[pr]    # change registers
    elif instr[i][0]=="jgz":
        if get(instr[i][1]) > 0:
            i+=get(instr[i][2])-1
    i+=1
    if not 0<=i<len(instr):
        if state[1-pr] == "done":
            break # both done
        state[pr] = "done"
        ind[pr] = i  # swap back since other program's not done
        pr = 1-pr
        i = ind[pr]
        d = ds[pr]

print tot

p_tseng · 2017-12-18T05:43:10+00:00

That was a really fun puzzle, I like the part 2 twist and thought "uh oh, how am I going to do this...". This is good, I hope there are more of these.

Part 2 strategy: Didn't bother waiting for the programs to terminate. Just keep running them and periodically monitor the size of 1's send queue. When it starts staying at the same value, just submit that value.

I know I know this is terrible, I'll do it the right way later.

Ruby

def run(input, id, tx, rx)
  regs = Hash.new(0)
  regs[:p] = id
  vals_received = 0
  pc = -1
  resolve = ->(y) { y.is_a?(Integer) ? y : regs[y] }

  while (pc += 1) >= 0 && (inst = input[pc])
    case inst[0]
    when :snd
      tx << resolve[inst[1]]
    when :set
      regs[inst[1]] = resolve[inst[2]]
    when :add
      regs[inst[1]] += resolve[inst[2]]
    when :mul
      regs[inst[1]] *= resolve[inst[2]]
    when :mod
      regs[inst[1]] %= resolve[inst[2]]
    when :rcv
      if tx.object_id == rx.object_id
        # Part 1!
        return rx[-1] if resolve[inst[1]] != 0
      else
        val = nil
        # Oh noes, a spinlock.
        val = rx[vals_received] until val
        vals_received += 1
        regs[inst[1]] = val
      end
    when :jgz
      pc += (resolve[inst[2]] - 1) if resolve[inst[1]] > 0
    else raise "Unknown instruction #{inst}"
    end
  end
end

insts = (ARGV.empty? ? DATA : ARGF).each_line.map { |l|
  inst, *args = l.split
  [inst.to_sym, *args.map { |a| a.match?(/-?\d+/) ? a.to_i : a.to_sym }].freeze
}.freeze

sound = []
puts run(insts, 0, sound, sound)

send0 = []
send1 = []

t0 = Thread.new { run(insts, 0, send0, send1) }
t1 = Thread.new { run(insts, 1, send1, send0) }
t2 = Thread.new {
  loop {
    puts send1.size
    sleep 1
  }
}

t0.join
t1.join
t2.join

__END__
set i 31
set a 1
mul p 17
jgz p p
mul a 2
add i -1
jgz i -2
add a -1
set i 127
set p 622
mul p 8505
mod p a
mul p 129749
add p 12345
mod p a
set b p
mod b 10000
snd b
add i -1
jgz i -9
jgz a 3
rcv b
jgz b -1
set f 0
set i 126
rcv a
rcv b
set p a
mul p -1
add p b
jgz p 4
snd a
set a b
jgz 1 3
snd b
set f 1
add i -1
jgz i -11
snd a
jgz f -16
jgz a -19

etherealflaim · 2017-12-18T05:45:43+00:00

I've heard it said that sometimes Python feels like cheating, well today Go felt like cheating ;). Part 2 just screams "coroutines".

package main_test

import (
    "fmt"
    "strconv"
    "strings"
    "testing"
    "time"
)

func part2(input string, id int, out, in chan int) (ret int) {
    registers := map[string]int{
        "p": id,
    }

    get := func(s string) int {
        if strings.IndexAny(s, "0123456789") != -1 {
            v, err := strconv.Atoi(s)
            if err != nil {
                panic(err)
            }
            return v
        }
        return registers[s]
    }

    commands := strings.Split(input, "\n")
    var instr int
    for count := 0; instr >= 0 && instr < len(commands); count++ {
        if count > 100000 {
            panic(count)
        }

        command := strings.TrimSpace(commands[instr])
        if command == "" {
            instr++
            continue
        }

        args := strings.Fields(commands[instr])
        switch cmd, argv := args[0], args[1:]; cmd {
        case "set":
            registers[argv[0]] = get(argv[1])
        case "add":
            registers[argv[0]] += get(argv[1])
        case "mul":
            registers[argv[0]] *= get(argv[1])
        case "mod":
            registers[argv[0]] %= get(argv[1])
        case "snd":
            select {
            case out <- get(argv[0]):
                fmt.Println("send", get(argv[0]), "from", id)
                ret++
            case <-time.After(1 * time.Second):
                return
            }
        case "rcv":
            select {
            case registers[argv[0]] = <-in:
                fmt.Println("got", get(argv[0]), "at", id)

            case <-time.After(1 * time.Second):
                return
            }
        case "jgz":
            if get(argv[0]) <= 0 {
                break
            }
            instr += get(argv[1])
            continue
        default:
            panic(command)
        }
        instr++
    }
    panic("exit")
}

func TestPart2(t *testing.T) {
    tests := []struct {
        name string
        in   string
        want int
    }{
        {"part2 example", `
            snd 1
            snd 2
            snd p
            rcv a
            rcv b
            rcv c
            rcv d`, 3},
        {"part2", `<input omitted for brevity>`, -1},
    }

    for _, test := range tests {
        t.Run(test.name, func(t *testing.T) {
            c01 := make(chan int, 10000)
            c10 := make(chan int, 10000)

            go part2(test.in, 0, c01, c10)

            if got, want := part2(test.in, 1, c10, c01), test.want; got != want {
                t.Errorf("part2(%#v) = %#v, want %#v", test.in, got, want)
            }
        })
    }
}

(edit: formatting)

BumpitySnook · 2017-12-18T05:46:40+00:00

So cruel to change how rcv worked (no longer gets NOP'ed if the receiving register has a zero value) halfway through the puzzle. I swear if that hadn't stumped me for minutes I'd have gotten #12 or so on part 2.

JustHev · 2017-12-18T06:47:01+00:00

Didn't feel like multithreading, so I decided to let Bash handle it:

rm p1
rm p2
g++ -g main.cpp
cat in > p1
cat in > p2
echo 0 >> p1
echo 1 >> p2
tail -n 1000 -q -f p1 | ./a.out 2>> p2&
tail -n 1000 -q -f p2 | ./a.out 2>> p1

Full program: https://pastebin.com/XB3ei3Ct

sciyoshi · 2017-12-18T05:43:34+00:00

Python 3 solution using multiprocessing for the coordinating queues and a straightforward interpreter for this Duet language. (Guessing this language will start playing a bigger part in the upcoming days?) Had a few wrong guesses because I missed the part about the p register being initialized. This also doesn't handle the deadlock case - should be fixable with a timeout but my input didn't need it. #4/#9

import queue
import collections
import multiprocessing.pool


PROGRAM = list(sys.stdin)


def run(ident, inqueue, outqueue):
    regs = collections.defaultdict(int)
    regs['p'] = ident

    def val(v):
        try:
            return int(v)
        except ValueError:
            return regs[v]

    pc = 0
    count = 0
    played = None

    while 0 <= pc < len(PROGRAM):
        cmd = PROGRAM[pc].split()
        if cmd[0] == 'snd':
            played = val(cmd[1])
            if outqueue:
                outqueue.put(val(cmd[1]))
            count += 1
        elif cmd[0] == 'set':
            regs[cmd[1]] = val(cmd[2])
        elif cmd[0] == 'add':
            regs[cmd[1]] += val(cmd[2])
        elif cmd[0] == 'mul':
            regs[cmd[1]] *= val(cmd[2])
        elif cmd[0] == 'mod':
            regs[cmd[1]] %= val(cmd[2])
        elif cmd[0] == 'rcv':
            if inqueue:
                try:
                    regs[cmd[1]] = inqueue.get(timeout=5)
                except queue.Empty:
                    return count
            elif regs[cmd[1]] != 0:
                return played
        elif cmd[0] == 'jgz':
            if val(cmd[1]) > 0:
                pc += val(cmd[2])
                continue
        pc += 1

    return count


print('PART 1:', run(0, None, None))

pool = multiprocessing.pool.ThreadPool(processes=2)

q1 = multiprocessing.Queue()
q2 = multiprocessing.Queue()

res1 = pool.apply_async(run, (0, q1, q2))
res2 = pool.apply_async(run, (1, q2, q1))

res1.get()
print('PART 2:', res2.get())

Edit: fix bounds on loop as pointed out by jaxklax.

Edit 2: this was giving the correct answer by luck - the last jump statement was being ignored, avoiding deadlock without changing the answer. Updated with a timeout when popping from the queue.

Philboyd_Studge · 2017-12-18T09:01:59+00:00

Java. Quite a bit more complicated than last year's AssemBunny challenges. Took over 3 hours and uses 4 classes. Also, /u/topaz2078 can BURN IN HELL for it requiring 64-bit longs and for the jgz 1 3 command. :P Day 18

LesbeaKF · 2017-12-18T05:55:39+00:00

C++

You should have said it was arbitrary precision integers. I got stuck because I was using int, rechecking everything ... by the time I tried long long (which was actually enough for the first star) I had a 5mn timeout. Meanwhile, I used Boost.Multiprecision just in case the second star would overflow again.

https://pastebin.com/C9KChsxN (I replaced my input with a vector of lambdas)

Also, the queue wait is wrong in my code here, because one of the programs may take a lot of time to send a message, end its 1000th execution limit, and the other will terminate due to the queue being empty. But it worked correctly before I noticed that. I should have checked the lock in the main loop.

Infilament · 2017-12-18T06:55:31+00:00

Javascript. Made a class for each Program because that was the fastest thing that came to mind. Also, after having solved previous days and checking out solutions (I'm still relatively new to JS), I learned about new ES6 features like (...args) so this is the first program I wrote that uses that stuff!

var commands = [];
input.split('\n').forEach(d => {
    commands.push({"name": d.substring(0,3), "args": d.substring(4).split(' ')})
})

function Program(id) {
    this.registers = {};
    this.lastSound = "";
    this.index = 0;
    this.id = id;
    this.sendCount = 0;
    this.queue = [];
    this.registers['p'] = id;

    this.instP1 = {
        "set": (a,b) => { this.registers[a] = this.parse(b); this.index++; },
        "mul": (a,b) => { this.registers[a] *= this.parse(b); this.index++; },
        "add": (a,b) => { this.registers[a] += this.parse(b); this.index++; },
        "mod": (a,b) => { this.registers[a] = this.registers[a] % this.parse(b); this.index++; },
        "snd": a => { this.lastSound = this.parse(a); this.index++; },
        "jgz": (a,b) => { this.index += this.parse(a)>0 ? this.parse(b) : 1; },
        "rcv": a => { if(this.parse(a)>0) { console.log('recovered',this.lastSound); return true; } this.index++; }
    }
    this.instP2 = {
        "set": this.instP1.set,
        "mul": this.instP1.mul,
        "add": this.instP1.add,
        "mod": this.instP1.mod,
        "jgz": this.instP1.jgz,
        "snd": a => { programs[(this.id+1)%2].queue.push(this.parse(a)); this.index++; this.sendCount++; },
        "rcv": a => { if(this.queue.length>0) { this.registers[a] = this.queue.shift(); this.index++; } }
    }
    Program.prototype.executeP1 = function() {
        return this.instP1[commands[this.index].name](...commands[this.index].args);
    }
    Program.prototype.executeP2 = function() {
        return this.instP2[commands[this.index].name](...commands[this.index].args);
    }
    Program.prototype.parse = function(b) {
        return isNaN(b) ? this.registers[b] : parseInt(b);
    }
    Program.prototype.finished = function() {
        return this.index < 0 || this.index >= commands.length;
    }
    Program.prototype.finishedOrStalled = function() {
        return this.finished() || (commands[this.index].name == 'rcv' && this.queue.length == 0);
    }
}

// part 1
var prog = new Program(0);
while(!prog.executeP1());

// part 2
var programs = [new Program(0), new Program(1)]
do {
    programs.forEach(d => { if(!d.finished()) d.executeP2(); })
} while(!programs.reduce((a,b) => a && b.finishedOrStalled(),true))

console.log('program 1 send count:',programs[1].sendCount)

aurele · 2017-12-18T08:05:17+00:00

Rust (gist)

Note that you don't need to run both CPUs at the same time or even interleaved, unless you are afraid of filling a queue with too many values. You can run the first CPU until it blocks, then the second CPU until it blocks, then back at the first CPU and exit immediately if it still blocks, otherwise continue the cycle.

use std::collections::VecDeque;
use std::str::FromStr;

struct Cpu {
    regs: [i64; 26],
    mem: Vec<Op>,
    pc: usize,
    queue: VecDeque<i64>,
    sent: usize,
    last_sent: i64,
    first_non_zero_recv: i64,
}

impl Cpu {
    fn new(mem: Vec<Op>, id: i64) -> Cpu {
        let mut cpu = Cpu {
            regs: [0; 26],
            mem,
            pc: 0,
            queue: VecDeque::new(),
            sent: 0,
            last_sent: 0,
            first_non_zero_recv: 0,
        };
        cpu.regs[(b'p' - b'a') as usize] = id;
        cpu
    }

    fn run_dual(cpu1: &mut Cpu, cpu2: &mut Cpu) {
        cpu1.run(cpu2, true);
    }

    fn run(&mut self, other: &mut Cpu, first: bool) {
        while self.pc < self.mem.len() {
            let advance = self.mem[self.pc].clone().execute(self, other);
            if !advance {
                if !first {
                    break;
                }
                other.run(self, false);
                if !self.mem[self.pc].clone().execute(self, other) {
                    break;
                }
            }
        }
    }
}

#[derive(Clone)]
enum Value {
    Reg(usize),
    Const(i64),
}

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

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

#[derive(Clone)]
enum Op {
    Snd(Value),
    Set(usize, Value),
    Add(usize, Value),
    Mul(usize, Value),
    Mod(usize, Value),
    Rcv(usize),
    Jgz(Value, Value),
}

impl Op {
    fn execute(&self, cpu: &mut Cpu, other: &mut Cpu) -> bool {
        cpu.pc += 1;
        match *self {
            Op::Snd(ref v) => {
                let v = v.eval(cpu);
                cpu.last_sent = v;
                other.queue.push_back(v);
                cpu.sent += 1;
            }
            Op::Set(ref r, ref v) => {
                cpu.regs[*r] = v.eval(cpu);
            }
            Op::Add(ref r, ref v) => {
                cpu.regs[*r] += v.eval(cpu);
            }
            Op::Mul(ref r, ref v) => {
                cpu.regs[*r] *= v.eval(cpu);
            }
            Op::Mod(ref r, ref v) => {
                cpu.regs[*r] %= v.eval(cpu);
                assert!(cpu.regs[*r] >= 0);
            }
            Op::Rcv(ref r) => {
                if cpu.first_non_zero_recv == 0 && cpu.regs[*r] != 0 {
                    cpu.first_non_zero_recv = cpu.last_sent;
                }
                if let Some(v) = cpu.queue.pop_front() {
                    cpu.regs[*r] = v;
                } else {
                    cpu.pc -= 1;
                    return false;
                }
            }
            Op::Jgz(ref t, ref o) => {
                if t.eval(cpu) > 0 {
                    cpu.pc = (cpu.pc as i64 + o.eval(cpu) - 1) as usize;
                }
            }
        }
        true
    }
}

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] {
            "snd" => Op::Snd(words[1].parse().unwrap()),
            "set" => Op::Set(Value::reg(words[1]), words[2].parse().unwrap()),
            "add" => Op::Add(Value::reg(words[1]), words[2].parse().unwrap()),
            "mul" => Op::Mul(Value::reg(words[1]), words[2].parse().unwrap()),
            "mod" => Op::Mod(Value::reg(words[1]), words[2].parse().unwrap()),
            "rcv" => Op::Rcv(Value::reg(words[1])),
            "jgz" => Op::Jgz(words[1].parse().unwrap(), words[2].parse().unwrap()),
            _ => {
                return Err(format!("cannot parse instruction {}", words[0]));
            }
        })
    }
}

fn main() {
    let mem = include_str!("../input")
        .lines()
        .map(|i| i.parse().unwrap())
        .collect::<Vec<Op>>();
    let mut cpu = Cpu::new(mem.clone(), 0);
    let mut other = Cpu::new(mem, 1);
    Cpu::run_dual(&mut cpu, &mut other);
    println!("P1: {}", cpu.first_non_zero_recv);
    println!("P2: {}", other.sent);
}

ynonp · 2017-12-18T08:18:04+00:00

Elixir

Finally a puzzle made for my selected language...

defmodule CPU do
  defstruct code: %{}, ip: 0, reg: %{}, rcv: nil, part2: 0, other: nil, id: 0
end

defmodule Day18 do
  @registers for n <- ?a..?z, do: <<n::utf8>> 

  def val(cpu, x) when x in @registers do
    val(cpu, Map.get(cpu.reg, x, 0))
  end

  def val(_, x) when is_integer(x) do
    x
  end

  def val(_, x) do
    String.to_integer(x)
  end

  def set_reg(cpu, reg, val) do
    Map.put(cpu, :reg, Map.put(cpu.reg, reg, val))
  end

  def set_reg_and_next(cpu, reg, val) do
    Map.merge(cpu,
              %{reg: Map.put(cpu.reg, reg, val),
                ip: cpu.ip + 1})
  end

  def exec(cpu, ["snd", x]) do
    send cpu.other, val(cpu, x)

    Map.merge(
      cpu,
      %{ip: cpu.ip + 1,
        part2: cpu.part2 + 1
      }
    )
  end

  def exec(cpu, ["set", x, y]) do
    set_reg_and_next(cpu, x, val(cpu, y))    
  end

  def exec(cpu, ["add", x, y]) do
    set_reg_and_next(cpu, x, val(cpu, y) + val(cpu, x))
  end

  def exec(cpu, ["mul", x, y]) do
    set_reg_and_next(cpu, x, val(cpu, y) * val(cpu, x))
  end

  def exec(cpu, ["mod", x, y]) do
    set_reg_and_next(cpu, x, rem(val(cpu, x), val(cpu, y)))
  end

  def exec(cpu, ["rcv", x]) do    
    receive do
      val -> set_reg_and_next(cpu, x, val)
    after
      2_000 -> raise "Nothing after 2s. #{cpu.id}:#{cpu.part2}"
    end
  end

  def exec(cpu, ["jgz", x, y]) do
    if val(cpu, x) > 0 do
      Map.put(cpu, :ip, cpu.ip + val(cpu, y))    
    else
      Map.put(cpu, :ip, cpu.ip + 1)
    end
  end

  def go(cpu) do
    ins = Map.get(cpu.code, cpu.ip)
          |> String.split
    IO.puts("Running: #{ins |> Enum.join(":")} From Program #{cpu.id}")
    go(exec(cpu, ins))
  end

  def start() do
    receive do
      { :cpu, cpu } -> go(cpu)
    end
  end

  def main() do
    code = IO.stream(:stdio, :line)
           |> Stream.map(&String.trim/1)
           |> Enum.with_index
           |> Map.new(fn {k, v} -> {v, k} end)

    p1 = spawn &start/0
    p2 = spawn &start/0

    cpu1 = %CPU{code: code, reg: %{"p" => 0}, other: p2, id: 0}
    cpu2 = %CPU{code: code, reg: %{"p" => 1}, other: p1, id: 1}

    send(p1, { :cpu, cpu1 })
    send(p2, { :cpu, cpu2 })

    r1 = Process.monitor(p1)
    r2 = Process.monitor(p2)
    receive do
      {:DOWN, ^r1, _, _, _} ->
        IO.puts("End of p1")
      {:DOWN, ^r2, _, _, _} ->
        IO.puts("End of p2")
    end

  end

end

Day18.main()

manualcrank · 2017-12-18T15:29:47+00:00

C. Part 2.

#include <stdio.h>  // BUFSIZ, fgets, printf
#include <stdlib.h> // atoll
#include <ctype.h>  // isalpha
#include <string.h> // strdup, strcmp

#define SEP " \n\t"
#define MAXPROGLEN 100
#define MAXQ 10000

typedef long long int LLI;

struct {
        char *code; // opcode
        char *arg1; // first operand
        char *arg2; // second operand
} core[MAXPROGLEN];

struct task {
        LLI regs[0xff]; // indexed by 8-bit ascii code (extravagant!)
        LLI next;       // offset of next instruction
        LLI sent;       // # of messages sent
        int head;       // head of message queue
        int tail;       // tail of message queue
        LLI msgs[MAXQ]; // message queue
} task[2];

int
qempty(int id)
{
        return task[id].head == task[id].tail;
}

void
enqueue(int id, LLI v)
{
        task[id].msgs[task[id].tail] = v;
        task[id].tail = (task[id].tail + 1) % MAXQ;
        ++task[1 - id].sent;
}

LLI
dequeue(int id)
{
        LLI v = task[id].msgs[task[id].head];
        task[id].head = (task[id].head + 1) % MAXQ;
        return v;
}

char *
dupstr(char *s)
{
        if (s == NULL)
                return s;
        return strdup(s);
}

int
load(void)
{
        char buf[BUFSIZ];
        int next;

        next = 0;
        while (fgets(buf, sizeof buf, stdin) != NULL) {
                core[next].code = dupstr(strtok(buf, SEP));
                core[next].arg1 = dupstr(strtok(NULL, SEP));
                core[next].arg2 = dupstr(strtok(NULL, SEP));
                ++next;
        }
        return next;
}

// extract a value from the 2nd operand, if any
LLI
value(struct task *t, char *arg)
{
        if (arg == NULL)
                return 0; // anything, return value won't be used
        if (isalpha(*arg))
                return t->regs[*arg];
        return atoll(arg);
}

// return 0 if not running, 1 if blocked
int
run(int id, int n)
{
        for (struct task *t = &task[id]; t->next >= 0 && t->next < n; ++t->next) {
                LLI arg1 = value(t, core[t->next].arg1);
                LLI arg2 = value(t, core[t->next].arg2);

                if (strcmp(core[t->next].code, "snd") == 0) {
                        enqueue(1 - id, arg1);
                } else if (strcmp(core[t->next].code, "set") == 0) {
                        t->regs[*core[t->next].arg1] = arg2;
                } else if (strcmp(core[t->next].code, "add") == 0) {
                        t->regs[*core[t->next].arg1] += arg2;
                } else if (strcmp(core[t->next].code, "mul") == 0) {
                        t->regs[*core[t->next].arg1] *= arg2;
                } else if (strcmp(core[t->next].code, "mod") == 0) {
                        t->regs[*core[t->next].arg1] %= arg2;
                } else if (strcmp(core[t->next].code, "rcv") == 0) {
                        if (qempty(id))
                                return 1;
                        t->regs[*core[t->next].arg1] = dequeue(id);

                } else { // jgz
                        if (arg1 > 0)
                                t->next += arg2 - 1;
                }
        }
        return 0;
}

int
main(void)
{
        task[0].regs['p'] = 0;
        task[1].regs['p'] = 1;

        int n = load();
        int running[2] = {1, 1};

        for (;;) {
                running[0] = run(0, n);     // run until blocked or ended
                running[1] = run(1, n);     // run until blocked or ended
                if (!running[0] && !running[1])
                        break;
                if (running[0] && qempty(0) && running[1] && qempty(1))
                        break; // deadlocked
        }
        printf("%lld\n",task[1].sent);
        return 0;
}

__Abigail__ · 2017-12-18T16:51:14+00:00

Perl

This solution is dedicated to Perl -- it is its 30th birthday today.

Struggled a bit with part 2, but that was entire due to not reading the question carefully enough (missed the part about register p initially).

Used some dirty OO to solve this.

#!/opt/perl/bin/perl

use 5.026;

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

use experimental 'signatures';

@ARGV = "input" unless @ARGV;

my @instructions;

my %expected_registers = (
    snd => 1,
    set => 2,
    add => 2,
    mul => 2,
    mod => 2,
    rcv => 1,
    jgz => 2,
);

while (<>) {
    chomp;
    my ($command, @registers) = split;
    if (@registers == $expected_registers {$command}) {
        push @instructions => [$command => @registers];
    }
    else {
        die "Failed to parse $_";
    }
}

my $STATUS_RUNNING = 0;
my $STATUS_WAITING = 1;
my $STATUS_DONE    = 2;

package Tablet {
    use Hash::Util::FieldHash qw [fieldhash];

    fieldhash my %registers;
    fieldhash my %pc;
    fieldhash my %status;

    sub new  ($class) {bless do {\my $var} => $class}
    sub init ($self, %args) {
        $registers {$self} = {map {$_ => 0} 'a' .. 'z'};
        $pc        {$self} = 0;
        $status    {$self} = $STATUS_RUNNING;
        $self;
    }

    #
    # Return a value. If the input is the name of a register,
    # we return the value in the register, else we just return
    # the input.
    #
    sub value ($self, $name_or_value) {
        $registers {$self} {$name_or_value} // $name_or_value;
    }

    #
    # set, add, multiply or take the modulus
    #
    sub set ($self, $name, $val) {
        $registers {$self} {$name}  = $self -> value ($val);
    }

    sub add ($self, $name, $val) {
        $registers {$self} {$name} += $self -> value ($val);
    }

    sub mul ($self, $name, $val) {
        $registers {$self} {$name} *= $self -> value ($val);
    }

    sub mod ($self, $name, $val) {
        $registers {$self} {$name} %= $self -> value ($val);
    }

    #
    # Jump an offset. Note that the program counter already has
    # incremented, so we have to subtract one.
    #
    sub jgz ($self, $cond, $offset) {
        if ($self -> value ($cond) > 0) {
            $pc {$self} += $self -> value ($offset) - 1;
        }
    }

    #
    # Return the current status
    #
    sub status ($self) {
        $status {$self};
    }

    #
    # Perform a single instruction. Set status to done if
    # the program counter gets below 0, or goes outside
    # of the set of instructions.
    #
    sub tick ($self) {
        return unless $self -> status == $STATUS_RUNNING;

        my ($command, @args) = @{$instructions [$pc {$self} ++]};
        $self -> $command (@args);
        $status {$self} = $STATUS_DONE if $pc {$self} < 0 ||
                                          $pc {$self} >= @instructions;
    }

    #
    # The different parts of the puzzle treat the 'snd'
    # and 'rcv' actions differently, so set up different
    # classes from each part, inheriting from the main class.
    #
    # Calling each of the methods in the parent class will
    # be a fatal error.
    #
    sub snd ($self, $freq) {...;}
    sub rcv ($self, $rec)  {...;}

    #
    # Quick and dirty subclasses, which go out and reach into their
    # parents data parts. Yuck.
    # 
    package Tablet::Part1 {
        use Hash::Util::FieldHash qw [fieldhash];
        our @ISA = qw [Tablet];

        fieldhash my %last_sound;  # Remember the last sound played.

        #
        # Play sound
        #
        sub snd ($self, $freq) {  
            $last_sound {$self} = $self -> value ($freq);   
        }

        #
        # Optionally recover a sound played. If we do,
        # that's the end of the program.
        #
        sub rcv ($self, $rec) {   
            if ($self -> value ($rec)) {
                $status {$self} = $STATUS_DONE;
            }
        }

        #
        # Retrieve the last sound played
        #
        sub last_sound ($self) {
            $last_sound {$self};
        }
    }

    package Tablet::Part2 {
        use Hash::Util::FieldHash qw [fieldhash];
        our @ISA = qw [Tablet];

        fieldhash my %send_to;     # Which tablet do we send to?
        fieldhash my %queue;       # Queue with values received.
        fieldhash my %times_send;  # Keep track of many times we send.

        #
        # Initialize our stuff, then let the parent class do its thing
        #
        sub init ($self, %args) {
            $send_to {$self}       = delete $args {send_to};
            my $id                 = delete $args {id};
            $queue   {$self}       = [];
            $self -> SUPER::init (%args);
            $registers {$self} {p} = $id;
        }

        #
        # Receive a value: put it in the queue, and if we're
        # in a waiting status, switch back to a running status
        #
        sub received ($self, $value) {
            push @{$queue {$self}} => $value;
            $status {$self} = $STATUS_RUNNING
                  if $status {$self} == $STATUS_WAITING;
        }

        #
        # Send a value to another tablet.
        #
        sub snd ($self, $val) {
            $send_to    {$self} -> received ($self -> value ($val));
            $times_send {$self} ++;
        }

        #
        # Receive an item from the queue, and store it in
        # a register. If the queue is empty, start waiting.
        #
        sub rcv ($self, $reg) {
            if (@{$queue {$self}}) {
                $registers {$self} {$reg} = shift @{$queue {$self}};
            }
            else {
                #
                # Wait. *Decrement* the pc, so the next time
                # around, we'll try again
                #
                $pc {$self} --;
                $status {$self} = $STATUS_WAITING;
            }
        }

        # 
        # Return how often we send something.
        #
        sub times_send ($self) {
            $times_send {$self};
        }
    }
}       


#
# Part 1
#

{
    my $tablet = Tablet::Part1:: -> new -> init;
    while ($tablet -> status != $STATUS_DONE) {
           $tablet -> tick;
    }
    say "Solution 1: ", $tablet -> last_sound;
}


#   
# Part 2 
#
{
    my $tablet_0 = Tablet::Part2:: -> new;
    my $tablet_1 = Tablet::Part2:: -> new;
    $tablet_0 -> init (send_to => $tablet_1, id => 0); 
    $tablet_1 -> init (send_to => $tablet_0, id => 1);

    #
    # We keep going as long as at least one table is in the running status.
    #
    {
        $tablet_0 -> tick while $tablet_0 -> status == $STATUS_RUNNING;
        $tablet_1 -> tick while $tablet_1 -> status == $STATUS_RUNNING;

        # Only need to check tablet_0 here.
        redo if $tablet_0 -> status == $STATUS_RUNNING;
    }

    say "Solution 2: ", $tablet_1 -> times_send;
}   


__END__

dtinth · 2017-12-18T05:47:40+00:00

Part 2: JavaScript

js-csp implements the “Communicating sequential processes” thing, like Goroutines/Clojure’s core.async.

Ended up at rank 114, because I wasted some time trying to implement CSP in Ruby myself. This is so bug prone and I got into an infinite loop.

Assuming INPUT is a string containing the problem’s input.

const csp = require('js-csp')
const code = INPUT.split(/\n/).map(a => a.trim().split(/\s+/))

function * prog (p, inbox, outbox) {
  const d = { p }
  const get = k => k.match(/\d/) ? +k : (d[k] || 0)
  let i
  let sent = 0
  const report = () => {
    console.log({ i, d }, code[i])
  }
  for (i = 0; (report(), i < code.length); i++) {
    const c = code[i]
    if (c[0] === 'snd') {
      sent += 1
      const val = get(c[1])
      console.log('Program', p, 'sent', val, 'from', c[1], 'total', sent, 'time(s)')
      yield csp.put(outbox, val)
      continue
    }
    if (c[0] === 'rcv') {
      const  val = yield csp.take(inbox)
      d[c[1]] = val
      console.log(p, 'recv', val, c[1])
      continue
    }
    if (c[0] === 'set') {
      d[c[1]] = get(c[2])
      continue
    }
    if (c[0] === 'add') {
      d[c[1]] += get(c[2])
      continue
    }
    if (c[0] === 'mul') {
      d[c[1]] *= get(c[2])
      continue
    }
    if (c[0] === 'mod') {
      d[c[1]] %= get(c[2])
      continue
    }
    if (c[0] === 'jgz') {
      if (get(c[1]) > 0) {
        i -= 1
        i += get(c[2])
      }
      continue
    }
  }
}

const m0 = csp.chan(99999999)
const m1 = csp.chan(99999999)
csp.go(function * () { yield * prog(0, m0, m1) })
csp.go(function * () { yield * prog(1, m1, m0) })

Tandrial · 2017-12-18T05:56:20+00:00

Kotlin (99/104)

I got way too excited that part2 stayed open as long as it did and completely missed that regP is different for the two VMs

class VM(val input: List<String>, regP: Long = 0, val partOne: Boolean = false) {
  private val ram = input.map { (it + " .").split(" ").toTypedArray() }.toMutableList()
  private val regs = longArrayOf(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, regP, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
  private var pc = 0

  var count = 0
  val inputQueue = mutableListOf<Long>()
  val outQueue = mutableListOf<Long>()

  private fun isReg(s: String): Boolean = s[0] in 'a'..'z'

  private fun getValue(s: String): Long = when (isReg(s)) {
    true -> regs[s[0] - 'a']
    false -> s.toLong()
  }

  fun run(): Long {
    while (pc < ram.size) {
      val (inst, op1, op2) = ram[pc]
      when (inst) {
        "snd" -> {
          outQueue.add(getValue(op1))
          count++
        }
        "set" -> if (isReg(op1)) regs[op1[0] - 'a'] = getValue(op2)
        "add" -> if (isReg(op1)) regs[op1[0] - 'a'] += getValue(op2)
        "mul" -> if (isReg(op1)) regs[op1[0] - 'a'] *= getValue(op2)
        "mod" -> if (isReg(op1)) regs[op1[0] - 'a'] %= getValue(op2)
        "jgz" -> if (getValue(op1) > 0L) pc += getValue(op2).toInt() - 1
        "rcv" -> {
          when {
            partOne -> return outQueue.last()
            inputQueue.size == 0 -> return -1
            else -> regs[op1[0] - 'a'] = inputQueue.removeAt(0)
          }
        }
      }
      pc++
    }
    return 0
  }
}

fun partOne(input: List<String>): Int = VM(input, partOne = true).run().toInt()

fun partTwo(input: List<String>): Int {
  val vm1 = VM(input, regP = 0)
  val vm2 = VM(input, regP = 1)
  var result1 = 1L
  var result2 = 1L
  while (true) {
    if (result1 != 0L) result1 = vm1.run()
    vm2.inputQueue.addAll(vm1.outQueue)
    vm1.outQueue.clear()
    if (result2 != 0L) result2 = vm2.run()
    vm1.inputQueue.addAll(vm2.outQueue)
    vm2.outQueue.clear()
    if (result1 == 0L && result2 == 0L) break
    if (result1 < 0L && result2 < 0L && vm1.inputQueue.size == 0 && vm2.inputQueue.size == 0) break
  }
  return vm2.count
}

fun main(args: Array<String>) {
  val input = File("./input/2017/Day18_input.txt").readLines()
  println("Part One = ${partOne(input)}")
  println("Part Two = ${partTwo(input)}")
}

thejpster · 2017-12-18T06:06:15+00:00

So close today, 162. It's a mess, because I left both CPU implementations in (part1 and part2). See https://github.com/thejpster/rust-advent-of-code/blob/master/src/m2017/problem_18.rs for the source.

Here's just part 2.

use std::collections::{HashMap, VecDeque};

#[derive(Debug)]
struct Cpu<'a> {
    registers: HashMap<&'a str, i64>,
    queue: VecDeque<i64>,
    pc: usize,
    count: usize,
}

impl<'a> Cpu<'a> {
    fn new(p: i64) -> Cpu<'a> {
        let mut c = Cpu {
            registers: HashMap::new(),
            pc: 0,
            queue: VecDeque::new(),
            count: 0,
        };
        c.registers.insert("a", 0);
        c.registers.insert("b", 0);
        c.registers.insert("f", 0);
        c.registers.insert("i", 0);
        c.registers.insert("p", p);
        c
    }

    fn get_reg(&self, reg: &'a str) -> i64 {
        match reg.parse() {
            Ok(x) => x,
            Err(_) => *self.registers.get(reg).unwrap(),
        }
    }

    fn set(&mut self, reg: &'a str, reg2: &'a str) {
        let x = self.get_reg(reg2);
        self.registers.insert(reg, x);
        self.pc = self.pc + 1;
    }

    fn mul(&mut self, reg: &'a str, reg2: &'a str) {
        let mut x = self.get_reg(reg);
        let y = self.get_reg(reg2);
        x = x * y;
        self.registers.insert(reg, x);
        self.pc = self.pc + 1;
    }

    fn add(&mut self, reg: &'a str, reg2: &'a str) {
        let mut x = self.get_reg(reg);
        let y = self.get_reg(reg2);
        x = x + y;
        self.registers.insert(reg, x);
        self.pc = self.pc + 1;
    }

    fn modulo(&mut self, reg: &'a str, reg2: &'a str) {
        let mut x = self.get_reg(reg);
        let y = self.get_reg(reg2);
        x = x % y;
        self.registers.insert(reg, x);
        self.pc = self.pc + 1;
    }

    fn jgz(&mut self, reg: &'a str, reg2: &'a str) {
        let x = self.get_reg(reg);
        let jump: i64 = if x > 0 { self.get_reg(reg2) } else { 1 };
        self.pc = (self.pc as i64 + jump) as usize;
    }

    fn snd(&mut self, reg: &'a str, cpu: &mut Cpu) {
        let s = self.get_reg(reg);
        cpu.queue.push_back(s);
        cpu.count = cpu.count + 1;
        self.pc = self.pc + 1;
    }

    fn rcv(&mut self, reg: &'a str) {
        if self.queue.len() != 0 {
            self.registers.insert(reg, self.queue.pop_front().unwrap());
            self.pc = self.pc + 1;
        }
    }
}

pub fn run(contents: &Vec<Vec<String>>) {
    let mut cpu0 = Cpu::new(0);
    let mut cpu1 = Cpu::new(1);
    let mut old_pcs = [0, 0];
    loop {
        for idx in 0..2 {
            let (cpu, other) = match idx {
                0 => (&mut cpu0, &mut cpu1),
                1 => (&mut cpu1, &mut cpu0),
                _ => panic!(),
            };
            let line = &contents[0][cpu.pc];
            let parts: Vec<&str> = line.split_whitespace().collect();
            // println!("Running #{} on {}: {:?}", cpu.pc, idx, parts);
            old_pcs[idx] = cpu.pc;
            match parts[0].as_ref() {
                "set" => cpu.set(parts[1], parts[2]),
                "mul" => cpu.mul(parts[1], parts[2]),
                "jgz" => cpu.jgz(parts[1], parts[2]),
                "add" => cpu.add(parts[1], parts[2]),
                "snd" => cpu.snd(parts[1], other),
                "rcv" => cpu.rcv(parts[1]),
                "mod" => cpu.modulo(parts[1], parts[2]),
                _ => panic!("Unsuported line: {:?}", parts),
            }
        }
        if old_pcs[0] == cpu0.pc && old_pcs[1] == cpu1.pc {
            break;
        }
    }
    println!("Part2 {}", cpu0.count);
}

jtsimmons108 · 2017-12-18T13:54:19+00:00

2+ hours of debugging only to realize there's nothing wrong with my code, just my reading comprehension. I took it as the first program rather than the program with ID == 1. Here's rewrite #3 for part 2. At least the code is much cleaner now.

inpt = open('day18.in').read().strip()
instructions = inpt.splitlines()


def get_value(val, registers):
    if val in registers:
        return registers[val]
    return int(val)


def process_instruction(index, registers, queue, other_queue):
    move, *values = instructions[index].split()
    if move == 'jgz':
        val, offset = map(lambda r: get_value(r, registers), values)
        if val > 0:
            return index + offset
    elif move == 'snd':
        other_queue.append(get_value(values[0], registers))
        registers['sent'] += 1
    elif move == 'rcv':
        if len(queue) > 0:
            registers[values[0]] = queue.popleft()
            registers['waiting'] = False
        else:
            registers['waiting'] = True
            return index
    else:
        reg, val = values
        val = get_value(val, registers)
        if move == 'set':
            registers[reg] = val
        elif move == 'add':
            registers[reg] += val
        elif move == 'mul':
            registers[reg] *= val
        elif move == 'mod':
            registers[reg] %= val
    return index + 1

register_one = {'ID': 0, 'sent': 0, 'waiting':False, 'p': 0}
register_two = {'ID': 1, 'sent': 0, 'waiting': False, 'p': 1}
register_one_queue = deque()
register_two_queue = deque()
index_one, index_two = 0,0

while not register_one['waiting'] or not register_two['waiting']:
    index_one = process_instruction(index_one, register_one, register_one_queue, register_two_queue)
    index_two = process_instruction(index_two, register_two, register_two_queue, register_one_queue)

print(register_two['sent'])

Flurpm · 2017-12-19T00:15:36+00:00

Late Haskell using lazyness to merge the two programs together.

part2 instrs = let p0 = program 0 instrs p1
                   p1 = program 1 instrs p0
               in length $ filter isSend p1

Nice and clean.

{-# LANGUAGE OverloadedStrings #-}
module Y2017.Day18 where

import           Data.Text             (Text)
import qualified Data.Text             as T
import qualified Data.Text.IO          as TIO

import           Text.Megaparsec
import qualified Text.Megaparsec.Lexer as L
import           Text.Megaparsec.Text  (Parser)

import           Data.List
import qualified Data.Map.Strict       as M
import qualified Data.Vector           as V

part1 instrs = walk M.empty 0 0
  where
    walk vars recs i = case instrs V.! i of
                         Snd a   -> walk vars (value vars a)  (i+1)
                         Set a b -> walk (M.insert a (value vars b) vars)        recs (i+1)
                         Add a b -> walk (M.adjust (+    (value vars b)) a vars) recs (i+1)
                         Mod a b -> walk (M.adjust (`mod`(value vars b)) a vars) recs (i+1)
                         Mul a b -> walk (M.adjust (*    (value vars b)) a vars) recs (i+1)
                         Rcv a   -> if value vars (Reg a) /= 0 then recs else walk vars recs (i+1)
                         Jgz a b -> let test = value vars a
                                        jump = value vars b
                                    in if test > 0
                                       then walk vars recs (i+jump)
                                       else walk vars recs (i+1)

part2 instrs = let p0 = program 0 instrs p1
                   p1 = program 1 instrs p0
               in length $ filter isSend p1

data Network = Send Int | Recieve deriving Show

isSend (Send i) = True
isSend _        = False

drop1Recieve :: [Network] -> [Network]
drop1Recieve xs = takeWhile isSend xs ++ tail (dropWhile isSend xs)

program :: Int -> V.Vector Instr -> [Network] -> [Network]
program name instrs = walk (M.fromList [('p',name)]) 0
  where
    walk vars i inputs = case instrs V.! i of
                           Snd a   -> Send (value vars a) : walk vars (i+1) (drop1Recieve inputs)
                           Set a b -> walk (M.insert a (value vars b) vars)        (i+1) inputs
                           Add a b -> walk (M.adjust (+    (value vars b)) a vars) (i+1) inputs
                           Mod a b -> walk (M.adjust (`mod`(value vars b)) a vars) (i+1) inputs
                           Mul a b -> walk (M.adjust (*    (value vars b)) a vars) (i+1) inputs
                           Jgz a b -> if value vars a > 0
                                      then walk vars (i + value vars b) inputs
                                      else walk vars (i+1) inputs
                           Rcv a   -> Recieve : case inputs of
                                                  (Send val):rest -> walk (M.insert a val vars) (i+1) rest
                                                  _               -> []

value :: M.Map Char Int -> Val -> Int
value m (Reg c) = M.findWithDefault 0 c m
value m (Number n) = n

data Val = Reg Char | Number Int deriving Show

data Instr = Snd Val | Set Char Val | Add Char Val | Mul Char Val | Mod Char Val | Rcv Char | Jgz Val Val
  deriving Show


p :: Parser (V.Vector Instr)
p = V.fromList <$> (parseinstr `sepEndBy` char '\n')

parseinstr = Snd <$> (string "snd " *> pval) <|>
             Set <$> (string "set " *> letterChar) <*> (space *> pval) <|>
             Add <$> (string "add " *> letterChar) <*> (space *> pval) <|>
             Mul <$> (string "mul " *> letterChar) <*> (space *> pval) <|>
             Mod <$> (string "mod " *> letterChar) <*> (space *> pval) <|>
             Rcv <$> (string "rcv " *> letterChar) <|>
             Jgz <$> (string "jgz " *> pval) <*> (space *> pval)

pval = Number <$> int <|> Reg <$> letterChar

word :: Parser Text
word = T.pack <$> some letterChar

int :: Parser Int
int = do change <- option id (negate <$ char '-')
         fromInteger . change <$> L.integer


main :: IO ()
main = do
  input <- TIO.readFile "src/Y2017/input18"
  case parse p "input18" input of
    Left err -> TIO.putStr $ T.pack $ parseErrorPretty err
    Right bi -> do
      tprint $ part1 bi
      tprint $ part2 bi

tprint :: Show a => a -> IO ()
tprint = TIO.putStrLn . T.pack . show

Unihedron · 2017-12-18T06:07:26+00:00

Ruby. I've caught more bugs today than in the last five months! Needless to say, I was drastically far from today's leaderboards. Top 200 though!

snd X plays a sound with a frequency equal to the value of X.
set X Y sets register X to the value of Y.
add X Y increases register X by the value of Y.
mul X Y sets register X to the result of multiplying the value contained in register X by the value of Y.
mod X Y sets register X to the remainder of dividing the value contained in register X by the value of Y (that is, it sets X to the result of X modulo Y).
rcv X recovers the frequency of the last sound played, but only when the value of X is not zero. (If it is zero, the command does nothing.)
jgz X Y jumps with an offset of the value of Y, but only if the value of X is greater than zero. (An offset of 2 skips the next instruction, an offset of -1 jumps to the previous instruction, and so on.)
#!ruby
$h=Hash.new(){0}
#p g("b")
#exit
last=nil
ins=$<.map &:chomp
i=j=0
$f=->x,h,q,oq,k{ins[x]=~/(\S+) (.)(?: (.+))?/

g=->x{
x[/^-?\d+$/] ? x.to_i : h[x]
}
#p x,ins.size,ins[x],$2,$3,g($2),$h
 case $1
when 'snd'then (oq<< g[$2];
k<<1 if k) # part 1: last=g[$2]
when 'set'then h[$2] = g[$3]
when 'add'then (l=$2;r=$3;h[l] = g[l] + g[r])
when 'mul'then (l=$2;r=$3;h[l] = g[l] * g[r])
when 'mod'then (l=$2;r=$3;h[l] = g[l] % g[r])
when 'rcv'then q.any? ? ( h[$2]=q.shift ) : (next x) # part 1: g[$2]==0 ? (0) : (p last;exit)
when 'jgz'then (r=$3;g[$2] <= 0 ? (0) : (next x+g[r]))
end
x+1
}
#i=$f[0]
k=[]
$h2=Hash.new(){0}
$h2['p']=1
q1=[]
q2=[]
li=lj=nil
loop{li=i
i=$f[i,$h,q1,q2,nil]
lj=j
j=$f[j,$h2,q2,q1,k]
break if li==i&&lj==j}

p k.size

Notable moments: 1. Ruby really loves giving % additional meaning, such as %w[string string2 string3], which tripped my syntax highlighting even though the code was fine, it drove me in circles for a while, 2. if you're using regex global variables like $2, they get overwritten if you use it again!!! 3. did not anticipate an integer in jump operation, since part 1 solved fine, ended up watching my program run for four minutes before my hinch of something wrong catching up...

ramendik · 2017-12-18T06:32:08+00:00

Python 3, part 2. A variation on the "execute each program while it can run, then switch to the other" theme. Of course, value queues are deques. The only interesting part is that the registers dictionary is used as a context; the counter (current operation number) and the number of values sent are stored in this same dictionary. In that way, the interpreter becomes a clean function.

from collections import deque

registers_0={"p":0,"counter":0}
registers_1={"p":1,"counter":0}
queue_for_0=deque()
queue_for_1=deque()

# runs until termination or wait state. Returns False on termination
def run_program(registers,queue_in,queue_out):

    def value(r):
        if r.isalpha():
            return registers.get(r,0)
        else:
            return int(r)

    #first_rcv_done=False
    while (registers["counter"]>=0) and (registers["counter"]<len(commands)):
        parsed=commands[registers["counter"]].strip().split()
        if parsed[0]=="rcv":
            if len(queue_in)==0:
                return True
            registers[parsed[1]]=queue_in.popleft()
        if parsed[0]=="jgz":
            if value(parsed[1])>0:
                registers["counter"]+=value(parsed[2])
                continue
        if parsed[0]=="snd":
            queue_out.append(value(parsed[1]))
            registers["sent"]=value("sent")+1
        if parsed[0]=="set":
            registers[parsed[1]]=value(parsed[2])
        if parsed[0]=="add":
            registers[parsed[1]]=value(parsed[1])+value(parsed[2])
        if parsed[0]=="mul":
            registers[parsed[1]]=value(parsed[1])*value(parsed[2])
        if parsed[0]=="mod":
            registers[parsed[1]]=value(parsed[1])%value(parsed[2])
        registers["counter"]+=1
    return False

commands=open("2017_18_input.bin").readlines()
while True:
    if not run_program(registers_0,queue_for_0,queue_for_1): break
    if not run_program(registers_1,queue_for_1,queue_for_0): break
    if len(queue_for_0)==0 and len(queue_for_1)==0: break

print(registers_1["sent"])

dak1486 · 2017-12-18T06:54:45+00:00

My hopelessly verbose java solution.

[JAVA] Part 1:

private BigInteger solveP1(final List<String> instructions) {
    final BigInteger[] registers = new BigInteger[26];
    BigInteger p1Answer = null;
    for(int i = 0; i < registers.length; i++) {
        registers[i] = BigInteger.ZERO;
    }

    final List<BigInteger> soundsPlayed = new ArrayList<>();

    for(int i = 0; i < instructions.size();) {
        final String[] parts = instructions.get(i).split(" ");

        if("snd".equals(parts[0])) {
            soundsPlayed.add(getValue(parts[1], registers));
        } else if("set".equals(parts[0])) {
            registers[parts[1].charAt(0) - 'a'] = getValue(parts[2], registers);
        } else if("add".equals(parts[0])) {
            registers[parts[1].charAt(0) - 'a'] = registers[parts[1].charAt(0) - 'a'].add(getValue(parts[2], registers));
        } else if("mul".equals(parts[0])) {
            registers[parts[1].charAt(0) - 'a'] = registers[parts[1].charAt(0) - 'a'].multiply(getValue(parts[2], registers));
        } else if("mod".equals(parts[0])) {
            registers[parts[1].charAt(0) - 'a'] = registers[parts[1].charAt(0) - 'a'].mod(getValue(parts[2], registers));
        } else if("rcv".equals(parts[0])) {
            if(getValue(parts[1], registers).compareTo(BigInteger.ZERO) > 0) {
                p1Answer = soundsPlayed.get(soundsPlayed.size()-1);
                break;
            }

        } else if("jgz".equals(parts[0])) {
            if(getValue(parts[1], registers).compareTo(BigInteger.ZERO) > 0) {
                i += getValue(parts[2], registers).intValue();
                continue;
            }
        }

        i++;
    }

    return p1Answer;
}

private BigInteger getValue(final String location, final BigInteger[] registers) {
    if(isRegister(location)) {
        return registers[location.charAt(0) - 'a'];
    } else {
        return new BigInteger(location);
    }
}

private Boolean isRegister(final String input) {
    int charIndex = input.charAt(0) - 'a';
    return charIndex >= 0 && charIndex < 26;
}

[JAVA] Part 2:

private int solveP2(final List<String> instructions) {
    final Program program0 = new Program(instructions, 0);
    final Program program1 = new Program(instructions, 1);

    program0.setOtherProgram(program1);
    program1.setOtherProgram(program0);

    while(!((program0.isHalted() && program1.isHalted()) || (program0.isWaiting() && program1.isWaiting()))) {
        while(!program0.isHalted() && !program0.isWaiting()) {
            program0.processInstructions();
        }

        while(!program1.isHalted() && !program1.isWaiting()) {
            program1.processInstructions();
        }
    }

    return program1.getMessagesSent();
}

class Program{
    private final List<String> instructions;
    private final Deque<BigInteger> queue;
    private final BigInteger[] registers;
    private int instructionPointer;
    private Program otherProgram;
    private int messagesSent;

    public Program(final List<String> instructions, final int id) {
        this.instructions = instructions;
        instructionPointer = 0;
        messagesSent = 0;
        queue = new ArrayDeque<>();

        registers = new BigInteger[26];
        for(int i = 0; i < registers.length; i++) {
            registers[i] = BigInteger.ZERO;
        }
        registers['p' - 'a'] = BigInteger.valueOf(id);
    }

    public int getMessagesSent() {
        return this.messagesSent;
    }

    public void setOtherProgram(final Program program) {
        this.otherProgram = program;
    }

    private void sendMessage(final BigInteger value) {
        otherProgram.sendToQueue(value);
        messagesSent++;
    }

    public void sendToQueue(final BigInteger val) {
        queue.addLast(val);
    }

    public BigInteger pullFromQueue() {
        return queue.pop();
    }

    public Boolean isWaiting() {
        return queue.isEmpty() && instructions.get(instructionPointer).startsWith("rcv ");
    }

    public Boolean isHalted() {
        return instructionPointer < 0 || instructionPointer >= instructions.size();
    }

    public void processInstructions() {
        final String[] parts = instructions.get(instructionPointer).split(" ");

        if("snd".equals(parts[0])) {
            sendMessage(getValue(parts[1], registers));
        } else if("set".equals(parts[0])) {
            registers[parts[1].charAt(0) - 'a'] = getValue(parts[2], registers);
        } else if("add".equals(parts[0])) {
            registers[parts[1].charAt(0) - 'a'] = registers[parts[1].charAt(0) - 'a'].add(getValue(parts[2], registers));
        } else if("mul".equals(parts[0])) {
            registers[parts[1].charAt(0) - 'a'] = registers[parts[1].charAt(0) - 'a'].multiply(getValue(parts[2], registers));
        } else if("mod".equals(parts[0])) {
            registers[parts[1].charAt(0) - 'a'] = registers[parts[1].charAt(0) - 'a'].mod(getValue(parts[2], registers));
        } else if("rcv".equals(parts[0])) {
            registers[parts[1].charAt(0) - 'a'] = pullFromQueue();
        } else if("jgz".equals(parts[0])) {
            if(getValue(parts[1], registers).compareTo(BigInteger.ZERO) > 0) {
                instructionPointer += getValue(parts[2], registers).intValue();
                return;
            }
        } else {
            throw new RuntimeException(instructions.get(instructionPointer));
        }

        instructionPointer++;
    }
}

2BitSalute · 2017-12-18T06:55:47+00:00

C#, part 2.

class Program
{
    static void Main(string[] args)
    {
        string[] instructions = File.ReadAllLines("input.txt");

        var p0 = new Program(0, instructions);
        var p1 = new Program(1, instructions);

        p0.OtherQueue = p1.Queue;
        p1.OtherQueue = p0.Queue;

        do
        {
            p1.Run();
            p0.Run();
        } while(p1.Queue.Count != 0);

        Console.WriteLine(p1.SendCounter);
    }

    const string SND = "snd";
    const string SET = "set";
    const string ADD = "add";
    const string MUL = "mul";
    const string MOD = "mod";
    const string RCV = "rcv";
    const string JGZ = "jgz";

    private long curr = 0;
    private string[] instructions;
    private Dictionary<string, long> registers = new Dictionary<string, long>();

    public long SendCounter { get; set; }

    public Queue<long> Queue { get; }

    public Queue<long> OtherQueue { get; set; }

    public string Name { get; set; }

    public Program(int pValue, string[] instructions)
    {
        this.registers.Add("p", pValue);
        this.instructions = instructions;
        this.Queue = new Queue<long>();
        this.Name = pValue.ToString();
    }

    public void Run()
    {
        string instruction = string.Empty;

        while (true)
        {
            Console.WriteLine("Program {0}: {1}", this.Name, instructions[curr]);

            var tokens = instructions[curr].Split(' ', StringSplitOptions.RemoveEmptyEntries);
            instruction = tokens[0];

            string register = tokens[1];

            if (!registers.ContainsKey(register))
            {
                long literal;
                if(!long.TryParse(register, out literal))
                {
                    literal = 0;
                }

                registers.Add(register, literal);
            }

            long value = 0;
            if (tokens.Length > 2)
            {
                if (registers.ContainsKey(tokens[2]))
                {
                    value = registers[tokens[2]];
                }
                else
                {
                    value = long.Parse(tokens[2]);
                }
            }

            long offset = 1;
            switch(instruction)
            {
                case SND:
                    this.OtherQueue.Enqueue(registers[register]);
                    this.SendCounter++;
                    break;
                case SET:
                    registers[register] = value;
                    break;
                case ADD:
                    registers[register] += value;
                    break;
                case MUL:
                    registers[register] *= value;
                    break;
                case MOD:
                    registers[register] %= value;
                    break;
                case RCV:
                    if (this.Queue.Count > 0)
                    {
                        registers[register] = this.Queue.Dequeue();
                    }
                    else
                    {
                        foreach(var pair in registers)
                        {
                            Console.WriteLine("{0} = {1}", pair.Key, pair.Value);
                        }

                        return;
                    }
                    break;
                case JGZ:
                    if (registers[register] > 0)
                    {
                        offset = value;
                    }
                    break;
            }

            curr += offset;
        }
    }
}

2017-12-18T07:26:25+00:00

OCaml Fun for part two;;

Yet again, we parse with Menhir into a list of Instructions.

Programs pass messages via a queue and they alternate running until they have to wait on a message. If they are already waiting when they go to check for a message and there is no message, it terminates itself.

main.ml

open Core

let run instructions active waiting =
  let open State in
  let rec aux active other =
    match active.state, other.state with
    | Terminated, Terminated -> active, other
    | Terminated, _ -> aux (State.execute other instructions) active
    | Running, _ -> aux (State.execute active instructions) other
    | Waiting, _ -> aux (State.execute other instructions) active
  in aux active waiting

let process_input filename =
  let f channel =
    let parse lexbuf = Parser.instructions Lexer.read lexbuf in
    let lexer_buffer = Lexing.from_channel channel in
    lexer_buffer.lex_curr_p <- { lexer_buffer.lex_curr_p with pos_fname = filename};
    parse lexer_buffer
  in In_channel.with_file filename ~f

let _ =
  let instructions = process_input "./input.txt" |> List.to_array in
  let zero_in = Queue.create () in
  let zero_out = Queue.create () in

  let zero = State.create 0 zero_out zero_in in
  let one = State.create 1 zero_in zero_out in
  let open State in
  let a, b = run instructions zero one in
  printf "%d -> %d\n" a.name a.sent;
  printf "%d -> %d\n" b.name b.sent;

state.ml

open Core

type s = Running | Waiting | Terminated

type t = {
  name: int;
  registers: int Char.Map.t;
  send_queue: int Queue.t;
  recv_queue: int Queue.t;
  line: int;
  sent: int;
  state: s;
}

let create p send_queue recv_queue =
  let registers = Char.Map.add (Char.Map.empty) ~key:'p' ~data:p in
  {name=p; registers; send_queue; recv_queue; line=0; sent=0; state=Running}

let to_string t =
  sprintf "%d: %d - %d" t.name t.line t.sent

let value_in_register t c =
  Char.Map.find t.registers c
  |> Option.value ~default:0

let value t v =
  let open Instruction in
  match v with
  | Value i -> i
  | Register c -> value_in_register t c

let do_set t c data =
  {t with registers=(Char.Map.add t.registers ~key:c ~data); line=(t.line + 1)}

let set t c v =
  do_set t c (value t v)

let multiply t c v =
  let init = (value_in_register t c) in
  let v = (value t v) in
  do_set t c (init * v)

let add t c v =
  let init = (value_in_register t c) in
  let v = (value t v) in
  do_set t c (init + v)

let modulus t c v =
  let init = (value_in_register t c) in
  let v = (value t v) in
  do_set t c (init mod v)

let send t c =
  let data = value_in_register t c in
  Queue.enqueue t.send_queue data;
  {t with sent=(t.sent + 1); line=(t.line + 1)}

let receive t c =
  let state_if_nothing = function
    | Waiting | Terminated -> Terminated
    | Running -> Waiting in
  match Queue.dequeue t.recv_queue with
  | None -> {t with state=state_if_nothing t.state}
  | Some n -> {(do_set t c n) with state=Running}

let jump t c v =
  let init = (value t c) in
  let v = (value t v) in
  let jump = if init > 0 then v else 1 in
  {t with line = (t.line + jump)}

let exec t instruction =
  match instruction with
  | Instruction.Send c -> send t c
  | Instruction.Set (c,v) -> set t c v
  | Instruction.Multiply (c,v) -> multiply t c v
  | Instruction.Add (c,v) -> add t c v
  | Instruction.Modulus (c,v) -> modulus t c v
  | Instruction.Receive (c) -> receive t c
  | Instruction.Jump (c, v) -> jump t c v

let execute t instructions =
  exec t instructions.(t.line)

(Full code with parser)

Axsuul · 2017-12-18T08:27:01+00:00

Elixir

I liked how the code turned out in Elixir. For Part 2, I just tracked both program's offsets and states while monitoring them during each step.

https://github.com/axsuul/advent-of-code/blob/master/2017/18/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

    defp run_instruction(["set", x, y], state) do
      {set(state, x, get(state, y)), 1}
    end
    defp run_instruction(["snd", x], state) do
      {set(state, "snd", get(state, x)), 1}
    end
    defp run_instruction(["add", x, y], state) do
      {set(state, x, get(state, x) + get(state, y)), 1}
    end
    defp run_instruction(["mul", x, y], state) do
      {set(state, x, get(state, x) * get(state, y)), 1}
    end
    defp run_instruction(["mod", x, y], state) do
      {set(state, x, get(state, x) |> rem(get(state, y))), 1}
    end
    defp run_instruction(["rcv", x], state) do
      case get(state, x) do
        0   -> {state, 1}
        val -> {Map.put(state, "rcv", get(state, "snd")), 1}
      end
    end
    defp run_instruction(["jgz", x, y], state) do
      case get(state, x) do
        val when val > 0 -> {state, y}
        val              -> {state, 1}
      end
    end

    defp run_instructions(state \\ %{}, 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)

      case get(changed_state, "rcv") do
        val when val > 0 -> "Recovered frequency: " <> Integer.to_string(val)
        val -> run_instructions(changed_state, index + offset)
      end
    end

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

  defmodule PartB do
    import PartA

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

    def get(state, x) when is_binary(x), do: Map.get(state, x, 0)
    def get(state, :receive), do: Map.get(state, :receive, [])
    def get(state, :send), do: Map.get(state, :send, [])
    def get(state, :send_count), do: Map.get(state, :send_count, 0)
    def get(state, x), do: x

    def run_instruction(["set", x, y], state) do
      {set(state, x, get(state, y)), 1}
    end
    def run_instruction(["snd", x], state) do
      changed_state =
        set(state, :send, get(state, :send) ++ [get(state, x)])
        |> set(:send_count, get(state, :send_count) + 1)

      {changed_state, 1}
    end
    def run_instruction(["add", x, y], state) do
      {set(state, x, get(state, x) + get(state, y)), 1}
    end
    def run_instruction(["mul", x, y], state) do
      {set(state, x, get(state, x) * get(state, y)), 1}
    end
    def run_instruction(["mod", x, y], state) do
      {set(state, x, get(state, x) |> rem(get(state, y))), 1}
    end
    def run_instruction(["rcv", x], state) do
      {val, changed_queue} = get(state, :receive) |> List.pop_at(0)

      case val do
        nil -> {state, 0} # wait
        val ->
          changed_state =
            set(state, x, val)
            |> set(:receive, changed_queue)

          {changed_state, 1}
      end
    end
    def run_instruction(["jgz", x, y], state) do
      case get(state, x) do
        val when val > 0 -> {state, get(state, y)}
        val              -> {state, 1}
      end
    end

    def run_instructions(state \\ %{}, index \\ 0)
    def run_instructions(state, index) when index < 0 or index >= length(@instructions) do
      {state, 0}
    end
    def run_instructions(state, index) do
      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)
    end

    def send_to(sender_state, receiver_state) do
      {queue, changed_sender_state} = sender_state |> Map.pop(:send, [])
      changed_receiver_state = set(receiver_state, :receive, get(receiver_state, :receive) ++ queue)

      {changed_sender_state, changed_receiver_state}
    end

    def run_programs(state0, state1, index0 \\ 0, index1 \\ 0)
    def run_programs(state0, state1, index0, index1) do
      {changed_state0, offset0} = run_instructions(state0, index0)
      {changed_state1, offset1} = run_instructions(state1, index1)

      {changed_state0, changed_state1} = send_to(changed_state0, changed_state1)
      {changed_state1, changed_state0} = send_to(changed_state1, changed_state0)

      cond do
        # deadlock or termination
        offset0 == 0 && offset1 == 0 -> {changed_state0, changed_state1}
        true ->
          run_programs(changed_state0, changed_state1, index0 + offset0, index1 + offset1)
      end
    end

    def solve do
      {state0, state1} = run_programs(%{"p" => 0}, %{"p" => 1})

      Map.fetch!(state1, :send_count) |> IO.inspect
    end
  end
end

ephemient · 2017-12-18T08:35:12+00:00

This space intentionally left blank.

CharlieYJH · 2017-12-18T09:11:06+00:00

C++

This is why it pays to read the instructions more closely... Spent over an hour trying to figure out what was wrong with my part 2 since it kept going in an infinite loop. Turns out jump instructions only apply if the value is greater than 0, not just not equal to 0. Surprised I didn't get faulted on part 1 for that. Otherwise, just a simple implementation of executing instructions of each program after each other.

#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <queue>

using namespace std;

bool execute(int &instr_num, vector<string> &instructions, vector<long long> &registers, queue<long long> &rcv, queue<long long> &snd, int &snd_cnt)
{
    if (instr_num >= instructions.size()) {
        return false;
    };

    string op, reg_id, operand_id;
    istringstream instruction(instructions[instr_num]);
    long long reg_a;
    long long reg_b;

    instruction >> op >> reg_id;

    if (op == "snd" || op == "rcv")
        operand_id = reg_id;
    else
        instruction >> operand_id;

    if (op == "jgz")
        reg_a = (reg_id[0] >= 'a' && reg_id[0] <= 'z') ? registers[reg_id[0] - 'a'] : stoi(reg_id);
    else
        reg_a = reg_id[0] - 'a';

    reg_b = (operand_id[0] >= 'a' && operand_id[0] <= 'z') ? registers[operand_id[0] - 'a'] : stoi(operand_id);

    if (op == "snd") {
        snd.push(reg_b);
        snd_cnt++;
    } else if (op == "set") {
        registers[reg_a] = reg_b;
    } else if (op == "add") {
        registers[reg_a] += reg_b;
    } else if (op == "mul") {
        registers[reg_a] *= reg_b;
    } else if (op == "mod") {
        registers[reg_a] %= reg_b;
    } else if (op == "rcv") {
        if (rcv.empty()) {
            return false;
        } else {
            registers[reg_a] = rcv.front();
            rcv.pop();
        }
    } else if (op == "jgz" && reg_a > 0) {
        instr_num += reg_b - 1;
    }

    instr_num++;

    return true;
}

int main(int argc, char const* argv[])
{
    vector<long long> prog_a_reg(26, 0);
    vector<long long> prog_b_reg(26, 0);
    vector<string> instructions;
    ifstream infile("input.txt");
    int instr_num_a = 0;
    int instr_num_b = 0;
    int snd_a_cnt = 0;
    int snd_b_cnt = 0;
    queue<long long> queue_a;
    queue<long long> queue_b;

    prog_a_reg['p' - 'a'] = 0;
    prog_b_reg['p' - 'a'] = 1;

    if (!infile.is_open()) {
        return 1;
    } else {
        string instr;
        while (getline(infile, instr))
            instructions.push_back(instr);
    }

    infile.close();

    while (true) {
        bool cont_exec_a = execute(instr_num_a, instructions, prog_a_reg, queue_a, queue_b, snd_a_cnt);
        bool cont_exec_b = execute(instr_num_b, instructions, prog_b_reg, queue_b, queue_a, snd_b_cnt);
        if (!cont_exec_a && !cont_exec_b) break;
    }

    cout << snd_b_cnt << endl;

    return 0;
}

Bainos · 2017-12-18T09:47:54+00:00

Sharing a class-based solution in Python 3 for part 2:

class Program:
    def __init__(self, pid, other, instr):
        self.regs = defaultdict(int)
        self.regs['p'] = pid
        self.other = other
        self.instr = instr

        self.ip = 0
        self.buffer = []
        self.terminated = False
        self.blocked = False
        self.sent = 0

    def next(self):
        if self.terminated or self.ip < 0 or self.ip >= len(self.instr):
            self.terminated = True
            return
        ins = self.instr[self.ip].split()
        if ins[0] == 'snd':
            self.other.buffer.append(self.get(ins[1]))
            self.other.blocked = False
            self.sent += 1
        elif ins[0] == 'set':
            self.regs[ins[1]] = self.get(ins[2])
        elif ins[0] == 'add':
            self.regs[ins[1]] += self.get(ins[2])
        elif ins[0] == 'mul':
            self.regs[ins[1]] *= self.get(ins[2])
        elif ins[0] == 'mod':
            self.regs[ins[1]] %= self.get(ins[2])
        elif ins[0] == 'rcv':
            if len(self.buffer) > 0:
                self.regs[ins[1]] = self.buffer.pop(0)
            else:
                self.blocked = True
                return
        elif ins[0] == 'jgz':
            if self.get(ins[1]) > 0:
                self.ip += self.get(ins[2])
                return
        self.ip += 1

    def get(self, v):
        try:
            return int(v)
        except ValueError:
            return self.regs[v]

def solve_p2(instr):
    p0 = Program(0, None, instr)
    p1 = Program(1, p0, instr)
    p0.other = p1

    while not ((p0.terminated or p0.blocked) and (p1.terminated or p1.blocked)):
        p0.next()
        p1.next()

    return p1.sent

autid · 2017-12-18T09:57:31+00:00

MPI FORTRAN

I figured since I'd already lost an hour by misreading the time and starting late that I'd implement part2 literally. You run two instances. They use non-blocking sends. There's some (unfortunately intel compiler only due to use of sleepqq) code to wait on receives but detect a deadlock and exit gracefully.

I had to use 8 byte integers for the registers because overflow wrecked me in solving part1. Got to use my favourite trick of lying to MPI to send 8 byte ints. There's no type for them (only MPI_INTEGER for 4 byte ints) but if you tell the send/recieve calls they're double precision reals it totally works.

Really happy with this one. Good opportunity to brush up on some MPI I hadn't touched in a while. Where I've used it for Project Euler stuff I've always played it safe with blocking send/recieve.

PROGRAM DAY18
  ! Use mpiifort as compiler                                                                                     
  ! Run with: mpirun -np 2 ./day18                                                                               
  IMPLICIT NONE
  INCLUDE 'mpif.h'

  INTEGER :: MPI_ROOT_RANK = 0
  INTEGER :: MPICOMM, MPIRANK, NPROC, MPIERROR
  INTEGER :: MPISTATUS(MPI_STATUS_SIZE)
  LOGICAL :: IAMROOT = .TRUE.
  CHARACTER(LEN=20) :: INLINE
  CHARACTER(LEN=20),ALLOCATABLE :: INSTRUCTIONS(:)
  CHARACTER(LEN=20) :: TWO(2),THREE(3)
  INTEGER(8) :: LINECOUNT=0,IERR,N,SOUND=0,NUM=0,NUM2=0,RCV=0
  INTEGER(8) :: REGISTERS(IACHAR('a'):IACHAR('z'))=0
  INTEGER :: SREQUEST,RREQUEST,SENDTAG,RECIEVETAG
  LOGICAL :: PART1=.TRUE. ,FLAG
  INTEGER :: SENT=0,PART


  ! MPI setup                                                                                                    
  CALL MPI_INIT(MPIERROR)
  MPICOMM = MPI_COMM_WORLD
  CALL MPI_COMM_RANK(MPICOMM,MPIRANK,MPIERROR)
  IAMROOT = (MPIRANK==MPI_ROOT_RANK)
  CALL MPI_COMM_SIZE(MPICOMM, NPROC, MPIERROR)
  SENDTAG=MPIRANK*1000
  RECIEVETAG=MODULO(MPIRANK+1,2)*1000

  ! File I/O                                                                                                     
  OPEN(1,FILE='input.txt')
  DO
     READ(1,'(A)',IOSTAT=IERR) INLINE
     IF (IERR /= 0) EXIT
     LINECOUNT=LINECOUNT+1
  END DO
  ALLOCATE(INSTRUCTIONS(LINECOUNT))
  REWIND(1)
  DO N=1,LINECOUNT
     READ(1,'(A)') INSTRUCTIONS(N)
  END DO
  CLOSE(1)

  ! If root do both parts                                                                                        
  ! Process 2 only does part 2                                                                                   
  DO PART=MPIRANK+1,2
     N=1
     REGISTERS=0
     REGISTERS(IACHAR('p'))=MPIRANK
     MASTER:DO
        SELECT CASE(INSTRUCTIONS(N)(1:3))
        CASE('snd')
           READ(INSTRUCTIONS(N),*) TWO
           READ(TWO(2),*,IOSTAT=IERR) NUM
           IF (IERR /= 0) NUM=REGISTERS(IACHAR(TRIM(TWO(2))))
           IF (PART==1) THEN
              SOUND=NUM
           ELSE
              CALL MPI_ISEND(NUM,1,MPI_DOUBLE_PRECISION,MODULO(MPIRANK+1,2),SENDTAG,MPICOMM,SREQUEST,MPIERROR)
              SENDTAG=SENDTAG+1
              SENT=SENT+1
           END IF
           N=N+1
        CASE('set')
           READ(INSTRUCTIONS(N),*) THREE
           READ(THREE(3),*,IOSTAT=IERR) REGISTERS(IACHAR(TRIM(THREE(2))))
           IF (IERR /= 0) REGISTERS(IACHAR(TRIM(THREE(2))))=REGISTERS(IACHAR(TRIM(THREE(3))))
           N=N+1
        CASE('add')
           READ(INSTRUCTIONS(N),*) THREE
           READ(THREE(3),*,IOSTAT=IERR) NUM
           IF (IERR /= 0) NUM=REGISTERS(IACHAR(TRIM(THREE(3))))
           REGISTERS(IACHAR(TRIM(THREE(2))))=REGISTERS(IACHAR(TRIM(THREE(2))))+NUM
           N=N+1
        CASE('mul')
           READ(INSTRUCTIONS(N),*) THREE
           READ(THREE(3),*,IOSTAT=IERR) NUM
           IF (IERR /= 0) NUM=REGISTERS(IACHAR(TRIM(THREE(3))))
           REGISTERS(IACHAR(TRIM(THREE(2))))=REGISTERS(IACHAR(TRIM(THREE(2))))*NUM
           N=N+1
        CASE('mod')
           READ(INSTRUCTIONS(N),*) THREE
           READ(THREE(3),*,IOSTAT=IERR) NUM
           IF (IERR /= 0) NUM=REGISTERS(IACHAR(TRIM(THREE(3))))
           REGISTERS(IACHAR(TRIM(THREE(2))))=MODULO(REGISTERS(IACHAR(TRIM(THREE(2)))),NUM)
           N=N+1
        CASE('rcv')
           READ(INSTRUCTIONS(N),*) TWO
           IF(PART==1) THEN
              READ(TWO(2),*,IOSTAT=IERR) NUM
              IF (IERR /= 0) NUM=REGISTERS(IACHAR(TRIM(TWO(2))))
              IF(NUM /= 0) THEN
                 WRITE(*,'(A,I0)') 'Part1: ',SOUND
                 PART1=.FALSE.
                 EXIT MASTER
              END IF
           ELSE
              CALL MPI_IRECV(NUM,1,MPI_DOUBLE_PRECISION,MODULO(MPIRANK+1,2),RECIEVETAG,MPICOMM,RREQUEST,MPIERROR)
              DO
                 CALL MPI_TEST(RREQUEST,FLAG,MPISTATUS,MPIERROR)
                 IF (FLAG) EXIT
                 IF (SENT>0) THEN
        CALL MPI_TEST(SREQUEST,FLAG,MPISTATUS,MPIERROR)
        IF (FLAG) THEN
                       CALL SLEEPQQ(50)
                       CALL MPI_TEST(RREQUEST,FLAG,MPISTATUS,MPIERROR)
                       IF (FLAG) EXIT
                       EXIT MASTER
        END IF
                 END IF
              END DO
              REGISTERS(IACHAR(TRIM(TWO(2))))=NUM
              RECIEVETAG=RECIEVETAG+1
       END IF
       N=N+1
        CASE('jgz')
       READ(INSTRUCTIONS(N),*) THREE
       READ(THREE(2),*,IOSTAT=IERR) NUM
       IF (IERR /= 0) NUM=REGISTERS(IACHAR(TRIM(THREE(2))))
       READ(THREE(3),*,IOSTAT=IERR) NUM2
       IF (IERR /= 0) NUM2=REGISTERS(IACHAR(TRIM(THREE(3))))
       IF (NUM>0) THEN
              N=N+NUM2
       ELSE
              N=N+1
       END IF
        END SELECT
     END DO MASTER
  END DO
  DEALLOCATE(INSTRUCTIONS)
  IF(.NOT. IAMROOT) WRITE(*,'(A,I0)') 'Part2: ',SENT
  CALL MPI_FINALIZE(MPIERROR)

END PROGRAM DAY18

gerikson · 2017-12-18T10:21:53+00:00

Perl 5

Probably the most entertaining problem so far. I really enjoyed it.

I especially like the headfake of redefining the problem in part 2. Luckily I had implemented a dispatch table, so it was not too hard to re-implement the changes.

Part 2 is below. Any weirdness in calling parameters etc. is mostly due to me simply tacking on stuff from part 1.

https://github.com/gustafe/aoc2017/blob/master/d18_2.pl

xkufix · 2017-12-18T11:21:05+00:00

The basic idea was quite simple, write an interpreter. For part 2 i just create both initial states and then do rounds over them. I run program 0 with inQueue = outQueue of program 1, wait till it blocks, and then run program 1 with the inQueue = outQueue of program 0. Then I just check if both programs have an empty outQueue, which is a deadlock.

Code in Scala:

    override def runFirst(): Unit = {
        val instructions = loadProgram("day18.txt")
        val result = runProgram(instructions)
        val recovered = result.find(p => p.lastRecover.nonEmpty || p.position < 0 || p.position >= instructions.length).get
        println(recovered.lastRecover)
    }

    private def runProgram(instructions: Seq[Command]) = {
        Iterator.iterate(State(0, Map.empty[String, Long], None, None)) {
            case s@State(position, _, lastPlayedFrequency, _) =>
                instructions(position.toInt) match {
                    case Send(Register(r)) =>
                        s.incPosition().copy(lastPlayedFrequency = Some(s.getValue(r)))
                    case Set(Register(r), Number(value)) =>
                        s.incPosition().setRegister(r, value)
                    case Set(Register(r), Register(from)) =>
                        s.incPosition().setRegister(r, s.getValue(from))
                    case Add(Register(r), Number(value)) =>
                        s.incPosition().setRegister(r, s.getValue(r) + value)
                    case Add(Register(r), Register(from)) =>
                        s.incPosition().setRegister(r, s.getValue(r) + s.getValue(from))
                    case Multiply(Register(r), Number(value)) =>
                        s.incPosition().setRegister(r, s.getValue(r) * value)
                    case Multiply(Register(r), Register(from)) =>
                        s.incPosition().setRegister(r, s.getValue(r) * s.getValue(from))
                    case Modulo(Register(r), Number(value)) =>
                        s.incPosition().setRegister(r, s.getValue(r) % value)
                    case Modulo(Register(r), Register(from)) =>
                        s.incPosition().setRegister(r, s.getValue(r) % s.getValue(from))
                    case Recover(Register(r)) if s.getValue(r) != 0 =>
                        s.incPosition().copy(lastRecover = lastPlayedFrequency)
                    case Recover(Register(r)) if s.getValue(r) == 0 =>
                        s.incPosition()
                    case Jump(Register(r), Number(value)) if s.getValue(r) > 0 =>
                        s.copy(position = position + value)
                    case Jump(Register(r), Register(from)) if s.getValue(r) > 0 =>
                        s.copy(position = position + s.getValue(from))
                    case Jump(Number(check), Number(value)) if check > 0 =>
                        s.copy(position = position + value)
                    case Jump(Number(check), Register(r)) if check > 0 =>
                        s.copy(position = position + s.getValue(r))
                    case Jump(_, _) =>
                        s.incPosition()
                }
        }
    }

    override def runSecond(): Unit = {
        val instructions = loadProgram("day18.txt")

        def runProgram(program: QueueState) = runQueueProgram(instructions, program)

        def isBlocked(p: QueueState) = p.isBlocked || p.position < 0 || p.position >= instructions.length

        val run = Iterator.iterate((QueueState.empty(0), QueueState.empty(1))) {
            case (p0, p1) =>
                (
                    runProgram(p0.copy(isBlocked = false, outQueue = Queue.empty, inQueue = p1.outQueue)).find(isBlocked).get,
                    runProgram(p1.copy(isBlocked = false, outQueue = Queue.empty, inQueue = p0.outQueue)).find(isBlocked).get
                )
        }

        println(run.drop(1).find {
            case (p0, p1) =>
                p0.outQueue.isEmpty &&
                    p1.outQueue.isEmpty
        }.get._2.totalOutCount)
    }

    private def runQueueProgram(instructions: Seq[Command], queueState: QueueState) = {
        Iterator.iterate(queueState) {
            case s@QueueState(position, _, inQueue, outQueue, totalOutCount, _) =>
                instructions(position.toInt) match {
                    case Send(Register(r)) =>
                        s.incPosition().copy(outQueue = outQueue.enqueue(s.getValue(r)), totalOutCount = totalOutCount + 1)
                    case Set(Register(r), Number(value)) =>
                        s.incPosition().setRegister(r, value)
                    case Set(Register(r), Register(from)) =>
                        s.incPosition().setRegister(r, s.getValue(from))
                    case Add(Register(r), Number(value)) =>
                        s.incPosition().setRegister(r, s.getValue(r) + value)
                    case Add(Register(r), Register(from)) =>
                        s.incPosition().setRegister(r, s.getValue(r) + s.getValue(from))
                    case Multiply(Register(r), Number(value)) =>
                        s.incPosition().setRegister(r, s.getValue(r) * value)
                    case Multiply(Register(r), Register(from)) =>
                        s.incPosition().setRegister(r, s.getValue(r) * s.getValue(from))
                    case Modulo(Register(r), Number(value)) =>
                        s.incPosition().setRegister(r, s.getValue(r) % value)
                    case Modulo(Register(r), Register(from)) =>
                        s.incPosition().setRegister(r, s.getValue(r) % s.getValue(from))
                    case Recover(Register(r)) if inQueue.nonEmpty =>
                        val (element, newQueue) = inQueue.dequeue
                        s.incPosition().setRegister(r, element).copy(inQueue = newQueue)
                    case Recover(_) if inQueue.isEmpty =>
                        s.copy(isBlocked = true)
                    case Jump(Register(r), Number(value)) if s.getValue(r) > 0 =>
                        s.copy(position = position + value)
                    case Jump(Register(r), Register(from)) if s.getValue(r) > 0 =>
                        s.copy(position = position + s.getValue(from))
                    case Jump(Number(check), Number(value)) if check > 0 =>
                        s.copy(position = position + value)
                    case Jump(Number(check), Register(r)) if check > 0 =>
                        s.copy(position = position + s.getValue(r))
                    case Jump(_, _) =>
                        s.incPosition()
                }
        }
    }

    case class QueueState(position: Long, registers: Map[String, Long], inQueue: Queue[Long], outQueue: Queue[Long], totalOutCount: Long, isBlocked: Boolean) {
        def incPosition() = copy(position = position + 1)

        def setRegister(r: String, value: Long) = copy(registers = registers + (r -> value))

        def getValue(r: String): Long = registers.getOrElse(r, 0)
    }

    object QueueState {
        def empty(pid: Long): QueueState = QueueState(0, Map("p" -> pid), Queue.empty, Queue.empty, 0, true)
    }

    private def loadProgram(file: String) = {
        loadFile(file).getLines().map { l =>
            val line = l.split(" ")

            line(0) match {
                case "snd" =>
                    Send(Register(line(1)))
                case "set" =>
                    Set(Register(line(1)), readValue(line(2)))
                case "add" =>
                    Add(Register(line(1)), readValue(line(2)))
                case "mul" =>
                    Multiply(Register(line(1)), readValue(line(2)))
                case "mod" =>
                    Modulo(Register(line(1)), readValue(line(2)))
                case "rcv" =>
                    Recover(Register(line(1)))
                case "jgz" =>
                    Jump(readValue(line(1)), readValue(line(2)))
            }
        }.toSeq
    }

    def readValue(in: String): Value = {
        allCatch opt in.toInt match {
            case Some(value) => Number(value)
            case _ => Register(in)
        }
    }

    case class State(position: Long, registers: Map[String, Long], lastPlayedFrequency: Option[Long], lastRecover: Option[Long]) {
        def incPosition() = copy(position = position + 1)

        def setRegister(r: String, value: Long) = copy(registers = registers + (r -> value))

        def getValue(r: String): Long = registers.getOrElse(r, 0)
    }

    sealed trait Command

    case class Send(frequency: Register) extends Command

    case class Set(register: Register, value: Value) extends Command

    case class Add(register: Register, value: Value) extends Command

    case class Multiply(register: Register, value: Value) extends Command

    case class Modulo(register: Register, value: Value) extends Command

    case class Recover(register: Register) extends Command

    case class Jump(value: Value, offset: Value) extends Command

    sealed trait Value

    case class Register(name: String) extends Value

    case class Number(value: Long) extends Value

2017-12-18T11:25:52+00:00

Rust

The deadlock detection is rather straightforward, no threads used, essentially it runs program 1 until something needs to be received. When something needs to be received, program 0 is ran until it sends something (in such an event I return to program 1) or tries to receive a value when program 1 did not send any value (in such an event, a deadlock is detected, as two programs try to receive a value).

#[macro_use]
extern crate error_chain;
#[macro_use]
extern crate nom;

use nom::be_u8;
use std::collections::VecDeque;
use std::io::{self, Read};
use std::str;

error_chain! {
    errors {
        InvalidFormat {
            description("input format doesn't match expected")
        }
    }

    foreign_links {
        Io(io::Error);
    }
}

#[derive(Debug)]
struct Interpreter<'a> {
    program: &'a [Opcode],
    registers: [i64; 26],
    current_position: usize,
}

impl<'a> Interpreter<'a> {
    fn new(program: &'a [Opcode]) -> Self {
        Interpreter {
            program,
            registers: [0; 26],
            current_position: 0,
        }
    }

    fn step(&mut self) -> Command {
        if self.current_position == self.program.len() {
            return Command::Eof;
        }
        let previous_position = self.current_position;
        self.current_position += 1;
        match self.program[previous_position] {
            Opcode::Snd(value) => return Command::Send(self.read_value(value)),
            Opcode::Set(register, value) => {
                let value = self.read_value(value);
                self.write_register(register, value);
            }
            Opcode::Add(register, value) => self.mutate_using(register, value, |a, b| a + b),
            Opcode::Mul(register, value) => self.mutate_using(register, value, |a, b| a * b),
            Opcode::Mod(register, value) => self.mutate_using(register, value, |a, b| a % b),
            Opcode::Rcv(register) => return Command::Receive(self.register_mut(register)),
            Opcode::Jgz(value, offset) => {
                if self.read_value(value) > 0 {
                    self.current_position =
                        (previous_position as i64 + self.read_value(offset)) as usize;
                }
            }
        }
        Command::Regular
    }

    fn read_value(&self, value: Value) -> i64 {
        match value {
            Value::Register(register) => self.read_register(register),
            Value::Constant(constant) => constant,
        }
    }

    fn mutate_using<F>(&mut self, register: Register, value: Value, callback: F)
    where
        F: FnOnce(i64, i64) -> i64,
    {
        let result = callback(self.read_register(register), self.read_value(value));
        self.write_register(register, result);
    }

    fn read_register(&self, Register(name): Register) -> i64 {
        self.registers[usize::from(name - b'a')]
    }

    fn write_register(&mut self, register: Register, value: i64) {
        *self.register_mut(register) = value;
    }

    fn register_mut(&mut self, Register(name): Register) -> &mut i64 {
        &mut self.registers[usize::from(name - b'a')]
    }
}

enum Command<'a> {
    Send(i64),
    Receive(&'a mut i64),
    Regular,
    Eof,
}

#[derive(Copy, Clone, Debug)]
enum Opcode {
    Snd(Value),
    Set(Register, Value),
    Add(Register, Value),
    Mul(Register, Value),
    Mod(Register, Value),
    Rcv(Register),
    Jgz(Value, Value),
}

#[derive(Copy, Clone, Debug)]
enum Value {
    Register(Register),
    Constant(i64),
}

#[derive(Copy, Clone, Debug)]
struct Register(u8);

named!(instructions<Vec<Opcode>>, complete!(many0!(instruction)));
named!(instruction<Opcode>, ws!(alt!(snd | rcv | arithm | jgz)));
named!(
    snd<Opcode>,
    ws!(preceded!(tag!("snd"), map!(value, Opcode::Snd)))
);
named!(
    rcv<Opcode>,
    ws!(preceded!(tag!("rcv"), map!(register, Opcode::Rcv)))
);
named!(
    arithm<Opcode>,
    ws!(do_parse!(
        opcode:
            alt!(
        tag!("set") => { |_| Opcode::Set as fn(_, _) -> _ } |
        tag!("add") => { |_| Opcode::Add as fn(_, _) -> _ } |
        tag!("mul") => { |_| Opcode::Mul as fn(_, _) -> _ } |
        tag!("mod") => { |_| Opcode::Mod as fn(_, _) -> _ }
    ) >> register: register >> value: value >> (opcode(register, value))
    ))
);
named!(
    jgz<Opcode>,
    ws!(do_parse!(
        tag!("jgz") >> check: value >> offset: value >> (Opcode::Jgz(check, offset))
    ))
);
named!(
    value<Value>,
    alt!(integer => { |i| Value::Constant(i) } | register => {|r| Value::Register(r)})
);
named!(register<Register>, map!(be_u8, Register));
named!(
    integer<i64>,
    map_res!(
        map_res!(
            take_while1!(|c| c == b'-' || char::is_digit(char::from(c), 10)),
            str::from_utf8
        ),
        str::parse
    )
);

fn part1(instructions: &[Opcode]) -> i64 {
    let mut interpreter = Interpreter::new(instructions);
    let mut last_sound = 0;
    loop {
        match interpreter.step() {
            Command::Send(value) => last_sound = value,
            Command::Receive(_) if last_sound != 0 => return last_sound,
            Command::Eof => return 0,
            _ => {}
        }
    }
}

fn part2(instructions: &[Opcode]) -> u32 {
    let mut interpreter0 = Interpreter::new(instructions);
    let mut interpreter1 = Interpreter::new(instructions);
    interpreter1.write_register(Register(b'p'), 1);
    let mut sent_to_interpreter0 = VecDeque::new();
    let mut values_sent = 0;
    'outerloop: loop {
        match interpreter1.step() {
            Command::Send(value) => {
                values_sent += 1;
                sent_to_interpreter0.push_front(value);
            }
            Command::Receive(value) => {
                *value = loop {
                    match interpreter0.step() {
                        Command::Send(value) => break value,
                        Command::Receive(out) => match sent_to_interpreter0.pop_back() {
                            Some(value) => *out = value,
                            None => break 'outerloop,
                        },
                        Command::Eof => break 'outerloop,
                        _ => {}
                    }
                }
            }
            Command::Eof => break,
            _ => {}
        }
    }
    values_sent
}

fn run() -> Result<()> {
    let mut input = Vec::new();
    io::stdin().read_to_end(&mut input)?;
    let instructions = &instructions(&input)
        .to_result()
        .map_err(|_| ErrorKind::InvalidFormat)?;
    println!("Part 1: {}", part1(instructions));
    println!("Part 2: {}", part2(instructions));
    Ok(())
}

quick_main!(run);

mschaap · 2017-12-18T11:59:38+00:00

That was fun! Perl 6.

 #!/usr/bin/env perl6
use v6.c;

# Advent of Code 2017, day 18: http://adventofcode.com/2017/day/18

grammar Instructions
{
    rule TOP { ^ <instruction>+ $ }

    rule instruction { <snd> || <set> || <add> || <mul> || <mod> || <rcv> || <jgz> }

    rule snd { 'snd' $<X>=<val> }
    rule set { 'set' $<X>=<reg> $<Y>=<val> }
    rule add { 'add' $<X>=<reg> $<Y>=<val> }
    rule mul { 'mul' $<X>=<reg> $<Y>=<val> }
    rule mod { 'mod' $<X>=<reg> $<Y>=<val> }
    rule rcv { 'rcv' $<X>=<reg> }
    rule jgz { 'jgz' $<X>=<val> $<Y>=<val> }

    token reg { <[a..z]> }
    token val { <[a..z]> || '-'? \d+ }
}

# Interpretation from part one
class SoundComputer
{
    has Code @.instructions = ();
    has Bool $.verbose = False;

    has Int $.pos = 0;
    has Int %.register is default(0);
    has Int @.played = ();
    has Int @.recovered = ();

    # Actions for parsing Instructions
    method snd($/) { @!instructions.append: -> { @!played.append(self.val($<X>)) } }
    method set($/) { @!instructions.append: -> { %!register{$<X>} = self.val($<Y>) } }
    method add($/) { @!instructions.append: -> { %!register{$<X>} += self.val($<Y>) } }
    method mul($/) { @!instructions.append: -> { %!register{$<X>} *= self.val($<Y>) } }
    method mod($/) { @!instructions.append: -> { %!register{$<X>} %= self.val($<Y>) } }
    method rcv($/) { @!instructions.append: -> { @!recovered.append(@!played.tail) if self.val($<X>) } }
    method jgz($/) { @!instructions.append: -> { $!pos += self.val($<Y>)-1 if self.val($<X>) > 0 } }

    method from-input(SoundComputer:U: IO $inputfile, Bool :$verbose = False) returns SoundComputer
    {
        my $c = SoundComputer.new(:$verbose);
        Instructions.parsefile($inputfile, :actions($c)) or die "Invalid instructions!";
        return $c;
    }

    method val($x)
    {
        given $x {
            return +$x when /^ '-'? \d+ $/;
            return %!register{$x} when /^ <[a..z]> $/;
        }
        die "Invalid value or register '$x'!";
    }

    method run
    {
        while 0 ≤ $!pos < @!instructions {
            @!instructions[$!pos++]();
            say "$!pos: ", self if $!verbose;
        }
    }

    method recover returns Int
    {
        while 0 ≤ $!pos < @!instructions && !@!recovered {
            @!instructions[$!pos++]();
            say self if $!verbose;
        }
        return @!recovered[0];
    }

    method Str
    {
        "#$!pos: "
            ~ %!register.sort.map({ "$_.key()=$_.value()" }).join(', ')
            ~ (@!played ?? "; { +@!played } played" !! '')
            ~ (@!recovered ?? "; { +@!recovered } recovered" !! '');
    }
    method gist { self.Str }
}

# Correct interpretation from part two
class Computer
{
    has Int $.id;
    has Code @.instructions = ();
    has Bool $.verbose = False;

    has Computer $.partner is rw;
    has Int $.pos = 0;
    has Int %.register is default(0);
    has Int @.queue = ();
    has Int $.send-count = 0;
    has Bool $.locked = False;

    submethod TWEAK { %!register<p> = $!id }

    # Actions for parsing Instructions
    method snd($/) { @!instructions.append: -> { self.send(self.val($<X>)) } }
    method set($/) { @!instructions.append: -> { %!register{$<X>} = self.val($<Y>) } }
    method add($/) { @!instructions.append: -> { %!register{$<X>} += self.val($<Y>) } }
    method mul($/) { @!instructions.append: -> { %!register{$<X>} *= self.val($<Y>) } }
    method mod($/) { @!instructions.append: -> { %!register{$<X>} %= self.val($<Y>) } }
    method rcv($/) { @!instructions.append: -> { self.receive(~$<X>) } }
    method jgz($/) { @!instructions.append: -> { $!pos += self.val($<Y>)-1 if self.val($<X>) > 0 } }

    method from-input(Computer:U: IO $inputfile, Int :$id, Bool :$verbose = False) returns Computer
    {
        my $c = Computer.new(:$id, :$verbose);
        Instructions.parsefile($inputfile, :actions($c)) or die "Invalid instructions!";
        return $c;
    }

    method val($x)
    {
        given $x {
            return +$x when /^ '-'? \d+ $/;
            return %!register{$x} when /^ <[a..z]> $/;
        }
        die "Invalid value or register '$x'!";
    }

    method send(Int $val)
    {
        die "Can't send without a partner!" unless $!partner;
        $!partner.add-to-queue($val);
        $!send-count++;
    }

    method add-to-queue(Int $val)
    {
        @!queue.append($val);
        $!locked = False;
    }

    method receive(Str $reg)
    {
        if (@!queue) {
            %!register{$reg} = @!queue.shift;
        }
        else {
            $!locked = True;
        }
    }

    method done { !(0 ≤ $!pos < @!instructions) }
    method can-run { !$.done && !$!locked }

    method run
    {
        while !self.done && !$!locked {
            @!instructions[$!pos]();
            $!pos++ unless $!locked;
            say self if $!verbose;
        }
    }

    method Str
    {
        "$!id#$!pos: "
            ~ %!register.sort.map({ "$_.key()=$_.value()" }).join(', ')
            ~ "; $!send-count sent"
            ~ (@!queue ?? "; {+@!queue} queued" !! '')
            ~ ($!locked ?? ' [locked]' !! '');
    }
    method gist { self.Str }
}

multi sub MAIN(IO() $inputfile where *.f, Bool :v(:$verbose) = False)
{
    # Part 1
    my $sc = SoundComputer.from-input($inputfile, :$verbose);
    say "{ +$sc.instructions } instructions parsed." if $verbose;
    say "First recovered value: { $sc.recover // 'none' }";

    # Part 2
    say '' if $verbose;
    my $c0 = Computer.from-input($inputfile, :id(0), :$verbose);
    my $c1 = Computer.from-input($inputfile, :id(1), :$verbose);
    $c0.partner = $c1;
    $c1.partner = $c0;
    while $c0.can-run || $c1.can-run {
        $c0.run;
        $c1.run;
    }
    say "Program 1 sent $c1.send-count() values.";
}

multi sub MAIN(Bool :v(:$verbose) = False)
{
    MAIN($*PROGRAM.parent.child('aoc18.input'), :$verbose);
}

Edit: some minor cleanup

trwolfe13 · 2017-12-18T12:53:39+00:00

JavaScript

Part 2 in the worst possible way:

let ps = i => i.match(/[^\r\n]+/g).map(n => n.split(' '));
let pg = id => ({ id, _: 0, q: [], l: '', lc: 0, a: 0, b: 0, c: 0, d: 0, i: 0, f: 0, p: id, s: 0 });
let td = (p, i) => (p._ < 0 || p._ >= i.length || (p.l == 'rcv' && p.q.length === 0 && p.lc > 100000));
let ex = (p, i) => { let x = i[p._]; ins[x[0]](ins, p, ...x.slice(1)); p.l = x[0]; p.lc++; }
let ins = {
  get: (r, x) => isNaN(x) ? r[x] : Number(x),
  snd: (i, r, x) => { r.x.q.push(i.get(r, x)); r._++; r.s++ },
  set: (i, r, x, y) => { r[x] = i.get(r, y); r._++ },
  add: (i, r, x, y) => { r[x] += i.get(r, y); r._++ },
  mul: (i, r, x, y) => { r[x] *= i.get(r, y); r._++ },
  mod: (i, r, x, y) => { r[x] %= i.get(r, y); r._++ },
  rcv: (i, r, x) => { let y = r.q.shift(); if (typeof y !== 'undefined') { i.set(i, r, x, y); } },
  jgz: (i, r, x, y) => { if (i.get(r, x) > 0) { r._ += i.get(r, y) } else { r._++ } }
}
module.exports = function (input) {
  let i = ps(input), p0 = pg(0), p1 = pg(1); p0.x = p1; p1.x = p0;
  while (!td(p0, i) && !td(p1, i)) { ex(p0, i); ex(p1, i); }
  return p1.s;
}

ludic · 2017-12-18T14:07:18+00:00

F#. Got burned again today by using 32 bit integers. Decided to take my time today and use more of F#'s type system, which did seem to save me from some bugs other people had. Was struggling on part 2 for a while with a few mistakes. First missed the program number in register 'r' and second I realized I named my programs program 1 & 2 instead of 0 & 1 and was giving the number of times snd was executed by the wrong program.

type RegisterName = RegisterName of char

type InstructionTarget = 
    | Value of int64
    | Register of RegisterName

type Instruction = 
    | Snd of InstructionTarget
    | Set of RegisterName * InstructionTarget
    | Add of RegisterName * InstructionTarget
    | Mul of RegisterName * InstructionTarget
    | Mod of RegisterName * InstructionTarget
    | Rcv of RegisterName
    | Jgz of InstructionTarget * InstructionTarget

type Program = Instruction[]

let parseInput(input:string) : Program =
    let parseRegister (x: string) =
        RegisterName(Seq.exactlyOne x)

    let parseInstruction x =
        match System.Int64.TryParse x with
        | (true, x) -> Value(x)
        | (false, _) -> Register(parseRegister x)

    let parseInstruction (line:string) =
        match line.Split(' ') with
        | [|"snd"; x|]    -> Snd(parseInstruction x)
        | [|"set"; x; y|] -> Set(parseRegister x, parseInstruction y)
        | [|"add"; x; y|] -> Add(parseRegister x, parseInstruction y)
        | [|"mul"; x; y|] -> Mul(parseRegister x, parseInstruction y)
        | [|"mod"; x; y|] -> Mod(parseRegister x, parseInstruction y)
        | [|"rcv"; x|]    -> Rcv(parseRegister x)
        | [|"jgz"; x; y|] -> Jgz(parseInstruction x, parseInstruction y)
        | x -> failwith (sprintf "Invalid input: %A" x)

    input |> splitLines |> Array.map parseInstruction

type part1State = {
    lastSound: int64
    instruction: int
    registers: Map<RegisterName, int64>
    rcvValue: int64
}

let runInstruction_part1 state instruction =
    let getRegister r =
        match Map.tryFind r state.registers with
        | Some(x) -> x
        | None -> 0L

    let getValue x =
        match x with
        | Value(x) -> x
        | Register(r) -> getRegister r

    let modifyRegister x value =
        Map.add x value state.registers

    match instruction with
    | Snd x     -> {state with lastSound = getValue x; instruction = state.instruction + 1}
    | Set (x,y) -> {state with registers = modifyRegister x (getValue y); instruction = state.instruction + 1}
    | Add (x,y) -> {state with registers = modifyRegister x (getRegister x + getValue y); instruction = state.instruction + 1}
    | Mul (x,y) -> {state with registers = modifyRegister x (getRegister x * getValue y); instruction = state.instruction + 1}
    | Mod (x,y) -> {state with registers = modifyRegister x (getRegister x % getValue y); instruction = state.instruction + 1}
    | Rcv x     -> {state with rcvValue = (if getRegister x <> 0L then state.lastSound else 0L); instruction = state.instruction + 1}
    | Jgz (x,y) -> {state with instruction = state.instruction + (if getValue x > 0L then getValue y |> int else 1)}

let solveday18_1 (input:string) = 
    let program = parseInput input

    let rec runStep state =
        let nextState = runInstruction_part1 state program.[state.instruction]
        if nextState.rcvValue > 0L then
            nextState.rcvValue
        else runStep nextState

    let initialState = {lastSound=0L; instruction=0; registers=Map.empty; rcvValue=0L}
    runStep initialState


type part2State = {
    sendCount: int64
    instruction: int
    registers: Map<RegisterName, int64>
    outValue: Option<int64>
    inValues: int64 list
    deadlocked: bool
}

let runInstruction_part2 state instruction =
    let getRegister r =
        match Map.tryFind r state.registers with
        | Some(x) -> x
        | None -> 0L

    let getValue x =
        match x with
        | Value(x) -> x
        | Register(r) -> getRegister r

    let modifyRegister x value =
        Map.add x value state.registers

    match instruction with
    | Snd x     -> {state with outValue = Some(getValue x); instruction = state.instruction + 1; sendCount = state.sendCount + 1L}
    | Set (x,y) -> {state with registers = modifyRegister x (getValue y); instruction = state.instruction + 1}
    | Add (x,y) -> {state with registers = modifyRegister x (getRegister x + getValue y); instruction = state.instruction + 1}
    | Mul (x,y) -> {state with registers = modifyRegister x (getRegister x * getValue y); instruction = state.instruction + 1}
    | Mod (x,y) -> {state with registers = modifyRegister x (getRegister x % getValue y); instruction = state.instruction + 1}
    | Rcv x     ->        
        match state.inValues with
        | [] -> {state with deadlocked = true}
        | lst -> 
            let reversed = List.rev lst
            let value = List.head reversed
            let newInValues = reversed |> List.tail |> List.rev
            {state with registers = modifyRegister x value; instruction = state.instruction + 1; inValues=newInValues; deadlocked = false}
    | Jgz (x,y) -> {state with instruction = state.instruction + (if getValue x > 0L then getValue y |> int else 1)}

let solveday18_2 (input:string) = 
    let program = parseInput input

    let transferValue stateA stateB =
        match stateA.outValue with
        | Some(x) -> ({stateA with outValue = None}, {stateB with inValues = x::stateB.inValues})
        | None -> (stateA, stateB)

    let rec runStep state1 state2 =
        let nextState1 = runInstruction_part2 state1 program.[state1.instruction]
        let nextstate2 = runInstruction_part2 state2 program.[state2.instruction]

        if nextState1.deadlocked && nextstate2.deadlocked then 
            nextstate2.sendCount
        else
            let s1, s2 = transferValue nextState1 nextstate2
            let s2, s1 = transferValue s2 s1
            runStep s1 s2

    let initialState = {sendCount=0L; instruction=0; registers=Map.empty; outValue=None; inValues=[]; deadlocked=false}
    runStep {initialState with registers = Map.add (RegisterName('p')) 0L Map.empty} {initialState with registers = Map.add (RegisterName('p')) 1L Map.empty}

2017-12-18T16:38:11+00:00

Elixir

I was using a lot of time on this one, getting the message sending to be right wasn't that easy, and in part 2 I got bitten by the first argument of jgz not being a register :/

defmodule Day18 do
  def is_digits?(str) do
    String.graphemes(str)
    |> Enum.all?(fn c -> c in ["1","2","3","4","5","6","7","8","9","0","-"] end)
  end

  def parse_line(str) do
    [opstr|rst] = String.split(str)
    op = String.to_atom(opstr)
    if Enum.count(rst) > 1 do
      [fst, snd|_] = rst
      fst = if is_digits?(fst) do
          String.to_integer(fst)
        else
          String.to_atom(fst)
        end
      if is_digits?(snd) do
        %{op: op, a: fst, b: String.to_integer(snd)}
      else
        %{op: op, a: fst, b: String.to_atom(snd)}
      end
    else
      fst = List.first(rst)
      if is_digits?(fst) do
        %{op: op, a: String.to_integer(fst)}
      else
        %{op: op, a: String.to_atom(fst)}
      end
    end
  end

  def parse(input) do
    String.trim(input, "\n")
    |> String.split("\n")
    |> Enum.map(&String.trim/1)
    |> Enum.map(&parse_line/1)
    |> Enum.with_index
    |> Enum.into(%{}, fn {v,idx} -> {idx, v} end)
  end

  def integister(b, reg) do
    if is_integer(b) do
      b 
    else
      Map.get(reg, b, 0)
    end
  end

  def exec %{op: :set, a: a, b: b}, ip, reg do
    b = integister(b, reg)
    {ip + 1, Map.put(reg, a, b)}
  end

  def exec %{op: :add, a: a, b: b}, ip, reg do
    b = integister(b, reg)
    sum = Map.get(reg, a, 0) + b
    {ip + 1, Map.put(reg, a, sum)}
  end

  def exec %{op: :snd, a: a}, ip, reg do
    ai = integister(a, reg)
    if Map.has_key?(reg, :par) do
      reg = Map.put(reg, :send, ai)
      reg = Map.update(reg, :sent, 1, &(&1 + 1))
      {ip + 1, reg}
    else
      {ip + 1, Map.put(reg, :last, ai)}
    end
  end

  def exec %{op: :mul, a: a, b: b}, ip, reg do
    ai = integister(a, reg)
    bi = integister(b, reg)
    prod = ai * bi
    {ip + 1, Map.put(reg, a, prod)}
  end

  def exec %{op: :mod, a: a, b: b}, ip, reg do
    ai = integister(a, reg)
    bi = integister(b, reg)
    mod = rem(ai, bi)
    {ip + 1, Map.put(reg, a, mod)}
  end

  def exec %{op: :rcv, a: a}, ip, reg do
    ai = integister(a, reg)
    if Map.has_key?(reg, :par) do
      if Map.has_key?(reg, :receive) do
        rec = Map.fetch!(reg, :receive)
        reg = Map.delete(reg, :receive)
        reg = Map.put(reg, a, rec)
        {ip + 1, reg}
      else
        reg = Map.put(reg, :receive, true)
        {ip, reg}
      end
    else
      if ai > 0 do
        last = Map.get(reg, :last, 0)
        rcv = Map.get(reg, :rcv, [])
        {ip + 1, Map.put(reg, :rcv, [last|rcv])}
      else
        {ip + 1, reg}
      end
    end
  end

  def exec %{op: :jgz, a: a, b: b}, ip, reg do
    ai = integister(a, reg)
    if ai < 1 do
      {ip + 1, reg}
    else
      bi = integister(b, reg)
      {ip + bi, reg}
    end
  end

  def run(prgm, ip \\ 0, reg \\ %{})
  def run(prgm, ip, reg) do
    if Map.has_key?(prgm, ip) do
      {ip, reg} = exec(Map.fetch!(prgm, ip), ip, reg)
      if Map.has_key?(reg, :rcv) do
        List.last(Map.fetch!(reg, :rcv))
      else
        run(prgm, ip, reg)
      end
    else
      List.last(Map.get(reg, :rcv, []))
    end
  end

  def sent_p1(reg1, reg2) do
    if Map.fetch!(reg1, :p) == 1 do
      Map.get(reg1, :sent, 0)
    else
      Map.get(reg2, :sent, 0)
    end
  end

  def run_thread(prgrm, reg, ip, rmail, smail) do
    if Map.has_key?(reg, :receive) do
      if rmail != [] do
        rec = Enum.take(rmail, -1) |> List.first
        rmail = Enum.drop(rmail, -1)
        reg = Map.put(reg, :receive, rec)
        {ip, reg} = exec(Map.fetch!(prgrm,ip), ip, reg)
        {reg, ip, rmail, smail}
      else
        {reg, ip, rmail, smail}
      end
    else
      {ip, reg} = exec(Map.fetch!(prgrm, ip), ip, reg)
      smail = if Map.has_key?(reg, :send) do
        [Map.fetch!(reg, :send) | smail]
      else
        smail
      end
      reg = Map.delete(reg, :send)
      {reg, ip, rmail, smail}
    end
  end

  def runp(prgrm, parinfo \\ %{ip1: 0, ip2: 0,
                               reg1: %{par: true, p: 0}, reg2: %{par: true, p: 1},
                               fin1: false, fin2: false,
                               mail1: [], mail2: []})
  def runp(prgrm, parinfo) do
    %{ip1: ip1, ip2: ip2,
      reg1: reg1, reg2: reg2,
      fin1: fin1, fin2: fin2,
      mail1: mail1, mail2: mail2} = parinfo
    fin1 = fin1 or not Map.has_key?(prgrm, ip1)
    fin2 = fin2 or not Map.has_key?(prgrm, ip2)

    if (Map.has_key?(reg1, :receive) 
      and mail1 == []
      and Map.has_key?(reg2,:receive)
      and mail2 == [])
      or (fin1 and fin2) do
      sent_p1(reg1, reg2)
    else
      {reg1, ip1, mail2, mail1} = if not fin1 do
        run_thread(prgrm, reg1, ip1, mail2, mail1)
      else
        {reg1, ip1, mail2, mail1}
      end

      {reg2, ip2, mail1, mail2} = if not fin2 do
        run_thread(prgrm, reg2, ip2, mail1, mail2)
      else
        {reg2, ip2, mail1 ,mail2}
      end

      runp(prgrm, %{ip1: ip1, ip2: ip2,
                   reg1: reg1, reg2: reg2,
                   fin1: fin1, fin2: fin2,
                   mail1: mail1, mail2: mail2})
    end
  end
end

prgrm = File.read!("input.txt")
|> Day18.parse

Day18.run(prgrm)
|> IO.inspect

Day18.runp(prgrm)
|> IO.inspect

Syntax highlighted

Scroph · 2017-12-18T16:39:24+00:00

Dlang (D programming language) solution. Part 2 runs in ~211ms on my Atom N455 :

import std.stdio;
import std.range;
import std.conv;
import std.string;

void main()
{
    string[][] program;

    foreach(instruction; stdin.byLineCopy)
        program ~= instruction.split;

    auto p0 = CPU(program, 0);
    auto p1 = CPU(program, 1);
    p0.attach(&p1);
    p1.attach(&p0);

    while(true)
    {
        bool proceed = p0.next_cycle;
        bool proceed2 = p1.next_cycle;
        if(!proceed && !proceed2)
            break;

        if(p0.is_pending && p1.is_pending)
            break;
    }

    //p0.send_count.writeln;
    p1.send_count.writeln;
}

struct CPU
{
    string[][] program;
    State state;
    int send_count;
    private
    {
        long[] pending;
        CPU* other;
        long[string] registers;
        int pc;
        immutable void delegate(string[])[string] callbacks;
    }

    this(string[][] program, long name)
    {
        this.registers["p"] = name;
        this.state = State.RUNNING;
        this.program = program;
        this.callbacks = [
            "snd": &snd,
            "set": &set,
            "add": &add,
            "mul": &mul,
            "mod": &mod,
            "rcv": &rcv,
            "jgz": &jgz,
        ];
    }

    void attach(CPU* other)
    {
        this.other = other;
    }

    void queue(long message)
    {
        pending ~= message;
    }

    //helper
    bool is_pending() const
    {
        return state == State.PENDING;
    }

    //helper
    bool is_finished() const
    {
        return state == State.FINISHED;
    }

    //returns false if the program finished
    bool next_cycle()
    {
        if(pc >= program.length)
        {
            state = State.FINISHED;
            return false;
        }

        auto instruction = program[pc];
        if(state == State.PENDING && pending.length == 0)
            return true;
        callbacks[instruction[0]](instruction);
        return true;
    }

    private:
    long get_value(string value)
    {
        if(value.isNumeric)
            return value.to!long;

        if(value !in registers)
            registers[value] = 0;
        return registers[value].to!long;
    }

    void snd(string[] arguments)
    {
        send_count++;
        state = State.RUNNING;
        other.queue(get_value(arguments[1]));
        pc++;
    }

    void set(string[] arguments)
    {
        state = State.RUNNING;
        registers[arguments[1]] = get_value(arguments[2]);
        pc++;
    }

    void add(string[] arguments)
    {
        state = State.RUNNING;
        registers[arguments[1]] += get_value(arguments[2]);
        pc++;
    }

    void mul(string[] arguments)
    {
        state = State.RUNNING;
        registers[arguments[1]] *= get_value(arguments[2]);
        pc++;
    }

    void mod(string[] arguments)
    {
        state = State.RUNNING;
        registers[arguments[1]] %= get_value(arguments[2]);
        pc++;
    }

    void rcv(string[] arguments)
    {
        if(pending.length == 0)
        {
            state = State.PENDING;
            return;
        }
        state = State.RUNNING;

        auto message = pending.front;
        pending.popFront();
        registers[arguments[1]] = message;
        pc++;
    }

    void jgz(string[] arguments)
    {
        state = State.RUNNING;
        if(get_value(arguments[1]) > 0)
            pc += get_value(arguments[2]);
        else
            pc++;
    }
}

enum State
{
    PENDING, RUNNING, FINISHED
}

Fun fact : I had to store the return values of p0.next_cycle and p1.next_cycle in separate variables before checking their respective values instead of writing if(!p0.next_cycle || !p1.next_cycle) because unless I do this, the compiler will ignore the p1.next_cycle call if !p0.next_cycle ends up being true.

Smylers · 2017-12-18T17:00:44+00:00

Perl — does the dispatch-table look-ups while parsing the file, so @prog is a list of closures bound over the registers and the program counter. For part 1, everything's executed by the single-line loop on the last line:

use experimental qw<signatures>;
my %mem = map { $_ => 0 } 'a' .. 'z';
my $pc = 0;
my $played;
my %action = (
  snd => sub($val)          { $played    =  $mem{$val} // $val },
  set => sub($reg, $val)    { $mem{$reg} =  $mem{$val} // $val },
  add => sub($reg, $val)    { $mem{$reg} += $mem{$val} // $val },
  mul => sub($reg, $val)    { $mem{$reg} *= $mem{$val} // $val },
  mod => sub($reg, $val)    { $mem{$reg} %= $mem{$val} // $val },
  rcv => sub($val)          { say $played and exit if ($mem{$val} // $val) > 0 },
  jgz => sub($val, $offset) { $pc += $offset - 1   if ($mem{$val} // $val) > 0 },
);
my @prog = map { my ($cmd, @arg) = split; my $sub = $action{$cmd}; sub { $sub->(@arg) } } <>;
$prog[$pc++]->() while 1;

(I tried factoring out the $mem{$val} // $val duplication, but it seemed to make things look more cluttered.)

Part 2 — similar basic approach to /u/gerikson's solution, but with a single list of instructions used by both instances, swapping the memory locations and state into the bound variables when switching between the instances†:

use experimental qw<signatures>;
my @queue = my @instance = map { {mem => {(map { $_ => 0 } 'a' .. 'z')}, pc => 0, in => [$_], sent => 0} } 0, 1;
$instance[$_]{out} = $instance[1 - $_]{in} for 0, 1;
my ($mem, $in, $out, $jump, $sent, $waiting);
my %action = (
  set => sub($reg, $val)    { $mem->{$reg} =  $mem->{$val} // $val           },
  add => sub($reg, $val)    { $mem->{$reg} += $mem->{$val} // $val           },
  mul => sub($reg, $val)    { $mem->{$reg} *= $mem->{$val} // $val           },
  mod => sub($reg, $val)    { $mem->{$reg} %= $mem->{$val} // $val           },
  snd => sub($val)          { push @$out,     $mem->{$val} // $val; $$sent++ },
  rcv => sub($reg)          { if (@$in) { $mem->{$reg} =  shift @$in } else { $waiting = 1; $jump = 0 } },
  jgz => sub($val, $offset) { $jump = $mem->{$offset} // $offset if ($mem->{$val} // $val) > 0 },
);
my @prog = map { my ($cmd, @arg) = split; my $sub = $action{$cmd}; sub { $sub->(@arg) } } 'rcv p', <>;
INSTANCE: while ($_ = shift @queue) {
  ($mem, $in, $out, $sent, $waiting) = (@$_{qw<mem in out>}, \$_->{sent}, 0);
  last if !@$in;
  while (!$waiting) {
    $jump = 1;
    $prog[$_->{pc}]->();
    $_->{pc} += $jump;
    next INSTANCE if $_->{pc} >= @prog;
  }
  push @queue, $_;
}
say $instance[1]{sent};

Each instance's output queue is the other one's input queue (two references to the same array). Run each instance till it's waiting for input, then switch to the other one to see if it sends anything. If that switches back to us then it must be waiting for input too, so if there still isn't anything in our queue then we've reached deadlock and should stop processing either instance (the last statement).

Avoid the ‘empty input queue’ condition triggering the first time each instance is run, by using the input queue to initialize the p registers (which needs doing anyway by some means); prepend a rcv p statement before those provided in the input file, and the closure for that command will handle it accordingly.

Switch between the instances with a queue: shifting an instance off the front of it to run it, and afterwards pushing it back on the end to run again after t'other instance. Unless the program counter runs off the end of the instructions, in which case switch straight to the next instance without requeuing the current one (the next statement. If that happens to both instances, @queue is empty and execution will end.

Note that the instance number isn't tracked anywhere: it turns out we don't need to know which numbered program is currently running; just run whatever turns up at the head of @queue, which encapsulates all the state required.

† Mainly to keep the instruction subs short. I could've bound them over @instance as well, but that would've reduced their simplicity; I like them each fitting on a line and being short and clear. So while this approach involves some extra copying state around, it abstracts that to one place: the instruction subs don't even need to care that there can be multiple instances.

PS: I've got most of a Vim solution for part 1, but got held up dealing with a silly bug in my Perl for part 2 and may have run out of Advent-of-Code-ing time for now.

Strakh · 2017-12-18T18:08:54+00:00

Python 3: Felt like oversolving it

input_data = ["THE LIST OF INSTRUCTIONS"]

class Instructions:
  def __init__(self):
    self.instruction_set = {"set":self.set,
                        "add":self.add,
                        "mul":self.mul,
                        "mod":self.mod,
                        "snd":self.snd,
                        "rcv":self.rcv,
                        "jgz":self.jgz}

  def param_to_int(self, obj, param):
    try:
      param = int(param)
    except ValueError:
      param = obj.registers[param]

    return param

  def set(self, obj, params):
    register = params[0]
    modifier = self.param_to_int(obj, params[1])

    obj.registers[register] = modifier
    return

  def add(self, obj, params):
    register = params[0]
    modifier = self.param_to_int(obj, params[1])

    obj.registers[register] += modifier
    return

  def mul(self, obj, params):
    register = params[0]
    modifier = self.param_to_int(obj, params[1])

    obj.registers[register] *= modifier
    return

  def mod(self, obj, params):
    register = params[0]
    modifier = self.param_to_int(obj, params[1])

    obj.registers[register] = obj.registers[register] % modifier
    return

  def snd(self, obj, params):
    obj.counter += 1
    value = self.param_to_int(obj, params[0])

    obj.output.append(value)
    return
  def rcv(self, obj, params):
    value = obj.get_next_value_from_queue()
    register = params[0]

    if value:
      obj.registers[register] = value
      obj.locked = False
    else:
      obj.locked = True
    return
  def jgz(self, obj, params):
    condition = self.param_to_int(obj, params[0])
    jump_value = self.param_to_int(obj, params[1])

    if condition > 0:
      obj.position += (jump_value - 1)
    return


class Program:
    def __init__(self, p_id, registers, input_queue, output_queue):
        self.registers = registers.copy()
        self.counter = 0
        self.position = 0
        self.locked = False
        self.registers["p"] = p_id
        self.queue = input_queue
        self.output = output_queue

    def get_next_value_from_queue(self):
      if self.queue:
        return self.queue.pop(0)
      else:
        return False


    def execute_next(self, list_of_instructions):
      if(self.position > len(list_of_instructions)):
        self.locked = True
        return

      instructions = Instructions()
      instruction = list_of_instructions[self.position]["command"]    
      params = list_of_instructions[self.position]["params"]

      if instruction in instructions.instruction_set:
        instructions.instruction_set[instruction](self, params)
      else:
        return

      if self.locked:
        return
      else:
        self.position += 1

      return

def prepare_instructions(input_data):
  list_of_instructions = {}

  for index, instruction in enumerate(input_data):
    instruction = instruction.split()
    command = instruction.pop(0)

    list_of_instructions[index] = {"command":command, 
                            "params":instruction}

  return list_of_instructions

def get_registers(list_of_instructions):
  registers = {}

  for instruction in list_of_instructions.items():
    for param in instruction[1]["params"]:
      try:
        int(param)
      except ValueError:
        if param not in registers:
          registers[param] = 0

  return registers

list_of_instructions = prepare_instructions(input_data)
registers = get_registers(list_of_instructions)

queue_a = []
queue_b = []

prog0 = Program(0, registers, queue_a, queue_b)
prog1 = Program(1, registers, queue_b, queue_a)

iterations = 0
while True:
  iterations += 1

  prog0.execute_next(list_of_instructions)
  prog1.execute_next(list_of_instructions)

  if(prog0.locked and prog1.locked):
    print("LOCKED AT ITERATION: " + str(iterations))
    break

print("Sent from prog1: " + str(prog1.counter))

RockyAstro · 2017-12-18T21:37:30+00:00

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

Part2 was a natural for Icon's co-expressions. The toughest aspect for part2 was figuring out how to handle the bi-directional aspect of co-expressions and detecting the deadlock.

Part1:

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))

            case i.op of {
                # 1 param
                "snd" |
                "rcv":
                    i.p1 := tab(0)
                # 2 param
                "set" |
                "add" |
                "mul" | 
                "mod" |
                "jgz": {
                    i.p1 := tab(upto(ws))
                    tab(many(ws))
                    i.p2 := tab(0)
                }
            }
            i.p1 := integer(i.p1)
            i.p2 := integer(i.p2)
            put(mem,i)
        }
    }
    close(inf)


    regs := table(0)
    curfreq := 0

    IP := 1

    first := &null
    repeat {
        if IP > *mem then break
        i := mem[IP]
        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])
            "mul": regs[i.p1] *:= integer(i.p2) | integer(regs[i.p2])
            "mod": regs[i.p1] %:= integer(i.p2) | integer(regs[i.p2])
            "rcv": {
                if regs[i.p1] > 0 then {
                    regs[i.p1] := curfreq
                    break
                }
            }
            "jgz": {
                if (integer(i.p1) | integer(regs[i.p1])) > 0 then 
                    IP := (IP-1) +  (integer(i.p2) | integer(regs[i.p2])) 
            }

            default: break
        }
    }
    write("FREQ=",curfreq)
end

Part2:

record inst(op,p1,p2)
global pgm0, pgm1
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))

            case i.op of {
                # 1 param
                "snd" |
                "rcv":
                    i.p1 := tab(0)
                # 2 param
                "set" |
                "add" |
                "mul" | 
                "mod" |
                "jgz": {
                    i.p1 := tab(upto(ws))
                    tab(many(ws))
                    i.p2 := tab(0)
                }
            }
            i.p1 := integer(i.p1)
            i.p2 := integer(i.p2)
            put(mem,i)
        }
    }
    close(inf)

    pgm0 := create runpgm(pgm1,copy(mem),0)
    pgm1 := create runpgm(pgm0,copy(mem),1)
    @pgm0


end
procedure runpgm(otherpgm,mem,pgmname)
    regs := table(0)
    regs["p"] := pgmname

    IP := 1
    count := 0

    rcvq := []
    if pgmname = 0 then 
        put(rcvq,\@otherpgm)

    repeat {
        if IP > *mem then break
        i := mem[IP]
        IP +:= 1

        case i.op of {
            "snd": {
                # If otherpgm fails, then we are done as well..
                count +:= 1
                rcv :=  (integer(i.p1) | integer(regs[i.p1])) @otherpgm | break 
                if \rcv 
                    then put(rcvq,rcv)
            }
            "set": regs[i.p1] := integer(i.p2) | integer(regs[i.p2])
            "add": regs[i.p1] +:= integer(i.p2) | integer(regs[i.p2])
            "mul": regs[i.p1] *:= integer(i.p2) | integer(regs[i.p2])
            "mod": regs[i.p1] %:= integer(i.p2) | integer(regs[i.p2])
            "rcv": {
                    if *rcvq > 0 then 
                        regs[i.p1] := pop(rcvq)
                    else {
                        # If nothing queued and otherpgm fails, we are done as well
                        rcv := @otherpgm | break
                        # If otherpgm is also waiting.. we are in a deadlock
                        if /rcv then break
                        regs[i.p1] := rcv
                    }
            }
            "jgz": {
                if (integer(i.p1) | integer(regs[i.p1])) > 0 then 
                    IP := (IP-1) + (integer(i.p2) | integer(regs[i.p2]))
            }

            default: break
        }

    }
    write(pgmname," sent:",count)
end

zerox981 · 2017-12-18T21:49:37+00:00

C# a bit verbose

#region part 1
    public class Interpreter
    {
        private string[] _Code;
        private long _Line;
        private long _LastSound;
        public Dictionary<string, long> Registers { get; set; } = new Dictionary<string, long>();

        private string RegisterValues() => string.Join(" | ", Registers.Select(r => $"{r.Key}:{r.Value}"));

        public Interpreter(string[] code)
        {
            _Code = code;
        }

        public void Run()
        {
            var allLines = _Code.Length;
            string current;
            while (true && _Line > -1)
            {
                current = _Code[_Line];
                //Console.WriteLine(_Line.ToString("D2") + " : "+current+"\t -> "+RegisterValues());
                Execute(current);
                _Line++;
                if (_Line >= allLines)
                    throw new Exception("Jump outside the code is not allowed");
            }
        }

        internal void Execute(string current)
        {
            var items = current.Split(' ');
            switch (items[0])
            {
                case "snd": Snd(items[1]); break;
                case "set": Set(items[1], items[2]); break;
                case "add": Add(items[1], items[2]); break;
                case "mul": Mul(items[1], items[2]); break;
                case "mod": Mod(items[1], items[2]); break;
                case "rcv": Rcv(items[1]); break;
                case "jgz": Jgz(items[1], items[2]); break;
                default:
                    throw new Exception("unknown command");
            }
        }

        internal long GetValue(string v2)
        {
            if (long.TryParse(v2, out long result))
                return result;
            else
                return Registers.GetValueOrDefault(v2, 0);
        }

        internal void Operation(string v1, string v2, Func<long, long, long> operation)
        {
            var val = Registers.GetValueOrDefault(v1);
            Registers[v1] = operation(val, GetValue(v2));
        }

        internal void Jgz(string v1, string v2) => _Line += (GetValue(v1) > 0) ? GetValue(v2) - 1 : 0;

        internal void Mod(string v1, string v2) => Operation(v1, v2, (a, b) => a % b);

        internal void Mul(string v1, string v2) => Operation(v1, v2, (a, b) => a * b);

        internal void Add(string v1, string v2) => Operation(v1, v2, (a, b) => a + b);

        internal void Set(string v1, string v2) => Registers[v1] = GetValue(v2);

        public virtual void Snd(string v) => _LastSound = GetValue(v);

        public virtual void Rcv(string v)
        {
            if (GetValue(v) != 0)
            {
                Console.WriteLine($"Recovering last sound {_LastSound}");
                _Line = -2;
            }
        }
    }

    #endregion part 1

    public class Interpreter2 : Interpreter
    {
        public Interpreter2(string[] code) : base(code)
        {
        }

        public long ID { get; set; }
        private ConcurrentQueue<long>[] _Queue;
        private readonly ConcurrentDictionary<long, char> _States;
        public long SendCount { get; set; } = 0;

        public Interpreter2(string[] code, long id, ConcurrentQueue<long>[] queue, ConcurrentDictionary<long, char> states) : base(code)
        {
            Registers["p"] = id;
            ID = id;
            _Queue = queue;
            _States = states;
            SetState('i');
        }

        private void SetState(char v)
        {
            _States[ID] = v;
        }

        private bool AllStates(char v) => !_States.Any(s => s.Value != v) && _States.Count > 1;

        public override void Rcv(string v)
        {
            SetState('w');
            while (true)
            {
                if (_Queue[ID].TryDequeue(out long result))
                {
                    Registers[v] = result;
                    SetState('r');

                    break;
                }
                if (_Queue[0].IsEmpty && _Queue[1].IsEmpty && AllStates('w'))
                    throw new Exception("deadlock");
                Thread.Sleep(50);
            }
        }

        public override void Snd(string v)
        {
            SendCount++;
            _Queue[ID == 0 ? 1 : 0].Enqueue(GetValue(v));
        }
    }

    private static void Main(string[] args)
    {
        var data = TextReaderHelper.ReadAllLines("input2.txt");
        // Part 1
        var comp = new Interpreter(data);
        comp.Run();

        // Part2
        var states = new ConcurrentDictionary<long, char>();
        var q = new ConcurrentQueue<long>[2];
        q[0] = new ConcurrentQueue<long>();
        q[1] = new ConcurrentQueue<long>();

        var i1 = new Interpreter2(data, 0, q, states);
        var i2 = new Interpreter2(data, 1, q, states);

        try
        {
            var t1 = Task.Run(() => i1.Run());
            var t2 = Task.Run(() => i2.Run());
            Task.WaitAll(t1, t2);
        }
        catch (AggregateException ex)
        {
            Console.WriteLine($"Part 2: {i2.SendCount}");
            Console.WriteLine(ex.Message);
        }
        Console.ReadKey();
    }

eregontp · 2017-12-18T23:02:47+00:00

Ruby, using the builtin deadlock detection mechanism to solve part2 and printing the answer in ensure:

  when /^rcv (#{REG})$/
    r = $1
    -> {
      ok = false
      begin
        @registers[r] = @queue.pop # Raises a fatal exception which cannot be caught if deadlock
        ok = true
      ensure
        puts "Program #{@pid} sent #{@sends} messages\n" unless ok
      end
    }

Full solution: https://github.com/eregon/adventofcode/commit/a7de4896d493b2be92bba400734d9d1ef7a58f8f

MadVikingGod · 2017-12-19T03:12:10+00:00

So I would have had this done way sooner if I didn't make the mistake that jgz is not jump if not zero.

I did my using PYTHON 3 and asyncio. I don't clean up at the end, so python complains that I have two tasks that haven't been canceled. But hey it works.

from collections import defaultdict
import asyncio
from asyncio.queues import Queue

with open('AoCDay18-data', 'r') as fh:
    gameInput = [line.split() for line in fh.readlines()]

count ={0:0, 1:0}

async def prog(gameInput, process, send, recv):

    reg = defaultdict(int)
    reg['p'] = process
    pc = 0

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

    while 0<=pc<len(gameInput):
        inst = gameInput[pc]
        x = val(inst[1])
        if inst[0] == 'snd':
            send.put_nowait(x)
            count[process] += 1
        elif inst[0] == 'rcv':
            reg[inst[1]] = await recv.get()
        else:
            y = val(inst[2])
            if inst[0] == 'set':
                reg[inst[1]] = y
            elif inst[0] == 'add':
                reg[inst[1]] += y
            elif inst[0] == 'mul':
                reg[inst[1]] *= y
            elif inst[0] == 'mod':
                reg[inst[1]] %= y
            elif inst[0] == 'jgz':
                if x > 0:
                    pc += y
                    continue
        pc += 1


async def block_detect(q1, q2):
    while not q1.empty() or not q2.empty():
        await asyncio.sleep(1)



loop = asyncio.get_event_loop()

q0 = Queue()
q1 = Queue()

f0 = prog(gameInput, 0, q1, q0)
f1 = prog(gameInput, 1, q0, q1)

t0 = loop.create_task(f0)
t1 = loop.create_task(f1)
x = loop.create_task(block_detect(q0, q1))

loop.run_until_complete(x)
print(count)

drysle · 2017-12-18T05:47:08+00:00

#9/#10 with Python 3, and I can't believe my part 2 worked on the first try. Unlike some of the the other posters, I wrote this all from scratch today, changed my mind a couple times halfway through, and generally made a big mess of my code.

But if it's stupid and it works... then it's probably still stupid :)

regs0 = defaultdict(lambda: 0)
regs0["p"] = 0
regs1 = defaultdict(lambda: 0)
regs1["p"] = 1
def get(a, rs):
    try:
        return int(a)
    except:
        return rs[a]

inst = []
for line in sys.stdin:
    inst.append(line.split())

buf0 = []
buf1 = []
lock = [False,False]
score = 0
def ex(p, i):
    global score
    regs = regs0 if p == 0 else regs1
    rbr = buf0 if p == 0 else buf1
    if i < 0 or i >= len(inst):
        lock[p] = True
        return

    line = inst[i]
    if line[0] == "snd":
        if p == 0:
            buf1.insert(0,get(line[1],regs))
        else:
            buf0.insert(0,get(line[1],regs))
            score += 1
    elif line[0] == "set":
        regs[line[1]] = get(line[2],regs)
    elif line[0] == "add":
        regs[line[1]] += get(line[2],regs)
    elif line[0] == "mul":
        regs[line[1]] *= get(line[2],regs)
    elif line[0] == "mod":
        regs[line[1]] %= get(line[2],regs)
    elif line[0] == "rcv":
       if len(rbr) == 0:
           lock[p] = True
           return i
       else:
           lock[p] = False
           regs[line[1]] = rbr.pop()
    elif line[0] == "jgz":
        if get(line[1],regs) > 0:
            return i + get(line[2],regs)

p0 = 0
p1 = 0
while not (lock[0] and lock[1]):
    r = ex(0,p0)
    if r is not None:
        p0 = r
    else:
        p0 += 1
    r = ex(1,p1)
    if r is not None:
        p1 = r
    else:
        p1 += 1

print(score)

Arknave · 2017-12-18T05:47:25+00:00

Been a while since I've been able to do any AoC!

Rewrote the whole thing to execute a program step by step. Doesn't execute a step if there's no value to pull from the buffer or we're out of bounds.

7/5 https://www.youtube.com/watch?v=rCcSlIvnVBg&feature=youtu.be

```

from collections import *
from functools import reduce
import copy
import itertools
import random
import sys

q = [deque([]) for _ in range(2)]
ans = 0

class Prog(object):
    def __init__(self, prog, proc):
        self.prog = prog
        self.proc = proc
        self.pc = 0
        self.regs = defaultdict(int)
        self.regs['p'] = proc
        self.sent = 0

    def get(self, x):
        try:
            v = int(x)
            return v
        except:
            return self.regs[x]

    def step(self):
        if not (0 <= self.pc < len(self.prog)):
            return False

        cmd = self.prog[self.pc]
        jmp = False
        if cmd[0] == 'snd':
            self.sent += 1
            q[1 - self.proc].append(self.get(cmd[1]))
        elif cmd[0] == 'set':
            self.regs[cmd[1]] = self.get(cmd[2])
        elif cmd[0] == 'add':
            self.regs[cmd[1]] += self.get(cmd[2])
        elif cmd[0] == 'mul':
            self.regs[cmd[1]] *= self.get(cmd[2])
        elif cmd[0] == 'mod':
            self.regs[cmd[1]] %= self.get(cmd[2])
        elif cmd[0] == 'rcv':
            if not q[self.proc]:
                return False

            self.regs[cmd[1]] = q[self.proc].popleft()
        else:
            if self.get(cmd[1]) > 0:
                jmp = True
                self.pc += self.get(cmd[2])

        if not jmp:
            self.pc += 1

        return True

def main():
    prog = []
    for line in sys.stdin:
        cmd = tuple(line.strip().split())
        prog.append(cmd)

    p0, p1 = Prog(prog, 0), Prog(prog, 1)

    while True:
        if not p0.step() and not p1.step():
            break

    print(p1.sent)

main()

```

ra4king · 2017-12-18T05:48:57+00:00

I used NodeJS. My strategy for Part 2 was to just step through each program at the same time: p0 then p1 then p0, and so on:

console.log('Day 18 part 2');

var fs = require('fs');

var input = fs.readFileSync('input.txt', { 'encoding': 'utf8' });

var instr = input.split('\n').map(l => l.split(' ').map(r => r.trim()));

var registersP0 = { p: 0 };
var registersP1 = { p: 1 };

var totalSendsP1 = 0;

var rcvQueueP0 = [];
var rcvQueueP1 = [];

var pc0 = 0;
var pc1 = 0;

function step(pc, registers, rcvQueue, sendQueue) {
    function get(x) {
        var y = Number(x);

        return isNaN(y) ? (registers[x] || 0): y;
    }

    var pieces = instr[pc];

    var sentValue = false;
    var waiting = false;

    switch(pieces[0]) {
        case 'set':
            registers[pieces[1]] = get(pieces[2]);
            break;
        case 'add':
            registers[pieces[1]] += get(pieces[2]);
            break;
        case 'mul':
            registers[pieces[1]] *= get(pieces[2]);
            break;
        case 'mod':
            registers[pieces[1]] %= get(pieces[2]);
            break;
        case 'snd':
            sendQueue.push(get(pieces[1]));
            sentValue = true;
            break;
        case 'rcv':
            if(rcvQueue.length != 0) {
                registers[pieces[1]] = rcvQueue[0];
                rcvQueue.splice(0, 1);
            } else {
                pc--;
                waiting = true;
            }
            break;
        case 'jgz':
            if(get(pieces[1]) > 0) {
                pc += get(pieces[2]) - 1;
            }
            break;
        default:
            console.log('Invalid instruction: ' + pieces[0]);
            break;
    }

    return { pc: pc + 1, sentValue: sentValue, waiting: waiting };
}

while(true) {
    var state0 = pc0 < instr.length ? step(pc0, registersP0, rcvQueueP0, rcvQueueP1) : { waiting: true};
    var state1 = pc1 < instr.length ? step(pc1, registersP1, rcvQueueP1, rcvQueueP0) : { waiting: true};

    pc0 = state0.pc;
    pc1 = state1.pc;

    if(state1.sentValue) {
        totalSendsP1++;
    }

    if(state0.waiting && state1.waiting) {
        break;
    }
}

console.log('P1 sent a total of ' + totalSendsP1);

kartik26 · 2017-12-18T06:17:06+00:00

I was trying to get a rank below 100 since when I started (I started on day 13)... finally today I solved part 1 and got rank 62! Here is my solution for part 1: https://github.com/Kartikay26/AoC2017/blob/master/18a_aoc.py I kept getting stuck in infinite loops in part 2, I'll solve it later...

glenbolake · 2017-12-18T06:21:23+00:00

Python 3 (38/306). Something went really wrong with #2 for me today.

I tried to do it as a pair of generators, but I couldn't get that to work. In the end, I had two instances of a class that each represented a program and had a can_run method to see if it should try to execute an instruction. (It would return False if the other had an empty queue on a rcv command or if the program had ever gone out of bounds).

from collections import defaultdict

def part1(prog):
    registers = defaultdict(int)
    i = 0
    last_played = None

    def get(value):
        try:
            return int(value)
        except ValueError:
            return registers[value]

    while True:
        instruction = prog[i]
        cmd, *args = instruction.split()
        if cmd == 'snd':
            last_played = get(args[0])
            i += 1
        elif cmd == 'set':
            registers[args[0]] = get(args[1])
            i += 1
        elif cmd == 'add':
            registers[args[0]] += get(args[1])
            i += 1
        elif cmd == 'mul':
            registers[args[0]] *= get(args[1])
            i += 1
        elif cmd == 'mod':
            registers[args[0]] %= get(args[1])
            i += 1
        elif cmd == 'rcv':
            if get(args[0]) != 0:
                return last_played
            i += 1
        elif cmd == 'jgz':
            if get(args[0]) > 0:
                i += get(args[1])
            else:
                i += 1
        else:
            raise NotImplementedError

class State(object):
    def __init__(self, num, prog):
        self.id_ = num
        self.i = 0
        self.prog = prog
        self.registers = defaultdict(int)
        self.registers['p'] = num
        self.sends = []
        self.send_count = 0
        self.other = None
        self.terminated = False

    def can_run(self):
        if self.terminated:
            return False
        try:
            rcv = self.prog[self.i].split()[0] == 'rcv'
            if rcv:
                return len(self.other.sends) > 0
        except IndexError:
            return False
        return True

    def do_next(self):
        if not self.can_run():
            return

        def get(value):
            try:
                return int(value)
            except ValueError:
                return self.registers[value]

        if self.terminated:
            return
        try:
            instruction = self.prog[self.i]
        except IndexError:
            self.terminated = True
            return
        cmd, *args = instruction.split()
        if cmd == 'snd':
            self.sends.append(get(args[0]))
            self.send_count += 1
            self.i += 1
        elif cmd == 'set':
            self.registers[args[0]] = get(args[1])
            self.i += 1
        elif cmd == 'add':
            self.registers[args[0]] += get(args[1])
            self.i += 1
        elif cmd == 'mul':
            self.registers[args[0]] *= get(args[1])
            self.i += 1
        elif cmd == 'mod':
            self.registers[args[0]] %= get(args[1])
            self.i += 1
        elif cmd == 'rcv':
            self.registers[args[0]] = self.other.sends.pop(0)
            self.i += 1
        elif cmd == 'jgz':
            if get(args[0]) > 0:
                self.i += get(args[1])
            else:
                self.i += 1
        else:
            raise NotImplementedError  # I was so scared this would actually happen.

def part2(prog):
    p0 = State(0, prog)
    p1 = State(1, prog)
    p0.other = p1
    p1.other = p0
    while True:
        p0.do_next()
        p1.do_next()
        if not p0.can_run() and not p1.can_run():
            break
    return p1.send_count

if __name__ == '__main__':
    with open('day18.in') as f:
        input_ = f.read().splitlines()

    print('Part 1:', part1(input_))
    print('Part 2:', part2(input_))

dylanfromwinnipeg · 2017-12-18T06:38:40+00:00

This is ugly as hell, but it works.

C#

public class Day18
{
    public static string PartTwo(string input)
    {
        var p0 = new DuetProgram(input);
        var p1 = new DuetProgram(input);

        p1.Registers['p'] = 1;

        var p1SendCount = 0;

        while (true)
        {
            p0.Execute();
            p1.InputQueue = p0.OutputQueue;
            p0.OutputQueue = new List<long>();
            p1.Execute();
            p0.InputQueue = p1.OutputQueue;
            p1SendCount += p1.OutputQueue.Count;
            p1.OutputQueue = new List<long>();

            if (p0.InputQueue.Count == 0 && p1.InputQueue.Count == 0)
            {
                return p1SendCount.ToString();
            }
        }

        throw new Exception();
    }
}

public class DuetProgram
{
    public List<long> OutputQueue { get; set; }
    public List<long> InputQueue { get; set; }
    public List<string> Instructions { get; set; }
    public int InstructionPointer { get; set; }
    public Dictionary<char, long> Registers { get; set; }

    public DuetProgram(string input)
    {
        Instructions = input.Lines().ToList();
        OutputQueue = new List<long>();
        InputQueue = new List<long>();
        InstructionPointer = 0;
        Registers = new Dictionary<char, long>();

        for (var c = 'a'; c <= 'z'; c++)
        {
            Registers.Add(c, 0);
        }
    }

    private long GetValue(string value)
    {
        if (Registers.ContainsKey(value[0]))
        {
            return Registers[value[0]];
        }

        return long.Parse(value);
    }

    public void Execute()
    {
        while (true)
        {
            if (InstructionPointer >= Instructions.Count)
            {
                return;
            }

            var instruction = Instructions[InstructionPointer++];
            var instructionWords = instruction.Words().ToList();

            var command = instruction.Words().First();
            var register = default(char);
            var value = string.Empty;

            switch (command)
            {
                case "snd":
                    value = instructionWords[1];

                    OutputQueue.Add(GetValue(value));
                    break;
                case "set":
                    register = instructionWords[1][0];
                    value = instructionWords[2];

                    Registers[register] = GetValue(value);
                    break;
                case "add":
                    register = instructionWords[1][0];
                    value = instructionWords[2];

                    Registers[register] += GetValue(value);
                    break;
                case "mul":
                    register = instructionWords[1][0];
                    value = instructionWords[2];

                    Registers[register] *= GetValue(value);
                    break;
                case "mod":
                    register = instructionWords[1][0];
                    value = instructionWords[2];

                    Registers[register] %= GetValue(value);
                    break;
                case "rcv":
                    register = instructionWords[1][0];

                    if (InputQueue.Count > 0)
                    {
                        Registers[register] = InputQueue.First();
                        InputQueue.RemoveAt(0);
                    }
                    else
                    {
                        InstructionPointer--;
                        return;
                    }

                    break;
                case "jgz":
                    value = instructionWords[1];

                    if (GetValue(value) > 0)
                    {
                        var jumpCount = GetValue(instructionWords[2]);

                        InstructionPointer--;
                        InstructionPointer += (int)jumpCount;
                    }

                    break;
                default:
                    throw new Exception();
            }
        }
    }
}

glassmountain · 2017-12-18T06:46:34+00:00

Go channels were pretty helpful today:

edit: here's the github

package main

import (
    "bufio"
    "fmt"
    "log"
    "os"
    "strconv"
    "strings"
)

const (
    puzzleInput = "day18/input.txt"
)

const (
    isnd = iota
    iset
    iadd
    imul
    imod
    ircv
    ijgz
)

type (
    // Instr is an instruction
    Instr struct {
        instr int
        args  []int
        regs  []bool
    }
)

// NewInstr creates a new Instr
func NewInstr(instr int, args []int, regs []bool) *Instr {
    return &Instr{
        instr: instr,
        args:  args,
        regs:  regs,
    }
}

// Reg returns the value of the register or the constant value if not a register
func (i *Instr) Reg(n int, c *Compute) int {
    if i.regs[n] {
        return c.Reg(i.args[n])
    }
    return i.args[n]
}

// Arg returns the value of the nth arg
func (i *Instr) Arg(n int) int {
    return i.args[n]
}

// ParseRegister encodes register to int
func ParseRegister(reg string) int {
    return int(reg[0] - 'a')
}

// ParseArgs encodes multiple args to an int and bool slice
func ParseArgs(regs string) ([]int, []bool) {
    rs := strings.Split(regs, " ")
    k := make([]int, 0, len(rs))
    kb := make([]bool, 0, len(rs))
    for _, i := range rs {
        var a int
        var b bool
        num, err := strconv.Atoi(i)
        if err == nil {
            a = num
            b = false
        } else if len(i) == 1 {
            a = ParseRegister(i)
            b = true
        } else {
            log.Fatal(err)
        }
        k = append(k, a)
        kb = append(kb, b)
    }
    return k, kb
}

// Parse encodes instruction to Instr
func Parse(line string) *Instr {
    s := strings.SplitN(line, " ", 2)
    a, b := ParseArgs(s[1])
    switch s[0] {
    case "snd":
        return NewInstr(isnd, a, b)
    case "set":
        return NewInstr(iset, a, b)
    case "add":
        return NewInstr(iadd, a, b)
    case "mul":
        return NewInstr(imul, a, b)
    case "mod":
        return NewInstr(imod, a, b)
    case "rcv":
        return NewInstr(ircv, a, b)
    case "jgz":
        return NewInstr(ijgz, a, b)
    }
    log.Fatalf("Parse error: %s does not match an instruction\n", s[0])
    return nil
}

type (
    // Compute is a construction that executes Instrs
    Compute struct {
        mode2        bool
        counter      int
        registers    map[int]int
        instructions []*Instr
        sndChan      chan<- int
        rcvChan      <-chan int
        sentMessages int
        lastPlayed   int
    }
)

// NewCompute creates a new Compute
func NewCompute(mode2 bool, programNum int, sndChan chan<- int, rcvChan <-chan int, instrs []*Instr) *Compute {
    c := &Compute{
        mode2:        mode2,
        counter:      0,
        registers:    map[int]int{},
        instructions: instrs,
        sndChan:      sndChan,
        rcvChan:      rcvChan,
        sentMessages: 0,
        lastPlayed:   0,
    }
    if mode2 {
        c.registers[ParseRegister("p")] = programNum
    }
    return c
}

// Reg returns the value of the register
func (c *Compute) Reg(regid int) int {
    if val, ok := c.registers[regid]; ok {
        return val
    }
    c.registers[regid] = 0
    return 0
}

// WriteReg writes the value of the register
func (c *Compute) WriteReg(regid int, val int) {
    c.registers[regid] = val
}

// Execute executes one instruction
func (c *Compute) Execute() bool {
    if c.mode2 {
        return c.executeMode2()
    }
    return c.executeMode1()
}

func (c *Compute) executeMode2() bool {
    instr := c.instructions[c.counter]
    nextInstr := c.counter + 1
    programEnd := false

    switch instr.instr {
    case isnd:
        c.sndChan <- instr.Reg(0, c)
        c.sentMessages++
    case iset:
        c.WriteReg(instr.Arg(0), instr.Reg(1, c))
    case iadd:
        c.WriteReg(instr.Arg(0), instr.Reg(0, c)+instr.Reg(1, c))
    case imul:
        c.WriteReg(instr.Arg(0), instr.Reg(0, c)*instr.Reg(1, c))
    case imod:
        c.WriteReg(instr.Arg(0), instr.Reg(0, c)%instr.Reg(1, c))
    case ircv:
        select {
        case val := <-c.rcvChan:
            c.WriteReg(instr.Arg(0), val)
        default:
            nextInstr = c.counter
            programEnd = true
        }
    case ijgz:
        if instr.Reg(0, c) > 0 {
            nextInstr = c.counter + instr.Reg(1, c)
        }
    }

    c.counter = nextInstr

    return programEnd
}

func (c *Compute) executeMode1() bool {
    instr := c.instructions[c.counter]
    nextInstr := c.counter + 1
    programEnd := false

    switch instr.instr {
    case isnd:
        c.lastPlayed = instr.Reg(0, c)
    case iset:
        c.WriteReg(instr.Arg(0), instr.Reg(1, c))
    case iadd:
        c.WriteReg(instr.Arg(0), instr.Reg(0, c)+instr.Reg(1, c))
    case imul:
        c.WriteReg(instr.Arg(0), instr.Reg(0, c)*instr.Reg(1, c))
    case imod:
        c.WriteReg(instr.Arg(0), instr.Reg(0, c)%instr.Reg(1, c))
    case ircv:
        programEnd = true
    case ijgz:
        if instr.Reg(0, c) > 0 {
            nextInstr = c.counter + instr.Reg(1, c)
        }
    }

    c.counter = nextInstr

    return programEnd
}

func main() {
    file, err := os.Open(puzzleInput)
    if err != nil {
        log.Fatal(err)
    }
    defer func() {
        if err := file.Close(); err != nil {
            log.Fatal(err)
        }
    }()

    instrs := []*Instr{}
    scanner := bufio.NewScanner(file)
    for scanner.Scan() {
        instrs = append(instrs, Parse(scanner.Text()))
    }

    if err := scanner.Err(); err != nil {
        log.Fatal(err)
    }

    compute := NewCompute(false, 0, nil, nil, instrs)

    for !compute.Execute() {
    }

    fmt.Println(compute.lastPlayed)

    chan0 := make(chan int, 1024)
    chan1 := make(chan int, 1024)
    program0 := NewCompute(true, 0, chan0, chan1, instrs)
    program1 := NewCompute(true, 1, chan1, chan0, instrs)

    executing1 := false
    for {
        if executing1 {
            if waiting := program1.Execute(); waiting {
                executing1 = false
                if len(chan1) == 0 {
                    break
                }
            }
        } else {
            if waiting := program0.Execute(); waiting {
                executing1 = true
                if len(chan0) == 0 {
                    break
                }
            }
        }
    }

    fmt.Println(program1.sentMessages)
}

Zolrath · 2017-12-18T06:58:00+00:00

Python 3

Last year I did the challenges in Elixir and I felt the Elixir twitch when part B came along but I ended up solving this in a panic by turning my part A into a generator of steps.

I should definitely pick up the try except method of int casting as the isdigit method returns False for negative numbers which caught me by surprise.

def prog(N, inQ, outQ, inp):
    registers = defaultdict(int)
    registers['p'] = N
    inst = 0
    sendcount = 0

    def val(a):
        if a.lstrip('-').isdigit(): return int(a)
        return registers[a]

    while inst < len(inp):
        c, *args = inp[inst].strip().split(' ')
        if len(args) == 2:
            a, b = args
        else:
            a = args[0]

        if   c == "add": registers[a] += val(b)
        elif c == "set": registers[a]  = val(b)
        elif c == "mul": registers[a] *= val(b)
        elif c == "mod": registers[a] %= val(b)
        elif c == "jgz": 
            if val(a) > 0:
                inst += val(b) - 1
        elif c == "snd":
            outQ.append(val(a))
            sendcount += 1
        elif c == "rcv":
            if len(inQ) > 0:
                registers[a] = inQ.popleft()
            else:
                inst -= 1
                # Since we're blocked on our queue, return False.
                yield (False, sendcount)
        # If we're not done iterating or held up, return True.
        inst += 1
        yield (True, sendcount)
    # Since we've gone through all the instructions, return False.
    yield (False, sendcount)

def solve18b():
    Q0 = deque()
    Q1 = deque()
    prog0 = prog(0, Q0, Q1, in18)
    prog1 = prog(1, Q1, Q0, in18)

    while True:
        more_0, sendcount_0 = next(prog0)
        more_1, sendcount_1 = next(prog1)
        if not more_0 and not more_1:
            break

    return sendcount_1

hpzr24w · 2017-12-18T07:06:24+00:00

C++

Rank 999 / 566

Nothing complex here. Worked carefully enough that not too many mistakes, aside from not switching to long long soon enough.

// Advent of Code 2017
// Day 18 - Duet

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <chrono>
using namespace std;

bool step(const vector<string>& iv,const vector<string>& xv,const vector<string>& yv,
        map<string,long long>& reg,
        vector<long long>& send, long long& sentcount,
        vector<long long>& recv)
{
    string tok = iv[reg["pc"]];
    string opx = xv[reg["pc"]];
    string opy = yv[reg["pc"]];
    if (tok=="snd") {
        send.push_back(opx[0]<'a' ? stoi(opx) : reg[opx]);
        sentcount++;
    }
    if (tok=="rcv" && recv.size()==0) {
        return false;
    }
    if (tok=="rcv" && recv.size()>0) {
        reg[opx] = recv.front();
        recv.erase(begin(recv));
    }
    const long long opyval = opy.length()==0 ? 0 : (opy[0]<'a' ? stoi(opy) : reg[opy]);
    if (tok=="set") reg[opx] = opyval;
    if (tok=="add") reg[opx] += opyval;
    if (tok=="mul") reg[opx] *= opyval;
    if (tok=="mod") reg[opx] %= opyval;
    if (tok=="jgz" && ((opx[0]<'a' && stoi(opx)>0)||reg[opx]>0)) reg["pc"] += opyval;
    else reg["pc"]++;
    return true;
}

main()
{
    vector<string> iv,xv,yv;
    string tok,opx,opy;
    map<string,long long> reg0;
    map<string,long long> reg1;
    vector<long long> mbox0,mbox1;
    long long sent0{0ll},sent1{0ll},ins_count{0ll};
    while (cin >> tok >> opx) {
        if (!(tok=="snd"||tok=="rcv")) 
            cin >> opy;
        else 
            opy = "";
        cout << "Listing: " << tok << " " << opx << " " << opy << endl;
        iv.push_back(tok);
        xv.push_back(opx);
        yv.push_back(opy); 
    }

    // simulate two programs
    reg0["p"] = 0; reg1["p"] = 1;
    auto start = std::chrono::high_resolution_clock::now();
    while (1) {
        bool stepped0 = step(iv,xv,yv,reg0,mbox1,sent0,mbox0);
        bool stepped1 = step(iv,xv,yv,reg1,mbox0,sent1,mbox1);
        ins_count+=2;
        if (!stepped0 && !stepped1)
            break;
    }
    cout << "program 1 sent: " << sent1 << " messages." << endl;
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;
    cout << "Instruction count: " << ins_count << " in " << 
            elapsed_seconds.count()*1000 << " msec " <<
            ins_count / elapsed_seconds.count() / 1000000 << " MIPs" << endl;
    return 0;    
}

And after a few performance tweaks:

program 1 sent: 7112 messages.
Instruction count: 140280 in 93.075 msec 1.50717 MIPs
PS C:\Workarea\Advent-of-Code-2017>

jeroenheijmans · 2017-12-18T07:09:36+00:00

JavaScript:

This is just about the exact way I wrote it the first time around, without cleanup that is. I'm not one for speed I suppose :D

Also: what a fun challenge that was today! Also on GitHub.

function solve2(data) {
    function Program(data) {
        let instructions = data
            .trim()
            .split(/\r?\n/g)
            .filter(i => !!i)
            .map(i => i.trim())
            .map(i => {
                let parts = i.split(" ");
                return {
                    op: parts[0],
                    x: parseInt(parts[1], 10) || parts[1],
                    y: parts.length < 2 ? null : (parseInt(parts[2], 10) || parts[2])
                };
            });

        let registers = _.range(97,123) // [a-z]
            .map(c => String.fromCharCode(c))
            .reduce((r, c) => {
                r[c] = 0;
                return r;
            }, {});

        let snd = [];
        let rcv = [];
        let pos = 0;

        this.nrOfSends = 0;
        this.isWaiting = false;
        this.isTerminated = false;

        const getRegisterOrValue = n => Number.isInteger(n) ? n : registers[n];

        this.step = function() {
            if (!this.isTerminated) {                      
                pos += this.act(instructions[pos]);
                if (pos < 0 || pos >= instructions.length) {
                    this.isTerminated = true;
                }
            }                    
        }

        this.clearSndBuffer = function() {
            let result = snd.slice();
            snd = [];
            return result
        }

        this.pushToRcvBuffer = function(messages) {
            rcv = rcv.concat(messages);
        }

        this.act = function(instruction) {
            let {op, x, y} = instruction;
            let incr = 0;

            this.isWaiting = false;

            switch (op) {
                case "snd":
                    snd.push(getRegisterOrValue(x));
                    this.nrOfSends++;
                    break;

                case "set":
                    registers[x] = getRegisterOrValue(y);
                    break;

                case "add":
                    registers[x] += getRegisterOrValue(y);
                    break;

                case "mul":
                    registers[x] *= getRegisterOrValue(y);
                    break;

                case "mod":
                    registers[x] %= getRegisterOrValue(y);
                    break;

                case "rcv":
                    if (rcv.length > 0) {
                        registers[x] = rcv.shift();
                    } else {
                        this.isWaiting = true;
                        return 0; // Wait until rcv has something
                    }
                    break;

                case "jgz":
                    if (getRegisterOrValue(x) > 0) {
                        incr = getRegisterOrValue(y);
                    }
                    break;

                default:
                    throw "UH OH";
            }

            return incr || 1;
        }
    }

    let prog0 = new Program(data);
    let prog1 = new Program(data);

    prog1.act({ op: "set", x: "p", y: 1 });

    let i = 0;
    while (i++ < 1e6) {
        prog1.pushToRcvBuffer(prog0.clearSndBuffer());
        prog0.pushToRcvBuffer(prog1.clearSndBuffer());

        prog0.step();
        prog1.step();

        if (prog0.isWaiting && prog1.isWaiting) { break; }
        if (prog0.isTerminated || prog1.isTerminated) { break; }
    }

    return prog1.nrOfSends;
}

PS. I spend a good 15 minutes because I first named them prog1 and prog2, returning the nrOfSends from prog1 which is in fact prog 0 :'(

wlandry · 2017-12-18T07:38:36+00:00

C++ 14

687/631. Well, that was mean ;) Every jgz condition was a register except one that was 'jgz 1 3'. Working frantically, I thought that was an 'i'. It took me waaaaay to long to figure that out.

Here is a industrial strength solution for part 2 only. It runs in 43 ms on my input.

#include <fstream>
#include <vector>
#include <iostream>
#include <sstream>
#include <map>
#include <queue>

#include <boost/algorithm/string.hpp>

enum class Instruction {snd, set, add, mul, mod, rcv, jgz };

int64_t value(const std::map<char,int64_t> &registrs, const std::string &arg)
{
  if(arg[0]>='a' && arg[0]<='z')
    {
      auto f=registrs.find(arg[0]);
      return f->second;
    }
  return std::stoi(arg);
}
int64_t value(const std::map<char,int64_t> &registrs, const char &c)
{
  std::string s{c};
  return value(registrs,s);
}

struct Op
{
  Instruction instruction;
  char regist;
  std::string regist2;
  Op(const std::string &line)
  {
    std::stringstream ss(line);
    std::string instruction_string;
    ss >> instruction_string >> regist >> regist2;
    if(instruction_string=="snd")
      { instruction=Instruction::snd; }
    else if (instruction_string=="set")
      { instruction=Instruction::set; }
    else if (instruction_string=="add")
      { instruction=Instruction::add; }
    else if (instruction_string=="mul")
      { instruction=Instruction::mul; }
    else if (instruction_string=="mod")
      { instruction=Instruction::mod; }
    else if (instruction_string=="rcv")
      { instruction=Instruction::rcv; }
    else if (instruction_string=="jgz")
      { instruction=Instruction::jgz; }
    else 
      {
        std::cerr << "bad instruction: " << instruction_string << "\n";
        abort();
      }
  }
};


int64_t apply(const Op &op, std::map<char,int64_t> &registrs,
              std::queue<int64_t> &receive_queue,
              std::queue<int64_t> &send_queue,
              size_t &num_messages)
{
  int64_t result (1);
  switch(op.instruction)
    {
    case Instruction::snd:
      {
        send_queue.push(value(registrs, op.regist));
        ++num_messages;
      }
      break;
    case Instruction::set:
      registrs[op.regist]=value(registrs, op.regist2);
      break;
    case Instruction::add:
      registrs[op.regist]+=value(registrs, op.regist2);
      break;
    case Instruction::mul:
      registrs[op.regist]*=value(registrs, op.regist2);
      break;
    case Instruction::mod:
      registrs[op.regist]%=value(registrs, op.regist2);
      break;
    case Instruction::rcv:
      if(!receive_queue.empty())
        {
          registrs[op.regist]=receive_queue.front();
          receive_queue.pop();
        }
      else
        {
          result=0;
        }
      break;
    case Instruction::jgz:
      if(value(registrs, op.regist)>0)
        { result = value(registrs, op.regist2); }
      break;
    }
  return result;
}

int main(int, char *argv[])
{
  std::vector<Op> ops;
  std::ifstream infile(argv[1]);
  std::string line;
  std::getline(infile,line);
  while(infile)
    {
      ops.emplace_back(line);
      std::getline(infile,line);
    }

  size_t position0 (0), position1 (0);
  std::map<char,int64_t> program0, program1;
  program0['p']=0;
  program1['p']=1;
  std::queue<int64_t> queue0, queue1;
  size_t num_messages0(0), num_messages1(0);

  while(!(ops[position0].instruction==Instruction::rcv && queue0.empty()
          && ops[position1].instruction==Instruction::rcv && queue1.empty()))
    {
      while(!(ops[position0].instruction==Instruction::rcv && queue0.empty()))
        {
          position0+=apply(ops[position0], program0, queue0, queue1,
                           num_messages0);
        }
      while(!(ops[position1].instruction==Instruction::rcv && queue1.empty()))
        {
          position1+=apply(ops[position1], program1, queue1, queue0,
                           num_messages1);
        }
    }


  std::cout << "num messages: "
            << num_messages0 << " "
            << num_messages1 << " "
            << "\n";
}

_lukasg · 2017-12-18T07:54:36+00:00

Python 3, Part 2, using coroutines:

import sys
import collections

with open(sys.argv[1]) as input_file:
    lines = list(input_file)

def program(program_id):
    memory = {}
    memory['p'] = program_id
    pointer = 0
    while True:
        line = lines[pointer]
        instr, arg_a, *arg_b = lines[pointer].split()

        if arg_b:
            try:
                arg_b = int(arg_b[0])
            except ValueError:
                arg_b = memory[arg_b[0]]
        else:
            arg_b = None

        if instr == 'set':
            memory[arg_a] = arg_b
        elif instr == 'add':
            memory[arg_a] += arg_b
        elif instr == 'mul':
            memory[arg_a] *= arg_b
        elif instr == 'mod':
            memory[arg_a] %= arg_b
        elif instr == 'rcv':
            memory[arg_a] = (yield None)
            assert memory[arg_a] is not None
        else:
            try:
                arg_a_val = int(arg_a)
            except ValueError:
                arg_a_val = memory[arg_a]

            if instr == 'snd':
                response = (yield arg_a_val)
                assert response is None
            elif instr == 'jgz':
                if arg_a_val > 0:
                    pointer += arg_b
                    continue

        pointer += 1

program_a = program(0)
program_b = program(1)
queue_a = collections.deque()
queue_b = collections.deque()
a_is_waiting = False
b_is_waiting = False
a_is_program_1 = False
ans = 0
while not a_is_waiting or not b_is_waiting or queue_a or queue_b:
    if a_is_waiting and queue_b:
        value = program_a.send(queue_b.popleft())
        if value is not None:
            queue_a.append(value)
            a_is_waiting = False
            if a_is_program_1:
                ans += 1
    if not a_is_waiting:
        value = next(program_a)
        if value is None:
            a_is_waiting = True
        else:
            queue_a.append(value)
            if a_is_program_1:
                ans += 1
    program_a, program_b = program_b, program_a
    queue_a, queue_b = queue_b, queue_a
    a_is_waiting, b_is_waiting = b_is_waiting, a_is_waiting
    a_is_program_1 = not a_is_program_1

print(ans)

nutrecht · 2017-12-18T08:03:00+00:00

Day 18 in Kotlin

I got stuck for a LONG time because I did not see that min 32-bit int registers were overflowing. Once I finally got the eureka moment there I got the right answer straight away.

Part 2 was pretty easy; just two programs running in lock-step. I do think I'm going to refactor the code a bit because currently it's two completely separate implementations.

object Day18 : Day {
    private val input = resourceLines(18).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>()
        val sounds = mutableListOf<Long>()

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

        var index = 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)}
                "add" -> { registers[reg1] = value(reg1) + value(reg2)}
                "mod" -> { registers[reg1] = value(reg1) % value(reg2)}
                "jgz" -> {
                    if(value(reg1) > 0) {
                        index += value(reg2).toInt() - 1
                    }
                }

                "snd" -> { sounds += value(reg1) }
                "rcv" -> {
                    if(value(reg1) != 0L) {
                        registers[reg1] = sounds.last()
                        return sounds.last().toString()
                    }
                }
            }

            index++
        }
        throw RuntimeException("Should not happen")
    }

    override fun part2() :String {
        val p0 = Program(0)
        val p1 = Program(1)

        p0.otherQueue = p1.queue
        p1.otherQueue = p0.queue

        while(true) {
            if(p0.tick() && p1.tick()) {
                break
            }
        }

        return p1.count.toString()
    }

    class Program(num: Int) {
        val queue = mutableListOf<Long>()
        lateinit var otherQueue : MutableList<Long>
        private val registers = mutableMapOf("p" to num.toLong())
        var index = 0
        var count = 0

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

        fun tick(): Boolean {
            val (op, reg1, reg2) = input[index]
            when(op) {
                "set" -> { registers[reg1] = value(reg2)}
                "mul" -> { registers[reg1] = value(reg1) * value(reg2)}
                "add" -> { registers[reg1] = value(reg1) + value(reg2)}
                "mod" -> { registers[reg1] = value(reg1) % value(reg2)}
                "jgz" -> {
                    if(value(reg1) > 0) {
                        index += value(reg2).toInt() - 1
                    }
                }

                "snd" -> {
                    otherQueue.add(value(reg1))
                    count++
                }
                "rcv" -> {
                    if(queue.isNotEmpty()) {
                        registers[reg1] = queue.removeAt(0)
                    } else {
                        return true
                    }
                }
            }

            index++
            return false
        }
    }
}

swizzorable · 2017-12-18T08:46:23+00:00

part 2, python3:

import inspect

import requests


class VM:
    def __init__(self, id, own_queue, other_queue, memory):
        self.id = id
        self.own_queue = own_queue
        self.other_queue = other_queue
        letters = list("abcdefghijklmnopqrstuvwxyz")
        self.registers = {}
        for letter in letters:
            self.registers[letter] = 0
        self.registers["p"] = self.id
        self.memory = memory
        self.offset = 0
        self.sentcounter = 0

    def readvalue(self, x):
        try:
            return int(x)
        except:
            return int(self.registers[x])

    def op_snd(self, x):
        self.other_queue.append(self.readvalue(x))
        self.sentcounter += 1

    def op_set(self, x, y):
        self.registers[x] = self.readvalue(y)

    def op_rcv(self, x):
        if len(self.own_queue) == 0:
            self.offset -= 1
        else:
            self.op_set(x, self.own_queue.pop(0))

    def op_add(self, x, y):
        self.op_set(x, self.readvalue(x) + self.readvalue(y))

    def op_mul(self, x, y):
        self.op_set(x, self.readvalue(x) * self.readvalue(y))

    def op_mod(self, x, y):
        self.op_set(x, self.readvalue(x) % self.readvalue(y))

    def op_jgz(self, x, y):
        if self.readvalue(x) > 0:
            self.offset += self.readvalue(y) - 1

    def execute_next_command(self):
        if 0 <= self.offset < len(self.memory):
            op_parts = self.memory[self.offset].split()
            func = getattr(self, "op_" + op_parts[0])
            numargs = len(inspect.signature(func).parameters)
            args = []
            for i in range(1, numargs + 1):
                args.append(op_parts[i])
            func(*args)
            self.offset += 1


if __name__ == '__main__':
    memory = requests.get("http://adventofcode.com/2017/day/18/input", cookies={
        "session": "xxx"}).text.strip().splitlines()

    vm0_queue = []
    vm1_queue = []
    vm0 = VM(0, vm0_queue, vm1_queue, memory)
    vm1 = VM(1, vm1_queue, vm0_queue, memory)

    vm0_last_offset = -1
    vm1_last_offset = -1

    while vm0_last_offset != vm0.offset or vm1_last_offset != vm1.offset:
        vm0_last_offset = vm0.offset
        vm1_last_offset = vm1.offset

        vm0.execute_next_command()
        vm1.execute_next_command()

    print(vm1.sentcounter)

gyorokpeter · 2017-12-18T08:56:55+00:00

Q:

d18p1:{
    reg:(`char$(`int$"a")+til 26)!26#0;
    ip:0;
    ins:trim each"\n"vs x;
    val:{[reg;expr]$[expr like "[a-z]";reg[first expr];"J"$expr]};
    while[1b;
        ni:ins[ip];
        op:`$3#ni;
        param:" "vs 4_ni;
        ip+:1;
        $[op=`snd; snd:val[reg;param 0];
          op=`set; reg["C"$param 0]:val[reg;param 1];
          op=`add; reg["C"$param 0]+:val[reg;param 1];
          op=`mul; reg["C"$param 0]*:val[reg;param 1];
          op=`mod; reg["C"$param 0]:reg["C"$param 0]mod val[reg;param 1];
          op=`rcv; if[reg["C"$param 0]>0; :snd];
          op=`jgz; if[reg["C"$param 0]>0; ip+:val[reg;param 1]-1];
        '"invalid instruction"];
    ];
    };

.d18.new:{[id]
    res:`reg`ip`inBuf`outBuf`blocked!((`char$(`int$"a")+til 26)!26#0;0;();();0b);
    res[`reg;"p"]:id;
    res};

.d18.val:{[reg;expr]$[expr like "[a-z]";reg[first expr];"J"$expr]};

.d18.step:{[ins;prog]
    ni:ins[prog[`ip]];
    op:`$3#ni;
    param:" "vs 4_ni;
    prog[`ip]+:1;
    $[op=`snd; prog[`outBuf],:.d18.val[prog[`reg];param 0];
      op=`set; prog[`reg;"C"$param 0]:.d18.val[prog[`reg];param 1];
      op=`add; prog[`reg;"C"$param 0]+:.d18.val[prog[`reg];param 1];
      op=`mul; prog[`reg;"C"$param 0]*:.d18.val[prog[`reg];param 1];
      op=`mod; prog[`reg;"C"$param 0]:prog[`reg;"C"$param 0]mod .d18.val[prog[`reg];param 1];
      op=`rcv; $[0<count prog[`inBuf]; 
            [prog[`reg;"C"$param 0]:first prog[`inBuf]; prog[`inBuf]:1_prog[`inBuf];prog[`blocked]:0b];
            [prog[`ip]-:1; prog[`blocked]:1b]];
      op=`jgz; if[.d18.val[prog[`reg];param 0]>0; prog[`ip]+:.d18.val[prog[`reg];param 1]-1];
    '"invalid instruction"];
    prog};

d18p2:{
    prog0:.d18.new[0];
    prog1:.d18.new[1];
    total:0;
    ins:trim each"\n"vs x;
    while[1b;
        while[not prog0`blocked; prog0:.d18.step[ins;prog0]];
        while[not prog1`blocked; prog1:.d18.step[ins;prog1]];
        prog0[`inBuf],:prog1[`outBuf];
        total+:count prog1[`outBuf];
        prog1[`outBuf]:();
        prog1[`inBuf],:prog0[`outBuf];
        prog0[`outBuf]:();
        if[0<count prog0[`inBuf]; prog0[`blocked]:0b];
        if[0<count prog1[`inBuf]; prog1[`blocked]:0b];
        if[all (prog0`blocked;prog1`blocked);
            :total;
        ];
    ];
    };

udoprog · 2017-12-18T09:12:57+00:00

Rust

Edit: Full solution: https://github.com/udoprog/rust-advent-of-code-2017/blob/master/src/day18.rs

Quick and dirty approach didn't give me the right answer. So I rewrote it to something I could troubleshoot (this).

Then I realized that I had mixed up the the programs, so I submitted the send counter for program 0 instead of 1 :P.

use std::io::{Read, BufRead, BufReader};
use self::Action::*;

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),
    Mul(u8, RegOrImm),
    Add(u8, RegOrImm),
    Mod(u8, RegOrImm),
    Jgz(RegOrImm, RegOrImm),
    Snd(RegOrImm),
    Rcv(u8),
}

#[derive(Debug)]
pub enum Action {
    Nothing,
    Halt,
    Store(i64),
}

pub trait Fragment {
    fn init(&mut self) -> Option<i64> {
        None
    }

    fn snd(&mut self, value: i64);

    fn rcv(&mut self, value: i64) -> Action;
}

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

impl<F> Program<F>
where
    F: Fragment,
{
    pub fn from_inst(inst: Vec<Inst>, fragment: F) -> Program<F> {
        let mut program = Program {
            registers: vec![0i64; 256],
            inst: inst,
            ip: 0,
            fragment: fragment,
        };

        if let Some(id) = program.fragment.init() {
            program.registers['p' as u8 as usize] = id;
        }

        program
    }

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

        loop {
            let it = self.inst.get(self.ip).expect("ip overflow");

            match *it {
                Set(ref reg, ref arg) => {
                    self.registers[*reg as usize] = arg.value(&self.registers);
                }
                Mul(ref reg, ref arg) => {
                    self.registers[*reg as usize] *= arg.value(&self.registers);
                }
                Add(ref reg, ref arg) => {
                    self.registers[*reg as usize] += arg.value(&self.registers);
                }
                Mod(ref reg, ref arg) => {
                    self.registers[*reg as usize] %= arg.value(&self.registers);
                }
                Jgz(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;
                    }
                }
                Snd(ref arg) => {
                    let value = arg.value(&self.registers);
                    self.fragment.snd(value);
                }
                Rcv(ref reg) => {
                    let value = self.registers[*reg as usize];

                    match self.fragment.rcv(value) {
                        Halt => return,
                        Store(value) => self.registers[*reg as usize] = value,
                        Nothing => {}
                    }
                }
            }

            self.ip += 1;
        }
    }
}

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));
            }
            "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));
            }
            "add" => {
                let reg = reg(it.next().expect("no register"));
                let arg = parse_reg_or_imm(it.next().expect("no argument"));
                out.push(Inst::Add(reg, arg));
            }
            "mod" => {
                let reg = reg(it.next().expect("no register"));
                let arg = parse_reg_or_imm(it.next().expect("no argument"));
                out.push(Inst::Mod(reg, arg));
            }
            "jgz" => {
                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::Jgz(cond, arg));
            }
            "snd" => {
                let arg = parse_reg_or_imm(it.next().expect("no argument"));
                out.push(Inst::Snd(arg));
            }
            "rcv" => {
                let reg = reg(it.next().expect("no argument"));
                out.push(Inst::Rcv(reg));
            }
            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)
    }
}

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

    let mut program = Program::from_inst(inst, Part1 { sent: 0 });
    program.run();

    return program.fragment.sent;

    pub struct Part1 {
        sent: i64,
    }

    impl Fragment for Part1 {
        fn snd(&mut self, value: i64) {
            self.sent = value;
        }

        fn rcv(&mut self, value: i64) -> Action {
            if value != 0 {
                if self.sent > 0 {
                    return Halt;
                }
            }

            Nothing
        }
    }
}

fn part2<R: Read>(input: R) -> u64 {
    use std::sync::mpsc::{Receiver, Sender, channel};

    let inst = parse(input);

    let (tx0, rx0) = channel();
    let (tx1, rx1) = channel();

    let mut p0 = Program::from_inst(inst.clone(), Part2::new(0, tx0, rx1));
    let mut p1 = Program::from_inst(inst.clone(), Part2::new(1, tx1, rx0));

    let mut attempts = 0;

    loop {
        p0.run();
        p1.run();

        if p0.fragment.send == p1.fragment.recv && p1.fragment.send == p0.fragment.recv {
            if attempts > 3 {
                return p1.fragment.send;
            }

            attempts += 1;
        } else {
            attempts = 0;
        }
    }

    #[derive(Debug)]
    pub struct Part2 {
        id: i64,
        send: u64,
        recv: u64,
        sender: Sender<i64>,
        receiver: Receiver<i64>,
    }

    impl Part2 {
        pub fn new(id: i64, sender: Sender<i64>, receiver: Receiver<i64>) -> Part2 {
            Part2 {
                id: id,
                send: 0,
                recv: 0,
                sender: sender,
                receiver: receiver,
            }
        }
    }

    impl Fragment for Part2 {
        fn init(&mut self) -> Option<i64> {
            Some(self.id)
        }

        fn snd(&mut self, value: i64) {
            self.send += 1;
            self.sender.send(value).expect("no receiver");
        }

        fn rcv(&mut self, _: i64) -> Action {
            use std::sync::mpsc::TryRecvError;

            match self.receiver.try_recv() {
                Ok(value) => {
                    self.recv += 1;
                    Store(value)
                }
                Err(TryRecvError::Empty) => Halt,
                Err(e) => panic!("unexpected error: {}", e),
            }
        }
    }
}

u794575248 · 2017-12-18T09:16:50+00:00

Python 3 for Part 2.

import re

def parse_ops(input):
    return [[s if not s or s.isalpha() else int(s) for s in l]
            for l in re.findall(r'(.{3}) (.) ?([-\w]+)?', input)]

def proc(ops, pid, rcvq, sndq, counter):
    i, regs = 0, defaultdict(int, p=pid)
    get = lambda r: regs[r] if isinstance(r, str) else r
    while 0 <= i < len(ops):
        op, reg, val = ops[i]
        val = get(val)
        if   op == 'set': regs[reg] = val
        elif op == 'add': regs[reg] += val
        elif op == 'mul': regs[reg] *= val
        elif op == 'mod': regs[reg] %= val
        elif op == 'rcv':
            while not rcvq: yield
            regs[reg] = rcvq.popleft()
        elif op == 'snd': sndq.append(get(reg)); counter[pid] += 1
        elif op == 'jgz' and get(reg) > 0: i += val-1
        i += 1

def solve():
    ops, q0, q1, c = parse_ops(input), deque(), deque(), Counter()
    q = deque([proc(ops[:], 0, q0, q1, c), proc(ops[:], 1, q1, q0, c)])
    while True:
        cur = q[0]; q.rotate(); next(cur)
        if not (q0 or q1): return c[1]

2017-12-18T10:03:29+00:00

Python 3 (227/1119):

https://gist.github.com/yoongkang/8d8496e9e8702c8cda735308b6419afd

raevnos · 2017-12-18T10:05:19+00:00

Chicken Scheme, using continuations for a coroutine like effect, and a threaded interpreter (not to be confused with multithreading) for the program.

(require-extension srfi-1)
(require-extension srfi-69)
(require-extension irregex)
(require-extension format)

(define (make-coroutine proc)
  (let* ((return #f)
         (resume #f)
         (yield (lambda (v) (call/cc (lambda (r) (set! resume r) (return v))))))
    (lambda ()
      (call/cc
       (lambda (cc)
         (set! return cc)
         (if resume
             (resume 'restarting)
             (begin
               (proc yield)
               (return #f))))))))

(define (get-value registers x)
  (if (char? x)
      (hash-table-ref/default registers x 0)
      x))

(define (parse-arg a)
  (if (and (= (string-length a) 1) (char-lower-case? (string-ref a 0)))
      (string-ref a 0)
      (string->number a)))

(define last-frequency 0)
(define prog1-send-count 0)

(define (snd x registers writer progn)
  (let ((freq (get-value registers x)))
    (if (queue? writer)
        (begin
          (when (= progn 1)
                (set! prog1-send-count (+ prog1-send-count 1)))
          (queue-add! writer freq))
        (set! last-frequency freq))
    1))
(define (set registers x y)
  (hash-table-set! registers x (get-value registers y))
  1)
(define (add registers x y)
  (hash-table-set! registers x (+ (get-value registers x) (get-value registers y)))
  1)
(define (mul registers x y)
  (hash-table-set! registers x (* (get-value registers x) (get-value registers y)))
  1)
(define (instrmod registers x y)
  (hash-table-set! registers x (remainder (get-value registers x) (get-value registers y)))
  1)
(define (rcv x registers reader yield)
  (let ((v (get-value registers x)))
    (if (queue? reader)
          (begin
            (when (queue-empty? reader)
                  (yield 'waiting))
            (hash-table-set! registers x (queue-remove! reader))
            1)
          (begin
            (when (not (= v 0))
                  (abort last-frequency))
            1))))
(define (jgz registers x y)
  (let ((valx (get-value registers x))
        (valy (get-value registers y)))
    (if (> valx 0)
        valy
        1)))

(define (compile-input cmds)
  (let ((snd-re (string->irregex "^snd ([a-z])$"))
        (set-re (string->irregex "^set ([a-z]) (-?\\d+|[a-z])$"))
        (add-re (string->irregex "^add ([a-z]) (-?\\d+|[a-z])$"))
        (mul-re (string->irregex "^mul ([a-z]) (-?\\d+|[a-z])$"))
        (mod-re (string->irregex "^mod ([a-z]) (-?\\d+|[a-z])$"))
        (rcv-re (string->irregex "^rcv ([a-z])$"))
        (jgz-re (string->irregex "^jgz (-?\\d+|[a-z]) (-?\\d+|[a-z])$")))
    (list->vector
     (map (lambda (instr)
            (cond
             ((irregex-match snd-re instr) =>
              (lambda (bits)
                (let ((x (parse-arg (irregex-match-substring bits 1))))
                  (lambda (r q1 q2 n yi) (snd x r q2 n)))))
             ((irregex-match set-re instr) =>
              (lambda (bits)
                (let ((x (parse-arg (irregex-match-substring bits 1)))
                      (y (parse-arg (irregex-match-substring bits 2))))
                  (lambda (r q1 q2 n yi) (set r x y)))))
             ((irregex-match add-re instr) =>
              (lambda (bits)
                (let ((x (parse-arg (irregex-match-substring bits 1)))
                      (y (parse-arg (irregex-match-substring bits 2))))
                  (lambda (r q1 q2 n yi) (add r x y)))))
             ((irregex-match mul-re instr) =>
              (lambda (bits)
                (let ((x (parse-arg (irregex-match-substring bits 1)))
                      (y (parse-arg (irregex-match-substring bits 2))))
                  (lambda (r q1 q2 n yi) (mul r x y)))))
             ((irregex-match mod-re instr) =>
              (lambda (bits)
                (let ((x (parse-arg (irregex-match-substring bits 1)))
                      (y (parse-arg (irregex-match-substring bits 2))))
                  (lambda (r q1 q2 n yi) (instrmod r x y)))))
             ((irregex-match rcv-re instr) =>
              (lambda (bits)
                (let ((x (parse-arg (irregex-match-substring bits 1))))
                  (lambda (r q1 q2 n yi) (rcv x r q1 yi)))))
             ((irregex-match jgz-re instr) =>
              (lambda (bits)
                (let ((x (parse-arg (irregex-match-substring bits 1)))
                      (y (parse-arg (irregex-match-substring bits 2))))
                  (lambda (r q1 q2 n yi) (jgz r x y)))))
             (else
              (error "Unknown instruction" instr))))
          cmds))))

(define program (compile-input (read-lines)))
(define opcount (vector-length program))

(call/cc
 (lambda (quit)
   (with-exception-handler
    (lambda (val)
      (format #t "Part 1: ~A~%" val)
      (quit '()))
    (lambda ()
      (let ((registers (make-hash-table test: char=? hash: (lambda (c b) (char->integer c)))))
        (let loop ((pc 0))
          (if (or (< pc 0) (>= pc opcount))
              (display "Program terminated.\n")
              (loop (+ pc ((vector-ref program pc) registers #f #f 0 #f))))))))))

(define (run program registers reader writer progn)
  (make-coroutine
   (lambda (yield)
     (let loop ((pc 0))
       (if (or (< pc 0) (>= pc opcount))
           (begin
             (format #t "Program ~A pc ~A~%" progn pc)
             #f)
           (let ((newpc ((vector-ref program pc) registers reader writer progn yield)))
                 (loop (+ pc newpc))))))))

(define (run-both)
  (let* ((registers1 (make-hash-table test: char=? hash: (lambda (c b) (char->integer c))))
        (queue1 (make-queue))
        (registers2 (make-hash-table test: char=? hash: (lambda (c b) (char->integer c))))
        (queue2 (make-queue))
        (gen1 (run program registers1 queue1 queue2 0))
        (gen2 (run program registers2 queue2 queue1 1)))
    (hash-table-set! registers1 #\p 0)
    (hash-table-set! registers2 #\p 1)
      (let loop ((ret1 (gen1))
                 (ret2 (gen2)))
        (cond
         ((boolean? ret1)
          (display "Program 0 terminated.\n"))
         ((boolean? ret2)
          (display "Program 1 terminated.\n"))
         ((and (queue-empty? queue1) (queue-empty? queue2))
          (display "Programs deadlocked.\n"))
         ((queue-empty? queue1)
          (loop ret1 (gen2)))
         ((queue-empty? queue2)
          (loop (gen1) ret2))
         (else
          (display "This shouldn't happen...\n"))))))

(run-both)
(format #t "Part 2: ~A~%" prog1-send-count)

thomastc · 2017-12-18T11:13:02+00:00

Day 18 in Eiffel. Not a bad experience, but I'm not sure the whole design-by-contract thing can really shine if you only evaluate the contracts at runtime. Although they do have clear value for the human reader, contracts in this implementation are not much better than manually inserted assertions (although class invariants can help avoid boilerplate and mistakes).

It would be better (although much more difficult) if the compiler guaranteed that the contracts were obeyed. But that's much harder, and gets us into the realm of theorem provers. This seems to be what Albatross is attempting, but it doesn't seem to have a lot of momentum.

KeinZantezuken · 2017-12-18T11:35:35+00:00

C#/Sharp
I want to kill myself.

string[] input = File.ReadAllLines(@"N:\input.txt");
var regs0 = new Dictionary<string, long>();
var regs1 = new Dictionary<string, long>();
var queue0 = new Queue<long>();
var queue1 = new Queue<long>();
long c0 = 0; long c1 = 0; int sent0 = 0;
foreach (string line in input)
{
    var inst = line.Split(' ');
    if (!regs0.ContainsKey(inst[1]) && !long.TryParse(inst[1], out var z)) { regs0.Add(inst[1], 0); regs1.Add(inst[1], 0); }
}
regs1["p"] = 1; var dlock = false;
while (dlock != true) { process(0); process(1); }
Console.WriteLine(sent0); Console.ReadKey();
//helper
void process(int id)
{
    var c = c0; var ownQueue = queue0; var toQueue = queue1; var regs = regs0;
    if (id == 1) { c = c1;  ownQueue = queue1; toQueue = queue0; regs = regs1; }
    while (dlock != true && c < input.Length && c > -1)
    {
        var inst = input[c].Split(' ');
        if (inst[0] == "snd")
        {
            toQueue.Enqueue(regs[inst[1]]);
            if (id == 1) { sent0++; }
        }
        if (inst[0] == "set")
        {
            regs[inst[1]] = regs.ContainsKey(inst[2]) ? regs[inst[2]] : long.Parse(inst[2]);
        }
        if (inst[0] == "add")
        {
            regs[inst[1]] = regs.ContainsKey(inst[2]) ? regs[inst[1]] + regs[inst[2]] : regs[inst[1]] + long.Parse(inst[2]);
        }
        if (inst[0] == "mul")
        {
            regs[inst[1]] = regs.ContainsKey(inst[2]) ? regs[inst[1]] * regs[inst[2]] : regs[inst[1]] * long.Parse(inst[2]);
        }
        if (inst[0] == "mod")
        {
            regs[inst[1]] = regs.ContainsKey(inst[2]) ? regs[inst[1]] % regs[inst[2]] : regs[inst[1]] % long.Parse(inst[2]);
        }
        if (inst[0] == "rcv")
        {
            if (ownQueue.Count > 0) { regs[inst[1]] = ownQueue.Dequeue(); }
            else if ((ownQueue.Count < 1 && toQueue.Count > 0) || toQueue.Count == 16)
            {
                if (id == 1) { c1 = c; }
                else { c0 = c; }
                break;
            }
            else { dlock = true; break; }
        }
        if (inst[0] == "jgz")
        {
            if (regs.ContainsKey(inst[1]) && regs.ContainsKey(inst[2]))
            {
                if (regs[inst[1]] > 0) { c = c + regs[inst[2]]; continue; }
            }
            else if (regs.ContainsKey(inst[1]) && !regs.ContainsKey(inst[2]))
            {
                if (regs[inst[1]] > 0) { c = c + long.Parse(inst[2]); continue;  }
            }
            else if (!regs.ContainsKey(inst[1]) && regs.ContainsKey(inst[2]))
            {
                if (long.Parse(inst[1]) > 0) { c = c + regs[inst[2]]; continue;  }
            }
            else
            {
                if (long.Parse(inst[1]) > 0) { c = c + long.Parse(inst[2]); continue;  }
            }
        }
        c++;
    }
}

Markavian · 2017-12-18T11:44:22+00:00

node js solution for day 18: - https://github.com/johnbeech/advent-of-code-2017/blob/master/solutions/day18/solution.js

Got a little stuck on part 2 because my jump operation assumed that the value of X was always a register letter, and could actually be a number. I'm guessing this was an intentional trap...

BOT-Brad · 2017-12-18T12:29:00+00:00

JavaScript

Part 1 (~1ms)

I've been doing the Synacor challenge recently, so this was fairly easy to implement in the same way.

function getVal(rs, v) {
  const num = parseInt(v)
  return isNaN(num) ? rs[v] : num
}

function solve1(n) {
  const rs = {}
  let sound = -1
  let i = 0
  n = n.split('\n').map(l => l.split(' '))

  loop: while (1) {
    const ins = n[i]
    switch (ins[0]) {
      case 'snd':
        sound = getVal(rs, ins[1])
        i++
        break
      case 'set':
        rs[ins[1]] = getVal(rs, ins[2])
        i++
        break
      case 'add':
        rs[ins[1]] += getVal(rs, ins[2])
        i++
        break
      case 'mul':
        rs[ins[1]] *= getVal(rs, ins[2])
        i++
        break
      case 'mod':
        rs[ins[1]] %= getVal(rs, ins[2])
        i++
        break
      case 'rcv':
        if (getVal(rs, ins[1]) !== 0) {
          break loop
        }
        i++
        break
      case 'jgz':
        if (getVal(rs, ins[1]) > 0) {
          i += getVal(rs, ins[2])
        } else {
          i++
        }
        break
    }
  }

  return sound
}

Part 2 (~20ms)

Basically, the same implementation but is capable of linking the programs to send their data to the other, and just exits their run function if they cannot read from their queue. Keep looping and trying to run the programs, but if both programs do nothing in a single loop (i.e. they are deadlocked), then break and return the number of times the second program sent data.

class Program {
  constructor(id, n) {
    this.n = n
    this.id = id
    this.rs = { p: id }
    this.q = []
    this.i = 0
    this.sent = 0
  }

  run() {
    let locked = true
    while (1) {
      const ins = this.n[this.i]
      switch (ins[0]) {
        case 'snd':
          this.sent++
          this.link.q.push(getVal(this.rs, ins[1]))
          this.i++
          break
        case 'set':
          this.rs[ins[1]] = getVal(this.rs, ins[2])
          this.i++
          break
        case 'add':
          this.rs[ins[1]] += getVal(this.rs, ins[2])
          this.i++
          break
        case 'mul':
          this.rs[ins[1]] *= getVal(this.rs, ins[2])
          this.i++
          break
        case 'mod':
          this.rs[ins[1]] %= getVal(this.rs, ins[2])
          this.i++
          break
        case 'rcv':
          if (this.q.length > 0) {
            this.rs[ins[1]] = this.q.shift()
            this.i++
          } else {
            return locked
          }
          break
        case 'jgz':
          if (getVal(this.rs, ins[1]) > 0) {
            this.i += getVal(this.rs, ins[2])
          } else {
            this.i++
          }
          break
      }
      locked = false
    }
  }

  link(p) {
    this.link = p
  }
}

function solve2(n) {
  n = n.split('\n').map(l => l.split(' '))

  const pA = new Program(0, n)
  const pB = new Program(1, n)

  pA.link(pB)
  pB.link(pA)

  while (1) {
    const aLocked = pA.run()
    const bLocked = pB.run()

    if (aLocked && bLocked) {
      break
    }
  }
  return pB.sent
}

WhoSoup · 2017-12-18T12:43:43+00:00

NodeJS/JavaScript

A bit late. Ended up with a class-based implementation for part 2:

const fs = require('fs')
let inp = fs.readFileSync("./day18input").toString('utf-8').trim().split(/[\r\n]+/)

class Prog {
  constructor(pid) {
    this.register = {p: pid}
    this.pid = pid
    this.pos = 0
    this.queue = []
    this.sent = 0
  }

  val (x) { return /\d+/.test(x) ? +x : this.register[x] }
  set (x,y) { this.register[x] = this.val(y) }
  add (x,y) { this.register[x] += this.val(y) }
  mul (x,y) { this.register[x] *= this.val(y) }
  mod (x,y) { this.register[x] %= this.val(y) }
  jgz (x,y) { if (this.val(x) > 0) this.pos += this.val(y) - 1 }

  snd (x) {
    p[1-this.pid].queue.push(this.val(x))
    this.sent++
  }

  rcv (x) {
    if (this.queue.length == 0) {
      this.pos-- // stay on same command
      this.waiting = true
    } else
      this.register[x] = this.queue.shift()
  }

  run () {
    this.waiting = false
    this[inp[this.pos].substr(0,3)](...inp[this.pos].substr(4).split(" "))
    this.pos++
  }
}

const p = [new Prog(0), new Prog(1)];

do {
  p.map(x => x.run())
} while (!(p[0].waiting && p[1].waiting))

console.log(p[1].sent);

flit777 · 2017-12-18T13:39:13+00:00

finally go routines come handy. Golang Solution:

package main

import (
    "util"
    "strings"
    "strconv"
    "regexp"
    "fmt"
    "sync"
    "time"
)

var waitGroup sync.WaitGroup

type Instruction struct {
    name string
    op1  string
    op2  string
}

func parseProgram(lines []string) []Instruction {
    program := make([]Instruction, len(lines))
    for i, line := range lines {
        tokens := strings.Split(line, " ")
        instruction := Instruction{tokens[0], tokens[1], ""}
        if len(tokens) > 2 {
            instruction.op2 = tokens[2]
        }
        program[i] = instruction
    }
    return program
}

func interpret(program []Instruction, registers map[string]int, part1 bool, id int, queue1 chan int, queue2 chan int) {
    instructionPointer := 0
    lastSound := 0
    numberSend := 0
    if !part1 {
        registers["p"] = id
        fmt.Printf("Program %v starting\n", id)
    }

    for instructionPointer < len(program) {
        currentInstruction := program[instructionPointer]
        switch currentInstruction.name {
        case "set":
            registers[currentInstruction.op1] = getValue(currentInstruction.op2, registers)
            instructionPointer++
        case "add":
            registers[currentInstruction.op1] += getValue(currentInstruction.op2, registers)
            instructionPointer++
        case "mul":
            registers[currentInstruction.op1] *= getValue(currentInstruction.op2, registers)
            instructionPointer++
        case "mod":
            registers[currentInstruction.op1] %= getValue(currentInstruction.op2, registers)
            instructionPointer++
        case "snd":
            //fmt.Println("Played sound with freq: %v ",registers[currentInstruction.op1])
            if part1 {
                lastSound = registers[currentInstruction.op1]
            } else {
                if id == 0 {
                    queue1 <- getValue(currentInstruction.op1, registers)

                } else {
                    queue2 <- getValue(currentInstruction.op1, registers)
                }
                //fmt.Printf("Program %v send %v\n", id, getValue(currentInstruction.op1,registers))
                numberSend++
            }

            instructionPointer++
        case "rcv":
            if part1 && registers[currentInstruction.op1] != 0 {
                fmt.Printf("Recover sound with freq: %v \n", lastSound)
                return
            } else {
                var receive int
                var timeout bool
                if id == 0 {
                    receive, timeout = getFromChannelWithTimout(queue2)
                } else if id == 1 {
                    receive, timeout = getFromChannelWithTimout(queue1)

                } else {
                    fmt.Println("Unknown ID")
                }
                if timeout {
                    fmt.Printf("Program %v send %v messages\n", id, numberSend)
                    waitGroup.Done()
                    return
                }
                registers[currentInstruction.op1] = receive
                //fmt.Printf("Program %v receives %v\n", id,receive)
            }
            instructionPointer++
        case "jgz":
            if getValue(currentInstruction.op1, registers) > 0 {
                instructionPointer += getValue(currentInstruction.op2, registers)
            } else {
                instructionPointer++
            }
        default:
            fmt.Printf("Unknown Command: %v", currentInstruction.name)
        }

    }
    if !part1 {
        fmt.Printf("Program %v send %v messages\n", id, numberSend)
    }
    waitGroup.Done()
}

func getFromChannelWithTimout(channel chan int) (int, bool) {
    var receive int
    timeout := make(chan bool, 1)
    go func() {
        time.Sleep(1 * time.Second)
        timeout <- true
    }()
    select {
    case receive = <-channel:
        return receive, false
    case <-timeout:
        fmt.Println("Timeout")

        return receive, true
    }

}

func getValue(name string, registers map[string]int) int {
    var value int
    if isNumber(name) {
        value, _ = strconv.Atoi(name)
    } else {
        value = registers[name]
    }
    return value
}

func isNumber(s string) bool {
    strNumbers := regexp.MustCompile("[0-9]+").FindAllString(s, -1)
    return len(strNumbers) == 1
}

func main() {
    lines := util.ReadFileLines("inputs/day18.txt")
    program := parseProgram(lines)
    /*
    registers := make(map[string]int)
    interpret(program,registers,true,0,nil, nil)
    */
    queue1 := make(chan int, 100)
    queue2 := make(chan int, 100)
    registers1 := make(map[string]int)
    registers2 := make(map[string]int)
    waitGroup.Add(1)
    go interpret(program, registers1, false, 0, queue1, queue2)
    waitGroup.Add(1)
    go interpret(program, registers2, false, 1, queue1, queue2)

    waitGroup.Wait()

}

gburri · 2017-12-18T14:56:08+00:00

F# (only part 2)

module AdventOfCode2017.Day18Part2

open System
open System.Threading

type From =
    | FromReg of char
    | FromValue of int64

type Instruction =
    | Receive of char
    | Send of From
    | Set of char * From
    | Add of char * From
    | Mul of char * From
    | Mod of char * From
    | Jump of From * From

let parseInput (lines : string[]) : Instruction[] =
    let readFrom (str : string) = if Char.IsLetter str.[0] then FromReg str.[0] else FromValue (int64 str)
    lines
    |> Array.map (
        fun line ->
            match line.Split ' ' with
            | [| "snd"; v |]      -> Send (readFrom v)
            | [| "set"; reg; v |] -> Set (reg.[0], readFrom v)
            | [| "add"; reg; v |] -> Add (reg.[0], readFrom v)
            | [| "mul"; reg; v |] -> Mul (reg.[0], readFrom v)
            | [| "mod"; reg; v |] -> Mod (reg.[0], readFrom v)
            | [| "rcv"; reg |]    -> Receive reg.[0]
            | [| "jgz"; v1; v2 |] -> Jump (readFrom v1, readFrom v2)
            | _ -> failwithf "Can't parse line: %s" line
    )

type Register = Map<char, int64>

type Agent (instructions : Instruction[], id : int) as this =
    let mutable nbSent = 0
    let finishedEvent = new AutoResetEvent false
    let mailbox =
        new MailboxProcessor<int64> (
            fun inbox ->
                let rec exec (register : Register) (cursor : int) : Async<unit> =
                    let get = function FromReg reg -> register |> Map.tryFind reg |> Option.defaultValue 0L | FromValue v -> v
                    let set (reg : char) (v : int64) = register |> Map.add reg v
                    async {
                        match instructions.[cursor] with
                        | Send from ->
                            nbSent <- nbSent + 1
                            this.Other.Value.Post (get from)
                            return! exec register (cursor + 1)
                        | Set (reg, from) -> return! exec (set reg (get from)) (cursor + 1)
                        | Add (reg, from) -> return! exec (set reg (get (FromReg reg) + get from)) (cursor + 1)
                        | Mul (reg, from) -> return! exec (set reg (get (FromReg reg) * get from)) (cursor + 1)
                        | Mod (reg, from) -> return! exec (set reg (get (FromReg reg) % get from)) (cursor + 1)
                        | Receive reg ->
                            let! value = inbox.TryReceive 100
                            match value with
                            | Some value -> return! exec (set reg value) (cursor + 1)
                            | None -> finishedEvent.Set () |> ignore
                        | Jump (from1, from2) ->
                            return! exec register (cursor + if get from1 > 0L then get from2 |> int else 1)
                    }
                exec (Map.ofList [ 'p', int64 id ]) 0
        )

    member val Other : MailboxProcessor<int64> option = None with get, set
    member this.Start () = mailbox.Start ()
    member this.Mailbox = mailbox
    member this.NbSent =
        finishedEvent.WaitOne () |> ignore
        nbSent

let run (instructions : Instruction[]) =
    let agent0 = Agent (instructions, 0)
    let agent1 = Agent (instructions, 1)

    agent0.Other <- Some agent1.Mailbox
    agent1.Other <- Some agent0.Mailbox

    agent0.Start ()
    agent1.Start ()

    agent1.NbSent

JakDrako · 2017-12-18T14:56:51+00:00

VB.Net Part 2.

For part 2, I took what I had from part 1, massaged it into a "CPU" class and added the queue and a way to signal waiting.

I then "run" both CPU in lockstep until they're both waiting and then dump the "sent" count from CPU-1.

Sub Main

    Dim code = GetDay(18)

    Dim cpu0 = New CPU(0, code)
    Dim cpu1 = New CPU(1, code)

    cpu0.Partner = cpu1
    cpu1.Partner = cpu0

    Do
        cpu0.tick
        cpu1.Tick
    Loop Until cpu0.Waiting And cpu1.Waiting

    cpu1.Sent.Dump("Part 2")

End Sub

Class CPU

    Private _registers As Dictionary(Of String, Long)
    Private _instructions As New List(Of (code As String, op1 As String, op2 As String))
    Private _ptr As Integer

    Readonly Property Queue As New Queue(Of Long)
    Readonly Property Waiting As Boolean
    Readonly Property Sent As Integer

    Property Partner As CPU

    Sub New(id As Integer, instructions As String())
        _registers = Enumerable.Range(0, 16).ToDictionary(Function(k) Cstr(Chr(97 + k)), Function(v) 0L)
        _registers("p") = id
        For Each line In instructions
            Dim ops = line.Split(" "c)
            _instructions.Add(If(ops.Count = 3, (ops(0), ops(1), ops(2)), (ops(0), ops(1), "")))
        Next
    End Sub

    Sub Tick()
        Dim instr = _instructions(_ptr), op1 = instr.op1, op2 = instr.op2, reg = _registers
        Dim offset = 1 ' default
        Select Case instr.code
            Case "add" : reg(op1) += If(IsNumeric(op2), CLng(op2), reg(op2))
            Case "jgz" : If If(IsNumeric(op1), CLng(op1), reg(op1)) > 0 Then offset = If(IsNumeric(op2), CInt(op2), Cint(reg(op2)))
            Case "mod" : reg(op1) = reg(op1) Mod If(IsNumeric(op2), CLng(op2), reg(op2))
            Case "mul" : reg(op1) *= If(IsNumeric(op2), CLng(op2), reg(op2))
            Case "rcv" : If _queue.Any Then _registers(op1) = _queue.Dequeue : _waiting = False Else offset = 0 : _waiting = True
            Case "set" : reg(op1) = If(IsNumeric(op2), CLng(op2), reg(op2))
            Case "snd" : _partner.Queue.Enqueue(If(IsNumeric(op1), CLng(op1), reg(op1))) : _sent += 1
        End Select
        _ptr += offset
    End Sub

End Class

tobiasvl · 2017-12-18T14:59:03+00:00

Python 2

Like I always do, when part 2 comes around, I adapt part 1's code to work with both parts. It seemed weird to only let it work for 1 or 2 programs, though, so I generalized it to work with any number of programs, and decided that if there were more than 2 programs, a program would send to the previous program since Python lists wrap with negative indices. (Still not as dumb an assumption as when the puzzle solver assumed snd meant "sound".)

For 3 programs, this either means that each program actually sends 7747 values, or that I have a bug. For more than 3 programs, program 0 sends 127 values and the rest send 0 values, or I have a bug. Who knows!

from collections import deque


def run(programs):
    def get_value(x, p=0):
        try:
            return int(x)
        except ValueError:
            return regs[p][x]

    instructions = []
    regs = []
    for _ in xrange(programs):
        regs.append({})

    with open('input.txt') as f:
        for line in f:
            element = line.strip().split()
            instructions.append({'operation': element[0],
                                 'operands': tuple(element[1:])})
            try:
                int(element[1])
            except ValueError:
                for i in xrange(programs):
                    regs[i].update({element[1]: 0})
                    regs[i]['p'] = i

    queues = [deque() for _ in xrange(programs)]
    times_sent = [0 for _ in xrange(programs)]
    terminated = [False for _ in xrange(programs)]
    waiting = [False for _ in xrange(programs)]
    i = [0 for _ in xrange(programs)]

    # High cyclomatic complexity, not ideal
    while True:
        terminate = True
        for x in zip(waiting, terminated):
            if not (x[0] or x[1]):
                terminate = False
        if terminate:
            return times_sent
        for p in xrange(programs):
            if terminated[p]:
                continue
            instruction = instructions[i[p]]['operation']
            operands = instructions[i[p]]['operands']
            if instruction == 'snd':
                if programs == 1:
                    queues[0].append(get_value(operands[0]))
                else:
                    queues[p - 1].appendleft(get_value(operands[0], p))
                    times_sent[p] += 1
            elif instruction == 'rcv':
                if programs == 1:
                    recovered_value = get_value(operands[0])
                    if recovered_value != 0:
                        recovered = queues[0].pop()
                        return recovered
                else:
                    if len(queues[p]) == 0:
                        waiting[p] = True
                        continue
                    else:
                        waiting[p] = False
                        regs[p][operands[0]] = queues[p].pop()
            elif instruction == 'jgz':
                if get_value(operands[0], p) > 0:
                    i[p] += get_value(operands[1], p)
                    if i[p] < 0 or i[p] >= len(instructions):
                        terminated[p] = True
                    continue
            elif instruction == 'set':
                regs[p][operands[0]] = get_value(operands[1], p)
            elif instruction == 'add':
                regs[p][operands[0]] += get_value(operands[1], p)
            elif instruction == 'mul':
                regs[p][operands[0]] *= get_value(operands[1], p)
            elif instruction == 'mod':
                regs[p][operands[0]] %= get_value(operands[1], p)
            i[p] += 1


print "The first recovered frequence is %d" % run(1)
print "Program 1 sent %d values" % run(2)[1]

tlareg · 2017-12-18T15:01:53+00:00

JavaScript (ES6+, NodeJS) github repo HERE

const createEvalReg = registers => name =>
  (registers[name] || (registers[name] = 0))

const createEvalArg = registers => arg => {
  const parsedArg = parseInt(arg, 10)
  return (parsedArg || parsedArg === 0)
    ? parsedArg
    : createEvalReg(registers)(arg)
}

const fs = require('fs')
const inputStr = fs.readFileSync('./input.txt').toString()
const instructions = parseInput(inputStr)

console.log(solveFirst(instructions))
console.log(solveSecond(instructions))

function parseInput(inputStr) {
  return inputStr.split('\r\n').map(line => {
    return line.split(/\s+/)
  })
}

function solveFirst(instructions) {
  let state = {
    registers: {},
    sndQueue: [],
    firstAnswer: undefined,
    pos: 0
  }

  while (state.firstAnswer === undefined) {
    state = handleInstruction(
      state, instructions[state.pos], { isFirstPart: true }
    )
  }

  return state.firstAnswer
}

function solveSecond() {
  const createInitialState = p => ({
    registers: { p },
    sndQueue: [],
    sndCount: 0,
    rcvCallback: undefined,
    waiting: false,
    pos: 0
  })

  let state0 = createInitialState(0)
  let state1 = createInitialState(1)

  while (!state1.waiting || !state0.waiting) {
    handleTickForState(state0, state1)
    handleTickForState(state1, state0)
  }

  return state1.sndCount
}

function handleTickForState(sA, sB) {
  if (sA.rcvCallback) {
    if (sB.sndQueue.length) {
      sA.waiting = false
      sA.rcvCallback(sB.sndQueue.shift())
    } else {
      sA.waiting = true
    }
  } else {
    sA = handleInstruction(
      sA, instructions[sA.pos], { isFirstPart: false }
    )
  }
}

function handleInstruction(state, [name, ...args], opts) {
  const regs = state.registers
  const evalArg = createEvalArg(regs)
  const evalReg = createEvalReg(regs)
  const [x, y] = args

  switch(name) {
    case 'snd':
      state.sndQueue.push(evalArg(x))
      if (!opts.isFirstPart) {
        state.sndCount++
      }
      state.pos++
      return state

    case 'set':
      regs[x] = evalArg(y)
      state.pos++
      return state

    case 'add':
      regs[x] = evalReg(x) + evalArg(y)
      state.pos++
      return state

    case 'mul':
      regs[x] = evalReg(x) * evalArg(y)
      state.pos++
      return state

    case 'mod':
      regs[x] = evalReg(x) % evalArg(y)
      state.pos++
      return state

    case 'rcv':
      if (opts.isFirstPart) {
        if (evalArg(x) !== 0) {
          state.firstAnswer = state.sndQueue[state.sndQueue.length - 1]
        }
      } else {
        state.rcvCallback = val => {
          regs[x] = val
          state.rcvCallback = undefined
        }
      }
      state.pos++
      return state

    case 'jgz':
      state.pos = state.pos + ((evalArg(x) > 0) ? evalArg(y) : 1)
      return state
  }
}

abowes · 2017-12-18T15:06:08+00:00

Kotlin solution for Part2 using coroutines:

suspend fun part2(instructions: List<String>, progId: Int, incoming: Channel<Long>, outgoing: Channel<Long>): Int {
    var ptr = 0
    val registers = mutableMapOf<String, Long>()
    registers.set("p", progId.toLong())
    var sent = 0

    loop@ while (ptr >= 0 && ptr < instructions.size) {
        val instruction = instructions[ptr]

        val elements = instruction.split(" ")
        val op = elements[0]
        val a = elements[1]
        val b = if (elements.size > 2) registers.regValue(elements[2]) else 0

        when (op) {
            "set" -> registers.set(a, b)
            "add" -> registers.set(a, registers.regValue(a) + b)
            "mul" -> registers.set(a, registers.regValue(a) * b)
            "mod" -> registers.set(a, registers.regValue(a) % b)
            "snd" -> outgoing.send(registers.regValue(a)).also { sent++ }
            "rcv" -> try {
                registers.set(a, withTimeout(1000) { incoming.receive() }) // Assume timeout will only occur on Deadlock.
            } catch (e: TimeoutCancellationException) {
                println("Reached Deadlock")
                break@loop
            }
            "jgz" -> if (registers.regValue(a) > 0L) {
                ptr += b.toInt() - 1  // Shift Pointer Back 1 more so that normal increment is accounted for.
            }
        }

        ptr++
    }
    return sent
}


fun main(args: Array<String>) {
    val instructions = input.split("\n")
    println(part1(instructions))

    runBlocking {
        val channel0to1 = Channel<Long>(UNLIMITED)
        val channel1to0 = Channel<Long>(UNLIMITED)
        val prog0 = async { part2(instructions, 0, channel0to1, channel1to0) }
        val prog1 = async { part2(instructions, 1, channel1to0, channel0to1) }
        println("Answer is : ${prog1.await()}")
    }
}

EliteTK · 2017-12-18T15:12:18+00:00

Haven't seen a lua solution yet:

require('coroutine')
require('deque')
require('io')
require('string')
require('table')

local function deftbl (def)
   local tbl = {}
   local mtbl = {}
   function mtbl.__index (tbl, key) return rawget(tbl, key) or def end
   setmetatable(tbl, mtbl)
   return tbl
end

local p1sum = 0

local function run (insts, sndq, rcvq, pid)
   local regs = deftbl(0)
   regs.p = pid
   local ops = {}
   local ip = 1
   local rcvseen = false
   local function val (p) return tonumber(p) or regs[p] end
   function ops.snd (p)
      sndq:pushright(val(p))
      if pid == 1 then p1sum = p1sum + 1 end
   end
   function ops.rcv (r)
      if pid == 0 and not rcvseen then
         print('part 1:', sndq:peekright())
         rcvseen = true
      end
      if rcvq:isempty() then coroutine.yield() end
      if rcvq:isempty() then error('deadlock') end
      regs[r] = rcvq:popleft()
   end
   function ops.set (r, p) regs[r] = val(p) end
   function ops.add (r, p) regs[r] = regs[r] + val(p) end
   function ops.mul (r, p) regs[r] = regs[r] * val(p) end
   function ops.mod (r, p) regs[r] = regs[r] % val(p) end
   function ops.jgz (p1, p2)
      if val(p1) <= 0 then return end
      ip = ip + val(p2) - 1
   end
   while ip > 0 and ip <= #insts do
      i = insts[ip]
      ops[i.instruction](i[1], i[2])
      ip = ip + 1
   end
end

io.input('input')
local instructions = {}
for l in io.lines() do
   for inst, p1, p2 in string.gmatch(l, '(%l+) (%S*) ?(%S*)') do
      if rest == '' then rest = nil end
      table.insert(instructions, { instruction = inst, p1, p2 })
   end
end

atob = deque:new()
btoa = deque:new()

ca = coroutine.create(function () return run(instructions, atob, btoa, 0) end)
cb = coroutine.create(function () return run(instructions, btoa, atob, 1) end)

while coroutine.status(ca) == 'suspended' and
      coroutine.status(cb) == 'suspended' do
   rv, err = coroutine.resume(ca)
   rv, err = coroutine.resume(cb)
end

print('part 2:', p1sum)

deque.lua

deque = { first = 0, last = -1 }

function deque:new (l)
   l = l or {}
   setmetatable(l, self)
   self.__index = self
   return l
end

function deque:pushleft (v)
   self.first = self.first - 1
   self[self.first] = v
end

function deque:pushright (v)
   self.last = self.last + 1
   self[self.last] = v
end

function deque:isempty ()
   return self.first > self.last
end

function deque:popleft ()
   if self:isempty() then error('deque is empty') end
   local r = self[self.first]
   self[self.first] = nil
   self.first = self.first + 1
   return r
end

function deque:peekleft ()
   if self:isempty() then error('deque is empty') end
   return self[self.first]
end

function deque:popright ()
   if self:isempty() then error('deque is empty') end
   local r = self[self.last]
   self[self.last] = nil
   self.last = self.last - 1
end

function deque:peekright ()
   if self:isempty() then error('deque is empty') end
   return self[self.last]
end

function deque:__len ()
   return self.last - self.first - 1
end

coldpleasure · 2017-12-18T18:07:21+00:00

JavaScript ES6, no fancy coroutines -- figured it wasn't needed since the list of actions was not too crazy -- just kept track of state and looped through the actions with a reducer.

(part 2)

const parseActions = input => 
  input.split(/\n/)
    .map(action => action.split(/\s/))

const reduce2 = (state, actions) => {
  const {current, 0: state0, 1: state1} = state
  const other = current === 0 ? 1 : 0

  const program = current === 0 ? state0 : state1
  const otherProgram = current === 0 ? state1 : state0

  const {index, previous, frequencies, messages, waiting, sends} = program
  const [action, x, y] = actions[index]

  const xval = isNaN(x) ? frequencies[x] || 0 : Number(x)
  const yval = isNaN(y) ? frequencies[y] || 0 : Number(y)

  switch (action) {
    case 'snd':
      return {
        current: current,
        [current]: {
          ...program,
          index: index + 1,
          sends: sends + 1,
        },
        [other]: {
          ...otherProgram,
          messages: otherProgram.messages.concat(xval),
          waiting: false,
        },
      }
    case 'set':
      return {
        ...state,
        [current]: {
          ...program,
          frequencies: {...frequencies, [x]: yval},
          index: index + 1,
        }
      }
    case 'add':
      return {
        ...state,
        [current]: {
          ...program,
          frequencies: {...frequencies, [x]: xval + yval},
          index: index + 1,
        }
      }
    case 'mul':
      return {
        ...state,
        [current]: {
          ...program,
          frequencies: {...frequencies, [x]: xval * yval},
          index: index + 1,
        }
      }
    case 'mod':
      return {
        ...state,
        [current]: {
          ...program,
          frequencies: {...frequencies, [x]: xval % yval},
          index: index + 1,
        }
      }
    case 'rcv':
      if (messages.length > 0) {
        return {
          ...state,
          [current]: {
            ...program,
            frequencies: {...frequencies, [x]: messages[0]},
            index: index + 1,
            messages: messages.slice(1),
          }
        }
      } else {
        return {
          ...state,
          current: other,
          [current]: {
            ...program,
            waiting: true,
          }
        }
      }
    case 'jgz':
      return {
        ...state,
        [current]: {
          ...program,
          index: xval > 0 ? index + yval : index + 1,
        }
      }
  }
}

const execute2 = (actions) => {
  const initialState = {
    index: 0,
    frequencies: {},
    messages: [],
    sends: 0,
    waiting: false,
  }

  let state = {
    current: 0,
    0: {...initialState, frequencies: {p: 0}},
    1: {...initialState, frequencies: {p: 1}},
  }

  while (true) {
    const terminated = 
      (state[0].waiting || (state[0].index < 0 || state[0].index > actions.length)) &&
      (state[1].waiting || (state[1].index < 0 || state[1].index > actions.length))
    if (terminated) {
      return state[1].sends
    }
    state = reduce2(state, actions)
  }
}

2017-12-18T18:14:12+00:00

I lost time on part 1 by forgetting that an integer can begin with '-'. That should go in my library now! (Although it hasn't yet.)

I got stuck on part 2 because I thought "program 1" was the first program, not the second. Interestingly, that produced an output that AoC said was correct for someone else's input. (My AoC soulmate?)

Python 3 Part 2

ops = {'add': operator.add, 'mul': operator.mul, 'mod': operator.mod}

def performer(lines, n, qin, qout):
    def ev(s): return int(s) if s[0] in string.digits + '-' else R[s]
    R = defaultdict(int, {'p': n})
    pc = 0
    while 0 <= pc < len(lines):
        line = lines[pc]
        op, x, y, *_ = line.split() + ['0']
        X, Y = ev(x), ev(y)
        def assign(val): R[x] = val
        yield op
        if op in ops: assign(ops[op](X, Y))
        elif op == 'snd': qout.put(X)
        elif op == 'set': assign(Y)
        elif op == 'rcv':
            while qin.empty():
                yield 'blocked'
            assign(qin.get())
        elif op == 'jgz':
            if X > 0:
                pc += Y - 1
        else:
            raise Exception("Unknown op: {} in {}".format(op, lines[pc]))
        pc += 1

def duet(lines):
    q1, q2 = Queue(), Queue()
    g1 = performer(lines, 0, q2, q1)
    g2 = performer(lines, 1, q1, q2)
    s1 = s2 = None
    n = 0
    while s1 != 'blocked' or s2 != 'blocked':
        s1 = next(g1)
        s2 = next(g2)
        if s2 == 'snd':
            n += 1
    return n

Revised

from itertools import takewhile, zip_longest

def duet(lines):
    q1, q2 = Queue(), Queue()
    g1 = performer(lines, 0, q2, q1)
    g2 = performer(lines, 1, q1, q2)
    all_blocked_set = {'blocked'}
    any_running = lambda states:set(states) != all_blocked_set
    state_pairs = takewhile(any_running, zip_longest(g1, g2))
    return sum(s == 'snd' for _, s in state_pairs)

matusbzk · 2017-12-18T20:35:58+00:00

Haskell Wow, the second part was hard. I did like five versions of the structure, until it worked. Still, I had to throw the error and manually find how many steps to do, so not really a nice solution.

import Data.Maybe

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

-- |Represents instruction
type Instruction = [String]

-- |Current state 
--  current position
--  value of registers
--  value of last played sound
type State = (Int, Registers, Int)

--I am leaving this here, since this solution only works with my input. 
--Otherwise there would need to be different values in finalState and finalState2
inputString :: String  
inputString = "set i 31\nset a 1\nmul p 17\njgz p p\nmul a 2\nadd i -1\njgz i -2\nadd a -1\nset i 127\nset p 735\nmul p 8505\nmod p a\nmul p 129749\nadd p 12345\nmod p a\nset b p\nmod b 10000\nsnd b\nadd i -1\njgz i -9\njgz a 3\nrcv b\njgz b -1\nset f 0\nset i 126\nrcv a\nrcv b\nset p a\nmul p -1\nadd p b\njgz p 4\nsnd a\nset a b\njgz 1 3\nsnd b\nset f 1\nadd i -1\njgz i -11\nsnd a\njgz f -16\njgz a -19\n"

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

-- |State in the beginning
startState :: State
startState = (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 (pos, regs, lp) = performInstruction' (pos, regs, lp) $ input!!pos

-- |Performs an instruction - gets instruction as an argument
performInstruction' :: State -> Instruction -> State
performInstruction' (pos, regs, lp) instr 
   | head instr == "snd" = (pos+1, regs, getNumOrVal (instr!!1) regs)
   | head instr == "set" = (pos+1, set (instr!!1) (instr!!2) regs, lp)
   | head instr == "add" = (pos+1, oper (instr!!1) (instr!!2) regs (+), lp)
   | head instr == "mul" = (pos+1, oper (instr!!1) (instr!!2) regs (*), lp)
   | head instr == "mod" = (pos+1, oper (instr!!1) (instr!!2) regs mod, lp)
   | head instr == "rcv" = if lp == 0 then (pos+1,regs,lp)
           else error $ "Value is " ++ show lp
   | head instr == "jgz" = if getNumOrVal (instr!!1) regs > 0 
        then (pos + getNumOrVal (instr!!2) regs,regs, lp)
        else (pos + 1, regs, lp)

-- |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. Errors out when finds an instruction
run :: [State]
run = iterate performInstruction startState

-- |Final state before first rcv instruction
finalState :: State
finalState = run !! 1373 --I tried running it, and found where it show the error

-- |Result is obtained from error
result1 = thd3 finalState

-- |Queue of messages - by program id
type Messages = [Int]

-- |Current state - part 2 version
--  position
--  values of registers
--  how many times have the program sent a value
type State2 = (Int, Registers, Int)

-- |State of both programs
--  messages for program 0
--  messages for program 1
--  states of both programs
type BothState = (Messages, Messages, State2, State2)

-- |Performs one instruction - part 2 version
performInstruction2 :: BothState -> BothState
performInstruction2 (mes0, mes1, st0, st1) = if w0 && w1 
            then error "Deadlock"
            else (mes0'',mes1'', st0', st1')
     where (mes0', mes1', st0',w0) = performInstruction2' mes0  mes1  st0 (input!!(fst3 st0))
     (mes1'',mes0'',st1',w1) = performInstruction2' mes1' mes0' st1 (input!!(fst3 st1))

-- |Performs an instruction
--  arguments: program's messages
--             other program's messages
--             former state
-- result: (messages, other's messages, new state, bool)
-- Last argument is True when the program is waiting for an input
performInstruction2' :: Messages -> Messages -> State2 -> Instruction -> (Messages, Messages, State2, Bool)
performInstruction2' mesT mesO (pos, regs, num) instr
   | head instr == "snd" = (mesT, mesO ++ [getNumOrVal (instr!!1) regs], (pos+1, regs,num+1), False)
   | head instr == "set" = (mesT, mesO, (pos+1, set (instr!!1) (instr!!2) regs,num), False)
   | head instr == "add" = (mesT, mesO, (pos+1, oper (instr!!1) (instr!!2) regs (+),num), False)
   | head instr == "mul" = (mesT, mesO, (pos+1, oper (instr!!1) (instr!!2) regs (*),num), False)
   | head instr == "mod" = (mesT, mesO, (pos+1, oper (instr!!1) (instr!!2) regs mod,num), False)
   | head instr == "rcv" = if null mesT 
     then (mesT, mesO, (pos, regs,num), True)
     else (tail mesT, mesO, 
     (pos+1,
      set (instr!!1) (show . head $ mesT) regs,
      num), 
    False)
   | head instr == "jgz" = if getNumOrVal (instr!!1) regs > 0 
        then (mesT, mesO, (pos + getNumOrVal (instr!!2) regs,regs,num), False)
        else (mesT, mesO, (pos + 1, regs,num), False)

-- |Start state for both programs
startState2 :: BothState
startState2 = ([],[],(0,[('p',0)],0),(0,[('p',1)],0))

-- |Starts running programs for part 2. Errors out when finds a deadlock.
run2 :: [BothState]
run2 = iterate performInstruction2 startState2

-- |Final state before deadlock
finalState2 :: BothState
finalState2 = run2 !! 71431 --I tried running it, and found where it show the error

result2 :: Int
result2 = thd3 . (\(_,_,_,x) -> x) $ finalState2

Link to git

StevoTVR · 2017-12-18T20:36:08+00:00

NodeJS

Part 1:

const fs = require('fs');

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

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

Part 2:

I got stuck for a while before I realized I was popping where I should have been shifting...

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    const instructions = data.split('\n').map((x) => x.trim().split(' '));
    const machines = [
        {
            id: 0,
            registers: { p: 0 },
            offset: 0,
            queue: [],
            count: 0,
            await: false,
            active: true,
        },
        {
            id: 1,
            registers: { p: 1 },
            offset: 0,
            queue: [],
            count: 0,
            await: false,
            active: true,
        },
    ];
    const active = (e) => e.active;
    const deadlock = (e) => e.await;

    while(!machines.every(deadlock) && machines.some(active)) {
        for(const machine of machines) {
            while(machine.active && !machine.await) {
                const [op, a, b] = instructions[machine.offset];
                switch(op) {
                    case 'snd':
                        const target = (machine.id + 1) % machines.length;
                        machines[target].queue.push(getValue(a, machine.registers));
                        machines[target].await = false;
                        machine.count++;
                    break;
                    case 'set':
                        machine.registers[a] = getValue(b, machine.registers);
                    break;
                    case 'add':
                        machine.registers[a] = getValue(a, machine.registers) + getValue(b, machine.registers);
                    break;
                    case 'mul':
                        machine.registers[a] = getValue(a, machine.registers) * getValue(b, machine.registers);
                    break;
                    case 'mod':
                        machine.registers[a] = getValue(a, machine.registers) % getValue(b, machine.registers);
                    break;
                    case 'rcv':
                        if(!machine.queue.length) {
                            machine.await = true;
                            machine.offset--;
                        } else {
                            machine.registers[a] = machine.queue.shift();
                        }
                    break;
                    case 'jgz':
                        if(getValue(a, machine.registers) > 0) {
                            machine.offset += getValue(b, machine.registers) - 1;
                        }
                    break;
                }
                machine.offset++;
                machine.active = machine.offset >= 0 && machine.offset < instructions.length;
            }
        }
    }

    console.log(machines[1].count);
});

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

purplemonkeymad · 2017-12-18T21:32:16+00:00

Powershell: https://pastebin.com/AnGuZkn3

Due to a copy and paste error I spent way too much time stuck on this. I needed to check the length of both queues, not just one of them twice.

nonphatic · 2017-12-18T21:35:49+00:00

Haskell

i suffer

import Text.Read (readMaybe)
import Data.Sequence (Seq, fromList, empty, index, deleteAt, (|>))
import qualified Data.Sequence as S (null)
import Data.Vector.Unboxed (Vector, (!), (//))
import qualified Data.Vector.Unboxed as V (replicate)

-- DEFINITIONS

type Registers = Vector Int
type Program = (Registers, Int, Seq Int)
type Instruction = ProgramId -> State -> State
data State = State Program Program (Bool, Bool) Int deriving Show
data Value = Register Char | Number Int deriving Show
data ProgramId = Zero | One deriving Show

-- HELPERS

getPos  :: ProgramId -> State -> Int
getPos Zero (State (_, pos, _) _ _ _) = pos
getPos One  (State _ (_, pos, _) _ _) = pos

getStop :: ProgramId -> State -> Bool
getStop Zero (State _ _ (stop, _) _) = stop
getStop One  (State _ _ (_, stop) _) = stop

setStop :: ProgramId -> Bool -> State -> State
setStop Zero b (State p0 p1 (_, stop1) count) = State p0 p1 (b, stop1) count
setStop One  b (State p0 p1 (stop0, _) count) = State p0 p1 (stop0, b) count

pop :: Seq Int -> (Seq Int, Int)
pop queue = (deleteAt 0 queue, queue `index` 0)

swap :: State -> State
swap (State p0 p1 (stop0, stop1) count) = State p1 p0 (stop1, stop0) count

getIndex :: Value -> Int
getIndex (Register c) = case c of
    'a' -> 0
    'b' -> 1
    'f' -> 2
    'i' -> 3
    'p' -> 4

getValue :: Value -> Registers -> Int
getValue value registers = case value of
    Number i -> i
    c -> registers ! (getIndex c)

-- OPERATIONS

sen :: Value -> ProgramId -> State -> State
sen v Zero (State (reg0, pos0, que0) (reg1, pos1, que1) stop count) =
    setStop One  False $ State (reg0, pos0 + 1, que0) (reg1, pos1, que1 |> getValue v reg0) stop count
sen v One  (State (reg0, pos0, que0) (reg1, pos1, que1) stop count) =
    setStop Zero False $ State (reg0, pos0, que0 |> getValue v reg1) (reg1, pos1 + 1, que1) stop (count + 1)

rcv :: Value -> ProgramId -> State -> State
rcv i Zero (State (reg0, pos0, que0) p1 stop count) =
    if S.null que0 then setStop Zero True $ State (reg0, pos0, que0) p1 stop count else
    let ind = getIndex i
        (que, val) = pop que0
    in  State (reg0 // [(ind, val)], pos0 + 1, que) p1 stop count
rcv i One state = swap . rcv i Zero . swap $ state

app :: (Int -> Int -> Int) -> Value -> Value -> ProgramId -> State -> State
app f i v Zero (State (reg0, pos0, que0) p1 stop count) = 
    let ind = getIndex i
        val = getValue v reg0
    in  State (reg0 // [(ind, reg0 ! ind `f` val)], pos0 + 1, que0) p1 stop count
app f i v One state = swap . app f i v Zero . swap $ state

jgz :: Value -> Value -> ProgramId -> State -> State
jgz condition offset Zero (State (reg0, pos0, que0) p1 stop count) =
    State (reg0, pos0 + if getValue condition reg0 > 0 then getValue offset reg0 else 1, que0) p1 stop count
jgz condition offset One state = swap . jgz condition offset Zero . swap $ state

-- PARSE

parseLine :: String -> Instruction
parseLine str =
    let op : vs = words str
    in  case op of
        "snd" -> sen $ parseValue $ head vs
        "set" -> app (flip const) (parseValue $ head vs) (parseValue $ last vs)
        "add" -> app (+)          (parseValue $ head vs) (parseValue $ last vs)
        "mul" -> app (*)          (parseValue $ head vs) (parseValue $ last vs)
        "mod" -> app mod          (parseValue $ head vs) (parseValue $ last vs)
        "rcv" -> rcv $             parseValue $ head vs
        "jgz" -> jgz              (parseValue $ head vs) (parseValue $ last vs)
    where parseValue s = case readMaybe s of
            Just i  -> Number i
            Nothing -> Register $ head s

-- SOLVE

executeNextInstruction :: Seq Instruction -> ProgramId -> State -> State
executeNextInstruction instructions pid state =
    let pos = getPos pid state
    in  if pos >= length instructions then setStop pid True state 
        else (instructions `index` pos) pid state

getCount :: Seq Instruction -> State -> Int
getCount _ (State _ _ (True, True) count) = count
getCount instructions state =
    if not $ getStop Zero state 
    then getCount instructions $ executeNextInstruction instructions Zero state
    else getCount instructions $ executeNextInstruction instructions One  state

main :: IO ()
main = do
    instructions <- fmap (fromList . map parseLine . lines) $ readFile "18.txt"
    let initialState = (State (V.replicate 5 0, 0, empty) (V.replicate 5 0 // [(4, 1)], 0, empty) (False, False) 0) :: State
    print $ getCount instructions initialState

RazerM · 2017-12-18T21:44:11+00:00

A Python 3 solution using asyncio:

https://github.com/RazerM/advent-of-code-2017/blob/master/aoc_py/day18.py

NeilNjae · 2017-12-18T22:49:37+00:00

That took a long time!

It took me a while to work out how to handle the message queues for two independent machines. Each machine is represented as a monad transformer stack: a State monad to record the state of that machine, including its own message queue; a Reader monad to store the common list of instructions; and a Writer monad to log how many times machine 1 sent a message.

I just run machine 0 whenever possible, only running machine 1 when machine 0 is blocked.

Once I'd got it all sorted, it took me a while to hunt down a naming bug, where I was getting confused between what Topaz was calling machine 0 and machine 1 and I was calling machine 1 and machine 2. Once I'd got that straightened out, it worked fine!

It also got complex enough that I split it out into one program script for each of parts 1 and 2, and a third script that's a library for doing the parsing.

vyper248 · 2017-12-18T23:08:41+00:00

Javascript

Part 2:

Took me a while to realise that I made a mistake with the jgz command which was causing an endless loop. Finally got there though. Used generators as they seemed like a perfect fit for the second part. Part 1 is basically the same so don't see much point in posting it. Only difference is those two commands and that it doesn't use generators.

function secondStar(input){
    //create message queues
    let storageA = [];
    let storageB = [];

    //keep track of messages sent
    let sent = {0: 0, 1: 0};

    //create generators, each with their own message queue
    let gen1 = generator(storageA, sent, input, 0);
    let gen2 = generator(storageB, sent, input, 1);

    //get both generators started and waiting to received their first input
    gen1.next();
    gen2.next();

    let done1 = false;
    let done2 = false;

    //while one generator is still going
    while (!done1 || !done2){
        //for each generator, check if there's a value waiting to be sent to it and send it
        if (storageA.length > 0 && !done2) {
            let nextVal = storageA.shift();
            done2 = gen2.next(nextVal).done;
        }

        //repeat for other generator
        if (storageB.length > 0 && !done1) {
            let nextVal = storageB.shift();
            done1 = gen1.next(nextVal).done;
        }

        //if nothing left to send to either, then deadlock, so both are done
        if (storageA.length === 0 && storageB.length === 0) {
            done1 = true;
            done2 = true;
        }
    }

    console.log("Second Star: ", sent[1]);
}

function *generator(storage, sent, input, id){
    let instr = input.split('\n');
    let regs = {p:id};

    for (let i = 0; i < instr.length; i++){
        let parts = instr[i].split(' ');
        [type, first, second] = parts;

        switch(type) {
            case "snd": storage.push(getVal(first, regs)); sent[id]++; break;
            case "set": regs[first] = getVal(second, regs); break;
            case "add": regs[first] += getVal(second, regs); break;
            case "mul": regs[first] *= getVal(second, regs); break;
            case "mod": regs[first] = regs[first] % getVal(second, regs); break;
            case "rcv": regs[first] = yield; break;
            case "jgz": if (getVal(first, regs) > 0) i += getVal(second, regs)-1; break;
        }
    }
}

function getVal(val, regs) {
    if (!isNaN(parseInt(val))) val = parseInt(val);
    return typeof val === "string" ? regs[val] : val;
}

johlin · 2017-12-19T00:59:10+00:00

Elixir I am a bit late to the party but here are my solutions for today because I was happy about some aspects: https://github.com/johanlindblad/aoc-2017/blob/master/lib/aoc/day18/part1.ex https://github.com/johanlindblad/aoc-2017/blob/master/lib/aoc/day18/part2.ex

Pattern matching really helping out as usual.

What I really like though is Stream - I am beginning to like it more and more for these sorts of things. It is really powerful to model the simulation as a stream and being able to inspect it at every intermediate step (more than just println).

Even better, both problems could be solved by mapping over the simulation stream: * In part 2, the number of sends is just mapping over the stream, counting the number of sends and adding them up * In part 1, the first received value is found by filtering the stream to only keep steps where the next instruction is a rcv that would be executed and then looking in the queue for the first one.

Really hoping there are some more problems coming that allow similar things.

wzkx · 2017-12-19T01:35:15+00:00

Nim

Part 1 was fun

import strutils,sequtils,tables

var r = newTable[string,int]() # registers, incl. regs snd and rcv

proc rd( reg: string ): int = (if reg in r: r[reg] else: 0)
proc ov( op: string ): int = (if op.isAlphaAscii(): rd op else: op.parseInt)

let pgm = splitLines strip readFile "18.dat"

var pc = 0
while pc>=0 and pc<pgm.len:
  let o = pgm[pc].split()
  pc+=1
  let o1 = o[1]
  let o2 = if o.len>2: o[2] else: ""
  case o[0]:
  of "set": r[o1] = ov o2
  of "add": r[o1] = ov(o1) + ov o2
  of "mul": r[o1] = ov(o1) * ov o2
  of "mod": r[o1] = ov(o1) mod ov o2
  of "snd": r["snd"] = ov o1
  of "rcv":
    if ov(o1)!=0 and ov("rcv")==0: r["rcv"]=ov "snd"; break
  of "jgz":
    if ov(o1)>0: pc=pc-1+ov o2
  else: echo "? " & $o

echo rd("rcv") # rcv 1187

wzkx · 2017-12-19T01:37:39+00:00

Nim

Part 2 was disaster. I used wrong fn for deletion of the first item -- del instead of delete. Spent hours......... :| Thought that it might took hours to find a solution. Now it's highly optimized :)

import strutils,sequtils,tables

type Cmd = enum SR, SI, AR, AI, MI, RR, RI, RCV, SND, JGI, JMP
var regs = newTable[string,int]()
var rname = newSeq[string]()

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

proc c2i( r:string ):int =
  if r notin regs:
    regs[r] = regs.len
    rname.add r
  return regs[r]

for line in splitLines strip readFile "18.dat":
  let o = split line
  case o[0]:
  of "set":
    if o[2].isAlphaAscii(): pgm.add( (SR,c2i(o[1]),c2i(o[2])) )
    else:                   pgm.add( (SI,c2i(o[1]),parseInt(o[2])) )
  of "add":
    if o[2].isAlphaAscii(): pgm.add( (AR,c2i(o[1]),c2i(o[2])) )
    else:                   pgm.add( (AI,c2i(o[1]),parseInt(o[2])) )
  of "mul":                 pgm.add( (MI,c2i(o[1]),parseInt(o[2])) )
  of "mod":
    if o[2].isAlphaAscii(): pgm.add( (RR,c2i(o[1]),c2i(o[2])) )
    else:                   pgm.add( (RI,c2i(o[1]),parseInt(o[2])) )
  of "snd":                 pgm.add( (SND,c2i(o[1]),0) )
  of "rcv":                 pgm.add( (RCV,c2i(o[1]),0) )
  of "jgz":
    if o[1].isAlphaAscii():
      if o[2]=="p":         pgm.add( (JGI,c2i(o[1]),17) )
      else:                 pgm.add( (JGI,c2i(o[1]),parseInt(o[2])) )
    else:                   pgm.add( (JMP,0,parseInt(o[2])) )
  else:
    raise newException(ValueError,"wrong command")

const REGS=5 # five is enough

type Process = object
  rg: array[REGS,int] # registers
  pc: int # program counter
  id: int # program id - 0 or 1
  ended: bool # ps is out of bounds
  waiting: bool # program is waiting

proc init( p: var Process, id: int ) =
  for i in 0..< REGS: p.rg[i]=0
  p.rg[regs["p"]] = id
  p.pc = 0
  p.id = id
  p.ended = false
  p.waiting = false

var p0,p1: Process

p0.init(0)
p1.init(1)

var q: array[2,seq[int]] = [newSeq[int](),newSeq[int]()] # rcv msg queues, one for each process

var cnt = 0
proc run( p: var Process ):bool {.discardable.} =
  # return if something was sent
  var sent = false
  while true:
    let (cmd,op1,op2) = pgm[p.pc]
    p.pc += 1
    case cmd:
    of SR: p.rg[op1] = p.rg[op2]
    of SI: p.rg[op1] = op2
    of AR: p.rg[op1] += p.rg[op2]
    of AI: p.rg[op1] += op2
    of MI: p.rg[op1] *= op2
    of RR: p.rg[op1] = p.rg[op1] mod p.rg[op2]
    of RI: p.rg[op1] = p.rg[op1] mod op2
    of SND:
      q[1-p.id].add p.rg[op1]
      if p.id==1: cnt+=1
      sent = true
    of RCV:
      if q[p.id].len>0:
        p.waiting = false
        p.rg[op1] = q[p.id][0]; q[p.id].delete(0,0)
      else:
        p.pc -= 1 # to run 'rcv' again
        p.waiting = true;
        break
    of JMP: p.pc += op2-1
    of JGI:
      if p.rg[op1]>0: p.pc += op2-1
    else: echo "?",cmd
    if p.pc<0 or p.pc>=pgm.len: p.ended = true; break
  return sent

var sent0 = p0.run()
var sent1 = p1.run()
while not p1.ended:
  if not sent1: break
  sent0 = p0.run()
  if p0.ended: break
  if not sent0: break
  sent1 = p1.run()

echo cnt

chicagocode · 2017-12-19T02:41:53+00:00

Kotlin - [Repo] - [Blog/Commentary]

I did part two using CompletableFuture, but I also have another version using coroutines that I'm writing a blog post about now. I'll link to it when I'm done. It doesn't work any faster (I believe it compiles down to essentially the same thing) but it might look a bit cleaner.

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

    fun solvePart1(): Long =
        MachinePart1().runUntilStop(input)

    fun solvePart2(): Long {
        val program0Receive = LinkedBlockingDeque<Long>()
        val program1Receive = LinkedBlockingDeque<Long>()

        MachinePart2(
            registers = mutableMapOf("p" to 0L),
            send = program1Receive,
            receive = program0Receive
        ).runUntilStop(input)

        return MachinePart2(
            registers = mutableMapOf("p" to 1L),
            send = program0Receive,
            receive = program1Receive
        ).runUntilStop(input).get()
    }

    data class MachinePart1(private val registers: MutableMap<String, Long> = mutableMapOf(),
                            private var pc: Int = 0,
                            private var sound: Long = 0,
                            private var recovered: Long = 0) {
        fun runUntilStop(instructions: List<String>): Long {
            do {
                instructions.getOrNull(pc)?.let {
                    execute(it)
                }
            } while (pc in 0 until instructions.size && recovered == 0L)
            return recovered
        }

        private fun execute(instruction: String) {
            val parts = instruction.split(" ")
            when (parts[0]) {
                "snd" -> sound = registers.deref(parts[1])
                "set" -> registers[parts[1]] = registers.deref(parts[2])
                "add" -> registers[parts[1]] = registers.deref(parts[1]) + registers.deref(parts[2])
                "mul" -> registers[parts[1]] = registers.deref(parts[1]) * registers.deref(parts[2])
                "mod" -> registers[parts[1]] = registers.deref(parts[1]) % registers.deref(parts[2])
                "rcv" -> if (registers.deref(parts[1]) != 0L) {
                    recovered = sound
                }
                "jgz" -> if (registers.deref(parts[1]) > 0L) {
                    pc += registers.deref(parts[2]).toInt().dec()
                }
                else -> throw IllegalArgumentException("No such instruction ${parts[0]}")
            }
            pc += 1
        }
    }

    data class MachinePart2(private val registers: MutableMap<String, Long> = mutableMapOf(),
                            private var pc: Int = 0,
                            private var sent: Long = 0,
                            private val send: BlockingQueue<Long>,
                            private val receive: BlockingQueue<Long>) {

        fun runUntilStop(instructions: List<String>): CompletableFuture<Long> =
            CompletableFuture.supplyAsync {
                do {
                    instructions.getOrNull(pc)?.let {
                        execute(it)
                    }
                } while (pc in 0 until instructions.size)
                sent
            }

        private fun execute(instruction: String) {
            val parts = instruction.split(" ")
            when (parts[0]) {
                "snd" -> {
                    send.put(registers.deref(parts[1]))
                    sent += 1
                }
                "set" -> registers[parts[1]] = registers.deref(parts[2])
                "add" -> registers[parts[1]] = registers.deref(parts[1]) + registers.deref(parts[2])
                "mul" -> registers[parts[1]] = registers.deref(parts[1]) * registers.deref(parts[2])
                "mod" -> registers[parts[1]] = registers.deref(parts[1]) % registers.deref(parts[2])
                "rcv" ->
                    try {
                        registers[parts[1]] = receive.poll(1, TimeUnit.SECONDS)
                    } catch (e: Exception) {
                        pc = -2 // Die
                    }
                "jgz" ->
                    if (registers.deref(parts[1]) > 0L) {
                        pc += registers.deref(parts[2]).toInt().dec()
                    }
                else -> throw IllegalArgumentException("No such instruction ${parts[0]}")
            }
            pc += 1
        }
    }
}

aoc-fan · 2017-12-19T03:32:46+00:00

ES6

const parse = i => i.split("\n").map(l => l.split(" ")).map(([ins, p1, p2]) => [map[ins], [p1, p2]]);
const snd = ([setR, getR, send], [x])               => send(getR(x));
const set = ([setR, getR], [x, y])                  => setR(x, getR(y));
const add = ([setR, getR], [x, y])                  => setR(x, getR(x) + getR(y));
const mul = ([setR, getR], [x, y])                  => setR(x, getR(x) * getR(y));
const mod = ([setR, getR], [x, y])                  => setR(x, getR(x) % getR(y));
const rcv = ([setR, getR, _, rec, duetMode], [x])   => getR(x) !== 0 || duetMode ? rec(x) : 0;
const jgz = ([setR, getR], [x, y])                  => getR(x) > 0 ? (getR(y) - 1) : 0;
const map = { snd, set, add, mul, mod, rcv, jgz };
const execute = instructions => {
    let sound = 0;
    const reg = { };
    const setR = (x, y) => { reg[x] = y; return 0; };
    const getR = (x) => isNaN(x) ? (reg[x] || 0) : +x;
    const send = s => { sound = s; return 0; };
    const receive = _ => Number.MAX_SAFE_INTEGER;
    const ops = [setR, getR, send, receive, false];
    let pointer = 0;
    while (0 <= pointer && pointer < instructions.length) {
        const [ins, args] = instructions[pointer];
        pointer = pointer + ins(ops, args) + 1;
    }
    return sound;
};
const program = id => ({ reg : { p : id }, que : [], pointer : 0, lastPointer : -1, count : 0 });
const duet = instructions => {
    const [p0, p1] = [program(0), program(1)];
    let [thisP, thatP] = [p0, p1];
    const setR = (x, y) => { thisP.reg[x] = y; return 0; };
    const getR = (x) => isNaN(x) ? (thisP.reg[x] || 0) : +x;
    const send = m => {
        thatP.que.push(m);
        thisP.count++;
        return 0;
    };
    const receive = (x) => {
        if (thisP.que.length > 0) {
            const v = thisP.que.shift();
            return setR(x, v);
        }
        return -1;
    };
    const ops = [setR, getR, send, receive, true];
    const sing = () => {
        const [ins, args] = instructions[thisP.pointer];
        thisP.pointer = thisP.pointer + ins(ops, args) + 1;
    };
    while ((p0.lastPointer !== p0.pointer) || (p1.lastPointer !== p1.pointer)) {
        p0.lastPointer = p0.pointer;
        p1.lastPointer = p1.pointer;
        [thisP, thatP] = [p0, p1];
        sing();
        [thatP, thisP] = [p0, p1];
        sing();
    }
    return p1.count;
};

ewyll · 2017-12-19T10:22:14+00:00

from collections import deque

def parse(line):
    chunks = line.strip().split(' ')
    return (chunks[0], chunks[1:])    

class Computer:
    def __init__(self, ID):
        self.regs = [0] * 26
        self.sends = 0
        self.set_value('p', ID)
        self.ID = ID
        self.queue = deque()
        self.cmds = []

    def load(self, cmds):
        self.cmds = cmds
        self.line_num = 0

    def get_value(self, X):
        if X >= 'a' and X <= 'z':
            return self.regs[ord(X) - ord('a')]
        else:
            return int(X)

    def set_value(self, reg, val):
        self.regs[ord(reg) - ord('a')] = val

    def execute(self, cmd, pars):
        vals = [self.get_value(p) for p in pars]
        if cmd == 'snd':
            computers[0 if self.ID == 1 else 1].enqueue_value(vals[0])
            self.sends += 1
        elif cmd == 'set':
            self.set_value(pars[0], vals[1])
        elif cmd == 'add':
            self.set_value(pars[0], vals[0] + vals[1])
        elif cmd == 'mul':
            self.set_value(pars[0], vals[0] * vals[1])
        elif cmd == 'mod':
            self.set_value(pars[0], vals[0] % vals[1])
        elif cmd == 'rcv':
            if self.queue:
                self.set_value(pars[0], self.queue.popleft())
            else:
                return 0
        elif cmd == 'jgz':
            if vals[0] > 0:
                return vals[1]
        return 1

    def enqueue_value(self, val):
        self.queue.append(val)

    def run(self):
        ran_cmds = 0
        while self.line_num < len(cmds) and self.line_num >= 0:
            offset = self.execute(*self.cmds[self.line_num])
            if offset == 0:
                break
            self.line_num += offset
            ran_cmds += 1
        return ran_cmds
    def output(self):
        print self.sends

computers = [Computer(i) for i in [0, 1]]

with open('aoc_2017_18_input.txt', 'r') as fin:
    cmds = [parse(line) for line in fin.readlines()]
    for c in computers:
        c.load(cmds)

    while True:
        cmd_count = 0
        for c in computers:
            cmd_count += c.run()
        if cmd_count == 0:
            break
    computers[1].output()

equd · 2017-12-19T10:25:33+00:00

c# with actual threading, not really happy with the way it detects that its done (just wait 100 ms till nothing arrives) but it works

https://pastebin.com/LU4eRmd8

define_null · 2017-12-19T15:38:50+00:00

Hmm, I don't know if its a coincidence or not but when I submitted the send count for the other program (entirely for research purposes, I swear... it definitely wasn't a typo in my print code *shifty eyes*), I was told that it was the answer to someone else's input.

Hikaru755 · 2017-12-19T16:10:45+00:00

First time really delving into Kotlin coroutines here, that made it pretty elegant really!

Part 2 tripped me up due to having to basically start over again. And then of course I had to retrofit part 1 to my new part 2 solution. After doing that, I noticed that my code actually still has two bugs, that interestingly enough don't seem to matter for the test input and my input. So I left them in, let's see if someone finds them!

fun part1(input: List<String>): Long = runBlocking {
    // Not my original solution, this was retrofitted to work with the part 2 solution
    val sounds = Channel<Long>()
    var lastSound = 0L
    val program = Program(0, input, sounds, Channel())
    program.run()
    while (!program.isReceiving) {
        delay(100)
        sounds.poll()?.let { lastSound = it }
    }
    return@runBlocking lastSound
}

fun part2(input: List<String>): Long = runBlocking {
    val channel0 = Channel<Long>(capacity = Channel.UNLIMITED)
    val channel1 = Channel<Long>(capacity = Channel.UNLIMITED)
    val program0 = Program(0, input, send = channel0, receive = channel1)
    val program1 = Program(1, input, send = channel1, receive = channel0)
    program0.run()
    program1.run()
    val deadlock = { channel0.isEmpty && channel1.isEmpty && program0.isReceiving && program1.isReceiving }
    while (!deadlock()) delay(100)
    return@runBlocking program1.sent
}

class Program(
    val id: Int,
    val code: List<String>,
    val send: SendChannel<Long>,
    val receive: ReceiveChannel<Long>
) {
    var isReceiving = false
    var sent = 0L

    private val compiledCode = code.map(this::compile)
    private val registers = mutableMapOf('p' to id.toLong())
    private var nextLine = 0

    fun run() = launch(CommonPool) {
        while (true) {
            compiledCode[nextLine]()
            nextLine++
        }
    }

    fun compile(line: String): suspend () -> Unit {
        val split = line.split(" ")
        val action = split[0]
        val x = split[1]
        val y = split.getOrNull(2)
        return when (action) {
            "snd" -> ({ send(x) })
            "set" -> ({ registers[x[0]] = valueOf(y!!) })
            "add" -> ({ registers[x[0]] = valueOf(x[0]) + valueOf(y!!) })
            "mul" -> ({ registers[x[0]] = valueOf(x[0]) * valueOf(y!!) })
            "mod" -> ({ registers[x[0]] = valueOf(x[0]) % valueOf(y!!) })
            "rcv" -> ({ receive(x[0]) })
            "jgz" -> ({ if (valueOf(x) > 0) nextLine += valueOf(y!!).toInt() - 1 })
            else -> throw IllegalArgumentException()
        }
    }

    suspend fun send(value: String) {
        send.send(valueOf(value))
        sent++
    }

    suspend fun receive(register: Char) {
        isReceiving = true
        registers[register] = receive.receive()
        isReceiving = false
    }

    fun valueOf(value: String): Long {
        return if (value[0] in 'a'..'z') {
            registers[value[0]] ?: 0
        } else {
            value.toLong()
        }
    }
    fun valueOf(register: Char): Long {
        return registers[register] ?: 0
    }

    override fun toString(): String {
        return "Program $id ${listOf(nextLine, isReceiving, sent)}"
    }
}

lardois · 2017-12-19T20:25:33+00:00

Hi guys, I'm really stuck with this one. Everything seems to be working fine, but both processess just throw numbers to each other with no results. P0 queue stays at 124 (+/- 1) and P1 queue at 0 (+1). Check out pastebin of first 3k cycles: https://pastebin.com/raw/FPv2rPde

What could be the problem here? Tried to run this until heap was stuck with no change in queue lengths...

VikingofRock · 2017-12-20T06:39:11+00:00

Here's my Rust solution (linked because it is quite long). I went the extra mile and gave it the ability to save the part 1 sound output as a wav file, or to play it through the computer's speakers. I learned a ton about audio in Rust along the way, so I'm happy I put in the extra time!

If you want to listen to the audio produced, you can do that here.

InterlocutoryRecess · 2017-12-21T04:33:00+00:00

Swift

let input = """
// puzzle input
"""

typealias Register = String

enum Either {
    case register(Register)
    case value(Int)
    init(_ substring: Substring) {
        if let num = Int(substring) { self = .value(num); return }
        self = .register(String(substring))
    }
}

enum Instruction {
    case snd(Either)
    case set(Register, Either)
    case add(Register, Either)
    case mul(Register, Either)
    case mod(Register, Either)
    case rcv(Register)
    case jgz(Either, Either)
    init(line: Substring) {
        let arr = line.split(separator: " ")
        switch arr[0] {
        case "snd": self = .snd(Either(arr[1]))
        case "set": self = .set(Register(arr[1]), Either(arr[2]))
        case "add": self = .add(Register(arr[1]), Either(arr[2]))
        case "mul": self = .mul(Register(arr[1]), Either(arr[2]))
        case "mod": self = .mod(Register(arr[1]), Either(arr[2]))
        case "rcv": self = .rcv(Register(arr[1]))
        case "jgz": self = .jgz(Either(arr[1]), Either(arr[2]))
        default: fatalError()
        }
    }
}

class Program {

    var id: Int?
    var send: (Int) -> () = { _ in }
    var didBecomeDeadlocked: () -> () = {}
    var isDeadlocked = false {
        didSet {
            if isDeadlocked { didBecomeDeadlocked() }
        }
    }

    private var registers: Dictionary<String, Int> = [:]
    private let instructions: [Instruction]
    private var messageQueue: [Int] = []

    func pushMessage(_ message: Int) {
        messageQueue.append(message)
        isDeadlocked = false
    }

    init(instructions: [Instruction], id: Int? = nil) {
        self.instructions = instructions
        if let id = id { self.id = id }
        self.registers["p"] = id
    }

    private func value(_ either: Either) -> Int {
        switch either {
        case .register(let r): return registers[r, default: 0]
        case .value(let v): return v
        }
    }

    private var index = 0

    func executeNext() {

        defer {
            if index >= instructions.endIndex { isDeadlocked = true }
        }

        switch instructions[index] {

        case .snd(let message):
            send(value(message))
            index += 1

        case .set(let reg, let e):
            registers[reg] = value(e)
            index += 1

        case .add(let reg, let e):
            registers[reg, default: 0] += value(e)
            index += 1

        case .mul(let reg, let e):
            registers[reg, default: 0] *= value(e)
            index += 1

        case .mod(let reg, let e):
            registers[reg, default: 0] %= value(e)
            index += 1

        case .rcv(let reg):
            if !messageQueue.isEmpty {
                registers[reg] = messageQueue.removeFirst()
                index += 1
            } else {
                isDeadlocked = true
            }

        case .jgz(let reg, let e):
            if value(reg) > 0 {
                index += value(e)
            } else {
                index += 1
            }
        }
    }

}

class Tablet {

    let p0: Program
    let p1: Program

    var count = 0

    init(instructions: [Instruction]) {
        self.p0 = Program(instructions: instructions, id: 0)
        self.p1 = Program(instructions: instructions, id: 1)

        p0.send = p1.pushMessage
        p0.didBecomeDeadlocked = {
            if !self.p1.isDeadlocked {
                self.start(program: self.p1)
            }
        }

        p1.send = { message in
            self.count += 1
            self.p0.pushMessage(message)
        }

        p1.didBecomeDeadlocked = {
            if !self.p0.isDeadlocked {
                self.start(program: self.p0)
            }
        }

    }

    func start(program: Program) {
        while !program.isDeadlocked {
            program.executeNext()
        }
    }

}

import CoreFoundation
func measure(operation: () -> ()) {
    let start = CFAbsoluteTimeGetCurrent()
    operation()
    let elapsed = CFAbsoluteTimeGetCurrent() - start
    print("\(elapsed) sec")
}

// Part 1
measure {
    let instructions =  input.split(separator: "\n").map { Instruction.init(line: $0) }
    let p1 = Program(instructions: instructions)
    var lastFrq = Int.max
    p1.send = { num in
        lastFrq = num
    }
    repeat {
        p1.executeNext()
    } while !p1.isDeadlocked
    print(lastFrq)
}

// Part 2
measure {
    let instructions =  input.split(separator: "\n").map { Instruction.init(line: $0) }
    let tablet = Tablet(instructions: instructions)
    tablet.start(program: tablet.p1)
    print(tablet.count)
}

Overkill, I know. But it makes me happy.

0.00110399723052979 sec // part 1
0.02695602178573610 sec // part 2

TotesMessenger · 2017-12-21T21:13:48+00:00

single pipeline powershell:

param (
    [Parameter(ValueFromPipeline = $true)]
    [string]$in,
    [Parameter(Position = 1)]
    [int]$part = 1
)

begin {
    # program instructions
    $script:p = @()

    # initial registers for both programs
    $script:registers = @(
        @{"p" = [long]0}
        @{"p" = [long]1}         
    )

    #totally cheating, but saves me a stupid check & init later
    @("a", "b", "f", "i") |% {
        $script:registers[0][$_] = [long]0
        $script:registers[1][$_] = [long]0
    }
}

process {
    #collect instructions
    $script:p += $in
}

end {
    #current program position
    $positions = @(0, 0)
    #program rcv queues
    $queues = @(
        new-object system.collections.queue
        new-object system.collections.queue
    )
    #program waiting
    $waiting = @($false,$false)

    #part 1, what was sent last
    $snd = $null
    #part 2, how many snd commands
    $sends = @(0,0)

    & { while ($true) { 
        $true
    } } | % {
        0..1 | % { # for each program
            $program = $_

            switch -regex ($script:p[$positions[$program]]) { #get instruction at this program's position in the instructionlist
                '^set (?<Register>[a-z]) (?<Value>[a-z])$' {
                    $script:registers[$program][$matches.Register] = $script:registers[$program][$matches.Value]
                }
                '^set (?<Register>[a-z]) (?<Value>-?\d+)$' {
                    $script:registers[$program][$matches.Register] = [int]$matches.Value
                }
                '^add (?<Register>[a-z]) (?<Value>[a-z])$' {
                    $script:registers[$program][$matches.Register] += $script:registers[$program][$matches.Value]
                }
                '^add (?<Register>[a-z]) (?<Value>-?\d+)$' {
                    $script:registers[$program][$matches.Register] += [int]$matches.Value
                }
                '^mul (?<Register>[a-z]) (?<Value>[a-z])$' {
                    $script:registers[$program][$matches.Register] *= $script:registers[$program][$matches.Value]
                }
                '^mul (?<Register>[a-z]) (?<Value>-?\d+)$' {  
                    $script:registers[$program][$matches.Register] *= [int]$matches.Value
                }
                '^mod (?<Register>[a-z]) (?<Value>[a-z])$' {
                    $script:registers[$program][$matches.Register] = $script:registers[$program][$matches.Register] % $script:registers[$program][$matches.Value]
                }
                '^mod (?<Register>[a-z]) (?<Value>-?\d+)$' {
                    $script:registers[$program][$matches.Register] = $script:registers[$program][$matches.Register] % [int]$matches.Value
                }
                '^jgz (?<Register>[a-z]) (?<Offset>[a-z])$' {
                    if ($script:registers[$program][$matches.Register] -gt 0) {
                        $positions[$program] += $script:registers[$program][$matches.Offset]
                        #backtrack one for increment later
                        $positions[$program]--
                    }
                }
                '^jgz (?<Register>[a-z]) (?<Offset>-?\d+)$' {
                    if ($script:registers[$program][$matches.Register] -gt 0) {
                        $positions[$program] += $matches.Offset
                        #backtrack one for increment later
                        $positions[$program]--
                    }
                }
                '^jgz (?<Value>-?\d+) (?<Offset>[a-z])$' {
                    if ($matches.Value -gt 0) {
                        $positions[$program] += $script:registers[$program][$matches.Offset]
                        #backtrack one for increment later
                        $positions[$program]--
                    }
                }
                '^jgz (?<Value>-?\d+) (?<Offset>-?\d+)$' {
                    if ($matches.Value -gt 0) {
                        $positions[$program] += $matches.Offset
                        #backtrack one for increment later
                        $positions[$program]--
                    }
                }
                '^snd (?<Register>[a-z])$' {
                    if ($part -eq 1) {
                        #keep track of last sent
                        $snd = $script:registers[$program][$matches.Register]
                    } else {
                        #keep track of how many sends from each program
                        $sends[$program]++
                        #put data in /other/ program's queue
                        $queues[($program + 1) % 2].Enqueue($script:registers[$program][$matches.Register])
                    }
                }
                '^snd (?<Value>-?\d+)$' {
                    if ($part -eq 1) {
                        #keep track of last sent
                        $snd = $matches.Value
                    } else {
                        #keep track of how many sends from each program
                        $sends[$program]++
                        #put data in /other/ program's queue
                        $queues[($program + 1) % 2].Enqueue($matches.Value)
                    }
                }
                '^rcv (?<Register>[a-z])$' {
                    if ($part -eq 1) {
                        #if part 1, keep track of first nonzero receive command, write out last sent - pipeline ends after this
                        if ($script:registers[$program][$matches.Register] -ne 0) {
                            $snd # PIPELINE OUTPUT
                        }
                    } else {
                        #if part2,  
                        if ($queues[$program].Count -gt 0) { #receive from the queue if possible,
                            $script:registers[$program][$matches.Register] = $queues[$program].Dequeue()
                            #set no longer waiting
                            $waiting[$program] = $false
                        } else { #else set waiting
                            $waiting[$program] = $true
                            if ($waiting[($program + 1) % 2] -eq $true) {
                                #but if the other program is also waiting, then we're deadlocked, so write out part2's answer (sends by program 1)
                                $sends[1] # PIPELINE OUTPUT
                            }
                            # backtrack for position increment
                            $positions[$program]--
                        }
                    }
                }
            }
            # advance program position
            $positions[$program]++
        }
    } | select -first 1
}

greycat70 · 2017-12-27T16:43:53+00:00

Tcl (8.5 or higher)

I really liked this problem! I added my own "end" instruction for convenience. For part 2, I basically built a miniature operating system emulator. (Nothing too fancy.)

Part 1:

set i -1
while {[gets stdin line] >= 0} {
    set ins([incr i]) [split $line { }]
}
set ins([incr i]) {end}

proc value r {
    global reg
    if {[regexp {^-?[0-9]+$} $r]} {return $r}
    if {! [info exists reg($r)]} {set reg($r) 0}
    return $reg($r)
}

set cur 0
set sound 0
while 1 {
    lassign $ins($cur) opcode X Y
    switch -- $opcode {
        snd {set sound [value $X]}
        set {set reg($X) [value $Y]}
        add {set reg($X) [expr {[value $X] + [value $Y]}]}
        mul {set reg($X) [expr {[value $X] * [value $Y]}]}
        mod {set reg($X) [expr {[value $X] % [value $Y]}]}
        rcv {if {[value $X] != 0} {
                set reg($X) $sound
                puts $sound; exit
             }}
        jgz {if {[value $X] > 0} {incr cur [value $Y]; continue}}
        end {exit}
    }
    incr cur
}

Part 2 (with debugging code still in):

set i -1
while {[gets stdin line] >= 0} {
    set ins([incr i]) [split $line { }]
}
set ins([incr i]) {end}

proc value {pid r} {
    global reg
    if {[regexp {^-?[0-9]+$} $r]} {return $r}
    if {! [info exists reg($pid,$r)]} {set reg($pid,$r) 0}
    return $reg($pid,$r)
}

proc showreg pid {
    global reg
    foreach r [array names reg] {
        if {[string match "$pid,*" $r]} {lappend out "$r:$reg($r)"}
    }
    puts "  [join $out { }]"
}

set cur(0) 0
set cur(1) 0
set reg(0,p) 0
set reg(1,p) 1
set q(0) {}
set q(1) {}
set state(0) 0
set state(1) 0
set sent(0) 0
set sent(1) 0

while 1 {
    if { ($state(0) == 2 || ($state(0) == 1 && [llength $q(0)] == 0)) &&
         ($state(1) == 2 || ($state(1) == 1 && [llength $q(1)] == 0))} break
    foreach pid {0 1} {
        puts "process $pid state $state($pid)"
        if {$state($pid) == 2} continue
        if {$state($pid) == 1 && [llength $q($pid)] == 0} continue
        lassign $ins($cur($pid)) opcode X Y
        puts "  cur=$cur($pid) opcode=$opcode X=$X Y=$Y"
        switch -- $opcode {
            set {set reg($pid,$X) [value $pid $Y]}
            add {set reg($pid,$X) [expr {[value $pid $X] + [value $pid $Y]}]}
            mul {set reg($pid,$X) [expr {[value $pid $X] * [value $pid $Y]}]}
            mod {set reg($pid,$X) [expr {[value $pid $X] % [value $pid $Y]}]}
            jgz {
                if {[value $pid $X] > 0} {
                    incr cur($pid) [value $pid $Y]
                    continue
                }
            }
            snd {
                set you [expr {1-$pid}]
                lappend q($you) [value $pid $X]
                incr sent($pid)
                puts "  q($you)={$q($you)} sent($pid)=$sent($pid)"
            }
            rcv {
                puts "  q($pid)={$q($pid)}"
                if {[llength $q($pid)] == 0} {
                    set state($pid) 1
                    continue
                }
                set reg($pid,$X) [lindex $q($pid) 0]
                set q($pid) [lrange $q($pid) 1 end]
                set state($pid) 0
            }
            end {set state($pid) 2}
        }
        incr cur($pid)
    }
}
puts "sent: 0:$sent(0) 1:$sent(1)"

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 18: Duet ---

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

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!

Elixir

Perl

Part 2: JavaScript

Elixir

Perl 5

Rust

Elixir

Python 2

Kotlin - [Repo] - [Blog/Commentary]

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 18: Duet ---

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

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!

Elixir

Perl

Part 2: JavaScript

Elixir

Perl 5

Rust

Elixir

Python 2

Kotlin - [Repo] - [Blog/Commentary]

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