mozy contest: problem 1 PHP solution

Steve smorrey at gmail.com
Mon Nov 6 10:59:42 MST 2006


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. <dcrookston at gmail.com> 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 <nick at leippe.com> 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.
> */
>



More information about the PLUG mailing list