Context
Given an array, with our standard formalism, let's see how we can reverse it, i.e [A,B,C] to become [C,B,A]. But to make it more complex, let's do it in place, without needing extra data storage.Well, more exactly, with a constant amount of data storage, meaning that we won't need more space for bigger arrays
- Start at the end of the array (let's say it's a stack)
- Copy last array item at the end of the reverted stack
- Move the current reverted stack to the left, to use constant memory
- Loop until all items are moved
Initial state
- Memory: 0, A, B, C, D, ..., 0...
- Cursor: last array item
- Input: any
Process
- Start on stack's last element
- While there is at least one element
- While element is not null
- Decrease it by 1
- Move right twice (reverted stack's start point)
- Move right until cell is empty (first free position)
- Here is the trick: we should not add the new item right here! (otherwise we won't be able to identify the end of the array)
- Instead, move right once again, and increase cell by 1.
- Move left twice, then move left until cell is empty, and finally move left once.
- Back to item we want to move
- Loop invariant: sum of first stack's last element and cell just after second stack
- When first stack's last element is finally null, cell just after second stack contains moved last element from first stack
- Go to second stack's end
- Move newly added item to the left (append at the end of the array)
- Go back to second array's first element
- We now have 2 zeros between our 2 stacks: first's final delimiter, and one empty cell (generated by the move of last element) : we need to move the whole second stack one cell to the left to stay in-place.
- While second array's end is not reached
- Move current element to the left
- Move cursor to right
- Go back to first stack's last element
- Loop invariant: memory contains 0, then some items from original stack, then zero and finally all items missing from original stack in reversed order
- When first stack is empty: 2 zeros then all stack in reversed order
- Finally, move the whole reverted stack to the left once, to avoid the extra 0
Code
[
consider last integer
[
while it is not null
-
move 1 from this number
>>[>]>+
to the end of the reverted stack
<<[<]<
and go back to the moved value
]
>>[>]>
go to the new item; not exactly at the end but one cell after
it wouldn't have been possible to reach the end of array otherwise
[-<+>]
move this value to the end of the array
<[<]>
go back to the reverted stack's first element
[[-<+>]>]
move each element to the left to have in place algorithm
<<[<]<
go to original stack's last element
]
revert completed
>>[[-<+>]>]<<
move all items to the left because both original and reverted 0 array delimiters are here
Code (minified)
[[->>[>]>+<<[<]<]>>[>]>[-<+>]<[<]>[[-<+>]>]<<[<]<]>>[[-<+>]>]<<
Final state
- Memory: 0,..., D, C, B, A, 0
- Cursor: on final item (A)
- Input: unchanged
- Output: unchanged
Example
Live 'Stack-revert' example, that reads input, place all chars in an array, revert the array, then print the reverted stack (e.g. input abcdefgh prints hgfedcba)
Aucun commentaire:
Enregistrer un commentaire