26
\$\begingroup\$

The gambler's fallacy is a cognitive bias where we mistakenly expect things that have occurred often to be less likely to occur in the future and things that have not occurred in a while to be more likely to happen soon. Your task is to implement a specific version of this.

Challenge Explanation

Write a function that returns a random integer between 1 and 6, inclusive. The catch: the first time the function is run, the outcome should be uniform (within 1%), however, each subsequent call will be skewed in favor of values that have been rolled fewer times previously. The specific details are as follows:

  • The die remembers counts of numbers generated so far.
  • Each outcome is weighted with the following formula: \$count_{max} - count_{die} + 1\$
    • For instance, if the roll counts so far are \$[1, 0, 3, 2, 1, 0]\$, the weights will be \$[3, 4, 1, 2, 3, 4]\$, that is to say that you will be 4 times more likely to roll a \$2\$ than a \$3\$.
    • Note that the formula means that a roll outcome of \$[a, b, c, d, e, f]\$ is weighted the same as \$[a + n, b + n, c + n, d + n, e + n, f + n]\$

Rules and Assumptions

  • Standard I/O rules and banned loopholes apply
  • Die rolls should not be deterministic. (i.e. use a PRNG seeded from a volatile source, as is typically available as a builtin.)
  • Your random source must have a period of at least 65535 or be true randomness.
  • Distributions must be within 1% for weights up to 255
    • 16-bit RNGs are good enough to meet both the above requirements. Most built-in RNGs are sufficient.
  • You may pass in the current distribution as long as that distribution is either mutated by the call or the post-roll distribution is returned alongside the die roll. Updating the distribution/counts is a part of this challenge.
  • You may use weights instead of counts. When doing so, whenever a weight drops to 0, all weights should increase by 1 to achieve the same effect as storing counts.
    • You may use these weights as repetitions of elements in an array.

Good luck. May the bytes be ever in your favor.

\$\endgroup\$
  • \$\begingroup\$ It appears you can comply with all the rules and banned loopholes by starting with a random number n, then outputting (n++ % 6). \$\endgroup\$ – Fax May 18 at 10:17
  • 2
    \$\begingroup\$ @Fax This problem specifies explicitly and exactly what the distribution of the $k$th number should be given the first $k-1$ numbers.Your idea gives obviously the wrong distribution for the second number given the first number. \$\endgroup\$ – JiK May 18 at 12:30
  • \$\begingroup\$ @JiK I disagree, as that argument could be used against any other code that uses a PRNG as opposed to true random. My proposal is a PRNG, albeit a very simplistic one. \$\endgroup\$ – Fax May 18 at 13:23
  • \$\begingroup\$ @JiK Assuming you're talking about theoretical distribution, that is. Measured distribution is within the required 1% for a $k$ large enough to have statistical significance. \$\endgroup\$ – Fax May 18 at 13:58
  • 1
    \$\begingroup\$ @Fax Your random source doesn't have a period of at least 65535, so it's not a PRNG sufficient for this problem. Also I don't understand what you mean by "measured distribution". \$\endgroup\$ – JiK May 18 at 17:18

11 Answers 11

12
\$\begingroup\$

R, 59 bytes

function(){T[o]<<-T[o<-sample(6,1,,max(T)-T+1)]+1
o}
T=!1:6

Try it online!

Keeps the counts in T, which is then transformed to be used as the weights argument to sample (which then most likely normalizes them to sum to 1).

The [<<- operator is used to assign a value to T in one of the parent environments (in this case, the only parent environment is .GlobalEnv).

\$\endgroup\$
  • 2
    \$\begingroup\$ Nice use of global assignment. Any reason you called your variable T? (Apart from making the code harder to read!) \$\endgroup\$ – Robin Ryder May 16 at 18:42
  • \$\begingroup\$ @RobinRyder I think my original idea was to use T or F internally to the function, and then I was too lazy to change it once I realized I needed global assignment. \$\endgroup\$ – Giuseppe May 16 at 18:58
  • 3
    \$\begingroup\$ @RobinRyder: I am surprised you are not proposing a Wang-Landau solution! \$\endgroup\$ – Xi'an May 17 at 5:54
  • 1
    \$\begingroup\$ @Xi'an I did start working on one! But the byte count was way too high when using package pawl. \$\endgroup\$ – Robin Ryder May 17 at 7:55
6
\$\begingroup\$

Python 3, 112 99 bytes

from random import*
def f(C=[0]*6):c=choices(range(6),[1-a+max(C)for a in C])[0];C[c]+=1;print(c+1)

Try it online!

Explanation

# we only need the "choice" function
from random import*

      # C, the array that holds previous choices, is created once when the function is defined
      # and is persisted afterwards unless the function is called with a replacement (i.e. f(C=[0,1,2,3,4,5]) instead of f() )
      C=[0]*6
# named function
def f(.......):
                  # generate weights
                  [1-a+max(C)for a in C]
# take the first item generated using built-in method
c=choices(range(6),......................)[0]
    # increment the counter for this choice
    C[c]+=1
    # since the array is 0-indexed, increase the number by 1 for printing
    print(c+1)

Edit: Saved 13 bytes. Thanks, attinat!

\$\endgroup\$
  • 1
    \$\begingroup\$ 99 bytes \$\endgroup\$ – attinat May 17 at 7:43
  • \$\begingroup\$ @attinat You can drop 2 bytes by using tuple unpacking (c,= and dropping [0]). Also worth noting that choices is Python 3.6+ \$\endgroup\$ – Mathias Ettinger May 17 at 9:57
5
\$\begingroup\$

05AB1E, 13 bytes

Z>αāDrÅΓΩ=Q+=

Try it online!

Takes the list of counts as input. Outputs the roll and the new counts.

Explanation:

Z                 # maximum
 >                # plus 1
  α               # absolute difference (vectorizes)
                  # the stack now has the list of weights
ā                 # range(1, length(top of stack)), in this case [1..6]
 D                # duplicate
  r               # reverse the entire stack
   ÅΓ             # run-length decode, using the weights as the run lengths
     Ω            # pick a random element
                  # the stack is now: counts, [1..6], random roll
=                 # output the roll without popping
 Q                # test for equality, vectorizing
  +               # add to the counts
   =              # output the new counts
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES8), 111 bytes

