4
\$\begingroup\$

AKA: the most complex way to return a string I could think of.

Requirements:

*Edit: * @Griffin, You are correct, the goal is to use crossover/mutation of characters in a string to eventually come up with the same as input, although, "Hello World" was simply an example. Really, I just like to see what the others on the site can come up with.

Golf. Try to keep it short. Have fun, dag nabbit!

Preferences (not required): -Using a fixed seed on a random number generator would help others reproduce your results. -Bonus if you test for 'properties' of the string, such as the number of L's in "Hello World", instead of only correct characters (like mine).

Shortest code, or highest voted, wins. One exception: if you manage to create a working version in BrainF***, you win.

My take using Java:

import static java.lang.Math.*;import java.util.Arrays;import static java.lang.System.out;import java.util.Random;class G{static char[]c;static Random r;public static void main(String[]a){c=a[0].toCharArray();r=new Random(6);P w=new P(9);int n=0;while(!w.f){w.s();if(w.f)out.println(w.g[w.p].x()+"@gen "+n);n++;}}static class P{boolean f=false;int p=0;M[]g=null;P(int s){if(s>=9)g=new M[s];else g=new M[9];for(int i=0;i<g.length;i++)g[i]=new M(c.length);}void s(){f();if(!f){h();j();}}void f(){for(int i=0;i<g.length;i++){g[i].f(c);if(g[i].l==0){f=true;p=i;}}}void h(){Arrays.sort(g);}void j(){M[]b=new M[g.length];for(int i=0;i<g.length-1;i++){float k=r.nextInt(100);if(k<40)b[i]=new M(g[0],g[1]);else if((k<60)&&(k>40))b[i]=new M(g[0],g[2]);else if((k<80)&&(k>60))b[i]=new M(g[1],g[2]);else if((k<90)&&(k>80))b[i]=new M(g[2],g[3]);else if((k<95)&&(k>90))b[i]=new M(g[2],g[4]);else if((k<99)&&(k>95))b[i]=new M(g[0],g[r.nextInt(g.length)]);else b[i]=new M(g[0],new M(c.length));b[g.length-1]=g[0];}g=b;}}static class M implements Comparable {char[]a=null;int l=0;int q=0;int u=8;int o=20;public int compareTo(Object o){M t=(M)o;if(this.l<t.l)return-1;else if(this.l>t.l)return 1;return 0;}M(int s){a=new char[s];for(int i=0;i<a.length;i++)a[i]=(char)r.nextInt(255);}M(M m,M p){a=new char[m.a.length];for(int i=0;i<m.a.length;i++){a[i]=(r.nextInt(100)>2)?m.a[i]:p.a[i];int z=r.nextInt(100);if(z<u)a[i]=(char)r.nextInt(255);else if(z<o){int b=r.nextInt(6);a[i]=(char)(a[i]^(1<<b));}}}void f(char[]v){l=0;for(int i=0;i<a.length;i++){int d=abs(a[i]-v[i]);l+=d;}}String x(){return new String(a);}}}

Example output from my code:

Hello World!@gen 3352
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Could you clarify the challenge a bit please? I'm assuming we are to create a genetic algorithm which starts off with a random string and produces the string Hello World! through iterative random mutation/recombination of the start string. Is this correct? \$\endgroup\$
    – Griffin
    Jul 30, 2012 at 12:23

4 Answers 4

2
\$\begingroup\$

APL (98)

L←⍴T←⎕UCS'Hello World!'⋄F←{+/2*⍨⍵-T}⋄0{0=F ⍵:⍺,⎕UCS⍵⋄(⍺+1)∇{(F⍵)≤F⊢C←⍵+(2-?3)×(⍳L)=?⍴⍵:⍵⋄C}⍵}L?255

Can be shortened, at the expense of easy configurability and of result, I'll do so when this one is beaten.

Output:

5940 Hello World!

(or another number between ~4000-~9000).

