puzzle - Código de golf: autómatas

code-golf rosetta-stone

Question

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

Reglas:

En cada iteración, ocurren 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

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 = $_[0] |  $_[1]]};p(0,$s);
for(1..9){$s=~s/(H(AA|H)?|A(AH?)?)/$m{$1}/g;p($_,$s)}
say q[n = ...]''

Despistado

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 = ...'';

Perl 150 caracteres.

(sin contar nuevas líneas innecesarias)

perl -E''
$s="H";
sub p{say qq[n = $_[0] |  $_[1]]};p(0,$s);
for(1..9){$s=~s/(?|(H)(?:AA|H)?|(A)(?:AH?)?)/("H"eq$1?"A":"H").$1/eg;p($_,$s)}
say q[n = ...]''

Despistado

#! /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 = ...'';

Answer 2

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 las 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 que pasa.

Answer 3

Javascript:

¡120 desnudando espacios en blanco 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}

Expandido:

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 4

Lex / Flex

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

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

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

EDITAR:

Aquí hay una entrada más legítima de Lex / Flex (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. Uso una macro de funciones, el operador de creación de cadenas y dos variables globales. Si desea una versión aún más desordenada que ni siquiera compruebe el error de malloc() , se parece a esto (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 solo le damos un MAX_BUFFER_SIZE de algún tipo, pero creo que eso está llevando esto demasiado lejos.

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

        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 por la que funciona mejor (es decir, la primera que puede iterar hasta que la memoria se agote y verifique sus errores), pero este es el código de golf.

Para compilar el primero, escribe:

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

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

Para compilar los otros, escriba:

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

O bien, GCC se quejará de ''for'' loop initial declaration used outside C99 mode y otra basura.

Pura respuesta C que viene.

Answer 5

MATLAB (v7.8.0):

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

Este script ("haha.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 6

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 7

Rubí

Este código de golf no está muy bien especificado; asumí 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 8

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

Edición : En respuesta al comentario de @Johannes Rössel , eliminé los genéricos de la solución para obtener algunos bytes más.

Edit : Otro cambio, se deshizo de 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 espacios 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 obtener 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í , el nombre de usuario y la contraseña son ''invitados'', sin las comillas.

Answer 9

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 un código de golf (se podría hacer mucho más corto), pero funciona. Cambie las LINES a las líneas que desee imprimir (nota: no funcionará para 0 ). Se imprimirá la salida de esta manera:

H

AH

HAAH

AHAH

HAAHHAAH

AHAHHA

HAAHHAAHHA

AHAHHAAHHA

HAAHHAAHHAAHHA

AHAHHAAHAHHA

Answer 10

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 hacerse más pequeño: D

Answer 11

REBOL, 150 caracteres. Desafortunadamente, REBOL no es un lenguaje propicio para codificar golf, pero 150 caracteres no están tan mal, como dice Adam Sandler.

Esto supone que la variable de bucle m ya ha sido definida.

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 mejor disposición:

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 12

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 hasta 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 hace una iteración, invoca con el 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 13

Erlang

241 bytes y listo para ejecutarse:

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

F #: 184 caracteres

Parece mapear bastante limpio 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 carrera 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]