Evolution of the 'x'

Question

Given is a board of variable size with a maximum size of 5 times 5 fields. Every field kann be filled with an 'x'. If it is not filled with an 'x', it is filled with an 'o'.

The starting state of every board is given (see below). With each board, 10 rounds have to be played (at max, conditions: see below) and the evolution of the x must be watched.

One round works the following way:

1. every 'x' spreads to orthogonally bordering fields, but dissapears itself
2. each time two 'x' are on one field, they neutralize each other

The evolution of all 'x' in each round has to happen simultaneously. Example:

    o o o            o x o
    o x o     ->     x o x
    o o o            o x o

With each round of evolution, you have to see if the board gets emptied of 'x'. Is it not empty, a repeating pattern could be present. If this is also not the case, we give up the analysis of the evolution. Additionally you have to print out the maximum percentage of x fields for every starting board (rounded down to whole numbers).

Input:

The input data can be found here (Pastebin) This data contains 100 starting states. As already mentioned, the boards vary in size. The number of rows is stated with number n from 1 to 5, followed by n rows that contain only 'x' and 'o', represent the starting pattern. Every row of a board has 1 to 5 fields.

Output:

The complete result must be printed out, one printed row for each starting board in the following form:

    Round {0-10}: {repetition/empty/giveup}, {0-100} percent maximum-fill

Examples:

Example 1:

    Input: 2       Starting state: x o x
           xox                     x x
           xx

                          Round 1: x x o
                                   o x

                          Round 2: x o x
                                   o x

                          Round 3: o x o
                                   o o

                          Round 4: x o x   -> The pattern repeats:
                                   o x        It is the same as in round 2,
                                              therefore we stop. Maximum fill was
                                              in the starting state with four times 'x'
                                              of 5 fields altogether,
                                              so we have 4/5 = 80 %.

    Output: Round 4: repetition, 80 percent maximum-fill

Example 2:

    Input: 1       Starting state: x x
           xx                      

                          Round 1: x x    ->  We already have a repetition, because
                                              the pattern is the same as in the starting
                                              state. The board is always filled 100 %.

    Output: Round 1: repetition, 100 percent maximum-fill

After eight dayst I will mark the working answer with the fewest characters as the winner. Additionally i will post the correct output for the 100 starting boards (input).

You can use your prefered (programming/scripting/whatever) language.

Have fun!

PS: If you have questions, feel free to ask.

PPS: In respect of the original creators: For people capable of speaking german, the question was taken from DO NOT CLICK IF YOU DO NOT WANT SPOILERS here. Since the official time for completing the challenge has ended, I wanted to see if someone could come up with a short and elegant solution.

22.04.2014:

