Monthly Archives: April 2013

This is a pretty incredible list of incredible places

http://imgur.com/a/MqR8x

In particular I like the Black Forest, Mount Roraima, and the Tunnel of Love in the Ukraine, and the Zhangye Danxia Landform in China.

Advertisements

Transporting the A-12

http://www.roadrunnersinternationale.com/transporting_the_a-12.html?m=8

This is a fascinating account of just one small part of the cold war: transporting the A-12, a predecessor of my favorite plane, the SR-71 Blackbird, from the Lockheed Skunkworks in Burbank to Area 51 for final assembly and flight testing. This was in the early 60s.

They took over roads, reshaped hills, and made a huge nuisance of themselves, all to transport some carefully-nondescript boxes from Burbank up to Area 51. It’s amazing to think about the conversations they must have had: “Hi California Highway Patrol. Yeah, I need to take over the freeway for a few days. No, I can’t tell you what I’m doing it for. But it’s important.”

I would love to see the project plan for this.

Lockheed moved the skunkworks to Palmdale around 1990, and this part of Burbank is just a bunch of nearly-abandoned buildings and vacant lots now: google maps link. Just north of this is Lockheed Drive.

Things are getting better, part 3

Minimum wage over the decades, from the Fiscal Times

Okay, maybe not entirely better. This is a breakdown by decade of the cost of gas, a movie ticket, and rent vs. the minimum wage. Instead of dragging it out in a slide show, here you go:

Decade Minimum Wage Gas Movie Ticket Rent
50s $0.75 $0.27 $0.48 $42
60s $1.00 $0.31 $0.69 $71
70s $1.60 $0.36 $1.55 $108
80s $3.10 $1.25 $2.60 $243
90s $3.80 $1.13 $4.23 $447
2000s $5.15 $1.49 $5.39 $602
2010s $7.25 $2.78 $7.95 $790

The overall tone of the article is negative, and by the raw numbers, that’s somewhat justified: while gas is actually cheaper in terms of wages, movie tickets have gone up by over 60%, and rent by 85%.

 

But consider what you got then for your money vs. now:

 

Cars today are safe, comfortable, fuel-efficient, and go practically forever with no maintenance.

Cars in the early 50s (some of them) still came with no seat belts, no padded dash (I remember Jay Leno joking once on Letterman, “You get in an accident in one of these babies, they hose off the dash and sell it to someone else!”), no disc brakes, no air conditioning, and got maybe 15MPG — oh, and needs an inspection/tune-up every 5000 miles.

 

Today your $7.95 movie ticket gets you this:

zz7c491fa4

 

In the 50s $0.48 got you this:

Annex - Chapman, Ben (Creature From the Black Lagoon)_NRFPT_05

 

Apartments today are harder to generalize about, but most have air conditioning, a dishwasher, and a bathroom. A microwave might not be built-in, but it wasn’t an option in the 50s. Everything is more energy-efficient now. Almost certainly the apartment some form of cable-tv available, and internet access — perhaps free wi-fi.

Apartments in the 1950s were unlikely to have a dishwasher. The refrigerator was primitive, and if the apartment had air conditioning (not nearly as likely) it was often a noisy bolt-on sitting in the window. Less expensive apartments used shared bathrooms. Lead paint and asbestos were much more common.

So, as I’ve said before, I’ll take today. Yesterday sucked.

Less Brutal Insanity

In Brute Force Insanity I described writing code to solve the  Instant Insanity puzzle. The code given there was bodged together quickly, and it shows. The example below has numerous improvements:

  1. It handles a variable number of cubes by taking advantage of recursion. This actually slowed it down a little, but the alternative nested loops was too ugly to consider.
  2. It has several significant optimizations. Fifteen cubes is probably reasonable. The theoretical maximum is 26, but that would be roughly 10^35 possibilities, and none of my optimizations will address that entirely.
  3. Cleaned up what it was doing overall, and added comments.
  4. Re-wrote the code to take a more-manageable format for the cube definitions: a straight line of six characters.
  5. Made numerous trade-offs where doing more efficiently was  less readable than the slightly less efficient method.

