Chad Perrin: SOB

18 December 2006

I shoulda been a basketball star.

Filed under: Metalog — apotheon @ 12:15

I just threw a wadded up kleenex from here, sitting in front of my computer desk, into the trash can next to the couch. That’s a distance of about twelve feet into a receptacle whose mouth is about the size of a normal US letter-size sheet of paper. It gets better, though.

The thing is about a foot tall. The couch’s sitting surface is about half a foot taller than that. Roughly the left half of the trash can’s opening is obscured by the couch from here.

There’s a table-like piece of furniture on wheels that is pushed up close to the trash can right now, so that it obscures the right-hand side. Combined with the couch, this leaves a narrow sliver of trash can visible from here.

Between me and the couch, there’s a small end table with a small lamp on it. The vertical shaft of the lamp is just about dead-center in the middle of the otherwise visible part of the trash can. Only the fact that I have two eyes (and thus binocular vision) let me have a view of the trash can at all, really.

The top of the lamp is sort of an umbrella shape, and extends up a ways past my view of the trash can.

I fired off this shot while sitting down. No standing up and facing the trash can for better ability to make the shot accurately — I just turned my head and tossed the kleenex in a pretty little arc a dozen feet where it just dropped neatly into the middle of the trash can. Maybe I’m too impressed with myself over such a small thing, but that was really a great shot.

EDIT: Okay, maybe I shouldn’t have been a basketball star. I just tried again with a wadded up paper bag. It bounced off the edge of the top of the table-on-wheels where it overhangs the trash can. Then again, if it wasn’t for the table, it would have gone into the trash can.

15 December 2006

UCBLogo and the Fibonacci sequence

Filed under: Geek,Metalog — apotheon @ 02:54

I’ve recently commented on syntax for generating Fibonacci numbers. Slightly more recently, I compared UCBLogo and Perl on the subject of reversing the order of words in a string. I figured I might as well provide examples of UCBLogo, in some context, for generating Fibonacci numbers.

These examples will only generate the final number of a given Fibonacci sequence, and will not output the entire sequence (despite the fact that they tend to need to iterate or recurse through the whole sequence to get to that number, some more explicitly than others). I’ll start by repeating some already presented examples, then go on to the new stuff.

Perl:


sub fib {
  my ($n, $a, $b) = (shift, 0, 1);
  ($a, $b) = ($b, $a + $b) while $n-- > 0;
  $a;
}

Perl (recursion):


sub fib {
  my $n = shift;
  return $n if $n < 2;
  return fib($n - 1) + fib($n - 2);
}

Python (I’m sure scoth or ToyKeeper will tell me if I screwed it up):


import sys

def fib(): a, b, n = 0, 1, int(sys.argv[1]) while n >= 0: yield a a, b, n = b, a+b, n-1

UCBLogo, inefficient but pretty version:


to fib :n
  if :n<2 [output 1]
  output (fib :n-1)+(fib :n-2)
end

UCBLogo, succinct but otherwise intermediate version:


to fib :n
  output (cascade :n [?1+?2] 1 [?1] 0)
end

UCBLogo, verbose but efficient version:


to fib :n
  output first fiblist :n
end

to fiblist :n if :n<2 [output [1 1]] output newfib fiblist :n-1 end

to newfib :list output fput (sum first :list first butfirst :list) :list end

Just for the extra comparisons, I'll throw in a few more languages, as borrowed from others' code.

PHP (I shudder):


function generatefibonaccisequence( $length ) {
    for( $l = array(1,1), $i = 2, $x = 0; $i < $length; $i++ )
            $l[] = $l[$x++] + $l[$x];

return $l;

}

Lisp with recursion (of course):


(define fibo
  (lambda (x)
    (if (< x 2)
      x
      (+ (fibo (- x 1)) (fibo (- x 2))))))

Python (yes, more of it, this time with recursion so it's prettier):


def fib(n):
   if   n < 2: return 1
   else      : return fib(n - 1) + fib(n - 2)

Haskell (recursive, obviously):


fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

OCaml (described as "a nice closed form" by its contributor on reddit):


let fibonacci n = let phi = ((1. +. sqrt 5.) /. 2.) in
  (intoffloat (((phi ** (floatofint n)) -. 
  ((1. -. phi) ** (floatofint n))) /. sqrt 5.))

let fibs n = let rec fibsi n i = match i with | 0 -> [fibonacci n] | _ -> fibonacci (n - i) :: fibs_i n (i - 1) in fibsi n n;;

Matlab (also from reddit):


([1 1; 1 0]^n)(1,1)

PHP (from reddit, natch):


function fib( $n ){
    return ( $n?2 )
           ? $n
           : fib( $n-1 )+fib( $n-2 );}

HSQL (yes, really -- only on reddit does this stuff arise): Read it HERE, since it's too long to use with code and pre tags without most of it being invisible in your browser if I post it here at SOB. Be forewarned, though, that you may need medical attention after viewing this code, particularly if you're epileptic. (note: Apparently, this code doesn't have anything to do with Fibonacci numbers, according to a commenter here. I really wouldn't know. It just looks like gibberish to me, anyway.)

Comments? Questions? Code snippets in other languages? Improvement to some here? It should be noted that I copied a couple of these things across (or linked to them) without understanding a word of it, like the HSQL. Ugh.

14 December 2006

linguistic comparisons: string reversal

Filed under: Geek — apotheon @ 07:48

Over at PerlMonks, a discussion cropped up about reversing a string of words in a number of different languages. It all started with the OP‘s encounter with C# programmers at work who commit the sin of cargo-cult premature optimization: they think about trying to optimize code for the computer before worrying about optimizing it for writing and maintaining, and aren’t even checking the optimization to see if it gets them anything, apparently.

The “canonical” C# version of a string reversal function is:


private static string reverseWords(string str) {
    string[] words = Array.FindAll(str.Split(
                     new char[] {' ','\t'}),
                     delegate(string s) {
                        return !String.IsNullOrEmpty(s); });
    int i = words.Length - 1;
    if (i < 0)
        return String.Empty;
    StringBuilder sb = new StringBuilder(words[i]);
    while (--i >= 0)
        sb.Append(' ').Append(words[i]);
    return sb.ToString();
}

It’s a mess. It’s a disaster area. The version the OP prefers (and so do I) would be:


Array.Reverse(words);
return String.Join(" ", words);

The OP then went on to provide some examples of how to accomplish the same thing in a number of different languages. This being in Perl, of course, there were about a half dozen or so other Perl versions presented in the discussion thread (TIMTOWTDI and all that), but I still like the OP’s best:


sub reverseWords {
  join ' ', reverse split(' ', shift)
}

The OP’s Ruby example is similarly elegant:


def reverseWords(s)
  s.split.reverse.join(' ')
end

Contrary to what my immediately previous post here at SOB might suggest, I rather like what I know about Haskell so far. I just think it should stand on its own merits, and doesn’t need someone inventing excuses to denigrate other languages to make Haskell look better by comparison. Here’s a very elegant Haskell solution to the string reversal, also of the OP’s making (with credit given to the Haskell-Cafe mailing list for help):


reverseWords = unwords . reverse . words

There were additional examples presented in a number of other languages, including even Lua and JavaScript (ew), both of which were predictably less elegant than others. REBOL put in a respectable showing. There were shell language entries to the examples, which of course looked like shell scripts — usable, understandable, uglay.

Because these comparisons often end up being about Perl vs. Python, I figured I’d bow to tradition and include Python from the discussion here. One discussion participant offered this example:


def reverseWords (s):
    l = s.split(" ")
    l.reverse()
    return " ".join(filter(lambda x: x != '', l))

Another contributor offered this:


def reverseWords(words):
    return ' '.join(words.split()[::-1])

. . . which is much more succinct. Both, however, suffer from symbol-obfuscation in a manner reminiscent of common Pythonista complaints about Perl. I mean, really — just compare both of those to the Perl example above and tell me which is more readable. I tend to think that x: x != '', l and [::-1] are less than perfectly clear. Is there a better (more readable and elegant) way to do this in Python?

Larry Wall himself, meanwhile, showed up to share these three gems of Perl 6 golf:


sub reverseWords ($) {~reverse .comb}
sub reverseWords {~reverse comb @}
my&reverseWords:={~.comb.reverse}

He commented that “The first two could even be construed as readable.” I responded that if we really want to golf to the fewest strokes, we might want to consider UCBLogo. Here’s my example:

That’s it. No keystrokes needed to define the function at all. If this was the Scottish game of golf, my ball would have started in the hole rather than on the tee. That’s because in UCBLogo, all data types are lists, and UCBLogo has a reverse procedure effectively identical to Perl’s reverse() function (which means it operates on lists, among other things, rather than being a string-based function). Because the data types are already lists in UCBLogo, including the equivalent of a multi-word “string”, there’s no need to use join() and split() (or comb, in Perl 6) to turn string data into list data before operating on it.

Someone else entirely suggested that one could achieve the same effect with Perl by loading up your data as a list in the first place, rather than as a string. For instance, instead of doing this:


$var = "one two three four";
. . . you might do this:

@var = qw(one two three four);

I’m paraphrasing, of course, but that’s the upshot of how the example might be altered. He’s right, you could do that — but it’s sorta cheating. The idea was to have a string (or whatever your language uses for the same purposes as strings), thus allowing the full range of the language’s common text/string manipulation tools. By creating the data as a list, and never making it a single string at all, one doesn’t satisfy that spirit of the challenge. At least, that’s my thought on the matter. As I said in the discussion:

Absolutely. You can do list-oriented programming in Perl as well. The problem that arises is that while doing list-oriented programming you lose the ability to do certain text manipulations without breaking the list-oriented style. For instance, you run afoul of problems with regular expressions over a string if you represent the string as an array. Similarly, you must convert to a list when you read strings in from external sources. There are many things that Perl does better for text processing than UCBLogo, but I think UCBLogo wins on this one score.

Generally, Perl is probably much better at text manipulation than UCBLogo, but in this case I was stunned to find that UCBLogo was a pretty clear winner. Go fig’.

« Newer PostsOlder Posts »

All original content Copyright Chad Perrin: Distributed under the terms of the Open Works License