# Implement Entombed's lookup table

## Background

Entombed is an Atari 2600 game released in 1982, with the goal of navigating through a continuous mirrored maze as it scrolls upwards. In recent times, the game has been subject to research — despite the strict hardware limitations of the Atari 2600, it somehow manages to create solvable mazes every time. By disassembling the game's ROM, researchers discovered that this is done with the help of a mysterious lookup table.

When a tile X is to be generated, the game first looks at the states of 5 tiles A, B, C, D, and E which are around it:

$$\bbox[5px, border: 1px solid white]{\color{white}{\mathsf{x}}} \bbox[6px, border: 1px solid black]{\mathtt{C}}\, \bbox[6px, border: 1px solid black]{\mathtt{D}}\, \bbox[6px, border: 1px solid black]{\mathtt{E}}\\ \; \bbox[6px, border: 1px solid black]{\mathtt{A}}\, \bbox[6px, border: 1px solid black]{\mathtt{B}}\, \bbox[6px, border: 1px solid white]{{\mathtt{X}}}\, \bbox[10px, border: 1px solid white]{\color{white}{\mathsf{x}}}\,$$

These five values then index into the following 32-byte lookup table to determine what should appear at X — a wall, an empty space, or either a wall or an empty space, chosen at random:

A B C D E    X
0 0 0 0 0    1
0 0 0 0 1    1
0 0 0 1 0    1
0 0 0 1 1    R
0 0 1 0 0    0
0 0 1 0 1    0
0 0 1 1 0    R
0 0 1 1 1    R
0 1 0 0 0    1
0 1 0 0 1    1
0 1 0 1 0    1
0 1 0 1 1    1
0 1 1 0 0    R
0 1 1 0 1    0
0 1 1 1 0    0
0 1 1 1 1    0
1 0 0 0 0    1
1 0 0 0 1    1
1 0 0 1 0    1
1 0 0 1 1    R
1 0 1 0 0    0
1 0 1 0 1    0
1 0 1 1 0    0
1 0 1 1 1    0
1 1 0 0 0    R
1 1 0 0 1    0
1 1 0 1 0    1
1 1 0 1 1    R
1 1 1 0 0    R
1 1 1 0 1    0
1 1 1 1 0    0
1 1 1 1 1    0


Here R represents a value to be chosen randomly.

Given values for A, B, C, D, and E as input, your program or function should output the correct value for X (either 0 or 1, depending on which row of the table the input corresponds to). However, if the input corresponds to a row in the table with an X value of R, your program should output either 0 or 1 uniformly randomly.

## Rules

• This is , so shortest answer in bytes wins.
• Your input can be given in any reasonable format, e.g. a list of values, a string with the values in it, an integer in the range [0..31], etc.
• When receiving input that corresponds to an X value of R in the table, your output has to be non-deterministic.
• @Arnauld Yes. I've amended the input rule accordingly. – sporeball Jun 21 '20 at 21:48
• May we choose any 2 distinct values for the output? – Shaggy Jun 21 '20 at 23:54
• @Shaggy No. 0 and 1 are the only distinct values that Entombed outputs, so I'd argue that they're the values that your code should output as well, despite the fact that, since 0 and 1 are "falsy" and "truthy", they can normally be eschewed in favor of alternatives. – sporeball Jun 22 '20 at 0:45
• What is meant by "solvable" in this context? I watched a replay and it seems that at eg. 0:35 there starts a path, which either needed to be dug through right there, or taking other path means digging through some 5 secs later youtu.be/RkvkOfVHayE – Gnudiff Jun 22 '20 at 14:41
• @gnudifff It's mentioned in the original paper in the question in the context of an unsolvable maze. "This would spell certain doom for the player, were it not for the free-floating rectangle in the upper right part of the screen. This is a “make-break,” and acquiring these allows the player to make a new piece of maze wall or, more importantly, remove an existing piece of wall." I didn't read the full paper, so I guess the algorithm isn't technically always solvable without the make-break, but that can be ignored for the challenge. – Calvin Godfrey Jun 22 '20 at 17:47

# Jelly, 2119 15 bytes

ị“£ṅ@kṃżF’b3¤BX


Try it online!

-4 bytes after inspiration from @Neil's Charcoal Answer (binary!).

Try all testcases listed out in a grid (each row is one input tested multiple times).

### How?

ị“£ṅ@kṃżF’b3¤BX     # Main link
b3              # to base 3: [1,1,2,0,0,2,2,1,1,1,1,2,0,0,0,1,1,1,2,0,0,0,0,2,0,1,2,2,0,0,0,1]
# (2 => R; 1 => 1; 0 => 0)
ị           ¤             # Index the input into the base 3 list above
# (1-indexed, and 0 gives the last element)
B            # convert to binary: 2 => [0,1], 1 => [1], 0 => [0]
X           # Pick a random element from that list


