### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,367)
- misc (4)
- project euler (2)
- puzzle (90)
- puzzle# (48)
- site news (58)
- tantalizer (94)
- teaser (7)

### Site Stats

- 233,130 hits

Programming Enigma Puzzles

30 November 2019

Posted by on **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]

%d bloggers like this:

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

koperations (onkdifferent 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:

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 ]There are more efficient algorithms to find the initial longest increasing subsequence [ @Wikipedia ], but this one is sufficient for small input lists.

The published solution says:

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.