Home

Advertisement

Customize
About this Journal
Current Month
 123456
78910111213
14151617181920
21222324252627
282930
Jun. 30th, 2009 @ 01:11 am ICFP 09, Post Mortem, Part One
Current Mood: tired
"It would be pointless to observe that the finest volume of all the many hexagons that I myself administer is titled Combed Thunder, while another is titled The Plaster Cramp, and another Axaxaxas mlö."
         — "The Library of Babel" Jorge Luis Borges.

Well, as of the point when they froze the scoreboard, my solo effort was ranked in the 24th place with 2763.6783 points. The following is the first half of my post mortem, describing the basics and the lower level parts of my code. I intend to post a second half tomorrow, describing my solutions to the specific problems.

Part One )
About this Entry
Zen-chan (smoothed)
Jun. 29th, 2009 @ 12:05 pm ICFP 09, #2
I'm calling it a night.
Position         Score           Team                   Problems Solved
21               2763.6783  	 Combed Thunder         16
I'd broke the top twenty and was in 19th place for a good long while earlier. Oh well. At least I finally had a respectable ICFP showing this year and did reasonably well for a solo effort.
About this Entry
Zen-chan (smoothed)
Jun. 28th, 2009 @ 06:50 am ICFP 09, #1
 Step: 0 Distance: 2.2343e+06 VDiff: 3588.08
 ...
 Step: 711 Distance: 0.0530664 VDiff: 3.04898e-05

This is just with made up numbers since I haven't hooked it into the VM yet, but still. I also need to optimize for fuel consumption (7688 units, in this case). By I can hit an arbitrary moving target fairly squarely now.

Debugging my VM this afternoon was frustrating when it turned out that the error was in the specification. On the other hand, I wrote a nifty little decompiler thing.
About this Entry
Zen-chan (smoothed)
Sep. 22nd, 2008 @ 02:35 pm Shell Recipes
I doubt these will be useful to anyone else reading this, but I'm going to collecting these here as notes to myself so that I don't lose them. I should really just turn them into shell scripts.


Generate an Emacs TAGS file for a project
find . | grep -E "\.(cpp|cc|cxx|hpp|h|hxx)$" | etags -
Use this recursively scan a directory and all subdirectories for C++ source code, and index it with etags.


Convert PDFLaTeX PDF to Illustrator-usable EPS
gs -dNOCACHE -dNOPAUSE -dBATCH -dSAFER -sDEVICE=epswrite -dEPSCrop -sOutputFile=out.eps in.pdf
Use this to turn a page with snippets of equations into vector paths that Adobe Illustrator can handle without choking on font embedding and substitution issues. Good for keeping fonts consistent when labeling charts and diagrams. Also good for embedding equations into diagrams.


Convert B&W scans to searchable PDF
convert pagexxx.png -filter Cubic -resize 200% -threshold 50% -compress Group4 pagexxx.tiff
tiff2pdf -z -p letter -ro -x 1200 -y 1200 -o pagexxx.pdf pagexxx.tiff
Scan pages in, clean them up in an image editor, save to individual files. Use these two commands to convert each page to PDF. Combine in Acrobat Professional, and use the built-in OCR with the "Searchable Image (Exact)" option. Gives excellent image quality and file size (avoids bad JPEG image recompression.)


Grouped bar charts, thick lines, and font embedding with gnuplot
set terminal postscript eps enhanced color solid linewidth 3 \
    "NimbusSanL-Regu,17" fontfile "/opt/local/share/texmf-dist/fonts/type1/urw/helvetic/uhvr8a.pfb"
set output 'cache_issue.eps'
set style data boxes
set boxwidth 0.2
set xlabel "Pirates"
set ylabel "Ninjas"
set grid y
set xrange [0:4]
set yrange [0:6]
set xtics ("1"  0.5, \
           "2"  1.5, \
           "3"  2.5, \
           "4"  3.5 )
plot '-' using ($1-0.7):($2) title "Red" with boxes fs pattern 0, \
     '-' using ($1-0.5):($2) title "Green" with boxes fs pattern 2, \
     '-' using ($1-0.3):($2) title "Blue" with boxes fs pattern 3
