@inproceedings{a8024dd4bb3c4a639e71bfa3a653d7c3,
title = "Snake in Optimal Space and Time",
abstract = "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.",
keywords = "Data structure, Nokia, Snake, String Algorithms",
author = "Philip Bille and Mart{\'i}n Farach-Colton and G{\o}rtz, {Inge Li} and {van der Hoog}, Ivor",
note = "Publisher Copyright: {\textcopyright} Philip Bille, Mart{\'i}n Farach-Colton, Inge Li G{\o}rtz, and Ivor van der Hoog.; 12th International Conference on Fun with Algorithms, FUN 2024 ; Conference date: 04-06-2024 Through 08-06-2024",
year = "2024",
month = jun,
doi = "10.4230/LIPIcs.FUN.2024.3",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Broder, {Andrei Z.} and Tami Tamir",
booktitle = "12th International Conference on Fun with Algorithms, FUN 2024",
}