Ferry

Logic Level 2

The goal is to design an algorithm that will take the lists (12345678, XY) and convert them to (87654321, XY). The algorithm must move elements in the following manner:

Select exactly two consecutive elements from the first list.
Without changing their order, exchange those elements with the two elements in the second list.

What is the least number of moves required by the algorithm?

Hint: The 13 steps below, even though non-optimal, show how to accomplish the job following the rules. So, your answer must be smaller than 13.

[Step 00] 1 2 3 4 5 6 7 8 (X Y)
[Step 01] 1 2 3 4 5 6 X Y (7 8)
[Step 02] 7 8 3 4 5 6 X Y (1 2)
[Step 03] 7 1 2 4 5 6 X Y (8 3)
[Step 04] 8 3 2 4 5 6 X Y (7 1)
[Step 05] 8 7 1 4 5 6 X Y (3 2)
[Step 06] 8 7 1 4 5 3 2 Y (6 X)
[Step 07] 8 7 6 X 5 3 2 Y (1 4)
[Step 08] 8 7 6 X 1 4 2 Y (5 3)
[Step 09] 8 7 6 5 3 4 2 Y (X 1)
[Step 10] 8 7 6 5 3 X 1 Y (4 2)
[Step 11] 8 7 6 5 4 2 1 Y (3 X)
[Step 12] 8 7 6 5 4 3 X Y (2 1)
[Step 13] 8 7 6 5 4 3 2 1 (X Y)

The answer is 9.

3 solutions

Ivo Zerkov
Aug 23, 2017

Step 1: XY34567812
Step 2: XY34127856
Step 3: XY34156827
Step 4: XY32756841
Step 5: XY32754168
Step 6: XY68754132
Step 7: XY68732154
Step 8: XY65432187
Step 9: 87654321XY
So answer is 9?

Is there some strategy here or is this just the result of search the space of all possible moves?

Richard Desper - 3 years, 9 months ago

Ya I'm curious to see if anyone has shown that it actually is the least possible or was this just basically a brute force/guess and check type problem.

John Smith - 3 years, 9 months ago

Ivo, you are a lucker...js

Nikola Yanakiev - 3 years, 9 months ago

How do we show that this is the smallest solution?

Agnishom Chattopadhyay - 3 years, 8 months ago

I got in 8 steps!

Aaditya Amin - 3 years, 9 months ago

Really? Maybe you could post a solution?

Agnishom Chattopadhyay - 3 years, 8 months ago

Step00:12345678XY
Step01:8X3456712Y
Step02:871456X32Y
Step03:876X51432Y
Step04:8763214X5Y
Step05:8765Y14X32
Step06:87654XY132
Step07:87654321XY
Is there a mistake in the above algorithm? Isn't the answer 7?

Jaswanth Sai - 3 years, 9 months ago

you're meant to swap 2 numbers from the first list of 8 numbers with the 2 numbers from the right list. In step 1 since X & Y are in the second list, they both should of been moved but you moved 8 & X.

John Brady - 3 years, 9 months ago

Given condition: 12345678 (XY) Step 1. 12785634 (XY)
Step 2. 85712634 (XY) Step 3. 81257634 (XY) Step 4. 87651234 (XY) Step 5. 87623514 (XY) Step 6. 87614523 (XY) Step 7. 87652143 (XY) Step 8. 87654321 (XY)

Aaditya Amin - 3 years, 9 months ago

You are not following the rules. You are swapping two consecutive numbers with a different pair of consecutive numbers, neither of which pair is the XY pair. Each move should swap two consecutive numbers with the numbers in the XY register.

Mark Hennings - 3 years, 9 months ago

Anand Krishnaswamy
Sep 2, 2017

My back-of-the-envelope calculation was there are 8 nos. in list-1 & what I really require is cyclic move of each by a position to get them to 87654321 (8 moves) & one final swap to get XY back in the 2nd list. Hence, I went with 9. I verified it by ordering it as Ivo did (above). What I will need to do is to verify if N+1 will always be the case for all N.

It is not true. The case for N=5 also requires 9 moves.

D G - 3 years, 9 months ago

Thanks for the clarification. Then my earlier comment was simply a coincidental guess...

Anand Krishnaswamy - 3 years, 9 months ago

Wow. I did the same thing

Samuel Shadrach - 3 years, 9 months ago

Perhaps it’s floor(n/2)+1? A move for each coupling and an additional to reset x and y.

David Coffman - 3 years, 9 months ago

Milly Choochoo
Sep 1, 2017

I guessed the right answer, but I don't really know how to solve this. It seems really interesting though. A few things I've noticed:

1. With only 3 numbers and the XY pair, the only "solution" is 321-YX (5 moves). You can't get it to 321-XY.
1. With only 4 numbers and the XY pair, there is no "solution". It's impossible to change the order.

I think the solution, general to all order-able lists of size (n), would involve some sort of permutation classification.

1, 5, and 8 are the only n with solutions from 1-8 (brute force, the graph grows too quickly past that).

D G - 3 years, 9 months ago

If one were attempting to move n consecutive nos. at a time (n >2) you'd need as many letters in the 2nd list to perform a swap, right? Would you then still say that there are no solutions?

Anand Krishnaswamy - 3 years, 9 months ago

My thinking was the following:

12345678, XY Swap 1 with X and 8 with Y
X234567Y, 18 Swap them back, but reverse the order so the 2 numbers will go to their correct final state.
82345671 YX And that's all we need.

We can see that step 3 is the exact same as step 1, except that we are 2 numbers closer to our final result. Each 2nd step we perform after the first initial state, moves us 2 numbers closer to the final state, i.e each step moves us one number closer to the final state. By realizing this we can see that we get a linear run time, or more specifically O(n+1). This is for all n that are even.

If n is odd, then we get just O(n). Because we will always have n-1 steps that we need to swap, and the last number (the one in the middle of the array) will not need to be swapped.

Samuel Andersson - 3 years, 5 months ago

Step 00] 1 2 3 4 5 6 7 8 (X Y) exchange 1 2 <-> 7 8

[Step 01] 7 8 3 4 5 6 1 2 (X Y) exchange 3 4 <-> 6 1

[Step 02] 7 8 6 1 5 3 4 2 (X Y) exchange 8 6 <-> 4 2

[Step 03] 7 4 2 1 5 3 8 6 (X Y) exchange 2 1 <-> 8 6

[Step 04] 7 4 8 6 5 3 2 1 (X Y) exchange 7 4 <-> 6 5

[Step 05] 6 5 8 7 4 3 2 1 (X Y) exchange 6 5 <-> 8 7

[Step 06] 8 7 6 5 4 3 2 1 (X Y)

It can be done with a minimum of 6 exchanges , ... if we do not use the second list.

Juan Manuel Cruz Morales - 1 year, 8 months ago

Ferry

The answer is 9.

3 solutions

1 pending report

Vote up reports you agree with