Código Golf: Autómatas

Question

Hice el último generador de risas usando estas reglas. ¿Puedes implementarlo en tu idioma favorito de una manera inteligente?

Reglas:

En cada iteración, se producen las siguientes transformaciones.

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

MATLAB (v7.8.0):

73 caracteres (sin incluir los caracteres de formato utilizados para que parezca legible)

Este script (" jaja.m ") asume que ya ha definido la variable n :

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

... y aquí está la versión de una línea:

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

Prueba :

>> 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

Answer 2

Lex / Flex

69 caracteres. En el texto aquí, cambié las pestañas a 8 espacios para que se vea bien, pero todos esos espacios consecutivos deberían ser pestañas, y las pestañas son importantes, por lo que sale a 69 caracteres.

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

Para lo que vale, el lex.yy.c generado tiene 42736 caracteres, pero no creo que eso realmente cuente. Puedo (y pronto lo haré) escribir una versión pura de C que será mucho más corta y haré lo mismo, pero creo que probablemente debería ser una entrada separada.

EDIT:

Aquí hay una entrada Lex / Flex más legítima (302 caracteres):

        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;}

Esto hace múltiples iteraciones (a diferencia de la última, que solo hizo una iteración, y tuvo que ser sembrada manualmente cada vez, pero produjo los resultados correctos) y tiene la ventaja de ser un código de aspecto extremadamente horrible. Yo uso una macro de función, el operador de encadenamiento y dos variables globales. Si desea una versión aún más desordenada que ni siquiera verifique la falla de malloc () , se ve así (282 caracteres):

        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;}

Se podría inventar una versión aún peor donde c es una matriz en la pila, y simplemente le damos un MAX_BUFFER_SIZE de algún tipo, pero creo que eso está tomando esto demasiado lejos.

... Es broma. 207 caracteres si tomamos los " 99 caracteres siempre serán suficientes " mentalidad:

        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;}

Mi preferencia es la que funciona mejor (es decir, la primera que puede iterar hasta que se agote la memoria y verifique sus errores), pero este es el código golf.

Para compilar el primero, escriba:

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

(Si tiene lex en lugar de flex , simplemente cambie flex a lex . Deberían ser compatibles .)

Para compilar los demás, escriba:

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

O bien, GCC se quejará de & # 8216; para & # 8217; declaración inicial de bucle utilizada fuera del modo C99 y otra basura.

Respuesta pura de C próximamente.

Answer 3

Una traducción simple a 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 [] = []

Y una versión más corta (122 caracteres, optimizada para tres reglas de derivación + caso base):

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[]=[]}

Y una traducción a C ++ (182 caracteres, solo realiza una iteración, invocar con estado inicial en la línea de comando):

#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 4

Javascript:

¡120 espacios en blanco de pelado y lo dejo solo ahora!

function f(n,s){s='H';while(n--){s=s.replace(/HAA|AAH|HH?|AA?/g,function(a){return a.match(/^H/)?'AH':'HA'});};return s}

Ampliado:

function f(n,s)
{
    s = 'H';
    while (n--)
    {
        s = s.replace(/HAA|AAH|HH?|AA?/g, function(a) { return a.match(/^H/) ? 'AH' : 'HA' } );
    };
    return s
}

¡ese sustituto es caro!

Answer 5

Aquí hay un ejemplo de C #, llegando a 321 bytes si reduzco el espacio en blanco a un espacio entre cada elemento.

Editar : en respuesta al @Johannes Rössel , eliminé los genéricos de la solución para buscar algunos bytes más.

Editar : Otro cambio, eliminó todas las variables temporales.

public static String E(String i)
{
    return new Regex("HAA|AAH|HH|AA|A|H").Replace(i, 
        m => (String)new Hashtable {
            { "H", "AH" },
            { "A", "HA" },
            { "AA", "HA" },
            { "HH", "AH" },
            { "AAH", "HA" },
            { "HAA", "AH" }
        }[m.Value]);
}

La solución reescrita con menos espacio en blanco, que aún se compila, tiene 158 caracteres:

return new Regex("HAA|AAH|HH|AA|A|H").Replace(i,m =>(String)new Hashtable{{"H","AH"},{"A","HA"},{"AA","HA"},{"HH","AH"},{"AAH","HA"},{"HAA","AH"}}[m.Value]);

Para una solución completa de código fuente para Visual Studio 2008, a continuación se encuentra disponible un repositorio de subversión con el código necesario, incluidas las pruebas unitarias.

El repositorio está aquí , nombre de usuario y la contraseña son 'invitados', sin las comillas.

Answer 6

Rubí

Este código de golf no está muy bien especificado: supuse que la función que devuelve la cadena de iteración n es la mejor manera de resolverlo. Tiene 80 caracteres.

