Advent of Code 2019 Solution Megathread - Day 7: Amplification Circuit

/// Day 7: Amplification Circuit
/// 
/// Use the Intcode Interpreter to AMPLIFY POWER!

use std::fs;
use itertools::Itertools;

use crate::intcode::IntcodeInterpreter;

/// Parses the input.  Expects a single line of integers separated by
/// commas
fn parse_input() -> Vec<isize> {
    let text: String = fs::read_to_string("data/day7.txt").unwrap();
    let cleaned = text.trim();
    cleaned.split(",").map( |c| c.parse().unwrap()).collect()
}

pub fn run() {
    let numbers = parse_input();
    let mut max_output = 0;
    for comb in (5..=9).permutations(5) {
        let mut a = IntcodeInterpreter::new(numbers.clone());
        let mut b = IntcodeInterpreter::new(numbers.clone());
        let mut c = IntcodeInterpreter::new(numbers.clone());
        let mut d = IntcodeInterpreter::new(numbers.clone());
        let mut e = IntcodeInterpreter::new(numbers.clone());

        a.push_input(comb[0]);
        b.push_input(comb[1]);
        c.push_input(comb[2]);
        d.push_input(comb[3]);
        e.push_input(comb[4]);

        let mut a_input = 0;
        let mut out;
        loop {
            a.push_input(a_input);
            a.run();

            b.push_input(a.shift_output());
            b.run();

            c.push_input(b.shift_output());
            c.run();

            d.push_input(c.shift_output());
            d.run();

            e.push_input(d.shift_output());
            e.run();

            out = e.shift_output();

            if e.current_instruction() == 99 {
                break;
            }
            a_input = out;
        }
        println!("Got {}", out);
        if out > max_output {
            max_output = out;
        }
    }
    println!("Max output is: {}", max_output);

}

use std::io;
use std::collections::HashMap;

/// An Intcode Interpreter is a simple virtual machine that uses opcodes
/// to modify its internal memory
pub struct IntcodeInterpreter {
    memory: HashMap<usize, isize>,
    in_buffer: Vec<isize>,
    out_buffer: Vec<isize>,
    ip: usize,
    relative_base: isize,
}

impl IntcodeInterpreter {
    pub fn new(numbers: Vec<isize>) -> Self {
        let mut memory: HashMap<usize, isize> = HashMap::new();
        for (ind, num) in numbers.iter().enumerate() {
            memory.insert(ind, *num);
        }
        Self {
            memory,
            in_buffer: Vec::new(),
            out_buffer: Vec::new(),
            ip: 0,
            relative_base: 0,
        }
    }

    /// Sets a memory address to a value
    pub fn set(&mut self, position: usize, value: isize) {
        self.memory.insert(position, value);
    }

    /// Reads from a memory address
    pub fn get(&mut self, position: usize) -> isize {
        *self.memory.entry(position).or_default()
    }

    /// Shows the memory for debugging
    pub fn print(&self) {
        println!("{:?}", self.memory);
    }

    /// Get the current instruction
    pub fn current_instruction(&mut self) -> isize {
        self.get(self.ip) % 100
    }

    /// Add a value to the input queue
    pub fn push_input(&mut self, value: isize) {
        self.in_buffer.push(value);
        if self.current_instruction() == 98 {
            self.memory.insert(self.ip, self.memory[&self.ip] - 95);
            // Return the instruction to
            // a 3 while maintaining
            // argtype values
        }
    }

    pub fn count_output(&self) -> usize {
        self.out_buffer.len()
    }

    /// Pop a value off the output queue
    pub fn shift_output(&mut self) -> isize {
        if self.out_buffer.is_empty() {
            panic!("Shift from empty out buffer!");
        }
        self.out_buffer.remove(0)
    }

    /// Runs the program in memory until the stopcode (99) is reached
    /// 
    /// All new ops should have their own method.
    /// They take no rust args, but read in args as needed and
    /// shift the instruction pointer when they're done.
    /// Steps should be the number of args used + 1 for the opcode
    pub fn run(&mut self) {
        loop {
            match self.current_instruction() {
                1 => self.op1(),
                2 => self.op2(),
                3 => self.op3(),
                4 => self.op4(),
                5 => self.op5(),
                6 => self.op6(),
                7 => self.op7(),
                8 => self.op8(),
                9 => self.op9(),
                98 => return,  // Halt until receiving input
                99 => return,  // End of program
                _ => panic!("Unrecognized opcode {}.", self.get(self.ip)),
            };
        }
    }

    /// Reads a number from STDIN
    fn read_stdin() -> isize {
        let mut buffer = String::new();
        io::stdin().read_line(&mut buffer).expect("STDIN read failed.");
        buffer.trim().parse::<isize>().unwrap()
    }

    /// Write a number to STDOUT
    fn write_stdout(number: isize) {
        println!("{}", number);
    }

