Sorting balls

[Foamy]

Little Jack has a new set of balls numbered 1 to n. However, he has them completely rearranged and wants them to be sorted from the least to the highest number. As Jack is ambitious, he doesn't want to do this in a typical way - he decided that he is allowed to make 2 types of moves only:
X moves - moving the last ball to the beggining
Y moves - moving the third ball to the beggining
He asked for your help since nothing makes him mad as much as not sorted balls!

INPUT: a<2222 and then a integers (from range 1 to a) showing the actual arrangement of the balls. You can be assured no integer will be used more than once.

OUTPUT: integer h (while h<=a^2) meaning how many sets of moves we have to make. By a "set of moves" we understand making operation X or Y g times. If h>0, in the second line you should output a sequence of h integers with X or Y beside them (hX means making X move h times). Also the types of moves have to be arranged alternately (for example, no 5X 5X). If there's more than one correct answer, you can write any of them. When there's no answer, however, you should output -1.

EXAMPLE:

IN:
6
1 5 2 3 6 4

OUT:
5
5X 2Y 4X 1Y 3X


Honestly, I've been sitting at this for past 3 hours and can't think of anything except dumb brute-force which obviously isn't the right track.. Could you please help me with this?

[Kirby]

For the case n = 3, there is not always a solution.

Suppose we have:
3 2 1

We can either move the last to front, or third to front. In this case, these are identical. Doing this gives
1 3 2
2 1 3
3 2 1

And we're back where we started, and never had a solution.

Assuming 1 < n < 2222, n ≠ 3...

The easiest thing that comes to mind is to pre-compute the solution path from the sorted state to each unsorted state. Then look up the input unsorted state, and the corresponding path to the sorted state. There are n! such states. is that fast enough?

[jaap]

The easiest thing that comes to mind is to pre-compute the solution path from the sorted state to each unsorted state. Then look up the input unsorted state, and the corresponding path to the sorted state. There are n! such states. is that fast enough?

Given that n can be up to 2222, that obviously is not feasible.

Shifting the third ball to the beginning rearranges three adjacent balls. Since you can shift the whole row, you can rearrange any 3 adjacent balls. It is fairly easy to sort the balls once you think of the row as being stationary and you moving along the balls instead. Instead of the X move shifting the row of balls to the right, it causes you to move to the left along the stationary row. With a Y move you rearrange the 3 balls in front of you.

Here's a complete example:

Spoiler:

Code: Select all

  164325
  ^^^
We want to move the 2 to the left so that it goes towards the 1. First we move to the right ourselves.

  164325
    ^^^
We moved 2 steps to the right, which is the same as moving the whole row 2 to the left relative to us, which is the same as moving the whole row n-2=4 steps to the right, i.e 4X.

  162435
    ^^^
Do 1Y to move the 2 towards the 1.

  162435
   ^^^
Move to the left (1X) so that we can then move the 2 without disturbing the already solved 1.

  124635
   ^^^
Do 2Y to put the 2 in place.

  124635
    ^^^
Move to the right one step (5X) towards the 3.

  123465
    ^^^
Do 1Y to put the 3 in place.

If the last two pieces are swapped, then there are 2 possibilities.
n is odd: Impossible to solve.
n is even: solve by jumping ball n over all the balls 1 to n-2.

  123465
    ^^^

  126345
    ^^^
Jump 6 over 3 and 4. (1Y)

  126345
  ^^^
Move left 2 steps (2X)

  612345
  ^^^
Jump 6 over 1 and 2. (1Y)
The balls are now ordered, but we still have to move to the start of the row:
  612345
   ^^^
Move 1 to the right (5X)

A full solution in this case is:
4X 1Y 1X 2Y 5X 2Y 2X 1Y 5X

Note that I had to merge the last 1Y of the main section with the first 1Y of the final swap.


[Foamy]

Thank you very much for the response but what does the Y move exactly do? What rearrangement does it make to three balls instead of the three we're focusing on that moment? Can't figure it out from the example...

[jaap]

Thank you very much for the response but what does the Y move exactly do? What rearrangement does it make to three balls instead of the three we're focusing on that moment? Can't figure it out from the example...

As the problem description says, it moves the third ball to the front. So if we're standing in front of balls ABC, it changes them to CAB. Doing 2Y changes ABC to BCA.

[Foamy]

OK.. So from what I see the algorithm should look like this:

Look for a triple containing 1 by using specific X's. When found, move it to the left using Y's until row[0]=1.
Set a "safe zone" on row[0] meaning the algorithm can't include 1 in any of its searches since it's already set properly.

