Snake in Optimal Space and Time.

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

doi:10.4230/LIPIcs.FUN.2024.3

Snake in Optimal Space and Time.

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

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

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	Undefined/Unknown
Title of host publication	FUN
Number of pages	15
Volume	291
Publication date	2024
Pages	3:1-3:15
DOIs	https://doi.org/10.4230/LIPIcs.FUN.2024.3
Publication status	Published - 2024
Externally published	Yes
Event	International Conference on Fun with Algorithms - Island of La Maddalena, Sardinia, Italy Duration: 4 Jun 2024 → 8 Jun 2024 Conference number: 12 https://sites.google.com/unipi.it/fun2024

Conference

Conference	International Conference on Fun with Algorithms
Number	12
Location	Island of La Maddalena
Country/Territory	Italy
City	Sardinia
Period	04/06/2024 → 08/06/2024
Internet address	https://sites.google.com/unipi.it/fun2024

Keywords

Data structure
Nokia
Snake
String algorithms

Access to Document

10.4230/LIPIcs.FUN.2024.3Licence: CC BY

Cite this

@inproceedings{7a961a768f28490284c010f0e8ad574c,

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 Hoog, \{Ivor van der\}",

note = "DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.; International Conference on Fun with Algorithms ; Conference date: 04-06-2024 Through 08-06-2024",

year = "2024",

doi = "10.4230/LIPIcs.FUN.2024.3",

language = "Udefineret/Ukendt",

volume = "291",

pages = "3:1--3:15",

booktitle = "FUN",

url = "https://sites.google.com/unipi.it/fun2024",

}

TY - GEN

T1 - Snake in Optimal Space and Time.

AU - Bille, Philip

AU - Farach-Colton, Martín

AU - Gørtz, Inge Li

AU - Hoog, Ivor van der

N1 - Conference code: 12

PY - 2024

Y1 - 2024

N2 - 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.

AB - 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.

KW - Data structure

KW - Nokia

KW - Snake

KW - String algorithms

U2 - 10.4230/LIPIcs.FUN.2024.3

DO - 10.4230/LIPIcs.FUN.2024.3

M3 - Konferencebidrag i proceedings

VL - 291

SP - 3:1-3:15

BT - FUN

T2 - International Conference on Fun with Algorithms

Y2 - 4 June 2024 through 8 June 2024

ER -