    /// Process the parameter mode and provide the value given
    /// as a parameter
    fn arg(&mut self, offset: usize) -> isize {
        let new_index = self.ip + offset;
        let mode = (self.memory[&self.ip] / 10isize.pow(1 + offset as u32)) % 10;
        if mode == 2 {
            let addr = self.relative_base + self.memory[&new_index];
            let val = self.get(addr as usize);
            self.get(addr as usize)
        } else if mode == 1 {
            self.memory[&new_index]
        } else if mode == 0 {
            self.get(self.memory[&new_index] as usize)
        } else {
            panic!("Unknown parameter mode {}", mode);
        }
    }

    /// Returns the address to write output to
    fn output_address(&self, offset: usize) -> usize {
        let mode = (self.memory[&self.ip] / 10isize.pow(1 + offset as u32)) % 10;
        let new_index = self.ip + offset;
        if mode == 0 {
            self.memory[&new_index] as usize
        } else if mode == 2 {
            (self.relative_base + self.memory[&new_index]) as usize
        } else {
            panic!("Output address with weird mode");
        }
    }

    /// Steps the IP forward "count" steps, wrapping if needed
    fn step(&mut self, count: usize) {
        self.ip = (self.ip + count) % self.memory.len();
    }

    /// Causes the interpreter to block until receiving input
    fn halt_on_input(&mut self) {
        // Update the last two digits from 03 to 98, but maintain
        // the argtype values
        self.memory.insert(self.ip, self.memory[&self.ip] + 95); 
    }

    /// Add [1] + [2], store in [3]
    fn op1(&mut self) {
        let in1 = self.arg(1);
        let in2 = self.arg(2);
        let out = self.output_address(3);

        self.set(out, in1 + in2);

        self.step(4);
    }

    /// Mult [1] * [2], store in [3]
    fn op2(&mut self) {
        let in1 = self.arg(1);
        let in2 = self.arg(2);
        let out = self.output_address(3);

        self.set(out, in1 * in2);

        self.step(4);
    }

    /// Read one value from STDIN and store it in [1]
    fn op3(&mut self) {
        let out = self.output_address(1);

        let val: isize;
        if self.in_buffer.is_empty() {
            self.halt_on_input();
            return;
        } else {
            val = self.in_buffer.remove(0);
        }
        self.set(out, val);

        self.step(2);
    }

    /// Read [1] and send it to STDOUT
    fn op4(&mut self) {
        let arg = self.arg(1);
        self.out_buffer.push(arg);

        self.step(2);
    }

    /// If [1] != 0, set IP -> [2], else nothing
    fn op5(&mut self) {
        if self.arg(1) != 0 {
            self.ip = self.arg(2) as usize;
        } else {
            self.step(3);
        }
    }

    /// if [1] == 0, set IP -> [2], else nothing
    fn op6(&mut self) {
        if self.arg(1) == 0 {
            self.ip = self.arg(2) as usize;
        } else {
            self.step(3);
        }
    }

    /// if [1] < [2], set [3] to 1, else 0
    fn op7(&mut self) {
        let out = self.output_address(3);

        if self.arg(1) < self.arg(2) {
            self.set(out, 1);
        } else {
            self.set(out, 0);
        }

        self.step(4);
    }

    /// if [1] == [2], set [3] to 1, else 0
    fn op8(&mut self) {
        let out = self.output_address(3);

        if self.arg(1) == self.arg(2) {
            self.set(out, 1);
        } else {
            self.set(out, 0);
        }

        self.step(4);
    }

    /// Shift relative base by [1]
    fn op9(&mut self) {
        self.relative_base += self.arg(1);
        self.step(2);
    }
}

// Shout out to MikeTheReader & Morganamilo for the help with part 2 of this one!

// Memory - initial puzzle input, a list of integers
const input = [3,8,1001,8,10.....3,9,1002,9,99];

// copy of initial input, so we can reset properly
let inputCopy = [...input];

// opcode 1 - get values at position 1&2 right after code, add together, store in position 3
function opcode1 (a, b, c, p, dir) {
  let valA = ptest(p[0], a, dir);
  let valB = ptest(p[1], b, dir);
  dir[c] = valA + valB;
  // console.log(`op1: ${valA} + ${valB} = ${valA + valB}`)
}

// opcode 2 - get values at position 1&2 right after code, multiply, store in position 3
function opcode2 (a, b, c, p, dir) {
  let valA = ptest(p[0], a, dir);
  let valB = ptest(p[1], b, dir);
  dir[c] = valA * valB;
  // console.log(`op2: ${valA} * ${valB} = ${valA * valB}`)
}

// opcode 3 - takes an input and stores in position 1
function opcode3 (iv, s, dir) {
  dir[s] = iv;
  // console.log(`op3: putting ${iv} into spot ${s}`)
}

// opcode 4 - outputs value at position 1
function opcode4 (s, p, dir) {
  let val = ptest(p[0], s, dir);
  // console.log(`op4: outputting ${val}`)
  return val;
}

// opcode 5 - if position 1 != 0, changes i to position 2; otherwise, does nothing
function opcode5 (a, b, inp, p, dir) {
  let valA = ptest(p[0], a, dir);
  let valB = ptest(p[1], b, dir);

  if (valA !== 0) {
    inp = valB;
  }
  // console.log(`op5: inst. pointer is now ${inp}`);
  return inp;
}

