Random Golf of the Day

code-golfrandom

Meta: I am running this as a little series of challenges revolving around the topic of randomness - in the form of a 9-hole golf course. I'm maintaining a leaderboard across all challenges in the series, and offer a large bounty to the person competing in all of them with the lowest overall score.

Just to be clear, despite the name, I won't be posting these once a day. Expect the next one in 6 to 8 weeks.

About the Series

This will be a series of 9 challenges. See the first instalment for more information about the series.

#1: Shuffle an Array

array-manipulationpermutations

#2: Numbers from a Normal Distribution

number

#3: Integer Partitions

numbercombinatoricsinteger-partitions

#4: The Bertrand Paradox

geometry

#5: Diamond Tilings

ascii-artcombinatorics

A regular hexagon can always be tiled with diamonds like so:

We will use an ASCII art representation of these tilings. For a hexagon of side-length 2, there are 20 such tilings:

 ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ /\_\_\ /\_\_\ /\_\_\ /\_\_\ /_/\_\ /_/\_\ /\_\_\ /_/\_\ /_/\_\ /_/\_\ /\/\_\_\ /\/_/\_\ /\/_/_/\ /\/_/\_\ /\_\/\_\ /\_\/_/\ /\/_/_/\ /\_\/\_\ /\_\/_/\ /_/\/\_\ \/\/_/_/ \/\_\/_/ \/\_\_\/ \/_/\/_/ \/\_\/_/ \/\_\_\/ \/_/\_\/ \/_/\/_/ \/_/\_\/ \_\/\/_/ \/_/_/ \/_/_/ \/_/_/ \_\/_/ \/_/_/ \/_/_/ \_\/_/ \_\/_/ \_\/_/ \_\/_/ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ /_/_/\ /\_\_\ /_/\_\ /_/_/\ /_/\_\ /_/\_\ /_/_/\ /_/_/\ /_/_/\ /_/_/\ /\_\_\/\ /\/_/_/\ /_/\/_/\ /\_\_\/\ /\_\/_/\ /_/\/_/\ /_/\_\/\ /\_\_\/\ /_/\_\/\ /_/_/\/\ \/\_\_\/ \/_/_/\/ \_\/\_\/ \/_/\_\/ \/_/_/\/ \_\/_/\/ \_\/\_\/ \/_/_/\/ \_\/_/\/ \_\_\/\/ \/_/_/ \_\_\/ \_\/_/ \_\/_/ \_\_\/ \_\_\/ \_\/_/ \_\_\/ \_\_\/ \_\_\/ 

Given a side length N, you should generate such a tiling for a hexagon of side length N at random. The exact distribution doesn't matter, but each tiling must be returned with non-zero probability.

For N ≤ 3, your submission must always produce a tiling within 1 minute.

You might like to know that the total number of possible tilings for given N can be found in OEIS A008793.

You may write a full program or a function and take input via STDIN (or closest alternative), command-line argument or function argument and produce output via STDOUT (or closest alternative), function return value or function (out) parameter.

This is code golf, so the shortest submission (in bytes) wins. And of course, the shortest submission per user will also enter into the overall leaderboard of the series.

Sandbox Questions

• Should I really rule out rejection-based algorithms? I think in this case, verifying the validity of a random tiling won't necessarily be shorter than generating valid tilings in the first place, but at the same time, I'd like to see answers run to completion for small N.

Further ideas (still unordered):

• Poisson disc sampling: This is a method to randomly distribute points across the plane densely while maintaining a minimum distance between points. I think this might be nice to golf. Further reading.
• Generate a random chessboard: The submissions should randomly produce a believable chessboard. "Believable" here mostly affects pawns: they may not appear on the first row of their colour, there may be more pieces of other types if pawns are missing (due to conversion), and two pawns may only be in the same column if at least one of the opponent's pieces is missing. Submissions should be able to generate any valid board with finite probability, but it doesn't have to be uniform.
• Generate a random arithmetic expression: This basically asks to create a tree of binary and unary operators, subject to some constraint - either on the structure of the tree (n nodes, say) or on the result of the arithmetic expression (generate a random expression that evaluates to a given n).
• Generate a random hole-free polyomino (or orthogonal polygon) (of given size).
• Vague idea: Generate points on a sphere with uniform distribution.
• Vague idea: I'd like to include a challenge on random walks.
• Vague idea: I'd like to include a challenge which has to generate a random number with a constraint based on its digits, but where you're not allowed to use strings or arrays (so you have to access the digits arithmetically).
• Idea I'm not sure about: Generate a valid Unicode character as a set of UTF-8 bytes with uniform randomness.
• Idea: Implement a (specific) PRNG.
• Idea: Generate a random Brainfuck program (or other balanced string). Would probably need to require uniform distribution and deterministic runtime to be interesting.