Puzzle: Sort Vector
idiomatic-fu.appspot.com
idiomatic-fu.appspot.com
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
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 :) ).
Example:
>>> result = Astar([1, 4, 2, 3, 6, 5], 2)
>>> result.path
[[1, 4, 2, 3, 6, 5], [1, 2, 4, 3, 6, 5], [1, 2, 3, 4, 6, 5], [1, 2, 3, 4, 5, 6]]
Just go to http://spoj.pl, http://online-judge.uva.es/, or http://acm.pku.edu.cn to name the three largest online judges.
[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
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.
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.
So, you always revert the same number of elements in the vector. In your example, you revert 5 elements and then 4.
Your example would give the following sequence:
[1 2 3 4 5 6]
[1 6 5 4 3 2]
[3 4 5 6 1 2]
[3 2 1 6 5 4]
[5 6 1 2 3 4]
[5 4 3 2 1 6]
[1 2 3 4 5 6]
Also, your memo table wouldn't work for large vectors...
Edit 2: Even worse, the branching factor of that search tree would be O(n!).
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.