// opcode 6 - if position 1 == 0, changes i to position 2; otherwise, does nothing
function opcode6 (a, b, inp, p, dir) {
  let valA = ptest(p[0], a, dir);
  let valB = ptest(p[1], b, dir);

  if (valA === 0) {
    inp = valB;
  }
  // console.log(`op6: inst. pointer is now ${inp}`);

  return inp;
}

// opcode 7 - if position 1 < position 2, position 3 is set to 1; otherwise, it's set to 0
function opcode7 (a, b, c, p, dir) {
  let valA = ptest(p[0], a, dir);
  let valB = ptest(p[1], b, dir);

  if (valA < valB) {
    dir[c] = 1;
  } else {
    dir[c] = 0;
  }
  // console.log(`op7: comparing if ${valA} is < ${valB}`);
}

// opcode 8 - if position 1 == position 2, position 3 is set to 1; otherwise, it's set to 0
function opcode8 (a, b, c, p, dir) {
  let valA = ptest(p[0], a, dir);
  let valB = ptest(p[1], b, dir);

  if (valA == valB) {
    dir[c] = 1;
  } else {
    dir[c] = 0;
  }
  // console.log(`op8: comparing if ${valA} equals ${valB}`);
}

// allows parameter modes - checks for 0 or 1, decides if returning actual number called or position of number in input
function ptest(param, checkval, dir) {
  if (param == 0 || !param) {
    return dir[checkval];
  } else if (param == 1) {
    return checkval;
  }
}

// opcode 99 - stop program

// run through memory input, following instructions until 99 is hit
function runProgram(amp) {
  for (let i = amp.pointer; i < inputCopy.length; i++) {
    if (amp.directions[i] === 99) {
      if (amp.haltCalled) {
        return amp.output;
      }
      amp.haltCalled = true;
      haltsCalled++;
      amp.pointer = i;
      return amp.output;
    }

    let instruct = amp.directions[i].toString();
    let opval = parseInt(instruct.slice(-2), 10);
    let params = instruct.slice(0, -2).split('').reverse();


    let ione = amp.directions[i+1];
    let itwo = amp.directions[i+2];
    let ithree = amp.directions[i+3];

    switch (opval) {
      case 01:
        opcode1(ione, itwo, ithree, params, amp.directions);
        i += 3;
        break;
      case 02:
        opcode2(ione, itwo, ithree, params, amp.directions);
        i += 3;
        break;
      case 03:
        if (amp.requestedInputs === 0) {
          opcode3(amp.inputPhase, ione, amp.directions);
          i++;
          amp.requestedInputs++;
          break;
        } else if (amp.requestedInputs === 1) {
          opcode3(amp.inputInit, ione, amp.directions);
          i++;
          amp.requestedInputs++;
          break;
        } else {
          opcode3(amp.inputSig, ione, amp.directions);
          i++;
          break;
        }
      case 04:
        let res = opcode4(ione, params, amp.directions);
        amp.output = res;
        i++;
        amp.pointer = i + 1;
        return amp.output;
        break;
      case 05:
        let checkt = opcode5(ione, itwo, i, params, amp.directions);
        if (i != checkt) {
          i = checkt - 1;
        } else {
          i += 2;
        }
        break;
      case 06:
        let checkf = opcode6(ione, itwo, i, params, amp.directions);
        if (i != checkf) {
          i = checkf - 1;
        } else {
          i += 2;
        }
        break;
      case 07:
        opcode7(ione, itwo, ithree, params, amp.directions);
        i += 3;
        break;
      case 08:
        opcode8(ione, itwo, ithree, params, amp.directions);
        i += 3;
        break;
    }
  }
}



let maxSignal = 0;


// Didn't feel like creating this, so found a method here: https://stackoverflow.com/a/20871714
const permutator = (inputArr) => {
  let result = [];

  const permute = (arr, m = []) => {
    if (arr.length === 0) {
      result.push(m)
    } else {
      for (let i = 0; i < arr.length; i++) {
        let curr = arr.slice();
        let next = curr.splice(i, 1);
        permute(curr.slice(), m.concat(next))
      }
    }
  }

  permute(inputArr);

  return result;
}

let phaseSettingOptions = [0,1,2,3,4];
let phaseSettingOptions2 = [5,6,7,8,9];

let phaseSettings = permutator(phaseSettingOptions);
let phaseSettings2 = permutator(phaseSettingOptions2);

