i believe its cut off. 'read more' doesn't finish the sentence.
this reminds me of the pancake sort problem, except there you can only flip a contiguous subarray at the beginning. i got this in an interview once and then used it a few times when i had to interview folks. some people seem to get it right away... others... well, they don't
It was cut off on Safari but not Firefox (for some reason).
Here is the full text:
You're given a vector V containing a permutation of the integers 0 to n-1. For example {0,2,1}. You're also given an integer N which is greater than or equal to 2 and less than V.size(). You can reverse N contiguous items in V at a time. For example V = {0,2,1} and N = 2 you can reverse the ints located in V[0] and V[1] to give V = {2,0,1}. You can also reverse the ints in V[1] and V[2] to give V = {0,1,2}. Write a function that takes V and N as parameters and returns the minimum number of reversals needed to sort the vector increasing. If it's not possible return -1. For example V = {0,2,1} N = 2 returns 1. (reverse V[1] and V[2])
Pass Astar a sequence and the reversal length. I'm a total Python noob so I may have done something stupid and/or inelegant (in which case please tell me so that I learn :) ).
One naive solution is to realize that you can move (remove/reinsert) any element with two reversals. For example, given:
[1 2 3 4 5 6]
You can reverse elements 1-5 (if indexing starts at 0):
[1 6 5 4 3 2]
And then reverse elements 1-4:
[1 3 4 5 6 2]
This moves the element in position 1 to position 5. Generally, to move the element in position x to position y (shifting everything else to make room for it), do the following:
def move(v, x, y):
v.reverse(x, y)
if y > x:
v.reverse(x, y-1)
else
v.reverse(x+1, y)
return v
Given this ability to move/insert elements, you can implement several sort algorithms. In fact, it's easy to see that there's a O(n * x) sort here, where x is the runtime of the reversal operator.
"You can reverse N contiguous items in V at a time."
When you reverse elements 1-5 you're assuming N == 5. When you reverse elements 1-4 you're assuming N == 4. I think this violates the problem statement that N is fixed.
Could do a Breadth First Search. Add a memo table to make it faster. The memo table key would be the vector changed into an int i.e. (2,1,4,5,3) -> 21453. The memo table value would just be a bool... true if we've already seen the current permutation of the vector, false otherwise.
It's actually not easy to come up with an admissible heuristic for this, because of the reversal operator. I'm about to be late for dinner at a friend's so I don't have time to come up with something now, but if no one has by the time I'm back I'll think about it.
Edit: How about the sum of the differences of adjacent elements - n - 2? This seems to capture the notion that something reversed but in order is okay. I still don't think this is admissible though.
Well, here's an admissible one. Count how many adjacent elements are not the element to the left + 1, and divide that sum by 2. Pretty sure that'd work.
this reminds me of the pancake sort problem, except there you can only flip a contiguous subarray at the beginning. i got this in an interview once and then used it a few times when i had to interview folks. some people seem to get it right away... others... well, they don't