One of the optimizations is interesting. I realized that it’s possible to rule out numerous options based solely on the number of colors they contribute, rather than their actual orientation. Reworking to take advantage of this wasn’t simple. First, it means checking through all the possible combinations and keeping track. There are three “loop”s for each cube, so for six cubes the number of possibilities could be as high as 3^n, where n is the number of cubes.

After figuring out which paths (potentially) work, it’s necessary to go check them in detail. The data on which ones need to be checked must be stored, and the checking code re-written to follow the combination already determined to be a possibility.

 

local cubeCount -- the number of cubes being solved
local stringList -- an array of the strings possible for each cube
local pathArray -- an array of the paths the solution can take
local loopColorCounts -- an array of how many faces of each color each loop contains

on setupStrings cubeList
   -- given a list of cubes
   -- get the permutations
   -- and store them in the local variable stringList
   put 0 into cubeCount
   repeat for each line L in cubeList
      add 1 to cubeCount
      -- dontPermute the first cube. it doesn't need to 
      -- flip or rotate since all the subsequent cubes can
      -- flip and rotate together
      put stringsFrom(L,cubeCount=1) into stringList[cubeCount]
   end repeat
end setupStrings

function pathsFor cubeList
   -- given a list of cubes
   -- each cube has three possible loops
   -- add the faces and discard any combinations 
   -- that have too many/too few of a color
   -- return the list of paths that have the
   -- right color total, although they might
   -- not be configurable to make the colors 
   -- work by column.
   
   -- first, set up the array with counts
   delete variable loopColorCounts
   repeat with theLevel = 1 to cubeCount
      put 1 into theBranch
      repeat for each char C in stringList[theLevel][0]
         -- [0] is the de-duped list of
         -- the three possible loops
         if C is cr then 
            add 1 to theBranch 
         else 
            add 1 to loopColorCounts[theLevel][theBranch][C]
            put 0 into colorArray[C]
         end if
      end repeat
   end repeat
   return pathsAtLevel(1,"",colorArray)
end pathsFor

function pathsAtLevel theLevel,thePath,colorCounts
   -- this is the recursing function
   -- for getting paths
   
   -- check for success
   if theLevel > cubeCount then return thePath & cr
   
   -- otherwise add another step to the path
   put empty into theReturn
   repeat for each key theBranch in loopColorCounts[theLevel]
      -- add the branch colors & check for > 4
      put colorCounts + loopColorCounts[theLevel][theBranch] into colorCountsX
      if max(colorCountsX) > 4 then next repeat
      put pathsAtLevel((theLevel + 1),(thePath & theBranch),colorCountsX) after theReturn
   end repeat
   return theReturn 
end pathsAtLevel


on makePathArray X
   -- put the list of possible paths
   -- into an array for easy reference
   delete variable pathArray
   repeat for each line L in X
      put 0 into tPath
      repeat with i = 1 to cubeCount
         if char i of L is not among the lines of pathArray[tPath] then put char i of L & cr after pathArray[tPath]
         put char i of L after tPath
      end repeat
   end repeat
end makePathArray


