Étant donné une configuration de dominos, votre tâche consiste à déterminer quels dominos tombent et lesquels ne le font pas.

Contribution

Prenez une représentation ASCII rectangulaire d'une configuration domino. Les caractères suivants sont utilisés pour la grille ASCII:

• (espace): cellule vide
• |, -, /, \: Dominos

Les dominos peuvent tomber dans 8 directions, qui sont représentées par les lettres suivantes (similaires aux orientations WASD):

Q W E
A   D
Z X C

Un ou plusieurs dominos seront remplacés par l'une de ces lettres pour indiquer que le domino est poussé au début. Voici un exemple:

D||||/  
  -   / 
  -    -
  -    -
  /|||||

Je ne veux pas que ce défi se transforme en un exercice d'analyse syntaxique, donc l'un des formulaires de saisie suivants est autorisé:

• Une chaîne avec la grille (éventuellement précédée de ses dimensions si cela vous aide)
• Un tableau / liste / tuple avec une chaîne pour chaque ligne (éventuellement avec des entiers de largeur et de hauteur)
• Un tableau / liste / tuple (imbriqué) avec une chaîne / caractère pour chaque cellule de la grille (éventuellement avec des variables de largeur et de hauteur)

Vous pouvez lire à partir de STDIN ou prendre un argument de fonction ou même vous attendre à ce que l'entrée soit stockée dans une variable.

Production

Écrivez dans STDOUT ou renvoyez (ou enregistrez dans une variable) la grille résultante dans l'un des formats d'entrée valides, indiquant quels dominos sont tombés et lesquels ne l'ont pas été. Autrement dit, remplacez chaque domino tombé par #et laissez chaque domino debout tel qu'il était dans l'entrée.

Règles

Bien sûr, les dominos propagent leur chute à travers l'installation. Comme il peut y avoir des conditions de concurrence, nous supposons qu'il y a des pas de temps fixes et que la chute propage une cellule de grille par pas de temps.