// phase 2 settings
let amps = [{
  'name': 'a',
  'pointer': 0,
  'inputPhase': 0,
  'inputInit': 0,
  'inputSig': 0,
  'requestedInputs': 0,
  'output': 0,
  'haltCalled': false,
  'directions': [...input]
},{
  'name': 'b',
  'pointer': 0,
  'inputPhase': 0,
  'inputInit': 0,
  'inputSig': 0,
  'requestedInputs': 0,
  'output': 0,
  'haltCalled': false,
  'directions': [...input]
},{
  'name': 'c',
  'pointer': 0,
  'inputPhase': 0,
  'inputInit': 0,
  'inputSig': 0,
  'requestedInputs': 0,
  'output': 0,
  'haltCalled': false,
  'directions': [...input]
},{
  'name': 'd',
  'pointer': 0,
  'inputPhase': 0,
  'inputInit': 0,
  'inputSig': 0,
  'requestedInputs': 0,
  'output': 0,
  'haltCalled': false,
  'directions': [...input]
},{
  'name': 'e',
  'pointer': 0,
  'inputPhase': 0,
  'inputInit': 0,
  'inputSig': 0,
  'requestedInputs': 0,
  'output': 0,
  'haltCalled': false,
  'directions': [...input]
},];

let haltsCalled = 0;

function runAmp(phase, init, sig, amp) {
  amp.inputPhase = phase;
  amp.inputInit = init;
  amp.inputSig = sig;
  let nextInput = runProgram(amp);
  return nextInput;
}

function runCycle(phase) {
  for (let j = 0; j < amps.length; j++) {
    let previous = j - 1;
    if (previous < 0) {
      previous = 4;
    }
    if (amps[j].pointer === 0) {
      amps[j].inputInit = runAmp(phase[j], amps[previous].output, 0, amps[j]);
    } else {
      amps[j].inputSig = runAmp(phase[j], amps[j].inputInit, amps[previous].output, amps[j]);
    }
  }
}

function resetValues() {
  for (let a = 0; a < amps.length; a++) {
    let thisAmp = amps[a];
    thisAmp.pointer = 0;
    thisAmp.inputPhase = 0;
    thisAmp.inputInit = 0;
    thisAmp.inputSig = 0;
    thisAmp.requestedInputs = 0;
    thisAmp.output = 0;
    thisAmp.haltCalled = false;
    thisAmp.directions = [...input];
  }
};

for (let i = 0; i < phaseSettings2.length; i++) {
  let phaseOrder = phaseSettings2[i];
  haltsCalled = 0;
  resetValues();
  do (
    runCycle(phaseOrder)
  ); while (haltsCalled !== 5);

  if (maxSignal === 0) {
    maxSignal = amps[4].output;
  } else if (amps[4].output > maxSignal) {
    maxSignal = amps[4].output;
    console.log(`best phase: ${phaseOrder}`);
  }
}

console.log(`Max signal: ${maxSignal}`);

import qualified Data.IORef          as IO
import qualified Control.Exception   as Exception
import qualified Control.Monad       as Monad
import qualified Data.List           as List
import qualified Data.Map.Strict     as Map
import qualified Data.Maybe          as Maybe
import qualified Data.Vector         as Vec
import qualified Data.Vector.Mutable as MVec
import qualified System.IO.Unsafe    as Unsafe
import qualified Data.IntMap.Strict as IntMap

data OpState = OpState
  { vmState           :: IntMap.IntMap Int
  , vmOutputs         :: Maybe Int
  , vmFramePtr        :: Maybe Int
  , vmInput           :: Maybe Int
  , vmBlocked         :: Bool
  } deriving (Eq, Show)

data AccessMode = Position
                | Immediate deriving (Eq, Show)

parseAccessMode :: Char -> AccessMode
parseAccessMode c =
  case c of
    '0' -> Position
    '1' -> Immediate

data Op = Add
        | Mult
        | Exit
        | Input
        | Output
        | JumpTrue
        | JumpFalse
        | StoreLT
        | StoreEq
        deriving (Eq, Show, Enum)

data Instruction = Instruction
  { _instrOp           :: Op
  , _instrArity        :: Int
  , _instrOperandModes :: [AccessMode]
  } deriving (Eq, Show)

parseInstruction :: Int -> Instruction
parseInstruction !instr =
  let [a,b,c,d,e] = take 5 $ (reverse $ show instr) <> repeat '0'
      operModes = map parseAccessMode [c,d,e]
      mkInstr op arity = Instruction { _instrOp = op, _instrArity = arity, _instrOperandModes = operModes }
  in case [b,a] of
       "99" -> mkInstr Exit 0
       "01" -> mkInstr Add 3
       "02" -> mkInstr Mult 3
       "03" -> mkInstr Input 1
       "04" -> mkInstr Output 1
       "05" -> mkInstr JumpTrue 2
       "06" -> mkInstr JumpFalse 2
       "07" -> mkInstr StoreLT 3
       "08" -> mkInstr StoreEq 3
       e    -> error $ "unexpected instruction: " <> e

readLoc :: IntMap.IntMap Int -> AccessMode -> Int -> Int
readLoc vec mode idx = do
  case mode of
    Immediate -> vec IntMap.! idx
    Position  -> vec IntMap.! (vec IntMap.! idx)

writeLoc :: IntMap.IntMap Int -> AccessMode -> Int -> Int ->  IntMap.IntMap Int
writeLoc vec mode idx val =
  case mode of
    Immediate -> IntMap.insert idx val vec
    Position  -> IntMap.insert (vec IntMap.! idx) val vec

