Proof Checking at Fedex Office

As part of keeping my Dominion box organized, I print off dividers that a wonderful soul has freely published onto cardstock via FedEx Office nee Kinkos.  The divider's I hadn't printed were for the latest release (Guilds) and so while having other fun Christmas-y stuff printed, I had these done as well.
The results are shown below.

Compare the above to the original file shown below:

Two problems here:

1. Clearly the file didn't print properly.  Where the name of the card should be in the title banner a black box exists.  No PDF viewer, including the online proofer provided by FedEx office shows this black box so I don't know how it ended up getting printed but it did.
2. Here is the full text of the pink note attached to the printed document.
   
   "PRODUCTION REVIEW SAMPLE
   Dear customer,
   I have compared the proof (if applicable), originals and the job ticket, and determined that it meets the FedEx Office standards of quality.
   All subsequent copies were produced to match this sample.
   We appreciate your business and look forward to meeting your needs in the future.
   (Team Member Signature)"
   
   Knowing that sometimes things get messed up, FedEx Office has a system in place where each print job is examined to ensure that it is getting printed properly and has an employee sign this verification. As the note clearly states, this includes comparing the printed product to the original. I know from trouble-shooting the problem with them after the fact that no digital representation of this file showed the problem, only the printed version.  They had a clear definition of the final product to use in comparing to the printer output and yet kind of blew it.

In my mind, the second problem is bigger than the first. 

Bad PDF Rendering?

The general publication of the professional society I belong to, IEEE, is their Spectrum magazine.  To make my life easier and less paper-oriented I've elected to receive the publication as a PDF which I often read on my iPad.  In the November issue I noticed an odd typesetting error.  The letters in the body of the text closest to the gray text box seemed to have something wrong. I have so little experience with preparing print-ready publications that I'm not going to speculate as to the cause of this problem.

Mutant Paperclip

Paper clips have been commandeered for a long time to be misshapen and turned into semi-sharp, pointy, pokey tools.  One of the most common uses in the world of personal computers is to reach a recessed reset button, one that the designers wants to ensure could ever to be pressed by accident.  Back when I was in middle school, our first computer came with the instructions to use such a paperclip to get to a manual eject button inside the disk drive. It was a bit scary that the official trouble-shooting procedure involved poking around in the computer innards but that was the way things were done.

Or "are done" I should say.  The receiver for my wireless mouse broke and the manufacturer sent me out a replacement.  The instructions for pairing the receiver to my mouse involved this recessed-button poking but rather than asking me to use one of my own paperclips, they send me one in the receiver package, pre-bent.

