コードゴルフ:オートマトン
https://stackoverflow.com/questions/831915
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
このルールを使って究極の笑いジェネレーターを作りました。あなたの好きな言語で賢い方法でそれを実装できますか?
ルール:
反復ごとに、次の変換が発生します。
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 = ...
解決
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
...そして、これが 1 行バージョンです。
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
他のヒント
Lex / Flex
69文字。ここのテキストでは、タブを8スペースに変更して見た目をよくしていますが、連続するスペースはすべてタブである必要があり、タブは重要であるため、69文字になります。
#include <stdio.h>
%%
HAA|HH|H printf("AH");
AAH|AA|A printf("HA");
価値のあるものとして、生成された lex.yy.c は42736文字ですが、それは本当に重要ではないと思います。かなり短くなり、同じことをするpure-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;}
これは複数の反復を行い（最後の反復では1回のみ反復し、毎回手動でシードする必要がありましたが、正しい結果を生成しました）、非常に恐ろしいコードであるという利点があります。関数マクロ、文字列化演算子、および2つのグローバル変数を使用します。 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 を与えるだけですが、これを取っているように感じます遠すぎます。
...冗談です。 ＆quot; 99文字を取得した場合、207文字で常に十分です＆quot;考え方：
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
（ flex の代わりに lex を使用している場合は、 flex を lex に変更します。これらは互換性があるはずです。 。）
その他をコンパイルするには、次のように入力します：
flex golf.l
gcc -std=c99 lex.yy.c
それ以外の場合、GCCは＆＃8216; for＆＃8217; C99モード以外で使用されるループ初期宣言およびその他のがらくた。
純粋なCの回答が近づいています。
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文字、3つの派生ルールに最適化+ベースケース）：
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文字、1回の反復のみ、コマンドラインで初期状態で呼び出します）：
#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個の空白を削除し、今はそのままにします！
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}
拡張：
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
}
代替品は高価です！
次のC＃の例では、空白を各アイテム間のスペースを1つに減らすと、321バイトになります。
編集： @Johannes R＆＃246; ssel コメントへの応答として、ソリューションからジェネリックを削除して、さらに数バイトを取り出しました。
編集：別の変更。すべての一時変数を削除しました。
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]);
}
空白を減らして、まだコンパイルされている書き換えられたソリューションは、158文字です：
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]);
Visual Studio 2008の完全なソースコードソリューションについては、ユニットテストを含む必要なコードを含むSubversionリポジトリを以下から入手できます。
リポジトリはこちら、ユーザー名とパスワードは両方とも引用符なしの「ゲスト」です。
ルビー
このゴルフはあまり明確に指定されていません- n 番目の反復文字列を返す関数がそれを解決する最良の方法であると想定しました。 80文字です。
def f n
a='h'
n.times{a.gsub!(/(h(h|aa)?)|(a(ah?)?)/){$1.nil?? "ha":"ah"}}
a
end
最初の文字列（71文字）を印刷するコード n ：
a='h';n.times{puts a.gsub!(/(h(h|aa)?)|(a(ah?)?)/){$1.nil?? "ha":"ah"}}
アーラン
241バイトで実行準備完了：
> 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"))
おそらく改善される可能性があります。
Perl 168文字。
（不要な改行をカウントしない）
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文字。
（不要な改行をカウントしない）
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 -E'
$s="H";
sub p{say qq[n = Perl 168文字。
（不要な改行をカウントしない）
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文字。
（不要な改行をカウントしない）
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 = ...';
難読化解除：
#! /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文字。
（不要な改行をカウントしない）
<*>
難読化解除
<*>[0] | Perl 168文字。
（不要な改行をカウントしない）
<*>
難読化解除：
<*>
Perl 150文字。
（不要な改行をカウントしない）
<*>
難読化解除
<*>[1]]};p(0,$s);
for(1..9){$s=~s/(H(AA|H)?|A(AH?)?)/$m{$1}/g;p( Perl 168文字。
（不要な改行をカウントしない）
<*>
難読化解除：
<*>
Perl 150文字。
（不要な改行をカウントしない）
<*>
難読化解除
<*>,$s)}
say q[n = ...]'
難読化解除：
<*>
Perl 150文字。
（不要な改行をカウントしない）
<*>
難読化解除
<*>[0] | Perl 168文字。
（不要な改行をカウントしない）
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文字。
（不要な改行をカウントしない）
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文字。
（不要な改行をカウントしない）
<*>
難読化解除
<*>[0] | Perl 168文字。
（不要な改行をカウントしない）
<*>
難読化解除：
<*>
Perl 150文字。
（不要な改行をカウントしない）
<*>
難読化解除
<*>[1]]};p(0,$s);
for(1..9){$s=~s/(H(AA|H)?|A(AH?)?)/$m{$1}/g;p( Perl 168文字。
（不要な改行をカウントしない）
<*>
難読化解除：
<*>
Perl 150文字。
（不要な改行をカウントしない）
<*>
難読化解除
<*>,$s)}
say q[n = ...]'
難読化解除：
<*>
Perl 150文字。
（不要な改行をカウントしない）
<*>
難読化解除
<*>[1]]};p(0,$s);
for(1..9){$s=~s/(?|(H)(?:AA|H)?|(A)(?:AH?)?)/("H"eq$1?"A":"H").$1/eg;p( Perl 168文字。
（不要な改行をカウントしない）
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文字。
（不要な改行をカウントしない）
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文字。
（不要な改行をカウントしない）
<*>
難読化解除
<*>[0] | Perl 168文字。
（不要な改行をカウントしない）
<*>
難読化解除：
<*>
Perl 150文字。
（不要な改行をカウントしない）
<*>
難読化解除
<*>[1]]};p(0,$s);
for(1..9){$s=~s/(H(AA|H)?|A(AH?)?)/$m{$1}/g;p( Perl 168文字。
（不要な改行をカウントしない）
<*>
難読化解除：
<*>
Perl 150文字。
（不要な改行をカウントしない）
<*>
難読化解除
<*>,$s)}
say q[n = ...]'
難読化解除：
<*>
Perl 150文字。
（不要な改行をカウントしない）
<*>
難読化解除
<*>,$s)}
say q[n = ...]'
Perl 150文字。
（不要な改行をカウントしない）
<*>
難読化解除
<*>[0] | Perl 168文字。
（不要な改行をカウントしない）
<*>
難読化解除：
<*>
Perl 150文字。
（不要な改行をカウントしない）
<*>
難読化解除
<*>[1]]};p(0,$s);
for(1..9){$s=~s/(H(AA|H)?|A(AH?)?)/$m{$1}/g;p( Perl 168文字。
（不要な改行をカウントしない）
<*>
難読化解除：
<*>
Perl 150文字。
（不要な改行をカウントしない）
<*>
難読化解除
<*>,$s)}
say q[n = ...]'
難読化解除：
<*> Perl 150文字。
（不要な改行をカウントしない）
<*>難読化解除
<*>Python（150バイト）
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)
出力
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
これは非常に単純な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');
}
}
正確にはコードゴルフではありません（もっと短くすることもできます）が、機能します。 LINES を印刷する行数に変更します（注： 0 では機能しません）。次のような出力を印刷します。
H
AH
HAAH
AHAH
HAAHHAAH
AHAHHA
HAAHHAAHHA
AHAHHAAHHA
HAAHHAAHHAAHHA
AHAHHAAHAHHA
ANSI C99
残忍な306文字でやってくる：
#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;}
マクロを使用して効果的にこれを減らすには、ネストされたifと条件演算子が多すぎます。私を信じて、試してみました。読み取り可能なバージョン：
#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;
}
将来、 strncmp（）を使用して短いバージョンを作成できるかもしれませんが、誰が知っていますか？どうなるか見てみましょう。
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))
最初の試行：198文字のコード、より小さくできると確信しています：D
REBOL、150文字。残念ながら、REBOLはゴルフをコーディングするのに役立つ言語ではありませんが、Adam Sandlerが言うように、150文字は粗末ではありません。
これは、ループ変数 m がすでに定義されていることを前提としています。
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]]
そして、ここではレイアウトが改善されています：
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文字
かなりきれいに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)
これは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]
