Search

mercredi 8 février 2017

Revert array, in place

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