Snake in Optimal Space and Time

Philip Bille, Martín Farach-Colton, Inge Li Gørtz, Ivor van der Hoog

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    We revisit the classic game of Snake and ask the basic data structural question: how many bits does it take to represent the state of a snake game so that it can be updated in constant time? Our main result is a data structure that uses optimal space (within constant factors). To achieve our results, we introduce several interesting data structural techniques, including a decomposition technique for the problem, a tabulation scheme for encoding small subproblems, and a dynamic memory allocation scheme.

    Original languageEnglish (US)
    Title of host publication12th International Conference on Fun with Algorithms, FUN 2024
    EditorsAndrei Z. Broder, Tami Tamir
    PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
    ISBN (Electronic)9783959773140
    StatePublished - Jun 2024
    Event12th International Conference on Fun with Algorithms, FUN 2024 - Sardinia, Italy
    Duration: Jun 4 2024Jun 8 2024

    Publication series

    NameLeibniz International Proceedings in Informatics, LIPIcs
    ISSN (Print)1868-8969


    Conference12th International Conference on Fun with Algorithms, FUN 2024


    • Data structure
    • Nokia
    • Snake
    • String Algorithms

    ASJC Scopus subject areas

    • Software


    Dive into the research topics of 'Snake in Optimal Space and Time'. Together they form a unique fingerprint.

    Cite this