I was in a lot of competitions back in my school days. There really wasn't a lot else to do. I didn't really study, and the teachers figured they better keep me busy or I'd just cause more trouble that I was already doing. So I got sent off to win trophies. There were math competitions, orchestra competitions, physics competitions, engineering competitions, drafting competitions, science competitions, accounting competitions; I even got sent off to a spelling bee once (by mistake probably, I hate spelling). But one of my favor ates was the computer competitions.
The first reason I liked computer competitions was that the school, or some local business (back when local businesses sold computers), would loan me a computer for a couple of weeks to "get ready". Actually I'd spend every night writing and playing games on them. (Back then a computer cost more than a car, so my parents had not bought me a computer of my own.) My parents didn't know what I was doing on the thing, and maybe writing games could be considered "getting ready" in any case. The second reason I liked computer competitions the best was that I liked writing programs under pressure even better than normal, as I considered myself rather good at thinking under fire, and whipping out five or six solutions in a couple of hours by myself just left those other teams of three and four people in the dust.
Interestingly enough, I often missed problems or could not come up with a solution in the time allotted. Luckily, no body else could either, but I learned from those problems, especially in competitions where they handed out the answers afterwards.
On particular problem was called magic squares. Basically you had to generate all the possible permutations of valid magic squares for a grid of size N. I of course tried to write something that would automatically permeate the board through its valid values: put a 1 in the first square, then create a list of numbers remaining and use that to populate the adjacent nodes and so on and so on. A big complicated mess of permutation trees. And I was trying to do this in BASIC on a 6502 machine. In about 20 minutes. Needless to say, I didn't succeed.
The answer turned out to be far more simple. Create a square NxN filled with the number 1. Then start adding 1 to the first square, carrying forward when it wrapped beyond N. Sure this generates a lot of invalid answers, but you just test to see if its valid at the end of the day, and only print it if it is. Wow, let the computer do all the hard work generating thousands and thousands of wrong answers and only bother to say something if it happens to find one that's right. "Brilliant!" I thought.
Computer back then could handle millions of cycles per second and thousands of pieces of information with ease. Who cares if you send them down dead ends again and again. (Besides Marvin the paranoid android) This approach turns out to be even smarter when you want an answer that's good enough, but you don't care how good enough it is. I ran into just this situation a few years later.
We were living in California and the S&L crisis had just passed which meant there were a lot of banks around with the name "Federal" in them (as in the federal government had bailed the banks out and now basically owned them). I was banking at Fidelity Federal and had my checking account, business account and mortgage there. (Its convenient to apply for a mortgage from the same back where your checking account is--when they want to know your account balance and last six months history, you can tell them to go look it up themselves.) Anyways, out of boredom I had started reducing the fractions on my checks sometimes. Like 50/100 is the same as 1/2, and in fact back in sixth grade if you wrote down 4/8 for an answer instead of 1/2, you were likely to get marked off by the teacher--it wasn't proper. So I started writing amounts like 19/25 on my checks. Then I noticed something even stranger.
SIDENOTE (for those under 30) Once apon a time the world did not run on plastic & electrons. It ran on paper. Specifically little rectangular pieces of paper, a little smaller than money, called checks. They came from the printer in little books, and we'd carry one around with us everywhere and called them "checkbooks", and they had your name & address on them and a little number on the corner which went up on each successive page. The first one was 101, then 102, etc. Actually, a check with '101' on it made you look like a newbie, so if you were really hip, you ordered your first book of checks (for your checkbook) starting with 501 or something. Then you looked really cool. And then the really bizarre part was that after you wrote a check and gave it to the store, and then the store sent it to your bank to exchange for dollars, and the bank took the money out of your account; it saved up all these little scraps of paper and sent them back to your at the end of the month. I know, you're thinking crazy, but that's what they did.
Anyways, one day I was looking at the checks that came back from the bank (ok, must have been a really slow day), and I noticed that somebody had taken the check that I wrote for eighteen dollars and 19/25ths, and had entered 19/25ths into their adding machine to verify that it came out to 0.76 and had noted on the check that it was indeed 0.76 and they had initialed it. I couldn't think of one possible reason why you would do that, but for some reason I decided that it was my mission in life to keep that guy employed, by writing every check from that day on as an odd fraction. Now even numbers were easy enough to reduce, I could divide any number between 2 and 98 by 2 easily enough, but the odd numbers were a little trickier. You can't really reduce 33/100 exactly. But then I had a wild idea. Maybe I didn't need too. Maybe I only needed to get close (like say 0.005 close). 1/3 was 0.3333333, but it rounded down to 0.33. That ought to keep that poor accountant busy for hours. Now I just needed some way to come up with the right fraction that was close enough for any decimal amount.
The solution turned out to be simple. Let the computer try a hundred numbers that didn't work and then have it stop when it found one that did. I told it to start with 0 / 1, adding one to the top if it was too small and one to the bottom if it was too big. No finesse, no optimizations; just brute force. For 0.33 it would just try 0/1, 1/1, 1/2, and then hit 1/3. For something a little harder, like 0.37 it would try: 1/1, 1/2, 1/3, 2/3, 2/4, 2/5, 2/6, 3/6, 3/7, 3/8, 3/9, 4/9, 4/10, 4/11, 5/11, 5/12, 5/13, 5/14, 6/14, 6/15, 6/16, 6/17, 7/17, 7/18 and then finally get 7/19 (which is 0.368421). Notice how it runs over the same ground a lot, like 1/2 2/4 3/6 or 2/5 4/10, but who cares. The core routine is three lines long:
Eventually I souped it up a little, adding another test to capture the results within both 0.005 and 0.001 (just for some variety), and I also made a wrapper that would call that function for all values between 0.01 and 0.99 so that I could make a little cheat sheet to carry around in my checkbook and use when I was at the store and needed to pay with a check.dtmp= 1. * ia / ib, delt= dtarget - dtmp ; if ((-0.005 < delt) && (delt < 0.005)) break ; /** found it */ if (delt < 0.) { ib ++ ; } else { ia ++ ; } /** work closer */
Don't get a chance to use that routine much anymore these days. Press a button, pay the bill. Occasionally you might see someone in the checkout line writ ting a small novel in order to pay for two gallons of milk and a bunch of bananas, but the check book is pretty much extinct. Too bad, I kind of miss that guy in accounting.
