(Challenge added over 6 years ago.)
Let's play a game ...
This challenge is a little different from the others you might have played. Instead of simply, after been given some input, having to produce some deterministic output, here there can be more than one correct solution.
The basis for this challenge is taken from a book called BASIC Computer Games. It featured a game called Reverse :
The game of REVERSE requires you to arrange a list of numbers in numerical order from left to right. To move, you tell the computer how many numbers (counting from the left) to reverse. For example, if the current list is
2 3 4 5 1 6 7 8 9and you reverse 4, the result will be
5 4 3 2 1 6 7 8 9. Now if you reverse 5, you win.
What we're asking you to do is, given a list of numbers in a random order, produce the moves required to arrange them so they end up in numerical order.
Obviously there can be more than one set of moves which will produce the desired result, and some will be shorter than others. For the moment, we're not concerned about how many moves it takes you to solve a given puzzle - We're still just concerned with the size of your code.
- Your submission will be given a list of consecutive numbers, starting at 1 and have been placed in a random order, on stdin. The numbers will be space-separated. You will always receive at least 5 numbers, and a maximum of 45.
- You should output the moves required to place the list in ascending numeric order to stdout. Each move is the amount of numbers you've decided to reverse that turn. The moves should be on one line space-separated, or each move on a line of its own. See the section below for an example of this.
- Your submission will be run 6 times. Your submission will have to pass all six runs for it to be deemed successful.
Given this starting list of numbers on stdin :
2 3 4 5 1 6 7 8 9your code should produce the moves which will order the list as
1 2 3 4 5 6 7 8 9
One solution (in fact, it's the only sensible solution) to this would be to reverse the first 4 numbers to give
5 4 3 2 1 6 7 8 9
Your next move should be to reverse the first 5 numbers to give our desired result. Your submission should, therefore, produce
as its output.
As mentioned above, your submission will be run 6 times. The first three times, you will receive the same input. To view the input you will receive, and a list of moves which solves that input, click on the links below. Remember that there can be more than one valid output.
For the last three runs, your submission will receive a random set of numbers. You will always receive at least 5 numbers, and perhaps up to 45. To see an example of a random run, click here. Reload the page for further, random examples.
Thanks to Paul Bissex who suggested this challenge. Please visit his blog post where talks about Reverse and how he wrote interactive solvers in a ton of languages. You can also see scans of the page of BASIC Computer Games (including a 60-odd line program in BASIC which plays the game interactively) where the Reverse idea came from.