Date: 2005-11-02 12:43 am (UTC)
I attach what I believe to be the implementation of the optimal algorithm. The proof is local to windows of size 3. First prove the windowing, then generate and fold the patterns.

I have also fixed the code (hence the repost) so it deals correctly with the degenerate cases (short sequences, end of sequence) correctly! All lines after the blank line deal with degenerate cases, and can be handled as special cases in the proof.

%{
#include <stdio.h>
#define OUT(x) do { fputs(#x, stdout); \
        if (#x[0] == yytext[0]) { score++; BEGIN(x); } \
        else BEGIN(INITIAL); } while(0)
static int  score = 0;
%}
%option noyywrap
%option noinput
%option nounput
%option noreject
%option debug
%option noyy_top_state
%x N Y
%%
<Y>N/NN { OUT(Y); }
<Y>N/NY { OUT(Y); }
<Y>N/Y  { OUT(Y); }
<N>Y/YY { OUT(N); }
<N>Y/YN { OUT(N); }
<N>Y/N  { OUT(N); }
<Y>Y    { OUT(Y); }
<N>N    { OUT(N); }
Y/Y     { OUT(Y); }
Y/NY    { OUT(Y); }
Y/NN    { OUT(N); }
N/YN    { OUT(N); }
N/YY    { OUT(Y); }
N/N     { OUT(N); }

<Y>N  { OUT(Y); }
<N>Y  { OUT(N); }
Y/N     { OUT(Y); }
N/Y     { OUT(N); }
Y       { OUT(Y); }
N       { OUT(N); }
%%
int main(void) {
    char    line[BUFSIZ];
    fgets(line, BUFSIZ, stdin);
    yy_scan_string(line);
    yylex();
    printf("Score = %d\n", score);
    return 0;
}
(will be screened)
(will be screened if not validated)
If you don't have an account you can create one now.
HTML doesn't work in the subject.
More info about formatting

If you are unable to use this captcha for any reason, please contact us by email at support@dreamwidth.org

Profile

ciphergoth: (Default)
Paul Crowley

January 2025

S M T W T F S
   1234
5678 91011
12131415161718
19202122232425
262728293031 

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 5th, 2025 09:13 pm
Powered by Dreamwidth Studios