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.
| Original language | English |
|---|---|
| Journal | Leibniz International Proceedings in Informatics, LIPIcs |
| Volume | 291 |
| Pages (from-to) | 3:1-3:15 |
| ISSN | 1868-8969 |
| DOIs | |
| Publication status | Published - 2024 |
| Event | 12th International Conference on Fun with Algorithms - Island of La Maddalena, Sardinia, Italy Duration: 4 Jun 2024 → 8 Jun 2024 |
Conference
| Conference | 12th International Conference on Fun with Algorithms |
|---|---|
| Country/Territory | Italy |
| City | Island of La Maddalena, Sardinia |
| Period | 04/06/2024 → 08/06/2024 |
Keywords
- Data structure
- Nokia
- Snake
- String Algorithms
Fingerprint
Dive into the research topics of 'Snake in Optimal Space and Time'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver