7
\$\begingroup\$

I'm new to code golf challenges. My problem came up in Advent of Code 2020 Day 8

The input is an array of arrays. In part two of the problem one needs to run several trials to produce a result by changing an element in the input array. My current code is this (comments added to explain what's going on):

p input.each_with_index { |val, i|
  next if val[0] != :acc # not all elements need to be experimented with
  changed = input.dup # clone input to make a change
  # change the first element of the value at input position i (but keep the rest)
  changed[i] = val.dup.tap { |v| v[0] = v[0] == :nop ? :jmp : :nop }
  result = try_with(changed) # run the experiment
  break result if result[1] == :terminate # success condition
end

So, that's quite a lot of code for something relatively simple. Can I make it shorter? Can I have a simple generator that produces different versions of the same array?

My complete code for day 8 is here

Edit:

As suggested in the comments, I'll try to put the problem my snippet is solving as a code golf challenge (note that this is just my snippet):

In ruby you have input: an array of instructions. Each element of input is another array of two elements, where the first is a symbol (the instruction name) which is one three: :acc, :jmp, or :nop, and the second is an integer (the instruction argument).

You also have a function try_with which works with such an array, executes the instructions and returns [n, :terminate] if the program terminates or [n, :loop] if the program is an endless loop. n is the value of the accumulator after the execution.

The original input is a loop. If you change one of the instructions in the input array from :nop to :jmp or from :jmp to :nop, and keep the argument, it will result in a terminating program. What is the value of the accumulator after you find and execute the terminating program?

The original AOC2008D8 problem

You have a file with valid assembly. Each line is a three character instruction and a (possibly negative) integer argument separated by a single space. Example

nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6

Instructions are acc add arg to accumulator and increment ip, jmp add arg to ip, nop ignore arg and just increment ip.

Then... what I said above about the snippet-only problem

Changing the next-to-last line in the example from jmp to nop results in a termination with acc value: 8

\$\endgroup\$
4
  • 6
    \$\begingroup\$ Welcome to Code Golf! You may also want to check out tips for golfing in ruby. \$\endgroup\$ Dec 8 '20 at 6:18
  • 4
    \$\begingroup\$ Welcome to the site. Could you state the problem the code is intended to solve in English along with how IO should be handled? Putting this in English rather than in code is ideal because often golfing can slightly change the behavior in acceptable ways, e.g. use more memory or time, and it is unclear what is acceptable from a code snippet alone. Plus English is just easier to understand a lot of the time. \$\endgroup\$
    – Wheat Wizard
    Dec 8 '20 at 6:58
  • \$\begingroup\$ @WheatWizard sure. Do you mean the AOC2020D8 problem or to try to put just the problem my snippet is solving as a code golf challenge? \$\endgroup\$ Dec 8 '20 at 7:51
  • \$\begingroup\$ I added a detailed description of the problem in a "human" language :) \$\endgroup\$ Dec 8 '20 at 8:48
6
\$\begingroup\$

Ruby, 102 99 98 95 bytes

(k=input.map &:dup)[$.-=1][0]=%i[nop jmp acc][k[$.][0]<=>:jmp]until(r=try_with k||$:)[1]>:t;p r

Try it online!

I assume that input and try_with are mandatory names for the Advent of Code challenge. If not, the code can obviously be even shorter. Here, I also assume that the try_with method will accept invalid input, that is, an array whose elements are not of the form [:instruction, integer]. See below for a slightly longer version in case try_with strictly requires valid input.

See commented code below for a complete list of ideas used. Apart from generic code-golf tips such as 'use short variable names', or common Ruby tips such as 'omit parentheses in method calls', here are some specific tips for the problem posed:

  • Instead of each_with_index, use a counter variable together with an anonymous lambda and redo together with until (or while) in modifier form. For the counter, a good choice in this case is the predefined global variable $., which is initialised to 0. Processing the input array in reverse (by decrementing $. in place) is the best approach. Incrementing $. in place doesn't work (because input[0] would be skipped); incrementing $. at the end of the loop would cost bytes.
  • Only call dup at the lowest level, that is, on the elements of input, not on input itself.
  • Lexicographical comparisons work with symbols, so >:t is better than == :terminate, for example.
  • It turns out to be slightly shorter to use the spaceship operator <=> instead of a ternary conditional to choose between instructions. In the code, k[$.][0]<=>:jmp returns -1 if the current instruction is :acc, 0 if it is :jmp, and 1 if it is :nop. Use these values to index into an array of the three symbols, ordered such that the correct replacement is chosen.
(k=                # use parentheses to define variables inline
   input.map &:dup # only duplicate the lowest-level arrays, and do all at once
)[$.-=1][0]        # use $. as a counter and decrement in place                       
=%i[nop jmp acc][k[$.][0]<=>:jmp] # use the spaceship operator to choose between instructions            
until              # loop with until
(r=try_with k      # omit parentheses in the call to try_with
||$:)[1]           # on the first iteration (only), k is nil so pass the predefined array $: to try_with as dummy input
>:t;               # test for >:t instead of ==:terminate
p r                # print the result

Ruby, 98 bytes

p->{(k=input.map &:dup)[$.-=1][0]=%i[nop jmp acc][k[$.][0]<=>:jmp];(r=try_with k)[1]>:t||redo;r}[]

Try it online!

Use this version if try_with rejects $: as valid input. Here, we iterate using an anonymous lambda and redo.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.