All posts for the month August, 2013

Ok, so I went to print something yesterday, and the print job would spool to the printer, then disappear, while nothing printed. Oh great, the printer is disconnected again.  This happens occasionally with my WiFi printer, which I leave on all the time because it also connects to Google Cloud Print, so I can print document from my phone or tablet (not that I do it very often).  Of course, when the printer is disconnected, I usually get an error explaining such, but this time, no error.

Ok, maybe Adobe Reader is broken, wouldn’t be the first time.  I’ll try printing a Word document instead… nope, same problem.  Well, lets try printing to the XPS document writer, nope, still the same problem.  Well, this is starting to suck.  Restart computer a bunch of times, re-install printer a bunch of times, nothing.  Use Windows Restore to roll-back my computer a day, 2, 5, 7, nothing.  This is getting desperate.

Ok, maybe something is really wrong with my computer, what does Google have for me?  Lets try using the System File Checker… update pending restart?  Ok, restart computer 4 more times… still pending restart?  Ok, search for solution to fix the pending restart issue, found.  Now run System File Checker… no problems found, well this isn’t promising.

Alright, I do weekly system image backups for a reason, lets restore the whole partition to last Sunday.  One hour later, still no printing.  Now this is just beyond frustrating.  No one else with this problem seems to have found a solution.  They can print from notepad, but nothing else (same here).  Well, I guess this means I get to re-install windows.  Luckily I use separate data partitions and drives, so after the Windows installation, I just point My Documents and My Music in the right place, spend all day re-installing programs, and now I’m back to normal.

This seems like a really odd corner case that has slipped through Microsoft’s fingers.  Something in the system causes the print spooler to suddenly, without warning or error, simply discard print jobs instead of passing them on to the printer.  I’m not the only one to have this problem, nor apparently the only one to not find a solution.  On the bright side though, I just cleared-out 3+ years of unused programs from my computer, and it boots much faster now.  Even Steam re-installed over itself, so I don’t have to re-download 700GB of video games.  Yay!

Ok, so here is another coding question:

Given an input string, determine whether or not the string is composed of only abbreviations from the periodic table of elements.

This actually sounds kind of complex, like the stacking athlete question I answered previously, but it actually has a 2-line solution:

That’s right, given a string in $line, $result with be true if the string is composed solely of element name abbreviations. Simple huh? As for complexity, who knows. I don’t know enough of how regular expressions are computed to guess, but I assume it’s been made to be somewhat efficient.

Of course, additional optimizations can be made, for instance, “J” is not used in an elemental abbreviation, so any line with “J” could be disqualified (of course that requires a linear search of the data first).

Anyway, here’s the full script, in case you want to impress your friends.

Second example problem:

Given an m * n field of trees and open spaces, find out the biggest square house that can be built with no intersection with trees.

For a suboptimal solution, simple solution starts with scanning every space to see if it is open or not (starting in the upper-left). Find the largest possible square starting at the given space, then find the maximum size square possible in the entire area.

Note that each loop has two conditions, the total width/height of the area AND the max value.  This max-value check keeps the loops from searching for open squares that could not possibly be larger than the current largest square (e.g. too close to one edge of the area).

Now, the function itself, starting at the specified location, searches diagonally for trees, stopping at the first and/or nearest tree it encounters.  It does this by first checking the current square for a tree.  If there is no tree it scans downward until it a) finds a tree or b) reaches the edge of the map.  It repeats the process to the right.  It then increments the “top-left” square inward and repeats the process.

The code above has one special optimization.  We first declare a global variable  std::unordered_map<int,int> FoundMax; This unordered (hash) map is keyed on the x,y coordinates of a square, and stores the maximum size of a square found starting at those coordinates.  This way, it we happen to be searching a diagonal sub-set of a previously searched larger square, we will not have to loop further to find the area of that square.  Note that because this searching works diagonally, we could actually use membership in the FoundMax map as an exit condition (or perhaps, in the outer main loop to prevent calling Find2 in the first place).

The complexity of this algorithm is N for the outer-most loop (once for each square).  From each square, we search a maximum of M additional squares (where M < N), making for a worst-case complexity of O(n*m).  This isn’t a valid expression, true, and by investigation we can see that m decreases logarithmically with respect to n, making a true complexity of O(n log(n)).

Ideas for further optimization: For all upper-left squares with the same X value, the maximum distance down is less than the maximum distance of the previous Y value down. We could therefore skip searching for the next downward tree with a lookup of the nearest downward tree from Y-1 (if we were storing that value). The same goes for the nearest tree to the right from the current X for squares starting on the same Y.