Repeat until all is sorted or it's proven that it can't be.

Is it OK or I didn't get sth?

[jaap]

OK.. So from what I see the algorithm should look like this:

Look for a triple containing 1 by using specific X's. When found, move it to the left using Y's until row[0]=1.
Set a "safe zone" on row[0] meaning the algorithm can't include 1 in any of its searches since it's already set properly.

Repeat until all is sorted or it's proven that it can't be.

Is it OK or I didn't get sth?

That's pretty much it.

BTW, I edited my example just now because the indentations weren't being shown properly. For some reason indenting by just one space is ignored.

[Yakk]

Bubble sort! Pretend X just moves your head -- keep a virtual "seam" where your head moves, and the head does the move Y around it, if that makes sense.

An arrangement of 3 elements is considered "more sorted" when the largest element is lowest.

"more sort" elements 1-3. Then "more sort" elements 2-4, etc.

After the first pass, the highest element is in the highest spot. On the 2nd pass, the second highest element is guaranteed at the highest spot.

Note that you will never sort over the seam (as by the time you reach it, the highest element is on it, so will never want to be "sorted down").

You might be able to do better with a kind of "insertion sort", where you work out where every element should be, and then use the Y move to move an element of your choice "closer" to the right spot. For one that is similar to the bubble sort above, choose the largest element in your range of 3, and do Y until it is in the position closest to where it wants to go -- I think that is at least as good as the bubble sort algorithm above.

As noted, lists of size 3 end up not working.

[Foamy]

