Solution to QOTW #23 in language of QOTW #24
Daniel Martin <martin-+m399P62/[email protected]> Sat, 18 Sep 2004 14:23:00 -0400
| Newsgroups | gmane.comp.lang.perl.qotw.discuss |
|---|---|
| Message-ID | <[email protected]> |
As a demonstration that turing machines can indeed do all the things more
convenient computer systems can, I attach a solution to the "parens" problem of
a few weeks ago in the turing machine language of QOTW #24.
Unfortunately, the restriction on the output format means that it can't quite
output like QOTW #23 specified. However, doing this should get you the right
output (assuming that your turing machine interpreter is called tm.pl, and that
you have a "tr" program that understands backslashed escapes):
perl tm.pl parens.tm 4 | tr 'xo_' '()\n'
If you're missing a decent version of tr, you can do:
perl tm.pl parens.tm 4 | perl -pe '$_=tr/xo_/()\n/'
The initial tape passed in should contain a single decimal number.
This solution is heavily based on mjd's regexp madness solution to QOTW #23.
--
@/=map{[/./g]}qw/.h_nJ Xapou cets krht ele_ r_ra/;
map{y/X_/\n /;print}map{pop@$_}@/for@/
parens.tm
(text/plain, 2.6 KB)
# Initialize things by making a "xo" string as long as # the decimal input says # scan to end-of-number ste 1 ste 1 R ste 2 ste 2 R ste 3 ste 3 R ste 4 ste 4 R ste 5 ste 5 R ste 6 ste 6 R ste 7 ste 7 R ste 8 ste 8 R ste 9 ste 9 R ste 0 ste 0 R ste _ dec _ L # find something to decrement dec 1 addinitxo1 0 R dec 2 addinitxo1 1 R dec 3 addinitxo1 2 R dec 4 addinitxo1 3 R dec 5 addinitxo1 4 R dec 6 addinitxo1 5 R dec 7 addinitxo1 6 R dec 8 addinitxo1 7 R dec 9 addinitxo1 8 R dec 0 dec 0 L dec _ cleartobegin _ R addinitxo1 0 addinitxo1 9 R addinitxo1 _ addinitxo2 _ R addinitxo2 x addinitxo2 x R addinitxo2 o addinitxo2 o R addinitxo2 _ addinitxo3 x R addinitxo3 _ backtonum o L backtonum x backtonum x L backtonum o backtonum o L backtonum _ dec _ L cleartobegin 0 cleartobegin _ R cleartobegin _ fsxs1 _ R # done initialization - now we get to the meat of it # Find second x string fsxs1 x fsxs1 x R fsxs1 o fsxs2 o R fsxs2 o fsxs2 o R fsxs2 x capend X R # Capitalize until end-of-string capend x capend X R capend o capend O R capend _ match1 _ L #Match #ignore O,X,Q,Y (L) match1 O match1 O L match1 X match1 X L match1 Q match1 Q L match1 Y match1 Y L match1 o match2 Q L match1 _ deqy _ R match1 x addx1 Y R #ignore o,Y (L) match2 o match2 o L match2 Y match2 Y L match2 x addxo1 Y R #addx #ignore Y,Q,X,O (R) addx1 Y addx1 Y R addx1 Q addx1 Q R addx1 X addx1 X R addx1 O addx1 O R addx1 _ addx2 _ R #ignore x,o,Q (R) addx2 x addx2 x R addx2 o addx2 o R addx2 Q addx2 Q R addx2 _ backm1 x L #addxo #ignore o,Y,Q,X,O (R) addxo1 o addxo1 o R addxo1 Y addxo1 Y R addxo1 Q addxo1 Q R addxo1 X addxo1 X R addxo1 O addxo1 O R addxo1 _ addxo2 _ R #ignore x,o addxo2 x addxo2 x R addxo2 o addxo2 o R addxo2 Q addxo2 o R addxo2 _ addxo3 x R addxo3 _ backm1 Q L #backm1 - back to state match1 #ignore x,o,Q backm1 x backm1 x L backm1 o backm1 o L backm1 Q backm1 Q L backm1 _ match1 _ L #deqy - Remove Q,Y deqy Q deqy o R deqy Y deqy x R deqy X cpfind X L #cpfind - find stuff to copy cpfind x cpfind x R cpfind o cpfind o R cpfind X copyx1 x R cpfind O copyo1 o R cpfind _ fsxs1 _ R #copyx copyx1 X copyx1 X R copyx1 O copyx1 O R copyx1 _ copyx2 _ R copyx2 x copyx2 x R copyx2 o copyx2 o R copyx2 Q copyo2 x R copyx2 _ backcpfind x L #copyo copyo1 X copyo1 X R copyo1 O copyo1 O R copyo1 _ copyo2 _ R copyo2 x copyo2 x R copyo2 o copyo2 o R copyo2 _ backcpfind o L #backcpfind - back to cpfind backcpfind x backcpfind x L backcpfind o backcpfind o L backcpfind _ backcpfind2 _ L backcpfind2 X backcpfind2 X L backcpfind2 O backcpfind2 O L backcpfind2 x cpfind x R backcpfind2 o cpfind o R