1 2.4104
2 4.4581
3 4.7087
4 4.7337
e
1 0.5815
2 1.0963
3 1.1257
4 1.1282
e
1 0.7219
2 1.3632
3 1.4184
4 1.4223
e
Basic example of how to set up grouped bar charts. First line shows how to make lines thicker so that they'll show up better when reduced to the width of a text-column. Also shows how to specify a specific postscript font file to be embedded.
About this Entry
Zen-chan (smoothed)
Aug. 25th, 2008 @ 05:04 pm Qualifying Exam
It's done! Grand totals: one full week, five questions, and seventeen typed pages written including almost four pages for the 64 entries in the references list. And countless iced chais chugged.

Frankly, I'd rather have spent the time and energy doing, well, the actual publishable research that this is supposedly testing my preparation to do. I often wish that the Ph.D. could simply be granted after you've published enough peer-reviewed first-author papers. Given that those would all have passed evaluation by many (hopefully impartial) external experts, I'd think it'd be pretty good proof that you know your field well enough at that point.
About this Entry
Zen-chan (smoothed)
Jul. 13th, 2008 @ 02:27 am ICFP 2008 #3 - The End, but with a bit of ray tracing
Current Mood: disappointed

Real life has sort of overtaken things and it's clear that I won't be able to get as far as I'd like in the ICFP contest so I've decided to bow out. Given that, I figure that I might as well save some time for those still in the running and impart some of my ray tracing knowledge. So I'm giving away two little routines that ought to be helpful to those still in the running. Read more )

About this Entry
Zen-chan (smoothed)
Jul. 12th, 2008 @ 02:27 am ICFP 2008 #2
Yay! Geometric stuff!

Yay! Book got signed!

Boo! Monitor died last night.

Alright, time to stop for the night. This problem is interesting. At first it looked a lot easier than last year's problem. Certainly the problem description seems much shorter. But on thinking about it, there's a lot of interesting potential gotchas. Once I realized this, I decided to adopt my usual C++ approach though I'd thought of using Python at first. I'm not sure how far I'll get on this by working alone -- I haven't even started in on the networking code yet or the low level point A to B navigation. But I seem to be well on my way to having a fairly cool exploration and static path planning module to eventually direct that A-to-B code. Fast spatial data structures I can do! :-)
About this Entry
Zen-chan (smoothed)
Jul. 10th, 2008 @ 04:57 pm ICFP 2008 #1 - The Live CD
Yay for fast network connections! I've now got a burnt copy of the official ICFP LiveCD in my hot little hands.

Here's hoping that it's an interesting problem and one that's soloable since it looks like I'll be working alone.

In an interesting case of timing, this guy will be visiting tomorrow. I'm going to have to see if I can get him to sign my copy of his book.
About this Entry
Zen-chan (smoothed)
Jun. 14th, 2008 @ 12:02 am The Eleventh ICFP Programming Contest

