Advent Of Code – Day 11: “Seating System”

And then, there was Day 11. We are supposed to look for a stabilized layout of seat occupation when all of the people follow certain rules, depending on how many seats around them are already occupied.

This is Conway’s Game of Life with a little addition: Tiles where no seat exists.

Since I wanted to try out the Oracle MODEL clause for a while, I thought it couldn’t hurt to do this challenge with the special toolkit it provides. And it even worked pretty well, using the small input of the example.

Another benefit was that I could use Kim Berg Hansens awesome book “Practical Oracle SQL” which covers exactly that Game of Life example with the MODEL clause.

Continue reading

Advent Of Code – Day 10: “Adapter Array”

Day 10 is a beast. Really.

We are supposed to order a bunch of adapters in a way that we get from 0 jolt to the jolt needed by our device (which is the max number in the input + 3) in a step-size between 1 and 3.

Part 1 feels nearly like cheating, because we can just use a little bit of window-function magic:

with
  base_data as (
    select
      to_number(column_value) num
    from table (
        aoc_file_loader.file_as_stringlist(
          aoc_file_loader.local_url('day_10_input.txt')
       )
    )
  ),
  jolt_diffs as (
    select
      num,
      num - nvl(lag(num) over (order by num),0) jolt_diff
    from base_data
  ),
  sums as (
    select
      jolt_diff,
      count(*) count,
      sum(jolt_diff) sum
    from jolt_diffs
    group by (jolt_diff)
  )
select
  (select count from sums where jolt_diff = 1)
  * (select count+1 -- +1 for the device-adapter
    from sums where jolt_diff = 3) result
from dual;

But then comes part 2, in which we need to calculate all the possible ways that we can use to get our adapter connected.

This was incredibly hard for me to solve and I’m not sure I got the best solution – but it’s very, very fast so I think I found a pretty efficient one.

For all possibilities need to end with the maximum number in the list, I decided to start with that number. But of course, iterating through all the possibilities would be terribly unefficient, so I dabbled around with multiplying and stuff – which didn’t work.

As a constant learner, I looked for algorithms other folks came up with (NOT in the context of Advent Of Code, of course) and found this explanation of an efficient algorithm to count possible ways to cover a distance.

It was not the solution to my problem, but it gave me the right idea to count the possibilities to each reachable next point in a recursive subquery.

This would look like the following for the larger example-data:

NUMMULTIPLIERDIST_1DIST_2DIST_3
prev.DIST_1 (or 1 to start with)prev.DIST_2 + (MULTIPLIER * Exists)previous.DIST_3 + (MULTIPLIER * Exists)MULTIPLIER * Exists
4910+(1*Exists(48))=10+(1*Exists(47))=11*Exists(46)=1
4811+(1*Exists(47))=21+(1*Exists(46))=21*Exists(45)=1
4722+(2*Exists(46))=41+(2*Exists(45))=32*Exists(44)=0
4643+(4*Exists(45))=70+(4*Exists(44))=04*Exists(43)=0
4570+(7*Exists(44))=00+(7*Exists(43))=07*Exists(42)=7
4400+(0*Exists(43))=07+(0*Exists(42))=70*Exists(41)=0
with
  base_data as (
    select
      to_number(column_value) num
    from table (
        aoc_file_loader.file_as_stringlist(
          aoc_file_loader.local_url('day_10_input.txt')
       )
    )
    union all select 0 from dual
  ),
  walk (num, multiplier, dist1, dist2, dist3) as (
    select
      num,
      1,
      (select count(*) from base_data where num = cur.num-1),
      (select count(*) from base_data where num = cur.num-2),
      (select count(*) from base_data where num = cur.num-3)
    from base_data cur
    where num = (select max(num) from base_data)
    union all
    select
      prev.num-1,
      prev.dist1,
      prev.dist2 + (
        prev.dist1 * (select count(*) from base_data where num = cur.num-1)),
      prev.dist3 + (
        prev.dist1 * (select count(*) from base_data where num = cur.num-2)),
      prev.dist1 * (select count(*) from base_data where num = cur.num-3)
    from walk prev
      left outer join base_data cur on prev.num-1 = cur.num
    where prev.num > 0
  )
