New Scientist Enigma 1656

I was flipping through an issue of New Scientist over lunch, and came across their Enigma column. It seemed like a pretty simple computational problem, so I thought I’d give it a try. Here’s the problem (link to New Scientist site):


Five integers

I have written down five single-digit positive integers.

The sum of the five integers is divisible by the fifth integer, but not by any of the first four. The sum of the first four integers is divisible by the fourth but not by any of the first three. The sum of the first three integers is divisible by the third but not by either of the first two. The sum of the first two integers is divisible by the second but not by the first.

List the five integers in the order in which I have written them down.


My code follows. It does the problem backwards, starting with a list of all 2-digit combinations, then deleting any that don’t meet the criteria. Then it expands the survivors to three digits, then eliminates any that don’t pass the test, etc. up to five digits.

And the output looks like:

For length 2
[[2, 1], [3, 1], [4, 1], [4, 2], [5, 1], [6, 1], [6, 2], [6, 3], [7, 1], [8, 1], [8, 2], [8, 4], [9, 1], [9, 3]]
For length 3
[[4, 2, 1], [4, 2, 3], [6, 2, 1], [6, 3, 1], [8, 2, 1], [8, 2, 5], [8, 4, 1], [8, 4, 2], [8, 4, 3], [8, 4, 6], [9, 3, 1], [9, 3, 2], [9, 3, 4]]
For length 4
[[8, 4, 2, 1], [8, 4, 2, 7], [8, 4, 6, 1], [8, 4, 6, 3], [8, 4, 6, 9], [9, 3, 4, 1]]
For length 5
[[8, 4, 6, 3, 1]]

Adding a MogileFS proxy

As noted previously, I’m using MogileFS as the data store for some high(-ish)-performance computing. So far, it does the job without complaints. I haven’t benchmarked it, but I’m not asking that much.

One issue is that it uses its own proprietary access protocol … sortof. A simple Mogile read goes something like:

  1. Computer A decides it wants a file from the Mogile cluster. It contacts one of the trackers using the Mogile protocol. [Computer A needs to know the hostnames of the tracker(s) in advance.]
  2. The tracker has a think, checks the database, and returns the path to the requested file on one of the storage hosts. This path is a normal URL. It passes this URL back to the client.
  3. Computer A uses HTTP to get the file from that URL on the storage host.

The fly in the ointment, of course is that the original client needs to speak Mogile to the tracker. I’m using a hacked version of SeattleRB’s Mogile-client Ruby gem in all of my various programs and clients to access Mogile directly.

One of those programs is a web front-end for browsing the data. When it wants to insert a Mogile asset into a web page (an image, typically), it will contact the tracker, get the storage URL, and insert it directly into the page, so you end up with HTML that contains code like:


<img src="http://my.mogile.storaged:7500/dev1/0/000/405/0000405859.fid">

The problem is that all of my Mogile trackers and storage nodes are behind a firewall (as they should be). When I’m on campus, this works fine, as my desktop can see both the web server and the storage nodes.

When I work off campus, I can use an SSH tunnel to get to the web server, but all of the storage node paths break terribly.

I’d like to add a web proxy, preferably running on the same web server as my web app, which can handle the Mogile requests. Instead of returning raw Mogile URLs, the web app can pass paths to the proxy, the proxy can get the data from Mogile, and send it back as HTTP. As my web app is mostly for browsing, the proxy can even be read-only.

How I did it

As a first attempt, I was more interested in getting a solution running than any sense of performance. As my web app is in Rails 3, I knew I could basically delegate a path to a separate, self-contained Rack server. The Resque control panel does this, for example.

As a sketch, then, I want any path of the form:


http://webserver.com/mogproxy/some/key/something

to return whatever Mogile has stored under the key /some/key/something

The first step was to add a route to the application in routes.rb:

I put my application code at lib/mogproxy/ which resulted in a bit of a search on autoloading files and require paths. The solution I arrived at looked something like this in application.rb

It may be possible to do away with the require through clever use of the autoload path, but I didn’t feel the automatic-ness was really worth it. Note the require has to go at the end after the autoload_path is set.

The application below is written in Sinatra because I’ve used it before and it’s handy. It’s pretty simple — take whatever path comes in and look it up in Mogile. Return the result.

[Yes, I know, my regexp-fu is weak…]

As a side note, the MogileModule::Mogilable and mog bits are code I wrote to make a class (*cough* global) variable Mogile client instance, which can be configured once and used throughout the application.

