Enigmatic Code

Programming Enigma Puzzles

Puzzle #32: Rearranging books

From New Scientist #3258, 30th November 2019 [link] [link]

Once a week, it is Jordie’s job at the library to put books back in order on the shelves.

This week, he finds that the 10-volume encyclopedia has been mixed up in the order shown above. He has to put them back in order, and since the books are heavy, he wants to move as few volumes as possible.

A move consists of taking a book off the shelf and sliding the other books to the side to make space, if necessary. What is the smallest number of moves he needs to make to rearrange the books in the order 1 to 10 from left to right?

[puzzle#32]

2 responses to “Puzzle #32: Rearranging books

  1. Jim Randell 30 November 2019 at 10:58 am

    We want to sort the sequence (10, 7, 2, 6, 5, 4, 1, 9, 3, 8) into ascending order using the minimum number of operations, where each operation involves removing an item from the list and reinserting it in a different position.

    The relative ordering of any items that are not moved in the operation remain unchanged, so the operation can only change how the other numbers relate to the moved item.

    So if we perform k operations (on k different items) then the items that were not removed will remain in the same relative ordering.

    So if we find a maximal length subsequence that is already in the right order, we just need to move the remaining items around into the appropriate positions relative to that subsequence to order the sequence.

    The given sequence has lots of increasing subsequences of length 3:

    (1, 3, 8)
    (2, 3, 8)
    (2, 4, 8)
    (2, 4, 9)
    (2, 5, 8)
    (2, 5, 9)
    (2, 6, 8)
    (2, 6, 9)

    But none of length 4 (or longer).

    So we can pick one of those and move the remaining 7 items into the appropriate positions in 7 operations to place the sequence in order.

    We cannot do it in fewer operations. As if we could do it in only 6 operations, then there would be 4 items that were still in their original relative order, so there would be a longer initial increasing subsequence.

    Solution: The books can be ordered using 7 moves.


    Here is a Python program that finds a minimal sequence of operations. It runs in 87ms.

    Run: [ @repl.it ]

    from enigma import irange, Accumulator, args, printf
    
    # generate increasing subsequences
    def incss(s, v=-1, ss=[]):
      if not s:
        yield ss
      else:
        # do we include the next element?
        x = s[0]
        if x > v:
          yield from incss(s[1:], x, ss + [x])
        # or not
        yield from incss(s[1:], v, ss)
    
    # find a maximal increasing subsequence
    def miss(s):
      r = Accumulator(fn=max).accumulate_data_from((len(ss), ss) for ss in incss(s))
      return r.data
    
    # sort the list
    def solve(s):
      # find a maximal increasing subsequence
      ss = miss(s)
      k = len(s) - len(ss)
      printf("[initial sequence = {s}, sorted = {ss}, sort in {k} moves]")
    
      # move the remaining items
      ss = set(ss)
      i = len(s) - 1
      for m in irange(1, k):
        # find the first non-sorted item
        while s[i] in ss: i -= 1
        v = s.pop(i)
        # insert it before the next largest sorted item
        xs = set(x for x in ss if x > v)
        if xs:
          j = s.index(min(xs))
        else:
          # or insert it at the end
          j = len(s)
        s.insert(j, v)
        printf("[{m}] remove {v}, insert at position {j} -> {s}")
        ss.add(v)
      return (s, k)
    
    # initial sequence
    s = args([ 10, 7, 2, 6, 5, 4, 1, 9, 3, 8 ], 0, int)
    
    (ss, k) = solve(s)
    assert ss == sorted(s)
    printf("sorted in {k} moves")
    

    There are more efficient algorithms to find the initial longest increasing subsequence [ @Wikipedia ], but this one is sufficient for small input lists.

    • Jim Randell 7 December 2019 at 9:30 am

      The published solution says:

      At least seven moves are needed to get the books in order.

      You can tell this by noticing that seven numbers (1, 3, 4, 5, 6, 8 and 9) are to the right of the next number up (2, 4, 5, 6, 7, 9, 10) and so have to be moved at some point.

      This rule works for any size of list.

      I agree that ordering the books requires at least 7 moves (actually it can be done in exactly 7 moves). But I don’t agree that you can order the books by moving only volumes 1, 3, 4, 5, 6, 8 and 9 around. As this means volumes 10, 7 and 2 would remain in the same positions relative to each other, and so would never be in the correct order no matter how you move the other volumes around them.

      However moving volumes 2, 4, 5, 6, 7, 9, 10 around leaves volumes 1, 3 and 8 in their original relative positions, and as they are already correctly ordered with respect to each other, the remaining 7 volumes can be inserted around them to place the books in the correct order.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: