# 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.
> */
>

```