Tuesday, September 16, 2008

Wooo

  • I cracked 50 lb of weight loss today. I'm still on track (±ε) to reach my original goal by Christmas. It also happens to be, as of yesterday, 10 lbs in 100 days, or almost exactly 350 calories/day.
  • Pursuant to that, I have made a breakthrough in food reduction technology. One of my favorite meals is...undocumented on this site?! WHAT. Anyway, it involves guacamole. The problem I've had is that I need to make enough to use up an entire avocado, which now that my metamabolism needs fewer calories is a little too much. Avocado turns brown if you look at it funny, so I can't put the excess in the fridge. I also can't throw it away because of the starving children in Africa. However, it turns out to freeze just fine. So now I can make M/Nths of a recipe which not only vastly reduces the hit points but also means I only use M avocados every N days.
  • I'm trying to embed a microcontroller into a project that I'll describe more later. All I know is Arduino, so I'm going with that. (I guess I could just use the Atmega chip or however that works, but baby steps, people.) The basic Arduino is a little unwieldy for this, but last night I finished soldering and testing the Really Bare Bones Board. And besides being much smaller and breadboard-compatible, it's also much cheaper because it pushes some of the cost of the unit into a one-time-purchase cable.
  • Number One Son, age 9, is trollering me. He just found out about HTML and has made a couple of pages. (With random size changes and font colors, naturally.) He keeps calling the .html file a "program".

Wednesday, September 10, 2008

New Control Structure Considered Useful

We have a large data processing problem at work. Basically, we get thousands of items every day and have to figure out which ones go together. The only way to know if they go together is to try them. Some items may not go with anything, some may fit with a hundred or more other items. The one nice thing is that once we've found 3-5 items that go together, we can zip through all the other members of the group.

The problem is finding those 3-5 items. Choosing every possible combination of 5 would take too long. Choosing every combination of 3 is fast enough, but leaves a lot of extras. The simple solution is to first try all the combos of 3, then try all the combos of 4 on the remainder, then try all the combos of 5 on the remainder of that. The smaller and smaller pile makes the larger and larger choices feasible.

My boss, who is a competent practical programmer, suggests we have 3 procedures: One that does a 3 nested loop, one that does a 4, and one that does a 5. Like this (in Tcl):

set items {apple orange banana grape strawberry}
set count 5

for {set i 0} {$i < $count} {incr i} {
    for {set j [expr $i + 1]} {$j < $count} {incr j} {
       for {set k [expr $j + 1]} {$k < $count} {incr k} {
         set string [lindex $items $i]
         lappend string [lindex $items $j]
         lappend string [lindex $items $k]
         puts $string
       }
    }
}

That's just the 3 level loop because the other two look almost the same. The 4 and 5 level loops are identical except for having additional levels. As a programmer who values elegance over readability, the phrase "identical except for" is a red flag. Why have 3 separate procedures when all you are adjusting is a single parameter? What I need is a new control structure that is basically a for loop but lets me control how many nested fors there are.

Tcl makes it easy to create new control structures. Here's the control structure definition:

# Usage:
#  indexcount - how many items are being chosen
#  itemcount  - how many items are being chosen from
#  indexvar   - variable to hold current combination of indexes
#  body       - code to execute for each combination
proc chooseloop {indexcount itemcount indexvar body} {

    if {$indexcount > $itemcount} { 
      error "More indexes than items"
    }

    if {$indexcount == 0} { return }

    set indexes {}
    for {set i 0} {$i < $indexcount} {incr i} {
       lappend indexes $i
    }

    set maxindexval [expr $itemcount - 1]

    while {1} {
 
       # make new body that sets indexvar first
       set newbody "set $indexvar {$indexes}\n$body"

       # do this iteration
       uplevel 1 [list eval $newbody]

       # find incrementable index
       set found no
       for {set i 0} {$i < $indexcount} {incr i} {
          set index [lindex $indexes end-$i]
          set thismax [expr $maxindexval - $i]
          if {$index < $thismax} {
             set found yes
             break
          }
       }

       if {!$found} { break }

       # increment this index and set all following ones
       set incrindex [expr ($indexcount - 1) - $i]
       set precedingval [lindex $indexes $incrindex]
       for {set j $incrindex} {$j < $indexcount} {incr j} {
          lset indexes $j [expr $precedingval + 1]
          set precedingval [lindex $indexes $j]
       }
    }
}

Now to get my 3 level loop, I can call like this:

chooseloop 3 5 indexes {
    set str ""
    foreach index $indexes {
       append str "[lindex $items $index] "
    }
    puts $str
}

In order to do 3, then 4, then 5, I can call like this:

for {set i 3} {$i < 6} {incr i} {
    chooseloop $i 5 indexes {
       set str ""
       foreach index $indexes {
          append str "[lindex $items $index] "
       }
       puts $str
    }
    puts "--"
}

The output of that last one is:

apple orange banana 
apple orange grape 
apple orange strawberry 
apple banana grape 
apple banana strawberry 
apple grape strawberry 
orange banana grape 
orange banana strawberry 
orange grape strawberry 
banana grape strawberry 
--
apple orange banana grape 
apple orange banana strawberry 
apple orange grape strawberry 
apple banana grape strawberry 
orange banana grape strawberry 
--
apple orange banana grape strawberry 
--