How is that turing incomplete?
Look at the first requirement...
Is this list of parenthesis balanced?
First you look for every ( and then you look for every ) if there are
an equal number then you have a balance unless of course you have
something stupid like just )(
Next you count total depth.
I did this by incrementing a counter for each ( and stopping the
counter when it hit the first )
So given
(((((((((())))))))))
We would get 10
On 11/6/06, Daniel C. <[EMAIL PROTECTED]> wrote:
You realize that this problem has been proved Turing-incomplete right?
There is no computer in the universe, and it is impossible to build
one, that can decide every string in that language. I'm assuming they
only gave you strings that were small enough to be decideable, but
still, it's a bit funny that they picked this one.
Dan
On 11/6/06, Nicholas Leippe <[EMAIL PROTECTED]> wrote:
> I don't have the text to the problem questions. Maybe someone that saved them
> or someone from mozy will post them. I'll just summarize them.
>
> The first problem was to evaluate a line full of parenthesis. If they were not
> balanced on the line output a 0. If they were balanced, output the maximum
> nesting depth.
>
> <?
> while ($line = fgets(STDIN)) {
> $mx = 0;
> $cur_depth = 0;
> for ($i = 0; $i < strlen($line); $i++) {
> $p = $line{$i};
> if ($p == '(') {
> $cur_depth++;
> } else if ($p == ')') {
> $mx = max($mx, $cur_depth);
> $cur_depth--;
> }
> }
> if ($cur_depth == 0) {
> echo "$mx\n";
> } else {
> echo "0\n";
> }
> }
>
>
> /*
> PLUG: http://plug.org, #utah on irc.freenode.net
> Unsubscribe: http://plug.org/mailman/options/plug
> Don't fear the penguin.
> */
>
/*
PLUG: http://plug.org, #utah on irc.freenode.net
Unsubscribe: http://plug.org/mailman/options/plug
Don't fear the penguin.
*/
/*
PLUG: http://plug.org, #utah on irc.freenode.net
Unsubscribe: http://plug.org/mailman/options/plug
Don't fear the penguin.
*/