(The manufacturer is Evoluent, by the way and I'm using their Vertical Mouse 4 to help reduce strain on my wrist.  The product is great and their technical support was top notch.  I called phone support, a real person answered, and once my problem was described, he knew what needed to happen and sent me out a replacement receiver.  The only downside: I have to drum up a Windows computer to run the mouse-receiver pairing software.)

Reinstalling a Hardwood Floor - My Solution

I've been spending quite a bit of time thinking about the hardware floor problem my father-in-law handed to me.  At first the problem seemed kind of straight-forward.  There's a pile of pieces of flooring, make sets of pieces whose total length is 184 +/- 1 inch.  As I thought it about it more, though, it became readily apparent that the problem was more complicated than I first thought.

1. No solution guaranteed - Though the total length of the pieces available sums to greater than the total length needed, there is no guarantee that the pieces come in lengths that will form 20 sets that each sum to 184 inches.
2. Unique start and end pieces - Certain pieces can only be used as start and end pieces as they have been cut and lack a tongue or groove on one side.  Additionally, there are only 13 starting and ending pieces which means that some pieces with both a tongue and groove (middle pieces) will end up acting as a starting or ending piece.
3. Cutting may be required - It may not be possible to find a solution EXCEPT if we allow middle pieces to be cut if they are at the beginning or end of a run, effectively making them starting or ending pieces.  If we don't allow for this scenario, we could end up in a situation where there are plenty of pieces left to complete the task, but they are none short enough to fit in the remaining space at the end of each run.  The flip side of the coin is that once a piece is cut, it can only act as a starting and ending piece so only want to cut pieces as a last resort.
4. Permutations, not combinations - The biggest complication: since once a piece has been used in one run it can't be used in another, this is not a simple combination (order independent) problem but rather a permutation (order dependent) problem. An exhaustive search of the problem space would test not only which groups of pieces sum to the correct length, but the order in which the pieces are tried.  This is necessary because we don't know if a given piece must be joined with specific set of other pieces (a critical set if you will).

My "solutions" to these problems:

1. No solution guaranteed - I have no actual solution to the "no solution" problem.  I worked under the assumption that there is a solution and wrote my program in such a way that it would stop looking after a predetermined number of attempts.
2. Unique start and end pieces  - To handle the fact that only certain pieces can be used as starting and end pieces I wrote the program to pick one of each of these to form the basis for each run.  The program then worked to fill in the gap between the two by working from the middle pieces list.  Since the start and end list only had 13 pieces, I padded the list with zeros to bring it up to 20, the number of runs required.  This leads me to...
3. Cutting may be required - The zero length pieces in the start and end list essentially represent middle pieces that act as end pieces. Furthermore, I allowed for longer pieces being cut down by allowing for runs longer than the strict 184 + 1 inches.  Any middle piece that ended up acting as an end piece would have to be cut down and in situations where dedicated start and end pieces were used in the run, this would make it necessary to cut those down as well.  This would not sacrifice a tongue or groove as the start and end pieces are already missing one or the other.  The larger the allowed deviation from 184 + 1 inches, the more material may have to be cut off from existing pieces.
4. Permutations, not combinations - Ahhhhh. This was the problem that kept me thinking the most.  trying to find easy ways to add and remove pieces from trial runs, keep track of which pieces were being used, had been tried, or were being tested, intelligently resetting the trial to preserve sets that had not been proven to be infeasible... In the end I decided to cheat: pieces were chosen at random and I was fairly quick to completely start over.
   
   At the beginning of forming a run a beginning and ending piece is each randomly chosen.  Next, middle pieces are randomly chosen and added to the run until the length exceeds the maximum allowable length.  If the maximum length is exceeded, the piece just added is removed from the run, placed in a "already tried these" list and another candidate from the middle-piece list is added to the run.  By keeping track of all the middle pieces being tested (moving them from the middle-piece list to the tried-piece list) the program is able to exhaustively check all middle pieces to see if any of them would work.
   
   If a middle piece did work to complete the run, all pieces used to form that run were removed from their respective pools of candidate pieces and were saved off in a separate completed-run list.  Two more starting and ending pieces were chosen at random and the process repeated.
   
   If all of the middle pieces were tried and the run was always too short or too long, then the program ruthlessly restarts the entire process.  All pieces used in all completed runs are moved back to their starting lists and we start all over.  This all or nothing approach is draconian and the program does save off the results of that attempt if it has resulted in more runs being completed than on any previous attempt.  Again, I don't know if any solution exists and I wanted to have access to the best solution in case I never found the perfect, all 20-runs solution.  The program is also limited in the number of restart attempts it is given so as to prevent it running endlessly, looking for a solution that may or may not exist.

I implemented the above algorithm in Matlab (the programming language I currently know best) and set it to running.  I found that when I kept the maximum length requirement to the strict 184" + 1" requirement, the best solution that has been found so far was 18 complete runs.  When I relax the maximum length to 184" + 2" my best result so far is 19 runs and adding another inch gets me all the way to 20.  

These numbers are a bit deceptive, though.  The 184" + 1" result took somewhere in the neighborhood of 40 million restarts, the 184" + 2" took about 20 million and the 184" + 3" less than 0.1 million.  Again, I don't know if the 184" + 1" constraint has a full 20-run solution but I'm going to continue to run the program and see if it can be found.  For the longest time, the best solution was 16 runs but just last night an 18 run solution was found.  Once pieces start to need cutting, I don't know if the amount of material needing to be removed (one inch vs two) matters that much.  Depending on the tools, it might even be easier to remove more material as the saw wouldn't be working quite so close to the end of the board. 

As I said, the program is going to continue to try to find a full solutions for the 184" + 1" case but I'm going to send these results off to my father-in-law so that he can get his floor put back together.

2012-12-13 Update: I forgot to share my Matlab code; here it is. There are still some bugs in it that I have had to hack around so as to keep the iteration train rolling.  Most of the time, it works great but somehow, sometimes, some list variables end up empty when they shouldn't be which grinds things to a halt.  This happens infrequently enough that I decided to patch over it rather than fix it properly.  In this case, it was more important to have something that works 99.999% of the time rather than waiting to use the tool until it is at 100%.

Heel Healing

I was in to visit the doctor yesterday to take a look at my heel and was given great news!  The bone and incision wound are healing wonderfully and I've been given the go ahead to move on to the next phase:

• I start five weeks of physical therapy today.  I have no idea what is in store except that it will probably be painful.
• I can sleep at night without my walking cast.
• I may be able to stop taking the drug I've been using to prevent nerve pain.  We might try going off of that as soon as this weekend.
• I can try walking!  TRY walking. I've made it a matter of practice to hobble around the house using one crutch as a cane.  It is very slow going, painful, and what I can only imagine is an essential part of my rehabilitation.

My wife and I are discussing what other lifestyle changes could be made as well.  I probably don't need to spend most of my waking hours in bedrest any more so maybe meals can move back to the dining room (instead of in the living room where my bedrest couch is).  Once I'm off the insomnia-inducing neurological drug I should be able to get back to a regular sleep schedule and move back into our bedroom with my wife.  Also, assuming all goes well, I should be able to start next semester as planned though there are still questions about transportation as I no longer have a motorcycle and my bicycle riding ability is greatly diminished. (We did pick up a stationary bike that I plan on using to "train" starting sometime soon.)

Even though the endless bedrest made it seem like I was making little progress, it turns out my body is healing after all.  Who would have thought?

Reinstalling a Hardwood Floor

Thankfully, this is not a story about one of my home improvement projects.  This is a story about programming.

To deal with a termite problem, my father-in-law recently had to tear out a portion of his living room floor.  His work in the crawlspace is nearing an end and he is ready to put the hardwood floor back into place.

Problem one: When tearing out the floor he was not anal retentive and did not mark where each piece originated.

Problem two: Not all of the pieces survived the removal and a new bundle of pieces was purchased having different lengths than the originals they are replacing.

The real problem: How do we figure out which pieces need to go where to reassemble the floor?

My father-in-law is an educated man and quickly realized that this might just be a job for a computer. He measured the lengths of all the pieces and entered them in Excel.  His question to me: was there a way to get Excel to take the list of piece lengths and pick groups of lengths that would sum to the width of his living room?  This got my brain turning right away because I too realized this was the kind of problem computers were made to solve.

I know there are a lot of programmer types out there that find the lay-man's reliance on Excel maddening.  Many of these complaints I also agree with but I do not share in their derision of those Excel-users.  Excel is, well, an excellent first programming tool.  Each cell is a variable, iteration can be done by repeating the formulas down the page using previous results, and for many people I suspect it makes abstract lines of code more concrete and understandable.  "I want to multiply this value by that value to find the interest rate and see how that will impact my mortgage payments."

Excel is a victim of its own success, though.  It is so easy use that it can quickly provide users with more than enough rope to hang themselves.  And because many many of its users do not feel ready to jump into more traditional programming languages (or even dip their toes into the built-in, full-fledged Visual Basic scripting/macro/programming environment), Microsoft tries to do what it can to make that hanging less certain.  Features like dependency tracing, input validation, and error checking are all essentially debugging tools built into the program so users that have this one hammer can be more efficient and using it on all the nails they may find.

So I'm not surprised that my father-in-law turned to Excel and I'm glad he did.  But my answer to him was that I didn't think Excel was the right tool for this job and I offered to see if I could put my modest programming skills to use.

For those of you playing along at home here are the details:

• The total length of the living room is 184 inches.  Due to floor moulding on both ends, the accepted length for a giving run of pieces is 183 to 185 inches.
• Due to the way the floor is assembled, there are specific pieces that must be used to start a run on one end of the room and specific pieces that must be used to end a run.
• It will take twenty runs laid side-by-side to reinstall the floor. 
• My father-in-law has already determined that there is enough wood to reinstall the floor but no guarantee that it has been cut in appropriate lengths.  This is to say, we don't know if there is actually a solution to the problem so it might be a good idea to find the best solution.  For our purposes, the best solution will be the one that completes the most runs with the given pieces.

So get to it my friends.  Here is a list of the lengths we have to work with. Let the iterations begin!

Starting pieces
Middle pieces
Ending pieces

(Right now, only 13 start and finish pieces are given.  I'm in communication with my father-in-law as to why this is the case.)

2013-12-08 Update: I've confirmed with my father-in-law that the list of 13 start and finish pieces is not an error.  The other seven runs will start and finish with middle pieces.

2013-12-12 Update: Follow-up article here.

Basil's Treasure

During the daily walk this morning, Basil made the sidewalk-find of his life:

The package of pork sausage must have been sealed because he didn't try to eat it.  I don't think it was until after we had taken it from him that he realized the value of what he had just moments before been holding in his mouth; he began to whine and jump up to peer over the counter ledge in hopes of locating his treasure.  This was much more valuable than the socks and Kleenexes he more frequently hunts.

If there was ever a moment for "finders, keepers", this was it.

Rainy Lawn

I forgot to get this posted back in August when it was relevant but I'm going to go with the "better late than never" approach.

This is what happens when you're out of town for two weeks and it rains nearly every day during that time:

I really enjoyed the vacation and am really glad we got the rain to relieve the drought in the area but I really didn't look forward to bringing this back under control.  Tools that didn't work so well: lawnmower and week-whacker.  I ended up using... (wait for it) .... clippers. That's right, I mowed most of our (not very large) backyard by hand.  It took many hours over many days but it was the best way to fell these 18 inch stalks.

Bug in gas pump

As the textbooks say, the following is an exercise left to the reader (which probably means you won't find the answer anywhere in the textbook, or in this case, blog).

Question 1: What do you think the second sentence (the one that doesn't end in a period) should be?

Questions 2: For you programmer's out there, what kind of operation/function isn't doing its job very well to cause this kind of error?