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

Did you get your IntCode machine just right on Day 5? Well, too bad, it was wrong.

Day 7 - The Problem

Looks like we need more power. And we're given some more parts to fix up our module to scrape a few more Joules out here and there. Unfortunately, our supply elves forgot to send us the documentation, and we have to find the optimal solution ourselves.

Part 1 is about finding the permutation of amplifiers that gives us the best output. Oh, and your IntCode compiler needs to be able to take multiple inputs now.

Part 2 decides that we need to create a feedback loop. I'm interested to see what people come up with for this one. Maybe we can fake the async?

This one swerves right back into hard territory for me. At the time of posting this, I've only solved part 1, and I may not be able to return to part 2 until Sunday! Calamity! (Ah well, such is life!)

Ongoing Meta

Dev.to List of Leaderboards

• 120635-5c140b9a - provided by Linda Thompson

If you were part of Ryan Palo's leaderboard last year, you're still a member of that!

If you want me to add your leaderboard code to this page, reply to one of these posts and/or send me a DM containing your code and any theming or notes you’d like me to add. (You can find your private leaderboard code on your "Private Leaderboard" page.)

I'll edit in any leaderboards that people want to post, along with any description for the kinds of people you want to have on it. (My leaderboard is being used as my office's leaderboard.) And if I get something wrong, please call me out or message me and I’ll fix it ASAP.

There's no limit to the number of leaderboards you can join, so there's no problem belonging to a "Beginner" and a language specific one if you want.

Neat Statistics

I'm planning on adding some statistics, but other than "what languages did we see yesterday" does anyone have any ideas?

Languages Seen On Day 06

• JavaScript × 4
• Python × 2
• Clojure × 1
• Elixir × 1
• Java × 1
• Kotlin × 1
• PHP × 1
• Prolog × 1
• Swift × 1

Many thanks to special guest stat compiler Massimo Artizzu

Comments

[Akansha Yadav]

Hi,
Someone please help me understand part 2 of day 7
I am trying to get the answer given in first example of part two.
The input is
3,26,1001,26,-4,26,3,27,1002,27,2,27,1,27,26,
27,4,27,1001,28,-1,28,1005,28,6,99,0,0,5
For sequence 9,8,7,6,5
First input I gave was 9 as phase setting
Then gave 0 at the second occurrence of opcode 3
The program proceeds but it encounters opcode 5 at position 23 and resets my address pointer to 6. At 6 again the opcode is 3. Now here I give 8(next phase setting) or previous output value? Also in this way my program is not reaching 99 and it kept running until i killed it.

[Jon Bristow]

Roughly I think:

• The input of an amp is tied to the output of the previous amps output (A goes to B, C goes to D, E goes to A)
• if an amp has no inputs, it needs to suspend until it has some.
• there’s nothing preventing an amp from executing if it doesn’t need an input

So... when the first amp gets to its third or later input, it needs to wait until it receives an output from the last amp.

Once all amps reach 99, the answer is the last outputted value from the last amp.

[Akansha Yadav]

Got the output. Its 3:30 AM and I can finally sleep now.

[John Persico]

Hello...
Believe it or not, I'm still not getting how Part 2 works... I like the way you spelled things out in your post per the sample data. Enter 9, then enter 0, etc. Can you do something similar with the understanding you've gained here? I would truly appreciate it. Thanks.

[Jon Bristow]

My attempt:

In part 1, a sequence of 2 amps (A0,A1) will operate like so:

A0-Start
A0-asks for phase number (0)
A0-asks for input (0)
A0-outputs oa1
A0-ends
A1-starts
A1-asks for a phase number (1)
A1 asks for input (oa1)
A1 outputs oa2 <—answer
A1 ends

Part 2 is... complicated to diagram, but I will try (again with two amps, A5 and A6)

A5	A6
Start	Start
input read: phase (5)	input read: phase (6)
input read from init: 0	input needed
output o1a5
input needed	input read from A5: o1a5
	output o1a6
input read from A6: o1a6	input needed
output o2a6
end	input read from A5: o2a6
	output o2a6 (answer)
	end

Obviously the prompt uses 5 amps, and your input code produces a larger number of outputs per amp than my example. But I think this is the minimal state diagram possible that shows off the difference.

Please feel free to ask clarifying questions!

[John Persico]

Thanks for replying... I'm a new programmer, and I'm not sure why, but things still aren't making sense. Let me tell you what I'm doing. First of all, Part 1 works fine for me. This is what I do for Part 2 (sample 1).

Sample one is:

