Advent Of Code 2020 in SQL – Day 8: “Handheld Halting”

#adventofcode #sql

I never ran and debugged an infinite loop of program consisting of the instructions nop, jmp and acc in SQL before – but it’s possible and the Day 8 puzzle gives me the possibility to do so.

Each of the commands has a possible value, and while we ignore it for nop, acc manipulates a global variable and jmp redirects the program to a different line.

To solve this in SQL we need recursive subqueries again. With a bit of case we can easily determine the next line number to be exectued, but how to we prevent the infinite loop from running?

My solution was to add a stack-column which holds all the previously called lines. With that I can check whether a line has already been called.

I use a “:” suffix and prefix, because when I check for “42” it will find that number in “142”, too, but “:42:” will not be found.

with
  base_data as (
    select
      rownum line_number,
      column_value line
    from table(
      aoc_file_loader.file_as_stringlist(
        aoc_file_loader.local_url('day_8_input.txt')
      )
    )
  ),
  command_value as (
    select
      line_number,
      substr(line, 1, 3) command,
      to_number(substr(line, 4)) value
    from base_data
  ),
  run_program (line_number, command, next, accumulator, stack) as (
    select
      line_number,
      command,
      line_number+1,
      case when cmd.command = 'acc' then
        cmd.value
      else
        0
      end,
      ':'||line_number||':'
    from command_value cmd where line_number = 1
    union all
    select
      cmd.line_number,
      cmd.command,
      case when cmd.command = 'jmp' then
        cmd.line_number+cmd.value
      else
        cmd.line_number+1
      end,
      case when cmd.command = 'acc' then
        call.accumulator+cmd.value
      else
        call.accumulator
      end,
      call.stack||':'||cmd.line_number||':'
    from command_value cmd, run_program call
    where cmd.line_number = call.next
      and instr(call.stack, ':'||cmd.line_number||':') <= 0
  )
select
  accumulator
from run_program
order by stack desc
fetch first row only;

Part 2 gets a bit more complicated now, because we need to find the single nop or jmp command that leads to the infinite loop – and replace it.

Because we have the power of computers (and modern computers are immensely powerful calcualation machines), we brute-force the solution by running all the variants in which we replace one command.

We can achieve that by cross-joining a variant_definition table which contains all the nop or jmp commands and the replacement commands.

To find the correct one, we look for the one variant that has NumberOfLines+1 as the maximum next value, because that means the program reached its end.

with
  base_data as (
    select
      rownum line_number,
      column_value line
    from table(
      aoc_file_loader.file_as_stringlist(
        aoc_file_loader.local_url('day_8_input.txt')
      )
    )
  ),
  command_value as (
    select
      line_number,
      substr(line, 1, 3) command,
      to_number(substr(line, 4)) value
    from base_data
  ),
  variant_definition as (
    select
      rownum variant_id,
      line_number,
      command,
      case command
        when 'jmp' then
          'nop'
        when 'nop' then
          'jmp'
      end replacement_command,
      value
    from command_value
    where command in ('jmp','nop')
  ),
  program_variants as (
    select
      variant.variant_id,
      cmd.line_number,
      case when cmd.line_number = variant.line_number then
        variant.replacement_command
      else
        cmd.command
      end command,
      cmd.value
    from variant_definition variant
    cross join command_value cmd
  ),
  run_program (variant_id, line_number, command, next, accumulator, stack) as (
    select
      variant_id,
      line_number,
      command,
      line_number+1,
      case when cmd.command = 'acc' then
        cmd.value
      else
        0
      end,
      ':'||line_number||':'
    from program_variants cmd where line_number = 1
    union all
    select
      cmd.variant_id,
      cmd.line_number,
      cmd.command,
      case when cmd.command = 'jmp' then
        cmd.line_number+cmd.value
      else
        cmd.line_number+1
      end,
      case when cmd.command = 'acc' then
        call.accumulator+cmd.value
      else
        call.accumulator
      end,
      call.stack||':'||cmd.line_number||':'
    from program_variants cmd, run_program call
    where cmd.variant_id = call.variant_id
      and cmd.line_number = call.next
      and instr(call.stack, ':'||cmd.line_number||':') <= 0
  ),
  last_values as (
    select
      variant_id,
      max(next) last_value
    from run_program
    group by variant_id
  )
select
  accumulator,
  variant_definition.line_number,
  variant_definition.command,
  variant_definition.replacement_command
from run_program
  inner join variant_definition using (variant_id)
where variant_id = (
  select variant_id from last_values where last_value-1 = (
    select count(*) from base_data
  )
)
order by stack desc
fetch first row only;