## Advent of Code 2020: "Seating System" - Day 11

Your career as a hacker brings you more and more unreasonable tasks. Today you arrive at the ferry station, head to your next gate (no one mentioned if you even got an ice cream), and figure out where to seat. Even though you are the first person in the waiting area that does not stop you from knowing the seating habits for all other passengers, and calculate their seating patterns.

Task 1: There are some seats, and some floor tiles. Every seat is empty. Seating follows some rules: 1) if a seat is empty, and no adjacent seat is occupied, someone will absolutely sit there 2) if a seat is currently occupied, but four or more adjacent seats are also occupied, the person will instantly jump up, disconnect all charging devices, and find a new seat 3) no one sits on the floor 4) this will not occupy all seats - which seems to be a good thing in Corona-19 times. Repeat that pattern until the seats do not change between two repeats. Then count the number of occupied seats.

Task 2: Adjacent seats spawn across floor tiles, so it can be a couple steps in each of the 8 possible directions. Looks like people don't like to look at other people here. Oh, and now it's 5 or more seats which must be occupied, before someone jumps up and changes seat. Again repeat the pattern of people getting up and finding new seats all one by one, until everyone is satisfied with their current seats. And then hope no additional passenger arrives!

My first thought was that this is one of the tasks which should not be solved in a database. It also reminds me of Game of Life. Nevertheless, here we are, at the ferry station, killing time with predicting seating habits instead of getting another ice cream.

I looked at this a bit, and decided to solve this with a couple of stored procedures, to follow a pattern. Turns out that it solves the problem, but is ridiculous slow. Maybe don't repeat this approach. Also along the way I am storing intermediate results in tables - maybe I should have spent some time figuring out a way to store everything in one blob.

### Preparations

As usual, I store the data in a table. It also turns out that I have to say good bye to the SERIAL I was using, and have to use "identity" instead. Later on I'm cloning the table, and "LIKE" can copy identity, but not a SERIAL definition.

I also need three stored procedures:

• One to access each seat by specifying the x and y coordinate, and optional the table name
• One to return the number of rows (y direction), optional parameter is the table name
• One to return the number of characters (x direction), optional parameter is the table name

``````\set ON_ERROR_STOP 1

DROP TABLE IF EXISTS day11;

CREATE TABLE day11 (
id      INTEGER GENERATED ALWAYS AS IDENTITY,
value   TEXT
);

COPY day11 (value) FROM STDIN;
LLLLLL.LLLLLLLLLL.LLLLLL.LLLLLLLLL.LLLL..LLLL.LLLLLL.LLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
LLLLLLLLLLL.LLLLL.LLLLLL.LLLLLLLLL.L.LLL.LLLL.LLLLLL.LLLL.LLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLLLLLLLL
LLLLLL.LLLL.LLLLL.LLLLLL.LLLLLLLLL.LLLLL.LL.L.LLLLLL.LLLL.LLLLLLLLL.LLLLLL.LLLLLLLLLL.LLLLLLLLLL
...
\.``````

There are 99 rows with seats. Quite a large waiting area for a small ferry.

``````SELECT COUNT(*) FROM day11;
count
-------
99
(1 row)``````

The stored procedure to access a specific seat:

``````CREATE OR REPLACE FUNCTION day11_seat (IN x_in INT, IN y_in INT, IN table_in TEXT DEFAULT 'day11')
RETURNS TEXT
AS \$\$
DECLARE
r RECORD;
BEGIN
EXECUTE 'SELECT SUBSTRING(value FROM \$1 FOR 1) AS value
FROM ' || quote_ident(table_in) || '
WHERE id = \$2'
USING x_in, y_in
INTO r;

RETURN r.value;
END;
\$\$
LANGUAGE plpgsql IMMUTABLE;``````

The function to return the number of columns:

``````CREATE OR REPLACE FUNCTION day11_max_x (IN table_in TEXT DEFAULT 'day11')
RETURNS INT
AS \$\$
DECLARE
r RECORD;
BEGIN
EXECUTE 'SELECT CAST(LENGTH(value) AS INT) AS length
FROM ' || quote_ident(table_in) || '
WHERE id = 1'
INTO r;