A blog entry linked from proggit reminded me that the ICFP programming contest is coming up in about a month. Last year, I tried it solo but I think it would be much more fun to compete on a team together this year. (It also helps that I don't have a fixed work schedule this summer and that that weekend is in a dead-zone for paper deadlines.)

So anyway, this is an open invitation to anyone who reads this to think about teaming up.

About this Entry
Zen-chan (smoothed)
Jun. 13th, 2008 @ 02:18 am How not to annoy me when I review your C.S. paper.
Current Mood: cheerful
Current Music: Steeleye Span "Well Done Liar"
I've been meaning to write this post for a good long while. Last week finally triggered it. It's partly a rant about the presentation in some of the papers that I had to review then and partly a how-to guide that codifies all of the little rules-of-thumb that I strive to follow when writing my own papers. They're basically cosmetic so I try not to let them affect my reviews too much. I won't reject an otherwise solid paper just because the presentation is a bit off. But it might annoy me into being a bit more critical. So without further ado, here's my list. )
About this Entry
Zen-chan (smoothed)
Jun. 2nd, 2008 @ 11:42 pm The Billionth Fibonacci Number
Current Mood: content
A few weeks ago, [info]lindseykuper wrote a post about calculating large Fibonacci numbers. Never one to resist a program challenge, I really wanted to try my hand at it and see if I could write an even faster program for calculating Fibonacci numbers. At the time, I was rather busy working on a paper but that's done now, so I gave it a shot today. Read more )
About this Entry
Zen-chan (smoothed)
Jan. 24th, 2008 @ 09:16 pm I dub thee... "triffid."
Current Mood: calm
It's taken some thought, but I've decided that "triffid" (24" iMac, 2.8GHz Core 2 Duo, 4GB ram, 500GB HD) shall be the name of the successor to "godzilla" (Dual 2.5GHz G5 Mac tower, 2GB ram, 250GB HD, 23" Apple Cinema) as my school machine.  Other contenders for the name were "dalek" and "chupacabra".

Past and present machine names in chronological order:
  • boojum: 233MHz P2 desktop, main college machine
  • grue: 100MHz P1 desktop, toy linux server
  • jabberwock: 800MHz P3 desktop, first work machine
  • wumpus: 1.8GHz P3 laptop, second work machine
  • trogdor: 2.4GHz P4-M laptop (Dell Inspiron 8500), third work machine
  • moogle: 3.06GHz P4 Northwood desktop (Dell Dimension XPS Gen 3), current home machine
  • domokun: 624MHz XScale Pocket PC (Dell Axim x30)
  • godzilla: 2.5GHz dual-G5 Mac tower, first school machine
  • sphinx: 1.8GHz Core 2 Duo, 17" iMac ([info]sonetka's current machine and choice of name)
In other news, my SIGGRAPH paper is done and off to the committee.  Much thanks to [info]tollingbell for his assistance with writing it up and to [info]sonetka for putting up with the insanity that a paper deadline involves.  Wish us luck!
About this Entry
Zen-chan (smoothed)
Dec. 27th, 2007 @ 09:20 pm Busy Computers Make Me Happy.
Current Mood: hopeful
Current Music: OCRemix: Chrono Cross Time's New Scar
I love it when I get some kind of metaprogramming tool or a brute force search program up and running. Then I can just send it off to a remote machine somewhere that has a few trillion spare cycles, fire it up in a screen session and go off to play some video games.

Right now, my school machine happens to be off crunching through a few million FFTs in a brute force search for some filter parameters. There's nothing quite like making the machine do all the hard work.
About this Entry
Zen-chan (smoothed)
Oct. 31st, 2007 @ 08:58 pm little_cat()
Current Mood: calm
Current Music: Steeleye Span - King Henry
/* And then Little Cat A
 * Took the hat off HIS head.
 * "It is good I have some one
 * To help ME," he said.
 * "This is Little Cat B.
 * And I keep him about,
 * And when I need help
 * Then I let him come out."
 * And then B said,
 * "I think we need Little Cat C."
 *     -- "The Cat in the Hat Comes Back"  Dr. Seuss
 */
void little_cat(
    const char letter )
{
    if ( letter == 'Z' )
        voom();
    else
        little_cat( letter + 1 );
}
If I ever end up as a tenured professor teaching first year CS, I'm going to put "The Cat in the Hat Comes Back" on the recommend reading list. I'd noticed a couple of weeks ago that the "Little Cats" stored under the Cat's hat were an excellent example of recursion, with Little Cat Z using Voom providing the base case. Also that it's tail recursive (as it should be when cats are involved). This morning while reading it once more to Daniel I noticed that the first half of the book illustrates iteration, too, with the cat transferring the spot from place to place.
About this Entry
Zen-chan (smoothed)
Nov. 30th, 2006 @ 01:13 am On the Naming of Variables
Current Mood: content
Current Music: Dwelling of Duels: Reign of the Mana Sword
Sometimes I hate trying to name things in my programs. I work hard to try to come up with really descriptive, clear, standardized names since I think that it makes the programs much easier to understand. My programs may be a bit more verbose than some but they also tend to read pretty well. Besides, long names are why we have M-/ in Emacs.

Sometimes the right name is immediately apparent and it just jumps out and writes itself into the code. Other times, it's rather difficult. I know the Extreme Programming folks talk about finding metaphors as descriptions for what a program is supposed to do. Admittedly naming something in a program is pretty much a matter of finding a metaphor for that entity. But it feels like sometimes, even when you know what the metaphor for something should be, it still doesn't quite feel right as a name. I think sometimes there's more overlap between writing good prose and writing good code than we programmers will admit. In both cases just finding the right word can be a challenging struggle.

This evening I'd planned to do some refactoring in my renderer and merge a pair of classes together. I'm happy with what I plan to call the new class but was stopped in my tracks trying to thing of a name by which the references to the instances should be propagated around. Oh well, I'd rather take a little more time to think it through and get it right.
About this Entry
Zen-chan (smoothed)
Nov. 15th, 2006 @ 08:29 pm Tidbits
Current Mood: contemplative
Current Music: Orchestral Game Concert V: Meridian Child (SoM2)
I suppose I really ought to actually start posting here, rather than using this account simply for lurking. So with that I'll offer a few small tidbits from the last few days.

I've been doing CS for too long...
Stopping by another grad lab today I noticed a table with a large puzzle showing map of the world. It was probably a 1500-piece puzzle at least, given the area that the border marked off relative to the size of the pieces. So what was the first thing that popped into my head? "Ooh, that looks nice"? Nope. It was "Wait a minute! The complexity of puzzles is quadratic with the number of pieces, not linear!" I was immediately horrified that the thought had even occurred.

On asserts
I was reminded again this weekend why I really ought to be using assert() in my code more. I spent some time trying to track down the cause of spurious bright pixels from one of the particularly nasty-to-code BRDFs in my renderer and found that the BRDF was fine. It was that the code for the sphere primitive which should have been returning a unit-length normal vector was returning one with length three or so. The normal was found by subtracting the sphere's center from intersection point and dividing that by the radius. This works pretty well as long as the intersection point was actually on the sphere, which you'd expect by definition. But once every now and then it snagged on some numerical instability and the computation blew up. This of course broke all sorts of downstream assumptions in my code. Normally I'm pretty at keeping track of all sorts of dependent assumptions like this but every now and then something goes wrong. Using assert() everywhere to sanity check these assumptions would have saved me a few hours. Lesson learned. I'm thinking I might go on an assert()-adding spree soon.

Copy-and-paste code checking
Copy-and-paste code is one of those programming evils that we all preach against and we all do. Yesterday I was doing some pair programming with another guy driving and he copy-and-pasted a line for one component of a vector computation and then started changing and x to y and z respectively. Except that he missed the z and made it a y too. I called him on it and he fixed it, but it got me thinking. It'd be nice if we as programmers could admit that copy-and-paste is going to happen and stop simply chastising each other for the inevitable errors. There are tools for checking other kinds of errors, so why not something to check for copy-and-paste errors? I envision a tool that would do something like a hierarchical diff on the parse tree of the source, looking for adjacent parallel structures that differ by just a few characters. When it finds them, it would look at the parts that differ to see if they form a recognizable pattern. If it sees a pattern like "x, y, z" when it's seen the "x, y, z" pattern in 99 other places it's probably okay. If it sees a pattern like "0, 1, 2" or "1, 3, 5" where there's a linear increment, then it's probably okay. But if it see something like "x, y, y" it could spit out a warning saying, "Hey, dufus, did you really mean that?" It'd be tricky to implement and would probably need a flexible system of heuristics for pattern matching, but it'd sure be nice.
About this Entry
Zen-chan (smoothed)
Apr. 1st, 2006 @ 09:18 pm (no subject)
Current Mood: ecstatic
Current Music: OC ReMix: Chrono Trigger Door to the End of Time
YAY! A paper with my name in the credits is going to SIGGRAPH this year. All those sleepless nights and hard work has paid off! Woohoo! Not bad for my first publication in computer graphics. (I'm only author number three, but this is still an auspicious beginning.)

And among other things, this means my little avatar here will be gracing the pages of the proceedings...
About this Entry
Zen-chan (smoothed)
Jan. 11th, 2006 @ 04:21 pm Book Meme
Current Mood: geeky
Current Music: VGMix.com: Unsealed (Legend of Zelda: A Link to the Past)
Meme from [info]grinnellian2001:

1. Grab the nearest book.
2. Open the book to page 123.
3. Find the fifth sentence.
4. Post the text of the sentence in your journal along with these instructions.
5. Don't search around and look for the coolest book you can find. Do what's actually next to you.

"The basic idea behind graph coloring is to construct a graph representing possible candidates for allocation to a register and then to use the graph to allocate registers."
About this Entry
Zen-chan (smoothed)
Jan. 6th, 2006 @ 11:41 pm More Snarkiness
Current Mood: cynical
Current Music: Super Castlevania: Theme of Simon
I think I need to stop reading the Joel on Software forums. JoS itself has some interesting ideas that seem fairly universally applicable to all segments of software development, even if I disagree with him on some of the particulars. But some of the opinions his readers express in the forums frankly annoy me.

I guess the main thing that bothers me is that they display a willful, almost cheerful, ignorance of the value of deeper computer science than that needed to slap a web interface onto an SQL database. This being, essentially a solved problem, they see no real need for developers to get a degree in computer science since they think most of what's needed for this kind of development can be self taught. Much of CS is seen as useless in those forums. Worse, they have a low opinion of those with CS degrees and the more advanced the degree the more condecension -- the attitude seems to be that most CS professors couldn't code their way out of a paper bag in a real production environment.

Maybe I'm just defensive of my own pursuit of degrees in CS, but that's not entirely it. I have a couple of problems with their attitude. First, my experience has been that self-taught hot shots are okay but actually produce moderately crappy code. "When everything is a hammer..." and all that. Not all of CS is immediately useful, but it at least enlarges ones toolbox. I used to be one of those self-taught hot shots, and I'd be ashamed to look at some of that code now. I've also had the pleasure of meeting some CS professors who are very talented coders in the classic sense. Some of their code is just brilliantly fast -- ray tracing 1024x1024 images in software at 60fps on a desktop, for example.

The other thing is a bit of a money issue. I'm a lot happier now working on much more challenging research problems, but I still get a little jealous of how much money some of the people whose work shows up on The Daily WTF earn. (i.e. consultants billing at $200/hr) Part of me always has this reaction of "Heck, for that price, I'll do it for you properly and make a tidy little sum for myself." And then I remember that I left for grad school to get away from those messes.

Lastly, I guess it's just a bit of pride on my part and annoyance that refering to myself as a software developer or having it as a job title on my resume lumps me in the same category as them. Calling them software developers feels like it dilutes the term, and I don't really know how to succinctly distinguish my approach to software development from theirs.

I really should stop reading those two forums. But it's like watching a train wreck where you just can't look away.
About this Entry
Zen-chan (smoothed)
Dec. 19th, 2005 @ 12:59 am Spell it out!
Current Mood: cranky
Current Music: The Waverly Consort Christmas: Exultation
I think I'm getting crotchety in my old age when it comes to software design. :-) As I've gotten better at it, my tolerance of certain things is lower. But there's one particular pet peeve that's been bothering me lately.

I'm taking a graduate level course in compilers next semester and in hopes of getting ahead on the project in that course, I've been reading up on it, thumbing through the textbook for the course: "Modern Compiler Implementation in Java" by Appel. It's a decent enough book on the topic, though truth be told, I prefer the Dragon book. But every time that I flip through it, I get irritate by the naming convention in the code samples. There are method names like procEntryExit3 and adj, class names like Assem, HashT and RegAlloc, and parameter names like aa, bb, cc, t, ig, etc. Even package names are abbreviated.

I really don't care whether code use BiCapitalization, camelCase, or underscores_between_words in identifier names as long as it's consistent. But please, be nice to your readers and maintainers and SPELL IT ALL OUT! The other annoying thing is that the worst offenders don't seem to comment their code well either, let alone use something like JavaDoc or Doxygen so the reader is left to rummage through the code to try to infer their cryptic interfaces.

I'll grant there was once a time when it made sense to abbreviate identifiers. Disk space and memory was at a premium, teletypes were slow and language implementations had fixed maximum limits on names. Those days are long gone. There are no browny points to be had for minimizing the characters in source code.

Typing time is no excuse either since most tools nowadays can help with that. Type a few characters, push a button and it guesses the rest of the name. Visual Studio, Eclipse and other IDEs have code completion with Alt-Space or whatever. Emacsen have dynamic expansion with M-/ and I know there's an equivalent in Vi. Any decent code editor is going to have some sort of similar feature.

It's there, so use it! People reading your code will thank you!
About this Entry
Zen-chan (smoothed)