How to Make a Weighted Random Choice May 5th, 2009
Patrick Stein

Today seemed like a dull day at the keyboard. I beat my head against Objective C a lot. And, I implemented a weighted random choice which I have done a thousand times before. Dull, right?

I needed a weighted random choice in two different places, and I implemented it differently in each place. Weird, right? Even weirder, I think I did the right thing in each place.

Picking a card from a deck

In the first case, I needed to choose a flash card from a deck. I want to favor cards that have given the player trouble in the past. I zip through the list once to sum up the weights. Then, I pick a random number greater or equal to zero and less than the sum of the weights. Then, I run through the list again summing the weights until my running sum exceeds my random number. (Here in Perl, um, for clarity?):

my $total = 0.0;
foreach my $item ( @list_of_items ) {
    $total += weight( $item );
}

my $thresh = rand( $total );
my $found;

foreach my $item ( @list_of_items ) {
    $thresh -= weight( $item );
    if ( $thresh < 0.0 ) {
        $found = $item;
        last;
    }
}

This requires that the weight() of a given item remains constant for the duration of the function. The weight() can change between choices, however. If the weight() will remain constant for large portions of the program then you can cache the total and only bother with the second half of the loop.

Choosing a letter of the alphabet

In a different portion of the program, I need to make random letter tiles. I feel like there should be more E‘s than Q‘s. I also want to leave a pathway to use the same artwork for different languages. Because of all of this, I opted to have the weights to come in from a file.

My data file is JSON encoded. I could, I suppose, do something like this (given the English letter frequencies):

{
    "english" : {
        "A": 8.167,
        "B": 1.492,
        "C": 2.782,
        ...
    }
}

But, that hurts to even think about. Instead, I opted to round them off to integer proportions. Then, I could just do this:

{
    "english": "AAAAAAAABBCCC..."
}

Now, making a random choice simply involves selecting one character from the string.

Can We Refluidize CSS? April 28th, 2009
Patrick Stein

I mentioned earlier that CSS makes each object responsible for how it flows in the layout rather than making the container responsible. So, what can be done?

Take a look at this very site. All of the widgets on the left are floating over there. If you narrow your browser window (or bump up your text size), they will eventually fall into a single column. Narrow further and they will fall below this text.

That’s 80% of what I wanted out them. There are weird artifacts though caused by the different widget sizes. To accomplish this, I not only had to float each widget, but I had to float the main column as well.

What I really wanted was a container that would flow things for me instead making me flow each item (poorly). It seems I should be able to specify a container that adds objects top-to-bottom-then-left-to-right keeping the minimum needed height for any addition. So, in adding a <div> to this container it would:

  • insert it below the last inserted item if it need not lengthen itself to do so
  • otherwise, insert it to the right of the last items as high up as it will go if it need not widen itself to do so
  • otherwise, lengthen itself enough to place it below the rest of the contents

It may be as simple as preferred-width and -height attributes on the container, a flow-order: top-bottom-left-right;, and judicious use of maximum-width and -height.

Nobody’s Perfect

This wouldn’t solve every fluidity problem one might like to tackle. But, it would make many of them much simpler. No one would ever switch apartments if each piece of furniture got to say where it belongs on the moving truck.

The Fluidity-Thwarting Flaw in CSS April 28th, 2009
Patrick Stein

I am the one who decides how big to make my browser window. Web sites have a hard time coming to grips with that. There is a mythical minimum browser size.

When I am browsing, I don’t want to have to care.

When I am designing a site, I don’t want the user to have to care.

CSS is my enemy

All of the trouble using floats for columns all spring from a fundamental flaw in CSS:

How items flow with CSS is a property of the object instead of its container.

Now, maybe I am being a bit harsh in calling it a fundamental flaw. For all I know, it was a conscious choice. My guess though is that it seemed natural to people who wrote browsers in the early 90’s (<blink> tags and all).

Sapir-Whorf with Programming Languages February 12th, 2009
Patrick Stein

I’ve been coding in Objective-C for a month or so now. It is interesting (in a Sapir-Whorf sort of way), how the language changes the way that I code. Switching from Objective-C to Lisp made me notice something that I hadn’t really noticed when moving from C++/Java/Perl to Lisp.

In Lisp, I will pull something out into a separate function if it makes the current function more self-contained, more one idea. In C++, I will only pull something out into a separate function if I need the same functionality in multiple places.

Actually, it’s even worse than that in C++. For stuff that is less than six or so lines, I might maintain it in several functions. Or, if I’m using some Literate Programming tool, I will just use the same chunk in multiple places. The notable exception in C++ is when I want to use something as a loop conditional, I may bother to break it out into its
own function:

while ( incrementCounter( cntr, min, max, dimensions ) ) {
    // body of loop here
}

In C++ or Objective-C, I might do something like this:

// some portion of my function

unsigned int choice = random() % length;
void* currentChoice = options[ choice ];
    // yes, I know I can memcpy(), but that's not as obvious
for ( unsigned int ii=choice+1; ii < length; ++ii ) {
    options[ ii-1 ] = options[ ii ];
}
--length;

// some code using currentChoice

In Lisp, I would never consider keeping that code inline. I would put it in another function right away.

This, this is one of the things I meant when I said Lisp is just plain fun. It’s easy to make a new function. I can just do it. I don’t have to fret too much over the name. I don’t have to fret too much over the argument
list. I don’t have to pre-declare it in this header file with the same signature as that implementation file. I
don’t have to pretend its a method when it’s really just a function. I can return multiple values if I need to do so. I don’t have to worry much about which compilation units will need to see this to compile.

Part of the maze generation code that I wrote in Objective-C needs to track walls. I don’t need the same structure during generation that I will use once it’s generated. So, I have a Wall class declared. It feels wrong to declare it right in the header file for the Maze. It feels silly to break it out into its own header file. What I should be doing is making a separate MazeFactory and have its implementation include the declaration of this Wall class. But, that is such overkill here. I just want the darn maze.

In Lisp, I would just be done with no feelings of guilt at all.

Lisp Package Dependencies October 21st, 2008
Patrick Stein

Some time back, xach posted information about all of the interdependcies amongst the Lisp packages available on Cliki. He had toyed with a few visualization techniques.

Me, I tweaked some old code visualization stuff I had written to output where everything was after it stabilized. Then, I tweaked my ray tracer to read that input and render the output.

Read the rest of this entry ⇒

Updates In Email

Email:

RSS Feeds

l