Monthly Archives: April 2012

Crushing Code and Shaving Chars

Who has heard of Code Golf? I hadn’t up until about 3 years ago when I first stumbled across some on Stack Overflow. I faintly recall the horror as I gazed upon some of the most cryptic code ever – somewhat akin to the feeling I had the first time I was shown a regular expression.

According to Wikipedia, “Code golf is a type of recreational computer programming competition in which participants strive to achieve the shortest possible code that implements a certain algorithm.”

Now I would never claim to be able to hold my own against some of the veteran golfers, however I do find myself growing more and more interested in how I can shave off a few bytes here and there. Such was the case today when I set out to answer a question on Stack Overflow.

The OP was asking how he might take a single-dimension array of words, sort them alphabetically, and then print them out. Each new group of words, categorized by their first letter, should be preceded by that letter. So you would first see “A”, followed by all “a” words, then “B”, followed by all “b” words, and so on. I’ve personally wanted to do this in the past myself.

After a few minutes I had posted the following:

$firstChar = ''; 
sort( $aTest );

foreach ( $aTest as $word ) {
  $firstChar = substr( $word, 0, 1 );
  if ( $firstChar != $currChar ) {
    $currChar = $firstChar;
    echo $currChar;
  }
  echo $word; 
}

This is ugly, but fairly straight-forward. You cycle through the array, printing out the first letter of the current word whenever it differs from the last iteration. Simple enough. But then one of the members pointed out via comment that instead of writing

substr( $word, 0, 1 );

I could just access the first letter as though the word itself were an array:

sort( $aTest );

foreach ( $aTest as $word ) {
  if ( $word[0] != $currChar ) {
    $currChar = $word[0];
    echo $currChar;
  }
  echo $word; 
}

Now it had been a while since I did that. So I was pleased to be reminded of this. Then that little spark of brevity begin to grow, and I wanted to see where else I could shave off some chars. My eyes were then drawn to the assignment and echo portion:

$currChar = $word[0];
echo $currChar;

That would be shortened so that the assignment and echo take place all at once:

sort( $aTest );

foreach ( $aTest as $word ) {
  if ( $word[0] != $currChar ) {
    echo ( $currChar = $word[0] );
  }
  echo $word; 
}

So now it’s down to a single if statement, and a trailing echo. I wondered if I could just load this up into a ternary, so I set my hand to do that:

sort( $aTest );

foreach ( $aTest as $word ) {
  echo ( $word[0] != $currChar ) 
    ? ( $currChar = $word[0] ) . $word 
    : $word; 
}

At this point, I was getting a little OCD about my second and third expression. They seemed unbalanced. The second one was setting the new current category letter, as well as echoing out the word. The third one was just echoing out the word. This is when my mind returned to something Brendan Eich called an “abusage” – using && in somewhat of an if-statement fashion.

$cond && ($foo = 'bar');

The second part is only evaluated when the first part is determined to be true. If the first part is false, the operation short-circuits and the second part is never touched. I realized I could use this to test the equality of the current category letter and the first char of the current word. If they were not equal, I could use the right hand side of the operator to record the new letter:

sort( $aTest );

foreach ( $aTest as $word ) {
  echo ( $word[0] != $currChar ) && ( $currChar = $word[0] ) 
    ? $currChar . $word 
    : $word; 
}

Awesome. Looking very slim. Now that I have only one statement within my foreach loop, I can strip away the curly braces. I can also reduce even more space by moving away from long variables names. Instead of “word”, I can simply use “w”. Instead of “currChar”, I can use “l” (for “letter”). I can also collapse my ternary operator onto one line:

sort( $aTest );

foreach ( $aTest as $w ) echo ( $w[0] != $l ) && ( $l = $w[0] ) ? $l . $w : $w ;

Nearly there. Last we can strip out all of the white space possible. Unfortunately with the syntax of the foreach, we cannot remove the spaces around the keyword “as” in the condition.

sort($aTest);foreach($aTest as $w)echo($w[0]!=$l)&&($l=$w[0])?$l.$w:$w;

In the end we’ve reduced about 195 characters and 11 lines down to 1 line and roughly 70 characters! Granted, that’s nothing compared to what others have acheived, however it’s awesome to see this solution iteratively collapse before my very eyes.

With some clever substring alternatives, ternary operators, and hacking the way logical operators work, we’re able to reduce a dandy solution into a horrific and cryptic trace of insanity. I don’t suggest you actually produce code like this when you ship (outside of the obvious minification), as it’s far better to write readable code than it is to write short code.

In the end, I was able to switch away from the original array declaration and use the deprecated split function to save even more bytes:

$a=split(",","apple,pear,banana,kiwi,pineapple,strawberry");
sort($a);foreach($a as $w)echo($w[0]!=$l)&&($l=$w[0])?$l.$w:$w;

So how about you? Do you engage in this type of behavior? Have any tricks of the trade to share? Place them in the comments below! Or perhaps you can shorten my code even further – I’d love to see what you come up with!

Abusages in JavaScript

Upon reading a recent blog entry by Brendan Eich (creator of the JavaScript language), I found myself falling under a bit of conviction when he described a popular use of || (OR) and && (AND) as an “abusage”.

I also agree…that the && line (!isActive && $parent.toggleClass(‘open’)) is an abusage, allowed due to JS’s C heritage by way of Java, but frowned upon by most JS hackers; and that an if statement would be much better style.

Now this word hardly requires defining for most of us, but for everybody else it is described on Wictionary as improper or incorrect use of language.

