Skip to content

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

First let's load the data:

\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.

Task 1

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;
    adjacent_seat TEXT;
    occupied_seats INT;
    adjacent_seats RECORD;
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;
                FOR adjacent_seats IN SELECT * FROM day11_adjacent_seats_task1(loop_x, loop_y, table_in) LOOP
                    SELECT day11_seat(adjacent_seats.x_out, adjacent_seats.y_out, table_in) INTO adjacent_seat;
                    IF adjacent_seat = '#' THEN
                        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
        PERFORM day11_calculate_seats_task1(table_source, table_out);
        -- 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
SELECT day11_flip_seats_task1('day11');

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
 day11_flip_seats_task1 
------------------------
                   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.

Task 2

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;
    adjacent_seat TEXT;
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;
                    IF adjacent_seat != '.' THEN
                        RETURN NEXT;
                        EXIT;
                    END IF;
                END IF;
            END LOOP;
        END LOOP;
    END LOOP;

END;
$$
LANGUAGE plpgsql IMMUTABLE;

Then day11_calculate_seats_task2() is a copy of day11_calculate_seats_task1(), using the new day11_adjacent_seats_task2() function, and applying the 5 seats rule instead of the 4 seats rule.

-- 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;
    adjacent_seat TEXT;
    occupied_seats INT;
    adjacent_seats RECORD;
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;
                FOR adjacent_seats IN SELECT * FROM day11_adjacent_seats_task2(loop_x, loop_y, table_in) LOOP
                    SELECT day11_seat(adjacent_seats.x_out, adjacent_seats.y_out, table_in) INTO adjacent_seat;
                    IF adjacent_seat = '#' THEN
                        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
        PERFORM day11_calculate_seats_task2(table_source, table_out);
        -- 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
SELECT day11_flip_seats_task2('day11');

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
 day11_flip_seats_task2 
------------------------
                   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
$$;

 

  • Twitter
  • Bookmark Advent of Code 2020: &quot;Seating System&quot; - Day 11 at del.icio.us
  • Facebook
  • Google Bookmarks
  • FriendFeed
  • Digg Advent of Code 2020: &quot;Seating System&quot; - Day 11
  • Bloglines Advent of Code 2020: &quot;Seating System&quot; - Day 11
  • Technorati Advent of Code 2020: &quot;Seating System&quot; - Day 11
  • Fark this: Advent of Code 2020: &quot;Seating System&quot; - Day 11
  • Bookmark Advent of Code 2020: &quot;Seating System&quot; - Day 11 at YahooMyWeb
  • Bookmark Advent of Code 2020: &quot;Seating System&quot; - Day 11 at Furl.net
  • Bookmark Advent of Code 2020: &quot;Seating System&quot; - Day 11 at reddit.com
  • Bookmark Advent of Code 2020: &quot;Seating System&quot; - Day 11 at blinklist.com
  • Bookmark Advent of Code 2020: &quot;Seating System&quot; - Day 11 at Spurl.net
  • Bookmark Advent of Code 2020: &quot;Seating System&quot; - Day 11 at Simpy.com
  • Bookmark Advent of Code 2020: &quot;Seating System&quot; - Day 11 at blogmarks
  • Bookmark Advent of Code 2020: &quot;Seating System&quot; - Day 11 with wists
  • wong it!
  • Bookmark using any bookmark manager!
  • Stumble It!
  • Identi.ca

Trackbacks

No Trackbacks

Comments

Display comments as Linear | Threaded

No comments

Add Comment

Enclosing asterisks marks text as bold (*word*), underscore are made via _word_.
E-Mail addresses will not be displayed and will only be used for E-Mail notifications.
To leave a comment you must approve it via e-mail, which will be sent to your address after submission.
Form options