It’s hardly efficient because it loads the asset from Mogile then spits it back out at the client. And the error checking is basically absent. But it works.

On the other side, I then rewrote my client code to return “/mogproxy/….” paths instead of looking up the mog paths themselves.

Resistor search in Ruby

Here’s a short snippet I wrote the other day. I think it’s a good illustration of Ruby’s potential for short scripts.

I needed to set the resistor divider to get 5.4V out of an adjustable LDO regulator (a REG102-A). The output voltage is set as:

V_{out} = left( 1 + frac{R1}{R2}right) V_{ref}

For the REG102, V_{ref} = 1.26V, and the bias current was about right if R1 and R2 were both in the order of 1-10K.

On the other hand, I had a big bag of completely unsorted SMD resistors. Somewhere in there was a nice combination that would give me the voltage I wanted.

The script reads a list of resistor values (one per line) from a file (by default ‘r.txt’). The output looks like:

Have these resistors: 0.91, 2.2, 4.7, 6.81, 8.06, 10.0, 11.5, 15.0, 22.0, 24.9, 30.0, 33.0, 35.7, 40.2, 42.2, 47.0, 51.0, 53.6, 56.0, 68.0, 100.0, 215.0, 226.0
Searching for Vtarget = 5.4
R1	R2	vout	error
24.90	8.06	5.15	-0.05
68.00	22.00	5.15	-0.05
6.81	2.20	5.16	-0.04
35.70	11.50	5.17	-0.04
47.00	15.00	5.21	-0.04
215.00	68.00	5.24	-0.03
15.00	4.70	5.28	-0.02
22.00	6.81	5.33	-0.01
33.00	10.00	5.42	+0.00
226.00	68.00	5.45	+0.01
100.00	30.00	5.46	+0.01
51.00	15.00	5.54	+0.03
40.20	11.50	5.66	+0.05

The code loads the resistors from the file, and removes duplicates, then calculates Vout for every permutation. It then deletes any permutations which don’t get within 5% of the desired voltage, and sorts and prints the results.

As a side note, it doesn’t matter than the resistors are given in Kohms (or Ohms, or MOhms, etc) because they’re divided in the script, as long as they’re in the same units.

Yes, it’s non-optimized because it does build an enormous list of possibilities, then throws the vast majority away. Even a simple permutation like not calculating Vout if R2 > R1 would eliminate many possible pairings.

But, there you go.

#!/usr/bin/env ruby

TARGETV = 5.4

filename = ARGV.pop || "r.txt"
r = ($File.open( filename ) { |f| f.readlines.map { |l| l.to_f } }).sort.uniq

puts "Have these resistors: " + r.join(', ')
puts "Searching for Vtarget = #{TARGETV}"

vals =  r.permutation(2).map { |res|
  vout = 1.26 * (1 + res[0]/res[1])
  error = (vout-TARGETV)/TARGETV 
  res+[vout, error]
}.delete_if { |res| (res[3]).abs > 0.05
}.sort { |a,b| a[2] <=> b[2] }


puts %w( R1 R2 vout error ).join("t")
vals.each { |v|
  puts "%.2ft%.2ft%.2ft%+.2f" % v
}

Allowing Ruby Benchmark reports to return values

I’ve recently started using Benchmark to record basic timings. It’s hardly profiling, more just a running record of where the time goes.

One annoyance (for me) was that Benchmark::report returns timing information, not the return value from the block being benchmarked. This means adding benchmarking to a function like:

def a_function
  a = an_expensive_function
  b = another_expensive_function
  c = a_third_function(a,b)
  puts c
end

Requires pre-defining a,b,c outside of the report blocks … otherwise they get scoped out:

require 'benchmark'

def a_function
  Benchmark.bm do |bm|
    a = b = c = nil

    bm.report("A") { a = an_expensive_function }
    bm.report("B") { b = another_expensive_function }
    bm.report("C") { c = a_third_function(a,b) }
    puts c
  end
end

which is an annoyance.

I’ve redefined Benchmark::report as:

module Benchmark
  class Report
    def report( label="", *format, &blk )
      retval = nil
      item( label, format ) { retval = blk.yield }
      retval
    end
  end
end

Which lets you do the (slightly more intuitive):

def a_function
  Benchmark.bm do |bm|
    a = bm.report("A") { an_expensive_function }
    b = bm.report("B") { another_expensive_function }
    c = bm.report("C") { a_third_function(a,b) }
    puts c
  end
end