views:

1423

answers:

14
+15  Q: 

Code Golf: Automata

I made the ultimate laugh generator using these rules. Can you implement it in your favorite language in a clever manner?

Rules:

On every iteration, the following transformations occur.

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 = ...
+1  A: 

Here is a very simple C++ version:

#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');
    }
}

It's not exactly code-golf (it could be made a lot shorter), but it works. Change LINES to however many lines you want printed (note: it will not work for 0). It will print output like this:

H

AH

HAAH

AHAH

HAAHHAAH

AHAHHA

HAAHHAAHHA

AHAHHAAHHA

HAAHHAAHHAAHHA

AHAHHAAHAHHA
Zifre
I was going to try to do this a similar way using lex/C (which I though would be easier), but this actually turned out to be very simple in C++ with a few macros.
Zifre
+5  A: 

A simple translation to 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 [] = []

And a shorter version (122 chars, optimized down to three derivation rules + base case):

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

And a translation to C++ (182 chars, only does one iteration, invoke with initial state on the command line):

#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;}
bdonlan
Wow that is an ugly 1 liner.
Unknown
Well, I was aiming for minimum size :)
bdonlan
The Haskell program is just so elegant :). I wish C++ were that cool...
Zifre
+6  A: 

MATLAB (v7.8.0):

73 characters (not including formatting characters used to make it look readable)

This script ("haha.m") assumes you have already defined the variable n:

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

...and here's the one-line version:

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
gnovice
Well this appears to be the shortest so far so I am accepting this. I never knew matlab code could be so condensed. I upvoted everyone that had a good effort.
Unknown
+2  A: 

Perl 168 characters.

(not counting unnecessary newlines)

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

De-obfuscated:

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

(not counting unnecessary newlines)

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

De-obfuscated

#! /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 = ...';
Brad Gilbert
+6  A: 

Lex/Flex

69 characters. In the text here, I changed tabs to 8 spaces so it would look right, but all those consecutive spaces should be tabs, and the tabs are important, so it comes out to 69 characters.

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

For what it's worth, the generated lex.yy.c is 42736 characters, but I don't think that really counts. I can (and soon will) write a pure-C version that will be much shorter and do the same thing, but I feel that should probably be a separate entry.

EDIT:

Here's a more legit Lex/Flex entry (302 characters):

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

This does multiple iterations (unlike the last one, which only did one iteration, and had to be manually seeded each time, but produced the correct results) and has the advantage of being extremely horrific-looking code. I use a function macro, the stringizing operator, and two global variables. If you want an even messier version that doesn't even check for malloc() failure, it looks like this (282 characters):

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

An even worse version could be concocted where c is an array on the stack, and we just give it a MAX_BUFFER_SIZE of some sort, but I feel that's taking this too far.

...Just kidding. 207 characters if we take the "99 characters will always be enough" mindset:

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

My preference is for the one that works best (i.e. the first one that can iterate until memory runs out and checks its errors), but this is code golf.

To compile the first one, type:

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

(If you have lex instead of flex, just change flex to lex. They should be compatible.)

To compile the others, type:

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

Or else GCC will whine about ‘for’ loop initial declaration used outside C99 mode and other crap.

Pure C answer coming up.

Chris Lutz
I must admit that I'm unfamiliar with Lex, so I was wondering A) how does your code get things started by initializing the string to 'H' and B) how do you get it to stop at a given n?
gnovice
I was lazy - the code does only one iteration. I'll figure out how to write a better version soon, but currently you put in "H" and it spits out "AH", so then you put in "AH" and it spits out "HAAH", and so on. I'l edit in a proper solution sometime, it's just very complicated. Anyway, to compile this code, type "flex file.l", which will generate the file "lex.yy.c". Compile it with a C compiler, and link to the lex library (libl.a most likely.)
Chris Lutz
+3  A: 

Javascript:

120 stripping whitespace and I'm leaving it alone now!

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}

Expanded:

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
}

that replacer is expensive!

annakata
+1  A: 

ANSI C99

Coming in at a brutal 306 characters:

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

There are too many nested ifs and conditional operators for me to effectively reduce this with macros. Believe me, I tried. Readable version:

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

I may be able to make a shorter version with strncmp() in the future, but who knows? We'll see what happens.

Chris Lutz
+3  A: 

Here's a C# example, coming in at 321 bytes if I reduce whitespace to one space between each item.

Edit: In response to @Johannes Rössel comment, I removed generics from the solution to eek out a few more bytes.

Edit: Another change, got rid of all temporary variables.

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

The rewritten solution with less whitespace, that still compiles, is 158 characters:

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]);

For a complete source code solution for Visual Studio 2008, a subversion repository with the necessary code, including unit tests, is available below.

Repository is here, username and password are both 'guest', without the quotes.

Lasse V. Karlsen
Couldn't you make the Dictionary non-generic and save a few bytes that way? (At the expense of runtime performance)
Joey
Didn't cross my mind actually, let me try that.
Lasse V. Karlsen
Change the method name to "E" and you save another 9.
TheSoftwareJedi
I also removed temporary variables, reduced to 239 characters.
Lasse V. Karlsen
And down to 158 with replace instead of string.join
Lasse V. Karlsen
+1  A: 

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

First attempt: 198 char of code, I'm sure it can get smaller :D

Andrea Ambu
+2  A: 

Ruby

This code golf is not very well specified -- I assumed that function returning n-th iteration string is best way to solve it. It has 80 characters.

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

Code printing out n first strings (71 characters):

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

Erlang

241 bytes and ready to run:

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

Could probably be improved.

Jonas
+2  A: 

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)

Output

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
J.F. Sebastian
http://codepad.org/4pNffpGK131 bytes.
Nick Presta
A: 

REBOL, 150 characters. Unfortunately REBOL is not a language conducive to code golf, but 150 characters ain't too shabby, as Adam Sandler says.

This assumes the loop variable m has already been defined.

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

And here it is with better layout:

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]
]
Gregory Higley
A: 

F#: 184 chars

Seems to map pretty cleanly to 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)

Here's a run in 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]
Juliet