step :: OpState -> OpState
step opState@(OpState _ _ Nothing _ _) = opState
step opState = do
  let
    (Just framePtr) = vmFramePtr opState
    binOp :: (Int -> Int -> Int)
          -> IntMap.IntMap Int
          -> (AccessMode, AccessMode, AccessMode)
          -> IntMap.IntMap Int
    binOp f v (mode1, mode2, mode3) =
        let in1 = readLoc v mode1 (framePtr + 1)
            in2 = readLoc v mode2 (framePtr + 2)
        in writeLoc v mode3 (framePtr + 3) (f in1 in2)

    handleInstruction :: Instruction -> OpState
    handleInstruction instruction@Instruction{..} =
      case _instrOp of
        Exit  -> opState{vmFramePtr = Nothing}
        Add   ->
          let
            st = binOp (+) (vmState opState) (_instrOperandModes !! 0,_instrOperandModes !! 1,_instrOperandModes !! 2)
          in opState{vmFramePtr = Just (framePtr + 4), vmState = st}
        Mult  ->
          let
            st = binOp (*) (vmState opState) (_instrOperandModes !! 0,_instrOperandModes !! 1,_instrOperandModes !! 2)
          in opState{vmFramePtr = Just (framePtr + 4), vmState = st}
        Input ->
          case vmInput opState of
            Nothing ->
              opState{vmBlocked = True}
            Just input ->
              let st = writeLoc (vmState opState) (_instrOperandModes !! 0) (framePtr + 1) input
              in opState{vmFramePtr = Just (framePtr + 2), vmInput = Nothing, vmBlocked = False, vmState = st}
        Output ->
          let outputVal = readLoc (vmState opState) (_instrOperandModes !! 0) (framePtr + 1)
          in opState{vmFramePtr = Just (framePtr + 2), vmOutputs = Just outputVal}
        JumpTrue ->
          let
            test      = readLoc (vmState opState) (_instrOperandModes !! 0) (framePtr + 1)
            framePtr' = if test == 0
                        then framePtr + 3
                        else readLoc (vmState opState) (_instrOperandModes !! 1) (framePtr + 2)
          in opState{vmFramePtr = Just framePtr'}
        JumpFalse ->
          let
            test      = readLoc (vmState opState) (_instrOperandModes !! 0) (framePtr + 1)
            framePtr' = if test /= 0
                        then framePtr + 3
                        else readLoc (vmState opState) (_instrOperandModes !! 1) (framePtr + 2)
          in opState{vmFramePtr = Just framePtr'}
        StoreLT ->
          let
            a = readLoc (vmState opState) (_instrOperandModes !! 0) (framePtr + 1)
            b = readLoc (vmState opState) (_instrOperandModes !! 1) (framePtr + 2)
            outputVal = if a < b then 1 else 0
            st = writeLoc (vmState opState) (_instrOperandModes !! 2) (framePtr + 3) outputVal
          in opState{vmFramePtr = Just (framePtr + 4), vmState = st}
        StoreEq ->
          let
            a = readLoc (vmState opState) (_instrOperandModes !! 0) (framePtr + 1)
            b = readLoc (vmState opState) (_instrOperandModes !! 1) (framePtr + 2)
            outputVal = if a == b then 1 else 0
            st = writeLoc (vmState opState) (_instrOperandModes !! 2) (framePtr + 3) outputVal
          in opState{vmFramePtr = Just (framePtr + 4), vmState = st}

    opCode = (vmState opState) IntMap.! framePtr
    parsed = parseInstruction opCode
    in handleInstruction parsed

toVec :: [Int] -> IntMap.IntMap Int
toVec prog = IntMap.fromList $ zip [0..] prog

runAmps :: [Int] -> Int -> [Int] -> OpState
runAmps prog initialInput ampVals = do
  let
    newState :: [Int] -> Int -> OpState
    newState program initialInput =
      runUntilBlocked $ OpState { vmState = toVec program
                   , vmOutputs = Nothing
                   , vmFramePtr = Just 0
                   , vmInput = Just initialInput
                   , vmBlocked = False
                   }

    runUntilBlocked :: OpState -> OpState
    runUntilBlocked st =
      let st' = step st
      in if (vmBlocked st' || Nothing == (vmFramePtr st'))
         then st'
         else runUntilBlocked st'

    transferIO :: OpState -> OpState -> OpState
    transferIO oldSt newSt =
      let (Just o) = vmOutputs oldSt
      in newSt { vmInput = Just o }

    ampStep :: [OpState] -> Int -> [OpState]
    ampStep (a:rest) !n =
      let
        a' = runUntilBlocked $ a{vmInput = Just n}
      in reverse $ List.foldl' go [a'] rest
      where
        go :: [OpState] -> OpState -> [OpState]
        go st@(prev:_) !next =
          (runUntilBlocked $ transferIO prev next) : st

    loop amps n =
      let
        stepState = ampStep amps n
        nextInput = (Maybe.fromJust . vmOutputs . last $ stepState)
      in
        case (vmFramePtr . last $ stepState) of
          Nothing -> stepState
          _ -> loop stepState nextInput

    amplifiers = map (newState prog) ampVals
    in last $ loop amplifiers 0

