Code Golf:Automata

Question

我使用这些规则制作了终极笑发生器.你能用聪明的方式用自己喜欢的语言实现它吗？

规则:

在每次迭代时,都会发生以下转换.

H   -> AH
A   -> HA
AA  -> HA
HH  -> AH
AAH -> HA
HAA -> AH

n = 0 |  H
n = 1 |  AH
n = 2 |  HAAH
n = 3 |  AHAH
n = 4 |  HAAHHAAH
n = 5 |  AHAHHA
n = 6 |  HAAHHAAHHA
n = 7 |  AHAHHAAHHA
n = 8 |  HAAHHAAHHAAHHA
n = 9 |  AHAHHAAHAHHA
n = ...

Answer 1

莱克斯/ Flex的

69个字符.在这里的文本中,我将标签更改为8个空格,因此它看起来正确,但所有这些连续的空格应该是标签,并且标签很重要,因此它出现了69个字符.

        #include <stdio.h>
%%
HAA|HH|H        printf("AH");
AAH|AA|A        printf("HA");

对于它的价值,生成的lex.yy.c是42736个字符,但我认为这不重要.我可以(很快就会)编写一个更短的纯C版本并做同样的事情,但我觉得应该是一个单独的条目.

编辑:

这是一个更合法的Lex/Flex条目(302个字符):

        char*c,*t;
        #define s(a) t=c?realloc(c,strlen(c)+3):calloc(3,1);if(t)c=t,strcat(c,#a);
%%
        free(c);c=NULL;
HAA|HH|H        s(AH)
AAH|AA|A        s(HA)
%%
int main(void){c=calloc(2,1);if(!c)return 1;*c='H';for(int n=0;n<10;n++)printf("n = %d |  %s\n",n,c),yy_scan_string(c),yylex();return 0;}int yywrap(){return 1;}

这会进行多次迭代(与最后一次迭代不同,它只进行一次迭代,并且每次都必须手动播种,但产生了正确的结果)并且具有非常可怕的代码的优点.我使用函数宏,字符串化运算符和两个全局变量.如果你想要一个甚至没有检查malloc()失败的更加混乱的版本,它看起来像这样(282个字符):

        char*c,*t;
        #define s(a) t=c?realloc(c,strlen(c)+3):calloc(3,1);c=t;strcat(c,#a);
%%
        free(c);c=NULL;
HAA|HH|H        s(AH)
AAH|AA|A        s(HA)
%%
int main(void){c=calloc(2,1);*c='H';for(int n=0;n<10;n++)printf("n = %d |  %s\n",n,c),yy_scan_string(c),yylex();return 0;}int yywrap(){return 1;}

一个更糟糕的版本可以被编造在c堆栈上的数组,我们只是给它MAX_BUFFER_SIZE一些,但我觉得这是太过分了.

...开玩笑.如果我们采取"99个字符将永远足够"的心态,207个字符:

        char c[99]="H";
%%
        c[0]=0;
HAA|HH|H    strcat(c, "AH");
AAH|AA|A    strcat(c, "HA");
%%
int main(void){for(int n=0;n<10;n++)printf("n = %d |  %s\n",n,c),yy_scan_string(c),yylex();return 0;}int yywrap(){return 1;}

我的偏好是最好的(即第一个可以迭代直到内存耗尽并检查其错误),但这是代码高尔夫.

要编译第一个,请键入:

flex golf.l
gcc -ll lex.yy.c

(如果你有,lex而不是flex,只需flex改为lex.他们应该兼容.)

要编译其他人,请键入:

flex golf.l
gcc -std=c99 lex.yy.c

否则海湾合作委员会会抱怨‘for’ loop initial declaration used outside C99 mode和其他废话.

纯C答案即将到来.

Answer 2

对Haskell的简单翻译:

grammar = iterate step
    where
        step ('H':'A':'A':xs) = 'A':'H':step xs
        step ('A':'A':'H':xs) = 'H':'A':step xs
        step ('A':'A':xs) = 'H':'A':step xs
        step ('H':'H':xs) = 'A':'H':step xs
        step ('H':xs) = 'A':'H':step xs
        step ('A':xs) = 'H':'A':step xs
        step [] = []

还有一个较短的版本(122个字符,优化到三个派生规则+基本情况):

grammar=iterate s where{i 'H'='A';i 'A'='H';s(n:'A':m:x)|n/=m=m:n:s x;s(n:m:x)|n==m=(i n):n:s x;s(n:x)=(i n):n:s x;s[]=[]}

并转换为C++(182个字符,只进行一次迭代,在命令行上调用初始状态):

#include<cstdio>
#define o putchar
int main(int,char**v){char*p=v[1];while(*p){p[1]==65&&~*p&p[2]?o(p[2]),o(*p),p+=3:*p==p[1]?o(137-*p++),o(*p++),p:(o(137-*p),o(*p++),p);}return 0;}

Answer 3

MATLAB(v7.8.0):

73个字符(不包括用于使其看起来可读的格式字符)

这个脚本("haha.m")假设你已经定义了变量n:

s = 'H';
for i = 1:n,
  s = regexprep(s,'(H)(H|AA)?|(A)(AH)?','${[137-$1 $1]}');
end

......这是单行版本:

s='H';for i=1:n,s = regexprep(s,'(H)(H|AA)?|(A)(AH)?','${[137-$1 $1]}');end

测试:

>> for n=0:10, haha; disp([num2str(n) ': ' s]); end
0: H
1: AH
2: HAAH
3: AHAH
4: HAAHHAAH
5: AHAHHA
6: HAAHHAAHHA
7: AHAHHAAHHA
8: HAAHHAAHHAAHHA
9: AHAHHAAHAHHA
10: HAAHHAAHHAHAAHHA