4 ms·

Puzzle: Sort Vector

13 points by tim_sw 18y ago

pz 18y ago
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
- Timothee 18y ago
  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])
spaghetti 18y ago
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.
- endtime 18y ago
  Why would you use a blind search rather than A*? It's not hard (edit: actually, maybe it is) to come up with a heuristic for this problem. 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!).
  - spaghetti 18y ago
    Right about the larger vectors. I don't know A*. What's an example heuristic for this puzzle?
    - endtime 18y ago
      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.
endtime 18y ago
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.
- spaghetti 18y ago
  "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.
- Timothee 18y ago
  I don't think it works that way. 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] For that case (6 elements and N=5), it looks like not many vectors V have a solution... but I'm too tired to keep going :)
  - endtime 18y ago
    Whoops, you're right, I didn't read it correctly.
endtime 18y ago
Okay, here's my quick solution with A* : http://cs.stanford.edu/~fra[REMOVE http://cs.stanford.edu/~fra[REMOVE THIS]nkel/listsort.py 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]] result will just be -1 if there was no path.
gacek 18y ago
Wow. A site with 4 algorithmic problems. Without any means of testing/comparing solutions. Just go to http://spoj.pl http://spoj.pl, http://online-judge.uva.es/ http://online-judge.uva.es/, or http://acm.pku.edu.cn http://acm.pku.edu.cn to name the three largest online judges.

13 points by tim_sw 18y ago

pz 18y ago

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

Timothee 18y ago
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])

spaghetti 18y ago

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.

endtime 18y ago
Why would you use a blind search rather than A*? It's not hard (edit: actually, maybe it is) to come up with a heuristic for this problem. 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!).
- spaghetti 18y ago
  Right about the larger vectors. I don't know A*. What's an example heuristic for this puzzle?
  - endtime 18y ago
    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.

endtime 18y ago

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.

spaghetti 18y ago
"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.
Timothee 18y ago
I don't think it works that way. 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] For that case (6 elements and N=5), it looks like not many vectors V have a solution... but I'm too tired to keep going :)
- endtime 18y ago
  Whoops, you're right, I didn't read it correctly.

endtime 18y ago

Okay, here's my quick solution with A* : http://cs.stanford.edu/~fra[REMOVE http://cs.stanford.edu/~fra[REMOVE THIS]nkel/listsort.py 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]] result will just be -1 if there was no path.

gacek 18y ago

Wow. A site with 4 algorithmic problems. Without any means of testing/comparing solutions. Just go to http://spoj.pl http://spoj.pl, http://online-judge.uva.es/ http://online-judge.uva.es/, or http://acm.pku.edu.cn http://acm.pku.edu.cn to name the three largest online judges.