RETURN r.length;
END;
\$\$
LANGUAGE plpgsql IMMUTABLE;``````

And the number of rows:

``````CREATE OR REPLACE FUNCTION day11_max_y (IN table_in TEXT DEFAULT 'day11')
RETURNS INT
AS \$\$
DECLARE
r RECORD;
BEGIN
EXECUTE 'SELECT CAST(COUNT(*) AS INT) AS count
FROM ' || quote_ident(table_in) || ''
INTO r;

RETURN r.count;
END;
\$\$
LANGUAGE plpgsql IMMUTABLE;``````

All of this is not elegant, but gives me a chance to look at it from a programmatic point of view.

First of all I need to know which seats are adjacent to any given seat I'm looking for. This is solved by another stored procedure. As input I specify x and y of the current seat I'm looking at, and optional the table name. Inside this function I need to know the min and max boundaries of the field. Min is always 1 in both x and y direction, max is calculated by day11_max_x() and day11_max_y(). Then I go from -1 to +1, and add this in both x and y direction to my current seat position. This results in 9 different fields, and each field is checked if it is the current seat (not checked), and if it is inside the boundaries. Every valid seat position is returned, whereas the function does return the adjacent seats as a table.

``````CREATE OR REPLACE FUNCTION day11_adjacent_seats_task1 (IN x_in INT, IN y_in INT, OUT x_out INT, OUT y_out INT, IN table_in TEXT DEFAULT 'day11')
RETURNS SETOF RECORD
AS \$\$
DECLARE
max_x INT;
max_y INT;
BEGIN
SELECT day11_max_x() INTO max_x;
SELECT day11_max_y() INTO max_y;

-- make sure we have a couple rows and columns
IF max_x < 2 THEN
RAISE EXCEPTION 'max_y is invalid: %', max_x;
END IF;
IF max_y < 2 THEN
RAISE EXCEPTION 'max_y is invalid: %', max_y;
END IF;

-- make sure the input stays inside the boundaries
IF x_in < 1 OR x_in > max_x THEN
RAISE EXCEPTION 'x_in is invalid: %', x_in;
END IF;
IF y_in < 1 OR y_in > max_y THEN
RAISE EXCEPTION 'y_in is invalid: %', y_in;
END IF;

-- loop over from -1 to 1, and calculate all seats
FOR loop_x IN -1..1 LOOP
FOR loop_y IN -1..1 LOOP
-- do not calculate the same seat as the input seat
CONTINUE WHEN loop_x = 0 AND loop_y = 0;
x_out := x_in + loop_x;
y_out := y_in + loop_y;
IF x_out > 0 AND x_out <= max_x AND y_out > 0 AND y_out <= max_y THEN
RETURN NEXT;
END IF;
END LOOP;
END LOOP;

END;
\$\$
LANGUAGE plpgsql IMMUTABLE;``````

Two examples what this function is returning:

``````SELECT * FROM day11_adjacent_seats_task1(1, 1);
x_out | y_out
-------+-------
1 |     2
2 |     1
2 |     2
(3 rows)``````
``````SELECT * FROM day11_adjacent_seats_task1(23, 42);
x_out | y_out
-------+-------
22 |    41
22 |    42
22 |    43
23 |    41
23 |    43
24 |    41
24 |    42
24 |    43
(8 rows)``````

The next function is looping over all seats, and applying the rules on each seat. For this the function has two parameters: the input table, and the output table. The output table is dropped (if it exists), and re-created, based on the input table. Then the function loops over y first (to go line by line), and then loops over x in each line (to go over every character). The day11_seat() returns the current seat from the input table, and then the loop over the result of day11_adjacent_seats_task1() applies the rules on each seat. At the end of each line, the result is written as a new line into the output table.

``````-- floor: .
-- empty: L
-- occupied: #

CREATE OR REPLACE FUNCTION day11_calculate_seats_task1 (IN table_in TEXT, IN table_out TEXT)
RETURNS VOID
AS \$\$
DECLARE
max_x INT;
max_y INT;
line TEXT;
current_seat TEXT;
new_seat TEXT;
occupied_seats INT;
BEGIN
SELECT day11_max_x(table_in) INTO max_x;
SELECT day11_max_y(table_in) INTO max_y;