Challenge Done! Winner marked as accepted. Correct output:

    Round 10: giveup, 50 percent maximum-fill
    Round 5: empty, 66 percent maximum-fill
    Round 1: repetition, 100 percent maximum-fill
    Round 1: empty, 100 percent maximum-fill
    Round 4: repetition, 100 percent maximum-fill
    Round 4: repetition, 70 percent maximum-fill
    Round 2: repetition, 60 percent maximum-fill
    Round 4: empty, 88 percent maximum-fill
    Round 10: giveup, 50 percent maximum-fill
    Round 5: repetition, 80 percent maximum-fill
    Round 10: repetition, 80 percent maximum-fill
    Round 1: empty, 80 percent maximum-fill
    Round 3: repetition, 60 percent maximum-fill
    Round 4: repetition, 48 percent maximum-fill
    Round 9: empty, 41 percent maximum-fill
    Round 10: giveup, 92 percent maximum-fill
    Round 10: giveup, 53 percent maximum-fill
    Round 10: giveup, 66 percent maximum-fill
    Round 6: repetition, 50 percent maximum-fill
    Round 10: giveup, 88 percent maximum-fill
    Round 10: giveup, 76 percent maximum-fill
    Round 10: giveup, 68 percent maximum-fill
    Round 10: giveup, 40 percent maximum-fill
    Round 10: giveup, 100 percent maximum-fill
    Round 10: giveup, 71 percent maximum-fill
    Round 2: empty, 81 percent maximum-fill
    Round 6: repetition, 36 percent maximum-fill
    Round 10: giveup, 61 percent maximum-fill
    Round 10: giveup, 60 percent maximum-fill
    Round 4: repetition, 66 percent maximum-fill
    Round 10: giveup, 72 percent maximum-fill
    Round 3: empty, 80 percent maximum-fill
    Round 10: giveup, 50 percent maximum-fill
    Round 10: giveup, 83 percent maximum-fill
    Round 7: repetition, 37 percent maximum-fill
    Round 9: repetition, 85 percent maximum-fill
    Round 5: repetition, 40 percent maximum-fill
    Round 5: repetition, 60 percent maximum-fill
    Round 4: empty, 80 percent maximum-fill
    Round 10: giveup, 60 percent maximum-fill
    Round 4: repetition, 46 percent maximum-fill
    Round 6: repetition, 42 percent maximum-fill
    Round 10: giveup, 72 percent maximum-fill
    Round 4: repetition, 70 percent maximum-fill
    Round 4: repetition, 80 percent maximum-fill
    Round 6: repetition, 50 percent maximum-fill
    Round 4: repetition, 56 percent maximum-fill
    Round 10: giveup, 60 percent maximum-fill
    Round 10: giveup, 54 percent maximum-fill
    Round 10: giveup, 66 percent maximum-fill
    Round 2: repetition, 40 percent maximum-fill
    Round 2: repetition, 40 percent maximum-fill
    Round 6: repetition, 75 percent maximum-fill
    Round 7: empty, 85 percent maximum-fill
    Round 10: giveup, 50 percent maximum-fill
    Round 6: repetition, 70 percent maximum-fill
    Round 2: empty, 66 percent maximum-fill
    Round 1: empty, 66 percent maximum-fill
    Round 3: empty, 100 percent maximum-fill
    Round 3: empty, 66 percent maximum-fill
    Round 8: repetition, 42 percent maximum-fill
    Round 1: empty, 60 percent maximum-fill
    Round 2: repetition, 100 percent maximum-fill
    Round 2: repetition, 83 percent maximum-fill
    Round 4: repetition, 66 percent maximum-fill
    Round 6: repetition, 75 percent maximum-fill
    Round 4: empty, 66 percent maximum-fill
    Round 10: giveup, 61 percent maximum-fill
    Round 10: giveup, 56 percent maximum-fill
    Round 4: empty, 66 percent maximum-fill
    Round 6: repetition, 33 percent maximum-fill
    Round 3: empty, 57 percent maximum-fill
    Round 3: repetition, 100 percent maximum-fill
    Round 6: repetition, 73 percent maximum-fill
    Round 10: giveup, 50 percent maximum-fill
    Round 6: repetition, 50 percent maximum-fill
    Round 10: giveup, 73 percent maximum-fill
    Round 5: empty, 80 percent maximum-fill
    Round 10: giveup, 61 percent maximum-fill
    Round 3: repetition, 53 percent maximum-fill
    Round 10: giveup, 33 percent maximum-fill
    Round 10: giveup, 80 percent maximum-fill
    Round 10: giveup, 63 percent maximum-fill
    Round 10: giveup, 70 percent maximum-fill
    Round 10: giveup, 84 percent maximum-fill
    Round 7: repetition, 70 percent maximum-fill
    Round 10: repetition, 57 percent maximum-fill
    Round 10: giveup, 55 percent maximum-fill
    Round 6: repetition, 36 percent maximum-fill
    Round 4: repetition, 75 percent maximum-fill
    Round 10: giveup, 72 percent maximum-fill
    Round 10: giveup, 64 percent maximum-fill
    Round 10: giveup, 84 percent maximum-fill
    Round 10: giveup, 58 percent maximum-fill
    Round 10: giveup, 60 percent maximum-fill
    Round 10: giveup, 53 percent maximum-fill
    Round 4: repetition, 40 percent maximum-fill
    Round 4: empty, 40 percent maximum-fill
    Round 10: giveup, 50 percent maximum-fill
    Round 10: giveup, 68 percent maximum-fill

Answer 1

Perl, 308, 304, 305, 293, 264, 262

Edit: A bug crept in after one of recent edits, causing wrong output for empty boards (test suite output was OK). Since Round 0 in given output format can mean only that there can be empty boards in the input (though none is in test suite), the bug had to be fixed. Quick fix meant byte count increase (by 1, actually) - not an option, of course. Therefore, I had to golf it a little bit more.

Run with -p (+1 added to count), reads from STDIN. Requires 5.014 because of r substitution modifier.

