Search code examples
javasqliteandroid-room

How to get the length of the last run of heads using sqlite

I am writing a game, where game play depends upon repeatedly finding the last run of consequtive values from a sequence. Players are randomly chosen to toss a coin resulting in a series of coin tosses. For example, if Alice and Bob are randomly chosen to toss a coin, they might produce the following sequence of heads (H) and tails (T).

player toss
-------------
Bob      H
Bob      T
Alice    T
Bob      T
Bob      H
Bob      H
Alice    T
Alice    T
Bob      H
Alice    H

A run is defined here as a series of consecutive head or tail values. The length of the last run of heads for Alice is 1. In the case of Bob, the length of the last run of heads is 3.

Primary question:

A. Is there an SQLite query to find the length of the last run of heads for a particular player?

This problem is similar to SQL query for run-length, or consecutive identical value encoding but in this case only the length of the last run of heads is required.

I currently get the outcomes for a particular player, order the outcomes in descending order using a timestamp, and then count the number of consecutive heads to get the length of the last run of heads for that player. Here is the SQLite portion of the solution that is from my Room DAO that gets the outcomes for a player:

@Query("SELECT toss FROM outcome WHERE player = :player ORDER BY auto_timestamp DESC")
List<Boolean> getOutcomes(String player);

Counting the number of consecutive heads using a Java loop seems inefficient and it would be cleaner to have the integer last run length be produced by an SQLite query.

Two Secondary Questions:

Getting the last run length of heads for a player is used to solve two other problems, currently implemented in Java:

B. Find the minimum last run length of heads for a sub-collection of players. Using the data for Alice and Bob, if the subcollection of players is {Alice, Bob} then the minimum last run length is 1, Alice's run length.

C. Find the players from a given sub-collection of players that have a last heads run length less than an integer m. If m is 2 or 3 then {Alice} would be returned because her last run length is 1. If m is 4, then {Alice, Bob} would be returned.

Additionaly, do you know if there are SQLite queries that solve B and C.?

Solution

  • A. Is there an SQLite query to find the length of the last run of heads for a particular player?

    You could write a query, although it would be quite complex if catering for a large range of Android API's/versions.

    For example the following query will return the last run and is suitable for most Android versions :-

    WITH
    /* CTE for the player - so only need to replce/bind once */
    cte_player(p) AS (
        SELECT 'Bob' /*<<<<<<<<<< change as necessary */
    ),
    cte_toss(t) AS (
        SELECT 'H'   /*<<<<<<<<<< change as/if necessary */
    ),
    /* get the base outcome to start from i.e. the latest row for the player */
    cte_base_outcome AS (
        SELECT auto_timestamp, toss,player 
        FROM outcome 
        WHERE player = (SELECT p FROM cte_player) 
            AND toss = (SELECT t FROM cte_toss) 
        ORDER BY auto_timestamp DESC 
        LIMIT 1
    ), 
    /* The recursive CTE */
    cte1(auto_timestamp,toss,player) AS (
        SELECT auto_timestamp,toss, player 
        FROM cte_base_outcome
        UNION ALL SELECT
            (
                SELECT auto_timestamp 
                FROM outcome  
                WHERE outcome.player = (SELECT p FROM cte_player) 
                    AND outcome.auto_timestamp < cte1.auto_timestamp
                    AND outcome.toss = (SELECT t FROM cte_toss)
                ORDER BY auto_timestamp 
                DESC LIMIT 1
            ),
            (
                SELECT toss 
                FROM outcome  
                WHERE outcome.player = (SELECT p FROM cte_player) 
                    AND outcome.auto_timestamp < cte1.auto_timestamp 
                ORDER BY auto_timestamp 
                DESC LIMIT 1
            ),
            (
                SELECT player 
                FROM outcome  
                WHERE outcome.player = (SELECT p FROM cte_player) 
                    AND outcome.auto_timestamp < cte1.auto_timestamp 
                ORDER BY auto_timestamp DESC 
                LIMIT 1
            )
            FROM cte1 WHERE toss = (SELECT t FROM cte_toss) LIMIT 10
    )
SELECT count() AS result 
FROM cte1 
WHERE toss = (SELECT t FROM cte_toss);

    Additionally, do you know if there are SQLite queries that solve B and C.?

    When you understand the above, the you could move on to solving B and C.

    You may wish to refer to https://sqlite.org/lang_with.html

    The following code was used for testing the above :-

    DROP TABLE IF EXISTS outcome;
CREATE TABLE IF NOT EXISTS outcome (player TEXT, toss TEXT, auto_timestamp);

INSERT INTO outcome VALUES 
    ('Alice','H',10),
    ('Bob','H',9),
    ('Alice','T',8),
    ('Alice','T',7),
    ('Bob','H',6),
    ('Bob','H',5),
    ('Bob','T',4),
    ('Alice','T',3),
    ('Bob','T',2),
    ('Bob','H',1);