Credit for the algorithm: http://www.electricmonk.nl/log/2011/09/28/evolutionary-algorithm-evolving-hello-world/

Explanation:

  • L←⍴T←⎕UCS'Hello World!': The target is the ASCII values (⎕UCS) of 'Hello World'. (You can change the string.) L is its length.
  • F←{+/2*⍨⍵-T}: F measures the 'distance' between a candidate and a target. This is the sum of the squares of the difference between each character.
  • 0{0=F ⍵:⍺,⎕UCS⍵⋄(⍺+1)∇...⍵}L?255: Starting with a random string (L?255), if the distance between the target and the candidate is 0 (i.e. we have it) (0=F ⍵:), then output the generation and the string (⍺,⎕UCS⍵). Otherwise, mutate the candidate and proceed to the next generation.
  • (F⍵)≤F⊢C←⍵+(2-?3)×(⍳L)=?⍴⍵:⍵⋄C: Generate a new candidate by selecting a random position and mutating it by one. If the distance to the target is less than the old candidate, return the new candidate, otherwise keep the old candidate.
\$\endgroup\$
2
\$\begingroup\$

pdfTeX, 2663

\RequirePackage{xparse}
\ExplSyntaxOn
\tl_new:N \l_my_base_tl
\int_new:N \l_my_len_int
\prop_new:N \l_my_base_prop
\prop_new:N \l_my_trial_a_prop
\prop_new:N \l_my_trial_b_prop
\int_new:N \l_my_diff_a_int
\int_new:N \l_my_diff_b_int
\cs_generate_variant:Nn \tl_replace_all:Nnn { Nno }
\DeclareDocumentCommand{\do}{v}
  {
    \tl_set:Nx \l_my_base_tl { \tl_to_str:n {#1} }
    \tl_replace_all:Nno \l_my_base_tl { ~ } { \c_catcode_other_space_tl }
    \int_zero:N \l_my_len_int
    \tl_map_inline:Nn \l_my_base_tl
      {
        \int_incr:N \l_my_len_int
        \prop_put:NVn \l_my_base_prop \l_my_len_int {##1}
      }
    \my_get_diff:NN \l_my_base_prop \l_tmpa_int
    \int_step_inline:nnnn { 1 } { 1 } { \l_my_len_int }
      { \prop_put:Nnn \l_my_trial_a_prop {##1} { O } }
    \my_term:
    \my_get_diff:NN \l_my_trial_a_prop \l_my_diff_a_int
    \bool_set_false:N \l_tmpa_bool
    \bool_until_do:Nn \l_tmpa_bool
      {
        \prop_set_eq:NN \l_my_trial_b_prop \l_my_trial_a_prop
        \prop_map_inline:Nn \l_my_trial_b_prop
          {
            \prop_get:NnN \l_my_trial_b_prop {##1} \l_tmpa_tl
            \prop_get:NnN \l_my_base_prop {##1} \l_tmpb_tl
            \exp_args:Noo \token_if_eq_charcode:NNF \l_tmpa_tl \l_tmpb_tl
              {
                \int_set:Nn \l_tmpa_int
                  { \exp_after:wN `\l_tmpa_tl + \pdfuniformdeviate 7 - 3 }
                \char_set_lccode:nn { `* }
                  { \int_max:nn { 32 } { \int_min:nn { 127 } { \l_tmpa_int } } }
                \tl_to_lowercase:n
                  { \prop_put:Nnn \l_my_trial_b_prop {##1} { * } }
              }
          }
        \my_get_diff:NN \l_my_trial_b_prop \l_my_diff_b_int
        \int_compare:nT { \l_my_diff_b_int < \l_my_diff_a_int }
          {
            \prop_set_eq:NN \l_my_trial_a_prop \l_my_trial_b_prop
            \int_set_eq:NN \l_my_diff_a_int \l_my_diff_b_int
            \int_compare:nT { \l_my_diff_b_int = 0 }
              { \bool_set_true:N \l_tmpa_bool }
            \my_term:
          }
      }
    \tex_end:D
  }
\cs_new_protected:Npn \my_get_diff:NN #1#2
  {
    \int_zero:N #2
    \prop_map_inline:Nn #1
      {
        \prop_get:NnN \l_my_base_prop {##1} \l_tmpa_tl
        \int_add:Nn #2
          {
            ( \my_char_value:o \l_tmpa_tl - \my_char_value:n {##2} )
            * ( \my_char_value:o \l_tmpa_tl - \my_char_value:n {##2} )
          }
      }
  }
\cs_new:Npn \my_char_value:n #1 { \int_eval:n { `#1 } }
\cs_generate_variant:Nn \my_char_value:n { o }
\cs_new_protected_nopar:Npn \my_term:
  { \iow_term:x { \prop_map_function:NN \l_my_trial_a_prop \use_ii:nn } }
\ExplSyntaxOff
\expandafter\do\noexpand

Call as

pdflatex Experiment573.tex +Hello, World+

where the + delimiters are arbitrary (identical). I chose + here because many more conventional delimiters have a meaning on the command line. This could be shortened quite a bit: I initially thought I'd need floating point computations, which are not available without the expl3 programming language, so I loaded and used that, which is quite verbose.

\$\endgroup\$
1
\$\begingroup\$

Python, 289 286

from random import randint as r
s=map(ord,raw_input()[:-1])
L=len(s)
d=lambda x:sum((a-b)**2 for a,b in zip(x,s))
p=map(list,[(64,)*L]*500)
n=0
while 1:
 n+=1
 for b in p:b[r(0,L-1)]+=r(-5,5)
 if any(i==s for i in p):break
 p=sorted(p,key=d)[:100]
 p+=[i[:]for i in p][:500-100]
print n

Starting population is a list of strings: "@" * length_of_input. Uses the squared sum of the distance for each character and corresponding target character as the fitness function.

\$\endgroup\$
0
\$\begingroup\$

C# - 432

using System;using System.Linq;class M{static void Main(string[] a){var g=a[0];int l=g.Length,P=182,S=P/2,k=0,I=0;var r=new Random();Func<int,string>z=null;z=A=>A==0?"":(char)(r.Next(S)+32)+z(A-1);var p=new string[P];while(k<P)p[k++]=z(l);while(p[k=0]!=g){p=p.OrderBy(s=>s.Select((t,i)=>t==g[i]?0:1).Sum()).ToArray();I++;while(k<S){var Q=p[k].ToCharArray();Q[r.Next(l)]=z(1)[0];p[S+k++]=new string(Q);}}Console.WriteLine(I+" "+g);}}

Example output: 171 Hello there :)

Better formatted (character count is higher...)

using System;
using System.Linq;
class M
{
    static void Main (string[] a)
    {
        var g = a [0];
        int l = g.Length, P = 182, S = P / 2, k = 0, I = 0;    
        var r = new Random ();
        Func<int,string> z = null;
        z = A => A == 0 ? "" : (char)(r.Next (S) + 32) + z (A - 1);
        var p = new string[P];
        while (k<P)
            p [k++] = z (l);
        while (p[k=0]!=g) {
            p = p.OrderBy (s => s.Select ((t,i) => t == g [i] ? 0 : 1).Sum ()). ToArray ();
            I++;
            while (k<S) {
                var Q = p [k].ToCharArray ();
                Q [r.Next (l)] = z (1) [0];
                p [S + k++] = new string (Q);
            }
        }
        Console.WriteLine (I + " " + g);
    }
} 

Initialization

An array of 198 random candidates is created (by use of the recursive random string generation function z)

Main Loop

The array is (re)sorted by the number of mismatches within the string (this used less characters than power or absolute value). The bottom half of the population is replaced with mutations (by one char) on the first half (the fitter part of the population).

Termination

Once the fittest member is equal to the goal, the number of iterations is printed along with the output string.

This is my first golf submission and likely the last one done with C#. I may also try to regolf this in a terser language later.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.