jaap - Hmm.. I came across a problem. How should I make my algorithm "see" a triplet? I mean: saving three elements to some array and then (if the next number we're looking for, say 2) if 2's not there, changing all these variables to the next triplet is extremely time consuming. For example:

Code: Select all

134562
^^^
As safe zone is set to "protect" row[0], we make our see[0]=row[1], see[1]=row[2], see[2]=row[3]. Check if see[0], [1], [2]==0. Here, however, it's not so let's move:
   134562
    ^^^
To move, we must have made see[0]=row[2], see[1]=row[3], see[1]=row[4]
And so on...

This way, it will take a vast amount of time to get to 2. So maybe instead we should move just using one pointer and when 2 is found, we check how many numbers we've moved and then treat 2 as it's the end of some triple. I mean:

Code: Select all

 134562
 ^
1 is in the safe zone so we start from 3.
   134562
    ^
134562
   ^
and so on till:
134562
     ^
Then, we check that we're on the index 5 so we moved t times and therefore made some X's. Then, we can highliht two previous numbers:
134562
   ^^^
And go like you did.

Is it OK?

Yakk - honestly, I can't imagine a seam and can't figure out what merge sort has to do with it. Could you plase explain further?

[Yakk]

Pretend you have a virtual 3-wide head.

X moves the head 1 unit.
Y rotates the 3 elements under the head by 1.

There is a "pretend seam" between the left most element in the list, and the right most element in the list.

In reality, X moves the elements not the non-existent "head", and Y always rotates the first 3 -- but by pretending that X moves the head, and Y rotates elements under the head, and having a virtual "seam" where the list started/ended when we started the problem, we turn the problem into a pretty simple bubble sort. We just finish the problem by moving the "head" back to the start of the list via repeated Xs.

[jaap]

jaap - Hmm.. I came across a problem. How should I make my algorithm "see" a triplet? I mean: saving three elements to some array and then (if the next number we're looking for, say 2) if 2's not there, changing all these variables to the next triplet is extremely time consuming.

I really don't understand why you would ever want to do it that way.
Suppose you have already solved a couple of balls. You just scan through the list to find out where the next ball is. Then you can calculate how many X moves you would need to do to get there. When you 'do' these X moves, you don't shift all the balls in the array. That is too time consuming. You just adjust one variable that indicates the index in the array you are standing in front of.
Like this:

Code: Select all

// array = array containing the current order of the balls.
mypos = 0; // array index of first of 3 balls in front of us.
for( ballnumber = 0 to array.length-2 )
   solveBall(ballnumber)
//todo swap last two balls if necessary and possible


function solveBall( ballnumber ){
   ballpos = array.indexOf(ballnumber)   // find ball in array
   while( ballpos > ballnumber ){  // ball is not yet solved
      // move so that ball is the middle one in front of us
      printmove( mypos-(ballpos-1), "X")
      mypos = ballpos-1
      // do 2Y to move ball left one step
      array[mypos+1] = array[mypos+2]
      array[mypos+2] = array[mypos]
      array[mypos] = ballnumber
      ballpos = ballpos - 1
      printmove( 1, "Y")
   }
}

[Foamy]

I really don't understand why you would ever want to do it that way.

Honestly - neither do I but couldn't think of a better algorithm.
In your code you stated that we should move so that the ball we're looking for is in the middle of our sight. But isn't looking for it to be in the third place better? Then, we move it to the beggining by just one Y.

Yakk - I don't think merge sort is a good idea here. How do we know how many Ys we should do if we simply merge sort a triple?

[jaap]

I really don't understand why you would ever want to do it that way.

Honestly - neither do I but couldn't think of a better algorithm.
In your code you stated that we should move so that the ball we're looking for is in the middle of our sight. But isn't looking for it to be in the third place better? Then, we move it to the beggining by just one Y.

Yes, but I''ll leave that to you. The problem doesn't require you to use a short way to solve it, and I couldn't be bothered to describe code that does that because it would be twice as long (a loop with steps of 2, followed by almost the same code for a possible final step of 1).

Yakk - I don't think merge sort is a good idea here. How do we know how many Ys we should do if we simply merge sort a triple?

Yakk mentioned bubble sort, not merge sort which is something entirely different and inapplicable to this situation.
I agree that on some triples Y moves are not enough to order them. Nevertheless a kind of bubble sort would work if you just skip over such troublesome triples, and bubble sort until there is at most one such triple left. I think it is a bit harder to program and not really quicker than what I described, which is essentially a selection sort.

[Foamy]

The problem doesn't require you to use a short way to solve it

And what about time? I mean: would this looking for the ball on the third place instead of the middle make the code faster or just the results shorter?

I couldn't be bothered to describe code that does that because it would be twice as long

It's obvious - I just wanted to make sure if my thinking's right

(a loop with steps of 2, followed by almost the same code for a possible final step of 1).

Hmm.. I thought of another way of implementing it. Namely: we look for our ball, then we check what (its_index-safe_zone)%3 would give us and, depending on the result, we know which position in the triple it holds.

Yakk mentioned bubble sort, not merge sort which is something entirely different and inapplicable to this situation.

My bad.. I read his "more sort" as "merge sort"

[jaap]

The problem doesn't require you to use a short way to solve it

And what about time? I mean: would this looking for the ball on the third place instead of the middle make the code faster or just the results shorter?

It will be about twice as fast of course, but that's not important compared to getting it to work at all.

(a loop with steps of 2, followed by almost the same code for a possible final step of 1).

Hmm.. I thought of another way of implementing it. Namely: we look for our ball, then we check what (its_index-safe_zone)%3 would give us and, depending on the result, we know which position in the triple it holds.

Yes, by checking whether the distance the ball has to travel is even or odd (%2 not %3) you can tell whether you can do it with just steps of 2 or whether you need a single step too. You can then do that single step first if you wish. I had in mind to do it last, once the distance was reduced to below 2.

[Foamy]

Hmm.. I came across this idea:

1. Check if any of the elements are sorted. If they are, set safe zone to the last of the sorted ones.
2. Look for the next element. When found, print suitable number of Xs and if:
a) it's possible to make it the last element of the triple (which means: it's not middle element in the first triplet after the safe zone) then do Y and change the order of elements (from 652 to 265, normal Y I mean)
b) it's not possible to do so then it must be the middle of the first non-safe triple so just print 2Y and it's sorted. Go to 2.
3. Check if it's just after the safe zone - if so then it's sorted. Go to 2.
4. Change the variable denoting the placing of the ball we're trying to sort to variable-=2 and print suitable number of Xs if making it the last element of the triple doesn't obstruct the safe zone. If it does, it must be second after the safe zone so print 2Y and it's sorted. Go to 2.
5. Go to 2a.

Does it sound right?

[Yakk]

The parity problem is interesting. The fix (rotating an element from front to back) is also interesting.

I wonder if there is an easy way to detect the parity problem? And efficiently change the parity of the proggy.

[jaap]

The parity problem is interesting. The fix (rotating an element from front to back) is also interesting.

I wonder if there is an easy way to detect the parity problem? And efficiently change the parity of the proggy.

As far as I know, all reasonable ways of calculating the parity of a permutation are O(n²).
If you know/calculate the parity at the start, you can fix it with a single X move if n is even, or quit if n is odd.

[Goplat]

Swapping any two elements inverts the parity, as I understand it, so it should be possible to

• scan through the permutation and build a table that gives the position of each item (this is just an "indexof[permutation[i]] = i" loop)
• do a selection-sort, using the table so each element can be found in constant time rather than the usual linear time
• return whether it took an even or odd number of swaps to sort

