tag:blogger.com,1999:blog-11981373029210756752024-03-04T21:39:35.262-08:00Computroniumderiving art from logicLaikahttp://www.blogger.com/profile/16165304577490923507noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-1198137302921075675.post-83912637988262348952008-06-18T05:35:00.000-07:002008-06-18T05:39:30.827-07:00Axon, axoff<p><img style="float:left; border-style:none;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjAZWU6FSkNn6MkZ5x58qT1ht2dmg_29NY37THPYTOcXIvvq1e4QbXFIzrcAAyb8CHSx41jCN45UxQHCQrywQC5AKOuFFyp9e7x_mfHGy_Qp3zEJxZsaLed33OqyhnOpow28SagfEVfdQ/s320/f.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5213199262678922914" />riend of mine poses an interesting question <a href="http://jimnauseam.blogspot.com/2007/07/i-heart-dendrites.html">on his blog</a>:</p><br /><p><i><br /><br /><blockquote>n most of the equipment I work with, the sensors (RTD’s - heat sensors that tell the controller the temperature of something, photocells – proximity sensors that sense when the product, ie., a box, is passing a certain point on a conveyor, limit switches – simple mechanical open/close switches that would tell the controller a safety door was open or a button was being pushed) each typically communicate with the controller through it’s own pair of wires that go from the sensor to an input/output board in the controller. You can end up with a lot of wires.</p><br /><p>Now there are systems that use control networks and “smart sensors” that not only send the information for which it exists (“115 ohms meaning 350 degrees F”, “I sense a box!”, or “button pushed”) but also a packet of info identifying the sensor. This way, you can run all this information through a single cable instead of hundreds of wire pairs.</p><br /><p>My question is… in which way does the human body work? The first (dumb open/close switches) or the second (smart sensors)? </p></blockquote><br /><p></i></p><br /><br /><p>His guess that it’s the second option (his initial guess at least). My guess was the first. Wikipedia talks of <a href="http://en.wikipedia.org/wiki/Nerve_cells">nerve cells</a> but I can’t seem to find a smoking gun. Opinions?<br /></p>Laikahttp://www.blogger.com/profile/16165304577490923507noreply@blogger.com1tag:blogger.com,1999:blog-1198137302921075675.post-39741560329525011012008-06-18T05:27:00.000-07:002008-06-18T05:35:14.265-07:00"May I ask you, inquired the elevator in its sweetest, most reasonable voice, if you've considered all the possibilities that down might offer you?"<p><img style="float:left; border-style:none;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhvWhuRt4PwAi7rtgGSJU8-YRwwyN9uqPGbtPNAwQ7J7TJ4XVPZ7iVT6xca-uBRY9qOND_Jy3-Oexthq6Vi4LpViTl2btZJYJwGl581UBJHnZNekbUTLdHyeEG8aecqvh985P_BbCL6Gw/s320/e.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5213197430164354402" />levators are fascinating things. I say that despite being trapped in one for forty-five minutes last week (no lie — myself and five other strangers found ourselves stuck 14 floors up, making nervous jokes during a rush hour malfunction).</p><br /><p>What I often ponder is the <b>ideal algorithm for running one</b>, or more critically, a set of elevators. Poking around I’ve found that my initial hunch was correct — there’s what’s referred to as the <a href="http://en.wikipedia.org/wiki/Elevator_algorithm">elevator algorithm</a> that dictates that an elevator will move in its current direction, stopping only to let people on or off, until it has no more calls in that direction.</p><br /><br /><p>At that point it can either sit there and wait (which is probably more energy and cost efficient) or try to go to a more useful floor (the lobby when people are expected to arrive, or the top floor when they’re expected to leave).</p><br /><p><b>Some other interesting factoids:</b></p><br /><ul><br /><li>The elevator algorithm is also used for <a href="http://en.wikipedia.org/wiki/Elevator_algorithm">hard disk access</a>, to optimize the motion of the arm when dealing with read/write requests.<br /><li>In areas where there are a lot of Jews, you will often find <a href="http://en.wikipedia.org/wiki/Sabbath_elevator">Sabbath elevators</a>, which operate in accordance with some Orthodox and conservative rabbinic prohibitions. Wild!<br /><li>Some modern elevators (including, apparently, the one in the Adelaide office of my company) require users to select their desired floor from a central console. They are then told which numbered elevator to get on. Inside the elevator, there are no buttons to push. This is apparently much more efficient but has some human-factors drawbacks:<br /><ul><br /><li>The console doesn’t recognize when a group of people is too large to fit in a single elevator.</li><br /><li>A single person requesting an elevator multiple times might end up with multiple elevators dispatched to retrieve her/him.</li><br /><li>People not knowing the system often get on an elevator and end up being taken for a ride!</li><br /></ul><br /></ul><br /><p>What other heuristics could you use if you had to program a set of elevators?</p><br /><p>Another thing to ponder: how could you determine the finer points of the algorithm used in a given office building, just by calling and riding the elevators? It would seem to require an accomplice at the very least.</p>Laikahttp://www.blogger.com/profile/16165304577490923507noreply@blogger.com0tag:blogger.com,1999:blog-1198137302921075675.post-1448268577285196902008-06-18T05:19:00.000-07:002008-06-18T05:27:08.483-07:00Unconventional solutions to computer miscreants<p><img style="float:left; border-style:none;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhfJIW7rN4rFZlvLCK5sA-w16aYdvnSrwHEswt5vB_rgqOe_ehcDesli1IMF_i2K3ChxY846DzQoLehuY3Al71zdUxC89FgIZL8NgZJo_sPi1Zi7Ailyva2w3Oo-TPbmnEUfLh21Wb2ZQ/s320/d.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5213195882630777298" />ecades ago, the writers of an early “shared” operating system known as the <a href="http://en.wikipedia.org/wiki/Incompatible_Timesharing_System">Incompatible Timesharing System</a> or ITS got so fed up with people deliberately trying to find ways to crash the system that they came up with a novel solution — a <b>KILL SYSTEM</b> command that anyone could run that would crash the system (presumably to take all the fun and challenge out of it). I love that. While it’s hard to imagine such a feature being implemented in a modern operating system, I believe the spirit of the idea might still be usable in other contexts.</p><br /><br /><p>Pretty much every single online gaming website I’ve seen has a problem with people running <b>cheats</b> — computer programs that stand in for the human and respond with uncanny precision or speed. I know <a href="http://en.wikipedia.org/wiki/First-person_shooter">FPS</a> games have a large problem with cheaters who can fire with with deadly aim (among other tricks), but my own experience is with more basic games. I used to spend a lot of time on online versions of the word game <a href="http://en.wikipedia.org/wiki/Boggle">Boggle</a>, including PlaySite’s Tangleword (which is now <a href="http://www.iwin.com/download/2/boggle-game">IWin’s Boggle</a>) and <a href="http://games.yahoo.com/play/ww&ss=1">Yahoo’s Word Racer</a>. Cheaters were a rampant, recurring, and frustrating problem. People would write programs that generated all the words for a given board from a dictionary, and would achieve phenomenal scores as a result, much to the chagrin of everyone trying to win on brainpower alone. Writing such a program is not difficult (I know, because I wrote one; I never used it to win, except against other cheaters), but these people were difficult if not impossible to discourage. Might the solution be to <b>allow anyone a “super-user” account that always wins</b>? I’d love to see the experiment done.</p><br /><br /><p>I recently worked on a major redesign of a website for a major maker of tourist guidebooks. They had just fully embraced the idea of letting users supply content across many different areas of the site, but in every case we had to seriously consider the possibility of malicious uploads, largely because of <b>one pathological individual</b> who had been carrying out a vendetta against the company for the last <i>decade</i>. On every public forum on their old site he took every opportunity to add comments that were embarrassing, confusing, malicious, or disgusting. He would create new accounts as soon as his old ones were banned, often several times in the same day. (The solution we implemented for the site redesign was that uploads everywhere had to be approved of by a moderator.)</p><br /><br /><p>I got to wondering, what if instead of banning such an individual, his account got tagged in such a way that he could still view his postings, but no one else could? Presumably he might never know that his account was so tagged, and would continue to waste his energies devising his malicious missives when in fact his words would be reaching <b>nobody</b>. It would be activated when either he is logged in, or a <a href="http://en.wikipedia.org/wiki/HTTP_cookie">cookie</a> is set on his machine (presuming he doesn’t disallow them; most forums require you to allow). I’m sure the most persistent people would eventually catch on, and resort to logging out and removing the cookie, or checking from another machine to see if their posts were actually getting through, but at the very least it would increase the burden on these lowlifes.</p><br /><br /><p>This idea might work with the problem of cheaters on some gaming sites too. If their account gets tagged, they can still “log in”, but <b>no one would see their scores but them</b>. I’ve found that such cheaters actually <b>thrive</b> on the outraged comments they generate, but I could never convince other players to just ignore them in the comment areas. When such a “secretly blacklisted” tag is set by a moderator, no one would see the cheater’s comments either, though he would see theirs. To the cheater, it would just seem like they were being ignored. It would be trickier for FPS-type games; when the cheater kills someone, the server would have to pretend (to the cheater’s client machine) that the person’s avatar had died, and send no more updates as to that person’s whereabouts. Some situations wouldn’t be fakable but I bet you could fool a lot of the cheaters for much of the time. It would be the ultimate <a href="http://en.wikipedia.org/wiki/Pwn">pwn</a>.</p><br /><br /><p>Could spam be dealt with similarly? I’ve always wished there was as option in email programs that allowed you to <b>respond as if your account didn’t exist</b>. That is, send the exact response to the sender that the mail server on your host would send if there was no such login on that host. I’m not fully sure if this could work, though; is the check for whether an account exists done during the initial handshake between sender and receiver, or at some later point?<br /></p>Laikahttp://www.blogger.com/profile/16165304577490923507noreply@blogger.com0tag:blogger.com,1999:blog-1198137302921075675.post-72883839596200632232008-01-27T21:00:00.000-08:002008-01-29T03:45:54.156-08:00Really big numbers. And I mean, REALLY big.<p><img style="float:left; border-style:none;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgLes2NPKD1lPlVV4uAw98codl8Xzyf0W6MR6H6XyaWMNlzdrn3TgS6ksbWnptdpBLEKGV1vZW2r9oDu1IIBQzgNkowps8DjQYghVVbbhMpOgX34AVlvCNS-CGHvZjpWwT2VhA-HVCKVw/s320/c.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5160853759190602210" />onsider a favorite song of mine, Built To Spill’s “Randy Describe Eternity”:<br /><br /><object classid="clsid:d27cdb6e-ae6d-11cf-96b8-444553540000" codebase="http://fpdownload.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=7,0,0,0" allownetworking="internal" height="13" width="13"><br /><br /><param name="wmode" value="transparent"><br /><param name="allowScriptAccess" value="sameDomain"><br /><param name="FlashVars" value="resourceID=1078257&flp=false"><br /><param name="movie" value="http://static.last.fm/webclient/inline/1/inlinePlayer.swf"><br /><param name="quality" value="high"><br /><param name="bgcolor" value="#ffffff"><embed wmode="transparent" src="http://static.last.fm/webclient/inline/1/inlinePlayer.swf" quality="high" flashvars="resourceID=1078257&flp=false" bgcolor="#ffffff" name="inlinePlayer" allownetworking="internal" allowscriptaccess="sameDomain" type="application/x-shockwave-flash" pluginspage="http://www.macromedia.com/go/getflashplayer" height="13" width="13"></embed> </object> <a href="http://www.blogger.com/music/Built+to+Spill">Built to Spill</a> – <a href="http://www.blogger.com/music/Built+to+Spill/_/Randy+Described+Eternity">Randy Described Eternity</a></p><br /><br /><p>The song asks you to imagine a very large number by means of an analogy. The full lyrics go like this:<a id="more-6"></a></p><br /><blockquote><p><br />every thousand years<br /><br />this metal sphere<br /><br />ten times the size of Jupiter<br /><br />floats just a few yards past the earth<br /><br />you climb on your roof<br /><br />and take a swipe at it<br /><br />with a single feather<br /><br />hit it once every thousand years<br /><br />`til you’ve worn it down<br /><br />to the size of a pea<br /><br />yeah I’d say that’s a long time<br /><br />but it’s only half a blink<br /><br />in the place you’re gonna be<br /><br />where you gonna be<br /><br />where will you spend eternity<br /><br />I’m gonna be perfect from now on<br /><br />I’m gonna be perfect starting now<br /><br />stop making that sound<br /><br />stop making that sound<br /><br />I will say I forgot<br /><br />but it was only yesterday<br /><br />and it’s all you had to say<br /></p></blockquote><br /><p>Despite the technical difficulties of having a metal sphere that large pass that close to the Earth, it’s a cool metaphor. So how long of a time are we talking about here? Let’s come up with an estimate.</p><br /><p>First consider how much a swipe of a feather would remove from the sphere. Let’s take a guess and say that 100 swipes would remove a square millimeter. (That’s being conservative, I think; could you really complete dissolve a grain of sand by brushing it a hundred times with a feather?)</p><br /><p>Now consider the size of the sphere, “ten times the size of Jupiter”. Let’s assume they mean ten times the <i>volume</i>, which would be 10 × <a href="http://en.wikipedia.org/wiki/Jupiter">1.43128 × 10<sup>15</sup> km³</a>, or 1.43128×10<sup>16</sup> km³, which in cubic millimeters is 1.43128 × 10<sup>34</sup> mm³. The “size of a pea” amount left over is incidental.</p><br /><br /><p>So if we just multiple that figure by 100 (feather swipes) times 1000 years, and we get <b>1.43128 × 10<sup>39</sup> years</b>. Let’s call this <b>Randy’s number</b>. Is it older than the current age of the universe? Yes, by a long shot. The universe is only about <a href="http://en.wikipedia.org/wiki/Age_of_the_universe">1.37 × 10<sup>10</sup> years</a>; Randy’s number is 100 000 000 000 000 000 000 000 000 000 times larger. <b>Yeah, I’d say that’s a long time.</b></p><br /><br /><p>Clifford Pickover’s <a href="http://www.amazon.com/Mazes-Mind-Unexpected-Clifford-Pickover/dp/0312103530/ref=pd_bbs_sr_1/102-1270487-1312963?ie=UTF8&s=books&qid=1186803611&sr=8-1">Mazes For The Mind</a> mentions a few other large (estimated) numbers:</p><br /><ul><br /><li>The <i>talking number</i> — the total number of words spoken by humans since the dawn of history: 10<sup>16</sup></li><br /><li>The <i>Coney Island number</i> — the total number of grains of sand on the beach at Coney Island: 10<sup>20</sup></li><br /><br /><li>The <i>ice age number</i> — the total number of ice crystals necessary to form the ice age: 10<sup>30</sup></li><br /></ul><br /><p>Douglas Hoftstadter in <a href="http://www.amazon.com/Metamagical-Themas-Questing-Essence-Pattern/dp/0465045669/ref=pd_bbs_sr_1/102-1270487-1312963?ie=UTF8&s=books&qid=1186804099&sr=1-1">Metamagical Themas</a> mentions a few others:</p><br /><ul><br /><li>The <i>Hemoglobin number</i> — the number of hemoglobin molecules in the human body: 6 x 10<sup>21</sup></li><br /><br /><li><i>Rubik’s constant</i> — the number of possible configurations of a Rubik’s cube: 4.3 x 10<sup>19</sup></li><br /></ul><br /><p>Huge numbers, to be sure. Larger still is the infamous <a href="http://en.wikipedia.org/wiki/Googol">googol</a>, which is 10<sup>100</sup>. Now consider the <a href="http://en.wikipedia.org/wiki/Googolplex">googolplex</a>, which is 10<sup>googol</sup>. It is said that such a number could never be written down, as it would require more space than is available in the known universe.</p><br /><br /><p>But even these numbers are peanuts compared to some other numbers which have been envisioned. Consider <a href="http://en.wikipedia.org/wiki/Tetration">tetration</a>, <a href="http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation">Knuth’s up-arrow notation</a>, <a href="http://en.wikipedia.org/wiki/Steinhaus-Moser_notation">Steinhaus-Moser notation</a>, or <a href="http://en.wikipedia.org/wiki/Conway_chained_arrow_notation">Conway’s chained arrow notation</a>.</p><br /><p>Finally, just to fry your brain a little more, consider a number proposed in the excellent web comic <a href="http://www.xkcd.com/">XKCD</a>, in his strip <a href="http://www.xkcd.com/207/">What XKCD Means”:</a></p><br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiXGwpvjIRXRVuI8ShsA-5P5GnCWITw573dXaKxI5mygRxsGtxcieTRjmOf9qhJ1e9trrO2Qd6EpyZxJhSpZ0vuVOtMsPnkgBLJWS2F_ljsz6rqqqeqcvN5hLMOQgFadvnJ51fsh16A6A/s1600-h/xkcd.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiXGwpvjIRXRVuI8ShsA-5P5GnCWITw573dXaKxI5mygRxsGtxcieTRjmOf9qhJ1e9trrO2Qd6EpyZxJhSpZ0vuVOtMsPnkgBLJWS2F_ljsz6rqqqeqcvN5hLMOQgFadvnJ51fsh16A6A/s320/xkcd.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5160862628298068482" /></a><br /><br /><p>The <a href="http://en.wikipedia.org/wiki/Ackerman_function">Ackermann function</a> with <a href="http://en.wikipedia.org/wiki/Graham%27s_number">Graham’s number</a> as its arguments is a number orders of magnitude larger than we can imagine. Actually, you can hardly say it’s “orders of magnitude” larger since that only implies exponentially larger; this number goes way, way, <i>way</i> beyond that!</p><br /><br /><p>But it’s still finite. And if you divide it by infinity, <b>you still get zero</b>. That kills me.<br /></p>Laikahttp://www.blogger.com/profile/16165304577490923507noreply@blogger.com0tag:blogger.com,1999:blog-1198137302921075675.post-14708045075802811872008-01-27T20:59:00.000-08:002008-01-29T03:55:43.246-08:00Quick and Dirty 3-D Rendering<p><img style="float:left; border-style:none;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgua-3MFmncPwnEvtPByv1IUqlru08fYhCXit1e3AGLqZJP5dAwtfgzXpKrMsFGtgwtPjJ59LRCa0hS-Ashlv88wJzqoQKp8r6yetP19sPKf03gglMGuN101vzGB8a5k5BKnSc6fB6cvg/s320/b.png" border="0" alt="B" />y using a handy shortcut, you can <strong>render 3D objects painlessly</strong>.</p><br /><p>Usually this is done using <a href="http://en.wikipedia.org/wiki/Transformation_matrix">transformation matrices</a>. This sort of matrix manipulation was actually discovered back in the 18th century, but like many great mathematical discoveries, had no real practical application. Until the modern era, that is, when someone discovered that this trick was perfect for rendering 3D graphics. It lets you rotate, scale, shear, etc. any image, and the really nice thing is that once you decide all the transformations you want, you can reduce them to a single matrix and so compute the positions of everything you want to draw rather quickly.</p><br /><p>But unless you live and breathe the stuff, it’s <strong>too complicated</strong> to remember how to set it up off the top of your head, and a lot of code even if you know how. So here’s a tip that will get you rendering 3D objects in no time.<a id="more-4"></a></p><br /><br /><p>First, draw yourself a set of axises, like so:</p><br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhhxPUkE9gK0UDJPSXg0A7apna202hAxj8rd-HPLuQMC7TF4M7uopRtY4YrY_z4wOgfgdd2kgTko9-lkHLL7RdVUY0vAUH2xobT7dzc16Xn9j-VrMXBkHbqdbQKEXJvuUQMsmj8EqfSNQ/s1600-h/axis.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhhxPUkE9gK0UDJPSXg0A7apna202hAxj8rd-HPLuQMC7TF4M7uopRtY4YrY_z4wOgfgdd2kgTko9-lkHLL7RdVUY0vAUH2xobT7dzc16Xn9j-VrMXBkHbqdbQKEXJvuUQMsmj8EqfSNQ/s320/axis.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5160857074905354738" /></a><br /><br /><p>It doesn’t have to be very accurate, just so as it looks fairly proportional. Now, imagine that each of the arrows is one unit long. You need to write functions that return x and y for a given (x,y,z) point. So ask yourself — for each unit of x, how much do we actually move horizontally? How about for each unit of y? For each unit of z, we don’t move horizontally at all, but for the other two, you can make a guess. Let’s say the tip of the x axis is 16 pixels to the right of the origin, and the tip of the y is 20. Again, accuracy isn’t important, as long as you’re in the ballpark and the numbers are proportional. Since you want it to appear in the center, add an offset that’s half the width of the screen. So your method for determining the screen x coordinate of your point will look something like this:</p><br /><pre><code><br />private int getX( Point p )<br />{<br /> return CENTER_X + p.x*16 + p.y*20 + p.z*0;<br />}<br /></code></pre><br /><p>Obviously, the p.z*0 could have been left out, but I leave it there for illustration.</p><br /><p>Similarly, the screen y coordinate can be determined just by guessing the offset of the tips of the x, y, and z axises on our sketch. Looks like about -10, 5, and -20 respectively (remember y coordinates count down from the top in most computer graphics systems). So our function for determining the screen y of your point will look like this:<br /></p><br /><pre><code><br />private int getY( Point p )<br />{<br /> return CENTER_Y + p.x*-10 + p.y*5 + p.z*-20;<br />}<br /></code></pre><br /><p>Let’s see it in action. Here’s an applet that defines a few lines in terms of their 3D endpoints, and then draws them on our 2D screen using the methods described above. Specifically, it defines all the lines necessary to draw the cube that stretches from -1 to 1 on each axis. Give it a click to run it:</p><br /><p><applet code="org.computronium.three_d.ThreeDRenderer" archive="http://www.computronium.org/blog/applet/threed.jar" width="300" height="200"><br /><br />Enable Java in your browser to see it.<br /><br /></applet><br /><br />(Java source for main class <a href="http://www.computronium.org/blog/code/java/org/computronium/three_d/">here</a>. Parent applet <a href="http://www.computronium.org/blog/code/java/org/computronium/applet/">here</a>.)</p><br /><p>Not bad, huh? It’s handy for quick visualizations, and you’ll probably see it again here before long.<br /><br /></p>Laikahttp://www.blogger.com/profile/16165304577490923507noreply@blogger.com0tag:blogger.com,1999:blog-1198137302921075675.post-46053361581899053592008-01-27T20:58:00.000-08:002008-01-29T03:56:16.483-08:00Towers of Hanoi<p><img style="border-style:none" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjEVEg3wIW9bLTG26vRKNORBXJ0HhrvKrfgz3VraCp5t-IVA4SCzByYxZEdjBb1cmAduQT2TCyPXmqKhyphenhyphen6PcCeoVxEjTousIUA1Teu665yIt_C8nHYMxSi8Va13RaVut8unvmCx9wunQg/s320/a.png" border="0" alt="A" />ny discussion of beauty in programming must necessarily begin with <strong>recursion </strong>in general, and the <strong>Towers of Hanoi</strong> in particular. This will be review for anyone who’s studied computer science, but that’s okay since I won’t have many readers at this point anyway.</p><br /><br /><p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgMYmhTHaxiEVFrF1BVUFw4I3gYlyBqoF_fOByCaoFmegu6YUiivnxITsujGsPyfMwbtq8jTBvAqM5T8oE1gaxavTdtIHd6W5jb47zDMqFX2S7OJjOEruHTmyG5jz1yvaRM9Q2YXh1ueQ/s1600-h/hanoi.jpg"><img style="cursor:pointer; cursor:hand;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgMYmhTHaxiEVFrF1BVUFw4I3gYlyBqoF_fOByCaoFmegu6YUiivnxITsujGsPyfMwbtq8jTBvAqM5T8oE1gaxavTdtIHd6W5jb47zDMqFX2S7OJjOEruHTmyG5jz1yvaRM9Q2YXh1ueQ/s320/hanoi.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5160851787800613330" /></a><br /><br />The Towers of Hanoi is a puzzle of simple construction but fascinating complexity. It consists of three pegs. To start with, on one of the pegs is a number of disks, stacked from largest to smallest. The object is to move the stack of disks to one of the other pegs, with the restrictions that you can only move one disk at a time, and a disk may never be placed on a disk that’s smaller than it.<a id="more-3"></a></p><br /><br /><p>There’s a beautiful computer algorithm to solve it, and that I want to talk about. But the Towers of Hanoi was <a href="http://www.amazon.com/7884-Tower-of-Hanoi/dp/B000RWEWBO/ref=sr_1_2/104-6244336-9923947?ie=UTF8&s=toys-and-games&qid=1184682252&sr=8-2">a toy</a> long before there were computers. So first, <a href="http://www.mazeworks.com/hanoi/index.htm">have a play</a> at solving it by yourself. Increase the number of disks if you find it too easy to start with. Most people, when they first start playing with it, end up moving disks pretty much randomly at the start. After a point you may find yourself making small goals, like “Okay, I need to get these smallest three disks over to this peg, so I can move the next biggest disk…” Eventually you realize that, if you’re starting with, say, six disks, you’re going to have to move five of them out of the way (onto the extra peg), then move the sixth and largest disk to the target peg, then move the first five on top of it.</p><br /><p>So let’s look at the actual program that solves it. The number of disks has been made a parameter so we can eventually solve it for any number of disks. I’ll add comments to make it exceedingly clear what’s going on.</p><br /><pre><code><br /> private static void hanoi( int numberOfPegs, String fromPeg,<br /> String targetPeg, String otherPeg )<br /> {<br /> // First, move all but the largest disk to the extra peg.<br /> if (numberOfPegs > 1)<br /> {<br /> hanoi( /* move */ numberOfPegs-1, /* pegs */<br /> /* from the */ fromPeg,<br /> /* to the */ otherPeg,<br /> /* via the */ targetPeg);<br /> }<br /><br /> // Next, move the largest disk to the target page. We'll just print <br /> // out the move we're making.<br /> System.out.println("Move a disk from " + fromPeg + " to " + targetPeg);<br /><br /> // Lastly, move the disks that we moved out of the way on top of <br /> // the largest disk.<br /> if (numberOfPegs > 1)<br /> {<br /> hanoi( /* move */ numberOfPegs-1, /* pegs */<br /> /* from the */ otherPeg,<br /> /* to the */ targetPeg,<br /> /* via the */ fromPeg);<br /> }<br /> }<br /></code></pre><br /><br /><p>We’ve had to add the extra peg as the last parameter, just to keep track of it. But notice how similar it is to the original plan, of moving all but the largest disk out of the way, then moving the largest disk, then moving all the remaining disks on top of it. But as an algorithm it looks like it only sketches the broad plan. It just doesn’t look complex enough to solve that first step — moving all but the largest disk out of the way — not to mention he third step, which is just as complex. But miraculously, it works! Try running <a href="http://www.computronium.org/blog/code/java/org/computronium/hanoi/">the code</a> yourself. <strong>How could it possibly do all those intermediate steps?</strong></p><br /><br /><p>It turns out that the problem of how to move n-1 disks from the “from” peg to the “other” peg is just a smaller, simpler version of the problem of moving n disks from the “from” peg to the “target” peg. It’s just that we’re now using the “extra” peg as our target peg, and the target peg as the extra peg. So this method will just be solving the problem for smaller and smaller versions of the problem, until eventually it has to solve it for only a single disk. And if you trace the code for what happens when there’s a single disk (when numberOfPegs==1), you’ll see that all it will do is the print statement.</p><br /><br /><p>To me, the Towers of Hanoi problem is <strong>the most beautiful algorithm there is</strong>. And it fits the requirements for a <a href="http://en.wikipedia.org/wiki/Recursion_%28computer_science%29">recursive algorithm</a> perfectly; it can be broken up into smaller problems, until it reaches an exceedingly simple case (just moving a single disk).</p><br /><p>I wonder how long it took after the first computers were made until the Towers of Hanoi was successfully programmed. Very probably it was done in machine code, using a <a href="http://en.wikipedia.org/wiki/Stack_%28data_structure%29">stack</a> of some sort. But what was the first language that would have allowed it to be done with a nice readable recursive function? I would love to have been a fly on the wall.</p><br /><p>There’s lots more to the Towers of Hanoi, which I will cover in a later post.</p>Laikahttp://www.blogger.com/profile/16165304577490923507noreply@blogger.com0tag:blogger.com,1999:blog-1198137302921075675.post-14287255500695189402008-01-27T20:55:00.000-08:002008-01-27T20:57:57.955-08:00Hello, world!<p><strong>Hello, World!</strong> And welcome to Computronium.</p><br /><p>In this forum I’ll be talking about things that thrill my brain. Mostly, as the name implies, it’ll be about <strong>computing</strong>, especially the <strong>recreational</strong> variety, but I’ll be taking brief interludes into <strong>math</strong>, <strong>physics</strong>, <strong>astronomy</strong>, or <strong>whatever else</strong> strikes my fancy. I’ll be focusing on the bits that are just fun, or interesting, or beautiful to me. Hopefully they will be to you too.</p><br /><br /><p>I have met a number of people in my life who enjoy computer programming for its own sake. But there’s also people who think that anything created on a computer is inherently soulless, and that any art created on a computer is cold and robotic. I couldn’t disagree more. Art created on a computer is as human as the person who makes it. But the logic underneath too is beautiful in and of itself.<a id="more-1"></a></p><br /><p>Though I’ll be presenting things that give me “intellectual” thrills, my goal will always be to simplify, and to explain clearly, without dressing things up in fancy language. I’ll be writing about what I know but also about what I don’t — things I’m curious about. So I’m counting on input from you all. Not everything I’ll be writing about will be deeply profound — some of the topics I’m pondering will require just a few sentences. But even in dusting off these old ideas that I’ve pondered before, I’ve come up with new ways of looking at them, as well as some completely new ideas. I’m sure, with the participation in this forum that I’m hoping for, there’ll be lots and lots of other things that come up.</p><br /><br /><p>So, the main topic: computing. Computers themselves are ghastly, I believe, BUT, they’re the only things that let you compute. We’ll not be arguing here the merits of Java versus C++, or talk much about the flavor du jour of software processes. I have preferences in these matters, of course, but the underlying algorithms are what really interest me. Some languages do indeed encourage you to look at problems in interesting ways, but for much of what I’ll be talking about, the choice of programming language is pretty much moot. And as far as process — while I’m totally convinced of the necessity of good software practices, I don’t find a lot of joy in talking about it.<br /></p>Laikahttp://www.blogger.com/profile/16165304577490923507noreply@blogger.com0