Golf untuk Hari Domino

14

Diberi pengaturan domino, tugas Anda adalah mencari tahu domino mana yang jatuh dan mana yang tidak.

Memasukkan

Ambil representasi ASCII persegi panjang dari pengaturan domino. Karakter berikut digunakan untuk kisi ASCII:

  • (spasi): sel kosong
  • |, -, /, \: Domino

Domino dapat jatuh ke 8 arah, yang diwakili oleh surat-surat berikut (mirip dengan orientasi WASD):

Q W E
A   D
Z X C

Satu atau lebih kartu domino akan diganti dengan salah satu dari surat-surat ini untuk menunjukkan bahwa kartu domino dimundurkan di awal. Berikut ini sebuah contoh:

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

Saya tidak ingin tantangan ini berubah menjadi latihan penguraian input sehingga salah satu dari formulir input berikut diizinkan:

  • Sebuah string dengan kisi (opsional didahului oleh dimensinya jika itu membantu)
  • Array / daftar / tupel dengan satu string untuk setiap baris (opsional bersama dengan bilangan bulat dan tinggi)
  • Array (daftar) / daftar / tupel dengan satu string / karakter untuk setiap sel grid (opsional bersama dengan variabel lebar dan tinggi)

Anda dapat membaca dari STDIN atau mengambil argumen fungsi atau bahkan mengharapkan input disimpan dalam variabel.

Keluaran

Menulis ke STDOUT atau mengembalikan (atau menyimpan dalam variabel) kotak yang dihasilkan dalam format input yang valid, menunjukkan domino mana yang telah jatuh dan yang belum. Artinya, ganti setiap domino yang jatuh dengan #dan biarkan setiap domino berdiri seperti yang ada di input.

Aturan

Tentu saja, domino menyebarkan kejatuhan mereka melalui pengaturan. Karena mungkin ada kondisi balapan, kami menganggap bahwa ada langkah waktu yang tetap dan jatuhnya merambatkan satu sel kisi per langkah waktu.

Domino umumnya jatuh seperti yang Anda harapkan secara intuitif, tetapi spesifikasi yang ketat dari akal sehat ternyata cukup panjang. Maaf untuk itu, saya harap contohnya membantu. Berikut adalah intisari dengan semua kombinasi dua ubin yang unik (hingga rotasi dan refleksi). Baca terus untuk peraturan yang ketat.

Setiap domino dapat jatuh hanya dalam dua arah:

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

Setiap kali domino jatuh itu mempengaruhi sel ke arah musim gugur. Jika sel itu berisi domino yang bisa jatuh ke arah yang sama atau dalam arah yang berbeda 45 derajat, domino itu melakukannya di langkah waktu berikutnya.

Contoh:

D|    ->    DD      (falls in same direction)

D/    ->    DC      (falls at 45 degrees)

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

Setiap kali domino yang berorientasi diagonal ( /atau \) jatuh, itu juga mempengaruhi dua sel yang menyentuh baik selnya maupun selnya ke arah kejatuhannya. Jika sel-sel ini mengandung domino yang dapat jatuh ke arah yang sama dengan domino asli, atau dalam arah sejajar sumbu menjauh darinya, domino itu melakukannya pada langkah waktu berikutnya.

Contoh:

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\     

Pengecualian : jika domino didorong ke dua arah yang valid sekaligus (yaitu jika ada aturan di atas yang bertentangan), itu tidak jatuh.

Contoh:

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)

Contohnya

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

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

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

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

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

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

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

Beri tahu saya jika Anda pikir saya melakukan kesalahan (terutama yang terakhir).

Martin Ender
sumber

Jawaban:

15

C # 1048 907 850bytes

Sekarang sangat golf, cukup banyak operasi bit pada array dua dimensi dari bilangan bulat bilangan bulat. Mungkin bisa dibuat agak lebih pendek dengan menggunakan array 1 dimensi, tapi saya tidak siap untuk mencoba dan bekerja kembali pada saat ini. Membaca dimensi dan string dari stdin, misalnya:

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

Karena saya mempunyai terlalu banyak waktu, saya telah memodifikasi versi yang tidak diserami untuk menghasilkan animasi gif dari domino yang jatuh (dengan bantuan dari pertanyaan SO ini dan dokumen-dokumen ini 1 2 ). Ini hanya menambahkan kode, dan itu baik di #if gifnessblok atau ditandai dengan jelas.

Untuk membuat gif Anda memberikan sepasang argumen baris perintah yang menjelaskan waktu bingkai, file output, dll,

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

Argumen ketiga adalah waktu bingkai untuk setiap frame (1/100 detik). Argumen keempat adalah waktu bingkai untuk frame terakhir (1/100 detik). Argumen kedua adalah nama file keluaran untuk gif. Anda dapat menghilangkan nama file, penundaan, dan penundaan akhir jika Anda hanya ingin keluaran konsol. Argumen pertama adalah penundaan antara frame yang diberikan ke terminal dalam milidetik. Anda dapat menghilangkan semua argumen jika Anda tidak menginginkan animasi sama sekali dan hanya ingin melihat hasilnya. Bunyinya data domino dari stdin seperti versi golf. Kode ini mengerikan dengan caranya sendiri (membantai gif sehingga loop).

Kode penghasil gif yang tidak digabungkan:

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

Contoh gif untuk input contoh ke-3 (dan yang ditunjukkan di atas)

Contoh ke-3

Contoh tata letak domino 100x25 yang dihasilkan secara acak

Tata letak domino 100x25

"Domino" dalam kartu domino

"Domino" dalam kartu domino

VisualMelon
sumber
3

Python 1188

Pada dasarnya hanya loop melalui terus-menerus mencocokkan beberapa regex yang kuat sampai berhenti berubah. Ini benar-benar cocok dengan semua dorongan dari masing-masing arah secara terpisah (melalui regex), dan kemudian menyusun hasil yang berbeda memastikan tidak ada konflik dan semacamnya.

Regex mungkin dapat dilakukan jauh lebih kompak, tetapi untuk sekarang inilah yang saya miliki (mengasumsikan grid disimpan dalam string g,, dan dimensi berada di dalam xdan 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)

Lebih ungolfed:

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)

Input yang terdaftar semua menghasilkan output mereka kecuali yang ketiga, di mana saya cukup yakin ada kesalahan (yang \-/paling atas seharusnya \|/jika output yang diberikan diinginkan). Saya juga berasumsi bahwa .di sudut kiri bawah yang terakhir dimaksudkan menjadi D.

KSab
sumber
Anda benar, itu adalah dua kesalahan ketik, meskipun yang terakhir seharusnya menjadi E(bukan berarti ada bedanya ...). Sepertinya Anda dapat menyimpan banyak karakter dengan mengurangi kedalaman lekukan ke minimum.
Martin Ender
Saya tidak yakin apakah saya melakukan kesalahan menyalin-menempelkan contoh ketiga, tetapi garis miring terbalik tidak akan jatuh (mereka tampaknya bekerja pada contoh keempat)
Martin Ender
1
@ MartinBüttner, meskipun saya memang memiliki masalah copy-paste (pastikan tidak ada spasi spasi di akhir baris, dan tidak ada tab, hanya spasi) tampaknya berfungsi setelah saya sudah benar. Mungkin membantu memiliki contoh input dalam format yang lebih mudah untuk disalin-tempel, tanpa hasil yang diharapkan pada baris yang sama.
KSab