1
$\begingroup$

Let's say that there is a tower of blocks labelled from top to bottom $1$ to $n$. Somebody comes along and removes a block and reinserts it somewhere in the tower (making space as needed). As they move these blocks one at a time, they write down in order which index they moved a block to (index starting at 1). For example, they take the block 5 from the 5th index and squeeze it into between the 6th and 7th making it the 7th index. They write down "block 5 to index 7". They can make as many moves as they like and move each block as many times as they like.

Note that the index "moved to" is the index of the block after the removal and insertion are complete.

Someone else finds the changeset the original person created. Knowing the size of the tower and having the list of changes, they must write another changeset that would have the same results as the first but with at most one move per block and the moves must take place in the order that the blocks were originally moved in without latter duplicates. This also means that only blocks of the original changeset can be moved.

I came up with one which is to repeat the steps in order excluding those where the block is moved again later. This seemed to work in some cases but not all.

Is there an algorithm to solve this problem?

$\endgroup$
5
  • $\begingroup$ Say the n is 4 [1, 2, 3, 4], someone moves them and now there is [4, 1, 3, 2] and the task is to write 4->1, 4->3? $\endgroup$
    – Evil
    Commented May 22, 2018 at 4:47
  • $\begingroup$ @Evil For the most part, I was using block #'s to describe what moved and indices to describe where to. So it would be [block] 4-> [index] 1, [block] 3-> [index] 3. $\endgroup$
    – Knox
    Commented May 22, 2018 at 14:41
  • $\begingroup$ Hints given by D.W. seems sufficient, do you understand them? $\endgroup$
    – Evil
    Commented May 22, 2018 at 22:21
  • $\begingroup$ I forgot an important requirement and I'm not sure if it would have been better to make a new questions: "the moves must take place in the order that the blocks were originally moved in without latter duplicates." $\endgroup$
    – Knox
    Commented May 22, 2018 at 22:29
  • 1
    $\begingroup$ It does not matter at all, it only determines order of moves you have to provide as the result, so it will be just 1 instead of any possible. So it does not require new question. $\endgroup$
    – Evil
    Commented May 22, 2018 at 23:29

1 Answer 1

1
$\begingroup$

Hint #1:

Suppose you are only given the final configuration of the stack (not the changeset that led to it). Could you find any sequence of moves that would lead to that configuration? Could you find a sequence of moves that would lead to that configuration, and that makes at most one move per block?

Hint #2:

Where does block 1 go to? Where does block 2 go to?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.