(@a,%h,$m)=('',map<>=~y/ox\n/\0!/rd,1..$_);for$n(0..10){$_="Round $n: ".($h{$_="@a"}++?repetition:(($.=100*y/!///y/ //c)<$m?$.:$m=$.)?giveup:empty).", $m percent maximum-fill\n";@a=/g/?map{$_=$a[$i=$_];y//!/cr&(s/.//r.P^P.s/.$//r^$a[$i+1]^$a[$i-1])}0..$#a:last}

i.e.

# '-p' switch wraps code into the 'while(<>){....}continue{print}' loop, 
# which reads a line from STDIN into $_, executes '....' and prints contents 
# of $_. We use it to read board height and print current board's result.

# First line reads board's state into @a array, a line per element, at the same 
# time replacing 'o' with 'x00', 'x' with '!' and chomping trailing newlines. 
# '!' was chosen because it's just like 'x01' except 5th bit (which is not important)
# but saves several characters in source code.

# Note: array is prepended with an empty line, which automatically remains in this 
# state during evolution, but saves us trouble of checking if actual (any non-empty)
# line has neighboring line below.

# %h hash and $m hold seen states and maximum fill percentage for current board,
# they are initialized to undef i.e empty and 0.

(@a,%h,$m)=('',map<>=~y/ox\n/\0!/rd,1..$_);

# /
# Then do required number of evolutions:

for$n(0..10){

# Stringify board state, i.e. concatenate lines with spaces ($") as separators.
# Calculate fill percentage - divide number of '!' by number of non-spaces. 
# Note: using $. magick variable automatically takes care of rounding.
# Construct output string. It's not used if loop gets to next iteration. 
# Check if current state was already seen (at the same time add it to %h) 
# and if fill percentage is 0.

$_="Round $n: "
    .($h{$_="@a"}++?repetition:(($.=100*y/!///y/ //c)<$m?$.:$m=$.)?giveup:empty)
    .", $m percent maximum-fill\n";

# /
# Next is funny: if output string contains 'g' (of 'giveup' word), then evolve 
# further, otherwise break-out of the loop.

    @a=/g/
        ?map{

# Do evolution round. Act of evolution for a given line is none other than 
# XOR-ing 4 strings: itself shifted right, itself shifted left, line above, line 
# below. Result of this operation is truncated to original length using bitwise '&'. 
# Note, when shifting string right or left we prepend (append) not an ascii-0, 
# but 'P' character. It's shorter, and 4th and 6th bits will be annihilated anyway.

            $_=$a[$i=$_];
            y//!/cr
            &(s/.//r.P
            ^P.s/.$//r
            ^$a[$i+1]
            ^$a[$i-1])
        }0..$#a
        :last
}

Answer 2

C# - 1164 chars

This is my first participation in code-golf so please be indulgent ;-)

I know, I am far off the best results - really amazing by the way!

But I thought I'd share my solution in C# anyway.

using System;using System.Collections.Generic;using System.IO;using System.Linq;using System.Net;class Program{static void Main(string[] args){new WebClient().DownloadFile("http://mc.capgemini.de/challenge/in.txt",@"D:\in.txt");var a=File.ReadAllLines(@"D:\in.txt");int l=0;while(l<a.Length){int n=Int32.Parse(a[l]);var b=a.Skip(l+1).Take(n).ToArray();var f=new List<string[]>{b};var d=0;string g=null;while(d<10){var s=f.Last();if(s.All(e=>e.All(c=>c=='o'))){g="empty";break;}var h=new string[n];for(int r=0;r<n;r++){var k="";for(int c=0;c<b[r].Length;c++){int x=0;try{if(s[r][c-1]=='x')x++;}catch{}try{if(s[r][c+1]=='x')x++;}catch{}try{if(s[r-1][c]=='x')x++;}catch{}try{if(s[r+1][c]=='x')x++;}catch{}k+=((x%2)==1)?'x':'o';}h[r]=k;}d++;f.Add(h);var w=false;for(int i=0;i<f.Count-1;i++){var m=f[i];if (!h.Where((t,y)=>t!=m[y]).Any())w=true;}if(w){g="repetition";break;}}if(d==10&&g==null)g="giveup";File.AppendAllLines(@"D:\out.txt",new[]{string.Format("Round {0}: {1}, {2} percent maximum-fill",d,g,f.Select(z=>{int t=0;int x=0;foreach(var c in z.SelectMany(s=>s)){t++;if(c=='x')x++;}return(int)Math.Floor((double)x/t*100);}).Concat(new[]{0}).Max())});l=l+n+1;}}}

Solely the using directives already count 97 characters - so I think it is going to be quite hard to achieve the rest within less than 200 characters.

It is a fairly iterative approach, making use of LINQ in many places. I also included the downloading of the input file and writing of the output file into the code.

Here is one little more readable version:

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Net;

class Program
{
    static void Main(string[] args)
    {
        // Download the file
        new WebClient().DownloadFile("http://mc.capgemini.de/challenge/in.txt", @"D:\in.txt");
        // Read of lines of downloaded file
        var a = File.ReadAllLines(@"D:\in.txt");
        // Line index in input file
        int l = 0;
        while (l < a.Length)
        {
            // Parse number of rows to take
            int n = Int32.Parse(a[l]);

            // Take the n rows
            var b = a.Skip(l + 1).Take(n).ToArray();
            var f = new List<string[]> { b };
            var d = 0;
            string g = null;
            while (d < 10)
            {
                // Last state consists only of o's? -> 
                var s = f.Last();
                if (s.All(e => e.All(c => c == 'o')))
                {
                    g = "empty";
                    break;
                }
                // In h we will build up the new state
                var h = new string[n];
                // Loop through all rows of initial state
                for (int r = 0; r < n; r++)
                {
                    // This is our new row we will build up for the current state
                    var k = "";
                    // Count number of orthogonal adjacent x's
                    // And catch potential OutOfRangeExceptions
                    for (int c = 0; c < b[r].Length; c++)
                    {
                        int x = 0;
                        try { if (s[r][c - 1] == 'x') x++; }
                        catch { }
                        try { if (s[r][c + 1] == 'x') x++; }
                        catch { }
                        try { if (s[r - 1][c] == 'x') x++; }
                        catch { }
                        try { if (s[r + 1][c] == 'x') x++; }
                        catch { }
                        // Is number of adjacent x's odd? -> character will be 'x'
                        // otherwise -> 'o'
                        k += ((x % 2) == 1) ? 'x' : 'o';
                    }
                    // Add the new row to the current state
                    h[r] = k;
                }
                // Increase round count
                d++;
                // Add the new state to our state collection
                f.Add(h);
                // Now check, whether it is a repetition by comparing the last state (h) with all other states
                bool w = false;
                for (int i = 0; i < f.Count - 1; i++)
                {
                    var m = f[i];
                    if (!h.Where((t, y) => t != m[y]).Any())
                        w = true;
                }
                if (w)
                {
                    g = "repetition";
                    break;
                }
            }
            // Check whether we reached maximum AND the last round wasn't a repetition
            if (d == 10 && g == null)
                g = "giveup";
            // Now we append the final output row to our text file
            File.AppendAllLines(@"D:\out.txt",
                new[]
                    {
                        string.Format("Round {0}: {1}, {2} percent maximum-fill",
                        d,
                        g,
                        // Here we select all rates of x's per state
                        // and then grab the maximum of those rates
                        f.Select(z =>
                            {
                                int t=0;
                                int x=0;
                                foreach (char c in z.SelectMany(s => s))
                                {
                                    t++;
                                    if(c=='x')
                                        x++;
                                }
                                return (int) Math.Floor((double) x / t *100);
                            }).Concat(new[] {0}).Max())
                    });
            // finally we shift our index to the next (expected) number n in the input file
            l = l + n + 1;
        }
    }
}

Answer 3

J - 275 char

Oh, all these I/O specifications! Such a shamefully large score for J, in the end. Takes input on STDIN with a trailing newline, and assumes there aren't any carriage returns (\r) in the input. Here's the result of applying it to the sample input file in the question.

stdout;,&LF&.>}:(".@{~&0(('Round ',":@(#->/@t),': ',(empty`repetition`giveup{::~2<.#.@t=.11&=@#,0={:),', ',' percent maximum-fill',~0":>./)@(100*1&=%&(+/"1)_&~:)@,.@(a=:(a@,`[@.(e.~+.10<#@[)(_*_&=)+[:~:/((,-)(,:|.)0 1)|.!.0=&1){:)@,:@('ox'&i.^_:)@{.;$: ::]@}.)}.)];._2[1!:1]3

Ungolfed: (I may add a more thorough and J-newbie-friendly explanation later.)

input   =: ];._2 [ 1!:1]3
convert =: 'ox'&i. ^ _:               NB. 'x'=>1  'o'=>0  else=>infinity
spread  =: ((,-)(,:|.)0 1) |.!.0 =&1  NB. x spreading outwards
cover   =: (_*_&=) + [: ~:/ spread    NB. collecting x`s and removing tiles not on board
iterate =: (iterate@, ` [ @. (e.~ +. 10<#@[) cover) {:
percent =: 100 * 1&= %&(+/"1) _&~:    NB. percentage of x at each step
max     =: 0 ": >./
stat    =: 11&=@# , 0={:              NB. information about the simulation
ending  =: empty`repetition`giveup {::~ 2 <. #.@stat   NB. how simulation ended
round   =: ": @ (# - >/@stat)         NB. round number
format  =: 'Round ', round, ': ', ending, ', ', ' percent maximum-fill',~ max
evolvex =: format @ percent@,. @ iterate@,: @ convert
joinln  =: ,&LF &.>
nlines  =: ". @ {~&0
remain  =: }.
stdout ; joinln }: (nlines (evolvex@{. ; $: ::]@}.) remain) input

The $: part makes the main body recurse over the input (a terribly inconvenient form for J to parse), applying the @ daisy-chain over each section. nlines finds the number of lines for the next board.

The action on each board (evolvex) is neat: iterate (called a in the golf) constructs a list of each iteration of the simulation until we hit either something seen before or too many steps. Then percent@,. calculates the percentage of filled square in each result, and format runs some statistics (stat, called t in the golf) to figure out how the simulation ended, which percentage was the greatest, and so on, before formatting all of that into a string.

Finally, }: takes care of some garbage before ; joinln joins all of the individual board outputs into one newline-separated string.