Perfect ruler search

Question

Definitions:

A sparse ruler, or simply a ruler, is a strict increasing finite sequence of nonnegative integers starting from 0, called marks.

A ruler is complete if the set of all distances it can measure is {1,2,3,...,k} for some integer k > 0.

A ruler is perfect if it is complete, and no complete ruler with the same length possesses fewer marks.

(The definitions are taken from OEIS A103294.)

Example:

The perfect rulers of length 5 are

[0, 3, 4, 5], [0, 2, 4, 5], [0, 1, 3, 5], [0, 1, 2, 5].

To simplify the notation, we will write them as binary strings:

100111, 101011, 110101, 111001.

The mapping should be clear: set the bit in position k of the 0-based string, read from left to right, if k is a mark on the ruler.

As you might have guessed, we want to create a list of all perfect rulers with a given length of n. The list should be an orderly one. The required order is given by interpreting the binary strings as integers and then taking the natural order.

In our example, for n = 5, the decimal integer representation of the rulers is [39, 43, 53, 57]. A second example of the three representations described above is, for n = 6:

[[0, 2, 5, 6], [0, 1, 4, 6]]
[1010011, 1100101]
[83, 101]

Output:

The program's output should be only the binary strings, as a comma-separated list, or by line-by-line output, whichever seems suitable, for any given positive integer n. So for n = 6 this might be:

1010011
1100101

Perfect rulers are the gold nuggets among the binary strings. Find them!

This is code-golf, so each language's shortest code in bytes wins.

Answer 1

K (ngn/k), 44 43 39 bytes

