2026-07-25T02:34:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19911 2024-05-29T09:43:29Z ddc:004 open_access

Snake in Optimal Space and Time Bille, Philip Farach-Colton, Martín Gørtz, Inge Li van der Hoog, Ivor Data structure Snake Nokia String Algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Philip Bille and Martín Farach-Colton and Inge Li Gørtz and Ivor van der Hoog 2024 Is Part Of LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2024.3 urn:nbn:de:0030-drops-199118 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.3 eng https://creativecommons.org/licenses/by/4.0/legalcode