WITH
    /* CTE for the player - so only need to replce/bind once */
    cte_player(p) AS (
        SELECT 'Bob' /*<<<<<<<<<< change as necessary */
    ),
    cte_toss(t) AS (
        SELECT 'H'   /*<<<<<<<<<< change as/if necessary */
    ),
    /* get the base outcome to start from i.e. the latest row for the player */
    cte_base_outcome AS (
        SELECT auto_timestamp, toss,player 
        FROM outcome 
        WHERE player = (SELECT p FROM cte_player) 
            AND toss = (SELECT t FROM cte_toss) 
        ORDER BY auto_timestamp DESC 
        LIMIT 1
    ), 
    /* The recursive CTE */
    cte1(auto_timestamp,toss,player) AS (
        SELECT auto_timestamp,toss, player 
        FROM cte_base_outcome
        UNION ALL SELECT
            (
                SELECT auto_timestamp 
                FROM outcome  
                WHERE outcome.player = (SELECT p FROM cte_player) 
                    AND outcome.auto_timestamp < cte1.auto_timestamp
                    AND outcome.toss = (SELECT t FROM cte_toss)
                ORDER BY auto_timestamp 
                DESC LIMIT 1
            ),
            (
                SELECT toss 
                FROM outcome  
                WHERE outcome.player = (SELECT p FROM cte_player) 
                    AND outcome.auto_timestamp < cte1.auto_timestamp 
                ORDER BY auto_timestamp 
                DESC LIMIT 1
            ),
            (
                SELECT player 
                FROM outcome  
                WHERE outcome.player = (SELECT p FROM cte_player) 
                    AND outcome.auto_timestamp < cte1.auto_timestamp 
                ORDER BY auto_timestamp DESC 
                LIMIT 1
            )
            FROM cte1 WHERE toss = (SELECT t FROM cte_toss) LIMIT 10
    )
SELECT count() AS result 
FROM cte1 
WHERE toss = (SELECT t FROM cte_toss);
/* Cleanup the Testing Environment */
DROP TABLE IF EXISTS outcome;

    With Bob and H then the result is :-

    enter image description here

    With Alice and H the result is :-

    enter image description here

    With Bob and T the result is :-

    enter image description here

    And finally with Alice and T :-

    enter image description here

    To utilise in Room then the SQL would be placed into an @Query and you would specify a function/method return type of Int/int or Long/long (no need for a POJO/Entity class for single column return values).

    e.g. :-

    @Query("WITH " +
        "/* CTE for the player - so only need to replace/bind once */ " +
        " cte_player(p) AS ( SELECT :player)," +
        " cte_toss(t) AS (SELECT :toss)," +
        "/* get the base outcome to start from i.e. the latest row for the player */" +
        " cte_base_outcome AS (" +
        "   SELECT auto_timestamp, toss,player " +
        "   FROM outcome " +
        "   WHERE player = (SELECT p FROM cte_player) " +
        "       AND toss = (SELECT t FROM cte_toss) " +
        "   ORDER BY auto_timestamp DESC " +
        "   LIMIT 1" +
        ")," +
        "/* The recursive CTE */" +
        " cte1(auto_timestamp,toss,player) AS (" +
        "   SELECT auto_timestamp,toss, player FROM cte_base_outcome " +
        "   UNION ALL SELECT(SELECT auto_timestamp " +
        "   FROM outcome " +
        "   WHERE outcome.player = (SELECT p FROM cte_player) " +
        "       AND outcome.auto_timestamp < cte1.auto_timestamp " +
        "       AND outcome.toss = (SELECT t FROM cte_toss) " +
        "   ORDER BY auto_timestamp DESC " +
        "   LIMIT 1" +
        "   )," +
        "   (" +
        "       SELECT toss " +
        "       FROM outcome " +
        "       WHERE outcome.player = (SELECT p FROM cte_player) " +
        "       AND outcome.auto_timestamp < cte1.auto_timestamp " +
        "       ORDER BY auto_timestamp DESC " +
        "       LIMIT 1" +
        "   )," +
        "   (" +
        "       SELECT player " +
        "       FROM outcome " +
        "       WHERE outcome.player = (SELECT p FROM cte_player) " +
        "           AND outcome.auto_timestamp < cte1.auto_timestamp " +
        "       ORDER BY auto_timestamp DESC " +
        "       LIMIT 1" +
        "   ) " +
        "   FROM cte1 " +
        "   WHERE toss = (SELECT t FROM cte_toss) " +
        "   LIMIT 10" +
        ") " +
        "SELECT count() AS result " +
        "FROM cte1 " +
        "WHERE toss = (SELECT t FROM cte_toss);")
abstract fun getLastRun(player: String, toss: String): Long
    • Note LIMIT 10 should not be required but is a failsafe obviously you may wish to increase this to a suitable value or exclude it. It limits the number of recursions. However, where LIMIT 1 has been coded, this is required to only get the 1 respective row.