Les dominos tombent généralement comme vous vous y attendez intuitivement, mais une spécification rigoureuse de bon sens s'avère assez longue. Désolé pour cela, j'espère que les exemples vous aideront. Voici un résumé avec toutes les combinaisons uniques de deux carreaux (jusqu'à la rotation et la réflexion). Lisez la suite pour les règles rigoureuses.

Chaque domino ne peut tomber que dans deux directions:

           W       Q          E
A | D      -        /        \
           X         C      Z

Chaque fois qu'un domino tombe, il affecte la cellule dans le sens de la chute. Si cette cellule contient un domino qui peut tomber dans la même direction ou dans une direction qui diffère de 45 degrés, ce domino le fait au pas de temps suivant.

Exemples:

D|    ->    DD      (falls in same direction)

D/    ->    DC      (falls at 45 degrees)

C     ->    C       (falls at 45 degrees)
 -           X

Chaque fois qu'un domino orienté en diagonale ( /ou\ ) tombe, il affecte également les deux cellules qui touchent à la fois sa cellule et la cellule dans le sens de sa chute. Si ces cellules contiennent un domino qui peut tomber dans la même direction que le domino d'origine, ou dans le sens de l'axe qui s'éloigne de lui, ce domino le fait au pas de temps suivant.

Exemples:

C/     ->   CC      (the cell in the direction of the fall is the one below
                     the /, so it falls in the same direction)

C|     ->   CD      (falls in the axis-aligned direction away from the C)

C-     ->   C-       (the direction away from the Q is W, 
  or                  but neither - nor \ can fall to W)
C\     ->   C\     

Exception : si un domino est poussé dans les deux directions valides à la fois (c'est-à-dire si l'une des règles ci-dessus est en conflit), il ne tombe pas.

Exemples:

D|A   ->    D|A     (central domino in pushed in both directions)

  Z           Z     (although it's pushed in one direction by two dominoes
D\A   ->    D\A      and in the other by only one, it doesn't fall)


 X           X      (the domino is being pushed from two opposing sides
D-A   ->    DXA      D and A, but neither is valid for that domino. Hence,
                     there is no conflict and the X can push the domino over)

 Z           Z      (pushed in the same direction by two dominoes, so falls)
\A    ->    ZA

   Z           Z           Z    (once the conflict arises, the affected
  \   ->      Z   ->      Z      domino is locked in its position and can't
D|A         D|A         D|A      be pushed over by future dominoes)

Exemples

8 5
D||||/            ######  
  -   /             -   # 
  -    -    -->     -    #
  -    -            -    #
  /|||||            /|||||

===============================================

17 9
E|/|||/                    #######          
  -   -                      #   #          
  -   -                      #   #          
  -   -                      #   #          
  /|||/|||||||||/    -->     ###############
       /        -                 #        #
        /       -                  #       -
         /      -                   #      #
          /|||||\                    #######

===============================================

19 8
       \|/                        ###           
       - -                        # #           
D||||/|\ /|||/             ######## #####       
      /      -                   #      #       
       -    \-       -->          -    \#       
      \-   \ -                   #-   \ #       
D||||\ /  \  /             ###### /  \  #       
        |\    |||||                |\    #####  

==============================================

11 11
-\\\/|\|\-|         -\##/|###-|
-|\\||\-|\-         -|#####-|\-
|\//\//|-/-         |#//\//|#/-
\|//|-|\-\|         #####-|##\|
---||/-\//|         #-######//|
///|||\----   -->   #/#####----
-|/---|-|-\         #|##--|-|-\
--|--\/|///         ####-\/|///
/|//--|//-|         ####--|//-|
|/\-|||-/-\         |/\####-/-\
E||\-|\---/         ####-|\---/

Faites-moi savoir si vous pensez que j'ai fait une erreur (surtout avec la dernière).

C # 1048 907 850 octets

Maintenant fortement golfé, à peu près juste un fouillis d'opérations binaires sur un tableau bidimensionnel d'énumérations entières. Pourrait probablement être raccourci un peu en utilisant un tableau unidimensionnel, mais je ne suis pas prêt à essayer de retravailler cela à ce stade. Lit les dimensions et la chaîne depuis stdin, par exemple:

11 11 -\\\/|\|\-|-|\\||\-|\-|\//\//|-/-\|//|-|\-\|---||/-\//|///|||\-----|/---|-|-\--|--\/|////|//--|//-||/\-|||-/-\E||\-|\---/

Golfé:

using L=System.Console;class R{static void Main(){int p=255,e,c,E=7,D,C,X,Z,A,m=-1,t=m,f=t,u,i=t;for(;t<0;)for(t=f,f=0;(C=L.Read())>47;)f=f*10+C-48;var T=new int[f,t];for(;++i<f;)for(c=0;c<t;T[i,c++]=(C>99?68:C>91?34:C>89?112:C>87?56:C>86?131:C>80?193:C>68?7:C>67?14:C>66?28:C>64?224:C>46?136:C>44?17:0)*(C>64&C<91?1:257))C=L.Read();for(;i+E>0;E=-E)for(i=c=m;++c<f;)for(C=m;++C<t;){if(E>0&(A=D=T[c,C])>0&D<p){T[c,C]=m; X=C+(i=(D&4)>0?1:(D&64)/-64);Z=c+(u=(D&16)>0?1:D%2*m);System.Action v=()=>{if(Z>m&Z<f&X>m&X<t&&(e=T[Z,X])>p&(e>>8&A)>0)T[Z,X]&=65280|A;};v();if((i&u)!=0){X=i==u?C:X;Z=i==u?Z:c;A=((D&128)/128+D*2)&D;v();X=C+i-X+C;Z=c+u-Z+c;A=(D%2*128+D/2)&D;v();}i=8;}if(E<0&D>p&((D=D&p)&(D-1))<1&D>0)T[c,C]=D<2?131:D>64?193:D/2*7;}for(D=m;++D<f;L.WriteLine())for(c=0;c<t;L.Write(C<0?'#':(C=C>>8)>99?'/':C>67?'|':C>33?'\\':C>9?'-':' '))C=T[D,c++];}}

Parce que j'ai trop de temps, j'ai modifié la version non golfée pour produire un gif animé des dominos tombant (avec l'aide de cette question SO et de ces documents 1 2 ). Cela n'a ajouté que du code, et il est soit dans un #if gifnessbloc, soit clairement marqué.

Pour créer les gifs, vous fournissez une paire d'arguments de ligne de commande décrivant les temps de trame, le fichier de sortie, etc.,

dominoGolf.exe console_delay (out_file_name (gif_frame_time (final_frame_time)))
dominoGolf.exe 0 outfile.gif 1 100

Le troisième argument est le temps de trame pour chaque trame (1 / 100s de secondes). Le quatrième argument est le temps de trame pour la dernière trame (1 / 100s de secondes). Le deuxième argument est le nom du fichier de sortie pour le gif. Vous pouvez omettre le nom de fichier, le délai et le délai final si vous voulez simplement la sortie de la console. Le premier argument est un délai entre les trames rendues au terminal en millisecondes. Vous pouvez omettre tous les arguments si vous ne voulez pas du tout d'animation et voulez simplement voir le résultat. Il lit les données domino de stdin tout comme la version golfée. Ce code est horrible à sa manière (boucher le gif pour qu'il boucle).

Code générateur de gif non golfé:

#define gifness

using L=System.Console;

class R
{
    static void Main(string[] args) // don't need args
    {
        int p=255,P=0xFF00,m=15,M=240, // might be able to inline a couple of these
        w=1,e=2,d=4,c=8,x=16,z=32,a=64,q=128, // most of these are reusable
        W=131,E=7,D=14,C=28,X=56,Z=X*2,A=Z*2,Q=193, // most (all?) of these are reusable
        Y=w+x,U=a+d,N=c+q,B=z+e, // one of these atleast is pre-evalable

        // recognise this?
        t=-1,f=t,k,u,i=t,j,J,K,o,O,b;
        for(;t<0;)
            for(t=f,f=0;(k=L.Read())>47;)
                f=f*10+k-48;

        var T=new int[f,t]; // main arr
        // domino: dir, copy(for render)
        // motion: pickup

        // input
        for(;++i<f;) // values of i and j don't matter, just counters
        {
            for(j=0;j<t;) // increment done 3down
            {
                k=L.Read();
                T[i,j++]=(
                // fallen
                k=='W'?W:k=='E'?E:k=='D'?D:k=='C'?C:k=='X'?X:k=='Z'?Z:k=='A'?A:k=='Q'?Q:
                // dominos
                k==' '?0:k=='-'?Y:k=='/'?N:k=='|'?U:B // ASCII, order for >
                )*(k>64&k<91?1:257);
            }
        }

        #if gifness
        System.Drawing.Font font1 = null;
        System.Windows.Media.Imaging.GifBitmapEncoder genc = null;
        System.Drawing.Bitmap bmp = null;
        System.Drawing.Graphics g = null;
        if (args.Length > 1)
        {
            font1 = new System.Drawing.Font(System.Drawing.FontFamily.GenericMonospace, 12, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Pixel);
            genc = new System.Windows.Media.Imaging.GifBitmapEncoder();
            bmp = new System.Drawing.Bitmap(t * 8, f * 14); // I have no clue what these should be in relation to em size
            g = System.Drawing.Graphics.FromImage(bmp);
        }
        #endif

        if (args.Length > 0) // not important
        {
            L.Clear();
        }

        // main
        for(;i>0;) // can do i=1-i and swap setting 1 for 0 to remove {}
        {

            if (args.Length > 0) // non-critical, renders the current state to the console/gif
            {
                var os="";
                for (o=0;o<f;o++) // values of i and j don't matter, just counters
                {
                    for (j=0;j<t;j++)
                    {
                        k=T[o,j];
                        os += k==0?' ':k<p?'#':(k=k>>8)==Y?'-':k==N?'/':k==U?'|':'\\'; // order for >
                    }
                    os+="\n";
                }
                L.SetCursorPosition(0, 0);
                L.Write(os);

                #if gifness
                if (args.Length > 1)
                {
                    g.Clear(System.Drawing.Color.White);
                    g.DrawString(os, font1, System.Drawing.Brushes.Black, 0, 0);
                    System.IO.MemoryStream bms = new System.IO.MemoryStream();
                    bmp.Save(bms, System.Drawing.Imaging.ImageFormat.Gif);
                    var bmpf = System.Windows.Media.Imaging.BitmapFrame.Create(bms);
                    genc.Frames.Add(bmpf);

                    // do I chose the frame duraton1??!?!?! (take from args[2] is present else args[0])
                }
                #endif

                System.Threading.Thread.Sleep(int.Parse(args[0]));
            }

            // back to important stuff
            i=0; // set me to 1 if we do anything (8 in golfed version due to E being 7)

            // move motions
            for (j=0;j<f;j++) // careful!!
            {
                for (k=0;k<t;k++) // careful!!
                {
                    O=o=T[j,k];
                    if (o>0&o<p) // we are motion
                    {
                        T[j,k]=-1; // do this so we can't skip it

                        K=k+(i=((o&d)>1?1:(o&a)>0?-1:0));
                        J=j+(u=((o&x)>1?1:(o&w)>0?-1:0));

                        System.Action v=()=>{
                            if(J>=0&J<f&K>=0&K<t&&(b=T[J,K])>p&&((b>>8)&O)>0)
                            {
                                T[J,K]&=(P|O);
                            }
                        };

                        v();
                        if (i!=0&u!=0)
                        {
                            K=i==u?k:K; // k+i == K
                            J=i==u?J:j; // j+u == J
                            O=(((o&q)>0?w:0)+o*2)&o;
                            v();

                            K=K==k?k+i:k;
                            J=J==j?j+u:j;
                            O=(((o&w)>0?q:0)+o/2)&o;
                            v();
                        }

                        i=1;
                    }
                }
            }

            // move dominos
            for (j=0;j<f;j++) // careful!!
            {
                for (k=0;k<t;k++) // careful!!
                {
                    o=T[j,k];
                    if (o>p) // we are domino
                    {
                        o=o&p;
                        if ((o&m)<1!=(o&M)<1)
                        { // we have motion
                            T[j,k]=o==w?W:o==q?Q:o+o/2+o*2;
                        }
                    }
                }
            }
        }

        if (args.Length > 0)
        {
            L.SetCursorPosition(0, 0);
        }

        // output
        for (o=0;o<f;o++)
        {
            for (j=0;j<t;j++)
            {
                k=T[o,j];
                L.Write(k<0?'#':(k=k>>8)==0?' ':k==Y?'-':k==N?'/':k==U?'|':'\\'); // order for >
            }
            L.WriteLine();
        }


        #if gifness
        if (args.Length > 1)
        {
            g.Dispose();
            bmp.Dispose();

            System.IO.MemoryStream ms = new System.IO.MemoryStream();

            genc.Save(ms);
            byte[] data = ms.GetBuffer();
            byte[] netscape = { 0x21, 0xFF, 0x0B, 0x4E, 0x45, 0x54, 0x53, 0x43, 0x41, 0x50, 0x45, 0x32, 0x2E, 0x30, 0x03, 0x01, 0x00, 0x00, 0x00 };

            if (args.Length > 2)
            {
                int last = -1;
                int duration = int.Parse(args[2]);

                // promise yourself now you will never use this in production code
                // I've not read enough of the GIF spec to know if this is a bad idea or not
                for (i = 0; i < ms.Length - 5; i++)
                {
                    if (data[i] == 0x21 && data[i+1] == 0xF9 && data[i+2] == 0x04 && data[i+3] == 01)
                    {
                        data[i+4] = (byte)(duration & p); // something endian (least significant first)
                        data[i+5] = (byte)((duration & P) >> 8);
                        last = i+4;
                    }
                }

                if (last != -1 && args.Length > 3)
                {
                    duration = int.Parse(args[3]);
                    data[last] = (byte)(duration & p);
                    data[last+1] = (byte)((duration & P) >> 8);
                }
            }

            using (System.IO.FileStream fs = new System.IO.FileStream(args[1], System.IO.FileMode.Create))
            {
                fs.Write(data, 0, 13);

                // behold
                fs.Write(netscape, 0, netscape.Length);

                fs.Write(data, 13, (int)ms.Length - 13); // lets hope these arn't in excess of 2GBs
            }
        }
        #endif
    }
}

Un exemple de gif pour le troisième exemple d'entrée (et celui illustré ci-dessus)

Exemple de disposition domino 100x25 générée aléatoirement

"Domino" dans dominos

Python 1188

Fondamentalement, il suffit de faire correspondre continuellement des regex lourds jusqu'à ce qu'il cesse de changer. Il correspond en fait à toutes les poussées de chaque direction séparément (via l'expression régulière), puis compose les différents résultats en s'assurant qu'il n'y a pas de conflits et autres.

Le regex peut probablement être fait de manière beaucoup plus compacte, mais pour l'instant voici ce que j'ai (il suppose que la grille est stockée dans une chaîne g, et les dimensions sont dans xet y):

import re;L='QWEADZXC';a='';m=(x*y+y);o=[0]*m;X='(.{%s})';t=X%x;u=X%(x+1);v=X%(x-1);R=range
def S(s,l):
 f=s
 for p,r in l:
    n=re.sub(p,r,s,flags=re.DOTALL)
    for i in R(len(n)):
     if n[i]!=s[i]:f=f[:i]+n[i]+f[i+1:]
 return f
while g != a:
 a=g;n='';d=[S(g,[(r'D\|','DD'),(r'D\\','DE'),('D/','DC')]),S(g,[(r'\|A','AA'),(r'\\A','ZA'),('/A','QA')]),S(g,[('-%sW'%t,r'W\1W'),(r'\\%sW'%t,r'E\1W'),('/%sW'%t,r'Q\1W')]),S(g,[('X%s-'%t,r'X\1X'),(r'X%s\\'%t,r'X\1Z'),(r'X%s/'%t,r'X\1C')]),S(g,[('C%s/'%u,r'C\1C'),('C%s-'%u,r'C\1X'),(r'C%s\|'%u,r'C\1D'),('C%s/'%t,r'C\1C'),('C%s-'%t,r'C\1X'),('C/','CC'),(r'C\|','CD')]),S(g,[(r'Z%s\\'%v,r'Z\1Z'),('Z%s-'%v,r'Z\1X'),(r'Z%s\|'%v,r'Z\1A'),(r'Z%s\\'%t,r'Z\1Z'),('Z%s-'%t,r'Z\1X'),(r'\\Z','ZZ'),(r'\|Z','AZ')]),S(g,[('/%sQ'%u,r'Q\1Q'),('-%sQ'%u,r'W\1Q'),(r'\|%sQ'%u,r'A\1Q'),('/%sQ'%t,r'Q\1Q'),('-%sQ'%t,r'W\1Q'),('/Q','QQ'),(r'\|Q','AQ')]),S(g,[(r'\\%sE'%v,r'E\1E'),('-%sE'%v,r'W\1E'),(r'\|%sE'%v,r'D\1E'),(r'\\%sE'%t,r'E\1E'),('-%sE'%t,r'W\1E'),(r'E\\','EE'),(r'E\|','ED')])]
 for i in range(m):
    c=0
    for r in d:
     if r[i]in L:
        if c==0:c=r[i]
        elif r[i]!=c:o[i]=1;break
    n+=g[i]if c==0 or o[i]else c
 g=n
print re.sub(r'\w','#',g)

Plus non golfé:

import re

L = 'QWEADZXC'

def sub_all(string,lst):
    final = string
    for p,r in lst:
        new = re.sub(p,r,string,flags=re.DOTALL)
        for i in range(len(new)):
            if new[i]!=string[i]:
                final=final[:i]+new[i]+final[i+1:]
    return final

def dominoes(grid,x,y):
    print len(grid),x*y+y
    print grid

    last = ''
    locked = [0]*(x*y+y)
    while grid != last:
        last = grid

        Dgrid = sub_all(grid,[(r'D\|','DD'),(r'D\\','DE'),('D/','DC')])
        Agrid = sub_all(grid,[(r'\|A','AA'),(r'\\A','ZA'),('/A','QA')])
        Wgrid = sub_all(grid,[('-(.{%s})W'%x,r'W\1W'),(r'\\(.{%s})W'%x,r'E\1W'),('/(.{%s})W'%x,r'Q\1W')])
        Xgrid = sub_all(grid,[('X(.{%s})-'%x,r'X\1X'),(r'X(.{%s})\\'%x,r'X\1Z'),(r'X(.{%s})/'%x,r'X\1C')])

        Cgrid = sub_all(grid,[('C(.{%s})/'%(x+1),r'C\1C'),('C(.{%s})-'%(x+1),r'C\1X'),(r'C(.{%s})\|'%(x+1),r'C\1D'),
                        ('C(.{%s})/'%x,r'C\1C'),('C(.{%s})-'%x,r'C\1X'),
                        ('C/','CC'),(r'C\|','CD')])

        Zgrid = sub_all(grid,[(r'Z(.{%s})\\'%(x-1),r'Z\1Z'),('Z(.{%s})-'%(x-1),r'Z\1X'),(r'Z(.{%s})\|'%(x-1),r'Z\1A'),
                        (r'Z(.{%s})\\'%x,r'Z\1Z'),('Z(.{%s})-'%x,r'Z\1X'),
                        (r'\\Z','ZZ'),(r'\|Z','AZ')])

        Qgrid = sub_all(grid,[('/(.{%s})Q'%(x+1),r'Q\1Q'),('-(.{%s})Q'%(x+1),r'W\1Q'),(r'\|(.{%s})Q'%(x+1),r'A\1Q'),
                        ('/(.{%s})Q'%x,r'Q\1Q'),('-(.{%s})Q'%x,r'W\1Q'),
                        ('/Q','QQ'),(r'\|Q','AQ')])

        Egrid = sub_all(grid,[(r'\\(.{%s})E'%(x-1),r'E\1E'),('-(.{%s})E'%(x-1),r'W\1E'),(r'\|(.{%s})E'%(x-1),r'D\1E'),
                        (r'\\(.{%s})E'%x,r'E\1E'),('-(.{%s})E'%x,r'W\1E'),
                        (r'E\\','EE'),(r'E\|','ED')])

        grids = [Dgrid,Agrid,Wgrid,Xgrid,Cgrid,Zgrid,Qgrid,Egrid]
        ngrid = ''

        for i in range(x*y+y):
            c = None
            for g in grids:
                if g[i] in L:
                    if c==None: c = g[i]
                    elif g[i] != c:
                        ngrid += grid[i]
                        locked[i]=1
                        break
            else:
                ngrid += grid[i] if c==None or locked[i] else c
        grid = ngrid
        print grid
    return re.sub(r'\w','#',grid)

Les entrées listées produisent toutes leurs sorties sauf la troisième, dans laquelle je suis presque sûr qu'il y a une erreur ( \-/tout en haut devrait être \|/si la sortie donnée est souhaitée). Je suppose également que le .coin inférieur gauche du dernier était destiné à être un D.