## 19 byte version

(I personally like this one more because it uses special properties of ị and X)

Try it online!

ị“©½B.ọṅc’b3¤Hị1,0X     # Main link
b3              # to base 3: [2,2,1,0,0,1,1,2,2,2,2,1,0,0,0,2,2,2,1,0,0,0,0,1,0,2,1,1,0,0,0,2]
# (2 => 1; 1 => R; 0 => 0)
ị           ¤             # Index the input into the base 3 list above
# (1-indexed, and 0 gives the last element)
H            # Halve: [2,1,0] => [1,0.5,0]
ị1,0        # Index into 1,0 (again 1-indexed)
# 1 gives 1, and 0 gives 0
# 0.5 gives [0,1]; since it is a fractional index, it gives both the element corresponding to floor(0.5) and ceil(0.5)
X       # Random; 3 different functions
# 0 => 0
# 1 => random integer from 1 to 1 => 1
# [0,1] => random element of [0,1]


# JavaScript (ES6), 47 bytes

Expects an integer in $$\[0..31]\$$ as input.

Similar to @histocrat's Ruby answer, except that the $$\\text{R}\$$-mask is left-shifted by 1 position so that we can directly get $$\0\$$ or $$\2\$$.

n=>Math.random()*(975060894>>n&2)|67571463>>n&1


Try it online!

# JavaScript (ES6),  58 56  49 bytes

Expects an integer in $$\[0..31]\$$ as input.

n=>(Math.random(k=n*5%62%46%18)*2|k<11)&253553>>k


Try it online!

### How?

The input $$\n\$$ is turned into an index $$\k \in[0..17]\$$ with the following formula:

$$\big(((n\times 5)\bmod 62)\bmod 46\big)\bmod 18$$

In addition to reducing the size of the lookup table, it isolates all $$\\text{R}\$$ values at the end of the table, with an index greater than $$\10\$$.

As a string, the lookup table looks as follows:

10001110011RR0RRRR


Therefore, we can use a bitmask to determine if the answer is either $$\0\$$ or something else, and the test $$\k<11\$$ to decide between $$\1\$$ and $$\\text{R}\$$.

  n | * 5 | mod 62 | mod 46 | mod 18 | output
----+-----+--------+--------+--------+--------
0 |   0 |    0   |    0   |    0   |   1
1 |   5 |    5   |    5   |    5   |   1
2 |  10 |   10   |   10   |   10   |   1
3 |  15 |   15   |   15   |   15   |   R
4 |  20 |   20   |   20   |    2   |   0
5 |  25 |   25   |   25   |    7   |   0
6 |  30 |   30   |   30   |   12   |   R
7 |  35 |   35   |   35   |   17   |   R
8 |  40 |   40   |   40   |    4   |   1
9 |  45 |   45   |   45   |    9   |   1
10 |  50 |   50   |    4   |    4   |   1
11 |  55 |   55   |    9   |    9   |   1
12 |  60 |   60   |   14   |   14   |   R
13 |  65 |    3   |    3   |    3   |   0
14 |  70 |    8   |    8   |    8   |   0
15 |  75 |   13   |   13   |   13   |   0
16 |  80 |   18   |   18   |    0   |   1
17 |  85 |   23   |   23   |    5   |   1
18 |  90 |   28   |   28   |   10   |   1
19 |  95 |   33   |   33   |   15   |   R
20 | 100 |   38   |   38   |    2   |   0
21 | 105 |   43   |   43   |    7   |   0
22 | 110 |   48   |    2   |    2   |   0
23 | 115 |   53   |    7   |    7   |   0
24 | 120 |   58   |   12   |   12   |   R
25 | 125 |    1   |    1   |    1   |   0
26 | 130 |    6   |    6   |    6   |   1
27 | 135 |   11   |   11   |   11   |   R
28 | 140 |   16   |   16   |   16   |   R
29 | 145 |   21   |   21   |    3   |   0
30 | 150 |   26   |   26   |    8   |   0
31 | 155 |   31   |   31   |   13   |   0


# Ruby, 35 bytes

->i{[67571463,487530447].sample[i]}


Try it online!

There are 128 different pairs of numbers such that the nth bit is 0 for both when the table's value is 0, 1 for both when the table's value is 1, and different when the table's value is R. So we just choose one of the two at random and take the nth bit.

It seems very likely there's a way to compress this array since we have 128 pairs to choose from, but some quick searching didn't turn it up.

# Charcoal, 20 19 bytes

‽⍘Ｉ§”)∨‴)Ｃ]!P"”↨²Ｓ²


Try it online! Link is to verbose version of code. Takes input as a string of five bits. Explanation:

    ”...”       Compressed string
