Complete Contact Configurations

Contact is a board game designed by Ken Garland in which players draw square tiles containing colored connections from a pile, attempting to form matches. Whilst the game is enjoyable to play — allowing the odd trading of cards in unfortunate circumstances — it seldom leads to a complete configuration, meaning a valid contacting arrangement using all available cards.

With the power of stochastically driven brute-force, however, finding such complete configurations turns out to be feasible — at least when playing with the 140 cards my Contact version contains. Not surprisingly, many solutions are of rather linear nature since the game only contains two branching cards, i.e. cards where three sides boast connections.
Thus, the search is further narrowed in by demanding a maximum dimension, that is the final configuration has to lie in a card rectangle of a given area. From my testing, a maximum dimension of 500 is moderately quickly computed (~ 30 sec @ 4.00 GHz), whilst lower maximum dimensions appear to be less likely.

This slideshow requires JavaScript.

From an implementation point of view a generalized Contact card (defined as four sides, each with three nodes being blank or colored one of three colors) snuggly fits into 24 bits, allowing for card rotation, reflection and match determination being implemented thru integer bit fiddling.
The stochastic process is driven by an (ideally assumed) uniformly distributed random number generator, being recursively applied until all cards are consumed. Finally, an image is created as a portable pixmap .ppm and resized to a .png using ImageMagick.

Source code: contact.c

Non-uniform shuffling

A shuffle of a finite sequence of length n of distinguishable elements refers to an algorithmic process which — modulo pseudo-randomness — can be modeled as a random variable uniformly distributed on the permutations \mathbb{S}_n.
However, most pseudo-random entropy sources provide only a pseudo-uniformly distributed realization of \mathbb{F}_2^\mathbb{N}, leading to the necessity of finding an algorithmic transformation process if one wishes to achieve a shuffle.
In the following, I will assume that a transforming process to a family of independent and uniformly on \{1..n\} distributed random variables is already present for any n\in\mathbb{N}.

One naive and seemingly correct (it is not) approach is to traverse the given sequence, uniformly swapping the current entry with another one, i.e.

void falseShuffle(uint64_t *arr, size_t len) {
    for (size_t j = 0; j < len; j++)
        swap(arr, j, unif(len)); }

as an exemplary C implementation where \texttt{unif}(n) is independent and uniformly distributed on \{0..n-1\}.

Yet, even though sensible on first sight, the above defined random variable is only in the most trivial cases uniformly distributed and — as empirical evidence suggests, see below — horrendously non-uniformly distributed otherwise.
To prove the non-uniformity postulated above, I first present the following number-theoretic result.

Claim. In only three trivial cases does the factorial of a natural number divide its tetration; formally

\forall\,n\in\mathbb{N}_{>2}:n!\nmid n^n.

Proof. Let n\in\mathbb{N}_{>2} be a natural number larger than two. By the definition of the factorial, \prod_{p<n\ \text{prime}}p\mid n!\mid n^n is evident. Adhering to the uniqueness of prime factorizations, \prod_{p<n}p\mid n follows. Observe that n-1>1 has to be prime since \forall\,p<n\ \text{prime}:n-1\equiv -1\not\equiv 0\mod p, implying n-1\mid\prod_p=n which cannot hold for n>2. QED

Now suppose, \texttt{falseShuffle} was indeed non-trivially distributed uniformly. Without loss of generality, all involved probability spaces were finite. Then there had to exist a surjection from this algorithm’s entropic state to \mathbb{S}_n with fibers of the same finite cardinality, implying n!\mid n^n. By the above proven claim, n<3 followed, making the distribution trivial. QED

One possible reason for the surprising nature of this non-uniformity is the striking source code resemblance to a correct implementation, i.e.

void shuffle(uint64_t *arr, size_t len) {
    for (size_t j = 0; j < len; j++)
        swap(arr, j, j + unif(len - j)); }

as an exemplary C implementation which can be inductively shown to resemble the same structure as \mathbb{S}_n, in each step sprinkling in some uniform randomness and thus being itself uniformly distributed.

To see just how non-uniform \texttt{falseShuffle} is, I have calculated its discrete density for n=4:

[       |                ]
[   |   |||              ]
[   |   |||              ]
[   |   |||              ]
[   ||  ||||||| ||       ]
[||||| |||||||| |||    ||]
[|||||||||||||||||| || ||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
n = 4

If it was uniformly distributed, the discrete density would look like a rectangle; [||||| ... |||||]. Further plots for 0\leq n\leq 6 are shown in nonUniformity.txt.

Source code for the analysis and plotting: nonUniformity.hs. Empirical evidence of non-uniformity: nonUniformity.c.

krrp

A project of epic proportions has come to a close. Yesterday, the 19th of April 2019, saw the first public release of my new programming language, krrp.

As of the 24th of April 2019, krrp is kindly included in the TIO language collection, making krrp interpretation available from within the web. Great thanks go out to TIO for providing this service.

krrp is a functional, dynamic, interpreted and (theoretically) Turing-complete esolang implemented only using standard C. As such, on top of designing the actual language, any data structures, memory management and general auxiliary functionality deviating from the lacking capabilities offered by C had to be home-brewed and hand-crafted. A time-consuming task — I have been working on this language for the past year. However, it gives the language a certain purity, as its high-level functional approach rests firmly and closely on the state-changing, mutable and segmentation-faulting depths that are the C language.

Continue reading