32
\$\begingroup\$

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.

Task

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.
Improve this question
\$\endgroup\$
8
  • 1
    \$\begingroup\$ @Arnauld Yes. I've amended the input rule accordingly. \$\endgroup\$
    – sporeball
    Jun 21, 2020 at 21:48
  • \$\begingroup\$ May we choose any 2 distinct values for the output? \$\endgroup\$
    – Shaggy
    Jun 21, 2020 at 23:54
  • \$\begingroup\$ @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. \$\endgroup\$
    – sporeball
    Jun 22, 2020 at 0:45
  • \$\begingroup\$ 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 \$\endgroup\$
    – Gnudiff
    Jun 22, 2020 at 14:41
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Calvin Godfrey
    Jun 22, 2020 at 17:47

12 Answers 12

Reset to default
13
\$\begingroup\$

Jelly, 21 19 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
 “©½B.ọṅc’                # The integer 1719989029560350
          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!

Try all testcases.

ị“©½B.ọṅc’b3¤Hị1,0X     # Main link
 “©½B.ọṅc’                # The integer 1719989029560350
          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]
Improve this answer
\$\endgroup\$
0
12
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
9
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

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
                               leading 0's.)
     {                       get the corresponding entry
   ?                         roll: 1 -> 0
                                   2 -> 0 or 1
                                   0 -> open interval (0,1)
>.                           round up the floats from 0.… to 1
Improve this answer
\$\endgroup\$
0
4
\$\begingroup\$

Python 3, 66 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Retina, 55 bytes

~`.+
K`111R00RR1111R000111R0000R01RR000¶$&L`.
R
10
@L`.

Try it online! Link includes test cases. Explanation:

.+
K`111R00RR1111R000111R0000R01RR000¶$&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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Also, how about (RAND()>.5)+0? \$\endgroup\$
    – General Grievance
    Jun 23, 2020 at 12:46
  • \$\begingroup\$ Or even better: =--IF(A1-2,A1,.5<RAND( \$\endgroup\$
    – General Grievance
    Jun 23, 2020 at 13:24
1
\$\begingroup\$

05AB1E, 15 bytes

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

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

Try it online or verify all test cases.

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

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Japt, 20 bytes

Takes input as 0-31.

g`qn77sq5p`nH ì3)¤ö

Try it - includes all test cases

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

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

Vyxal r, 14 bytes

3»∧l%≥D⋎v»τiB℅

Try it Online!

Takes input as a number.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.