[jaap]

Swapping any two elements inverts the parity, as I understand it, so it should be possible to

• scan through the permutation and build a table that gives the position of each item (this is just an "indexof[permutation[i]] = i" loop)
• do a selection-sort, using the table so each element can be found in constant time rather than the usual linear time
• return whether it took an even or odd number of swaps to sort

Doh! Of course. Parity calculation is at least as fast as sorting if you are allowed to rearrange the numbers (or use O(n) extra memory to make a copy), and if it is a permutation of consecutive numbers then sorting is O(n).
I'd love to know if there is a faster way than O(n²) to calculate the parity with constant memory (and no rearrangement).

[Foamy]

Erm.. But what parity are you talking about and how it should help me solve the problem?

BTW: Was the algorithm I wrote above bad?

[jaap]

Erm.. But what parity are you talking about and how it should help me solve the problem?

It is the parity of a permutation. An easier explanation might be this page of mine.
If the permutation of the balls is odd, then you will end up with the last pair of balls swapped. They can be sorted if there are an even number of balls, as explained in the worked example I gave.
You could determine the parity beforehand, and start the solve in such a way that you don't have to fix it at the end. I don't think this is worth it since the parity fix is easy.

BTW: Was the algorithm I wrote above bad?

It seems ok (apart from missing the parity fix for even n).

[Foamy]

Hmm.. but would calculating the parity in the beggining make the algorithm noticeably slower? It's sure it'd make the algorithm faster for the -1 cases but what about the "normal" ones?

[jaap]

Hmm.. but would calculating the parity in the beggining make the algorithm noticeably slower? It's sure it'd make the algorithm faster for the -1 cases but what about the "normal" ones?

Yes, unsolvable ones would be dealt with faster, solvable ones slower. If you are really going for speed, then whether it is worth checking parity first (using a fast way as Goplat suggested) would depend on how many unsolvable ones there were compared to solvable ones. I wouldn't bother, unless speed has become a problem and then I'd test it to see if it helps.

[Foamy]

So it seems one last thing is unclear to me.. How should I store these moves? I can't just print the required number of moves every time I do one since (from the problem description) I'm to write the number of sets first. Should I store them in a string or a chars array? Then, however, I would be unable to sum 1Y and 1Y when the parity problem occurs, for example. So what? A special int array which I would use just for storing a proper number of X and Y moves in every step and a variable telling the algorithm if we're to start from X or Y move?

[Yakk]

std::vector<int>, with negative corresponding to X and positive to Y?
std::vector<struct { bool isX; int count; };>?

[Foamy]

But isn't working on vectors a waste of time? I mean, I can create an array of 4 million ints and not bother with push_back and all the other stuff which would make it slower.

[Yakk]

No, learning how to use a std::vector is not a waste of time.

It is true that solving a toy problem like this using your existing skills will take less time than learning a new skill, because learning new skills is harder than not learning new skills. I hope your goal isn't to solve this toy problem, but rather to learn.

You understand the basics of arrays. Picking up how vectors work is a good idea. I can even explain why the vector will be very close to as fast as an array (it won't be as fast as a stack array, but the stack is shockingly small -- outside of a toy problem, burning 1 meg of stack space is hostile) (and you should avoid using global variables).

vectors keep track of amount of valid data, do exponential storage growth to efficiency dynamically size the amount of storage you need based on data needs, and in many cases contain debug-time checks to make sure you aren't an idiot and miss your fenceposts. push_back is exactly the operation of "insert some data, and increase the count of elements" that you need.

But in any case, feel free to use a large array.

[Foamy]

I understand the basics of vectors. What I meant was if there's any point in using vectors here when I know that I have enough memory to use 4 million int array, not if there is any point in learning how to use vectors... Would using them make it any faster?

[Yakk]

std::vector is slower than an on-stack array. The degree to which it is slower is not large -- write good readable, error-resistant, robust code, worry about O-notation level speed issues, then after you are done work on speed.

Speed (faster code) is something you can generate by investing programmer time. By making your code bug-resistant, you save tonnes of debugging time. By making your code readable, you save tonnes of debugging time. You can then take that time and invest it in speed increases. . .

And using std::vectors instead of malloced, newed, stack-based or global arrays will make your code more bug resistant and readable. Which should be among your top goals as a programmer. And vectors are ridiculously useful in a whole myriad of situations.

[Foamy]

OK, thank all of you for the help, I implemented this version with trying to set a ball as the last from the triple and while it runs great for short tests, when it comes to n=2000, for example, it takes around 2 minutes to calculate. Is it normal?