Re: Solution to QOTW #23 in language of QOTW #24
Mark Jason Dominus <[email protected]> Tue, 21 Sep 2004 14:28:46 -0400
| Newsgroups | gmane.comp.lang.perl.qotw.discuss |
|---|---|
| Message-ID | <[email protected]> |
On Sep 21, 2004, at 1:51 PM, Mark Jason Dominus wrote:
> I think it has fewer
> states and fewer total instructions,
I realize now that I could have gotten rid of at least one state and
five instructions:
>
> C_scan_R [ C_scan_R [ R
> C_scan_R ] C_scan_R ] R
> C_scan_R ( C_close [ R
> C_scan_R ) C_close [ R
> C_scan_R _ D_fix _ L
>
> C_close ( C_open ] R
> C_close ) C_open ] R
>
> C_open ( C_close [ R
> C_open ) C_close [ R
> C_open _ D_fix _ L
C_open is superfluous here; I could re-use C_scan_R instead, like this:
>
> C_close ( C_scan_R ] R
> C_close ) C_scan_R ] R
and then get rid of C_open and its three instructions entirely.
By the time control reaches section D, there are no remaining ( or )
marks; they have all been replaced with [ and ]. So these instructions
can be eliminated:
>
> D_fix ( D_fix ( L
> D_fix ) D_fix ) L
>
None of this affects the performance of the algorithm, however.
Total run time to generate strings of 2n parentheses is about
19n-27 steps per string.
init: <(>) ( ) ( )
init: (<)>( ) ( )
init: ( )<(>) ( )
init: ( ) (<)>( )
init: ( ) ( )<(>)
init: ( ) ( ) (<)
init: ( ) ( ) ( )<_
()()()
A_scan_1: ( ) ( ) (<)>_
A_scan_1: ( ) ( )<(>) _
A_scan_2: ( ) (<)>( ) _
A_change: ( ) ( [<(>) _
B_scan_L: ( ) (<[>] ) _
B_scan_L: ( )<(>[ ] ) _
B_scan_R: ( ) [<[>] ) _
B_scan_R: ( ) [ [<]>) _
B_scan_R: ( ) [ [ ]<)>_
B_scan_L: ( ) [ [<]>] _
B_scan_L: ( ) [<[>] ] _
B_scan_L: ( )<[>[ ] ] _
B_scan_L: (<)>[ [ ] ] _
B_scan_L: <(>) [ [ ] ] _
B_scan_R: [<)>[ [ ] ] _
B_scan_L: <[>] [ [ ] ] _
B_scan_L: <_>[ ] [ [ ] ] _
C_scan_R: _<[>] [ [ ] ] _
C_scan_R: _ [<]>[ [ ] ] _
C_scan_R: _ [ ]<[>[ ] ] _
C_scan_R: _ [ ] [<[>] ] _
C_scan_R: _ [ ] [ [<]>] _
C_scan_R: _ [ ] [ [ ]<]>_
C_scan_R: _ [ ] [ [ ] ]<_
D_fix: _ [ ] [ [ ]<]>_
D_fix: _ [ ] [ [<]>) _
D_fix: _ [ ] [<[>) ) _
D_fix: _ [ ]<[>( ) ) _
D_fix: _ [<]>( ( ) ) _
D_fix: _<[>) ( ( ) ) _
D_fix: <_>( ) ( ( ) ) _
init: _<(>) ( ( ) ) _
init: _ (<)>( ( ) ) _
init: _ ( )<(>( ) ) _
init: _ ( ) (<(>) ) _
init: _ ( ) ( (<)>) _
init: _ ( ) ( ( )<)>_
init: _ ( ) ( ( ) )<_
()(())
A_scan_1: _ ( ) ( ( )<)>_
A_scan_1: _ ( ) ( (<)>) _
A_scan_1: _ ( ) (<(>) ) _
A_scan_2: _ ( )<(>( ) ) _
A_scan_2: _ (<)>( ( ) ) _
A_change: _ ( [<(>( ) ) _
B_scan_L: _ (<[>] ( ) ) _
B_scan_L: _<(>[ ] ( ) ) _
B_scan_R: _ [<[>] ( ) ) _
B_scan_R: _ [ [<]>( ) ) _
B_scan_R: _ [ [ ]<(>) ) _
B_scan_L: _ [ [<]>] ) ) _
B_scan_L: _ [<[>] ] ) ) _
B_scan_L: _<[>[ ] ] ) ) _
B_scan_L: <_>[ [ ] ] ) ) _
C_scan_R: _<[>[ ] ] ) ) _
C_scan_R: _ [<[>] ] ) ) _
C_scan_R: _ [ [<]>] ) ) _
C_scan_R: _ [ [ ]<]>) ) _
C_scan_R: _ [ [ ] ]<)>) _
C_close: _ [ [ ] ] [<)>_
C_open: _ [ [ ] ] [ ]<_
D_fix: _ [ [ ] ] [<]>_
D_fix: _ [ [ ] ]<[>) _
D_fix: _ [ [ ]<]>( ) _
D_fix: _ [ [<]>) ( ) _
D_fix: _ [<[>) ) ( ) _
D_fix: _<[>( ) ) ( ) _
D_fix: <_>( ( ) ) ( ) _
init: _<(>( ) ) ( ) _
init: _ (<(>) ) ( ) _
init: _ ( (<)>) ( ) _
init: _ ( ( )<)>( ) _
init: _ ( ( ) )<(>) _
init: _ ( ( ) ) (<)>_
init: _ ( ( ) ) ( )<_
(())()
A_scan_1: _ ( ( ) ) (<)>_
A_scan_1: _ ( ( ) )<(>) _
A_scan_2: _ ( ( )<)>( ) _
A_change: _ ( ( ) [<(>) _
B_scan_L: _ ( ( )<[>] ) _
B_scan_L: _ ( (<)>[ ] ) _
B_scan_L: _ (<(>) [ ] ) _
B_scan_R: _ ( [<)>[ ] ) _
B_scan_L: _ (<[>] [ ] ) _
B_scan_L: _<(>[ ] [ ] ) _
B_scan_R: _ [<[>] [ ] ) _
B_scan_R: _ [ [<]>[ ] ) _
B_scan_R: _ [ [ ]<[>] ) _
B_scan_R: _ [ [ ] [<]>) _
B_scan_R: _ [ [ ] [ ]<)>_
B_scan_L: _ [ [ ] [<]>] _
B_scan_L: _ [ [ ]<[>] ] _
B_scan_L: _ [ [<]>[ ] ] _
B_scan_L: _ [<[>] [ ] ] _
B_scan_L: _<[>[ ] [ ] ] _
B_scan_L: <_>[ [ ] [ ] ] _
C_scan_R: _<[>[ ] [ ] ] _
C_scan_R: _ [<[>] [ ] ] _
C_scan_R: _ [ [<]>[ ] ] _
C_scan_R: _ [ [ ]<[>] ] _
C_scan_R: _ [ [ ] [<]>] _
C_scan_R: _ [ [ ] [ ]<]>_
C_scan_R: _ [ [ ] [ ] ]<_
D_fix: _ [ [ ] [ ]<]>_
D_fix: _ [ [ ] [<]>) _
D_fix: _ [ [ ]<[>) ) _
D_fix: _ [ [<]>( ) ) _
D_fix: _ [<[>) ( ) ) _
D_fix: _<[>( ) ( ) ) _
D_fix: <_>( ( ) ( ) ) _
init: _<(>( ) ( ) ) _
init: _ (<(>) ( ) ) _
init: _ ( (<)>( ) ) _
init: _ ( ( )<(>) ) _
init: _ ( ( ) (<)>) _
init: _ ( ( ) ( )<)>_
init: _ ( ( ) ( ) )<_
(()())
A_scan_1: _ ( ( ) ( )<)>_
A_scan_1: _ ( ( ) (<)>) _
A_scan_1: _ ( ( )<(>) ) _
A_scan_2: _ ( (<)>( ) ) _
A_change: _ ( ( [<(>) ) _
B_scan_L: _ ( (<[>] ) ) _
B_scan_L: _ (<(>[ ] ) ) _
B_scan_R: _ ( [<[>] ) ) _
B_scan_R: _ ( [ [<]>) ) _
B_scan_R: _ ( [ [ ]<)>) _
B_scan_L: _ ( [ [<]>] ) _
B_scan_L: _ ( [<[>] ] ) _
B_scan_L: _ (<[>[ ] ] ) _
B_scan_L: _<(>[ [ ] ] ) _
B_scan_R: _ [<[>[ ] ] ) _
B_scan_R: _ [ [<[>] ] ) _
B_scan_R: _ [ [ [<]>] ) _
B_scan_R: _ [ [ [ ]<]>) _
B_scan_R: _ [ [ [ ] ]<)>_
B_scan_L: _ [ [ [ ]<]>] _
B_scan_L: _ [ [ [<]>] ] _
B_scan_L: _ [ [<[>] ] ] _
B_scan_L: _ [<[>[ ] ] ] _
B_scan_L: _<[>[ [ ] ] ] _
B_scan_L: <_>[ [ [ ] ] ] _
C_scan_R: _<[>[ [ ] ] ] _
C_scan_R: _ [<[>[ ] ] ] _
C_scan_R: _ [ [<[>] ] ] _
C_scan_R: _ [ [ [<]>] ] _
C_scan_R: _ [ [ [ ]<]>] _
C_scan_R: _ [ [ [ ] ]<]>_
C_scan_R: _ [ [ [ ] ] ]<_
D_fix: _ [ [ [ ] ]<]>_
D_fix: _ [ [ [ ]<]>) _
D_fix: _ [ [ [<]>) ) _
D_fix: _ [ [<[>) ) ) _
D_fix: _ [<[>( ) ) ) _
D_fix: _<[>( ( ) ) ) _
D_fix: <_>( ( ( ) ) ) _
init: _<(>( ( ) ) ) _
init: _ (<(>( ) ) ) _
init: _ ( (<(>) ) ) _
init: _ ( ( (<)>) ) _
init: _ ( ( ( )<)>) _
init: _ ( ( ( ) )<)>_
init: _ ( ( ( ) ) )<_
((()))
A_scan_1: _ ( ( ( ) )<)>_
A_scan_1: _ ( ( ( )<)>) _
A_scan_1: _ ( ( (<)>) ) _
A_scan_1: _ ( (<(>) ) ) _
A_scan_2: _ (<(>( ) ) ) _
A_scan_2: _<(>( ( ) ) ) _
A_scan_2: <_>( ( ( ) ) ) _
Time: 176