select multiplier as result
from walk
order by num fetch first row only

Enjoy. I never did such a thing before and I’m pretty proud right now I’ve figured it out.

You can find the solution on my github-repository.

Advent Of Code – Day 9: “Encoding Error”

The Day 9 puzzle wants us to find certain anomalies in a stream of numbers: Each number must be the sum of two previous numbers in a range of 25 (between line-1 and line-25). We should find the first number that doesn’t meet this requirement.

For databases are great at adding numbers, I have no problem doing a lot of additional work (well, let the machine do a lot of additional work) and calculate the sum of each of these possibilities.

I also added a config-subquery so I can easily switch my actual data to the data provided in the example. The puzzles really get so challenging that I usually start with the example-data.

Continue reading

Advent Of Code – Day 8: “Handheld Halting”

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.

Continue reading

Advent Of Code – Day 7: “Handy Haversacks”

Day 7’s puzzle comes with a bunch of rules about bags that contain other bags – and a lot of different colors (very cool puzzle setting btw!)

As always, the first thing we want to do is to normalize the input in a way that gives us a workable result set. In this case I aim to have a row for each child-rule, groupable by the bag’s name.

If we want to split a column into several rows, one of best approaches (if we cannot easily unpivot) is to use recursive subqueries. They seemed complicated to me at first, but once I used them several times I really get to like them:

Continue reading

Advent Of Code – Day 6: “Custom Customs”

The puzzle of Day 6 requests us to group answers to a customs declaration form and analyse them.

Challenge one is the format we need to normalize into something we can work with in SQL. Each answer is a line, but several answers are grouped together and the groups are separated by an empty line.

So as a first step, we introduce a new column that indicates whether the row is a break or not and then use window functions to summarize all breaks from beginning to the current position, which will be our group-ID

Continue reading

Advent Of Code – Day 5: “Binary Boarding”

Ah, the title already reveals what the challenge will be about – and yes, I’m two days late, because it’s been weekend and weekend is family time, usually way from any computer device.

Our task is to get seat locations and IDs from the proprietary “FBFBBFFRLR” format – which is in reality a representation of binary numbers:

FBFBBFF = 7-bit number = 0101100 = 44
RLR = 3-bit number = 101 = 5

The first step is to get the binary representation of the row and column data. I used a little helper function I wrote to get the input as sys.odcivarchar2list and into the aoc_day5_input table in the same way as I did with the previous inputs (downloading from local webserver).

Continue reading

Advent Of Code – Day 4: “Passport Processing”

Day 4 comes with a new challenge – we need to validate passport data that comes in batches that are pretty unstructured. SQL is usually used to tame structured data, but it’s totally possible to use it to deal with unstructured data, too.

The main challenge here for SQL folks is to get the data into a structured form where we can filter it.

I could do the same as before, loading the data via PL/SQL, but I want to do as much as possible inside the boundaries of pure (Oracle) SQL. Therefore, I will use the SQL Loader feature to get access to external data. To be able to do that, we need an Oracle directory and the file stored reachable for the database.

Continue reading

Advent Of Code – Day 3: “Toboggan Trajectory”

Okay, this is a tougher one in SQL – but totally possible!

We have a repeating pattern of trees and need to calculate how many trees we will hit, starting from top left position, when we always go 1 down and 3 right.

To make it a little bit easier I will use PL/SQL to translate the input (again getting it from local webserver) into a Table with that layout:

LINEPOSTREE
110
121
130
Continue reading

Advent Of Code – Day 2: “Password Philosophy”

Today’s challenge is to analyze a given list of passwords towards the provided policy.

The policy of part 1 is that the given character must occur in the password inside a given threshold – sounds like we could use some regex.

The biggest challenge – again – was to get the input data into the database (I want to avoid setting up tables if I can). sys.odcivarchar2list seems like a good choice, but the input has 1000 entries and the constructor of odcivarchar2list only supports 999 items.

Luckily, we got the UNION ALL operator 🙂

Continue reading