def f n
a='h'
n.times{a.gsub!(/(h(h|aa)?)|(a(ah?)?)/){$1.nil?? "ha":"ah"}}
a
end

Código imprimiendo n primeras cadenas (71 caracteres):

a='h';n.times{puts a.gsub!(/(h(h|aa)?)|(a(ah?)?)/){$1.nil?? "ha":"ah"}}

Answer 7

Erlang

241 bytes y listo para ejecutar:

> erl -noshell -s g i -s init stop
AHAHHAAHAHHA

-module(g).
-export([i/0]).
c("HAA"++T)->"AH"++c(T);
c("AAH"++T)->"HA"++c(T);
c("HH"++T)->"AH"++c(T);
c("AA"++T)->"HA"++c(T);
c("A"++T)->"HA"++c(T);
c("H"++T)->"AH"++c(T);
c([])->[].
i(0,L)->L;
i(N,L)->i(N-1,c(L)).
i()->io:format(i(9,"H"))

Probablemente podría mejorarse.

Answer 8

Perl 168 caracteres.

(sin contar nuevas líneas innecesarias)

perl -E'
($s,%m)=qw[H H AH A HA AA HA HH AH AAH HA HAA AH];
sub p{say qq[n = 
  Perl  168 caracteres. 

  (sin contar nuevas líneas innecesarias)  

use strict;
use warnings;
use 5.010;

my $str = 'H';

my %map = (
    H => 'AH',
    A => 'HA',
   AA => 'HA',
   HH => 'AH',
  AAH => 'HA',
  HAA => 'AH'
);

sub prn{
 my( $n, $str ) = @_;
 say "n = $n |  $str"
}

prn( 0, $str );

for my $i ( 1..9 ){
  $str =~ s(
    (
      H(?:AA|H)? # HAA | HH | H
    |
      A(?:AH?)?  # AAH | AA | A
    )
  ){
    $map{$1}
  }xge;

  prn( $i, $str );
}

say 'n = ...';


 Desfuscado: 

perl -E'
$s="H";
sub p{say qq[n = 
  Perl  168 caracteres. 

  (sin contar nuevas líneas innecesarias)  

perl -E'
($s,%m)=qw[H H AH A HA AA HA HH AH AAH HA HAA AH];
sub p{say qq[n = 
  Perl  168 caracteres. 

  (sin contar nuevas líneas innecesarias)  

use strict;
use warnings;
use 5.010;

my $str = 'H';

my %map = (
    H => 'AH',
    A => 'HA',
   AA => 'HA',
   HH => 'AH',
  AAH => 'HA',
  HAA => 'AH'
);

sub prn{
 my( $n, $str ) = @_;
 say "n = $n |  $str"
}

prn( 0, $str );

for my $i ( 1..9 ){
  $str =~ s(
    (
      H(?:AA|H)? # HAA | HH | H
    |
      A(?:AH?)?  # AAH | AA | A
    )
  ){
    $map{$1}
  }xge;

  prn( $i, $str );
}

say 'n = ...';


 Desfuscado: 

#! /usr/bin/env perl
use strict;
use warnings;
use 5.010;

my $str = 'H';

sub prn{
 my( $n, $str ) = @_;
 say "n = $n |  $str"
}

prn( 0, $str );

for my $i ( 1..9 ){
  $str =~ s{(?|
        (H)(?:AA|H)? # HAA | HH | H
      |
        (A)(?:AH?)?  # AAH | AA | A
    )}{
      ( 'H' eq $1 ?'A' :'H' ).$1
    }egx;
  prn( $i, $str );
}

say 'n = ...';


  Perl  150 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado 

<*>[0] |  
  Perl  168 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado: 

<*>

  Perl  150 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado 

<*>[1]]};p(0,$s);
for(1..9){$s=~s/(H(AA|H)?|A(AH?)?)/$m{$1}/g;p(
  Perl  168 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado: 

<*>

  Perl  150 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado 

<*>,$s)}
say q[n = ...]'


 Desfuscado: 

<*>

  Perl  150 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado 

<*>[0] |  
  Perl  168 caracteres. 

  (sin contar nuevas líneas innecesarias)  

perl -E'
($s,%m)=qw[H H AH A HA AA HA HH AH AAH HA HAA AH];
sub p{say qq[n = 
  Perl  168 caracteres. 

  (sin contar nuevas líneas innecesarias)  

use strict;
use warnings;
use 5.010;

my $str = 'H';

my %map = (
    H => 'AH',
    A => 'HA',
   AA => 'HA',
   HH => 'AH',
  AAH => 'HA',
  HAA => 'AH'
);

sub prn{
 my( $n, $str ) = @_;
 say "n = $n |  $str"
}

prn( 0, $str );

for my $i ( 1..9 ){
  $str =~ s(
    (
      H(?:AA|H)? # HAA | HH | H
    |
      A(?:AH?)?  # AAH | AA | A
    )
  ){
    $map{$1}
  }xge;

  prn( $i, $str );
}

say 'n = ...';


 Desfuscado: 

<*>

  Perl  150 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado 

<*>[0] |  
  Perl  168 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado: 

<*>

  Perl  150 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado 

<*>[1]]};p(0,$s);
for(1..9){$s=~s/(H(AA|H)?|A(AH?)?)/$m{$1}/g;p(
  Perl  168 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado: 

<*>

  Perl  150 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado 

<*>,$s)}
say q[n = ...]'


 Desfuscado: 

<*>

  Perl  150 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado 

<*>[1]]};p(0,$s);
for(1..9){$s=~s/(?|(H)(?:AA|H)?|(A)(?:AH?)?)/("H"eq$1?"A":"H").$1/eg;p(
  Perl  168 caracteres. 

  (sin contar nuevas líneas innecesarias)  

perl -E'
($s,%m)=qw[H H AH A HA AA HA HH AH AAH HA HAA AH];
sub p{say qq[n = 
  Perl  168 caracteres. 

  (sin contar nuevas líneas innecesarias)  

use strict;
use warnings;
use 5.010;

my $str = 'H';

my %map = (
    H => 'AH',
    A => 'HA',
   AA => 'HA',
   HH => 'AH',
  AAH => 'HA',
  HAA => 'AH'
);

sub prn{
 my( $n, $str ) = @_;
 say "n = $n |  $str"
}

prn( 0, $str );

for my $i ( 1..9 ){
  $str =~ s(
    (
      H(?:AA|H)? # HAA | HH | H
    |
      A(?:AH?)?  # AAH | AA | A
    )
  ){
    $map{$1}
  }xge;

  prn( $i, $str );
}

say 'n = ...';


 Desfuscado: 

<*>

  Perl  150 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado 

<*>[0] |  
  Perl  168 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado: 

<*>

  Perl  150 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado 

<*>[1]]};p(0,$s);
for(1..9){$s=~s/(H(AA|H)?|A(AH?)?)/$m{$1}/g;p(
  Perl  168 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado: 

<*>

  Perl  150 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado 

<*>,$s)}
say q[n = ...]'


 Desfuscado: 

<*>

  Perl  150 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado 

<*>,$s)}
say q[n = ...]'


  Perl  150 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado 

<*>[0] |  
  Perl  168 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado: 

<*>

  Perl  150 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado 

<*>[1]]};p(0,$s);
for(1..9){$s=~s/(H(AA|H)?|A(AH?)?)/$m{$1}/g;p(
  Perl  168 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado: 

<*>

  Perl  150 caracteres. 

  (sin contar nuevas líneas innecesarias)  

<*>

 Desfuscado 

<*>,$s)}
say q[n = ...]'