part2' :: [Int] -> [Int] -> Int
part2' prog args =
  let OpState{..} = runAmps prog 0 args
  in (Maybe.fromJust vmOutputs)

part2 :: [Int] -> Int
part2 prog =
  maximum . map (part2' prog) $ List.permutations [5..9]

from itertools import permutations

def get_permutations(li):
    for permutation in permutations(li):
        yield permutation

def get_modes(modes):
    return [int(mode) for mode in [modes[2], modes[1], modes[0], modes[3:]]]


class Computer:
    def __init__(self, data):
        self.idx = 0
        self.data = data[:]
        self.done = False
        self.output = None
        self.inputs = []

    def get_params(self, mode1, mode2):
        return self.get_param(mode1, 1), self.get_param(mode2, 2)

    def get_param(self, mode, increment):
        if mode == 0:
            return self.data[self.data[self.idx + increment]]
        return self.data[self.idx + increment]

    def add(self, param1, param2):
        return param1 + param2

    def multiply(self, param1, param2):
        return param1 * param2

    def less_than(self, param1, param2):
        return 1 if param1 < param2 else 0

    def equals(self, param1, param2):
        return 1 if param1 == param2 else 0

    def jump_if_true(self, mode1, mode2):
        param1, param2 = self.get_params(mode1, mode2)
        return param2 if param1 != 0 else self.idx + 3

    def jump_if_false(self, mode1, mode2):
        param1, param2 = self.get_params(mode1, mode2)
        return param2 if param1 == 0 else self.idx + 3

    def calculate(self, input_val):
        self.inputs.append(input_val)
        while True:
            mode1, mode2, mode3, opcode = get_modes(f"{self.data[self.idx]:05}")
            if opcode == 1:
                param1, param2 = self.get_params(mode1, mode2)
                self.data[self.data[self.idx + 3]] = self.add(param1, param2)
                self.idx += 4
            elif opcode == 2:
                param1, param2 = self.get_params(mode1, mode2)
                self.data[self.data[self.idx + 3]] = self.multiply(param1, param2)
                self.idx += 4
            elif opcode == 3:
                self.data[self.data[self.idx + 1]] = self.inputs.pop(0)
                self.idx += 2
            elif opcode == 4:
                self.output = self.data[self.data[self.idx + 1]]
                self.idx += 2
                return self.output
            elif opcode == 5:
                self.idx = self.jump_if_true(mode1, mode2)
            elif opcode == 6:
                self.idx = self.jump_if_false(mode1, mode2)
            elif opcode == 7:
                param1, param2 = self.get_params(mode1, mode2)
                self.data[self.data[self.idx + 3]] = self.less_than(param1, param2)
                self.idx += 4
            elif opcode == 8:
                param1, param2 = self.get_params(mode1, mode2)
                self.data[self.data[self.idx + 3]] = self.equals(param1, param2)
                self.idx += 4
            elif opcode == 99:
                self.done = True
                return self.output


with open("input.txt") as _file:
    for line in _file:
        input_vals = [int(num) for num in line.split(",")]
        max_output_signal = 0
        for permutation in get_permutations([0, 1, 2, 3, 4]):
            output_signal = 0
            for input_signal in permutation:
                computer = Computer(input_vals[:])
                computer.inputs.append(input_signal)
                output_signal = computer.calculate(output_signal)
            max_output_signal = max(max_output_signal, output_signal)
        print(f"Part 1: {max_output_signal}")

        max_output_signal_2 = 0
        for permutation in get_permutations([5, 6, 7, 8, 9]):
            computers = [Computer(input_vals[:]) for _ in range(5)]
            output_signal = 0
            for computer, phase_setting in zip(computers, permutation):
                computer.inputs.append(phase_setting)
            while computers[-1].done == False:
                for computer in computers:
                    output_signal = computer.calculate(output_signal)
            max_output_signal_2 = max(output_signal, max_output_signal_2)
        print(f"Part 2: {max_output_signal_2}")

const parameterCount = { 1: 3, 2: 3, 3: 1, 4: 1, 5: 2, 6: 2, 7: 3, 8: 3, 99: 0 };
const codes = input.split(',').map(Number);

// As amplifiers are now stateful machines, we'll sort out to generators again.
// A copy of the memory and the input stack is given.
function* createProgramInstance(localCodes, ...stack) {
  let instructionPointer = 0;
  function* getInstructions() {
    while (instructionPointer < localCodes.length) {
      const instruction = localCodes[instructionPointer];
      const opcode = instruction % 100;
      const modes = Array.from({ length: 3 }, (_, index) => Math.floor(instruction / 10 ** (index + 2) % 10));
      const paramCount = parameterCount[opcode];
      const params = localCodes.slice(instructionPointer + 1, instructionPointer + paramCount + 1);
      instructionPointer += paramCount + 1;
      yield { opcode, modes, params };
    }
  }

  function getValue(index, mode) {
    return mode === 0 ? localCodes[index] : index;
  }

  function execute({ opcode, modes, params }) {
    switch (opcode) {
      case 1:
        localCodes[params[2]] = getValue(params[0], modes[0]) + getValue(params[1], modes[1]);
        break;
      case 2:
        const result = getValue(params[0], modes[0]) * getValue(params[1], modes[1]);
        localCodes[params[2]] = result;
        break;
      case 3:
        localCodes[params[0]] = stack.shift();
        break;
      case 4:
        return getValue(params[0], modes[0]);
      case 5:
        if (getValue(params[0], modes[0])) {
          instructionPointer = getValue(params[1], modes[1]);
        }
        break;
      case 6:
        if (getValue(params[0], modes[0]) === 0) {
          instructionPointer = getValue(params[1], modes[1]);
        }
        break;
      case 7:
        localCodes[params[2]] = +(getValue(params[0], modes[0]) < getValue(params[1], modes[1]));
        break;
      case 8:
        localCodes[params[2]] = +(getValue(params[0], modes[0]) === getValue(params[1], modes[1]));
        break;
    }
  }

  for (const instruction of getInstructions()) {
    if (instruction.opcode === 99) {
      return;
    }
    const output = execute(instruction);
    if (typeof output === 'number') {
      // In order to resume execution, we get a new input (passed with .next())
      stack.push(yield output);
    }
  }
}

// Given a number, returns the corresponding permutation of 0-length.
// Can surely be improved, but it's definitely not the bottleneck.
function getPermutation(length, index) {
  const items = Array.from({ length }, (_, i) => i);
  let factorial = 1;
  return items.reduce((permutation, num) => {
    const itemIdx = Math.floor(index / factorial) % (num + 1);
    factorial *= num + 1;
    permutation.splice(itemIdx, 0, num);
    return permutation;
  }, []);
}

function createAmplifier(phaseSetting, initialInput) {
  const ampCodes = [ ...codes ];
  return createProgramInstance(ampCodes, phaseSetting, initialInput);
}

const AMPS = 5;

// Basically, AMPS!
let permutationCount = 1;
for (let i = 1; i <= AMPS; i++) {
  permutationCount *= i;
}

function runPermutation(permutation) {
  let previousOutput = 0;
  const amplifiers = [];
  let counter = 0;
  while (true) {
    const index = counter % AMPS;
    if (amplifiers.length - 1 < index) {
      amplifiers.push(createAmplifier(permutation[index], previousOutput));
    }
    const amplifier = amplifiers[index];
    const { value } = amplifier.next(previousOutput);
    if (typeof value === 'number') {
      previousOutput = value;
    } else {
      return previousOutput;
    }
    counter++;
  }
}

const results = [];
for (let i = 0; i < permutationCount; i++) {
  const permutation = getPermutation(AMPS, i).map(num => num + 5);
  const result = runPermutation(permutation);
  results.push(result);
}
console.log(Math.max(...results));

const INSTRUCTIONS = {
  ADD: 1,
  MULT: 2,
  INPUT: 3,
  OUTPUT: 4,
  JUMP_IF_TRUE: 5,
  JUMP_IF_FALSE: 6,
  LESS_THAN: 7,
  EQUALS: 8,
  HALT: 99
}

function runProgram(instructions) {
  instructions = instructions.slice()

  return function* amplifier() {
    let lastOutput = null
    for (let i = 0; i < instructions.length; ++i) {
      const instruction = instructions[i]
      const parsed = String(instruction)
        .padStart(5, '0')
        .split('')
      const valueMode = (value, mode = '0') =>
        mode === '0' ? instructions[value] : value
      const opCode = Number(parsed.slice(3).join(''))
      const modes = parsed.slice(0, 3)
      switch (opCode) {
        case INSTRUCTIONS.ADD: {
          const x = valueMode(instructions[++i], modes[2])
          const y = valueMode(instructions[++i], modes[1])
          instructions[instructions[++i]] = x + y
          break
        }
        case INSTRUCTIONS.MULT: {
          const x = valueMode(instructions[++i], modes[2])
          const y = valueMode(instructions[++i], modes[1])
          instructions[instructions[++i]] = x * y
          break
        }
        case INSTRUCTIONS.INPUT: {
          instructions[instructions[++i]] = yield { type: 'INPUT' }
          break
        }
        case INSTRUCTIONS.OUTPUT: {
          lastOutput = valueMode(instructions[++i], modes[2])
          yield { type: 'OUTPUT', value: lastOutput }
          break
        }
        case INSTRUCTIONS.JUMP_IF_TRUE: {
          const compare = valueMode(instructions[++i], modes[2])
          const jumpTo = valueMode(instructions[++i], modes[1]) - 1
          if (compare != 0) {
            i = jumpTo
          }
          break
        }
        case INSTRUCTIONS.JUMP_IF_FALSE: {
          const compare = valueMode(instructions[++i], modes[2])
          const jumpTo = valueMode(instructions[++i], modes[1]) - 1
          if (compare == 0) {
            i = jumpTo
          }
          break
        }
        case INSTRUCTIONS.LESS_THAN: {
          const x = valueMode(instructions[++i], modes[2])
          const y = valueMode(instructions[++i], modes[1])
          instructions[instructions[++i]] = x < y ? 1 : 0
          break
        }
        case INSTRUCTIONS.EQUALS: {
          const x = valueMode(instructions[++i], modes[2])
          const y = valueMode(instructions[++i], modes[1])
          instructions[instructions[++i]] = x === y ? 1 : 0
          break
        }
        case INSTRUCTIONS.HALT:
          return lastOutput
      }
    }
  }
}

const permutations = inputArr => {
  let result = []

  const permute = (arr, m = []) => {
    if (arr.length === 0) {
      result.push(m)
    } else {
      for (let i = 0; i < arr.length; i++) {
        let curr = arr.slice()
        let next = curr.splice(i, 1)
        permute(curr.slice(), m.concat(next))
      }
    }
  }

  permute(inputArr)

  return result
}

function part1(instructions) {
  const allInputs = permutations([0, 1, 2, 3, 4])
  const results = allInputs.map(inputs => {
    const amplifiers = inputs.map((input, i) => {
      const amplifier = runProgram(instructions)()
      amplifier.next()
      // set phase
      const state = amplifier.next(input)
      const name = String.fromCharCode(i + 65)
      return { amplifier, state, name }
    })

    let power = 0

    for (const amp of amplifiers) {
      const { amplifier } = amp
      const out = amplifier.next(power)
      power = out.value.value
    }

    return power
  })

  return results.reduce((p, v) => Math.max(p, v), 0)
}

function part2(instructions) {
  const allInputs = permutations([9, 8, 7, 6, 5])
  const results = allInputs.map(inputs => {
    const amplifiers = inputs.map((input, i) => {
      const amplifier = runProgram(instructions)()
      amplifier.next()
      // set phase
      const state = amplifier.next(input)
      const name = String.fromCharCode(i + 65)
      return { amplifier, state, name }
    })

    let power = 0

    while (amplifiers[amplifiers.length - 1].state.done === false) {
      for (const amp of amplifiers) {
        const { amplifier } = amp
        const out = amplifier.next(power)
        // continue to next input
        amp.state = amplifier.next()
        power = out.done ? out.value : out.value.value
      }
    }

    return power
  })

  return results.reduce((p, v) => Math.max(p, v), 0)
}

if (process.argv[1] === __filename) {
  const input = require('fs')
    .readFileSync(0)
    .toString()

  const instructions = input.split(',').map(Number)

  const p1Max = part1(instructions)
  console.log(p1Max)

  const p2Max = part2(instructions)
  console.log(p2Max)
}

import 'dart:async';
import 'dart:io';
import 'dart:math' as math;

import './tools/intcode_computer.dart';
import './tools/permutations.dart';

//! Part 1 of day 7 is in day_7.py

void main() async {
  var input = (await File('inputs/day_7.txt').readAsString())
      .split(',')
      .map((a) => int.parse(a))
      .toList();

  run(input);
}

void run(input) async {
  var permutations = findAllPermutations('56789');

  int max;
  for (var permutation in permutations) {
    var out = await runCycle(input, permutation);

    max = math.max(max ?? 0, out);
  }

  print(max);
}

Future<int> runCycle(input, String permutation) async {
  var controllers = List.generate(5, (_) => StreamController());

  /// Creating a list of the broadcast streams of the controllers so that I can subscribe to them from here
  var streams = List.generate(
    5,
    (i) => controllers[i].stream.asBroadcastStream(),
  );

  /// Create a list of intcode computers - the amplifiers
  var comps = List.generate(
    5,
    (i) => IntcodeComputer(List.from(input),

        /// Giving each computer the broadcast stream at its index as the input stream and the controller
        /// of an index one higher as the output stream, which means the computer will output to the next
        /// computer's input stream. The last computer outputs to the first computer's stream
        inputStream: streams[i],
        outputStream: controllers[i + 1 < 5 ? i + 1 : 0]),
  );

  var split = permutation.trim().split('');

  /// Add the phase setting of the computer to that computer's input stream as the first input
  for (int i = 0; i < 5; i++) {
    controllers[i].sink.add(int.parse(split[i]));
  }

  /// Provide the first computer with the input signal 0
  controllers[0].sink.add(0);

  /// Keep track of every input to the first computer (ie every output of the last computer). The
  /// last value this will have will be the last value of the operation
  int last;
  streams.first.listen((output) => last = output);

  /// Run all computers, but keep a reference of the last computer run so that we can wait until it
  /// finishes before closing the stream controllers and returning the last value
  for (int i = 0; i < comps.length - 1; i++) comps[i].run();
  var run4 = comps[4].run();
  await run4;

  /// Close all stream controllers to prevent memory leaks
  for (var controller in controllers) controller.close();

  return last;
}