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