function solutionsFor cubeList
   -- takes a list of cubes and returns a list of all possible solutions
   
   -- configure the permutations of the cubes and the paths that might work
   setupStrings cubeList
   get pathsFor(cubeList)
   
   --return it
   
   if it is empty then return 0 & cr
   put the number of lines of it into pathCount
   makePathArray it
   
   -- pathArray[0] contains all the valid starting points
   repeat for each line L in pathArray[0]
      -- starting path:
      put "0" & L into thePath
      
      -- build the candidate list
      -- first four items are the colors used so far
      -- items 5- are the actual colors from each cube
      put empty into candidateList
      repeat for each line cubeLoop in stringList[1][L]
         repeat for each char C in cubeLoop
            put C & comma after candidateList
         end repeat
         put cubeLoop & cr after candidateList
      end repeat
      
      -- for each branch in the path:
      repeat for each line theBranch in pathArray[thePath]
         -- actual start of recursion:
         put solutionsAtLevel(2,thePath,theBranch,candidateList) after resultList
      end repeat
   end repeat
   if resultList is empty then return 0 & tab & pathCount & cr
   
   -- Remove the four items at the start of each solution
   -- that stored the tally of colors in each column
   put 0 into LC
   repeat for each line L in resultList
      add 1 to LC
      delete item 1 to 4 of L
      put L & cr after theReturn
   end repeat
   
   -- return the number of solutions
   -- the number of paths (this was for optimization)
   -- and the solutions themselves
   return LC & tab & pathCount & cr & theReturn
end solutionsFor



function solutionsAtLevel theLevel,thePath,theBranch,candidateList
   put empty into newCandidateList
   repeat for each line L in stringList[theLevel][theBranch]
      repeat for each line C in candidateList
         put checkit(C,L) after newCandidateList
      end repeat
   end repeat
   
   -- if the path is complete or all paths failed, return now
   if theLevel = cubeCount or newCandidateList is empty then return newCandidateList
   
   -- add the branch to the path, find the next branches, and call again
   put theBranch after thePath
   repeat for each line theBranch in pathArray[thePath]
      -- next step in the recursion
      put solutionsAtLevel(theLevel+1,thePath,theBranch,newCandidateList) after theReturn
   end repeat
   return theReturn
end solutionsAtLevel



function stringsFrom cubeFaces,dontPermute
   -- Takes a six-character representation of the faces of a cube
   -- and returns the unique loops of four sides (could be up to 24)
   
   -- The string 123456 represents this unfolding of the cube:
   --   1
   -- 623
   --   4
   --   5
   
   -- That translates to these four loops:
   -- 1245
   -- 1346
   -- 2356
   
   -- Each of those can be reversed ( x2 ) and rotated ( x4 )
   -- 3 x 2 x 4 = 24 possibilities
   
   -- Data is returned in an array:
   -- Z[0] is the three unique loops themselves
   -- Z[1] is up to eight loops based on 1245
   -- Z[2] is up to eight loops based on 1346
   -- Z[3] is up to eight loops based on 2356
   
   -- Start with a string representing all the patterns, with 7s for the CRs for convenience
   put "124574215721547154275421724517451275124713467613473461746137" \
         & "43167316471643764317235673265726537653276235753267356275623" into R
   
   -- Use replace to get the cube faces in place and to replace the 7s with CRs
   put cr after cubeFaces
   repeat with i = 1 to 7
      replace i with char i of cubeFaces in R
   end repeat
   
   -- Remove dupes from the entire list, but leave the empty lines so paths can work
   put sparseDeDupe(R) into R
   
   -- set up Z[0]
   put line 1 of R & cr & line 9 of R & cr & line 17 of R into Z[0]
   
   -- set up Z[1] through Z[3]
   put 0 into branchID
   repeat with i = 1 to 3
      if line i of Z[0] is empty then next repeat
      add 1 to branchID
      if dontPermute then
         put line i of Z[0] into Z[branchID]
      else
         put deDupe(line 8 * i - 7 to 8 * i of R)  into Z[branchID]
      end if
   end repeat
   put deDupe(Z[0]) into Z[0]
   return Z
end stringsFrom

function deDupe X
   -- remove any duplicate lines in X

   repeat for each line L in X
      if L is empty or L is among the lines of R then next repeat else put L & cr after R
   end repeat
   return R
end deDupe

function sparseDeDupe X
   -- make any duplicate lines in X blank
   -- no lines are deleted, so remaining data stays in the same line

   repeat for each line L in X
      if L is among the lines of R then put cr after R else put L & cr after R
   end repeat
   return R
end sparseDeDupe

