Drawing Blanks

Premature Optimization is a Prerequisite for Success

Archive for February 2010

Random Shuffle

with one comment

Here is a really funny story


I imagine how that happened:

Dude1: “Dude, how do I randomly shuffle an array?”

Dude2: “Easy: just sort it in a random order.”

Dude1: “Awesome idea! Here I go: array.Sort(randomOrder)”.

Instead of sorting the array in a random order, the dude sorted it using a random comparer. Which resulted in a non-uniform shuffle with distribution that depends on the sorting algorithm.

While this shuffle algorithm http://en.wikipedia.org/wiki/Fisher-Yates_shuffle remains the fastest, simplest and safest, sorting by a random key is not a wrong approach. But if we choose it, we need to be very cautious. We need to make sure the random keys don’t change during sorting, otherwise it may be same as using a random comparer. Check this out:

var list = Enumerable.Range(1, 10);
Random rand = new Random();
var sorted = list.OrderBy(i => rand.NextDouble()); 

The code looks suspiciously similar to the wrong implementation. But the parameter of Enumerable.OrderBy() is not a comparer, but rather a key selector. So this code should result in a uniform shuffle (assuming Random.NextDouble() is uniform). But imagine what happens if the OrderedEnumerable enumerator calls the key selector function each time it compares two elements. Then our random key selector becomes equivalent to the random comparer and the result is not uniform. I attempted to figure out how OrderedEnumerable actually works using Reflector, but I gave up. Instead I just ran some tests to check how many times the key selector gets called, and it appeared that it’s called only once for each element. But I would still use the Knuth – Fisher – Yates, of course.

Anagram of the day “uniform shuffle” = “snuff life humor”

Written by bbzippo

02/25/2010 at 6:46 am

Posted in fun, programming

Applied group theory

with 2 comments

Imagine a simple image editor program that runs under strict resource constraints – on a mobile phone. (A friend of mine has been writing one). The user edits the picture in the preview mode, and after they are done, they click “apply”, and the program applies all the edits to the actual full-resolution image. The same approach is used in MS Photo Gallery (even though the Gallery is not resource-constrained, but rather resource-demanding).

Among other things, the app allows to perform the usual set of rotate/flip transforms. Namely, rotate by 90, 180, 270 degrees, flip horizontally and flip vertically. Obviously, if the user has performed a series of such transforms, you don’t want to apply them one-by-one. If they’ve made two 90 degree rotations, you want to apply them as one 180 degree rotation, and if they’ve done 2 horizontal flips you don’t want to do anything. So the problem is clear: how to simplify a series of rotations and flips? It’s obvious how to simplify rotations: you simply add the degrees modulo 360. Flips are even easier. But if you mix them, it becomes harder. Mirrors don’t commute with rotations. E.g. a 90 degree rotation followed by a vertical flip is not the same as a vertical flip followed by a 90 degree rotation.

Read the rest of this entry »

Written by bbzippo

02/19/2010 at 6:50 am

Posted in math, programming

LINQ to Quine

leave a comment »

Here’s a LINQ query that selects its own source code. Not that this is something cool, just for fun.

from s in new string[]{"select \"from s in new string[]{\\\"\" + 
s.Replace(@\"\\\", @\\\\\\).Replace(\"\\\"\", \"\\\\\\\"\") + \"\\\"} \" + s" }
select "from s in new string[]{\"" + s.Replace(@"\", @"\\")
.Replace("\"", "\\\"") + "\"} " + s;
(it all needs to be in one line)

I’d be curious to see a multiline LINQ query that enumerates its own lines, or a query that enumerates its own characters.

Written by bbzippo

02/17/2010 at 4:03 am

Posted in fun, programming

Alternative theme for counting equivalence classes

leave a comment »

The problem from the previous post https://bbzippo.wordpress.com/2010/02/14/crossing-lines/ has obviously nothing to do with geometry. All we needed to know about lines on the plane is that they intersect if and only if they are not parallel, and that being parallel is an equivalence relation. This is one of those cases when we need to use some very abstract, foundational properties of objects to solve the problem. I already wrote about the most fascinating example of this approach that I know: https://bbzippo.wordpress.com/2009/11/05/i-think-therefore-vector-basis-exists/ .

Anyway, I thought with regards to the problem about intersecting lines, how to reformulate it in terms of “belongs to the same class” rather than “intersects/parallel”. That would remove one layer of abstraction (or rather the layer that hides the abstraction!) and might make this problem easier for kids.

Let’s recall the anime series “Gakkou-no Kawaii Baka” (I don’t know whether an anime with this name actually exists). It is about a bunch of school girls. Two girls consider each other rivals if they both have a crush on the same boy, otherwise they consider each other friends. By the end of Season 1, each girl has exactly 5 friends. How many girls are there? The answer is 10, since the other answer 6 is unrealistic.

Wait, the whole problem is unrealistic. It assumes that a girl cannot have a crush on more than one boy at a time. Let’s reformulate: two girls are rivals if they have the same hair color. Now the answer is 6, because 2 is too small to be the number of different hair colors in an anime series.

Written by bbzippo

02/15/2010 at 8:07 am

Posted in fun, math

Crossing lines

with one comment

Here is a simple problem that requires an approach somewhat similar to what we used to solve the crocodile problem here https://bbzippo.wordpress.com/2010/01/08/applied-type-theory/

There are n straight lines on the plane. Each of them intersects with exactly 101 other lines. How many lines are there?


Read the rest of this entry »

Written by bbzippo

02/14/2010 at 1:21 am

Posted in math

Introducing Word Morph

leave a comment »

Word Morph is a fun little game that is about building word chains by changing only one letter at a time, e.g. break – bread – tread – trend. Xworder now features an interactive chain builder for Word Morph.

Besides being fun and educational, Word Morph may have a practical use in composing rap rhymes:

hope – dope – dose – rose – role – rule – rude – dude 🙂

I’m also planning to implement automatic finding of morphs from one word to another, and also a game where you can compete in morphing versus the computer.

Written by bbzippo

02/02/2010 at 4:05 am

Posted in Uncategorized