_=>++C[C.map((v,i)=>s+=''.padEnd(Math.max(...C)-v+1,i),s=''),n=s[Math.random()*s.length|0]]&&++n;[,...C]=1e6+''

Try it online!

How?

This is a rather naive and most probably suboptimal implementation that performs the simulation as described.

We keep track of the counts in \$C\$. At each roll, we build a string \$s\$ consisting of each die \$i\$ repeated \$max(C)-C_i+1\$ times and pick a random entry in there with a uniform distribution.

\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog Unicode), 32 bytesSBCS

-4 bytes using replicate instead of interval index.

{1∘+@(⎕←(?∘≢⌷⊢)(1+⍵-⍨⌈/⍵)/⍳6)⊢⍵}

Try it online!

Defined as a function that takes the current distribution as an argument, prints the resulting die roll, and returns the updated distribution. First run on TIO is 100 invocations starting with [0,0,0,0,0,0], second run is heavily biased towards 1 with [0,100,100,100,100,100], and the last run is heavily biased towards 6 in the same manner.

\$\endgroup\$
3
\$\begingroup\$

Perl 6, 31 bytes

{--.{$/=.pick}||++«.{1..6};$/}

Try it online!

Accepts the current weight distribution as a BagHash, starting with one where all weights are 1. The distribution is mutated in-place.

The BagHash pick method selects a key at random using the associated weights; the weight of that key is then decremented by one. If that weight is thereby made zero, ++«.{1..6} increments the weights of all numbers 1-6.

\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 91 bytes

w=1~Table~6
F:=Module[{g},g=RandomChoice[w->Range@6];w[[g]]++;w=Array[Max@w-w[[#]]+1&,6];g]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Javascript (ES6+), 97 bytes

d=[1,2,3,4,5,6]
w=[...d]
r=x=>(i=~~(Math.random()*w.length),k=w[i],w.concat(d.filter(x=>x!=k)),k)

Explanation

d=[1,2,3,4,5,6]                   // basic die
w=[...d]                          // weighted die
r=x=>(                            // x is meaningless, just saves 1 byte vs ()
  i=~~(Math.random()*w.length),   // pick a random face of w
  k=w[i],                         // get the value of that face
  w.concat(d.filter(x=>x!=k)),    // add the faces of the basic die that aren't the value
                                  // we just picked to the weighted die
  k                               // return the value we picked
)

Note this will eventually blow up if w exceeds a length of 232-1, which is the max array length in js, but you'll probably hit a memory limit before then, considering a 32-bit int array 232-1 long is 16GiB, and some (most?) browsers won't let you use more than 4GiB.

\$\endgroup\$
2
\$\begingroup\$

Perl 6, 49 bytes

{($!=roll (1..6 X=>1+max 0,|.{*})∖$_:),$_⊎$!}

Try it online!

Takes the previous rolls as a Bag (multiset). Returns the new roll and the new distribution.

Explanation

{                                            }  # Anon block taking
                                                # distribution in $_
                     max 0,|.{*}  # Maximum count
                   1+             # plus one
           1..6 X=>  # Pair with numbers 1-6
          (                     )∖$_  # Baggy subtract previous counts
     roll                            :  # Pick random element from Bag
 ($!=                                 )  # Store in $! and return
                                       ,$_⊎$!  # Return dist with new roll
\$\endgroup\$
1
\$\begingroup\$

Pyth, 22 20 bytes

Xt
hOs.e*]kh-eSQbQQ1

Try it online!

Input is the previous frequencies as a list, outputs the next roll and the updated frequencies separated by a newline.

Xt¶hOs.e*]kh-eSQbQQ1   Implicit: Q=eval(input())
                       Newline replaced with ¶
      .e         Q     Map elements of Q, as b with index k, using:
             eSQ         Max element of Q (end of sorted Q)
            -   b        Subtract b from the above
           h             Increment
        *]k              Repeat k the above number of times
                       Result of the above is nested weighted list
                       e.g. [1,0,3,2,1,0] -> [[0, 0, 0], [1, 1, 1, 1], [2], [3, 3], [4, 4, 4], [5, 5, 5, 5]]
     s                 Flatten
    O                  Choose random element
   h                   Increment
  ¶                    Output with newline
 t                     Decrement
X                 Q1   In Q, add 1 to the element with the above index
                       Implicit print
\$\endgroup\$
1
\$\begingroup\$

Jelly, 12 bytes

’ạṀJx$X,Ṭ+¥¥

Try it online!

A monadic link which takes a single argument, the current count list, and returns a list of the number chosen and the updated count list.

Jelly, 18 bytes

0x6+ɼṀ_®‘Jx$XṬ+ɼṛƊ

Try it online!

As an alternative, here’s a niladic link which returns the number chosen and keeps track of the count list in the register.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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