Archives

Implementing a brainball solver  2018 04 02
Some years ago, I got a "brainball" as a present, a game similar to a rubiks cube and supposed to be pretty hard. I was not able to solve it by hand, so I decided to write a solver in Rust.

Learned the hard way: Type safety is not everything  2018 03 27
You may have heard that in Haskell "once it compiles, it works". While this seems to apply in Haskell more than in other languages, a compiling program is not guaranteed to be bugfree, even if you might think so. In this post, I shortly want to showcase an example I experienced and what I hopefully learned from it.

An adventure in Haskell: A simple lambda interpreter  2018 03 27
I was never an expert of lambdacalculus, but I always wanted to learn (at least the basics of) it. So, I decided to write a very simplistic interpreter for the untyped lambda calculus.

A simple lambda interpreter  2018 03 27
I was never an expert of lambdacalculus, but I always wanted to learn (at least the basics of) it. So, I decided to write a very simplistic interpreter for the untyped lambda calculus.

Five ways to solve one of my favourite mathematical problems  2014 05 11
During my studies, we had to take the lecture "Discrete Probability Theory" which quickly became one of my favourite ones. The day before the exam, I found the following riddle in the internet (see here):
n persons, all of different heights are standing in a queue facing the window of ticket distributor in a cinema hall. What is the expected number of persons visible to the person at the ticket window if each permutation of n persons is equally likely?
Over time, I found some solutions to this problem, and I'd like to present them to you.

A (pure) C extension  2014 05 11
Over three years ago, I came across a little problem and was able to write a header file for C++ that allowed the programmer two write things like the following:
10 times { do_something_here(); }
This did exactly what you would expect from what it read. Additionally, the implementation had support for an implicitly generated counting variable denoted by a single underscore. The only drawback: It was only for C++.
Now, over three years later, I can claim that I have found a way to implement (at least to some extent) the original thing in pure C.
 An Amazon interview question (not completely solved)  2014 05 11
 A little... extension for C++  2014 05 11
 Moved to WordPress  2014 05 11

Expected number of runs in a random permutation  2014 03 21
My last post was about the expected number of cycles in a random permutation. Today, we'll compute the expected number of runs in a random permutation.

Expected number of cycles in a random permutation  2014 03 21
Once again a random experiment and an associated random variable: We generate a random permutation and are interested in the expected number of cycles.

Bird tree  2014 03 21
I came across a very nice method of enumerating the positive rational numbers based on a particular tree. This post explains how this tree is constructed and shows that actually all positive rational numbers are contained in this tree.

Finding all paths  2014 03 21
Consider the following problem: You are given a twodimensional array of integers and you are allowed to place a chess king on one of the arrays. The king can move in any of the eight directions at a time and you want to know how many (simple) paths this king can go that satisfy that the corresponding numbers are strictly increasing and that end in an even number.
As an example, consider the following array:
0 1 2 3
In this array, we have the paths
[0], [0 1 2], [0 2], [1 2], [2]
(strictly increasing and ending in an even number). 
A hiring problem  2014 03 21
Imagine the following scenario: You want to hire a new employee, and of course you want to take the best candidate. Therefore, you conduct a series of interviews with the candidates one after another. We now impose the following restriction: You have to tell the candidate whether he or she is good enough or not (i.e. if you want to hire him or her) directly after the interview. That is, once you told a candidate you hire her or him, the interview process is over and you do not interview any more candidates. And once you told a candidate you won't hire her or him, this candidate is away and can not be hired anymore. We now consider a strategy to solve this problem: We hire a candidate if he or she is better than the expected value of the best of all following candidates. If there are no more candidates, we have to hire the last candidate.

Vim LatexSuite missing features  2014 03 21
Since Emacs needs quite an amount of time to start, I decided to give vim a try and am quite happy with it. However, I missed a feature that I appreciated since I came to know it in AucTeX: Showing and browsing the table of contents. So, I implemented a basic table of contents myself.

An interesting bijection  2014 03 21
I came across the following identity recently: \(\sum_{i=0}^n \binom{n}{i}^2 = \binom{2n}{n}\). This can be proved in various ways. Here, I will describe a "combinatorial proof".

Addendum: Encoding tuples with numbers  2014 03 21
I described how to encode tuples of natural numbers into natural numbers. Now, I wrote (hacked) a small piece in Haskell to try it in practice.
 Intermezzo: A brainf***interpreter  2014 03 21
 A nice property of primes  2014 03 21
 A very nice proof of existence  2014 03 21
 A little thougt about how to encode tuples of natural numbers with prime numbers  2014 03 21
 Messing with skolemization  2014 03 21
 A quick and dirty unification algorithm  2014 03 21
 Height of an AVLtree  2014 03 21
 A seemingly simple problem proven hard  2014 03 21
 Expected waiting time  2014 03 21
 A winamp plugin: Making of  2014 03 21
 Eulerian numbers  2014 03 21
 How to algorithmically simulate probabilistic distributions using other distributions  2014 03 21
 Geometric distribution "extended"  2014 03 21
 Differential equation intermezzo!  2014 03 21
 Merge shuffle  2014 03 21
 Fibonacci numbers "the other way"  2014 03 21
 Emacs regular expressions...  2014 03 21