--- Juho Snellman <[EMAIL PROTECTED]> wrote: > [1] The most cruel case being Greg Allen's solutions under 200. The > code worked on Activestate, but segfaulted on stock 5.6.1 on > Linux. No experimental regexp features. And it would have worked > with a maximum input size of 9980!
Indulge me, as I reminisce. Thanks of course to the hard work of the refs - good course, just don't make them that hard every time, or nothing will ever have time to happen in the other (real?) world... I also liked the fact that it was the algorithm that mattered, rather than golfing to achieve a fussy output format. The only cruelty was lack of time - I had just mastered a bottom up parsing approach, but ran out of spare time to work on it Sat night. I did have some other success though. http://www.colchesterfencing.co.uk/essex_open_results_me.html regarding the regexp approach: initially I feared replacing sub-expressions with postfix expressions, as I was convinced I'd never be able to match them correctly during later processing. Instead I started replacing sub-expressions with %n, where n indexes @0, then I did: s/%(\d+)/$0[$1]/ewhile/%/ appears I never submitted that approach though - just too long (mine was anyway). Eventually though I found this regexp which matches a simple number or any expression already in postfix: $*='(?:-?\d+(?: (?:[-*\/+]|-?\d+))*)' I then saw that I could remove the bracketed expressions from the bottom up, but my last submitted solution was still handling the +-*/ ops using top-down parsing 1/2/3/4 -> a(1/2/3)/4 -> etc. On the road I saw the overkill of this, therefore the possibility of doing */ and +- using the same regexp - no PC though, and the deadline inevitably passed. Back on the PC this morning and after just half an hour's work the strokes just melt away to an almost respectable 145.62: #!perl -pl sub a{ my$o='*/'; 0while s/\(([^()]+)\)/$_=$1;&a/e ||s&($*)([$o])($*)&$1 $3 $2& ||$o=~s&./&-+&; $_; } s/\s//g +a$*='(?:-?\d+(?: (?:[-*\/+]|-?\d+))*)' My 266 solution implements a recursive descent approach, without using RecDescent, and it never needs to backtrack explicitly (of course the regexps do tho). I could achieve this by pinching the regexp for a well bracketed expression from man perlre: $b=qr/\((?:(?>[^()]+)|(??{$b}))*\)/ and the rest from the grammar at the back of the C Language manual: so an atom is: $p=qr/$b|-?\d+/; and a factor is: ($p(?:[*\/]$p)*)) That allows you to write a recursive solution parsing addition then mult, then brackets, glueing the rests together on the way back up. well impressed by some of Eugene's tricks. is this first use seen in golf of /[@_^abc]/ or similar use of a variable toggle the meaning of the ^ ? until next month or minigolf time, Greg --- Juho Snellman <[EMAIL PROTECTED]> wrote: > [1] The most cruel case being Greg Allen's solutions under 200. The > code worked on Activestate, but segfaulted on stock 5.6.1 on > Linux. No experimental regexp features. And it would have worked > with a maximum input size of 9980! __________________________________________________ Do You Yahoo!? Yahoo! Finance - Get real-time stock quotes http://finance.yahoo.com
