Re: Fast pancake flipping

From: Joe \ (joe_at_bftsi0.UUCP)
Date: 02/23/04 

Date: Mon, 23 Feb 2004 10:00:51 -0800

"James Dow Allen" <jdallen2000@yahoo.com> wrote in message <news:266426e1.0402230103.5ea4d484@posting.google.com>...

> The most clever of you will be able to reproduce the entire
> subroutine from the brief excerpt. (The most annoying of you
> will insist that my alleged fast flipper doesn't exist at all!)

Here's a quick-and-dirty existence proof in my usual 'toy' language:

Sub TestReverse(ByVal P As Long)
  Const Nil = 0
  Dim List(1 To 10) As Long, Head As Long
  Dim Curr As Long, Prev As Long, Temp As Long

  ' O(N) initialize the xor-linked list
  Head = 1
  For Curr = 1 To 9
    List(Curr) = (Curr - 1) Xor (Curr + 1)
  Next
  List(10) = 9 'Xor Nil

  ' O(N) skip over P nodes
  Prev = Nil
  Curr = Head
  While Curr <> Nil And P > 0
    Temp = Curr
    Curr = List(Curr) Xor Prev
    Prev = Temp
    P = P - 1
  Wend

  ' O(1) flip the nodes from Head to Prev inclusive
  If Head <> Nil Then List(Head) = List(Head) Xor Curr
  If Prev <> Nil Then List(Prev) = List(Prev) Xor Curr
  If Curr <> Nil Then List(Curr) = List(Curr) Xor Prev Xor Head
  If Prev <> Nil Then Head = Prev

  ' O(N) print the folded/spindled/mutilated list
  Prev = Nil
  Curr = Head
  While Curr <> Nil
    Debug.Print Curr;
    Temp = Curr
    Curr = List(Curr) Xor Prev
    Prev = Temp
  Wend
  Debug.Print

End Sub 

--
Joe Foster <mailto:jlfoster%40znet.com>  Sign the Check! <http://www.xenu.net/>
WARNING: I cannot be held responsible for the above        They're   coming  to
because  my cats have  apparently  learned to type.        take me away, ha ha!

Relevant Pages