function checkit X,Y
   -- Return X,Y & cr if it won't duplicate any colors
   -- items 1-4 of X are the total of the solution-in-progress
   
   repeat with i = 1 to 4
      -- Check colors in Y against items in X
      -- Fail if it already exists, add it if it doesn't
      if item i of X contains char i of Y then return empty
      put char i of Y after item i of X
   end repeat
   -- success. return X with Y added
   return X,Y & cr
end checkit


function randomCubes N
   -- a utility function, returns a set of N randomly colored cubes
   if N is empty then put 4 into N
   repeat with i = 1 to N
      repeat 9
         put char i of "ABCDEFGHIJKLMNOPQRSTUVWXYZ" after S
      end repeat
   end repeat
   repeat N
      repeat 6
         get random(length(S))
         put char it of S after R
         delete char it of S
      end repeat
      put cr after R
   end repeat
   return char 1 to -2 of R
end randomCubes

Brute Force Insanity

I have a puzzle called Instant Insanity. It consists of four cubes, with each face one of four colors (each cube has several faces that are colored the same). No one at the office has solved it, despite several of us  devising methods to help. 

Someone was fiddling with the cubes today, and after talking about the possible combinations, I realized a fairly simple brute force attack wouldn’t be too difficult to write. So I bet I could do it in ten minutes.

I lost. I took twenty minutes to write about sixty lines of code that didn’t find the solution.

Everything looked right, but it didn’t work. I looked at it again later, and after another twenty minutes I noticed my mistake. The problem was in the stringsFrom function. In a repeat, I used the variable I was iterating over instead of the iterator. The correct code was:

  repeat for each line L in R2
    put rotString(L) after R3

But I had this:


  repeat for each line L in R2
    put rotString(R2) after R3

And that’s all it takes to put a hurt on you — bad developer, no biscuit.
Updated to add the layout of the four cubes:

 G
BGB
 R
 W

 R
RWR
 B
 G

 W
RGW
 B
 R

 B
WWG
 R
 B

Here’s the correct version, along with all the utility functions that build the strings and check the solutions:

function stringsFrom X
  -- Takes a cross-shaped representation of the sides of a cube
  -- and returns all the possible unique loops of four sides (could be up to 24)

  -- First loop: across the t, and the bottom
  put char 1 to 3 of line 2 of X & char 2 of line 4 of X & cr after R

  -- Second loop: the vertical of the t
  repeat with i = 1 to 4
    put char 2 of line i of X after R
  end repeat

  -- Third loop loop: around the intersection of the t
  put cr after R
  put char 2 of line 3 of X & char 3 of line 2 of X & char 2 of line 1 of X & char 1 of line 2 of X & cr after R

  -- add the reverse of the strings
  repeat for each line L in R
    put rString(L) & cr after R2
  end repeat

  -- add the rotations of the strings
  repeat for each line L in R2
    put rotString(L) after R3
  end repeat

  -- de-dupe
   repeat for each line L in R3
     put 1 into R4[L]
   end repeat
   return the keys of R4
end stringsFrom

function cube x
-- Returns the data for the requested cube

   return line 5 * x - 4 to 5 * x - 1 of fld 1
end cube
 
function rString X
-- Takes a 4-character string
-- Returns the string and its reverse

   put cr before X
   repeat with i = 1 to 4
      put char i of line 2 of X before X
   end repeat
   return X
end rString
 
function rotString X
-- Takes a 4-character string
-- Returns the four rotations of it

   put X after X
   repeat with i = 1 to 4
      put char i to i + 3 of X & cr after R
   end repeat
   return R
end rotString
 

function checkit X
-- Takes a set of lines in a string, and returns true if they have
-- no columns with duplicate characters
-- Hard-coded to 4-character strings and "RGBW"
-- But will handle 2, 3, or 4 lines

   put the number of lines of X into LC
   repeat with i = 1 to 4
      put "RGBW" into T
      repeat with z = 1 to LC
         replace (char i of line z of X) with empty in T
      end repeat
      if length(T) > 4 - LC then return false
   end repeat
   return true
