Thue, 100 bytes
A::=~Minecraft
B::=~Minceraft
10::=A
10::=1
12::=A
12::=A
12::=A
12::=A
12::=1
13::=B
::=
1000022223
Try it online! NB: TIO's version of Thue requires a trailing newline. Here is one such interpreter that has no such restriction. You can replace 1000022223
with 103
to convince yourself that a 50-50 chance works (although note again TIO's Thue interpreter seems to seed the RNG with the time in seconds, making quick, successive runs often have the same output). For more convincing, feel free to read my justification below.
Explanation
(For this explanation, I shall substitute "Minecraft" with x
and "Minceraft" with y
for clarity.)
Outputting numbers with an arbitrary random chance isn't straightforward in Thue. We need to output y
with a 1 in 10000 chance, and x
otherwise. Thue's source of randomness is the way it chooses replacements to make: It samples the available valid substitutions and picks one at random to perform. We can bias the selection by increasing the number of substitutions we want to inflate. The naive approach would be to include 9999 replacements mapping to x
, and 1 mapping to y
, but this would be an inordinate amount of bytes.
Instead, we'll encode 1/10000 by simulating its prime factors: \$2^4\cdot5^4\$. We can pretty easily simulate a binary choice:
A::=~x
B::=~y
13::=B
10::=A
10::=1
::=
103
50% of the time, we'll replace 10
with A
, immediately terminating further substitutions with A
. The other 50% of the time, we'll replace it with 1
. When we reach 13
, we'll output B
. We can generalize this quite easily, as inserting \$N\$ 0
s gives a \$\frac{1}{2^N}\$ chance to output B
. This process can be thought of as moving the 1
forward along a strip of 0
s, with a 50% chance each time to terminate and output x
. The 3
acts as the end of the road, allowing us to output B
. The odds of it reaching the end are quite clearly \$\frac{1}{2^N}\$. Observe the following examples:
For 10->A, 10->1:
103 = 50% / 50% (1/2)
1003 = 75% / 25% (1/4)
10003 = 87.5% / 12.5% (1/8)
100003 = 93.75% / 6.25% (1/16)
In fact, we can simulate a \$\frac{1}{K^N}\$ chance by having \$K-1\$ copies of the replacement 10::=A
, and 1 copy of the replacement 10::=1
. For \$K=5\$, this gives an 80% chance at each step to terminate and output x
, rather than the 50% chance in the previous example. Observe the following:
For (12->A)x4, 12->1
123 = 80% / 20% (1/5)
1223 = 96% / 4% (1/25)
12223 = 99.2% / 0.8% (1/125)
122223 = 99.84% / 0.16% (1/625)
Concatenating both yields 1000022223
, with a combined chance of \$\frac{1}{2^4}\cdot\frac{1}{5^4}=\frac{1}{10000}\$.
We can justify this to ourselves empirically. For N=1000000 trials, we would expected to see about 1000000/10000 == 100
instances of y
. And, from one such trial:
x: 999892 (99.98%)
y: 108 (0.01%)
We can see this is quite convincingly the case.
Alternative version, 102 bytes
A::=~Minecraft
B::=~Minceraft
013::=A
013::=13
12::=A
12::=A
12::=A
12::=A
12::=01
.13::=B
::=
.122223
This one generates the 0
s on the fly, exploiting the symmetry between the prime factors. It's unfortunately 2 bytes longer, as the more complicated behavior requires extra symbols.
Metagolfer
For similar tasks, where one must output something with a 1/n chance, I've written a Ruby script that compiles a corresponding program. Of course, this works nicer for some numbers rather than others (a prime encoded by this approach requires lines equal to its value), so perhaps some ingenuity would be required for certain cases.
if ARGV.empty?
STDERR.puts "Insufficient arguments. Usage:"
STDERR.puts " #$0 n"
exit 1
end
require 'prime'
$alphabet = "02456789abcdefghijklmnopqrstuvwxyz"
n = ARGV[0].to_i
comp = ""
puts "[COMMENT]::=Inserts B with 1/n probability, A otherwise."
Prime::prime_division(n).each_with_index { |(prime, count), i|
(1..prime).each { |k|
print "1#{$alphabet[i]}::="
puts k == prime ? "1" : "A"
}
comp << $alphabet[i] * count
}
puts "13::=B"
puts "::="
puts "1#{comp}3"