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;
That was challenging and very fun!
You can find the complete solution in my github-repository.
0 Comments