Enigmatic Code

Programming Enigma Puzzles

Enigma 1697: Binary palindrome

From New Scientist #2864, 12th May 2012 [link]

I have before me a number, which when written in binary is palindromic and has n digits. If I told you the value of n, and you wrote a list of all the possible palindromic binary numbers of length n, your list would have n numbers in it.

If your list was in ascending numeric order, and I told you the difference between my number and the next higher number in the list, you would be able to identify my number.

What is my number, in decimal form?

[enigma1697]

Advertisements

7 responses to “Enigma 1697: Binary palindrome

  1. Jim Randell 9 May 2012 at 5:54 pm

    Here’s my initial attempt in Python. It runs in 39ms.

    from itertools import count
    from collections import defaultdict
    from enigma import printf
    
    # convert n to a binary string
    def base2(n):
      return '{:b}'.format(n) # or bin(n)[2:]
    
    # check the conditions
    def check(n, ps):
      # check there are n numbers
      if len(ps) != n: return False
      # find the differences
      d = defaultdict(list)
      for i in range(n - 1):
        d[ps[i + 1] - ps[i]].append(ps[i])
      # find unique differences
      u = 0
      for (k, v) in d.items():
        if len(v) > 1: continue
        printf("{v[0]} [n={n} {ps} d={k}]")
        u += 1
      # check there is only one unique difference
      return u == 1
    
    # generate binary palindromes, and accumulate them by length
    (n, ps, qs) = (1, [], [])
    for i in count(1):
      s = base2(i)
      l = len(s)
      r = s[::-1]
      if l > n:
        # check even length palindromes
        if check(2 * n, ps): break
        # and odd length palindromes
        if check(2 * n + 1, qs): break
        # reset the accumulators
        (n, ps, qs) = (l, [], [])
      ps.append(int(s + r, 2))
      qs.extend((int(s + '0' + r, 2), int(s + '1' + r, 2)))
    

    Solution: The number is 189.

    • Jim Randell 9 May 2012 at 6:51 pm

      Initially I wrote this only to check even-length binary palindromes, and then added in odd-length binary palindromes later. Although the answer can not be an odd-length palindrome as they must always come in pairs, so the total number of binary palindromes for a given odd-length must always be even, so I could have stuck with my original code. (Just take out all the qs stuff). It doesn’t make any difference to the run time anyway.

      A little bit more analysis tells you exactly what the only possibility for n is.

      • Jim Randell 10 May 2012 at 10:41 pm

        Here’s a variation that only checks even length binary palindromes.

        from collections import defaultdict
        from enigma import flatten, printf
        
        # generate lists of binary digits to make binary palindromes from
        # (each element is the first half of the palindrome)
        def generate():
          # initial list
          l = [ '1' ]
          while True:
            yield l
            # make the next list of elements
            l = flatten((i + '0', i + '1') for i in l)
        
        def check(l):
          # check there are the right number of elements
          if 2 * len(l[0]) != len(l): return False
          # turn each element into the integer representation of a binary palindrome
          l = list(int(p + p[::-1], 2) for p in l)
          # find the differences between the integers
          d = defaultdict(list)
          for i in range(len(l) - 1):
            d[l[i + 1] - l[i]].append(l[i])
          # find unique differences
          u = list((k, v[0]) for k, v in d.items() if len(v) == 1)
          # if there's only one, we've found a solution
          if len(u) != 1: return False
          printf("{u[0][1]} [n={n} {l} d={u[0][0]}]", n=len(l))
          return True
        
        # find the first list of palindromes that satisfies the conditions
        any(check(l) for l in generate())
        
  2. Brian Gladman 9 May 2012 at 8:57 pm

    Here is my version

    from itertools import count
    from collections import defaultdict
    
    for no_digits in count(1):
      # list for palindromes of length 'no_digits'
      l = []
      # number form is '1abc...cba1' where abc.. is a number in
      # the range 2 ** ((no_digits - 1) // 2) - but if n is odd
      # we have to remove a duplicated centre digit
      len_upc = (no_digits - 1) // 2
      for i in range(2 ** len_upc):
        # upper half of centre    
        sf = ('{:0' + str(len_upc) + 'b}').format(i)
        # lower half of centre
        sr = (sf[::-1])[no_digits & 1:]
        # form the palindrome and add it to the list
        l += [int('1' + sf + sr + '1', 2)]
      # if the number of palindromes matches the number of digits
      if len(l) == no_digits:
        # map palindrome differences to palindromes
        d = defaultdict(list)    
        for i in range(no_digits - 1):
          d[l[i + 1] - l[i]] += [l[i]]
        # find and output any unique value
        v = [d[k][0] for k in d if len(d[k]) == 1]
        if len(v) == 1:  
          print(v[0])
          break
    
  3. Brian Gladman 10 May 2012 at 5:57 pm

    And here is a better version:

    from itertools import count
    from collections import defaultdict
    
    # palindrome number form is '1abc...cba1' where the upper 
    # half of the central digits (abc...) includes the middle 
    # digit if n is odd and has ((no_digits - 1) // 2) binary
    # digits;  the lower half is the reverse of this but will
    # have one less digit when n is odd with the middle digit
    # of the palindrome being duplicated
    
    for no_digits in count(2):
      len_upc = (no_digits - 1) // 2
      # the number of palindromes equals the number of digits
      if 2 ** len_upc == no_digits:
        # accumulate palindromes
        pals = tuple()
        for i in range(2 ** len_upc):      
          # upper half of centre    
          sf = ('{:0' + str(len_upc) + 'b}').format(i)
          # lower half of centre
          sr = (sf[::-1])[no_digits & 1:]
          # form the palindrome and add it to the list
          pals += (int('1' + sf + sr + '1', 2),)
        # now map pallindrome differences to palindromes
        d, p_last = defaultdict(list), pals[-1]    
        for p in reversed(pals):
          d[p_last - p] += [p]
          p_last = p
        # find and output palindromes with unique differences
        v = [d[k][0] for k in d if k and len(d[k]) == 1]
        if len(v) == 1:  
          print(v[0], pals)
          break
    
  4. Steven Siew 15 May 2012 at 10:36 am

    Solved the New Scientist Enigma Problem number 1697

    The answer in decimal form is 189
    The binary palindrome is 10111101

    my solution as a picture

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: