Rulers!

Rulers have been around a long time for measurement but are they efficient tools? A typical ruler will have many pairs of marks between which a specific length can be measured and this could be viewed as inefficient if, for example, the cost of making marks was very costly.

The coverage of rulers given here is the result an interest inspired by the following old Sunday Times puzzle:

Sunday Times Brain Teaser 560

Published on 26 March 1972

The draper sells ribbon by the inch. His counter is exactly 100 inches
long, and he has marked it off into sixteen segments: six of 11 inches
together near the middle (he must think 11 inches make a foot!), two of
6 inches, three of 5 inches, one of 3 inches, and four of 1 inch. That
way he can measure any number of inches up to 100, by picking the right
pair of marks.

Of course one of the 1-inch lengths has to be at one end, or he wouldn’t
be able to measure 99 inches. In fact, two of them are at the same end,
which is how he measures 98 inches. Can you work out how the segments
are arranged?

Because we are told the positions of the one and six inch segments, it is not too hard to solve this puzzle in Python:


from itertools import combinations, permutations

def unique_permutations(seq):
  """
  generate unique permutations of sequence <s>
  using Knuth's 'Algorithm L'
  """

  seq = sorted(seq)
  # pre-calculate the loop indices for speed
  i_indexes = range(len(seq) - 1, -1, -1)
  k_indexes = i_indexes[1:]

  while True:
    yield tuple(seq)

    # working backwards from the last-but-one index, to
    # find the index of the first decrease in value
    for k in k_indexes:
      if seq[k] &lt; seq[k + 1]:
        break
    else:
      # the seq is weakly decreasing so we are done
      return

    # working backwards starting with the last item
    # find the first one greater than the one at k
    k_val = seq[k]
    for i in i_indexes:
      if k_val &lt; seq[i]:
        break

    (seq[k], seq[i]) = (seq[i], seq[k])
    # reverse the part after but not including k
    seq[k + 1:] = seq[-1:k:-1]

# generate the cumulative sum of a sequence 
def cumulative_sum(x, s=0):
  for i in x:
    s += i
    yield s

# the marked segment lengths
segs = [11, 11, 11, 11, 11, 11, 6, 6, 5, 5, 5, 3, 1, 1, 1, 1]

# leave out the 11's and the last two 1's (0 will be a marker
# for where to put the 11's back in)
pv = (0,) + tuple(x for x in segs[:-2] if x != 11)

# consider all arrangements of these segments 
for p in unique_permutations(pv):
  # now put the 1's and the 11's back in
  i = p.index(0)
  pp = (1, 1) + p[:i] + (11,) * 6 + p[i + 1:]
  
  # create a ruler with these segments
  marks = (0,) + tuple(cumulative_sum(pp))
   for 
  # now find the set of measurements available
  v = set(b - a for  a, b in combinations(marks, 2))
  
  # are all values in 1 .. 100 available?
  if v == set(range(1, 101)):
    print((1, 1) + pp, marks)
</s>

from itertools import combinations, permutations

def unique_permutations(seq):

"""

generate unique permutations of sequence <s>

using Knuth's 'Algorithm L'

"""

seq = sorted(seq)

# pre-calculate the loop indices for speed

i_indexes = range(len(seq) - 1, -1, -1)

k_indexes = i_indexes[1:]

while True:

yield tuple(seq)

# working backwards from the last-but-one index, to

# find the index of the first decrease in value

for k in k_indexes:

if seq[k] < seq[k + 1]:

break

else:

# the seq is weakly decreasing so we are done

return

# working backwards starting with the last item

# find the first one greater than the one at k

k_val = seq[k]

for i in i_indexes:

if k_val < seq[i]:

break

(seq[k], seq[i]) = (seq[i], seq[k])

# reverse the part after but not including k

seq[k + 1:] = seq[-1:k:-1]

# generate the cumulative sum of a sequence

def cumulative_sum(x, s=0):

for i in x:

s += i

yield s

# the marked segment lengths

segs = [11, 11, 11, 11, 11, 11, 6, 6, 5, 5, 5, 3, 1, 1, 1, 1]

# leave out the 11's and the last two 1's (0 will be a marker

# for where to put the 11's back in)

pv = (0,) + tuple(x for x in segs[:-2] if x != 11)

# consider all arrangements of these segments

for p in unique_permutations(pv):