Max thruster signal 139629729 (from phase setting sequence 9,8,7,6,5):
3,26,1001,26,-4,26,3,27,1002,27,2,27,1,27,26,
27,4,27,1001,28,-1,28,1005,28,6,99,0,0,5

So...
I start the program, I guess it would be on Amp A. It asks for input, and I give it 9 (from the phase setting sequence above). Then it asks for a second input, and I give it 0 (from the instructions in Part 2). At that point I get an output of 5 and the program stops... Here I have a few questions... 1) should the program have stopped? 2) When I start up the program on Amp B do I start with fresh data (above), or do I use the updated data (I'm using a hash table).

So, then, I guess I start Amp B; it asks for an input. I give it 8, the second number in the phase setting sequence. It asks for another input, and I give it a 5 (from the output above). At that point the program stops and outputs 14. So, at this point I have two amps that have already stopped. This goes on until I get to the fifth amp and I get an output there. But, Amp A has already stopped (it stopped right away). So, what do I do with the output I just got from the fifth amp? It's not the solution; it's a low number.

Hopefully, some of this makes sense. If I can't get the sample to work, I don't know how I'm going to get the puzzle data to work. Any replies would be very welcome.

[Jon Bristow]

The key to debugging what you have here is probably knowing why your program stopped.

In my initial version of the IntCode interpreter would explode when it tried to read input when there was none to give it.

Each Amp should "pause", but not stop when it needs input that isn't there.

[Rebecca Skinner]

Here's my part 2 solution in #haskell. I ended up needing to do some substantial refactoring from my previous solution that I'd used for day 5 as well as part 1. My original version attempting to go for performance by using mutable vectors to store the program state, ostensibly allowing for more performant seeks and writes to the program state. I started to extend this approach using IORefs to program state and some other clever trickery. Although I managed to get constant memory utilization, the performance was so bad the program never actually finished running.

After profiling didn't help enough, and I verified that there was nothing unsound about my algorithm, I decided to start from the ground up with the simplest solution and went back to a pure implementation using record updates to manage all of the changes to start, and manually sending IO between the amplifiers. Once again proving that when it comes to optimization I'm never as clever as I think I am, the compiler did it's job and took my naive implementation and gave me a version that finished in a couple hundred milliseconds.

My new version needs some refactoring still, both for readability and ergonomics during future challenges, but here is the version left on my disk from when I finally finished up at 5am:

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]

[Massimo Artizzu]

Yoooo and I thought day 5 was annoying 😫

Anyway... JavaScript. It has this nice generator thing that I basically never used professionally and very rarely by myself, and here I am using them twice here. But you know, they're quite good for stateful machines. (Which is also why I rarely use them - like many others, I prefer stateless approaches.)