Desfuscado:

<*>

Perl 150 caracteres.

(sin contar nuevas líneas innecesarias)

<*>

Desfuscado

<*>

Answer 9

Python (150 bytes)

import re
N = 10
s = "H"
for n in range(N):
    print "n = %d |"% n, s
    s = re.sub("(HAA|HH|H)|AAH|AA|A", lambda m: m.group(1) and "AH" or "HA",s)

Salida

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

Answer 10

Aquí hay una versión muy simple de C ++:

#include <iostream>
#include <sstream>
using namespace std;

#define LINES 10

#define put(t) s << t; cout << t

#define r1(o,a,c0) \
    if(c[0]==c0) {put(o); s.unget(); s.unget(); a; continue;}
#define r2(o,a,c0,c1) \
    if(c[0]==c0 && c[1]==c1) {put(o); s.unget(); a; continue;}
#define r3(o,a,c0,c1,c2) \
    if(c[0]==c0 && c[1]==c1 && c[2]==c2) {put(o); a; continue;}

int main() {
    char c[3];
    stringstream s;
    put("H\n\n");
    for(int i=2;i<LINES*2;) {
        s.read(c,3);
        r3("AH",,'H','A','A');
        r3("HA",,'A','A','H');
        r2("AH",,'H','H');
        r2("HA",,'A','A');
        r1("HA",,'A');
        r1("AH",,'H');
        r1("\n",i++,'\n');
    }
}

No es exactamente el código de golf (podría hacerse mucho más corto), pero funciona. Cambie LINES a la cantidad de líneas que desee imprimir (nota: no funcionará para 0 ). Imprimirá una salida como esta:

H

