Programming challenge #1: 3n + 1

One of the reasons I joined Near Infinity is the annual allowance of $500 for books, subscriptions, and software. This made it a no-brainer to get a copy of "Programming Challenges" by Steven Skiena and Miguel Revilla. I just wanted a challenge which wasn't following ornate business logic or deploying said software. The book is full solid but (hopefully :) tractable technical challenges. I really like Ruby and decided to use it despite the supported languages being C, C++, Java, and Pascal.

The first problem is called "The 3n + 1 problem." The core idea is to reduce a positive number to one by evaluating these steps:

• one: stop
• even number: divide by two
• odd number: multiply by three and then add one

def step(val)
  if (val == 1)
    val
  elsif (val % 2 == 0)
    val / 2
  else
    val * 3 + 1
  end
end

The next piece is to count the number of steps taken. The rules are clear that the initial number and one are both to be counted as steps. Basically, count the posts in the fence, not the gaps.

def countSteps(val)
  steps = 1
  until (val == 1) do
    val = step(val)
    steps = steps + 1
  end
  steps
end

The final piece is to run a series of numbers through the code, and report which number required the most steps.

def maxSteps(range)
  max = 0
  range.each do |val|
    max = [max, countSteps(val)].max
  end
  max
end

Large numbers passing through this code won't have much effect on memory or stack usage; it looks CPU bound. I wondered how easy it would be to balance CPU usage with memory usage. Since each positive number always needs the same number of steps to reduce to one, it's safe to save the number with its step count in a map. While processing steps, check each result to see if it has been cached. A cache hit results in no further processing, except to cache the step count of the argument. The memory usage will grow with the number of unique arguments.

# elsewhere: @chain = { 1 => 1 }
def computeCycles(val)
  spin = 0
  origVal = val

  until (@chain[val]) do
    val = step(val)
    spin = spin + 1
  end

  unless (origVal == 1)
    @chain[origVal] = @chain[val] + spin 
  end

  @chain[origVal]
end

Here are some tacky metrics produced running on a cold cache while processing 1..200.

[...]
10 => spins used/avoided, %avoided, cache size = 28/49 -- 64, 10
[...]
100 => spins used/avoided, %avoided, cache size = 803/2439 -- 75, 100
[...]
200 => spins used/avoided, %avoided, cache size = 1393/7225 -- 84, 200

So, to wrap up Ruby was a mixed blessing here. Fortunately I was able to do non-trivial things without wasting time & tendons on basic infrastructure. Unfortunately the processing website doesn't accept Ruby :( Soon I hope to tackle more of these challenges ... maybe using Groovy and Lua.