Re: hacker challenge - traverse a list



On Mar 3, 11:40 am, spinoza1111 <spinoza1...@xxxxxxxxx> wrote:
On Mar 1, 1:56 am, c...@xxxxxxxx (Richard Harter) wrote:

Here is a little challenge - print the contents of a binary tree
in order only using O(1) additional memory. In other words you
can't use recursion or simulate it with a stack. As far as I
know you can't do this without some kind of hack. Also AFAIK
there is no way to do this that should ever be used in real code.
Rules? We don't need no steenking rules! Use whatever language
you like, though I suppose this is a natural for C based
languages. Tag bit solutions (i.e. mark a link as visited when
we go down it and unmark it when we come back up) don't count
because (a) everyone thinks of it, and (b) it (debatably) uses
O(log n) memory. Platform dependencies are okay - this a hack,
after all.

Thanks for submitting this very interesting challenge!

I am solving the problem (slowly as my schedule permits) without
hacking. I won't look at other solutions until I am done or give up.
This essay response describes my approach. Use of this approach or
comments are welcome.

In a nutshell: "don't hack: SIMULATE a stack".

The untested C sharp code that follows the essay is a stack simulator
which uses a single number to represent a stack with a fixed bound. It
is best viewed in a monospaced font.

It uses an old Fortran trick for representing arrays and stacks I used
in the very limited memory of IBM 1401 Fortran running on a minimal 8K
configuration, and learned in an old Cambridge University Press book
called, if memory serves, "Non-Numerical Programming in Fortran".
Decimal numbers are "squozed" into a large binary number by shifting
them by powers of ten.

It's not a hack and that's the beauty of the thing: using an object-
oriented language means that you can encapsulate your dirty laundry in
a class!

Right now, though, I am stuck on how to write inorder traversal with
my nice new stack. It is easy if you can use recursion, but we cannot.

I claim that using a stack simulated by a single integer gives
"order(1) prime" memory complexity and not O(1) because I view the
direct application of the big O notation to code as an error. Scoffers
may scoff and be damned, but given optimizing OO compilation, there is
no limit to inlining, and for this reason the essential cost of the
stack is (1) the cost of the integer that holds the stack and (2) the
code associated with the stack, which doesn't count.

I am looking forward to reading other replies because in the post tree
I see good people including Julienne and few of the thugs. Hey Randy
where is your solution, big man? But first I will spend some time
trying to do inorder traversal with a stack but without recursion.

Here is the untested code of the stack class, best viewed in a
monospaced font such as Courier New and implemented, in C Sharp, as a
struct.

private struct TYPintegerStack
{
uint INTstack;
byte BYTdecimalWidth;
ushort SHRshift;
public TYPintegerStack(byte bytWidth) // constructor
{
INTstack = 0;
BYTdecimalWidth = bytWidth;
SHRshift = (ushort)Math.Pow(10, BYTdecimalWidth);
}
public bool push(ushort shrValue)
{
if (shrValue >= Math.Pow(10, BYTdecimalWidth))
{
Console.WriteLine
("Value for push " +
shrValue.ToString() + " " +
"exceeds decimal width " +
BYTdecimalWidth.ToString());
return false;
}
long lngTest = INTstack * SHRshift + shrValue + 1;
if (lngTest > Math.Pow(2, 31) - 1)
{
Console.WriteLine("Stack overflow");
return false;
}
return true;
}
public ushort pop()
{
if (INTstack == 0)
{
Console.WriteLine("Stack underflow");
return 0;
}
ushort shrReturn =
(ushort)(INTstack % (int)SHRshift - 1);
INTstack /= SHRshift;
return shrReturn;
}
public bool Empty
{
get { return INTstack == 0; }
}
}





Richard Harter, c...@xxxxxxxxxxxx://home.tiac.net/~cri,http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.- Hide quoted text -

- Show quoted text -

The solution doesn't, I believe, even need a simulated stack.

Subsequent to the above post I found the following algorithm in
wikipedia for "threaded tree traversal inorder" with neither recursion
nor the stack but so far I haven't got its transliteration to C Sharp
to work and will try to do so. It is time for me to look at the rest
of the posts in this very interesting challenge, but I will continue
to work on this solution as well.

//while hasleftchild(node) do
// node = node.left
//do
// visit(node)
// if (hasrightchild(node)) then
// node = node.right
// while hasleftchild(node) do
// node = node.left
// else
// node = node.right
//while node ≠ null
.



Relevant Pages

  • Re: Memory management strategy
    ... >>trading memory for speed ... The use of registers instead of the stack doesn't need inlining. ... >longer instructions to access smaller data than they were optimized for. ... square) but it didn't need recursion or some kind of stack. ...
    (comp.lang.c)
  • Re: Optimize a discovery algorithm
    ... from the beginning (and without using recursion). ... it's a stack of 33 pairs of 32 bit words. ... Using a large amount of memory is mandatory to achieve the minimum ... uint32_t top, bottom, reusable; ...
    (comp.lang.c)
  • Re: If Macs have no spyware....
    ... First you yammer about being a Mac advocate, then bad mouth me for dumping XP in favor of a Mac. ... Supposedly Microsoft had made a complete code review of its operating system and removed all the buffers which could overflow. ... the fundamental problem is that the basic architecture of Windows has two fatal flaws in its memory management and while these remain in the software the ad hoc patches will never be enough to make Windows a secure operating system. ... These problems are bad enough when dealing with data in the one routine but when the data exists on the stack, it can cause very large problems. ...
    (comp.sys.mac.advocacy)
  • Re: If Macs have no spyware....
    ... >had made a complete code review of its operating system and removed all ... and writing new data into those memory locations would ... >but when the data exists on the stack, it can cause very large problems. ... >location that needs to be written in place of the correct execution ...
    (comp.sys.mac.advocacy)
  • Re: Maybe we should stop "Paging Beth Stone" already...
    ... I'll want to work on my OS while running my OS, so the assembler that it's written with has to run under it. ... You have to swap CR3 if you want seperate memory spaces. ... The alternate stacks aren't used by the processor unless the task calls a different protection level, so they're not part of the TSS swap. ... This lets any application use up to a gigabyte of stack before Linux is forced to tell it that it's gone too far. ...
    (alt.lang.asm)