AH

HAAH

AHAH

HAAHHAAH

AHAHHA

HAAHHAAHHA

AHAHHAAHHA

HAAHHAAHHAAHHA

AHAHHAAHAHHA

Answer 11

ANSI C99

Llegando a un brutal 306 caracteres:

#include <stdio.h>
#include <string.h>
char s[99]="H",t[99]={0};int main(){for(int n=0;n<10;n++){int i=0,j=strlen(s);printf("n = %u |  %s\n",n,s);strcpy(t,s);s[0]=0;for(;i<j;){if(t[i++]=='H'){t[i]=='H'?i++:t[i+1]=='A'?i+=2:1;strcat(s,"AH");}else{t[i]=='A'?i+=1+(t[i+1]=='H'):1;strcat(s,"HA");}}}return 0;}

Hay demasiados ifs anidados y operadores condicionales para que pueda reducir esto de manera efectiva con macros. Créeme, lo intenté. Versión legible:

#include <stdio.h>
#include <string.h>
char s[99] = "H", t[99] = {0};
int main()
{
    for(int n = 0; n < 10; n++)
      {
        int i = 0, j = strlen(s);
        printf("n = %u |  %s\n", n, s);
        strcpy(t, s);
        s[0] = 0;
        /*
         * This was originally just a while() loop.
         * I tried to make it shorter by making it a for() loop.
         * I failed.
         * I kept the for() loop because it looked uglier than a while() loop.
         * This is code golf.
         */
        for(;i<j;)
          {
            if(t[i++] == 'H' )
              {
                // t[i] == 'H' ? i++ : t[i+1] == 'A' ? i+=2 : 1;
                // Oh, ternary ?:, how do I love thee?
                if(t[i] == 'H')
                    i++;
                else if(t[i+1] == 'A')
                    i+= 2;
                strcat(s, "AH");
              }
            else
              {
                // t[i] == 'A' ? i += 1 + (t[i + 1] == 'H') : 1;
                if(t[i] == 'A')
                    if(t[++i] == 'H')
                        i++;
                strcat(s, "HA");
              }
          }
      }
    return 0;
}

Es posible que pueda hacer una versión más corta con strncmp () en el futuro, pero ¿quién sabe? Veremos qué pasa.

Answer 12

En python:

def l(s):
 H=['HAA','HH','H','AAH','AA','A']
 L=['AH']*3+['HA']*3
 for i in [3,2,1]:
  if s[:i] in H: return L[H.index(s[:i])]+l(s[i:])
 return s

def a(n,s='H'):
 return s*(n<1)or a(n-1,l(s))

for i in xrange(0,10):
 print '%d: %s'%(i,a(i))

Primer intento: 198 caracteres de código, estoy seguro de que puede reducirse: D

Answer 13

REBOL, 150 caracteres. Desafortunadamente, REBOL no es un lenguaje propicio para el golf de código, pero 150 caracteres no son demasiado malos, como dice Adam Sandler.

Esto supone que la variable de bucle m ya se ha definido.

s: "H" r: "" z:[some[["HAA"|"HH"|"H"](append r "AH")|["AAH"|"AA"|"A"](append r "HA")]to end]repeat n m[clear r parse s z print["n =" n "|" s: copy r]]

Y aquí está con un mejor diseño:

s: "H"
r: ""
z: [
    some [
        [ "HAA" | "HH" | "H" ] (append r "AH")
    |   [ "AAH" | "AA" | "A" ] (append r "HA")
    ]
    to end
]

repeat n m [
    clear r
    parse s z
    print ["n =" n "|" s: copy r]
]

Answer 14

F #: 184 caracteres

Parece que se asigna bastante limpiamente a F #:

type grammar = H | A
let rec laugh = function
    | 0,l -> l
    | n,l ->
        let rec loop = function
            |H::A::A::x|H::H::x|H::x->A::H::loop x
            |A::A::H::x|A::A::x|A::x->H::A::loop x
            |x->x
        laugh(n-1,loop l)

Aquí hay una ejecución en fsi:

> [for a in 0 .. 9 -> a, laugh(a, [H])] |> Seq.iter (fun (a, b) -> printfn "n = %i: %A" a b);;
n = 0: [H]
n = 1: [A; H]
n = 2: [H; A; A; H]
n = 3: [A; H; A; H]
n = 4: [H; A; A; H; H; A; A; H]
n = 5: [A; H; A; H; H; A]
n = 6: [H; A; A; H; H; A; A; H; H; A]
n = 7: [A; H; A; H; H; A; A; H; H; A]
n = 8: [H; A; A; H; H; A; A; H; H; A; A; H; H; A]
n = 9: [A; H; A; H; H; A; A; H; A; H; H; A]