This is the solution for the second part, as the first can run the first (except for the phase settings, where I just add 5 to the permutation's elements - see at the end).

Many parts are the same of day 5 of course. Sorry for the repetition.

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

See text, input and first part on my repo.

[Linda Thompson]

Horray, finally got part 2 solved!! happy dance Took FOREVER but I finally got it working. This will be the part 2 solution in JavaScript (part 1 was very similar, just slightly more simplified and didn't involve the objects I created for each amp).

// 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}`);

[Rizwan]

Day 7 with swift

import Cocoa

extension BinaryInteger {
    var digits: [Int] {
        return String(describing: self).compactMap { Int(String($0)) }
    }
}

class Amplifier {
    var done = false
    var setting: Int = 0
    var output: Int!
    var numbers: [Int] = []
    var index = 0
    var settingUsed = false

    func computeIntCodeWithStatus(_ inputIds: [Int]) -> Int {
        guard done == false else { return output }
        //var numbers = input
        //var output: Int = -1
        func add(_ aPosition: Int, _ bPosistion: Int) -> Int {
            return numbers[aPosition] + numbers[bPosistion]
        }

        func multiply(_ aPosition: Int, _ bPosistion: Int) -> Int {
            return numbers[aPosition] * numbers[bPosistion]
        }

        while true {
            let optcode = numbers[index]
            let instruction = ((optcode.digits.dropLast().last ?? 0) * 10) + optcode.digits.last!
            let numberOfValues = 4
            var parameters: [Int] = []
            if (instruction != 99 && instruction != 4) {
                parameters = Array(numbers[index+1...index+numberOfValues])
            }
            let digits = optcode.digits

            func getValue(_ i: Int) -> Int {
                return digits.dropLast(2 + i).last == 1 ? numbers[index + 1 + i] : numbers[numbers[index + 1 + i]]
            }
            func getValues() -> [Int] {
                var values : [Int] = []
                values.append(getValue(0))
                values.append(getValue(1))
                return values
            }

            if instruction == 01 {
                let values = getValues()
                let result = values[0] + values[1]
                numbers[parameters[2]] = result
                index = index + numberOfValues
            }
            else if instruction == 02 {
                let values = getValues()
                let result = values[0] * values[1]
                numbers[parameters[2]] = result
                index = index + numberOfValues
            }
            else if optcode == 3 || instruction == 03 {
                let parameter = numbers[index + 1]
                let input: Int = settingUsed ? inputIds[1] : inputIds[0];
                settingUsed = true
                numbers[parameter] = input
                index = index + 2
            }
            else if optcode == 4 || instruction == 04 {
                let parameter = numbers[index + 1]
                output = numbers[parameter]
                index = index + 2
                return output
            }
            else if instruction == 5 {
                let values = getValues()
                if values[0] != 0 {
                    index = values[1]
                }
                else {
                    index = index + 3
                }
            }
            else if instruction == 6 {
                let values = getValues()
                if values[0] == 0 {
                    index = values[1]
                }
                else {
                    index = index + 3
                }
            }
            else if instruction == 07 {
                let values = getValues()
                let result = values[0] < values[1] ? 1 : 0
                numbers[parameters[2]] = result
                index = index + 4
            }
            else if instruction == 08 {
                let values = getValues()
                let result = values[0] == values[1] ? 1 : 0
                numbers[parameters[2]] = result
                index = index + 4
            }
            else if optcode == 99 {
                done = true
                return output
            }
            else {
                fatalError("unexpected optcode \(instruction)")
            }
        }
    }
}

var input = """
3,8,1001,8,10,8,105,1,0,0,21,42,67,88,105,114,195,276,357,438,99999,3,9,101,4,9,9,102,3,9,9,1001,9,2,9,102,4,9,9,4,9,99,3,9,1001,9,4,9,102,4,9,9,101,2,9,9,1002,9,5,9,1001,9,2,9,4,9,99,3,9,1001,9,4,9,1002,9,4,9,101,2,9,9,1002,9,2,9,4,9,99,3,9,101,4,9,9,102,3,9,9,1001,9,5,9,4,9,99,3,9,102,5,9,9,4,9,99,3,9,102,2,9,9,4,9,3,9,101,1,9,9,4,9,3,9,101,2,9,9,4,9,3,9,1001,9,2,9,4,9,3,9,102,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,1,9,4,9,3,9,102,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,101,2,9,9,4,9,99,3,9,1002,9,2,9,4,9,3,9,1001,9,2,9,4,9,3,9,102,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,101,1,9,9,4,9,3,9,101,1,9,9,4,9,3,9,1002,9,2,9,4,9,99,3,9,102,2,9,9,4,9,3,9,101,1,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,102,2,9,9,4,9,3,9,101,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,1001,9,2,9,4,9,3,9,1001,9,1,9,4,9,99,3,9,1002,9,2,9,4,9,3,9,1001,9,1,9,4,9,3,9,101,2,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,101,2,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,102,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,2,9,4,9,99,3,9,1002,9,2,9,4,9,3,9,101,1,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,102,2,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,1,9,4,9,3,9,101,2,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,1002,9,2,9,4,9,99
""".components(separatedBy: ",").compactMap{Int($0)}
extension Array {
    var permutations: [[Element]] {
        guard count > 0 else {
            return [[]]
        }

        return indices
            .flatMap { index -> [[Element]] in
                let first = self[index]
                var rest = self
                rest.remove(at: index)
                return rest.permutations.map { [first] + $0 }
        }
    }
}
func partOne() {
    var outputs: [Int] = []
    for settings in [0,1,2,3,4].permutations {
        var inputSignal = 0
        for setting in settings {
            let amplifier = Amplifier()
            amplifier.setting = setting
            amplifier.numbers = input
            inputSignal = amplifier.computeIntCodeWithStatus([setting,inputSignal])
        }
        outputs.append(inputSignal)
    }
    print("Max thruster signal : \(outputs.max() ?? 0)")
}

func partTwo() {
    var outputs: [Int] = []
    for settings in [5,6,7,8,9].permutations {
        var inputSignal = 0
        var amplifiers: [Amplifier] = []
        for setting in settings {
            let amplifier = Amplifier()
            amplifier.setting = setting
            amplifier.numbers = input
            amplifiers.append(amplifier)
        }
        while !(amplifiers.last?.done ?? false) {
            for amplifier in amplifiers {
                inputSignal = amplifier.computeIntCodeWithStatus([amplifier.setting,inputSignal])
            }
        }
        outputs.append(inputSignal)
    }

    print("Max thruster signal : \(outputs.max() ?? 0)")
}

partOne()
partTwo()

[Johnny]

I did it all in sync, runs well enough nonetheless.

(load-file "intcode.clj")

(ns Day07
  (:require intcode)
  (:import (clojure.lang PersistentQueue)))

; Returns a sequence of all possible permutations for a given collection.
(defn permutations [coll]
  (lazy-seq
    (if (seq (rest coll))
      (apply concat (for [element coll] (map #(cons element %) (permutations (remove #{element} coll)))))
      [coll])))

; Creates a sequence of the initial amp states, initialised with the Amp Controller Software memory and one of the given settings
(defn prepare-amps [acs settings]
  (map (partial intcode/initial-state acs) settings))

; Continues processing an amp state by removing its interrupted state and adding the given input
(defn continue [input amp-state]
  (intcode/process (-> amp-state (dissoc :interrupted) (update :inputs #(conj % input)))))

; Returns true if all of the given states are terminated
(defn all-terminated? [states]
  (not-any? (complement identity) (map :terminated states)))

; Runs a feedback loop given the Amp Controller Software and settings.
; It loops until all amp states are terminated, which means that it can be used for both parts.
(defn feedback-loop [acs settings]
  (loop [amp-states (reduce conj PersistentQueue/EMPTY (prepare-amps acs settings))
         input 0]
    (if (all-terminated? amp-states)
      input
      (let [processed (continue input (first amp-states))]
        (recur (conj (pop amp-states) processed) (last (:outputs processed)))))))

; Finds the largest output signal possible given an acs and the possible phase settings.
(defn largest-output-signal [acs possible-settings]
  (apply max (for [settings (permutations possible-settings)]
               (feedback-loop acs settings))))

(def input (intcode/parse-intcodes (slurp (first *command-line-args*))))

(println "Highest output signal:" (largest-output-signal input (range 5)))
(println "Highest output signal (with feedback loop settings):" (largest-output-signal input (range 5 10)))

And here's the ever growing intcode computer: github.com/jkoenig134/AdventOfCode...

[Ali Spittel]

Part one was a piece of cake imo. Part two was a lot tougher.

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

[Einar Norðfjörð]

I decided to go with javascript and use generators so I could easily suspend the amplifier program between inputs

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

[Jakub Charvat]

Well, today was definitely fun. Continuing in Python from previous days, part one was fairly easy as the modifications to my existing Intcode computer were minimal and the task itself was fairly straight-forward, but part two was interesting.

For part two, I chose to rewrite my whole Intcode computer in dart, as that is the language I am most familiar with, and I'm happy I did so. I then gave each amplifier a StreamController as its output and the BroadcastStream of the previous amplifier's StreamController as its input and had them listen to each other in async. Probably not the easiest way to do it, but very fun and interesting to write.

Here's the code for part 2:

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

And the code for my dart Intcode Computer: gist.github.com/jakcharvat/818c477...

[Jon Bristow]

Here's my solution to part 1 minus the obscene overhaul to Day05. I spent too long futzing because my refactor wasn't as friendly as I had hoped, and there was a terrible bug in my permutation generator.

    fun permute(input: Option<List<Int>>): Sequence<List<Int>> {
        return generateSequence(input) { currOpt ->
            currOpt.flatMap { curr ->
                val optK = curr.windowed(2)
                    .mapIndexed { i, it -> i to it }
                    .findLast { (i, ak) -> ak[0] < ak[1] }
                    .toOption()
                    .map { it.first }

                optK.map { k ->
                    val l = curr.indices
                        .findLast { l -> curr[k] < curr[l] }!!
                    val newList = curr.toMutableList()
                    newList[k] = curr[l]
                    newList[l] = curr[k]
                    newList.take(k+1) + newList.drop(k+1).reversed()
                }
            }
        }.takeWhile { it !is None }
            .map { it.getOrElse { throw Error("Bad permutation.") } }
    }

    val permutations = Day07.permute((0 until 5).toList().some())

    private fun List<Int>.runPermutation(code: Array<Int>): Int {
        return fold(Option.empty<Int>()) { result, phase ->
            Day05.step(
                code,
                CurrentState(inputs = result.fold({ listOf(phase, 0) }, { listOf(phase, it) })).right()
            )
                .toIntOrNull()
                .toOption()
        }.getOrElse { -1000000 }
    }

    fun part1(): Option<Int> {
        val best = permutations.maxBy { p ->
            p.runPermutation(data.toTypedArray())
        }.toOption()

        println("best: $best")
        return best.map {
            it.runPermutation(data.toTypedArray())
        }
    }

I'm now mulling whether I want to go full Coroutines for part 2...