*<==!/+/'\{'[#x^/-/:/2#,&:]_+!x:'2}@!1+

Try it online!

                                    !1+ range 0..n
          {                       }@    complete rulers:
                            +!x:'2        n+1-d range (0...)..(1...)
           '[             ]_              keep where
                 -/:/2#,&:                  distances
             #x^/                           superset of range 0..n
   =!/+/'\                              group by #marks
*<=                                     min

Answer 2

Jelly, 16 bytes

‘ŒPŒcIQLƲÐṀLÐṂṬṚ

A monadic Link that accepts the ruler length, \$N\$, and yields all perfect rulers of length \$N\$ as lists of binary marks ordered numerically.

Try it online! Or see the test-suite.

How?

If we can assert that a ruler has implicit marks of \$0\$ and \$N\$, which I believe is part of the definition of a sparse ruler, then we know that \$N\$ is always in the set of all distances a ruler can measure and hence \$k \ge N\$. At the same time, we cannot hope to measure any distance greater than \$N\$ (as that is the length of our ruler!), so \$k=N\$. Furthermore, no ruler of length less than \$N\$ can make as many measurements (they can't measure \$N\$).

Thus I believe we can just look for those rulers of length up to \$N\$ with maximal measuring capability (i.e. the set \$\{1,2,\cdots,N\}\$) and then filter these rulers down to those with the fewest marks. (Please correct me if I've made a false assertion!)

‘ŒPŒcIQLƲÐṀLÐṂṬṚ - Link: non-negative integer, N
‘                - increment {N} -> N+1
 ŒP              - powerset {[1..N+1]}
                   -> [[],[1],[2],...,[N+1],[1,2],[1,3],...,[1..N+1]]
                      i.e. all rulers of length <=N where the 0-mark is represented
                           by a value of 1 or higher while no value may exceed N+1
                           (e.g. [1,3,8] & [2,4,9] both represent [0,2,7] when N>=8)
                           Note that there is, therefore, exactly one representation
                           present of every sparse-ruler of length N
         ÐṀ      - keep those maximal under:
        Ʋ        -   last four links as a monad:
   Œc            -     unordered pairs
     I           -     forward deltas
      Q          -     deduplicate
       L         -     length
            ÐṂ   - keep those minimal under:
           L     -   length
              Ṭ  - untruth (convert to their binary representations)
               Ṛ - reverse (equivalent to sorting by binary representation)

Answer 3

JavaScript (ES7), 139 bytes

Returns the rulers as a space-separated string of bit-masks.

f=(n,N)=>(g=q=>--q?g(q)+((h=j=>~j?q>>j&1**h(j-1)&&a.push(a.map(x=>h|=1<<j+~x)&&j)<N:a=[])(n)+h>>n?q.toString(2)+" ":""):"")(2<<n)||f(n,-~N)

Try it online!

Slower but not limited by the size of the call stack: 140 bytes

Commented

f = (                   // outer recursive function taking:
  n,                    //   n = input
  N                     //   N = exclusive upper bound for the number of
) =>                    //       marks in the ruler (initially undefined)
( g = q =>              // inner recursive function taking q
  --q ?                 // decrement q; if it's not zero:
    g(q) +              //   append the result of a recursive call
    (                   //
      ( h = j =>        //   h is a recursive function taking j
                        //   NB: h is reused as a bitmask to test the ruler
        ~j ?            //   if j is not equal to -1:
          q >> j &      //     test the j-th bit of q
          1 ** h(j - 1) //     do a recursive call to h with j-1
          && a.push(    //     if the j-th bit is set, push j in a[] and
            a.map(x =>  //     for each value x in a[] (before the push):
              h |= 1 << //       update h by setting the bit at index j-x-1
                j + ~x  //       for a valid ruler, h will end up with all
            ) && j      //       bits from 0 to n-1 set to 1
          ) < N         //     test whether a[] has less than N elements
        :               //   else (end of recursion):
          a = []        //     initialize a[] to an empty array
      )(n) +            //   invoke h with n -> returns 1 if a.length < N
      h >> n ?          //   add this to h; if the n-th bit is set:
        q.toString(2)   //     success -> append the ruler as the binary
        + " "          //     representation of q followed by a space
      :                 //   else:
        ""              //     append nothing
    )                   //
  :                     // else (q = 0):
    ""                  //   stop
)(2 << n)               // initial call to g with q = 2 << n
|| f(n, -~N)            // if no ruler was found, try again with N+1

Answer 4

05AB1E, 33 bytes

>EÝN.Æεœ.Δ.ÆíÆêILQ}}®KZdiIÝδå{që\

Try it online or verify \$n\$ in the range 1-7.

If binary-strings are mandatory, a J can be added after the { for +1 byte:
Try it online or verify \$n\$ in the range 1-7.

Explanation:

>                  # Increase the (implicit) input by 1
                   # (for edge-cases n=1 and n=2 that have larger output-rulers)
 E                 # Loop `N` in the range [1,input+1]:
  Ý                #  Push a list in the range [0,(implicit) input]
   N.Æ             #  Pop and push a list of all `N`-sized combinations
      ε            #  Map over each inner list:
       œ           #   Get all permutations of this list
        .Δ         #   Get the first that's truthy for:
                   #   (or -1 if none are truthy)
          .Æ       #    Pop the list and get all combination-pairs
            í      #    Reverse each inner pair
             Æ     #    And then reduce each pair by subtracting
                   #    (these are all sizes this ruler can measure)
              ê    #    Uniquify and sort it
               IL  #    Push a list in the range [1,input]
                 Q #    Check that the two lists are the same
         }         #   Close the find_first
      }            #  Close the map
       ®K          #  Remove all -1s
         Zdi       #  If valid rulers have been found:
            IÝ     #   Push a list in the range [0,input] again
              δ    #   Apply double-vectorized:
               å   #    Check for each value in [0,input] if it's in the ruler
                   #   (we now have a list of binary-lists)
                {  #   Sort this list of binary-lists
                 q #   Stop the program
                   #   (after which the list of binary-lists is output implicitly)
           ë       #  Else:
            \      #   Discard the empty list (so we can use the implicit input
                   #   for the next iteration again)

Answer 5

Pyth, 26 bytes

.mSbf.Amsm}`11%hd>TkQQ^`Th

Try it online!

Alternatively +1 byte to seperate by newlines.

Explanation

.mSbf.Amsm}`11%hd>TkQQ^`ThQ    # implicitly add Q
                               # implicitly assign Q = eval(input())
                       `T      # string "10"
                      ^  hQ    # Q+1 times repeated cartesian product (this generates all binary strings of lenght Q+1)
    f                          # filter list on lambda T
       m             Q         #   map range(Q) over lambda d
         m          Q          #     map range(Q) over lambda k
          }`11                 #       check whether "11" is in
              %hd              #       the string made from taking every (d+1)-th character of
                 >Tk           #       T[k:]
        s                      #     sum (check if at least one boolean is true) the following
     .A                        #   check if all items in list are truthy
.m                             # filter for elements which minimize lambda b
  Sb                           #   sort the characters in b

Answer 6

Ruby, 86 bytes

->n{(1..2<<n).select{|x|(1..n).all?{|y|x&x<<y>0}}.group_by{|x|x.digits(2).sum}.min[1]}

Try it online!

First check which numbers are complete rulers, by means of arithmetic shift and bitwise and, then group by number of marks (popcount) and take the minimum.

Answer 7

Charcoal, 34 bytes

Ｎθ≔ＥΦＸ²⊕θ⌊＆ι×ιＸ²…·¹θ⍘ι²ηΦη⁼Σι⌊ＥηΣλ

Try it online! Link is to verbose version of code. Explanation: Uses @GB's bitwise And trick to find complete rulers.

Ｎθ

Input n.

≔ＥΦＸ²⊕θ⌊＆ι×ιＸ²…·¹θ⍘ι²η

Check all numbers up to 2ⁿ⁺¹ to see which ones correspond to complete rulers, then convert those to binary strings.

Φη⁼Σι⌊ＥηΣλ

Output those binary strings with the equal fewest number of 1s.