§            Indexed by
Ｓ    Input string
↨²     Converted from base 2
Ｉ             Cast to integer
⍘          ²   Converted to base 2
‽               Random element
Implicitly print


The compressed string contains 2 where either 0 or 1 is allowed. This converts to base two as 10 thus giving the randomisation operator a choice.

# J, 30 28 bytes

Takes in an integer.

>.@?@{&(36bkmh2k8esv#:~32#3)


Try it online! Apparently TIO resets J's random seed every session. If you run it locally, the results of R will change.

### How it works

>.@?@{&(36bkmh2k8esv#:~32#3)
36bkmh2k8esv         base 36 representation of the table
with 0 and 1 swapped
#:~32#3  back to base 3 (there is usually the
shorter 3#.inv, but that would drop the
{                       get the corresponding entry
?                         roll: 1 -> 0
2 -> 0 or 1
0 -> open interval (0,1)
>.                           round up the floats from 0.… to 1


# Python 3, 66 bytes

lambda n:randint(67571463>>n&1,487530447>>n&1)
from random import*


Try it online!

# Retina, 55 bytes

~.+
K111R00RR1111R000111R0000R01RR000¶$&L. R 10 @L.  Try it online! Link includes test cases. Explanation: .+ K111R00RR1111R000111R0000R01RR000¶$&L.


Replace the input by Retina code that takes the nth character of the lookup table.

~


Evaluate that code.

R
10


Change R to 10.

@L.


Output a random character.

# Excel, 63 56 55 bytes

Cell A1 (33 bytes):

=MID(BASE(940349744638137,3),A2,1


Cell B1 (Output Cell, 22 bytes):

=--IF(A1-2,A1,.5<RAND(


-8 thanks to @Calculuswhiz

Input goes into cell A2. Input is 1 indexed rather than 0 indexed, and needs to be in the range $$\[1, 32]\$$

## But How?

Well, lets first look at cell A1. This is where the row lookup is performed.

     BASE(940349744638137,3)        | Produces the number 11120022111120001112000020122000
=MID(                       ,A2,1   | Indexes that number at the position in A2 (input)


Then, we go to cell B1 (the output cell). This is where we check if we need to pick a random number.

    IF(A1-2,                | Coerce A1 to Number and subtract 2 from it.
A1,             | If A1 isn't 2, condition is nonzero->TRUE. Set to A1.
.5<RAND(     | Otherwise, pick FALSE or TRUE at random
=--                         | Coerce Boolean to Number, or do nothing to Number


## Where's the Closing Brackets?!?

Not needed. That's where. ;P

• Also, how about (RAND()>.5)+0? – Calculuswhiz Jun 23 '20 at 12:46
• Or even better: =--IF(A1-2,A1,.5<RAND( – Calculuswhiz Jun 23 '20 at 13:24

# 05AB1E, 15 bytes

•3-aáδÜ[•3вbIèΩ


Input as an integer in the range $$\[0,31]\$$.

Explanation:

•3-aáδÜ[•  # Push compressed integer 940349744638137
3в        # Convert it to base-3 as list:
#  [1,1,1,2,0,0,2,2,1,1,1,1,2,0,0,0,1,1,1,2,0,0,0,0,2,0,1,2,2,0,0,0]
b       # Take the binary string of each, converting the 2s to 10s:
#  [1,1,1,10,0,0,10,10,1,1,1,1,10,0,0,0,1,1,1,10,0,0,0,0,10,0,1,10,10,0,0,0]
Iè     # Index the input-integer into this list
Ω    # And pop and push a random digit of this integer
# (after which it is output implicitly as result)


See this 05AB1E tip of mine (sections How to compress large integers? and How to compress integer lists?) to understand why •3-aáδÜ[• is 940349744638137 and •3-aáδÜ[•3в is [1,1,1,2,0,0,2,2,1,1,1,1,2,0,0,0,1,1,1,2,0,0,0,0,2,0,1,2,2,0,0,0].

# Japt, 20 bytes

Takes input as 0-31.

gqn77sq5pnH ì3)¤ö


Try it - includes all test cases

# C (gcc), 81 $$\\cdots\$$ 66 52 bytes

Saved 2 bytes thanks to ceilingcat!!!

Saved a whopping 14 bytes thanks to Neil!!!

f(n){n=(n=0x29200950255a095l>>n*2&3)<2?n:time(0)&1;}


Try it online!

Inputs an integer in the range $$\[0,31]\$$ and returns either $$\0\$$, $$\1\$$, or one of them randomly.
Uses the bits of a long int to map each return value to 2-bits.

• Would returning time(0)%2 be sufficiently random? – Neil Jun 24 '20 at 13:17
• @Neil Don't see why not since we're seeding the random generator with time() it's consistent across seconds anyway. ¯\_(ツ)_/¯ – Noodle9 Jun 24 '20 at 17:32