If you’re not familiar with using || and && in the aforementioned manner, here’s the reasoning behind it. It acts as something of a short-cut if-statement. In fact, as Brendan said “an if statement would be much better style.” Let’s compare the two:

!isActive && $parent.toggleClass( 'open' )

In this line, if everything to the left of the operator evaluates to true, the “argument” to the right is also evaluated. Of course this behavior is being tricked into actually executing a method if the argument to the left, treated as a condition all by itself, evaluates to true. As an if statement it would look like this:

if ( !isActive ) $parent.toggleClass( 'open' )

This makes sense to the majority of developers. It actually reads the way in which we expect it to behave.

Similar to the if statement, if our “condition” (in this case, everything to the left of &&) evaluates to false, only then will the statement on the right be evaluated, invoking the toggleClass method.

The && and || operators perform what is known as short-circuit evalutation. The second argument is only evaluated if the first wasn’t sufficient to determine the value of the expression. Contrary to &&, || will only evaluate the argument to the right if the argument on the left evaluates to false.

I really only learned about this trick of the JavaScript language in the last year or so. I have been using && and || in expressions for years, but never thought to bring them outside the parens.

Lately I have been using these within things like feature-detection:

!!foo.classList || loadScript( 'classListPolyfill.js' );

Using double-negation (!!), we can convert an undefined value into a boolean false. So if the classList member is not found, the argument on the left evaluates to false, which in turn causes the “argument” on the right to be executed. We hi-jack this behavior to load a polyfill script for the classList member. You could modify this to use && instead, and save a char, however “OR” sounds more appropriate.

Bottom line, if Brendan Eich is right (and I suspect he of all people would be), it’s far wiser to just stick within the design and intended use of the language:

if ( !foo.classList ) {
  loadScript( 'classListPolyfill.js' );
}

There goes another super-cool esoteric trick of the masters. Guess I’ll find my seat on the bench and wait to be picked for dodge-ball.

n Parts for Sum in PHP

I was bouncing around on Stack Overflow, answering questions here, voting on questions and answers there, when I came across a question on how to construct an array of arbitrary size, whose members add up to an explicit sum. This sounded fun, especially since math has always been an area I’d like to see some personal growth in.

So I set out to answer the question, jotting down some pseudo-code in notepad, and working through some functional portions on writecodeonline.com/php and coderpad.org. After about 10 minutes or so I felt as though I had a good solution for the OP (original poster), so I clicked back over to my Stack Overflow tab. To my terror, the question had been closed as a duplicate.

Now what? Did I just waste all that time and brain-power constructing a solution that I cannot even share? Meh, screw it, I’ll share it on my blog!

My first step was to build up an array of values that were each a fraction of the sum, rounded down to keep away from decimals. This would, of course, leave me with a slightly larger number in the end if the sum isn’t equally divisible by the expected number of parts. That’s okay, I’ll just push that last number onto the end of the array.

$sum = 200; 
$parts = 10; 
$valus = array();

for ( $i = 0; $i < $parts; $i++ ) {
  $num = $i < ( $parts - 1 )
    ? floor( $sum / $parts )
    : $sum - array_sum( $valus );
  array_push( $valus, $num );
}

Awesome. This results in an array of values that are almost entirely the same number, with the exception of the last index, which will be slightly larger when the sum doesn’t divide equally.

Next I need to randomize the values. I figured I would cycle back through and have some of the values share the wealth, so to speak. Each number would have a random portion of itself donated to a random sibling. At the very least, any particular number could be reduced to 1, but no lower (more on that in a bit).

foreach ( $valus as $key => &$value ) {
  if ( $value == 1 ) continue;
  $rVal = rand( 1, $value - 1 );
  $rKey = rand( 1, $parts );
  while ( $rKey == ( $key + 1 ) )
    $rKey = rand( 1, $parts );
  $value -= $rVal;
  $valus[--$rKey] += $rVal;
}

That’s it! (KEEP READING! One important change yet to be made) Tell it how much, and how many, and it builds an array of randomized values for you. One run of the code against the above settings resulted in the following output:

Array
(
  [0] => 26
  [1] => 59
  [2] => 4
  [3] => 61
  [4] => 35
  [5] => 1
  [6] => 2
  [7] => 7
  [8] => 1
  [9] => 4
)

One interesting thing I noticed after toying with the input was that if your sum is less than your number of parts, the code will at times provide a negative number in order to provide adjusted values for each key. For example:

$sum = 2;
$parts = 5;

Produced the following results after one run:

Array
(
  [0] => -1
  [1] => 0
  [2] => -1
  [3] => 3
  [4] => 1
)

Count it up, -1 + 0 + -1 + 3 + 1 indeed equals 2. Of course this wasn’t at all what I wanted. But it did cause me to consider what would happen if somebody wanted more parts than their provided sum. This lead me to return to my share the wealth portion and rewrite the first condition:

if ( $value <= 1 ) continue; // change == to <=

Now, whenever our current value is less than or equal to 1, we skip it. It is possible for the value to be zero already, because we floor the results of the division in earlier code. If the sum is less than our parts, that result will be a fraction, which we promptly round down to 0. This will now prevent the code from further reducing the value from 0 into negative numbers. In cases where our sum is much larger than our parts, we don’t want to borrow so much from one key that we leave another with 0. This is why I skip if the value is already 1 as well.

So asking again for the following:

$sum = 2;
$parts = 5;

Will output the following array (or one similar to it):

Array
(
  [0] => 0
  [1] => 0
  [2] => 1
  [3] => 0
  [4] => 1
)