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

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › 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.

Originalsprog	Udefineret/Ukendt
Titel	FUN
Antal sider	15
Vol/bind	291
Publikationsdato	2024
Sider	3:1-3:15
DOI	https://doi.org/10.4230/LIPIcs.FUN.2024.3
Status	Udgivet - 2024
Udgivet eksternt	Ja
Begivenhed	International Conference on Fun with Algorithms - Island of La Maddalena, Sardinia, Italien Varighed: 4 jun. 2024 → 8 jun. 2024 Konferencens nummer: 12 https://sites.google.com/unipi.it/fun2024

Konference

Konference	International Conference on Fun with Algorithms
Nummer	12
Lokation	Island of La Maddalena
Land/Område	Italien
By	Sardinia
Periode	04/06/2024 → 08/06/2024
Internetadresse	https://sites.google.com/unipi.it/fun2024

Adgang til dokumentet

10.4230/LIPIcs.FUN.2024.3Licens: CC BY

Citationsformater

@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 -