-- make sure we have a couple rows and columns
IF max_x < 2 THEN
RAISE EXCEPTION 'max_y is invalid: %', max_x;
END IF;
IF max_y < 2 THEN
RAISE EXCEPTION 'max_y is invalid: %', max_y;
END IF;

-- drop old output table if exists
EXECUTE 'DROP TABLE IF EXISTS ' || quote_ident(table_out);
EXECUTE 'CREATE TABLE ' || quote_ident(table_out) || ' (LIKE ' || quote_ident(table_in) || ' INCLUDING ALL)';

FOR loop_y IN 1 .. max_y LOOP
line := '';
FOR loop_x IN 1 .. max_x LOOP
current_seat := day11_seat(loop_x, loop_y, table_in);
IF current_seat = '.' THEN
line := line || current_seat;
ELSE
occupied_seats := 0;
occupied_seats := occupied_seats + 1;
END IF;
END LOOP;
-- here I know how many adjacent seats are occupied

-- If a seat is empty (L) and there are no occupied seats adjacent to it, the seat becomes occupied.
-- If a seat is occupied (#) and four or more seats adjacent to it are also occupied, the seat becomes empty.
-- Otherwise, the seat's state does not change.
-- Floor (.) never changes; seats don't move, and nobody sits on the floor.
IF current_seat = 'L' AND occupied_seats = 0 THEN
new_seat := '#';
ELSIF current_seat = '#' AND occupied_seats >= 4 THEN
new_seat := 'L';
ELSE
new_seat := current_seat;
END IF;
line := line || new_seat;
END IF;
END LOOP;
EXECUTE 'INSERT INTO ' || quote_ident(table_out) || ' (value) VALUES (\$1)'
USING line;
END LOOP;

RETURN;
END;
\$\$
LANGUAGE plpgsql VOLATILE;``````

Now that I have a function which can run one re-seating, I need to do that until nothing changes. The next function runs the previous function in a loop (with some safeguard built in), creates new tables and table names, and compares the content of the two tables afterwards. If they are the same, the loop if aborted, and the number of occupied seats is counted.

``````CREATE OR REPLACE FUNCTION day11_flip_seats_task1 (IN table_in TEXT)
RETURNS INTEGER
AS \$\$
DECLARE
max_x INT;
max_y INT;
num_diffs RECORD;
table_source TEXT;
table_out TEXT;
table_num INT DEFAULT 0;
occupied_seats INT DEFAULT 0;
current_seat TEXT;
BEGIN
SELECT day11_max_x(table_in) INTO max_x;
SELECT day11_max_y(table_in) INTO max_y;

-- make sure we have a couple rows and columns
IF max_x < 2 THEN
RAISE EXCEPTION 'max_y is invalid: %', max_x;
END IF;
IF max_y < 2 THEN
RAISE EXCEPTION 'max_y is invalid: %', max_y;
END IF;

LOOP
table_num := table_num + 1;
RAISE NOTICE 'loop number: %', table_num;
table_out := table_in || '_run' || table_num;
IF table_num = 1 THEN
table_source := table_in;
ELSE
table_source := table_in || '_run' || (table_num - 1);
END IF;

-- another run
-- compare both tables
EXECUTE 'SELECT COUNT(*) AS count
FROM ' || quote_ident(table_source) || ' d1,
' || quote_ident(table_out) || ' d2
WHERE d1.id = d2.id
AND d1.value != d2.value'
INTO num_diffs;
IF num_diffs.count = 0 THEN
RAISE NOTICE 'found same pattern';
EXIT;
END IF;
IF table_num > 200 THEN
RAISE EXCEPTION 'too many loops, abort';
EXIT;
END IF;
END LOOP;

-- the last (and previous last) table have the number of seats
FOR loop_y IN 1 .. max_y LOOP
FOR loop_x IN 1 .. max_x LOOP
current_seat := day11_seat(loop_x, loop_y, table_out);
IF current_seat = '#' THEN
occupied_seats := occupied_seats + 1;
END IF;
END LOOP;
END LOOP;

RETURN occupied_seats;
END;
\$\$
LANGUAGE plpgsql VOLATILE;``````

When I run this function:

``````\timing ON

psql:11-1.sql:404: NOTICE:  loop number: 94
psql:11-1.sql:404: NOTICE:  loop number: 95
psql:11-1.sql:404: NOTICE:  found same pattern
------------------------
2424
(1 row)

Time: 248244,227 ms (04:08,244)``````

Slow, really slow. But I have time, because no other passenger arrived so far. And I did not have ice cream. And the result is correct.

Most of the functionality for this task is already in place. I need to modify day11_adjacent_seats_task1() into day11_adjacent_seats_task2(), and change the way the adjacent seats are found. No longer looking for the neighbours, but looping into the specific direction until either a seat is found, or the boundary of teh seating area is left. For this I need to lookup the actual type at the current position, which involves an additional call to day11_seat() each time. Did I say that this approach is slow?

``````CREATE OR REPLACE FUNCTION day11_adjacent_seats_task2 (IN x_in INT, IN y_in INT, OUT x_out INT, OUT y_out INT, IN table_in TEXT DEFAULT 'day11')
RETURNS SETOF RECORD
AS \$\$
DECLARE
max_x INT;
max_y INT;
num_steps INT;
BEGIN
SELECT day11_max_x() INTO max_x;
SELECT day11_max_y() INTO max_y;

-- make sure we have a couple rows and columns
IF max_x < 2 THEN
RAISE EXCEPTION 'max_y is invalid: %', max_x;
END IF;
IF max_y < 2 THEN
RAISE EXCEPTION 'max_y is invalid: %', max_y;
END IF;

-- make sure the input stays inside the boundaries
IF x_in < 1 OR x_in > max_x THEN
RAISE EXCEPTION 'x_in is invalid: %', x_in;
END IF;
IF y_in < 1 OR y_in > max_y THEN
RAISE EXCEPTION 'y_in is invalid: %', y_in;
END IF;

-- loop over from -1 to 1, and calculate all seats
FOR loop_x IN -1..1 LOOP
FOR loop_y IN -1..1 LOOP
-- do not calculate the same seat as the input seat
CONTINUE WHEN loop_x = 0 AND loop_y = 0;
-- problem is two-fold
--  * go into each direction until a non-floor field is found
--  * but abort if the step goes outside the field
num_steps := 0;
LOOP
num_steps := num_steps + 1;
x_out := x_in + (loop_x * num_steps);
y_out := y_in + (loop_y * num_steps);
-- check if still inside the boundaries
IF x_out <= 0 OR x_out > max_x OR y_out <= 0 OR y_out > max_y THEN
EXIT;
END IF;
IF x_out > 0 AND x_out <= max_x AND y_out > 0 AND y_out <= max_y THEN
-- get the seat plan
SELECT day11_seat(x_out, y_out, table_in) INTO adjacent_seat;
RETURN NEXT;
EXIT;
END IF;
END IF;
END LOOP;
END LOOP;
END LOOP;

END;
\$\$
LANGUAGE plpgsql IMMUTABLE;``````

``````-- floor: .
-- empty: L
-- occupied: #

CREATE OR REPLACE FUNCTION day11_calculate_seats_task2 (IN table_in TEXT, IN table_out TEXT)
RETURNS VOID
AS \$\$
DECLARE
max_x INT;
max_y INT;
line TEXT;
current_seat TEXT;
new_seat TEXT;
occupied_seats INT;
BEGIN
SELECT day11_max_x(table_in) INTO max_x;
SELECT day11_max_y(table_in) INTO max_y;

-- make sure we have a couple rows and columns
IF max_x < 2 THEN
RAISE EXCEPTION 'max_y is invalid: %', max_x;
END IF;
IF max_y < 2 THEN
RAISE EXCEPTION 'max_y is invalid: %', max_y;
END IF;

-- drop old output table if exists
EXECUTE 'DROP TABLE IF EXISTS ' || quote_ident(table_out);
EXECUTE 'CREATE TABLE ' || quote_ident(table_out) || ' (LIKE ' || quote_ident(table_in) || ' INCLUDING ALL)';

FOR loop_y IN 1 .. max_y LOOP
line := '';
FOR loop_x IN 1 .. max_x LOOP
current_seat := day11_seat(loop_x, loop_y, table_in);
IF current_seat = '.' THEN
line := line || current_seat;
ELSE
occupied_seats := 0;
occupied_seats := occupied_seats + 1;
END IF;
END LOOP;
-- here I know how many adjacent seats are occupied

-- If a seat is empty (L) and there are no occupied seats adjacent to it, the seat becomes occupied.
-- If a seat is occupied (#) and four or more seats adjacent to it are also occupied, the seat becomes empty.
-- new rule: it now takes five or more visible occupied seats for an occupied seat to become empty
-- Otherwise, the seat's state does not change.
-- Floor (.) never changes; seats don't move, and nobody sits on the floor.
IF current_seat = 'L' AND occupied_seats = 0 THEN
new_seat := '#';
ELSIF current_seat = '#' AND occupied_seats >= 5 THEN
new_seat := 'L';
ELSE
new_seat := current_seat;
END IF;
line := line || new_seat;
END IF;
END LOOP;
EXECUTE 'INSERT INTO ' || quote_ident(table_out) || ' (value) VALUES (\$1)'
USING line;
END LOOP;

RETURN;
END;
\$\$
LANGUAGE plpgsql VOLATILE;``````

And finally run the seat flips until the pattern is stable:

``````CREATE OR REPLACE FUNCTION day11_flip_seats_task2 (IN table_in TEXT)
RETURNS INTEGER
AS \$\$
DECLARE
max_x INT;
max_y INT;
num_diffs RECORD;
table_source TEXT;
table_out TEXT;
table_num INT DEFAULT 0;
occupied_seats INT DEFAULT 0;
current_seat TEXT;
BEGIN
SELECT day11_max_x(table_in) INTO max_x;
SELECT day11_max_y(table_in) INTO max_y;

-- make sure we have a couple rows and columns
IF max_x < 2 THEN
RAISE EXCEPTION 'max_y is invalid: %', max_x;
END IF;
IF max_y < 2 THEN
RAISE EXCEPTION 'max_y is invalid: %', max_y;
END IF;

LOOP
table_num := table_num + 1;
RAISE NOTICE 'loop number: %', table_num;
table_out := table_in || '_run' || table_num;
IF table_num = 1 THEN
table_source := table_in;
ELSE
table_source := table_in || '_run' || (table_num - 1);
END IF;

-- another run
-- compare both tables
EXECUTE 'SELECT COUNT(*) AS count
FROM ' || quote_ident(table_source) || ' d1,
' || quote_ident(table_out) || ' d2
WHERE d1.id = d2.id
AND d1.value != d2.value'
INTO num_diffs;
IF num_diffs.count = 0 THEN
RAISE NOTICE 'found same pattern';
EXIT;
END IF;
IF table_num > 200 THEN
RAISE EXCEPTION 'too many loops, abort';
EXIT;
END IF;
END LOOP;

-- the last (and previous last) table have the number of seats
FOR loop_y IN 1 .. max_y LOOP
FOR loop_x IN 1 .. max_x LOOP
current_seat := day11_seat(loop_x, loop_y, table_out);
IF current_seat = '#' THEN
occupied_seats := occupied_seats + 1;
END IF;
END LOOP;
END LOOP;

RETURN occupied_seats;
END;
\$\$
LANGUAGE plpgsql VOLATILE;``````

Running this takes even more time:

``````\timing ON

psql:11-2.sql:257: NOTICE:  loop number: 88
psql:11-2.sql:257: NOTICE:  loop number: 89
psql:11-2.sql:257: NOTICE:  found same pattern
------------------------
2208
(1 row)

Time: 450791,399 ms (07:30,791)``````

Now that everyone is seated, the gate agent calls for boarding the ferry.

### Cleanup

The above approach left behind a couple of intermediate tables. I could have made them temporary tables, but in the beginning I needed them to figure out if my calculation was wrong. Now it's time to get rid of them:

``````DO LANGUAGE plpgsql \$\$
BEGIN
FOR t IN 1 .. 200 LOOP
EXECUTE 'DROP TABLE IF EXISTS day11_run' || CAST(t AS TEXT);
END LOOP;
END
\$\$;``````