Code Golf: Automates
-
06-07-2019 - |
Question
J'ai créé le générateur de rire ultime en utilisant ces règles. Pouvez-vous le mettre en œuvre intelligemment dans votre langue préférée?
Règles:
À chaque itération, les transformations suivantes ont lieu.
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 = ...
La solution
MATLAB (v7.8.0):
73 caractères (sans compter les caractères de formatage utilisés pour le rendre lisible)
Ce script ("haha.m") suppose que vous avez déjà défini la variable n :
s = 'H';
for i = 1:n,
s = regexprep(s,'(H)(H|AA)?|(A)(AH)?','${[137-$1 $1]}');
end
... et voici la version en une ligne:
s='H';for i=1:n,s = regexprep(s,'(H)(H|AA)?|(A)(AH)?','${[137-$1 $1]}');end
Test:
>> 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
Autres conseils
Lex / Flex
69 caractères. Dans le texte ci-dessous, j'ai remplacé les tabulations par 8 espaces pour que cela ait l'air correct, mais tous ces espaces consécutifs doivent être des tabulations, et les tabulations sont importantes, ce qui donne 69 caractères.
#include <stdio.h>
%%
HAA|HH|H printf("AH");
AAH|AA|A printf("HA");
Pour ce que cela vaut, le lex.yy.c
généré contient 42736 caractères, mais je ne pense pas que cela compte vraiment. Je peux (et vais bientôt) écrire une version en C pur qui sera beaucoup plus courte et fera la même chose, mais j'estime que cela devrait probablement être une entrée séparée.
EDIT:
Voici une entrée Lex / Flex plus légitime (302 caractères):
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;}
Cela fait plusieurs itérations (contrairement à la dernière, qui ne faisait qu'une itération et devait être ensemencée manuellement à chaque fois, mais produisait les résultats corrects) et qui présentait l'avantage d'être un code extrêmement horrible. J'utilise une macro de fonction, l'opérateur stringing et deux variables globales. Si vous voulez une version encore plus désordonnée qui ne vérifie même pas l’échec de malloc ()
, cela ressemble à ceci (282 caractères):
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;}
Une version encore pire pourrait être concoctée où c
est un tableau sur la pile, et nous lui donnons simplement un MAX_BUFFER_SIZE
, mais je sens que cela prend cela trop loin.
... Je plaisante. Si vous prenez 207 caractères, 207 caractères seront toujours suffisants " état d'esprit:
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;}
Ma préférence va à celle qui fonctionne le mieux (c'est-à-dire la première capable de parcourir jusqu'à épuisement de la mémoire et de vérifier ses erreurs), mais c'est du code golf.
Pour compiler le premier, tapez:
flex golf.l
gcc -ll lex.yy.c
(Si vous avez lex
au lieu de flex
, remplacez simplement flex
par lex
. Ils doivent être compatibles. .)
Pour compiler les autres, tapez:
flex golf.l
gcc -std=c99 lex.yy.c
Sinon, GCC se plaindra de & # 8216; pour & # 8217; déclaration initiale de la boucle utilisée en dehors du mode C99
et d'autres conneries.
La réponse en pur C à venir.
Une traduction simple en 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 [] = []
Et une version plus courte (122 caractères, optimisée jusqu'à trois règles de dérivation + cas de 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[]=[]}
Et une traduction en C ++ (182 caractères, une seule itération, invoquer avec l'état initial sur la ligne de commande):
#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;}
Javascript:
120 décapage des espaces et je le laisse seul maintenant!
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}
Développé:
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
}
ce substitut coûte cher!
Voici un exemple en C #, avec 321 octets si je réduis les espaces à un espace entre chaque élément.
Modifier : en réponse au commentaire de @Johannes R & # 246; ssel , J'ai supprimé les médicaments génériques de la solution pour obtenir quelques octets supplémentaires.
Éditer : autre changement, suppression de toutes les variables temporaires.
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 solution réécrite avec moins d'espaces, qui compile toujours, comporte 158 caractères:
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]);
Pour une solution complète de code source pour Visual Studio 2008, un référentiel de sous-version avec le code nécessaire, y compris les tests unitaires, est disponible ci-dessous.
Le référentiel est ici , nom d'utilisateur et mot de passe sont tous les deux 'invité', sans les guillemets.
Ruby
Ce code golf n’est pas très bien spécifié - j’ai supposé que la fonction renvoyant la n -th chaîne d’itération est la meilleure façon de le résoudre. Il a 80 caractères.
def f n
a='h'
n.times{a.gsub!(/(h(h|aa)?)|(a(ah?)?)/){$1.nil?? "ha":"ah"}}
a
end
Code imprimant les n premières chaînes (71 caractères):
a='h';n.times{puts a.gsub!(/(h(h|aa)?)|(a(ah?)?)/){$1.nil?? "ha":"ah"}}
Erlang
241 octets et prêt à fonctionner:
> 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"))
Peut probablement être amélioré.
Perl
168 caractères.
(sans compter les nouvelles lignes inutiles)
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 caractères.
(sans compter les nouvelles lignes inutiles)
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 = ...';
De-obscurci:
perl -E'
$s="H";
sub p{say qq[n = Perl
168 caractères.
(sans compter les nouvelles lignes inutiles)
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 caractères.
(sans compter les nouvelles lignes inutiles)
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 = ...';
De-obscurci:
#! /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 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci
<*>[0] | Perl
168 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci:
<*>
Perl
150 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci
<*>[1]]};p(0,$s);
for(1..9){$s=~s/(H(AA|H)?|A(AH?)?)/$m{$1}/g;p( Perl
168 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci:
<*>
Perl
150 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci
<*>,$s)}
say q[n = ...]'
De-obscurci:
<*>
Perl
150 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci
<*>[0] | Perl
168 caractères.
(sans compter les nouvelles lignes inutiles)
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 caractères.
(sans compter les nouvelles lignes inutiles)
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 = ...';
De-obscurci:
<*>
Perl
150 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci
<*>[0] | Perl
168 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci:
<*>
Perl
150 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci
<*>[1]]};p(0,$s);
for(1..9){$s=~s/(H(AA|H)?|A(AH?)?)/$m{$1}/g;p( Perl
168 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci:
<*>
Perl
150 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci
<*>,$s)}
say q[n = ...]'
De-obscurci:
<*>
Perl
150 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci
<*>[1]]};p(0,$s);
for(1..9){$s=~s/(?|(H)(?:AA|H)?|(A)(?:AH?)?)/("H"eq$1?"A":"H").$1/eg;p( Perl
168 caractères.
(sans compter les nouvelles lignes inutiles)
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 caractères.
(sans compter les nouvelles lignes inutiles)
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 = ...';
De-obscurci:
<*>
Perl
150 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci
<*>[0] | Perl
168 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci:
<*>
Perl
150 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci
<*>[1]]};p(0,$s);
for(1..9){$s=~s/(H(AA|H)?|A(AH?)?)/$m{$1}/g;p( Perl
168 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci:
<*>
Perl
150 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci
<*>,$s)}
say q[n = ...]'
De-obscurci:
<*>
Perl
150 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci
<*>,$s)}
say q[n = ...]'
Perl
150 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci
<*>[0] | Perl
168 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci:
<*>
Perl
150 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci
<*>[1]]};p(0,$s);
for(1..9){$s=~s/(H(AA|H)?|A(AH?)?)/$m{$1}/g;p( Perl
168 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci:
<*>
Perl
150 caractères.
(sans compter les nouvelles lignes inutiles)
<*>
De-obscurci
<*>,$s)}
say q[n = ...]'
De-obscurci:
<*> Perl
150 caractères.
(sans compter les nouvelles lignes inutiles)
<*>De-obscurci
<*>Python (150 octets)
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)
Sortie
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
Voici une version très 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');
}
}
Ce n’est pas exactement du code-golf (il pourrait être beaucoup plus court), mais ça marche. Modifiez LINES
en fonction du nombre de lignes à imprimer (remarque: cela ne fonctionnera pas pour 0
). Il imprimera le résultat comme ceci:
H
AH
HAAH
AHAH
HAAHHAAH
AHAHHA
HAAHHAAHHA
AHAHHAAHHA
HAAHHAAHHAAHHA
AHAHHAAHAHHA
ANSI C99
306 caractères brutaux à venir:
#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;}
Il y a trop de if imbriqués et d'opérateurs conditionnels pour que je puisse réduire cela efficacement avec les macros. Croyez-moi, j'ai essayé. Version lisible:
#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;
}
Je pourrai peut-être créer une version plus courte avec strncmp ()
, mais qui sait? Nous verrons ce qui se passe.
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))
Première tentative: 198 caractères de code, je suis sûr qu'il peut être plus petit: D
REBOL, 150 caractères. Malheureusement, REBOL n’est pas un langage propice à la codification du golf, mais 150 caractères ne sont pas si médiocres, comme le dit Adam Sandler.
Cela suppose que la variable de boucle m
a déjà été définie.
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]]
Et le voici avec une meilleure mise en page:
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] ]
F #: 184 caractères
Il semble que la correspondance soit nette avec 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)
Voici un essai 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]