2019-12-10 J madness continued

Ah, the madness continues... This is for day 2 of Advent of Code 2019.

  1. Your input is a list of numbers describing a program. The instructions consist of opcodes and some parameters. The opcode 99 has no parameters and indicates that the end has been reached. The opcode 1 means addition and 2 means multiplication. They both take three parameters, namely addresses into the same, 0-indexed list: the addresses of the two operands and the address of the result. The answer is the number in address 0 when the program ends.

What follows is an example input and how it changes with each step. The arrow is the current execution pointer.

01234567891011
191032311099304050
1910702311099304050
3500910702311099304050

First, let’s read data from the file and convert into a list of numbers. We use the same code as before, dumping the commas by simply picking the elements in the odd positions. This is our “original” program.

w =. ;: 1!:1 <'original'
o =: ". > ((#w) $ 1 0) # w

Then we need a function that takes the program, and an instruction pointer, executes it, modifies the program, and calls itself again, until we’re done.

This is not J-style array processing, sadly!

step =: dyad define
select. y { x
case. 1 do.
  a =. ((y+1){x){x
  b =. ((y+2){x){x
  c =. ((y+3){x)
  n =. (a + b) c } x
  n step y+4
case. 2 do.
  a =. ((y+1){x){x
  b =. ((y+2){x){x
  c =. ((y+3){x)
  n =. (a * b) c } x
  n step y+4
case. 99 do.
  0 { x
end.
)

Some notes:

  1. select. case. do. end. is similar to other languages
  2. 3 { x gets the third element from list x
  3. we need to do it twice, because the first { gives us the address we need to look at, and the second { gives us the value at that address
  4. 4 5 } x gives us a copy of x where the fifth value has been replaced by the number 4, which is why we need pass this modified value along to the next call

This computes the solution for part 1 of the challenge:

o step 0

What’s trickier to do is the second part. We are asked to “fix” the program by replacing the second and first number by all the numbers between 0 and 99 inclusive and find the pair that results in some magic value...

Here’s how to “fix” the program:

fix =. 1 2 }

And this is how you use it. The list to the left has to be exactly two elements long.

6 7 fix 1 2 3 4 5
1 6 7 4 5

Next we need a function that takes the original program, fixes is based on the two arguments, and computes the result using our step function.

try =. (4 : '((x, y) fix o) step 0')"0

Notable things that gave me headaches:

  1. I need to write (x, y) which is different from (6 7) because space-separated numbers are a thing of their own, where as space-separated identifiers are an application.
  2. I need “rank 0” (the part at the very end) such that the function gets called for every single pair of numbers in the end, and not on whole arrays.

Here’s one example of how to call it:

12 try 2

And now let’s create a 100×100 matrix and call try for every single pair:

try/~i.100

To pick this apart:

  1. i.100 creates a list of 0–99
  2. ~ is an “adverb” and modifies the preceding “verb” such that it gets called with two copies of it’s argument, so two lists of 0–99 instead of one ...
  3. / is an “adverb” and modifies the preceding “verb” such that it results in a table, getting called for every a in x and every b in y ...
  4. try is our “verb” – so in effect we’re calling 0 try 0, 0 try 1, ... which is just what we wanted

But actually we only care for the one call that produced the correct result:

19690720=try/~i.100

This gives us a truth table: a table full of zeroes and a single one. All we need to do is unravel the matrix and find the index of that single true value and we’re done.

The reason that we’re done is that the solution is “What is 100 noun + verb?” Not quite surprisingly, as 100 is the length of a row, that’s exactly what we’re getting.

I.,19690720=try/~i.100
  1. , unravels the matrix
  2. I. find the index and defaults to finding the value 1

Tags:

Comments


Please make sure you contribute only your own work, or work licensed under the GNU Free Documentation License. Note: in order to facilitate peer review and fight vandalism, we will store your IP number for a number of days. See Privacy Policy for more information. See Info for text formatting rules. You can edit the comment page if you need to fix typos. You can subscribe to new comments by email without leaving a comment.

To save this page you must answer this question:

Please say HELLO.