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