end checkit

I was surprised that checkit was seemingly fast. I tried arrays, which made more intuitive sense than using replace, and found that this was roughly twice as slow:

function checkit X
  -- Takes a set of lines in a string, and returns true if they have
  -- no columns with duplicate characters
  -- Handles arbitrary line length, number of lines, and characters

  repeat for each line L in X
    repeat with i = 1 to length(L)
      if T[i] contains char i of L then return false else put char i of L after T[i]
    end repeat
  end repeat
  return true
end checkit

Here’s the too-brute-force code. It builds a list of all the possible combinations, and then parses through them looking for one that works.

on mouseUp
  -- Takes four cube definitions in t format
  -- And finds any solution to the Instant Insanity puzzle

  -- Get the sets of strings for the cubes
  repeat with i = 1 to 4
    put stringsFrom(cube(i)) into stringList[i]
  end repeat

  -- Build all the candidate solutions
  put 1 into X
  repeat for each line L1 in stringList[1]
    repeat for each line L2 in stringList[2]
      repeat for each line L3 in stringList[3]
        repeat for each line L4 in stringList[4]
          put L1 & cr & L2 & cr & L3 & cr & L4 into T[X]
          add 1 to X
        end repeat
      end repeat
    end repeat
  end repeat

  -- Test each candidate to see if it works
  repeat for each element E in T
    if not checkit(E) then next repeat

    -- Success!
    put E into fld "solution" 
    exit to top
  end repeat
  -- Failure.

  put "fail" into fld "solution"
end mouseUp

Here’s a much better version that checks the combinations as it generates them, meaning that it will stop building a combination after two or three cubes if it has duplicate colors, and exits as soon as it finds a solution. Further optimizations are obviously possible, but this reduces the runtime from just under a second to about 30 milliseconds, so I’m done.

on mouseUp
  -- Takes four cube definitions in t format
  -- And finds any solution to the Instant Insanity puzzle

  -- Four nested repeats
  -- Each based on the set of strings for one cube

  repeat for each line L1 in stringsFrom(cube(1))
    repeat for each line L2 in stringsFrom(cube(2))

      -- If the first two cubes have duplicate colors,
      -- jump to the next option
      if not checkit(L1 & cr & L2) then next repeat
      repeat for each line L3 in stringsFrom(cube(3))

        -- If the first three cubes have duplicate colors,
        -- jump to the next option
        if not checkit(L1 & cr & L2 & cr & L3) then next repeat
        repeat for each line L4 in stringsFrom(cube(4))

          -- If the four cubes have duplicate colors,
          -- jump to the next option
          if not checkit(L1 & cr & L2 & cr & L3 & cr &  L4) then next repeat

          -- Otherwise, success!
          put L1 & cr & L2 & cr & L3 & cr & L4 into fld "solution" 
          exit to top
        end repeat
      end repeat
    end repeat
  end repeat
  put "fail" into fld "solution"
end mouseUp

A better way to calculate the day of the week

Look Like a Genius

Calculating the day of the week for historical date is impressive, but it isn’t as hard as it seems. Several methods have been shown to work and be performable by average humans. This is an improvement to one of the simplest methods.

The Doomsday Rule

Paraphrased from wikipedia:

The Doomsday rule or Doomsday algorithm is a relatively simple way to calculate the day of the week of a given date. It was devised by John Conway, drawing inspiration from Lewis Carroll’s work on a perpetual calendar algorithm. The algorithm takes advantage of the fact that several easy-to-remember dates fall on the same day each year; for example, 4/4, 6/6, 8/8, 10/10, 12/12, and the last day of February are all the same day of the week.

Conway’s original algorithm required dividing by 12 and 4, and remembering several intermediate values. It’s achievable, but not simple.

Odd+11

The Odd+11 rule simplifies the math, requiring nothing more than knowing if a number is odd, and adding 11.