# now put the 1's and the 11's back in

i = p.index(0)

pp = (1, 1) + p[:i] + (11,) * 6 + p[i + 1:]

# create a ruler with these segments

marks = (0,) + tuple(cumulative_sum(pp))

for

# now find the set of measurements available

v = set(b - a for a, b in combinations(marks, 2))

# are all values in 1 .. 100 available?

if v == set(range(1, 101)):

print((1, 1) + pp, marks)

</s>

This gives two solutions for the positions of the segments, one being:

(1, 1, 3, 5, 5, 5, 11, 11, 11, 11, 11, 11, 6, 6, 1, 1)

and the second its reverse. If we rewrite this in terms of the positions of the marks (including the two ends of the ruler) we obtain a ruler with seventeen marks:

[0, 1, 2, 5, 10, 15, 20, 31, 42, 53, 64, 75, 86, 92, 98, 99, 100]

But could we have solved this problem if we had not been given the positions of some of the segments? Moreover, although we have a solution for measuring all integer values between 0 and 100 inclusive with a seventeen mark ruler, is it possible to do this with less than seventeen marks?

My first step in trying to answer these questions was with this Python program:


def marks(ruler_length, no_of_marks, ruler, mark_nbr):
  # are we at the last but one mark
  if mark_nbr == no_of_marks - 1:
    # add the mark at the end of the ruler
    ruler.append(ruler_length)
    # and check that all lengths can be measured
    m = [0] * ruler_length
    s = set()
    for a, b in combinations(ruler, 2):
      m[b - a - 1] = 1
    if all(x for x in m):
      yield ruler
  else:
    # position the next mark on the ruler and continue
    for i in range(ruler[-1] + 1, ruler_length):
      yield from marks(ruler_length, no_of_marks, ruler + [i], mark_nbr + 1)

# increase the ruler length until there are no solutions
# and return the maximum length for a solution
def get_len(no_of_marks, ln):
  for ruler_len in count(ln):       
    ruler = [0, 1]
    for r in marks(ruler_len, no_of_marks, ruler, 2):
      break
    else:
      return ruler_len - 1

# find the maximum ruler length for each number of marks
t0 = time_ns()
ruler_len = 3
for no_of_marks in count(3):
  ruler_len = get_len(no_of_marks, ruler_len)
  t = time_str(time_ns() - t0)
  print(f"No of marks: {no_of_marks:2} -&gt; max length {ruler_len:2} {t}")

def marks(ruler_length, no_of_marks, ruler, mark_nbr):

# are we at the last but one mark

if mark_nbr == no_of_marks - 1:

# add the mark at the end of the ruler

ruler.append(ruler_length)

# and check that all lengths can be measured

m = [0] * ruler_length

s = set()

for a, b in combinations(ruler, 2):

m[b - a - 1] = 1

if all(x for x in m):

yield ruler

else:

# position the next mark on the ruler and continue

for i in range(ruler[-1] + 1, ruler_length):

yield from marks(ruler_length, no_of_marks, ruler + [i], mark_nbr + 1)

# increase the ruler length until there are no solutions

# and return the maximum length for a solution

def get_len(no_of_marks, ln):

for ruler_len in count(ln):

ruler = [0, 1]

for r in marks(ruler_len, no_of_marks, ruler, 2):

break

else:

return ruler_len - 1

# find the maximum ruler length for each number of marks

t0 = time_ns()

ruler_len = 3

for no_of_marks in count(3):

ruler_len = get_len(no_of_marks, ruler_len)

t = time_str(time_ns() - t0)

print(f"No of marks: {no_of_marks:2} -> max length {ruler_len:2} {t}")

which considers rulers with increasing numbers of marks, to find their maximum lengths. It produces the following results:

\[\begin{array}{|c|c|r|}\hline Number\;of\;Marks & Max\;Ruler\;Length &Time\;(ms) \\
\hline 3 & 3 & 0 \\
\hline 4 & 6 & 0 \\
\hline 5 & 9 & 1 \\
\hline 6 & 13 & 2 \\
\hline 7 & 17 & 7 \\
\hline 8 & 23 & 99 \\
\hline 9 & 29 & 1,727 \\
\hline 10 & 36 & 38,734 \\
\hline 11 & 43 & 701,800 \\
\hline \end{array}\]

Rulers!

Recent Posts

Recent Comments

Archives

Categories

Meta