tag:blogger.com,1999:blog-25647775026814637172024-03-05T22:15:32.142-05:00Teaching, Playing, and ProgrammingChris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.comBlogger34125tag:blogger.com,1999:blog-2564777502681463717.post-7188912925027967132013-11-03T08:13:00.000-05:002013-11-03T08:14:03.161-05:00Quickselect FTW!<p><i>More than a year ago, I answered a <a href="http://stackoverflow.com/questions/10861388/quickselect-algorithm-simplified-explanation">question on Stack Overflow</a> about the <a href="http://en.wikipedia.org/wiki/Quickselect">Quickselect algorithm</a>, which takes some unsorted data and finds the k-th smallest value (that is, the value that would be in position k if you were to sort the data). The person asking the question had seen multiple technical descriptions of the algorithm, but was looking for a simplified explanation that was not expressed as computer code. I tried to illustrate the algorithm in story form, and others seemed to like my story. The surprising part to me has been that votes continue to trickle in even today, and that this deliberately silly story is now my most upvoted answer. I suppose there's a lesson in there somewhere...</i></p><p>You walk into a gymnasium containing 200 children. It is September 8th, so you have a burning desire to find the 98th shortest child. You know that you could line them all up from shortest to tallest, but that would take forever. “I know”, you think, “I could use QUICKSELECT!”</p><p>You walk out into the crowd, close your eyes, stick out your finger, and spin around three times. When you open your eyes, you are pointing directly at one of the children, Peter Pivot. You say, “Quickly! Everybody shorter than Peter, come stand over here. And everybody taller than Peter, go stand over there. If you're the same height as Peter, you can go into either group.”</p><p>The children shuffle around, and soon they are standing in the two groups. You count and find 120 children in the shorter group, and 79 children in the taller group. You know the 98th shortest child must be in the shorter group, so you tell Peter and the 79 taller children to sit in the bleachers.</p><p>You again close your eyes, stick out your finger, and spin around three times. When you open your eyes, you are pointing directly at Peter's sister, Paula Pivot. You say, “Quickly! Those of you who are still standing. If you're shorter than Paula, come stand over here. If you're taller than Paula, go stand over there. If you're the same height, you can go into either group.”</p><p>The children shuffle around, and soon they are standing in the two groups. You count and find 59 children in the shorter group, and 60 children in the taller group. You know the 98th shortest child must be in the taller group, so you tell Paula and the 59 shorter children to sit in the bleachers.</p><p>You again close your eyes, stick out your finger, and spin around three times. When you open your eyes, you are pointing directly at Paula's cousin, Prudence Pivot. You say, “Quickly! Those of you who are still standing. If you're shorter than Prudence, come stand over here. If you're taller than Prudence, go stand over there. If you're the same height, you can go into either group.”</p><p>The children shuffle around, and soon they are standing in the two groups. You count and find 37 children in the shorter group, and 22 children in the taller group. You know that Paula and 59 other shorter children are sitting on the bleachers. Along with the 37 shorter children still standing, you know that a total of 97 children are shorter than Prudence. Therefore, Prudence is the 98th shortest child!</p><p>Quickselect FTW!</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com2tag:blogger.com,1999:blog-2564777502681463717.post-53447973610567836222011-11-06T14:41:00.003-05:002011-11-06T14:55:16.423-05:00On the Dangers of Giving Games as Wedding PresentsorWell, it seemed like a good idea at the time...[<i>This is a letter I included with a recent wedding present.</i>]
<p>Dear Ben and Sarah,</p>
<p>Well, it seemed like a good idea at the time…</p>
<p>I think you’ll enjoy this game, <i>Thunderstone</i>. I’ve been playing it a lot with my son. Like <i>Race for the Galaxy</i>, this one works very well with two players, but can also handle more players. (Predictably, with more players, it becomes very chaotic, especially when thieves are in play…) I’m so certain you’ll enjoy it that I also got you the first expansion, <i>Wrath of the Elements</i>.</p>
<p>You might notice that this box is the <i>Wrath of the Elements</i> box. See, the first <i>Thunderstone</i> comes with a huge box, with lots of wasted space. That box is twice as big as this one, and only comes with about half the cards you see before you. Knowing that dealing with the larger box would be difficult for you, I’ve combined all the cards for both the main game and the expansion into this one box. (By the way, if you end up liking the game, this box will also easily hold the cards for the second expansion, <i>Doomgate Legion</i>.)</p>
<p>There was just one eensy teensy flaw with my plan. A minor thing really, hardly worth mentioning.</p>
<p>The original rulebook was too big for this box.</p>
<p>I considered several options: Just leave out the rulebook and point you to the <a href="http://www.alderac.com/thunderstonerules.pdf">online rules</a>. Stick the rulebook in a separate, sturdy envelope, which is guaranteed to get lost in about 13.8 nanoseconds. Fold the rulebook in half and jam it in the box. Then I found the perfect solution. A post on BoardGameGeek described trimming the top and bottom off the rulebook—which is all wasted space anyway—with a paper cutter.</p><p style="border: solid thin black"><b>Fun With Words</b> Did you know that a <i>mangle</i> was a British machine used in the 1800’s to press water out of clothes? It’s called a <i>wringer</i> in the US. A probably apocryphal story asserts that the word mangle came into the English language to describe the damage done to clothes by this machine, but I think the causal chain is more likely to run in the other direction, with the machine being named after the word.</p><p>Umm, where was I? Oh yes, paper cutter. </p>
<p>Anyway, so I bring the rulebook into school and take it over to the room with the paper cutter. I line it up carefully, and pull down the chopper…which cuts about an inch into the rulebook and sticks. I push down a little harder…and the entire back of the paper cutter lifts off the table, the chopper twists the rulebook and pulls it partway off the bed and…</p>
<p>Hey, have you ever had a jam in a paper shredder? And cleared it by pulling half shredded paper back out the top of the machine. The papers come out looking pristine partway down the page, and then at a certain line of demarcation (<i>you know, that line really ought to have a cool name, like the Maginot Line or the Mendoza Line</i>), the rest comes out drooping in sad, wrinkled tatters. What’s the word? Oh yeah, mangled. Why do I bring that up? No reason, really.</p>
<p>Hmm, where was I? Right, paper cutter!</p>
<p>So I lift up the chopper and pull the rulebook out and…let’s just say it’s not looking too good. I flip it over—the rulebook, not the paper cutter, although that might have worked better—and try again on the other side. Let’s just say that <i>that</i> side left me longing for the Golden Age epitomized by the results of the first side. A few more minutes, and a few muttered imprecations later, and… </p>
<p>You know, my wife use to do scrapbooking, and they sell these funny little scissors that are designed to make an artistic ragged edge. Expensive little buggers. If only I had known, I could have saved her a lot of money.</p>
<p>So…<i>Thunderstone</i>! Great game! I think you’re going to like it. [<i>a few personal comments deleted</i>]</p>
<p>Congratulations!</p>
<p>Chris</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com9tag:blogger.com,1999:blog-2564777502681463717.post-7173119877274300032010-07-18T03:46:00.002-04:002010-07-19T06:03:37.964-04:00Eating My Way Across Oahu<p>See also <a href="http://okasaki.blogspot.com/2010/07/eating-my-way-across-kauai.html">Eating My Way Across Kauai</a></p>
<p><b>New for <i>Lost</i> fans: see extra links at the end of the post</b></p>
<p>We had fewer days on Oahu than Kauai, and part of that time was spent visiting family, so we had a lot fewer meals out on Oahu. But, on our last full day, we went on the <a href ="http://hawaiifoodtours.com/hitw.html">Hole-In-The-Wall</a> food tour of Honolulu with <a href="http://hawaiifoodtours.com/">Hawaii Food Tours</a>. I've been on several really good food tours around New York, but this blew them all away. I <b>highly</b> recommend taking the tour if you ever get the chance.</p>
<p>Also, the title above is misleading, because all but one of the places reviewed below were in Honolulu.</p>
<h3>Mochi</h3>
<p>As a kid, one of my favorite treats was when my father picked up mochi from <a href="http://www.fugetsu-do.com/">Fugetsu-Do</a> in the Little Tokyo area of Los Angeles. Unfortunately, New York offers nothing comparable. (I've found several places that offer various kinds of manju, but not the kind I grew up with.)</p>
<p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://jakebrattain.com/LA-6-20-09.php"><img style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;width: 320px; height: 240px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg2vbgM2aNwLGWi1j0v5DrKsqOdDruzmKQWdNObBdp6ZzbS0h8g7T9GM5ChHKrcJ8Cd9V4hdYi5tv7OhQ6OZiDAduopefyZFs-Srd8f961Qrg4UBXyoKSAt6ZW0bzybJRb9JqOqeEXvgeE/s320/mochi-with-red-bean.jpg" border="0" alt="Mochi (photo by Jake Battrain)" id="BLOGGER_PHOTO_ID_5494612110280889618" /></a>What is mochi? The kind I'm talking about is a sweet, sticky, soft, smooth rice dough, usually wrapped around a sweet red or white bean filling.</p>
<p>In planning our trip, I found several mochi stores in Honolulu that I knew we had to try.</p>
<p><b><a href="http://www.yelp.com/biz/mikawaya-confectionery-honolulu">Mikawaya Confectionary</b></a> (inside the Shirokaya department store in Ala Moana Center): We bought four pieces and split them. The hits were <i>orange gyohi</i> (an unfilled orange-flavored piece that tasted a bit like a creamsicle), and <i>taro gyohi</i> (a purple piece with taro-flavoring in the outer dough).</p>
<p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.yelp.com/biz_photos/hEmwcibuecBV8W7YOCXJ0A?select=Cy1PV2TdYeDFA16mUOlr3Q"><img style="margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 200px; height: 150px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgpI9jsisxwYNGVqsJ6WWTyBeaZszxCGlQoOM6otPAii-_GL8ZzwG96ZUvVe_OKf9ziiR1XYpkwnZQoFI6JB7j3p_gM0swDLpLyTDOtx2x98fxTpG2KVBMHm5jRMae0heKMOgPVD0cXxtQ/s200/l.jpeg" border="0" alt="Orange Gyohi (photo by Steph L.)" id="BLOGGER_PHOTO_ID_5494621112085494594" /></a><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.yelp.com/biz_photos/hEmwcibuecBV8W7YOCXJ0A?select=WrhQ6SyHlhfm5EOYTxPAng"><img style="margin:0 0 10px 10px;cursor:pointer; cursor:hand;width: 200px; height: 150px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj9q7a9bocFVTLZfklOiwfy0FKRb3rKHre39pigCYTFrJp_2P8iY-QoMmjVOo7BOCPqfxjaSg0MCAktNuqHfa_hVyi5zzCIAKwHD2HRDySKGQWYzfO5HoUs-VaWQ0DNhJzBQId_K6anyDY/s200/l-1.jpeg" border="0" alt="Taro Gyohi (photo by Steph L.)" id="BLOGGER_PHOTO_ID_5494622123412427874" /></a></p>
<p><b><a href="http://www.yelp.com/biz/fujiya-limited-honolulu">Fujiya Limited</a></b> (hard to spot store on Waikamilo Road): The specialty here is fruit mochi. I was expecting some kind of fruit paste, but no, it's whole pieces of fruit wrapped inside the dough along with a little bit of bean paste. We had strawberry, blueberry, and raspberry. (I also snuck in a <i>tsumami</i>, which was the closest I've had to the ones I grew up with, but softer.)</p>
<p><b>Nisshodo Candy Store</b>: The hardest of the three to find, it's literally in a warehouse behind a strip mall. Unfortunately, it was by far the worst of the three, so don't bother. My beloved white bean filling was particularly bad.</p>
<h3>Other Sweets</h3>
<p>I usually tend more to the savory side, but the rest of my family shares a profound sweet tooth. Hence, many of our stops involved sweets, even beyond the mochi above.</p>
<p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiY0qUu_L_WEnhyQrX7zVfz743M_bPa-ee7fIFP9kHpmtgaRDMV2dJUyJXpFUFdN7Ys8fIVwuk6bhbfQZzUf6o6KrCX8D8otqO7UBY52ubTZQa8q5F39fQwj4jBcljHdRUhOBxp4XvNYk4/s1600/l.jpeg"><img style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;width: 320px; height: 282px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiY0qUu_L_WEnhyQrX7zVfz743M_bPa-ee7fIFP9kHpmtgaRDMV2dJUyJXpFUFdN7Ys8fIVwuk6bhbfQZzUf6o6KrCX8D8otqO7UBY52ubTZQa8q5F39fQwj4jBcljHdRUhOBxp4XvNYk4/s320/l.jpeg" border="0" alt="Coco Puffs (photo by )" id="BLOGGER_PHOTO_ID_5494681440966616786" /></a><b><a href="http://www.yelp.com/biz/liliha-bakery-honolulu-2">Liliha Bakery</a></b> (N Kuakini St, just a little off Liliha St): Two words‒<b>coco puffs</b>. They sell over 5000 of these puppies a day. Basically an oversize cream puff with a creamy chocolate filling and a cap of chantilly frosting. How good are they? We went to the bakery four times, including three times in less than 24 hours! Interesting tidbit: The tiny little diner attached to this bakery is where they shot the scene in <i>Lost</i> where Kate visited her mother.</p>
<p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.yelp.com/biz_photos/7bJ83Jb_DTAF0eOw8j9fow?select=EHEBFLahVpcINwfhx-Gcuw"><img style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;width: 320px; height: 240px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjaxjAbHAKiZR6OhZatbkCkXhoyf3sCYaPt3FPw7pHmyfqMYDBum2CsABChZJvYU1hwy-mIgWvFhidUaavKgvYOZTmFsMKC93khf3Pi0FkgUqDdkL4MmNeNjCys8oww_49y39gWegzseK0/s320/l.jpeg" border="0" alt="Malasada (photo by Lina O.)" id="BLOGGER_PHOTO_ID_5494802199456842082" /></a><b><a href="http://www.yelp.com/biz/leonards-bakery-honolulu">Leonard's Bakery</a></b> (Kapahalu and Charles): It's all about the <i>malasadas</i> (Portuguese doughnuts). Fried dough, more bread-like than ordinary doughnuts, with hints of Portuguese sweet bread. Always served warm. Covered in your choice of several different powders (I took the classic sugar, but wish I had tried the li hing). Available with several different fillings (I chose haupia), or without. If you're into sweet fried dough‒you know who you are!‒this is probably a must try. I'm not, so I thought it was merely good. However, more people on our food tour picked this as their favorite stop than any other single place. Given the quality of the other places we stopped, Leonard's must be doing something right.</p>
<p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.yelp.com/biz_photos/iq5trScNb57AMWf8y5vKGQ?select=mEOYOfl6CPAXsa1tw8HWLg"><img style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;width: 320px; height: 240px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhddyvgPyBXIotEeFbo0Mo3OYVFX1hfxHJFJx9ZOfVoyWDGkBiVoW3FjgJ1xvHVyY3n-FBOEMw2rCceK_ECaXZ2h3V72DgUP3Qsl7My2-vCGp1ASNPI8N_7Ta586_zAOpfQ930zR6xz5JE/s320/l-1.jpeg" border="0" alt="Coconut tarts (photo by Mark G.)" id="BLOGGER_PHOTO_ID_5494896824163590066" /></a><b><a href="http://www.yelp.com/biz/rainbow-tea-stop-and-bakery-honolulu">Rainbow Tea Stop</a></b> (Maunakea Marketplace): Very good coconut tarts, but then we tried their <i>banana lumpia</i>. Bananas fried in lumpia wrappers, with a carmelized coating. Out of this world. And I don't even like bananas!</p>
<p>While I'm talking about sweets, I should say a few words about <i>haupia</i>, a kind of coconut pudding. Imagine coconut-milk jello not quite as firm as finger jello and you'll be on the right track. Haupia is everywhere in Hawaii, either by itself or as a filling for other desserts, such as malasadas from Leonards or the amazing vanilla haupia pie at the Snack Shack on <a href="http://okasaki.blogspot.com/2010/07/eating-my-way-across-kauai.html">Kauai</a>. If you're willing to use canned coconut milk, it's very easy to make at home. Whisk 3 cups canned coconut milk with 5 tablespoons sugar and 5 tablespoons cornstarch. Keep whisking over heat until bubbly. Spread into a pan, and refrigerate until firm. Cut into squares to serve. (Some people substitute water or milk for up to half of the coconut milk.)</p>
<h3>Manapua</h3>
<p>The name “manapua” literally translates to “flower power”, which makes no sense because it was a corruption of the longer phrase “mea ono pua'a” (roughly, pork pastry).</p>
<p>Manapua is the Hawaiian version of a Chinese bao, with the bun made out of a dough similar to Portuguese sweet bread. The buns can be baked or steamed, and the fillings can be savory or sweet, with char siu (Chinese roast pork) being the most popular. Manapua are so popular on Hawaii that they used to be sold door-to-door by the “manapua man” (Hawaii's version of the Good Humor Man). These days the manapua man sells out of a truck.</p>
<p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.yelp.com/biz_photos/ACBP9wpl99euV81GtATOmA?select=5MG6E0VDmFVbShZe8BRt7Q"><img style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;width: 320px; height: 240px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhY07IHv-aMX9T1yRh57lthqcP38kNXLLF186OJsSpLCOouFn1OqnKFL7xyiyVnkxSBHw7GTDxKS3K03KM8yWPhu521sguYiiyaow5-o1tgk54OR2x4nVCeHRzpD_4sLeDPTqVdfmBmM5g/s320/l-2.jpeg" border="0" alt="Char Siu Manapua (photo by Chelsey C.)" id="BLOGGER_PHOTO_ID_5494909949764642914" /></a><b><a href="http://www.yelp.com/biz/royal-kitchen-honolulu">Royal Kitchen</a></b> (on the pedestrian part of River Street just off N Kukui Street): If I could transport one shop from Hawaii to my neighborhood, this would be it. I could eat a couple of these EVERY SINGLE DAY for breakfast. I loved the cha siu manapua, and the lup chong manapua was almost as good. I probably wouldn't bother with the curry chicken manapua again, but I'd still like to try the kalua pork and the Portuguese sausage. The sweet lovers in my family also enjoyed the coconut manapua and the black sugar manapua. (Another <i>Lost</i> sighting: the pedestrian bridge by Royal Kitchen is where they filmed Sun paying off Jin's mother.)</p>
<p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.yelp.com/biz_photos/0tYdrYX_lElBLSuBOniOgA?select=gcio7EHk7DW8tf4QtsN4QA"><img style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;width: 320px; height: 282px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhVpZnCH0Kv5MmC2Hg2y4Zc3zqtd93_Pj2mGrJxs8uTVh4fBZihOcFL30WgF6XY1G9AYpCxAnJPn99ibIcJvKMAcsHcBVOak5YJV76nRscoYQgvBLTFlHMVGjlJnqDlIRPivumPG6Owy_Q/s320/l.jpeg" border="0" alt="Manapua and pork hash (photo by Malia H.)"id="BLOGGER_PHOTO_ID_5494919484494413602" /></a><b><a href="http://www.yelp.com/biz/libby-manapua-shop-honolulu">Libby Manapua</a></b> (corner of Kalihi and Kalani): After enjoying Royal Kitchen so much, we stopped here on our way to the airport to pick up lunch. My internet research had turned up Libby Manapua as a strong contender for best manapua on the island. My verdict was that Royal Kitchen is better. The buns at Libby were bigger than Royal Kitchen's, but with too little filling for all that bread. Also, Libby offered a much smaller selection of fillings. On the other hand, the <i>pork hash</i> at Libby was fantastic. You can see these little pork-filled dumplings in the upper right corner of the box.</p>
<p><b><a href="http://www.yelp.com/biz/sing-cheong-yuan-bakery-honolulu-2">Sing Cheong Yuan Bakery</a></b> (Maunakea Street): Not really manapua, but close enough that I'll mention it here. We never went into the store, but we were able to sample their <i>ma tai su</i>, a flaky bun filled with an intensely flavorful pork/shrimp mixture. Heavenly!</p>
<h3>Noodles</h3>
<p><b><a href="http://www.yelp.com/biz/ramen-nakamura-honolulu">Ramen Nakamura</a></b> (on Kalakaua Avenue in Waikiki): After binging on Hamura Saimin on <a href="http://okasaki.blogspot.com/2010/07/eating-my-way-across-kauai.html">Kauai</a>, I wanted to compare it to the “real thing”. Ramen Nakamura was very, very good‒I'd happily eat there again anytime‒but a notch below Hamura. To me, the biggest difference was in the noodles themselves, but I also had a slight preference for Hamura's broth. To be fair, Ramen Nakamura offers several different broths; I had the miso, but maybe the shio or shoyu broth would have fared better. Someone whose opinion I trust later told me that Ramen Nakamura has the best ramen in the city, and I believe it. Any negativity here should be read as praise for Hamura rather than a knock against Ramen Nakamura.</p>
<p><b><a href="http://www.yelp.com/biz/ying-leong-look-funn-factory-honolulu">Ying Leong Look Funn Factory</a></b> (Keekaulike Street): We were lucky enough to tour this tiny factory, where they still make <i>look funn</i> rice noodles by hand. First, they ladle the soupy noodle batter onto aluminum sheet pans, then steam them in the silver steamers shown in back.
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjy9J2y_n-6gSnQa7ZX0yOPdHdsdLaSWbudjmeSIdHfaaKHB3G2liGjpPYk8DuoGYpKcP94ypLz6mMXstuVgU_wE4rQYU81wsyJro4kuxNZm2aPR1S4Jy3uQt6sulFpd2MmRUAdZF8RAsc/s1600/noodle1.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 300px; height: 400px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjy9J2y_n-6gSnQa7ZX0yOPdHdsdLaSWbudjmeSIdHfaaKHB3G2liGjpPYk8DuoGYpKcP94ypLz6mMXstuVgU_wE4rQYU81wsyJro4kuxNZm2aPR1S4Jy3uQt6sulFpd2MmRUAdZF8RAsc/s400/noodle1.jpg" border="0" alt="(photo by Maria Ebling)"id="BLOGGER_PHOTO_ID_5494945724937841474" /></a>
When the pans come out of the steamer, they are stacked in front of fans to cool.
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg4dE5HgPXOGBz1NaPjjDVZjFNbD1PnZ2ST4aLWneZm6YehlZxhm9IDi8ezwWaznF3efQnEEPjO39OZugq_pkhGMKLYShaW_I-bGvqWpE-YB9EBEYkNOLzApyJ0ANG3gYcTfBzzJkyiZUg/s1600/noodle3.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 300px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg4dE5HgPXOGBz1NaPjjDVZjFNbD1PnZ2ST4aLWneZm6YehlZxhm9IDi8ezwWaznF3efQnEEPjO39OZugq_pkhGMKLYShaW_I-bGvqWpE-YB9EBEYkNOLzApyJ0ANG3gYcTfBzzJkyiZUg/s400/noodle3.jpg" border="0" alt="(photo by Maria Ebling)"id="BLOGGER_PHOTO_ID_5494947493400847890" /></a>
The noodles are carefully peeled out of the pan...
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiEGRIzZSKvWYqp61QSWviWIiIXD8PeyFl3ZBvtHPT6A50TT5yC2StIBLO-qPtpGOCYKz7chXQZQ-OdVUqG_yNeLqoAhjtQmjlo19QToAo4ImVVj9I81fiAxF5T078m8-YnD0RiYide1N8/s1600/noodle2.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 300px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiEGRIzZSKvWYqp61QSWviWIiIXD8PeyFl3ZBvtHPT6A50TT5yC2StIBLO-qPtpGOCYKz7chXQZQ-OdVUqG_yNeLqoAhjtQmjlo19QToAo4ImVVj9I81fiAxF5T078m8-YnD0RiYide1N8/s400/noodle2.jpg" border="0" alt="(photo by Maria Ebling)"id="BLOGGER_PHOTO_ID_5494948069352962802" /></a>
...and folded into stacks that look like giant calamari.
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgGVIq_SU8AhRqsRDJ2ebKcDx7-R7GBJz-aT0NdtuoMugp1EaKSDzBZjMF9cLI6nqCJCBKR4SCuuGq_8ax_cc-Z8cNpWSXsp_NgIThvxVPHkNMEjWGOFjZHjvWgs2E_BQxWe-61hmpGwvU/s1600/noodle5.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 300px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgGVIq_SU8AhRqsRDJ2ebKcDx7-R7GBJz-aT0NdtuoMugp1EaKSDzBZjMF9cLI6nqCJCBKR4SCuuGq_8ax_cc-Z8cNpWSXsp_NgIThvxVPHkNMEjWGOFjZHjvWgs2E_BQxWe-61hmpGwvU/s400/noodle5.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5494948651654823682" /></a>
Most of the noodles shown in these pictures are plain, but you can see small chunks in the batter in the first picture. These chunks are green onion and either char siu or shrimp. Below, you can see the finished product, sliced and drizzled with a little bit of soy sauce. Delicious!
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.yelp.com/biz_photos/N5FZYX3Xe_Db203POfVL1Q?select=2tfdfG5yX-Usgq8bTt07lQ"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 240px; height: 320px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgDXbgKl4uPZu6Rs0M8vDB9VxcMHKkVJVZlVVbnafaninPQP9CiQNNTDoIc22vCyTOo1pSpq5Giy8BaMSYq2a1P-TZlMjCNI4rg16SyZcUNEOS7ZoiZUW1JBnBGYKS5wyDXEgw28rIy_xk/s320/l-1.jpeg" border="0" alt="Look Funn (photo by Joshua C.)" id="BLOGGER_PHOTO_ID_5494934294423564002" /></a>
<h3>Polynesian Cultural Center Luau</h3>
<p>We spent a full day at the <a href="http://www.polynesia.com/">Polynesian Cultural Center</a>. It's fun and worth the trip, although if we do it again we would skip the tour guide. But forget all the cultural stuff‒I'm here to talk about the food!</p>
<p>First, I have to get something off my chest: <b>Dear PCC, The shave ice you sell in the park really should be shaved, not crushed!</b></p>
<p>Ok, I feel much better now.</p>
<p>The shave ice may have been disappointing, but their luau more than made up for it. Everything I tried was at least good, with many dishes reaching into outstanding territory, including
<ul>
<li> fabulous <i>kalua pig</i>, probably the second best I had on the trip
<li> outstanding <i>taro rolls</i> (purple dinner rolls made with taro flour)
<li> the best <i>poke</i> I had on the trip (poke is marinated chunks of raw ahi, although I found out later that PCC uses a Tahitian recipe rather than Hawaiian)
<li> a wonderful sweet potato salad made from purple Okinawan sweet potatoes
<li> fabulous <i>pipikaula</i> (similar to beef jerky, but softer)
<li> the best <i>haupia</i> I had on the trip
</ul>
<p>Of course, they also had luau staples such as poi, lomilomi salmon, chicken long rice, chicken teriyaki, and fresh pineapple. All these were good, but not as memorable as the above dishes.</p>
<p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.flickr.com/photos/18268873@N00/507309003"><img style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;width: 320px; height: 240px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjObhU9zzGNBwthryJ6sjVSDTBLCuZmZn1H1LMLmybCWY87ypxWUgOPoIon8Jk1nATgchFHxfuJidbLWmrNR8LBV6DL0q-u6rdXjGndtyqXu_F0rboKf7qDE0wC8-z09wuVr6D-6cSxVzA/s320/507309003_89218b7bbf.jpg" border="0" alt="Pineapple with li hing powder (photo by millietastic)" id="BLOGGER_PHOTO_ID_5495143553175549186" /></a>Speaking of fresh pineapple... At the family luau we went to for my cousin's first birthday, I gorged myself on fresh pineapple sprinkled with <i>li hing powder</i>.</p>
<p>A few years ago, I tried <i>li hing mui</i>, the king of the Hawaiian snack genre known as “crack seed”. Li hing mui is a salty dried plum covered with a bright red powder. The combination is salty, sweet, sour, stains your fingers red, and does funny things to your mouth. I have to admit I didn't like it. I think I even used the word “disgusting”.</p>
<p>But what I've now learned is that you can get the powder without the plum. I had it several times this trip sprinkled on fresh pineapple, which takes an already excellent treat up to the next level. I've heard that the powder is also good sprinkled on other kinds of fruit, on popcorn, even on ice cream. We brought a bag home that I look forward to experimenting with.</p>
<h3>New for <i>Lost</i> Fans</h3>
<p>I found a website (<a href="http://www.lostvirtualtour.com/welcome.php">Lost Virtual Tour</a>) that includes some great pictures of the places I mentioned, showing what they look like in the show and in real life.
<ul>
<li> <a href="http://www.lostvirtualtour.com/lost/filming_locations/lilihabakery/index.html">The diner from Liliha Bakery</a>
<li> <a href="http://www.lostvirtualtour.com/lost/filming_locations/kila_kalikimaka/index.html">The bridge by Royal Kitchen</a>
</ul>
To my surprise, this site also shows <a href="http://www.lostvirtualtour.com/lost/filming_locations/murphys/index.html">the pub where we went to our family luau</a>.</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com2tag:blogger.com,1999:blog-2564777502681463717.post-69381818018612421942010-07-16T12:14:00.002-04:002010-07-18T03:50:06.558-04:00Eating My Way Across Kauai<p>See also <a href="http://okasaki.blogspot.com/2010/07/eating-my-way-across-oahu.html">Eating My Way Across Oahu</a></p>
<p><i>I love to eat, so I'm going to temporarily hijack this blog with some dining recommendations from our recent vacation in Hawaii.</i></p>
<p>We just got back from almost two weeks in Hawaii. My favorite part of the trip was eating my way across Kauai and Oahu. In planning for the trip, I got a lot of good tips from food blogs and other internet reviews, so I'm going to pay it forward by reporting on our dining hits and misses. This post will cover Kauai, and the next post will cover Oahu.</p>
<p>Be aware that many of these places take cash only.</p>
<h3>Must Try</h3>
<p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.yelp.com/biz_photos/JH2tvTBx0PAZ4XTlFmUrlQ?select=w5J35ePhxmh2E4cEV8BNvw"><img style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;width: 320px; height: 240px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgCOAqci2-1j5UVLLs7rsreem_-bffWfE-9mxK7bCkJ8vpvlKdt23P0TU2DMMhOGhBcI34Clph7XdNUOBG_PRuuXUlRErHRwwsa_Sk6yxeWjJflg6XXVytxk67DlQlBzO_w0mU40VjCFbc/s320/l.jpeg" border="0" alt="Saimin Special (Photo by Christina C.)" id="BLOGGER_PHOTO_ID_5494479338581163122" /></a><b><a href="http://www.yelp.com/biz/hamura-saimin-stand-lihue-2">Hamura Saimin Stand</a></b> (Lihue, close to the airport): This place is a dive...and I mean that in the best possible way. It's old, run-down, hard-to-find, and tiny, so you'll probably have to wait for a few minutes. But the food is amazing, not to mention cheap and plentiful! I'm a huge fan of ramen (the real stuff, not the dried packages you find in the grocery store) and Hamura serves some of the best you'll find this side of Japan. The “special” (shown to the right) is a huge bowl filled with wonderful noodles and broth, and then topped with char siu (roast pork), won tons, fish cake, ham, green onions, cabbage, and a hard-boiled egg. The bbq sticks (beef or chicken), crispy wontons, and lilikoi (passion fruit) chiffon pie are also excellent, but be aware that they run out of the pie. Seating is at a single zig-zag counter, so be prepared to chat with your neightbors.</p>
<h3>Highly Recommended</h3>
<p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.yelp.com/biz_photos/5Fq5MhhxEj51wsOwUxhZZw?select=moq522LB5MpQjfMxFEW6TQ"><img style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;width: 320px; height: 240px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEivHJUMBAcppqKx8pYMzpZB-s_AhO6BMP-HUVJUdYpzyYnL9WclUKc0OJlaBbk21AQ5bI5RYDTxJ1ewlfhWhWvJLkqA1LLjrWHWWO9ZiBH9HIvX-ONojO-Tvad1EJ8SQMTrsgmG7Z5mB3Y/s320/l.jpeg" border="0" alt="Hanalei Dolphin (photo by Cheri A G.)" id="BLOGGER_PHOTO_ID_5494502967509599826" /></a><b><a href="http://www.yelp.com/biz/hanalei-dolphin-restaurant-hanalei">Hanalei Dolphin Restaurant</a></b> (Hanalei, on the right as you first drive into town): The best “fancy” meal we had on the trip. I had the shutome (broadbill swordfish) and my wife had the walu (Hawaiian butter fish). The shutome was among the best fish I've had in my life, and the walu was almost as good. Both were simply grilled, and then served with a slice of lemon and some drawn butter. The butter, in particular, was a revelation for me. Sure, you often see it with lobster and the like, but usually not with fish. After experiencing how much it enhanced the fish here, I'll have to ask for it at other places.</p>
<p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.yelp.com/biz_photos/RLizju7GoEXDMO248MESSg?select=g441bR_5qP1WvcCy68y7iQ"><img style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;width: 320px; height: 240px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjdMhxt7MD9ZbL7GsNIoklJtlCOOqpz9Mm5ftAjOrN5KZJCwtESP0DMXnmjsZcIy6yBY0tsx7qfjVwQ7Fi06vWZBpSfMB1Wnz8i9aHqrgAFFTga2vmewaawCMQrypM0R6z8YzD1T2sMEag/s320/l-1.jpeg" border="0" alt="Puka Dog (photo by Diana H.)" id="BLOGGER_PHOTO_ID_5494501593543790994" /></a><b><a href="http://www.yelp.com/biz/puka-dog-koloa">Puka Dog</a></b> (Poipu, inside the Poipu Shopping Village): My son LOVED these, declaring them almost as good as my father's sweet-and-sour chicken wings, which is his high-water mark for non-dessert foods. They take a huge unsliced bun, and stick it onto a big spike, which both makes a hole for the dog and toasts the inside of the bun. They then put some toppings in the hole, fill the bun with a polish sausage, and add some more toppings to the tip of the sausage sticking out of the hole. Okay, the hole thing is a gimmick, but where they really shine is the toppings‒six different fruit relishes including mango, pineapple, papaya, banana, star fruit, and coconut (mango and pineapple are probably the best). They also include a mayonnaise-like “garlic lemon secret sauce”.</p>
<p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.yelp.com/biz_photos/72kRIAYe_GlTOkFk-RJ2nQ?select=EcMSJP-IT3sAZKGhPaKbnQ"><img style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;width: 320px; height: 240px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjamnjGiCONROHApXFeIzaGZDHkxaX4wuJVE_G9Jr52KxOMpy2ROaUnxoVY4HkqCtTkQAI8tsku-alOskrSX40n_8SI45untqJ_nSSgPaALEg0W887zQH1GuM6zycYWHUXrYlO6C2PuUr8/s320/l-1.jpeg" border="0" alt="Pat's Taqueria (photo by Mark W.)" id="BLOGGER_PHOTO_ID_5494504672767348002" /></a><b><a href="http://www.yelp.com/biz/pats-taqueria-hanalei">Pat's Taqueria (aka Pat's Taco Wagon)</a></b> (Hanalei, by the base of the pier): On the mainland, lunch wagons are usually nothing special, but Hawaii has a tradition of great food served out of trucks. Pat's Taco Wagon is an excellent example. My first visit, I had the kalua pork burrito, which was very good. My second visit, I had the carne asada taco, which was mind-blowing. Both were kind of drippy, so be sure to lean over when you eat them.</p>
<p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.yelp.com/biz_photos/VcFDqt0Cm0IlPeSpl324Ig?select=6OxSY02KecPl_0Knda-Xfg"><img style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;width: 320px; height: 240px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjQwkPxu6SxT5QR5YN4RAw12-E_kGpjsm6F0Vha2liXwUETW22J0MAe7r0-AVdrH7CRKBRKEaBg4looKCT3Zluu3FFftZpMauhnYnW0yyt9YSVjAUctpvH7EynVLV-HtDCw_ZsfhCJwgEI/s320/l.jpeg" border="0" alt="Vanilla haupia pie (photo by alli t.)" id="BLOGGER_PHOTO_ID_5494508433804527714" /></a><b><a href="http://www.yelp.com/biz/village-snack-and-bakery-shop-hanalei">Village Snack & Bakery (aka The Snack Shack)</a></b> (Hanalei, in the back of the Ching Young Village Shopping Center): My favorite dessert on the island, vanilla haupia pie. Mmmm! If you get there early in the morning, you may also be lucky enough to get their fried mochi (three balls of mochi with a sugary coating on a stick). Their loco moco (a Hawaiian tradition with two scoops of rice, a hamburger steak, and two fried eggs, covered with brown gravy) and teriyaki beef sandwich were also outstanding, but the pancakes and apple cobbler were only so-so.</p>
<p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.yelp.com/biz_photos/qrHJwpDrwrp_FX0Uq0BHng?select=P2z57x-PoysDDAAwKxEPJA"><img style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;width: 320px; height: 240px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgWEW1Ge1PxKSeXphIIdrv6X_gGSN7zNQ9If27qTF8dc1pN3zJW51uSlsi4tiRUQk7qTiv_KNK8_Tpm05qNF2EKNrj9elS0j7xIhNuDX6gdkv4FBjTBFlM1A08Al4gtT7caFryDr4aToEU/s320/l.jpeg" border="0" alt="Shave Ice Paradise (photo by beno h.)" id="BLOGGER_PHOTO_ID_5494512243145286098" /></a><b><a href="http://www.yelp.com/biz/shave-ice-paradise-hanalei-2">Shave Ice Paradise</a></b> (Hanalei, across the street from the Ching Young Village Shopping Center): Shave ice is everywhere in Hawaii. Think giant snow cone, but made with shaved ice instead of crushed ice. The difference in texture is substantial, smooth instead of pebbly. You have a choice of many different syrups, and can add on ice cream underneath or sweetened condensed milk on top. The ice cream at the bottom didn't do much for me because you end up eating the top half of the ice without it, but the sweetened condensed milk on top (sometimes called a sno cap) is fantastic, changing what can sometimes be sickly sweet to sweet and creamy. Shave ice stands are very common, and there's not necessarily a lot of difference between them, but this one was the best we tried.</p>
<p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.yelp.com/biz_photos/8qTkY3ZqSx115u8uph14zQ?select=QMhG1bsnfklnJU54mm8AQg"><img style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;width: 320px; height: 240px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjBlI_arnTm2OBwvCq1U8-ffxQsHosXISbc1E5jbaEdCWQoDG7GDaGpVK9K2SSjTFtEHcKGiX3ssuLhcYbBfJexEdaTqtPTXaUVT6SXVfKq_HtWhlLJguneGPvv2y7Hb0TY8snb2VWJRoI/s320/l-1.jpeg" border="0" alt="Hanalei Taro & Juice Company (photo by Janet D.)" id="BLOGGER_PHOTO_ID_5494514049031240354" /></a><b><a href="http://www.yelp.com/biz/hanalei-taro-and-juice-co-hanalei">Hanalei Taro & Juice Company</a></b> (Hanalei, in front of Kayak Kauai): Another lunch wagon. Plate lunches are a Hawaiian tradition with two scoops of rice, macaroni salad, and some kind of meat. I had the kalua pork plate lunch, which turned out to be the best kalua pork I tried on the island. The plate lunch also came with a little slice of their mochi cake, which is very good. They are famous for their smoothies, with use a taro base in addition to various combinations of fruit. My smoothie was good, but nothing special. The downside is that it's hard to find them open! I think they move around, but I didn't know where to look other than their main location.</p>
<h3>Recommended</h3>
<p><b><a href="http://www.yelp.com/biz/kountry-kitchen-kapaa-2">Kountry Kitchen</a></b> (Kapaa): Gigantic macadamia nut pancakes, which were fantastic with coconut syrup. I had the special loco moco, which had kalua pork instead of the usual hamburger steak, and it was very good also.</p>
<p><b><a href="http://www.yelp.com/biz/bubba-burgers-hanalei">Bubba Burgers</a></b> (Hanalei, across the street from the Ching Young Village Shopping Center): Try the teriyaki burger with pineapple. These are fast food burgers rather than restaurant burgers, but still good.</p>
<p><b><a href="http://www.yelp.com/biz/lapperts-hawaii-hanalei">Lappert's Hawaii</a></b> (Princeville, in the Princeville Center): Good ice cream with unusual flavors. I'd say good, but not great. Both <a href="http://www.yelp.com/biz/kilauea-video-ice-cream-and-candy-kilauea">Kilauea Video and Ice Cream</a> (in Kilauea) and <a href="http://www.yelp.com/biz/pinks-creamery-hanalei">Pink's Creamery</a> (in Hanalei) sounded better to me, but we didn't get to try those.</p>
<p><b><a href="http://www.yelp.com/biz/banana-joes-kilauea">Banana Joe's</a></b> (Kilauea, just off the highway): I didn't go, but my family loved their frostees. They also had some great fresh fruit, including lychees and “apple bananas”.</p>
<p><b><a href="http://www.yelp.com/biz/tip-top-motel-cafe-and-bakery-lihue">Tip Top Motel Cafe & Bakery</a></b> (Lihue): Very busy, but incredibly fast service. The pancakes were good, but not as good as Kountry Kitchen's. I enjoyed the bento breakfast, which included teriyaki beef, chicken wings, Goteborg sausage, rice and macaroni salad.</p>
<p><b><a href="http://www.yelp.com/biz/the-mediterranean-gourmet-hanalei">Mediterranean Gourmet</a></b> (Hanalei, way past the main drag, almost to Haena, at the Hanalei Colony Resort): We ate two lunches there, with good gyros, falafels, and chicken kebabs. We also went to their once-a-week luau since we were staying at the resort. The food at the luau was only so-so, but the entertainment was fun, if much lower key than many of the fancier tourist luaus.</p>
<h3>Not Recommended</h3>
<p><b><a href="http://www.yelp.com/biz/bar-acuda-hanalei-2">Bar Acuda</a></b> (Hanalei): We were disappointed in this highly recommended tapas bar. The food we had there was good, some of it excellent. The problem is that their menu is just too limited, with only about a dozen choices for tapas. After running through everything we wanted to try out of their tapas offerings, we proceeded down the street to Bubba Burgers because the kids were still hungry.</p>
<p><b><a href="http://www.yelp.com/biz/the-hanalei-gourmet-hanalei">Hanalei Gourmet</a></b> (Hanalei): Okay, but nothing special.</p>
<p><b><a href="http://www.yelp.com/biz/bouchons-hanalei-hanalei">Bouchons Hanalei</a></b> (Hanalei): Nice atmosphere, but mediocre food. I did not try their sushi, so maybe that's better.</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com3tag:blogger.com,1999:blog-2564777502681463717.post-75035151124919231192009-11-23T23:35:00.001-05:002009-11-23T23:37:04.829-05:00Round-Robin Tournament Scheduling<p>For the last several years, I've held an in-class tournament on the last class day before Thanksgiving. Everybody's mind is elsewhere anyway, so the positive vibes generated by an hour spent hootin' and hollerin' are far more valuable than class content that would be forgotten long before the turkey made it into the oven.</p>
<p>Tomorrow's the big day, so I've spent part of today working out the tournament schedule. As usually seems to be the case, I have a different number of teams this year from past years, so I had to make a new schedule from scratch. I keep forgetting how I did it last time, but I always seem to converge back on the same technique. I finally decided to write down the technique so I can just look it up next year. Also, I'm hoping somebody can tell me what this technique is called, since it can't possibly be original.</p>
<p>Unless I have too many teams, I like to run a round-robin tournament, where everybody plays everybody else. There's a well-known algorithm for scheduling such a tournament by hand. I'll illustrate this algorithm with 6 teams, numbered 0–5. Start by writing the teams down in two rows, as follows:
<pre>
0 1 2
5 4 3
</pre>
The columns say which teams play each other. In this case, team 0 plays team 5, team 1 plays team 4, and team 2 plays team 3.
<p>
Now, leave team 0 in place, but rotate teams 1–5 one position clockwise.
<pre>
0 5 1
4 3 2
</pre>
In this round, team 0 plays team 4, team 5 plays team 3, and team 1 plays team 2. This process continues for three more rounds:
<pre>
0 4 5
3 2 1
0 3 4
2 1 5
0 2 3
1 5 4
</pre>
For an even number of teams, this technique generates a schedule with N−1 rounds, and N/2 games per round. For an odd number of teams, you add an extra dummy team, yielding a schedule with N rounds and (N−1)/2 games per round. In each round, the team scheduled against the dummy gets a bye.
<p>Many games have a slight asymmetry, such as a homefield advantage or a first-move advantage. For my game, the “red” team has a very small advantage over the “blue” team. In tournaments for such games, it is important to balance the number of “home” games and “away” games played by each team. In the above algorithm, this is accomplished by making the top row the home team in odd-numbered rounds and the bottom row the home team in even-numbered rounds. (Note that, when N is even, half the teams will get one extra home game.)
<p>Okay, so the above technique is easy, but it has a major drawback for my purposes, at least when N is odd. Because the tournament must be completed by the end of the class period, I need to be ready to drop games from the schedule if it looks like we're running long. The easiest way to accomplish this is to drop an entire round. But when N is odd, one team has a bye, which means that that team will end up playing a different number of games from everybody else, which in turn can make it difficult to determine the winner of the tournament.</p>
<p>
To avoid this problem, I use the following technique. I organize the schedule in N/2 rounds, rounded down if N is odd. In each round (except possibly the last), every team plays twice: one home game and one away game. The rule is that, in round R, team X plays at home against team (X+R) mod N, and away against team (X−R) mod N. (If you don't remember how mod works, it simply means that the team numbers wrap around.) For example, here is a schedule for 7 teams, numbered 0–6.
<pre>
Round 1: 0-1 1-2 2-3 3-4 4-5 5-6 6-0
Round 2: 0-2 1-3 2-4 3-5 4-6 5-0 6-1
Round 3: 0-3 1-4 2-5 3-6 4-0 5-1 6-2
</pre>
Each game is listed as HOME TEAM–AWAY TEAM.
<p>
If N is even, then the last round is treated specially. As described so far, the last round in an 8-team tournament would look like
<pre>
Round 4: 0-4 1-5 2-6 3-7 4-0 5-1 6-2 7-3
</pre>
This involves repeat games, such as 0-4 and 4-0. To prevent such repeats, we chop off the second half of the last round when N is even.
<p>
Again, the advantage of this scheduling algorithm is that I can delete a round on the fly without causing an imbalance in the number of games that each team plays. Deleting a round also maintains the balance between home games and away games for each team, although that's a lesser concern.</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com6tag:blogger.com,1999:blog-2564777502681463717.post-79610335834911302292009-10-22T20:17:00.010-04:002009-10-23T15:24:45.629-04:00Binomial queues as a nested type<p><i><b>Warning: this is probably only of interest to functional programmers.</b></i></p>
<p><i>Maciej Kotowicz recently asked on the Haskell Cafe mailing list about implementing binomial queues (also known as <a href="http://en.wikipedia.org/wiki/Binomial_heap">binomial heaps</a>) using fancy type machinery so that the type-checker can enforce the shape invariants of the data structure. This reminded me of a discussion I had with some colleagues in the summer of 1998 about using nested types to enforce these kinds of invariants. A little digging around in mail archives yielded this email, presented here with some light formatting and a few fixed typos.</i></p>
<p>I've been playing with binomial queues as a nested type, and I think
you'll find the end result interesting.</p>
<h3>REVIEW</h3>
<p>Let me first quickly review the usual implementation of binomial queues.
Recall that a binomial tree has the shape
<pre>
data Tree a = Node a [Tree a]
</pre>
A binomial tree of rank k has k children, of ranks k-1 .. 0 (stored in the
list in decreasing order of rank). Note that we can combine two
heap-ordered binomial trees of rank k to get a heap-ordered binomial
tree of rank (k+1) as follows:
<pre>
combine a@(Node x xs) b@(Node y ys)
| x <= y = Node x (b : xs)
| otherwise = Node y (a : ys)
</pre>
Now a binomial queue is a list of heap-ordered binomial trees of increasing
height (but not necessarily of consecutive ranks). We'll represent the ranks
of those trees that are present by their position in the tree. Thus,
some ranks will be empty. This could be implemented as
<pre>
type Binom a = [Maybe (Tree a)]
</pre>
or somewhat more efficiently as
<pre>
data Binom a = Nil
| Zero (Binom a)
| One (Tree a) (Binom a)
</pre>
or better still by unboxing the Tree in the One constructor
<pre>
data Binom a = Nil
| Zero (Binom a)
| One a [Tree a] (Binom a)
</pre>
I won't go over all the operations -- they are amply covered elsewhere.
I'll just describe two functions. The first, add, takes a tree and a
list (where the tree has the same rank as the first position in the
list), and returns a new list. It works basically like the increment
function on binary numbers.
<pre>
add :: Ord a => a -> [Tree a] -> Binom a -> Binom a
add x xs Nil = One x xs Nil
add x xs (Zero h) = One x xs h
add x xs (One y ys h)
| x <= y = Zero (add x (Node y ys : xs) h)
| otherwise = Zero (add y (Node x xs : ys) h)
</pre>
The merge function is similar and works basically like the addition
function on binary numbers.
<p>
Finally, the getMin function returns the minimum element of a queue
paired with the queue without that element. The helper function
getMin_ returns a triple of the minimum element in some suffix of the
queue, the list of children associated with that minimum element, and
the suffix without that element.
<pre>
getMin_ :: Ord a => Binom a -> (a, [Tree a], Binom a)
getMin_ (Zero h) = case getMin_ h of
(y,ys,h') -> (y,ys,Zero h')
getMin_ (One x xs Nil) = (x,xs,Nil)
getMin_ (One x xs h) = case getMin_ h of
(y,ys,h') | x <= y -> (x,xs,Zero h)
| otherwise -> (y,ys,One x xs h')
getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
in (x,merge (list2binom xs Nil) h')
list2binom [] h = h
list2binom (Node x xs : ys) h = list2binom ys (One x xs h)
</pre>
Note that when getMin receives a list of children, it converts them
to a valid binomial queue by reversing the list (and changing each
pair of a Node constructor and a (:) constructor to a One constructor).
<h3>NESTED REPRESENTATION -- FIRST ATTEMPT</h3>
<p>
By following the same approach we have been using to design nested
datatypes, we get the following representation of binomial queues.
<pre>
data Binom_ a b = Nil
| Zero (Binom_ a (Trees a b))
| One a b (Binom_ a (Trees a b))
type Trees a b = (a, b, b)
type Binom a = Binom_ a ()
</pre>
Here the list of children
<pre>
(Node x3 xs3 : Node x2 xs2 : Node x1 xs1 : Node x0 xs0 : [])
</pre>
is being represented by the nested triples
<pre>
(xs3,xs3', (x2,xs2', (x1,xs1', (x0,xs0', ()))))
</pre>
(where xsN' is the appropriate conversion of xsN).
<p>All the functions are perfectly straightforward, except for getMin and
getMin_ which must incrementally build up the reversing function to
convert
<pre>
(xs3,xs3', (x2,xs2', (x1,xs1', (x0,xs0', ()))))
</pre>
to
<pre>
One x0 xs0' (One x1 xs1' (One x2 xs2' (One x3 xs3' Nil)))
</pre>
As a result of building up this reverse function incrementally, this
implementation ends up being roughly 10% slower than the original.
<h3>INTERLUDE ON REVERSING LISTS</h3>
Suppose we want to support the following ADT. We want sequences with
three operations:
<pre>
empty :: ReversableSeq a
cons :: a -> ReversableSeq a -> ReversableSeq a
rev :: ReversableSeq a -> [a]
</pre>
with the obvious semantics. cons must take O(1) time, but rev may take
O(n) time. A list is a reasonable implementation with
<pre>
type ReversableSeq a = [a]
empty = []
cons = (:)
rev = reverse
</pre>
but, if you think about it, there's a fair amount of interpretive
overhead in the pattern matching that reverse performs at every step.
Way back in 1985, John Hughes came up with a representation that
avoids this overhead:
<pre>
type ReversableSeq a = [a] -> [a]
empty = id
cons x xs = xs . (x:)
rev xs = xs []
</pre>
The result of cons 1 (cons 2 (cons 3 empty)) is
<pre>
id . (3:) . (2:) . (1:)
</pre>
which, when applied to [] by the rev function, yields [3,2,1]. One way to
think of this representation is as lists with "holes" at the ends. The
cons operation fills in this hole with an element and another hole, and the
rev operation fills in the hole with []. (This is quite similar to
difference lists in logic programming...)
<p>Applying this trick to the regular representation of binomial queues
yields
<pre>
data Binom a = Nil
| Zero (Binom a)
| One a (Binom a -> Binom a) (Binom a)
</pre>
which turns out to be about 10% faster than the original representation.
<h3>NESTED REPRESENTATION -- SECOND ATTEMPT</h3>
<p>Ok, let's try to make a nested datatype out of this. Conceptually, the
nesting should keep track of our position in the queue so that we know
what rank the current tree has and can't possibly mix up trees of different
ranks. We hypothesize some Base type for the beginning of the list,
and some type transformer Succ that modifies the type as we
move down the queue.
<pre>
type Base = ???
type Succ b = ??? -- this might need to be Succ a b
type Binom a = Binom_ a Base
data Binom_ a b = Nil
| Zero (Binom_ a (Succ b))
| One a (Binom_ a ??? -> Binom_ a ???) (Binom_ a (Succ b))
</pre>
Now, what should the missing types in the One constructor be? Well,
the function (Binom_ a ??? -> Binom_ a ???) represents the children
of the current node. If this node is of rank k, then these children
are of ranks 0 .. k-1. The function (Binom_ a ??? -> Binom_ a ???)
takes a queue starting at rank k and adds the children to the front of
it, yielding a queue starting at rank 0. So the ???'s can be filled in as
<pre>
| One a (Binom_ a b -> Binom_ a Base) (Binom_ a (Succ b))
</pre>
or just
<pre>
| One a (Binom_ a b -> Binom a) (Binom_ a (Succ b))
</pre>
Now, what should the types Base and Succ be? It doesn't matter because
we never construct data of those types, we simply use the types to
discriminate between positions in the queue. So we can define Base
and Succ as
<pre>
type Base = Void
newtype Succ b = S Void
</pre>
I think this is a very interesting type for several reasons:
<ul>
<li>It includes an arrow type, which we haven't seen much.
<li>The RHS of the datatype definition (in fact, just the One constructor)
has occurrences of Binom_ at no fewer than three different types
<pre>
Binom_ a b
Binom_ a Base
Binom_ a (Succ b)
</pre>
I've seen two before, but not three.
<li>It includes types which are never used, but are merely there to
capture certain invariants (in this case, that trees of different
ranks should never be confused). <i>[2009 Comment: Today, these are called <a href="http://www.haskell.org/haskellwiki/Phantom_type">phantom types</a>.]</i> In some ways this might make
this type less interesting, but an interesting consequence is that the
code satisifes a certain "type erasure" property: if you erase the
types from all the functions, you get code for the optimized
regular representation.
</ul>
Because of this "type erasure" property, you might expect it to be just
as fast as the optimized regular representation, but in fact it is roughly
10% slower -- or roughly as fast as the original regular representation.
This is because the extra types hinder a certain optimization that the
programmer might make (and which I did make in the optimized regular
representation).
<p>
Recall the type of the getMin_ function from the original regular
representation, and the way it was used by getMin.
<pre>
getMin_ :: Ord a => Binom a -> (a, [Tree a], Binom a)
getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
in (x,merge (list2binom xs Nil) h')
</pre>
For the optimized regular representation, this becomes
<pre>
getMin_ :: Ord a => Binom a -> (a, Binom a -> Binom a, Binom a)
getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
in (x,merge (xs Nil) h')
</pre>
Now, consider the optimized nested representation. We can't just write
<pre>
getMin_ :: Ord a => Binom_ a b -> (a, Binom_ a b -> Binom a, Binom_ a b)
</pre>
because we don't know the rank of the tree that the second component of
the triple came from. (Note that if we had existential types, we could
write
<pre>
getMin_ :: Ord a => Binom_ a b ->
(a, exists c. Binom_ a c -> Binom a, Binom_ a b)
getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
in (x,merge (xs Nil) h')
</pre>
Some implementations do in fact support existential types, but in limited
ways that would carry efficiency costs of their own...)
<p>
Instead of returning the children and then applying them to Nil at the
end, we apply the children to Nil first, and then return the result,
yielding the type
<pre>
getMin_ :: Ord a => Binom_ a b -> (a, Binom a, Binom_ a b)
getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
in (x,merge xs h')
</pre>
This depends on laziness to evaluate only the children of the final
minimum, and not all the children of the temporary minimums along the
way. However, this does mean that we build a lot more thunks of the
form (xs Nil) along the way. And building these thunks is apparently
quite expensive.
<p><i><b>2009 Addendum</b> Ralf Hinze considers a similar representation in Section 6 of <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.571">Numerical Representations as Higher-Order Nested Datatypes</a>. Today, you would probably use fancier type machinery like dependent types or maybe GADTs, but it's still amazing how far you can get with only nested types.</i></p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com6tag:blogger.com,1999:blog-2564777502681463717.post-56098534477230394672008-10-01T23:36:00.000-04:002008-10-01T23:36:22.874-04:00Score one for induction!<p>One of my favorite textbooks on algorithms—in spite of the fact that it's twenty years old—is Udi Manber's <i>Introduction to Algorithms: A Creative Approach</i>. However, I have never been tempted to actually use it in class. You see, the book's greatest strength is also its greatest weakness.</p>
<p>Most textbooks on algorithms show you a lot of polished algorithms, but provide little or no insight on how to go about designing such algorithms. Manber's book does a very good job providing such insight, by making an analogy with inductive proofs. If you have any skill with induction, then you can use Manber's approach to help you design algorithms. (Of course, this should come as no surprise since writing an inductive proof and writing a recursive function are essentially the same activity.)</p>
<p>I'm sure you see the flaw here—most students are even less comfortable with induction than they are with recursion. It's like trying to help somebody learn to drive a car by making an analogy with riding a unicycle. For a certain segment of the audience, that analogy might be just what they need, but for the most of the audience, the analogy will only produce puzzled looks.</p>
<p>I was recently helping a student who was struggling to get a handle on recursion. He was making the common beginner mistake of trying to think about what happens during the recursive call instead of trusting that the recursive call works (sometimes called the recursive leap of faith). By sheer coincidence, I had happened to notice the day before that this student had done very well in our discrete math course the previous year. Time to give it a try...</p>
<p>“You know when you're writing a proof by induction and at some point you use the inductive hypothesis? That's just like a recursive call. You don't worry about what happens inside the inductive hypothesis, you just say ‘Assume that it works for N-1...’ It's the same with recursion. You just assume that the recursive call works.”</p>
<p>That comparison actually seemed to help. Maybe Manber was onto something after all!</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com7tag:blogger.com,1999:blog-2564777502681463717.post-28163376343770417942008-09-25T23:46:00.002-04:002008-09-25T23:50:00.702-04:00Less than vs Greater than<p>From math, we know that X < Y is the same as Y > X. But in programming, they're not the same.</p>
<p>Oh, I'm not talking about situations where X and Y have side effects that interact badly. Instead, I'm talking about situations where one may be more error prone than the other.</p>
<p>Although the two expressions are mathematically equivalent, they're not <i>linguistically</i> equivalent. One focuses attention on something being smaller, and the other focuses attention on something being bigger. For example, it is a relatively common mistake to go the wrong way when searching a binary search tree. However, almost every time I run into this error, the student has also written the comparisons backward from the direction I think of as “natural”.</p>
<p>Consider the following function for determining whether a given key <tt>x</tt> appears in a binary search tree <tt>t</tt>:
<pre>
function member(x,t) is
if t = null then return false
if t.key = x then return true
if t.key < x then return member(x,t.left)
if t.key > x then return member(x,t.right)
</pre>
The fact that I've written this using recursion instead of iteration is irrelevant. What matters is that the third case goes left when it should go right, and vice versa for the fourth case. But looking more carefully at that third case
<pre>
if t.key < x then return member(x,t.left)
</pre>
I'm not particularly surprised by the error. The comparison <tt>t.key < x</tt> focuses attention on something being smaller, and the left side of the tree is where the smaller keys go. By asking whether <tt>x</tt> is smaller than <tt>t.key</tt>, rather than whether <tt>t.key</tt> is smaller than <tt>x</tt>, I think we're much less likely to fall into this trap.</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com11tag:blogger.com,1999:blog-2564777502681463717.post-25326589202630587002008-09-13T00:10:00.001-04:002008-09-14T22:49:27.671-04:00Hey, you got your loop in my recursion!<p>I've written <a href="http://okasaki.blogspot.com/2008/02/boolean-confusion.html">before</a> about trying to diagnose students' broken or ineffective mental models from the mistakes they make. Here's a mistake that I see frequently from students who are not yet comfortable with recursion.</p>
<p>Say you wanted to write a function to calculate the sum of a list using a loop. Many students could easily write something like
<pre>
function sum(list) is
variable total := 0
while list /= null do
total := total + list.item
list := list.next
return total
</pre>
But ask them to write the sum function using recursion, and you might get something like
<pre>
function sum(list) is
variable total := 0
if list = null then
return total
else
total := total + list.item
return sum(list.next)
</pre>
Of course, this code always returns 0. It's pretty clear that the writer had the
iterative algorithm in mind, and doesn't understand that each recursive call to <tt>sum</tt> creates a new instance of the <tt>total</tt> variable.</p>
<p>When I watch such a student writing code like this, he often declares the variable immediately, before even beginning to think about what the recursive decomposition is going to look like, an almost spinal reflex conditioned by several semesters of writing loops. I can explain recursion until I'm hoarse and draw pictures until my hand cramps up, but I can't compete with the will-o'-the-wisp allure of that variable. Once it's there, it will almost inevitably lead the student to his doom in the bogs of iterative thinking.</p>
<p>
One trick to help such a student is to break the cycle where it begins, by getting rid of that variable. Tell him to write the function <i>without</i> using any local or global variables. Or, if he really thinks he needs a variable, to declare it as a constant instead. Of course, there are times when a variable is perfectly appropriate inside a recursive function, but such examples can often be avoided until the student has a better grasp of recursion.</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com18tag:blogger.com,1999:blog-2564777502681463717.post-74818809712453694812008-07-31T11:42:00.001-04:002008-07-31T11:42:22.787-04:00In search of epiphany<p>I watched the movie <a href="http://www.imdb.com/title/tt0377107/">Proof</a> last night. I highly recommend it. It's not often that mathematicians get so much screen time.</p>
<p>The nature of mathematical <a href="http://okasaki.blogspot.com/2008/03/creativity.html">creativity</a> plays a large role in the movie. One comment was especially intriguing. (Minor spoiler ahead.) In describing the process of solving a particularly difficult problem, one character says, “It was like...connecting dots. Some nights I...I could connect three or four of them. And some nights they'd be really far apart. I'd have no idea how to get to the next one, if there was the next one.”</p>
<p>This description rings both true and false for me. The true part is <i>I'd have no idea how to get to the next one, if there was the next one.</i> This nicely summarizes what it's like to work on a hard problem. You don't know what to do next, and you're not sure that a solution even exists.</p>
<p>But the connecting dots part doesn't feel right. It makes the process sound linear, when the reality is anything but. In my experience, the really hard problems—the ones that require the most creativity—are most often solved by <i>epiphany</i>, by having the whole solution burst into your head, seemingly in an instant. That's when the connecting dots part happens, but it all happens at once, not a few a time.</p>
<p>Of course, the catch is that epiphany can't be forced. I'm reminded of the old joke about the lottery. A man prays fervently every night, “Please, Lord, let me win the lottery tomorrow.” After twenty years, a heavenly voice responds, “Would you buy a ticket already!”</p>
<p>No, you can't just sit around waiting for an epiphany to happen. Epiphanies are hard work! <a href="http://en.wikipedia.org/wiki/TANSTAAFL">TANSTAAFL.</a> So, how do you go about searching for epiphany? Every epiphany I've ever had has been the result of a two-pronged effort.</p>
<p>The first prong is building up <a href="http://en.wikipedia.org/wiki/Sweat_equity">sweat equity</a>. I thoroughly explore the space around the problem, playing with the problem from many different angles. Of course, I'm actively trying to solve the problem during this time, because I might get lucky and stumble across a solution. But I don't worry too much if I don't seem to be getting anywhere. This part of the process is not so much about connecting the dots as about building lots and lots (and lots) of <i>potential</i> connections.</p>
<p>The second prong is staying alert. That's easy to say, but really hard to do over long periods of time. Eventually, I hope, some stray thought or some environmental trigger will start a cascade, where some subset of those potential connections will become actual connections, creating a path to the solution. Sometimes this happens when you're relaxed and your mind is drifting, such as in the shower or while driving. I remember once in grad school trying all afternoon to track down a bug. That night my wife and I went over to a friend's house for dinner. Everybody was shocked when, in the middle of beef stroganoff, I suddenly shouted out, “That's it!”</p>
<p>Other times the epiphany can happen while you're actively working on something else. For example, the key insight behind <a href="http://okasaki.blogspot.com/2008/03/what-heck-is-math-trade.html">TradeMaximizer</a> came while I was trying to put together a homework for my Algorithms class. I had been working off and on for weeks trying to find cycles in the trade graph. But I had set that aside and was coming up with homework problems, when I stumbled across a stray comment that talked about converting a directed graph into a bipartite graph. That sentence was enough to set off the chain reaction of connections and, within seconds, TradeMaximizer was born.</p>
<p>Probably the most famous story about scientific epiphany is that of <a href="http://en.wikipedia.org/wiki/Eureka_%28word%29#Archimedes">Archimedes' bath</a>. Funny story: Shortly after announcing TradeMaximizer to the math trade community on BoardGameGeek, I received a peevish email from another BoardGameGeek user who thought he also had a solution. He described how he had come to BoardGameGeek, eager to share his discovery, only to find my announcement first. He complained “Argh! Way to shout ‘Eureka!’ while Archimedes is drying himself off!” (The other solution turned out to be bogus.)</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com0tag:blogger.com,1999:blog-2564777502681463717.post-75302670969205906882008-07-16T23:27:00.001-04:002008-07-31T09:41:31.999-04:00Games for Programmers: Black Vienna<p><i>The next in an irregular series of board game recommendations for programmers. Of course, you don't have to be a programmer to enjoy these games, but if you are a programmer, then I think there's a pretty good chance that you'll like them.</i></p>
<p>O frabjous day!</p>
<p>My favorite deduction game, <a href="http://www.boardgamegeek.com/game/756">Black Vienna</a>, has long been out of print, but now you can give it a try online, thanks to the efforts of Greg Aleknevicus. Go check out <a href="http://www.aleknevicus.com/bv/">Black Vienna Online</a>. It's free and easy to use. The user interface isn't going to win any awards, but it gets the job done. I'm thrilled that this game can now reach a wider audience.</p>
<p>Most deduction games are for two players, but Black Vienna handles three to six players. Your goal is to figure out the members of the infamous “Black Vienna” gang. There are 27 suspect cards, labeled A-Z and Ö. At the beginning of the game, three of these cards are chosen randomly and set aside. Those are the members of the gang.</p>
<p>The remaining 24 suspect cards are dealt out evenly to the players. (With 5 players, one of the players gets only 4 cards.) These are the cards of suspects for whom you can provide alibis.</p>
<p>On your turn you conduct an investigation. There is a pool of available investigation cards, each showing three suspects. You choose one of the available investigation cards and place it in front of another player. That player marks the card with plastic chips, according to how many of the suspects are in her hand. For example, if I have the cards BGMTXY and somebody plays the BQT card on me, I would mark it with two chips (for the B and the T). Other players would then know that I had two of the three suspects, but not necessarily which ones.</p>
<p>The turn then passes to the player who was just investigated.</p>
<p>One nice thing about Black Vienna as a game is that every player is involved on every turn. Even if you are not actively part of the investigation, you still need to update your information with the results of the investigation, and follow any chains of deductions to their conclusions.</p>
<h3>Example Deductions</h3>
<p>Some deductions are obvious. For example, if I played two chips on the BQT card, and you have the Q card in your hand, then you know that I have the B and the T. Other deductions are less obvious. Here's an actual example from a recent game. Call the other players Caitlin, Monica, Drew, and Dom.</p>
<p>Monica played one chip on GPX, but I had the X, so I knew that she had either G or P (but not both). Similarly, she also played one chip on DHR, but I knew Dom had the R, so Monica had either D or H. Finally, she played two chips on LNV.</p>
<p>Drew played one chip on DVY and zero chips on FÖY, so he had either D or V. Between Drew and Monica, they had at least 4 of the 5 cards DHLNV and at least 5 of the 7 cards DGHLNPV (possibly more if Drew had any of GHLNP).</p>
<p>Meanwhile, I knew all but two of Caitlin's cards. The only possibilities for those last two cards were DGHLNPV. Monica and Drew together had at least 5 of those 7 cards, so Monica, Drew, and Caitlin together must have all 7.</p>
<p>This tells me that none of these 7 cards are in the gang, and none of these 7 cards are in Dom's hand. It also tells me that Drew does not have any of GHLNP.</p>
<p>Finally, I can be more specific about Caitlin's cards. One of her two cards is G or P, and the other is one of DHLNV.</p>
<h3>Online Play</h3>
<p>The online implementation is asynchronous. You do not need to be logged in at the same time as other players. Instead, the system emails you whenever a turn is taken with the results of the investigation. When it is your turn, you can log on and take your turn at your leisure. This means that a 45-minute face-to-face game can take days or even weeks when played online, but it also means that you can play the game with odd minutes here and there, instead of having to carve out a solid chunk of time. An additional benefit is that it is easy to play with friends in different time zones. For example, I frequently play with friends on the other side of the country.</p>
<p>However, the greatest benefit of the online implementation is that it does away with the greatest weakness of face-to-face play—player errors. Not errors in deductions, which would be your own fault and would only affect you, but errors in answering investigations. If a player carelessly puts out, say, one chip when he should have put out two chips, it ruins the game for everyone. Even if the player notices the error a few turns later and tries to correct it, it's far too late. By then, the other players have already updated their notes with deductions made from the faulty answer, and typically have no way of backing out of those deductions.</p>
<p>If you want to give Black Vienna a try, see the <a href="http://www.aleknevicus.com/bv/rules.php">detailed rules of the game</a> and the <a href="http://www.aleknevicus.com/bv/about.php">instructions for the online interface</a>.</p>
<p><b>Addendum:</b> I've played in several three-player games recently. It's ok with that number, but I think it's significantly better with four or five players. (I haven't tried six yet.) With three players, the deductions are less interesting, and there is a greater chance for one player to get lucky.</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com20tag:blogger.com,1999:blog-2564777502681463717.post-50152743432822616032008-07-08T23:39:00.001-04:002008-07-08T23:40:07.952-04:00Breadth-First Numbering: An Algorithm in Pictures<p>I've always enjoyed the mathematical tradition of “proofs without words”, so I wanted to see if something similar could be done with an algorithm. Of course, an algorithm is typically more complicated than a mathematical identity, so it's not surprising that an algorithm typically can't be captured in a single picture. Instead, I've found the idea of a <a href="http://en.wikipedia.org/wiki/Commutative_diagram">commutative diagram</a> to be a useful pictorial shorthand, where the short way around the diagram gives a high-level view of the operation, and the long way around gives more detail. Here is an attempt to describe my breadth-first numbering algorithm from ICFP 2000 using this idea.</p>
<h3>Wanted</h3>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnmJpk5VoJEIcI9OYwRjAfrThyphenhyphen2lr314EZ8zNOknVyV8jQ4-GezptyT6I9bXcrDmyXpBMihoUQmouWJ6LmpeQXcCm-GBu0t9qh14cccurgByQDNgDQJOJ1vVVg5K6GZu2xitW7gjX3sXY/s1600-h/bfn-wanted.jpg"><img style="cursor:pointer; cursor:hand;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnmJpk5VoJEIcI9OYwRjAfrThyphenhyphen2lr314EZ8zNOknVyV8jQ4-GezptyT6I9bXcrDmyXpBMihoUQmouWJ6LmpeQXcCm-GBu0t9qh14cccurgByQDNgDQJOJ1vVVg5K6GZu2xitW7gjX3sXY/s400/bfn-wanted.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5220839721371851250" /></a>
<h3>Rules</h3>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhtjo8lgIbz_35acTiYTPn5HCBW4ZYh-2mGwbCJ06ZCPDSMoUgWfmsFkHuFFYm5rvFYEU05TX67Drz4kFcAEwEBCEs9MR7zYBwOcEo7Tgy3NM7kBFOqPgyCTywo_0w66Tcg9JeQmxwj8kE/s1600-h/bfn-rules.jpg"><img style="cursor:pointer; cursor:hand;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhtjo8lgIbz_35acTiYTPn5HCBW4ZYh-2mGwbCJ06ZCPDSMoUgWfmsFkHuFFYm5rvFYEU05TX67Drz4kFcAEwEBCEs9MR7zYBwOcEo7Tgy3NM7kBFOqPgyCTywo_0w66Tcg9JeQmxwj8kE/s400/bfn-rules.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5220852788093657250" /></a>
<h3>Example</h3>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhXXEzbzjhNAiVNyvNVxhr-8MIZCKMEHg6uSYU2O7BuQ8HOfFJ8nQTt6pS9X7bqiyPx8m7srtRIOtAoSfpwWSXbu71-hVNI1lRn-jUFNR4yt_QvQMbU0qyqUoq7KAIZPFuHTkvj6-H1CkA/s1600-h/bfn-example.jpg"><img style="cursor:pointer; cursor:hand;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhXXEzbzjhNAiVNyvNVxhr-8MIZCKMEHg6uSYU2O7BuQ8HOfFJ8nQTt6pS9X7bqiyPx8m7srtRIOtAoSfpwWSXbu71-hVNI1lRn-jUFNR4yt_QvQMbU0qyqUoq7KAIZPFuHTkvj6-H1CkA/s400/bfn-example.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5220852966754625378" /></a>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com3tag:blogger.com,1999:blog-2564777502681463717.post-50640631702715339012008-07-02T20:35:00.017-04:002008-07-02T21:06:54.345-04:00Functional Programming in...Ada?<p>Ada is not the first language that comes to mind when you want to do functional programming. (<i>You in the back, stop laughing!</i>) Why, with excellent functional programming languages like Haskell or ML easily available, would I choose to do a functional programming project in Ada? (<i>I CAN STILL HEAR YOU LAUGHING!</i>) Partly because we use Ada in some courses at our institution, and I wanted a library that could help in teaching recursion to novices. But, honestly, mostly I just wanted to see if it could be done.</p>
<blockquote style="width: 65%; font: bold 1.0em Arial, Helvetica, Verdana, sans-serif; border: 1pt solid black; padding: 0.5ex;">“It's like this fellow I knew in El Paso. One day, he just took all his clothes off and jumped in a mess of cactus. I asked him that same question, ‘Why?’...He said, ‘It seemed like a good idea at the time.’” <div style="textalign:right;">– Steve McQueen, <i>The Magnificent Seven</i></div></blockquote>
<p>Somewhat to my surprise, functional programming actually works reasonably well in Ada. You wouldn't want to program a large system this way, but small-scale projects are quite possible, albeit much more verbose than functional programmers are used to.</p>
<h3>Instrumenting recursive functions</h3>
<p>My application is going to be a library for instrumenting recursive functions. I want to be able to take a recursive function and run it with different combinations of <i>monitors</i>. Each monitor executes a little bit of extra code every time the recursive function is called, including recursive calls. Simple examples of useful monitors include counting the number of calls, or tracking the maximum call depth, or printing trace information on every call or return. More complicated examples include adding memoization to a recursive function or automatically detecting when a function is stuck in an infinite recursion.</p>
<p>Ideally, the library should be easy enough for students to use, but I'll settle for it being easy enough for instructors to use.</p>
<p>Of course, there are many ways to design such a library. I'm going to use a design based on ideas from functional programming. The basic ideas have been folklore in the functional programming community for a long time. For example, I remember doing something similar in SML in the early '90s. Bruce McAdam wrote a nice <a href="http://www.lfcs.inf.ed.ac.uk/reports/97/ECS-LFCS-97-375/ECS-LFCS-97-375.pdf">tech report</a> describing these techniques in great detail. The trick here is going to be figuring out how to implement this design in Ada.</p>
<p>(Incidentally, if anybody has a truly object-oriented approach to solving the same problem, I'd be interested in seeing it.)</p>
<h3>Preparing the recursive function</h3>
<p>Without some kind of support for <a href="http://en.wikipedia.org/wiki/Reflection_(computer_science)">reflection</a>, it seems too much to hope that I'll be able to observe the recursive calls inside a recursive function. Therefore, I'm willing to require some modifications to the recursive function, as long as those modifications are fairly straightforward. However, I should only need to modify the function once, rather than every time I run it with a different monitor.</p>
<p>Stealing an idea from functional programming called the <a href="http://en.wikipedia.org/wiki/Fixed_point_combinator">Y combinator</a>, I'll modify each recursive function to take an extra argument that is itself a function (or, more specifically, a pointer to a function). The recursive function will call this passed-in function wherever it would normally call itself. The passed-in function will eventually call the recursive function, but may run some other code first.</p>
<p>Here's an example using the ever popular Fibonacci function. The original recursive function might be written
<pre>
function Fib(X : Integer) return integer is
begin
if X <= 1 then
return 1;
else
return Fib(X-1) + Fib(X-2);
end if;
end Fib;
</pre>
Adding the extra argument and replacing the recursive calls with calls to the passed-in function yields
<pre>
function Fib(<font color="red"><b>Rec : access function(X : Integer)
return Integer;</b></font>
X : Integer) return integer is
begin
if X <= 1 then
return 1;
else
return <font color="red"><b>Rec</b></font>(X-1) + <font color="red"><b>Rec</b></font>(X-2);
end if;
end Fib;
</pre>
where the changes are shown in red. Note that <tt>access function(X :
Integer) return Integer</tt> is the type of a pointer to a function
that takes an integer and returns an integer. In the rest of this
post, I'll assume that the functions being instrumented always take an
integer and return an integer. If I can get this to work at all, then
generalizing this to arbitrary argument and return types will be
trivial using Ada's notion of <a href="http://en.wikipedia.org/wiki/Generic_programming#Generics_in_Ada">generics</a>.
<h3>Running the recursive function</h3>
<p>
Now, to simply run this function recursively <i>without</i> attaching
a monitor, I'll call it with <tt>Run</tt>, which is responsible for
“tying the knot” by somehow making the function call
itself. The <tt>Run</tt> function is written
<pre>
function Run(Fun : ...<i>type to be filled in
later</i>...
X : Integer) return Integer is
function Rec(X : Integer) return Integer is
begin
Fun(Rec'Access, X);
end Rec;
begin
return Rec(X);
end Run;
</pre>
Here, <tt>Fun</tt> is a function like the modified <tt>Fib</tt>
above. <tt>Run</tt> defines a local helper functon, <tt>Rec</tt>,
that merely passes itself to <tt>Fun</tt>.</p>
<p>
I would call this function by writing something like
<pre>
...Run(Fib'Access, 10)...
</pre>
where <tt>Fib'Access</tt> is Ada-speak for a pointer to the <tt>Fib</tt> function. This
calls <tt>Rec(10)</tt>, which calls <tt>Fib(Rec'Access,10)</tt>, which in turn calls <tt>Rec(9)</tt>, which in turn calls <tt>Fib(Rec'Access,9)</tt>, and so on. Eventually, the whole thing returns 89, as expected.</p>
<p>
I left out the type of <tt>Fun</tt> above, because it starts to get
unwieldy. I can figure out what this type should be by looking at the type of <tt>Fib</tt>. The full signature of <tt>Run</tt> is
<pre>
function Run(Fun : access function
(Rec : access function(X:Integer)
return Integer;
X : Integer) return Integer;
X : Integer) return Integer;
</pre>
<h3>A small lie</h3>
<p>
What I'd really <i>like</i> to be able to do is define a type abbreviation
<pre>
type Fun_Type is access function
(Rec : access function(X:Integer)
return Integer;
X : Integer) return Integer;
</pre>
and then write the signature of <tt>Run</tt> as
<pre>
function Run(Fun : Fun_Type;
X : Integer) return Integer;
</pre>
Unfortunately, I can't. Or rather, I can, but it turns out to be
useless. The problem is that Ada is really paranoid about what you do
with pointers to functions. In particular, it won't let a pointer to
a function match a named type if that function is defined in a
deeper lexical scope than the type definition. This restriction does
not apply to so-called <i>anonymous access</i> types, so I'm forced to
rewrite the entire type everywhere it's used rather than giving it a name and referring to the name.</p>
<p>
However, to simplify the presentation, I'm going to <i>pretend</i>
that I can use <tt>Fun_Type</tt> as defined above. Just remember
that, in the real implementation, every occurrence of
<tt>Fun_Type</tt> needs to be replaced with the more verbose anonymous type. I'll write <tt><i>Fun_Type</i></tt> in italics as a reminder that it's not the real code.
<h3>A simple monitor</h3>
<p>
Now, here is a simple monitor that counts the number of calls to the recursive function, and prints out that number at the end.
<pre>
function Count(Fun : <i>Fun_Type</i>;
X : Integer) return Integer is
Num_Calls : Integer := 0;
function My_Fun
(Rec : access function(X:Integer)
return Integer;
X : Integer) return Integer is
begin
Num_Calls := Num_Calls + 1;
return Fun(Rec,X);
end My_Fun;
Result : Integer := Run(My_Fun'Access,X);
begin
Put("Number of calls = ");
Put(Num_Calls,0);
New_Line;
return Result;
end Count;
</pre>
<p>Now, when I call
<pre>
Put( Count(Fib'Access,10) );
</pre>
I get
<pre>
Number of calls = 177
89
</pre>
where the first line is printed by the monitor and the second line is printed by the external <tt>Put</tt>.
<p>The <tt>Count</tt> monitor creates a new function <tt>My_Fun</tt> to give to <tt>Run</tt>. <tt>My_Fun</tt> simply increments <tt>Num_Calls</tt> and calls <tt>Fun</tt>. Now, every time <tt>Fun</tt> makes a recursive call to <tt>Rec</tt>, <tt>Rec</tt> will call <tt>My_Fun</tt>, which calls <tt>Fun</tt>.
<p>So basically, <tt>Count</tt> “wraps” <tt>Fun</tt> with
a little bit of code to increment the <tt>Num_Calls</tt> variable, and
this code gets executed every time the <tt>Rec</tt> function is
called.
<p>In addition, <tt>Count</tt> does a little bit of work around the
top-level recursive call, namely initializing the <tt>Num_Calls</tt>
variable to 0, and printing the number of calls at the end.
<h3>A memoization monitor</h3>
<p>
Here's a more complicated monitor. This one modifies the recursive
function to do <a href="http://en.wikipedia.org/wiki/Memoization">memoization</a> (first
cousin to <a href="http://en.wikipedia.org/wiki/Dynamic_programming">dynamic
programming</a>). The idea is that, when a function is called
multiple times on the same arguments, you can save time by remembering
those arguments and the corresponding results. Then when the function
is called with arguments you have seen before, you can simply return
the stored result, instead of recomputing it.</p>
<pre>
function Memoize(Fun : <i>Fun_Type</i>;
X : Integer) return Integer is
Results : array (0..X) OF Integer;
Ready : array (0..X) OF Boolean
:= (others => False);
function My_Fun
(Rec : access function(X:Integer)
return Integer;
X : Integer) return Integer is
begin
if not Ready(X) then
Results(X) := Fun(Rec,X);
Ready(X) := True;
end if;
return Results(X);
end My_Fun;
begin
return Run(My_Fun'Access,X);
end Memoize;
</pre>
The difference can be dramatic.
<pre>
...Memoize(Fib'Access, 30)...
</pre>
executes the body of <tt>Fib</tt> a total of 31 times, whereas
<pre>
...Run(Fib'Access, 30)...
</pre>
executes the body of <tt>Fib</tt> almost 2.7 <i>million</i> times (2692537 times, to be exact).
<p>
I made an assumption above that, if the original argument was X, then the range of possible arguments in all the calls is 0..X. This is good enough to illustrate the idea, but a more general implementation might be parameterized by the bounds to use, or by a function that calculates those bounds from the original X.</p>
<h3>Multiple monitors</h3>
<p>How did I know above that <tt>Run</tt> executes the body of
<tt>Fib</tt> 2692537 times? By running <tt>Fib</tt> with the
<tt>Count</tt> monitor. How did I know that <tt>Memoize</tt> executes
the body of <tt>Fib</tt> 31 times? By running <tt>Fib</tt> with both the
<tt>Memoize</tt> and <tt>Count</tt> monitors together.</p>
<p>Except that, as currently written, the <tt>Memoize</tt> and
<tt>Count</tt> monitors <i>can't</i> be used together. I can run <tt>Fib</tt> with one or the other, but not both simultaneously.
<p>What I want is a way to layer one monitor on top of another,
building arbitrary stacks of monitors. The clues to how to do this are already in the current implementations of <tt>Memoize</tt> and <tt>Count</tt>.</p>
<p>Notice that both <tt>Memoize</tt> and <tt>Count</tt> have the same
interface as <tt>Run</tt>. In other words, a monitor is an
alternative run function that adds some extra machinery to the basic
<tt>Run</tt>. Further, notice that both <tt>Memoize</tt> and
<tt>Count</tt> build a <tt>My_Fun</tt> function by wrapping some extra
code around <tt>Fun</tt> and then run <tt>My_Fun</tt> using the
<tt>Run</tt> function. The key insight is that we can parameterize <tt>Memoize</tt> and <tt>Count</tt> by which run function to use for running <tt>My_Fun</tt>. That might be the basic <tt>Run</tt> function, but it might also be a run function corresponding to a different monitor.</p>
<p>
To achieve this parameterization, I'll use generics instead of passing function pointers. The existing definitions of <tt>Memoize</tt> and <tt>Count</tt> will still work, but they need to be preceded by additional code to take a run function as a generic parameter. For example,
<pre>
<font color="red">generic
with function Run(Fun : <i>Fun_Type</i>;
X : Integer) return Integer;
function Count(Fun : <i>Fun_Type</i>;
X : Integer) return Integer;</font>
function Count(Fun : <i>Fun_Type</i>;
X : Integer) return Integer is
...
... Run(My_Fun'Access, X);
...
</pre>
The new parts are in red. I didn't change the existing code of
<tt>Count</tt> at all, but now the call to <tt>Run</tt> in the body of
<tt>Count</tt> refers to the run function passed in as a generic
parameter.
<p>
Using a monitor is now a two-stage process, first instantiating the generic function to create the desired run function, and then calling that run function. For example,
<pre>
function C_Run is new Count(Run);
function MC_Run is new Memoize(C_Run);
...MC_Run(Fib'Access, 30)...
</pre>
Notice that the basic <tt>Run</tt> function is always used in the first instantiation, where it serves as the base of the stack of monitors.</p>
<p>
But wait! Something strange is happening here. This program displays 59 calls, not 31 calls as expected. However, if we layer the monitors in the opposite order
<pre>
function M_Run is new Memoize(Run);
function CM_Run is new Count(M_Run);
...MC_Run(Fib'Access, 30)...
</pre>
then we get the 31 calls.</p>
<p>
It's really a question of when the memoization code checks for a
repeated argument relative to when the counting code increments
the counter. If the memoization check happens before the increment,
we get 31 calls. If the memoization check happens after the
increment, we get 59 calls. Either way, the body of the original
<tt>Fib</tt> function is only executed 31 times.
</p>
<p>
And that's it, really. There's still a lot of grunt work involved in
fleshing out a complete, robust library, but all the important design
decisions have already been made. Implementing a wide variety of monitors is
fairly easy using <tt>Count</tt> and <tt>Memoize</tt> as templates.
</p>
<h3>Generics vs function pointers</h3>
<p>
One aspect of this design deserves a little more discussion. I'm
mixing two different styles of passing functions as arguments, using
generics in some places and function pointers in other places. Why
not just use one style consistently? Because the two styles of
passing around functions have different strengths and weaknesses.
</p>
<p>
One major difference is that generics work much better than function
pointers when you want to <i>return</i> a function. For example, the
generic <tt>Count</tt> monitor takes a run function and returns a run
function. It's easy to imagine writing <tt>Count</tt> as
<pre>
function Count(Run : <i>Run_Type</i>)
return <i>Run_Type</i> is ...
</pre>
where <tt><i>Run_Type</i></tt> is the appropriate <tt>access function</tt> type. But, in practice, this doesn't work because Ada lacks
<a href="http://en.wikipedia.org/wiki/Closure_%28computer_science%29">closures</a>. The natural way to write this would be
<pre>
function Count(Run : <i>Run_Type</i>) return <i>Run_Type</i> is
function My_Run(Fun : <i>Fun_Type</i>;
X : Integer) return Integer is
...
begin
return My_Run'Access;
end Count;
</pre>
but you can't return <tt>My_Run'Access</tt> because <tt>My_Run</tt> goes away as soon as <tt>Count</tt> returns.</p>
<p>
Note that it is possible to get around this restriction against
returning function pointers by re-writing strategic code fragments in
<a href="http://en.wikipedia.org/wiki/Continuation_passing_style">continuation-passing style</a>, so that the function pointers in question can be passed to
a continuation instead of returned. This works fine on a small scale,
but quickly blows the runtime stack when attempted on a large scale.</p>
<p>
A second major difference is that it is easier to write third-order
(or even higher-order) functions using function pointers than
using generics. A first-order function takes an ordinary value as an
argument. A second-order function takes a first-order function as an
argument. A third-order function takes a second-order function as an
argument, and so on. Now, consider a monitor like <tt>Count</tt>.
<tt>Count</tt> takes a <tt>Run</tt> function, which takes a
<tt>Fun</tt> function, which takes a <tt>Rec</tt> function, so
<tt>Count</tt> is fourth-order!</p>
<p>
Currently, I pass the <tt>Run</tt> functions using generics, but the
<tt>Fun</tt> functions using function pointers. (Ignore the
<tt>Rec</tt> functions for now.) Suppose I wanted to pass both
<tt>Run</tt> functions and <tt>Fun</tt> functions using generics.
This would mean that each <tt>Run</tt> function would take its
<tt>Fun</tt> function as a generic parameter. But <i>that</i> means
that, when we pass a <tt>Run</tt> function to a monitor like
<tt>Count</tt>, we need to pass it as a generic function. In other
words, <tt>Count</tt> would need to be a generic function that takes a
generic function as an argument. That's not allowed in Ada. Or, more
truthfully, it is sometimes allowed, but it's extremely painful.
</p>
<p>
In Ada, a generic function can neither take a generic function as an
argument nor return a generic function as a result. However, a
package can contain generic components, so you can sometimes fake it
wrapping the argument or result in a package. For example, you can
fake a generic function that returns a generic function by writing a
generic package that contains a generic function as a component.
</p>
<p>
In a limited way, you can do the same thing in the other direction.
If you want a generic function to take a generic function as an
argument, you can fake it by wrapping the argument in a package, so
that the outer generic function takes a package (which contains a
generic function as a component). The catch is that you can't
instantiate the outer generic function with just any old package
meeting a certain specification, but only with packages that are
themselves instantiations of a single generic package. Making all
that work is an exercise in pain that I leave to the most masochistic
of readers.
</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com6tag:blogger.com,1999:blog-2564777502681463717.post-81109861322766088122008-06-04T10:41:00.000-04:002008-06-04T10:41:32.485-04:00No Applause, Please<p>My school recently had its graduation. This year's graduating seniors (the computer science majors, anyway) are particularly memorable for me. For one thing, I had more success than usual in luring them into playing board games, especially Race for the Galaxy, Attika, RoboRally, and Ricochet Robots.</p>
<p>However, this group also stood out for a classroom behavior that I'm not used to—applause.</p>
<p>It started in Algorithms. In this course, when a homework is due, I usually have several students present their solutions. If the student solutions have not illustrated a point that I wanted to make, I will then present my solution, which is usually more elegant, and sometimes significantly more efficient as well. My goal in doing this is not to show them up, or to say “hey, dummy, this is what you should have written”, but rather to help them catch a glimpse of the beauty I see in an elegant algorithm, to inspire them with what is possible. (I do worry sometimes that fragile personalities might find the experience demoralizing, rather than inspiring.)</p>
<p>Last year, after presenting such a solution, I was very surprised when one particular student started clapping. He continued to do this in future weeks, and eventually pressured other students into joining him.</p>
<p>At first, I was taken aback, but over time, I got more and more frustrated. It felt like the applause was saying “this is so far beyond me that I could never hope to match it”, whereas I was hoping for a reaction more like “this may be beyond me right now, but, by golly, if I work at it, I'll be able to do that someday”. Eventually, I snapped, “C'mon, I'm not trying to impress you with <i>my</i> brilliance. I want you to impress me with <i>your</i> brilliance!”</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com6tag:blogger.com,1999:blog-2564777502681463717.post-53868577576568660052008-05-23T13:26:00.000-04:002008-05-23T13:26:31.868-04:00A Story About Odd and Even Numbers<p><i>This is a story my son and I wrote together when he was four. He came up with the basic story. I helped with the English and with the turtle character.</i></p>
<h3 align="center">The Seven Jellybeans</h3>
<p>Once upon a time, there was a lizard and a snake who were friends. They played together and had fun everyday until one day, the lizard's daddy gave them a bag of jellybeans to share.</p>
<p>In the bag, there were seven jellybeans. The lizard divided the jellybeans into two piles. His pile had 5 jellybeans, and the snake's pile had 2 jellybeans.</p>
<p>The snake said, “Wait a minute. That's not fair. You have more jellybeans than I do. You'd better give me one more jellybean.”</p>
<p>So the lizard gave the snake one more jellybean. And now the lizard had 4 jellybeans, and the snake had 3 jellybeans. The snake said, “Hey, that's still not fair. You still have more jellybeans than I do. You'd better give me one more jellybean.”</p>
<p>So the lizard gave the snake one more jellybean. And now the lizard had 3 jellybeans, and the snake had 4 jellybeans. Now the snake was happy, but the lizard said, “Hey, that's not fair. Now you have more jellybeans than I do. You'd better give me back one jellybean.”</p>
<p>So the snake gave the lizard back one jellybean. And now the lizard had 4 jellybeans, and the snake had 3 jellybeans. The snake said, “Hey, what happened? Now you have more jellybeans again. You must have cheated!”</p>
<p>And then the lizard and the snake began to fight.</p>
<p>While they were fighting, their friend the turtle walked by. He asked them why they were fighting, and the lizard and the snake told him.</p>
<p>“Hmm,” said the turtle. “If I solve your problem, will you give me one jellybean?”</p>
<p>The lizard and the snake didn't want to share their jellybeans, but they didn't want to fight either, so they agreed.</p>
<p>The turtle slowly ate one jellybean. Then he turned around and began to walk away.</p>
<p>“Wait a minute,"” shouted the lizard and the snake together. “You said that if we gave you one jellybean, you would solve our problem.”</p>
<p>“I just did,” said the turtle as he continued to walk away.</p>
<p>The lizard and the snake looked at their piles of jellybeans. The lizard had 3 jellybeans and the snake had 3 jellybeans. They happily ate their jellybeans, and soon all of the jellybeans disappeared.</p>
<p>The next day, the snake's mommy gave them a box of raisins to share. The lizard and the snake opened the box and counted seven raisins. “Oh no,” they said, and they went to look for the turtle to give him one of their raisins.</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com4tag:blogger.com,1999:blog-2564777502681463717.post-16454244676163497002008-05-20T11:44:00.000-04:002008-05-20T11:44:52.174-04:00Designing a Data Structure<p>Students are rarely given an opportunity to design an algorithmically non-trivial data structure. We might give them a scenario and ask them to design how to represent the data, but that design decision is usually something like choosing between a hash table or an array or a linked-structure. Once that high level decision is made, there is very little left to design.</p>
<p>One reason for this is that many data structures depend on non-obvious invariants. Most students are pretty shaky on the whole idea of invariants to begin with; they're never going to spontaneously come up with something like the rules describing <a href="http://en.wikipedia.org/wiki/Red_black_tree">red-black trees</a> or <a href="http://en.wikipedia.org/wiki/Leftist_heap">leftist heaps</a>. With these kinds of data structures, we basically present the finished product and possibly ask them to implement and/or analyze the data structure, but we never ask them to design something like that.</p>
<p>For several years, I've been trying to give students a taste of real data structure design, using the sample priority queue below. I usually do this in class, where I can help steer them with gentle questioning, but I try very hard to make sure that <i>they</i> come up with the important parts.</p>
<p>I always do this at some point after the students have studied <a href="http://en.wikipedia.org/wiki/Binary_heap">binary heaps</a> (the kind typically used in heapsort). I briefly review the priority queue operations binary heaps support (<tt>insert</tt>, <tt>findMin</tt>, and <tt>deleteMin</tt>) and the basic idea of heap-ordered trees. Then, I introduce the idea of <i>merging</i> two heaps. With binary heaps, this takes O(N) time, or even O(N log N) time, if done naively. I ask them to design a new data structure to support merging in O(log n) time, while the other priority queue operations run in the same bounds as for binary heaps, O(1) for <tt>findMin</tt> and O(log N) for <tt>insert</tt> and <tt>deleteMin</tt>. I suggest that they use heap-ordered binary trees (real trees, rather than simulating trees using arrays like in binary heaps), but that they can modify these trees in any way that is helpful.</p>
<p>With heap-ordered trees, <tt>findMin</tt> is trivial—it just returns the root. To get their creative juices flowing, I then ask them to implement <tt>insert</tt> and <tt>deleteMin</tt> in terms of <tt>merge</tt>. This is also pretty easy: <tt>insert</tt> creates a new singleton tree and calls <tt>merge</tt>; <tt>deleteMin</tt> discards the root and calls <tt>merge</tt> on the two children of the root. So the whole problem boils down to merging two trees efficiently.</p>
<p>At this point, they usually flounder for a while, which is both ok and expected. Some floundering is good. Naturally, they'll start to get a little frustrated. That, too, is ok and expected. I just don't want them to get frustrated to the point where they shut down. If the floundering continues too long without any progress, I'll ask them what they can tell immediately about the result tree by only looking at the roots of the input trees. They'll quickly reply that the smaller of the two input roots becomes the root of the result tree. So I have them draw that much of the result. Depending on how things are going, I may further suggest that they draw two question marks for the children of the root in the result tree.</p>
<p>Then the students will play for a while with how to fill in those question marks. There are two slots for subtrees, but we have three subtrees that need to go in those slots: the two subtrees of the “winning” input root plus the “losing” input root. To fit three subtrees into two slots, naturally we need to merge two of them and leave one unchanged. But which two should be merged?</p>
<p>Usually, the students will begin with some fixed strategy, such as always merge the two subtrees of the winning root. But it's easy to come up with counter-examples where such a strategy will take O(N) time.</p>
<p>Once it becomes clear that some smarter strategy is required, the students focus on the question of which two of the three subtrees to merge. Usually the next thing they try is merging the two subtrees with the smallest roots, which fails on the same kinds of counterexamples as before.</p>
<p>Eventually, based on the intuition that <tt>merge</tt> should run faster on small trees than on big trees, they try merging the two smallest trees. This is always a good learning point about ambiguity, as we realize that there are three different possible meanings of “smallest”: the smallest root according to the ordering on keys, the smallest subtree according to number of nodes, or the smallest subtree according to the height of the subtrees. We've already shot down the first one, but either of the other two will work, so I just go with whichever one the class prefers (usually smallest in number of nodes).</p>
<p>One catch is that to efficiently compare sizes of subtrees (either number of nodes or height), we need to store the sizes at every node. But that's easy to do by adding an extra field, and maintaining that size information is also easy, albeit slightly easier for number of nodes than for height.</p>
<p>Typically, we don't have a lot of time left in class at this point, so I help them with the analysis, but it's easy to show that this design supports <tt>merge</tt> in O(log N) time. And there was much rejoicing!</p>
<p>I call this data structure <i>maxiphobic heaps</i> because of the way <tt>merge</tt> avoids the biggest subtree at every step. But I don't tell the students that name until after they've already come up with the design.</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com8tag:blogger.com,1999:blog-2564777502681463717.post-13979386816689223142008-05-13T23:42:00.001-04:002008-05-13T23:42:45.373-04:00On Balanced Trees and Car Insurance<p>I usually don't teach our Data Structures course, but I often give a guest lecture about balanced binary search trees. This comes right after they've learned about plain (unbalanced) binary search trees. Often the previous lesson has ended with an illustration of what happens when values are inserted into the tree in sorted order.</p>
<p>After reviewing that pathological case and how it can easily arise in practice, I dive in and explain how to keep the trees balanced. In my case, I use red-black trees, but the exact choice of balancing scheme isn't critical to my point here. At the end of class, I ask them how much faster they think the balanced trees are than the unbalanced trees. They're shocked when I tell them that, most of the time, the balanced trees are <i>slower</i> than the unbalanced trees. As long as the data arrives in a reasonably random order, the plain binary search trees will actually end up being fairly balanced, without doing any extra work. No mucking around with colors, no rotations—of course the balanced trees are slower!</p>
<p>So why bother?</p>
<p>I tell them that it's like buying car insurance. When you buy car insurance, you hope that you're just throwing your money away. At the end of the year, if you haven't been in any accidents, you're happy to have wasted that money. Why bother? To protect against the uncommon case, to keep one unlucky event from turning into catastrophe. You pay a little bit extra all the time to keep from paying a <i>lot</i> extra every once in a while.</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com6tag:blogger.com,1999:blog-2564777502681463717.post-78808376082980637682008-05-09T10:21:00.001-04:002008-07-09T16:47:01.860-04:00Barriers to Creativity<p>Last week, I had lunch with some friends of mine, all college-level instructors. I brought up the subject of creativity, which has been <a href="http://okasaki.blogspot.com/2008/03/creativity.html">much on my mind lately</a>. Our discussion highlighted some of the barriers to creativity in education, especially from the side of the instructor.</p>
<h3>Creativity means artsy, doesn't it?</h3>
<p>At one point, I asked the chemistry professor in our group about the role of creativity in the first few college-level chemistry courses. She was confused by the question at first, because she thought I meant something like writing poems about chemical reactions. (That reminds me of a scene in <a href="http://en.wikipedia.org/wiki/Lois_McMaster_Bujold">Lois McMaster Bujold</a>'s <a href="http://www.amazon.com/Civil-Campaign-Lois-McMaster-Bujold/dp/0671578855">A Civil Campaign</a>, in which a biochemist decides to rewrite the abstract to his dissertation in sonnet form. “Can you think of a word to rhyme with <i>glyoxylate</i>?”)</p>
<p>Actually, I meant creativity in the sense of creative problem solving. You know, the kind of thing <a href="http://en.wikipedia.org/wiki/MacGyver">MacGyver</a> might do with 2 aspirins, a tube of superglue, and a Diet Coke. This misconception that creativity is the exclusive property of the arts is quite common. If we the instructors of techncial courses don't think of what we do as creative, then we are hardly likely to portray our discipline in a way that encourages creativity.</p>
<p>I'm using the word “arts” here to mean traditional arts like painting or poetry or music. I happen to think an elegant algorithm can be quite beautiful and artistic, but I don't expect a layperson to recognize it as art.</p>
<h3>Foundations, Foundations, Foundations</h3>
<p>A common theme in instructor comments was that students need to learn the foundations and basic skills of the discipline before they can do much that's creative. There's certainly some truth to this. But how long of an apprenticeship can we expect somebody to serve before finally exposing them to the beauty and wonder, the <i>fun</i> of the creative side? Do we save up all the creative parts for a senior-level capstone course (or even later), or can we intersperse skill development with appropriately-scaled opportunities to use those skills creatively?</p>
<p>A favorite movie of many teachers is <a href="http://en.wikipedia.org/wiki/The_Karate_Kid">The Karate Kid</a>, especially the part where Mr. Miyagi teaches Daniel karate by having him do household chores such as waxing cars or painting fences. Eventually Daniel rebels at what he sees as pointless menial labor, and Mr. Miyagi demonstrates that Daniel has been learning valuable defensive moves all along. The point teachers usually draw from this example is that students can learn valuable lessons without realizing that they are learning, but there's another point here as well. What if, instead of confronting Mr. Miyagi, Daniel simply quit coming to his lessons? That's the situation we face as college teachers. If we give students too much skills development up front without any hint of a payoff, they'll simply stop taking our courses and never come back.</p>
<p>There's another danger as well. I saw this among my fellow students in graduate school. Students who had spent their entire undergraduate careers very successfully learning foundations and practicing skills were often lost when they were finally expected to do creative research. It was completely different from what they were used to, and often they found that they didn't like it.</p>
<p>Think of a piano teacher who makes her students practice nothing but scales for four years. By the time she feels her students are finally ready to play real music, she may find that the only students she has left are the ones who would rather play scales than anything else.</p>
<h3>But...it's hard!</h3>
<p>Incorporating creativity into a college classroom can be hard, especially in large classes. The lecture format is particularly bad at nurturing creativity in the listeners, but a teacher facing several hundred students often has little choice.</p>
<p>Grading also becomes substantially more difficult if you design assignments that allow students room for creativity. Suddenly, there's no longer a single, “approved” solution that can be easily checked for. Instead, you need judgement to evaluate quite different solutions individually. This can be especially difficult in a course where TAs are expected to do most of the grading.</p>
<p>Fortunately, I suppose, I don't have large class sizes and I don't have any TAs, so I don't have those excuses to fall back on.</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com4tag:blogger.com,1999:blog-2564777502681463717.post-74754619714660790682008-05-02T14:29:00.000-04:002008-05-02T14:29:32.389-04:00Beware Pseudo-Arrays<p>I'm always fascinated by the kinds of programming mistakes that novices make, and what they say about that student's state of mind. I particularly enjoy mistakes that aren't really mistakes, in the sense that the student has actually gotten the code to work, but where the code clearly demostrates some flaw in that student's mental model of programming. For example, see my previous post on <a href="http://okasaki.blogspot.com/2008/02/boolean-confusion.html">Boolean confusion</a>.</p>
<p>Here's another example involving arrays, or rather the lack of them. I was reminded of this example just yesterday when multiple teams tried to use this idea in a local programming contest.</p>
<p>Suppose you are rolling some standard six-sided dice, and keeping track of how many times each number has appeared. The most natural way to do this would be to use an array indexed from 1-6. In a language with zero-based arrays, you might use indices 0-5 and subtract 1 from each die value, or you might use indices 0-6 and simply ignore index 0.</p>
<p>However, many novices faced with this decision will reject arrays altogether and use six separate variables, perhaps named <tt>count1</tt>, <tt>count2</tt>, <tt>count3</tt>, <tt>count4</tt>, <tt>count5</tt>, and <tt>count6</tt>. (Or, if they are really gluttons for punishment, <tt>ones</tt>, <tt>twos</tt>, <tt>threes</tt>, <tt>fours</tt>, <tt>fives</tt>, and <tt>sixes</tt>.) I call these kinds of variables <i>pseudo-arrays</i>.</p>
<p>Why use pseudo-arrays? Because real arrays are scary. Plain variables and if-statements are much friendlier! After all, why write
<pre>
count[dieValue]++;
</pre>
when you could write
<pre>
if (dieValue == 1) {
count1++;
}
else if (dieValue == 2) {
count2++;
}
else if (dieValue == 3) {
count3++;
}
else if (dieValue == 4) {
count4++;
}
else if (dieValue == 5) {
count5++;
}
else {
count6++;
}
</pre>
Oh, and don't bother suggesting a switch-statement — if-statements are good enough, thank you very much.</p>
<p>Why do so many novices do this? In many cases, I think it is because they were first exposed to if-statements, and found them easy, and then later were exposed to loops, and found them difficult. Arrays are usually processed using loops, and are usually introduced while the beginner is still reeling from the trauma of loops. Thus, arrays become tainted and suspect. In such a novice's mind, the approach with variables and if-statements truly is easier, especially because so many of the if-statements can be programmed using cut-and-paste — the favorite editing commands of most novice programmers!</p>
<p>Every once in a while, I see code by somebody who has gotten over their fear of loops, but has not yet become reconciled with arrays. This can lead to gems where the student tries to loop through a pseudo-array, as in
<pre>
for (int d = 1; d <= 6; d++) {
if (d == 1) {
System.out.println(count1);
}
else if (d == 2) {
System.out.println(count2);
}
else if (d == 3) {
System.out.println(count3);
}
else if (d == 4) {
System.out.println(count4);
}
else if (d == 5) {
System.out.println(count5);
}
else {
System.out.println(count6);
}
}
</pre>
As Dave Barry would say, I am not making this up.
</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com17tag:blogger.com,1999:blog-2564777502681463717.post-23420691816388916422008-04-17T08:41:00.000-04:002008-04-17T08:42:16.701-04:00Games for Programmers: Jotto<p><i>The next in an irregular series of board game recommendations for programmers. Of course, you don't have to be a programmer to enjoy these games, but if you are a programmer, then I think there's a pretty good chance that you'll like them.</i></p>
<p><i>However, you might not want to play this particular game with your spouse. Here's why...</i></p>
<p><b>“End. E-N-D”, she guessed. “One”, I replied.<br>
“Cab. C-A-B”, I guessed. “One”, she replied.</b></p>
<p>We were driving to a campground in Massachusetts. My wife and I were in the front seats of the minivan; our daughter was in the middle seat, watching a DVD; and our son and his friend were chatting in the back seat.</p>
<p>We had been on the road for several hours, and I was feeling a bit tired. I needed to do something to help keep me alert. “Jotto?”, I suggested to my wife. “Ok.“</p>
<p><b>“Icy. I-C-Y”, she guessed. “Zero”, I replied.<br>
“Fed. F-E-D”, I guessed. “One”, she replied.</b></p>
<p><a href="http://www.boardgamegeek.com/game/11821">Jotto</a> is a two-player deduction game, kind of like Mastermind but with words. In fairness, I should say that Mastermind is like Jotto but with colors, since Jotto is older than Mastermind.</p>
<p>Each player secretly chooses a five-letter word with no duplicate letters. The usual restrictions apply—no proper nouns, etc.</p>
<p>The players take turns guessing each other's words. For each guess, you tell the player how many letters were correct. Unlike Mastermind, it doesn't matter whether the letter is in the right position or not. For example, if you guessed BOARD and got one letter right, the answer might be PLAYS (the A matches, in the same place) but it could just as easily be GAMES (the A matches, not in the right place).</p>
<p><b>“Map. M-A-P”, she guessed. “One”, I replied.<br>
“Jig. J-I-G”, I guessed. “Zero”, she replied.</b></p>
<p>Jotto is a favorite game for situations where it would not be feasible to set up a board or deal out cards. For example, you can easily play it in a restaurant, or waiting in line, or on a long drive. All you need is two pencils and two pieces of paper.</p>
<p><b>“Age. A-G-E”, she guessed. “Two”, I replied.<br>
“Out. O-U-T”, I guessed. “Zero”, she replied.</b></p>
<p>In fact, you don't even need the pencil and paper! Most of the time, we play it in our heads with three-letter words instead of five. This is a great variation that allows the driver to play in the car. It also lets you play in situations where you are moving too much to be able to take notes comfortably, such as jogging or hiking.</p>
<p>For this game, I picked AXE as my word.</p>
<p><b>“Axe. A-X-E”, she guessed. “Got it. Dang that was fast!”, I replied.<br>
“Men. M-E-N”, I guessed. “One”, she replied.</b></p>
<p>I started playing Jotto this way with my son when he was 10. We still enjoy it and play it often, but it has become kind of a running joke, because we almost always finish within one guess of each other. This is the first time I have played mental Jotto with my wife, and she's killing me! She got it in five guesses, and I'm not even close!</p>
<p>Ok, with ones for both FED and MEN, I guess that it probably has an E. Next, I want to figure out which letter from CAB was correct. I'll try the A, and I'll also throw one of the other letters from FED to help confirm that it really was the E.</p>
<p><b>“Far. F-A-R”, I guessed. “One”, she replied.</b></p>
<p>Good. It probably really was the A. What has an E and an A?</p>
<p><b>“Sea. S-E-A”, I guessed. “Two”, she replied.</b></p>
<p>Now I'm getting somewhere. It looks like the E-A is correct. What else has an E-A?</p>
<p><b>“Pea. P-E-A”, I guessed. “Two”, she replied.</b></p>
<p>Hmm. I'm nearly certain now that the E-A are correct. What else has an E-A? It can't be TEA because I already got a zero for OUT. What if it's A-E instead of E-A?</p>
<p>Wait a minute. No way. No, she couldn't possibly have picked...</p>
<p><b>“Axe. A-X-E”, I guessed. “Got it”, she laughed.</b></p>
<p>Oh, man. We really have been married too long.</p>
<p><i>Originally written as a session report for <a href="http://www.boardgamegeek.com/">BoardGameGeek</a>.</i></p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com3tag:blogger.com,1999:blog-2564777502681463717.post-88441826760294497342008-04-14T10:50:00.000-04:002008-04-14T10:54:41.769-04:00Creativity<p>I recently stumbled across <a href="http://www.ted.com/index.php/talks/view/id/66">the TED video by Ken Robinson</a> (via <a href="http://gametheorist.blogspot.com/2008/03/its-funny-cause-its-true.html">Joshua Gans</a>). This video is almost two years old, so I'm getting to it rather late.</p><p>Robinson describes the increasing importance of creativity in the modern world, and bashes the education system for “educating people out of their creativity”. He contends that “creativity now is as important in education as literacy and we should treat it with the same status”. Robinson is an entertaining speaker, and I quite enjoyed his video. However, as I thought about it later, I become more dissatisfied.</p><p>I agree that creativity is important, and that the education system is doing a terrible job nurturing creativity. My problem with his talk is that he equates creativity with the arts: drawing, drama, dance, etc. I would hate to see some school administrator be inspired by the talk and attempt to “solve” the problem by simply adding an extra art class to the curriculum.</p><p>I'm not anti-arts. I'm not saying that art classes are bad. I am saying that giving students one art class in which to be creative, while systematically sucking the creativity out of them in every other class, is not going to solve the problem.</p><p>Instead, we need to recognize that other disciplines outside the arts also require creativity, and teach them that way. For example, mathematics is often taught in a way that brooks no creativity whatsoever, whereas the practice of actually doing real mathematics is highly creative. See <a href="http://www.maa.org/devlin/devlin_03_08.html">Paul Lockhart's essay</a> (<a href="http://www.maa.org/devlin/LockhartsLament.pdf">pdf</a>) for a wonderful discussion about creativity in mathematics education.</p><p>I think people often view technical subjects as having no place for creativity. You don't want a student getting creative when multiplying two numbers. I certainly don't want my programming students getting creative about <a href="http://okasaki.blogspot.com/2008/02/in-praise-of-mandatory-indentation-for.html">indentation</a>. In fact, in many technical subjects, the very word <i>creative</i> is often used as a synonym for <i>wrong</i> or <i>mistaken</i> (or sometimes <i>unethical</i>, as in “creative accounting”).</p><p>For example, I just said that you don't want a student getting creative when multiplying two numbers. But that's only because, in that context, “getting creative” would usually be interpreted as getting the wrong answer. In reality, I'd be thrilled if my grade-schooler, when faced with a multiplication problem like 37x999, rejected <a href="http://www.mathsisfun.com/numbers/multiplication-long.html">long multiplication</a> and instead said, “Hmm. 999 is almost 1000. 37x1000 is 37000. Then take away 37 to get 36963.” That's creativity!</p><p>Perhaps the biggest difference between creativity in the arts and in technical subjects has to do with constraints. In the arts, you tend to have fewer constraints, and those constraints are often flexible. In technical subjects, you tend to have more constraints, and those constraints are often non-negotiable. Think of the scene from <a href="http://www.imdb.com/title/tt0112384/">Apollo 13</a>: “We've got to find a way to make this...fit into the hole for this...using nothing but that.” Or the t-shirt about the speed of light that says “300,000 kilometers per second: It's not just a good idea, IT'S THE LAW!”</p><p>Common perception is that, the more constraints you have, the less creativity is involved. I don't think that's true. In fact, as Marissa Mayer of Google fame says, <a href="http://edcorner.stanford.edu/authorMaterialInfo.html?mid=1530&author=205">creativity loves constraints</a>. Of course, sometimes the creativity lies in figuring out which constraints are real, and which aren't.</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com9tag:blogger.com,1999:blog-2564777502681463717.post-21861329570977334112008-04-08T23:33:00.001-04:002008-04-08T23:36:04.889-04:00Immortality<p>Last week, I wrote about one of my more <a href="http://okasaki.blogspot.com/2008/04/spectacular-failure.html">spectacular failures</a>, which involved a progression that began 1, 2, 4, 8, 16, 32, but then rather than continuing sensibly as 64, 128, ..., instead exploded into 273, 65569, 4294967361, and 1.5x10<sup>82</sup>. The next term is a little over 2<sup>65569</sup> and the term after that a little over 2<sup>4294967361</sup>, which has about a <i>billion</i> digits when written out in full.</p>
<p>Joshua Zucker suggested that I submit this to the <a href="http://www.research.att.com/~njas/sequences/Seis.html">On-Line Encyclopedia of Integer Sequences</a>, which I did. So I've now been immortalized in Sequence <a href="http://www.research.att.com/~njas/sequences/A137181">A137181</a>. I can see my tombstone now: “He failed...BIG.”</p>
<p>Several years ago I was giving a guest lecture in a colleague's Algorithms class, when I encountered immortality of a different sort. The students were asking me about how I invented “Okasaki trees”, and were dumbfounded when I didn't know what they were talking about. How could I not know about Okasaki trees when I invented them? “Well,” I told them, “I've invented a lot of different <a href="http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html">data structures</a>, and most of them are trees of one kind or another. But I've never called any of them Okasaki trees.” After a bit more digging, it turned out that my colleague (who wasn't there that day) had been telling them the previous week about my simplification of red-black trees, and <i>he</i> called them Okasaki trees.</p>
<p>The lasting result of this is that I now have a friend at work who ribs me about Okasaki trees every chance she gets.</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com0tag:blogger.com,1999:blog-2564777502681463717.post-42255005538160814832008-04-04T00:18:00.001-04:002008-04-04T08:02:02.770-04:00A Spectacular Failure<p>About five years ago, a mathematical puzzle occurred to me. I eventually solved the puzzle, but I don't want to talk about that solution here. Instead, I want to talk about my <i>first</i> attempt at solving the puzzle, which was an utter failure. A glorious, spectacular failure. Perhaps the single most impressive failure of my career. Failures are often much more interesting than successes, but for some unfathomable reason, people are often reluctant to discuss them.</p>
<h3>The Puzzle and My “Solution”</h3>
<p><i>You don't need to understand the details of the puzzle to enjoy the failure, so if you're not familiar with <a href="http://en.wikipedia.org/wiki/SKI_combinator_calculus">SK combinators</a> and their ilk, or if you just can't be bothered, then please skip ahead to the <a href="#nextSection">next section.</a></i></p><p>I was playing around with SK combinators one day when a puzzle occurred to me. Could I introduce new combinators that would allow me to linearize any combinator expression? Combinator expressions are normally binary trees, and are written using parentheses to indicate the tree structure. The convention is that parentheses on the left can be omitted. For example, ((<i>w</i> <i>x</i>) <i>y</i>) <i>z</i> can be written as <i>w x y z</i>, but <i>w</i> (<i>x</i> (<i>y</i> <i>z</i>)) cannot be written without parentheses. I wondered if I could introduce new combinators that would allow me to rewrite any expression into an equivalent expression with no parentheses. I called such a transformation “flattening”.</p><p>One of the standard combinators in the SK family is B, which has the rewrite rule<center>B <i>f</i> <i>g</i> <i>x</i> = <i>f</i> (<i>g</i> <i>x</i>)</center>Reading this rule backwards works well for flattening small expressions—for example, <i>x</i> (<i>y</i> <i>z</i>) can be rewritten without parentheses as B <i>x</i> <i>y</i> <i>z</i>—but I ran into problems using it to flatten larger expressions, so I quickly turned to a variation of B that swaps the first two arguments
<center>R <i>f</i> <i>g</i> <i>x</i> = <i>g</i> (<i>f</i> <i>x</i>)</center> This new combinator works well for flattening expressions of the form <i>c</i> (<i>c</i><sub>1</sub> <i>c</i><sub>2</sub> ... <i>c</i><sub>N</sub>). For example,<pre> <i>c</i> (<i>c</i><sub>1</sub> <i>c</i><sub>2</sub> ... <i>c</i><sub>7</sub>)
= R (<i>c</i><sub>1</sub> <i>c</i><sub>2</sub> ... <i>c</i><sub>6</sub>) <i>c</i> <i>c</i><sub>7</sub>
= R (<i>c</i><sub>1</sub> <i>c</i><sub>2</sub> ... <i>c</i><sub>5</sub>) R <i>c</i><sub>6</sub> <i>c</i> <i>c</i><sub>7</sub>
= R (<i>c</i><sub>1</sub> <i>c</i><sub>2</sub> ... <i>c</i><sub>4</sub>) R <i>c</i><sub>5</sub> R <i>c</i><sub>6</sub> <i>c</i> <i>c</i><sub>7</sub>
...
= R <i>c</i><sub>1</sub> R <i>c</i><sub>2</sub> R <i>c</i><sub>3</sub> R <i>c</i><sub>4</sub> R <i>c</i><sub>5</sub> R <i>c</i><sub>6</sub> <i>c</i> <i>c</i><sub>7</sub>
</pre></p><p>Now, another combinator F works in conjunction with R to flatten more complicated expressions. F is defined as<center>F <i>f</i> <i>g</i> <i>x</i> <i>y</i> = <i>f</i> <i>x</i> (<i>g</i> <i>y</i>)</center> For example, we can now rewrite <i>c</i><sub>1</sub> <i>c</i><sub>2</sub> <i>c</i><sub>3</sub> (<i>d</i><sub>1</sub> <i>d</i><sub>2</sub> <i>d</i><sub>3</sub>)
as follows:<pre> <i>c</i><sub>1</sub> <i>c</i><sub>2</sub> <i>c</i><sub>3</sub> (<i>d</i><sub>1</sub> <i>d</i><sub>2</sub> <i>d</i><sub>3</sub>)
= F (<i>c</i><sub>1</sub> <i>c</i><sub>2</sub>) (<i>d</i><sub>1</sub> <i>d</i><sub>2</sub>) <i>c</i><sub>3</sub> <i>d</i><sub>3</sub>
= R <i>c</i><sub>1</sub> F <i>c</i><sub>2</sub> (<i>d</i><sub>1</sub> <i>d</i><sub>2</sub>) <i>c</i><sub>3</sub> <i>d</i><sub>3</sub>
= F (R <i>c</i><sub>1</sub> F) <i>d</i><sub>1</sub> <i>c</i><sub>2</sub> <i>d</i><sub>2</sub> <i>c</i><sub>3</sub> <i>d</i><sub>3</sub>
= R (R <i>c</i><sub>1</sub>) F F <i>d</i><sub>1</sub> <i>c</i><sub>2</sub> <i>d</i><sub>2</sub> <i>c</i><sub>3</sub> <i>d</i><sub>3</sub>
= R R R <i>c</i><sub>1</sub> F F <i>d</i><sub>1</sub> <i>c</i><sub>2</sub> <i>d</i><sub>2</sub> <i>c</i><sub>3</sub> <i>d</i><sub>3</sub>
</pre></p><p>The complete rules for flattening are
<ul>
<li> flatten(<i>c</i>) = <i>c</i> </li>
<li> flatten(<i>e</i> <i>c</i>) = flatten(<i>e</i>) <i>c</i> </li>
<li> flatten(<i>c1</i> (<i>e</i> <i>c2</i>)) = flatten(R <i>e</i> <i>c1</i> <i>c2</i>) </li>
<li> flatten(<i>e1</i> <i>c1</i> (<i>e2</i> <i>c2</i>)) = flatten(F <i>e1</i> <i>e2</i> <i>c1</i> <i>c2</i>) </li>
<li> flatten(<i>e1</i> <i>e2</i>) = flatten(flatten(<i>e1</i>) flatten(<i>e2</i>)) </li>
</ul>
where each <i>c</i> is a simple symbol and each <i>e</i> is an arbitrary expression.</p>
<h3><a name="nextSection"></a>Not So Fast</h3>
<p>I run my solution by hand on a few examples and it works great. So I code it up, run it on my examples and get the same answers. Yippee! Next, I run it on a larger example and.........nothing. The computer justs sits there, mocking me. Obviously, I've got a bug somewhere that is causing infinite recursion.</p><p>I stare at my program for awhile, but I'm not seeing any bugs. Hmmm. I run it on a different example and it finishes this time. I print out the result and...whoa, that's a lot of output! I wonder how big the transformed expressions are? Ok, calculating the size of the result shouldn't be too hard. I whip up another program and print out a table of the maximum output for an input of size N.
<pre> N=1 max output=1
2 2
3 4
4 8
5 16
6 32
.
.
.
.
</pre>
Quick! Guess the next value in the table! 64, right? RIGHT?!
<pre>
.
.
.
.
.
7 273
.
.
.
.
.
</pre>
Huh? 273? What the heck is that?
<pre>
.
.
.
.
.
8 65,569
.
.
.
.
.
</pre>
65,569?! You're joking, right?
<pre>
.
.
.
.
.
9 4,294,967,361
.
.
.
.
.
</pre>
4 billion? Well, that's just silly.
<pre> .
.
.
.
.
10 15,177,100,720,513,508,366,
558,296,147,058,741,458,143,
803,430,094,840,009,779,784,
451,085,189,728,165,691,939</pre>
<p>
What do you even say to a number like that? That's 1.5x10<sup>82</sup>. To put that in perspective, <a href="http://en.wikipedia.org/wiki/Observable_universe#Matter_content">the number of atoms in the observable universe</a> is estimated to be about 10<sup>80</sup>. No wonder my program was running slow! At a few billion operations a second, that calculation should only take about...um...carry the 3...dang, where's <a href="http://www.ted.com/index.php/talks/view/id/199">Art Benjamin</a> when you need him?...let's just say <i>a long time</i>.</p><p>If you're curious, here's the function that describes the size of the biggest possible output for an input of size N:
<ul>
<li>Biggest(N) = 2^(N-1), if N <= 6</li>
<li>Biggest(N) = 2^Biggest(N-3) + 2*Biggest(N-3) + 1, if N > 6</li>
</ul>
And here's the input of size 10 that gives the absurd result above:<center>X (X X) (X (X X) (X (X (X X))))</center>
</p><p>Once I recovered from the shock of this experience, I did eventually come up with a very nice solution to the puzzle, based on ideas from postfix languages like Forth and Postscript, but nothing quite compares with getting an answer like 1.5x10<sup>82</sup>.</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com2tag:blogger.com,1999:blog-2564777502681463717.post-21230909775814971092008-03-28T12:15:00.001-04:002008-03-28T12:16:11.064-04:00Wrong Number<p>Is it time to overhaul the user interface of the phone system?</p>
<p>A few months ago we started getting a lot of calls that were wrong numbers. Before that we used to get maybe one a week, but suddenly we were getting 5 or 6 a day. After an initial period of frustration, we eventually started to apply our debugging skills.</p>
<p>Our first guess was that somebody was distributing our phone number on a flyer or something, either as a prank or by accident. But this didn't make sense because every caller was asking for somebody different. “Hello, is Juan there?” “Hi, Elizabeth/Gary/Tanya/Carlos?” Or the ever popular “<<i>pause</i>> Who is this?!!” No, dude, you called me, so you tell first.</p>
<p>Ok, scratch that idea. Hmm, I suppose we could always ask. “Sorry, wrong number, what number are you trying to reach?” At last, some progress. Our phone number is 987-654-3210 (not our real number). The people who were calling us were uniformly dialing 654-321-0xxx. The 654 area code is for an area maybe 20 miles away, so <i>lots</i> of people in our area code were dialing numbers there. Even worse, there are up to 1000 numbers in that area code that match this pattern. No wonder we were getting a lot of calls!</p>
<p>The reason they were getting us was that they were forgetting to dial a 1 first. Without the 1, the phone system was interpreting this as a local call within the 987 area code to 654-3210, with the extra three digits on the end simply being ignored. On many (most?) cell phones the 1 is not necessary, so people lose the habit of dialing it. Then when they use a land line, where the 1 is required, they get us.</p>
<p>With this insight, we contacted the phone company. It took three tries and many patient explanations to even get somebody to understand what the problem was. I asked what had changed in the system recently, because clearly something had changed to cause the sudden increase in wrong numbers.</p> “Uh, I don't know. I'll ask our tech guy.” A few minutes later. “Our tech guy says the 321 exchange in the 654 area code is a Cingular exchange. You should call them.” “But how is that supposed to help? The phone calls are originating in your system and never getting out of your system, so even if they made a change over there, it wouldn't change what's happening here.” “Well, you should call Cingular.”</p>
<p>Predictably, Cingular couldn't help. They couldn't even tell us if the 321 exchange was new because “our computers don't tell us that”.</p>
<p>The really frustrating thing about the problem is that it's so easy to fix. It should be easy for the system to detect when somebody has dialed a 10 digits but is being connected to a 7-digit number. Give the caller a warning and ask them to redial! It's possible this might break some systems with extensions, where the leftover 3 digits indicate the extension. So perhaps disable the warning if there is a pause between the 7th and 8th digits.</p>
<p>Has anyone else had this problem?</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com6tag:blogger.com,1999:blog-2564777502681463717.post-11134635863867340012008-03-19T15:29:00.001-04:002008-03-19T15:34:10.566-04:00Program Testing For The Sake Of Learning<p>A number of years ago, I used to compete in the <a href="http://www.topcoder.com/tc">TopCoder</a> on-line programming contests. As an educator, I was fascinated by the TopCoder environment, less by the contests themselves than by the so-called <i>Practice Rooms</i>. These were archives of problems from old contests, where you could submit solutions and run them against the test data used in the actual contest.</p><p>I was amazed by how hard many people would work in the Practice Rooms. I wished I could get my students to work half that hard! At first, I thought these people were motivated by the idea of doing better in the contest. And, indeed, that was probably what got most of them to come to the Practice Rooms in the first place. But then I noticed that many of the people working hard in the Practice Rooms competed only rarely, if at all. Something else was going on.</p><p>Eventually, it dawned on me that the secret lay in the ease of running system tests. As teachers, we know that feedback is crucial to learning, and that quick feedback is better than slow feedback. These programmers were getting feedback within a few seconds, while they were still “in the moment”. The experience of this tight, nearly instantaneous feedback loop was so powerful that it kept them coming back for more. The burning question then was <i>could I re-create this experience in the classroom?</i></p><h3>Why test?</h3><p>Of course, program testing has been part of CS education forever. However, there are several different reasons for testing, and which reason or reasons the teacher has in mind will strongly affect how testing plays out in any particular class.</p><p>Here are several common reasons for testing:</p><p><b>Improved software quality.</b> Ironically, the number one reason for using testing in the real world is the least important reason to use it in the classroom. Most student programs, especially in early courses, will never be used for real. What matters in these programs is not that students complete the program correctly, but <a href="http://okasaki.blogspot.com/2008/03/get-job-done-but-what-is-job.html">what they learn</a> in the process.</p><p><b>Easier grading.</b> Grading programs can be hard, especially if you have a lot of students. Naturally, many CS educators seek to automate this process as much as possible. Many systems exist that will run student programs against a set of instructor tests and record the results. These results may used as a guide for human grading, or the results may entirely determine the student grade. When testing is performed as part of the grading process, it is common for the actual test cases to be hidden from the students.</p><p><b>To learn about testing.</b> Of course, testing is a vital part of real-world software development. Therefore, it is important to expose students to the testing process so they have some idea of how to do it. However, care must be taken here, especially in early courses. Hand-crafting good test cases is hard work. If students are forced to fight through a heavy-weight testing process on toy problems, including making up their own tests, the lesson they frequently take away is that testing is much more trouble than it's worth.</p><p><b>Testing as design.</b> In recent years, <i>test-first</i> and <i>test-driven</i> development have begun to spread from agile programming into the classroom. Advocates view such testing as part of the design process. By writing tests before writing code, students are forced to consider what the behavior of the program should be, rather than diving in without a clear idea of what the program is supposed to do.</p><h3>Another way</h3><p>All of these reasons are important, but none of them quite capture what I was seeing in the TopCoder practice rooms. There, people were becoming addicted to quick, easy-to-run tests as a powerful learning experience. This suggests viewing program testing as a way to improve learning. Not learning about testing, but learning about the content being tested.</p><p>In an attempt to re-create the relevant parts of the TopCoder experience in the classroom, I adopted the following process. With most programming assignments, I distribute some testing code and test cases. Students then run these tests while they are developing their programs, and they turn in their test results along with their code.</p><p>Note that this is an extremely lightweight process. All I'm doing is adding maybe 20 lines of test-driver code to the code I distribute for each assignment, and I can usually cut-and-paste that code from the previous assignment, with only a few tweaks. I then add maybe 50-100 test cases, either hardwired into the code or in a separate text file. I usually generate perhaps 5 of the tests by hand, and the rest randomly. Usually this process adds about 20-30 minutes to the time it takes me to develop an assignment.</p><p>I think CS teachers are often scared away by ideas like this because they imagine a fancy system with a server where students submit their programs, and the server runs the tests and records the results into a database. That all sounds like a lot of work, so teachers put it off until “next year”. In contrast, what I'm suggesting could probably be added without much hassle to an assignment that is going out <i>tomorrow</i>.</p><p>Similarly, teachers are sometimes scared away by the need to come up with the test suite, thinking it will take too much time to come up with a set of high-quality tests. But that's not what I'm doing. Experience has shown that large numbers of random tests work essentially as well as smaller numbers of hand-crafted tests, but at a fraction of the cost. (See, for example, the wonderful <a href="http://www.cs.chalmers.se/~rjmh/QuickCheck/">QuickCheck</a> testing tool.) Besides, I'm not trying to guarantee that my test suite will catch all possible bugs, which is a hopeless task anyway. Instead, I'm providing a low-cost test suite that is good enough to gain most of the benefits I'm looking for.</p><h3>Benefits</h3><p>And just what are those benefits? Well, since I started using this kind of testing in my homeworks, the general quality of submissions has gone up substantially. Partly, this is because of a drastic decrease in the number of submissions that are complete nonsense. When I did not require tests, students would write code that seemed correct to them at the time, and turn it in without testing it. Now, they can still turn in complete nonsense, but at least they'll know that they are doing so. Usually, however, when they see that they're failing every test, they'll go back and at least try to fix their code. In addition, many students who would have gotten the problem almost right without testing now get it completely right with testing.</p><p>Which leads me to the second benefit—there has been a noticeable improvement in the students' debugging skills. As one student put it, “<i>[The testers] also taught us how to troubleshoot our problems. Without those test cases, many of us would have turned in products that were not even close to complete. This would have meant for worse grades and harder grading for the instructor. We also would not have been able to use and develop our troubleshooting skills. When we don't know that something is wrong, it is very hard to try to test for the failures.</i>”</p><p>However, the main benefit is that the students are learning more. They are getting needed feedback while they are still “in the moment”, and can immediately apply that feedback, which is all great for learning. Contrast this, for example, to feedback that is received after an assignment has been turned in. Often such feedback comes days or weeks later. Students often don't even look at such feedback, but even if they do, they have often lost the context that would allow them to incorporate the feedback into their learning. Even with an automated system that gives feedback instantly, if students do not have an opportunity to resubmit, then they will usually not bother to apply the feedback, and so will miss out on a substantial portion of the benefit to their learning.</p><p>As another student put it, “<i>The automated testers are much more than just a means of checking the block to ensure the program works. They function almost as an instructor themselves, correcting the student when he or she makes a mistake, and reaffirming the student's success when he or she succeeds. Late at night, several hours before the assignment is due, this pseudo-instructor is a welcome substitute.</i>”</p><h3>Grading</h3><p>I have the students turn in the results of their testing, which makes grading significantly easier. Failed tests give me clues about where to look in their programs, while passed tests tell me that I can focus more on issues such as style or efficiency than on correctness.</p><p>But this is merely a fringe benefit. Note that I only use the test results to help guide my grading, not to determine grades automatically. I worry that when grading becomes the primary goal of testing, it can interfere with the learning that is my primary goal. For example, testing when used for grading often breaks the tight feedback loop that is where my students learn the most.</p><p>Also, when testing is used for grading, the instructor's test suite is often kept hidden from the students. In contrast, I can make my test suites public, which saves me all kinds of headaches. I'm not worried that a student might hardcode all the test cases into their code just to pass all the tests, because I'll see that when I look at their code. (In fact, this happens about once a year.) Students like having the test cases public because, if they don't understand something in the problem statement, they can often answer their own questions by looking at the test cases.</p><p>Admittedly, sometimes students take this too far. I occasionally catch them poring over the test cases like trying to read tea leaves, instead of coming to ask me a 30-second question.</p><h3>Crawl-Walk-Run</h3><p>I am not advocating that this approach to testing should be used everywhere in the curriculum. Among other things, I agree that students should have the experience of creating their own test cases. The question is when.</p><p>I see my approach as being most useful in beginning programming courses, and in courses that are not nominally about programming. For example, it works particularly well in Algorithms.</p><p>In other programming courses, however, I believe that a crawl-walk-run approach is appropriate. The “crawl” step is about attitude rather than skills; it is to convince students that testing is valuable. I believe my approach does this, especially if you occasionally leave out the tests and explicitly ask students to compare the experiences of developing with or without tests.</p><p>The “walk” step might be to have students generate their own tests, but using instructor-supplied scaffolding. The “run” step might be to have students generate both the tests and the scaffolding. I admit, however, that I have not taught the courses in which those steps would be most appopriate.</p>Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.com8