The Difficulty

The Doomsday Rule and the Odd+11 update both start with the actual day of the week. From the Wikipedia article:

Suppose that you want to find the day of week that the September 11, 2001 attacks on the World Trade Center occurred. The century anchor was Tuesday, and Doomsday for 2001 is one day beyond, which is Wednesday. September 5 was a Doomsday, and September 11, six days later, fell on a Tuesday.

Having converted to the day of the week, adding numbers to it can be tough — what day of the week is 11 days after a Friday? Further, the methods require remembering the century day while doing the year calculation (per the Wikipedia article), or remembering the century while doing the year calculation and then evaluating the actual day of the week — the doomsday — from both.

Finally, to find the desired date, work theough the weeks mentally (perhaps backwards). This can be simplified by memorizing additional doomsdays. Conway’s mnemonics are very useful, but they only cover one date per month.

The Modification

Instead of starting with a day of the week for the century, this method delays conversion to the day of the week until the last step. Before that, everything is simply in terms of numbers. This avoids having to do week-based calculations, memorizing additional doomsdays, or remembering multiple intermediate steps.

Two variants of the algorithm are given. The first works in the same order as the Conway algorithm, starting from the year and century and then adding in the month and finally subtracting the day. The second algorithm starts with the month, then subtracts the day, then adds in the century and year. This allows the user to process the information in the order that it is ordinarily given: March 23rd, 1974 (a Saturday) — although the algorithm has a few more steps.

Century First

Here is an example for January 18, 1936:

  1. 1900s: start with 8
  2. Add the year: 8 + 36 = 44
  3. 44 is even so don’t add 11
  4. 44/2 = 22
  5. 22 is even  so don’t add 11
  6. Add the month “doomsday” number for January: 22 + 3 = 25
  7. It’s January in a leap year, so 25 + 1 = 26
  8. Subtract the day: 26 – 18 = 8
  9. Take the 7s complement — this is the number of days until the next multiple of 7, which is probably the easiest way to produce it. Technically it is: (7 – 8 mod 7) mod 7 = 6
  10. Convert to a day of the week starting from Sunday = 0, so 6 = Saturday.

Here is a flowchart:

20130409-221650.jpg

Month First

Here is an example for September 16th, 2065:

  1. Start with the month number (the “doomsday” date for the month): September = 5
  2. Subtract the day. 16 > 5, so first add a multiple of 7: 5 + 14 = 19, 19 – 16 = 3
  3. It’s not January or February in a leap year, so don’t add 1
  4. 3 is odd, so: 3 + 7 = 10
  5. 10 * 2 = 20
  6. Add the century number for 2000s: 20 + 24 = 44
  7. Add the year: 44 + 65 = 109
  8. 109 is odd, so: 109 + 11 = 120
  9. 120/2 = 60
  10. 60 is even, so don’t add 11
  11. Take the 7s complement — this is the number of days until the next multiple of 7, which is probably the easiest way to produce it. Technically it is: (7 – 60 mod 7) mod 7 = 3
  12. Convert to a day of the week starting from Sunday = 0, so 3 = Wednesday.

Here is a flowchart:

20130409-221828.jpg

Roger Ebert Wins the Cartoon Caption Contest : The New Yorker

Quantity does not guarantee quality. But as Malcolm Gladwell has pointed out, in most fields, the more you do, the better you get at it. And this is true of Cartoon Caption Contests: In 2009, the creativity researcher Keith Sawyer interviewed a number of winners and found that,

cartoon contest winners usually generate lots of captions. Studies of creativity have shown that quantity breeds quality—what I call the productivity theory, because high productivity corresponds to high creativity.

via Roger Ebert Wins the Cartoon Caption Contest : The New Yorker.

And people who buy more lottery tickets are more likely to win the PowerBall. Tell me that people who send in more captions are more likely to win on a per-submission basis (the cited research doesn’t say that) and then you might actually be saying something.

I’m sad that Roger Ebert is gone.