Tanam pohon di taman - Secepat mungkin!

20

Tantangan ini terinspirasi oleh aplikasi ini . Kasing uji dipinjam dari aplikasi itu.


Ini adalah tantangan , di mana tujuannya adalah untuk menyelesaikan kasus uji terbesar dalam jumlah waktu paling sedikit. Tersedia beberapa kasus uji yang lebih kecil, sehingga orang dapat menguji algoritme mereka lebih cepat.


Anda akan diberi kotak input persegi, dengan dimensi n-oleh-n di mana 9 <= n <= 12 . Kotak ini akan dibagi menjadi n area, di mana sel-sel di setiap area memiliki pengidentifikasi unik (saya akan menggunakan huruf kecil dari al dalam teks di sini, tetapi Anda dapat memilih apa pun yang Anda suka, misalnya bilangan bulat 1-12 ) .

Input mungkin terlihat seperti ini (format input opsional):

aabbbbbcc
adddbbbcc
adeeecccc
adddefgcc
hhhdifggg
hdddifffg
hhhiifffg
hihiifffg
iiiiiiggg

Atau, lebih mudah untuk divisualisasikan:

masukkan deskripsi gambar di sini

Tantangan:

Anda harus menempatkan 2 * n pohon di taman ini, sesuai dengan aturan berikut:

  • Tepatnya akan ada 2 pohon per kolom, dan 2 pohon per baris
  • Semua area harus memiliki tepat 2 pohon.
  • Tidak ada pohon yang dapat berbatasan dengan pohon lain, secara vertikal, horizontal atau diagonal

Solusi untuk tata letak di atas adalah:

masukkan deskripsi gambar di sini

Catatan: Hanya ada satu solusi untuk setiap puzzle

Aturan tambahan:

  • Format input dan output adalah opsional
    • Keluaran mungkin misalnya berupa daftar indeks, kisi dengan 1/0 yang menunjukkan apakah ada pohon di posisi itu, atau versi input yang dimodifikasi di mana pohon ditunjukkan
  • Waktu pelaksanaan harus deterministik
  • Program harus selesai dalam 1 menit di komputer @ isaacg
    • Spesifikasi: 4 CPU, CPU i5-4300U @ 1,9 GHz, RAM 7,5G.
  • Jika program Anda tidak dapat menyelesaikan dua test case terbesar dalam satu menit masing-masing maka waktu untuk terbesar kedua ( n = 11 ) akan menjadi skor Anda. Anda akan kalah terhadap solusi yang memecahkan kasus terbesar.

Kasus uji:

Saya mungkin mengedit daftar ini jika pengajuan tampaknya disesuaikan agar sesuai dengan kasus pengujian ini.

12-oleh-12 :

--- Input ---
aaaaabccccdd
aaaaabccccdd
aaaaabbbbddd
eeeafffgbghh
eeaafffgbghh
eefffffggghh
eeefijffghhh
iieiijjjjkhh
iiiiijjjjkhk
lljjjjjjjkkk
llllllkkkkkk
llllllkkkkkk
--- Solution ---
aaaaabcccCdD
aaaaaBcCccdd
aAaaabbbbdDd
eeeaffFgBghh
eeAaFffgbghh
eefffffGgGhh
EeefijffghhH
iiEiIjjjjkhh
IiiiijjjjkHk
lljJjJjjjkkk
lLllllkkKkkk
lllLllKkkkkk

11-oleh-11 :

--- Input ---
aaaaaaabbcc
adddabbbbcc
edddbbbbbbc
eddddbbbbbb
effffggghhh
effffgghhii
eefffjjhhii
eeeejjjhhii
eeejjjjkiii
jjjjjjkkiii
jjjjjkkkiii
--- Solution ---
aaAaaaabbCc
adddAbBbbcc
eDddbbbbbbC
eddDdBbbbbb
effffggGhHh
eFfffGghhii
eefFfjjhHii
EeeejjjhhiI
eeEjjjjKiii
JjjjJjkkiii
jjjjjkKkIii

10-kali-10

--- Input ---
aaaaabccdd
aeaabbbccd
aeaabfbgcd
eeeaafggcd
eeeaafghcd
eeeiifghcd
ieiiigghcd
iiijighhcd
jjjjighhcd
jjjggghhdd
--- Solution ---
aaAaabccdD
aeaaBbBccd
aEaabfbgcD
eeeaaFgGcd
eEeAafghcd
eeeiiFghCd
IeiIigghcd
iiijigHhCd
JjJjighhcd
jjjgGghHdd

9-oleh-9

--- Input ---
aabbbbbcc
adddbbbcc
adeeecccc
adddefgcc
hhhdifggg
hdddifffg
hhhiifffg
hihiifffg
iiiiiiggg
--- Solution ---
aAbBbbbcc
adddbbBcC
adEeEcccc
AdddefgCc
hhhDiFggg
hDddifffG
hhhiIfFfg
HiHiifffg
iiiiiIgGg
--- Input ---
aaabbbccc
aaaabbccc
aaaddbcce
ffddddcce
ffffddeee
fgffdheee
fggfhhhee
iggggheee
iiigggggg
--- Solution ---
aaAbBbccc
AaaabbcCc
aaaDdBcce
fFddddcCe
fffFdDeee
fGffdheeE
fggfHhHee
IggggheeE
iiIgggGgg
Stewie Griffin
sumber
"Format input dan output adalah opsional, tetapi harus sama" Apa artinya itu? Tidak bisakah saya membuat daftar daftar yang berisi angka 1 dan 0 untuk pohon dan bukan pohon tanpa peduli mengeluarkan area?
Fatalkan
@Singkat, diedit. Saya pikir mengeluarkan daftar indeks atau kotak dengan 1/0 seperti yang Anda sarankan adalah ide yang bagus.
Stewie Griffin
1
Informasi (jika saya hitung dengan benar): Ada 3647375398569086976 konfigurasi untuk menempatkan 24 pohon dalam kisi 12 * 12 hanya memuaskan (1):, There shall be exactly 2 trees per column, and 2 trees per rowsehingga kekuatan kasar mungkin tidak mungkin.
user202729
"seharusnya tidak menjadi masalah besar" : Saya pribadi berpikir begitu. Implementasi saya saat ini memecahkan kasus uji pertama dalam ~ 150ms dan yang ketiga dalam 5s tetapi gagal untuk menyelesaikan yang terakhir (yang 'hanya' 11x11) dalam jumlah waktu yang wajar. Mungkin akan membutuhkan pemangkasan maju yang jauh lebih agresif - dan karenanya sejumlah besar kode tambahan - untuk diselesaikan dalam 1 menit.
Arnauld
1
@Arnauld, saya mengubah maksimum menjadi 11 karena itu adalah ujian terbesar. Anda dapat memposting solusi Anda (sebagai pengiriman yang valid dan bersaing), tetapi itu tidak akan menang jika seseorang memposting solusi yang menyelesaikan semua kasus uji, terlepas dari panjang kode. Adil?
Stewie Griffin

Jawaban:

7

JavaScript (ES6), 271 byte

Mengambil input sebagai array array karakter. Mengembalikan array bitmask (bilangan bulat) yang menggambarkan posisi pohon di setiap baris, di mana bit paling signifikan adalah posisi paling kiri.

f=(a,p=0,r=[S=y=0],w=a.length)=>a.some((R,y)=>a.some((_,x)=>r[y]>>x&1&&(o[k=R[x]]=-~o[k])>2),o=[])?0:y<w?[...Array(1<<w)].some((_,n)=>(k=n^(x=n&-n))<=x*2|k&-k^k|n&(p|p/2|p*2)||r.some((A,i)=>r.some((B,j)=>A&B&n&&i<y&j<i))?0:(w=r[y],f(a,r[y++]=n,r),r[--y]=w,S))&&S:S=[...r]

Diformat dan dikomentari

f = (                                           // given:
  a,                                            //   - a = input matrix
  p = 0,                                        //   - p = previous bitmask
  r = [                                         //   - r = array of tree bitmasks
        S = y = 0 ],                            //   - S = solution / y = current row
  w = a.length                                  //   - w = width of matrix
) =>                                            //
  a.some((R, y) => a.some((_, x) =>             // if there's at least one area with more
    r[y] >> x & 1 && (o[k = R[x]] = -~o[k]) > 2 // than two trees:
  ), o = []) ?                                  //
    0                                           //   abort right away
  :                                             // else:
    y < w ?                                     //   if we haven't reached the last row:
      [...Array(1 << w)].some((_, n) =>         //     for each possible bitmask n:
        (k = n ^ (x = n & -n)) <= x * 2 |       //       if the bitmask does not consist of
        k & - k ^ k |                           //       exactly two non-consecutive bits,
        n & (p | p / 2 | p * 2) ||              //       or is colliding with the previous
        r.some((A, i) => r.some((B, j) =>       //       bitmask, or generates more than two
          A & B & n && i < y & j < i            //       trees per column:
        )) ?                                    //
          0                                     //         yield 0
        :                                       //       else:
          (                                     //
            w = r[y],                           //         save the previous bitmask
            f(a, r[y++] = n, r),                //         recursive call with the new one
            r[--y] = w,                         //         restore the previous bitmask
            S                                   //         yield S
          )                                     //
      ) && S                                    //     end of some(): return false or S
    :                                           //   else:
      S = [...r]                                //     this is a solution: save a copy in S

Uji kasus

Cuplikan ini mencakup fungsi tambahan untuk menampilkan hasil dalam format yang lebih mudah dibaca. Terlalu lambat untuk menyelesaikan kasus uji terakhir.

Runtime yang diharapkan: ~ 5 detik.

Arnauld
sumber
Catatan OP: Pengajuan ini dibuat ketika tantangannya adalah tantangan kode-golf. Karena itu valid, meskipun tidak dioptimalkan untuk kriteria kemenangan saat ini!
Stewie Griffin
Pengaturan waktu: Membutuhkan waktu lebih dari satu menit pada 11x11.
isaacg
Kami sedang dalam acar, mungkin Anda bisa membantu. Bisakah Anda memikirkan cara apa pun untuk menghasilkan contoh puzzle yang lebih besar dan tidak penting?
isaacg
7

C, waktu resmi: 5ms untuk 12x12

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <omp.h>

#define valT char
#define posT int

#ifndef _OPENMP
#  warning Building without OpenMP support
#  define omp_get_max_threads() 1
#  define omp_get_num_threads() 1
#  define omp_get_thread_num() 0
#endif

#define MIN_THREADED_SIZE 11

static void complete(posT n, valT *workspace) {
    const posT s = n * 3 + 2;

    const valT *regions = workspace;
    valT *output = &workspace[n*2+1];

    for(posT y = 0; y < n; ++ y) {
        for(posT x = 0; x < n; ++ x) {
//          putchar(output[y*s+x] ? '*' : '-');
            putchar(regions[y*s+x] + (output[y*s+x] ? 'A' : 'a'));
        }
        putchar('\n');
    }

    _Exit(0);
}

static void solveB(const posT n, valT *workspace, valT *pops, const posT y) {
    const posT s = n * 3 + 2;

    const valT *regions = workspace;
    const valT *remaining = &workspace[n];
    valT *output = &workspace[n*2+1];

    for(posT r = 0; r < n; ++ r) {
        if(pops[r] + remaining[r] < 2) {
            return;
        }
    }

    for(posT t1 = 0; t1 < n - 2; ++ t1) {
        posT r1 = regions[t1];
        if(output[t1+1-s]) {
            t1 += 2;
            continue;
        }
        if(output[t1-s]) {
            ++ t1;
            continue;
        }
        if((pops[t1+n] | pops[r1]) & 2 || output[t1-1-s]) {
            continue;
        }
        output[t1] = 1;
        ++ pops[t1+n];
        ++ pops[r1];
        for(posT t2 = t1 + 2; t2 < n; ++ t2) {
            posT r2 = regions[t2];
            if(output[t2+1-s]) {
                t2 += 2;
                continue;
            }
            if(output[t2-s]) {
                ++ t2;
                continue;
            }
            if((pops[t2+n] | pops[r2]) & 2 || output[t2-1-s]) {
                continue;
            }
            output[t2] = 1;
            ++ pops[t2+n];
            ++ pops[r2];
            if(y == 0) {
                complete(n, &workspace[-s*(n-1)]);
            }
            solveB(n, &workspace[s], pops, y - 1);
            output[t2] = 0;
            -- pops[t2+n];
            -- pops[r2];
        }
        output[t1] = 0;
        -- pops[t1+n];
        -- pops[r1];
    }
}

static void solve(const posT n, valT *workspace) {
    const posT s = n * 3 + 2;

    valT *regions = workspace;
    valT *remaining = &workspace[n];
    valT *pops = &workspace[n*s];
//  memset(&remaining[n*s], 0, n * sizeof(valT));

    for(posT y = n; (y --) > 0;) {
        memcpy(&remaining[y*s], &remaining[(y+1)*s], n * sizeof(valT));
        for(posT x = 0; x < n; ++ x) {
            valT r = regions[y*s+x];
            valT *c = &remaining[y*s+r];
            valT *b = &pops[r*3];
            if(*c == 0) {
                *c = 1;
                b[0] = y - 1;
                b[1] = x - 1;
                b[2] = x + 1;
            } else if(x < b[1] || x > b[2] || y < b[0]) {
                *c = 2;
            } else {
                b[1] = b[1] > (x - 1) ? b[1] : (x - 1);
                b[2] = b[2] < (x + 1) ? b[2] : (x + 1);
            }
        }
//      memset(&output[y*s], 0, (n+1) * sizeof(valT));
    }
    memset(pops, 0, n * 2 * sizeof(valT));

    posT sz = (n + 1) * s + n * 3;
    if(n >= MIN_THREADED_SIZE) {
        for(posT i = 1; i < omp_get_max_threads(); ++ i) {
            memcpy(&workspace[i*sz], workspace, sz * sizeof(valT));
        }
    }

#pragma omp parallel for if (n >= MIN_THREADED_SIZE)
    for(posT t1 = 0; t1 < n - 2; ++ t1) {
        valT *workspace2 = &workspace[omp_get_thread_num()*sz];
        valT *regions = workspace2;
        valT *output = &workspace2[n*2+1];
        valT *pops = &workspace2[n*s];

        posT r1 = regions[t1];
        output[t1] = pops[t1+n] = pops[r1] = 1;
        for(posT t2 = t1 + 2; t2 < n; ++ t2) {
            posT r2 = regions[t2];
            output[t2] = pops[t2+n] = 1;
            ++ pops[r2];
            solveB(n, &regions[s], pops, n - 2);
            output[t2] = pops[t2+n] = 0;
            -- pops[r2];
        }
        output[t1] = pops[t1+n] = pops[r1] = 0;
    }
}

int main(int argc, const char *const *argv) {
    if(argc < 2) {
        fprintf(stderr, "Usage: %s 'grid-here'\n", argv[0]);
        return 1;
    }

    const char *input = argv[1];
    const posT n = strchr(input, '\n') - input;
    const posT s = n * 3 + 2;

    posT sz = (n + 1) * s + n * 3;
    posT threads = (n >= MIN_THREADED_SIZE) ? omp_get_max_threads() : 1;
    valT *workspace = (valT*) calloc(sz * threads, sizeof(valT));
    valT *regions = workspace;

    for(posT y = 0; y < n; ++ y) {
        for(posT x = 0; x < n; ++ x) {
            regions[y*s+x] = input[y*(n+1)+x] - 'a';
        }
    }

    solve(n, workspace);

    fprintf(stderr, "Failed to solve grid\n");
    return 1;
}

Dikompilasi dengan GCC 7 menggunakan tanda -O3dan -fopenmp. Seharusnya memiliki hasil yang serupa pada versi GCC dengan OpenMP diinstal.

gcc-7 Trees.c -O3 -fopenmp -o Trees

Format input dan output seperti yang diberikan dalam pertanyaan.

Pada komputer saya ini membutuhkan 0,009s 0,008s 0,005s untuk contoh 12x12, dan 0,022s 0,020s 0,019s untuk menjalankan semua contoh. Pada mesin benchmark, isaacg melaporkan 5ms untuk contoh 12x12 menggunakan versi kode asli (non-berulir).

Pemakaian:

./Trees 'aaabbbccc
aaaabbccc
aaaddbcce
ffddddcce
ffffddeee
fgffdheee
fggfhhhee
iggggheee
iiigggggg'

Hanya pemecah brute-force sederhana, mengerjakan satu baris sekaligus. Ini berjalan dengan kecepatan yang baik dengan mengenali situasi-situasi yang mustahil sejak dini (mis. Tidak ada sel wilayah yang tersisa, tetapi kurang dari 2 pohon di wilayah itu).

Pembaruan pertama meningkatkan hit cache dengan menempatkan data terkait berdekatan dalam memori, dan membuat kalkulasi kemungkinan-tree-tersisa-di-segmen sedikit lebih pintar (sekarang memperhitungkan fakta bahwa pohon tidak dapat berdekatan). Itu juga mengekstrak loop terluar sehingga kasus khusus lebih sedikit diperlukan di bagian terpanas dari algoritma.

Pembaruan kedua membuat loop terluar berjalan paralel di seluruh prosesor yang tersedia (menggunakan OpenMP), memberikan peningkatan kecepatan linier. Ini hanya diaktifkan untuk n> = 11, karena overhead dari spawning threads lebih besar daripada manfaatnya untuk grid yang lebih kecil.

Dave
sumber
Waktu resmi: 5ms untuk 12x12. Jika ada orang lain yang dekat, kita akan membutuhkan kasus uji yang lebih besar.
isaacg
Kami sedang dalam acar, mungkin Anda bisa membantu. Bisakah Anda memikirkan cara apa pun untuk menghasilkan contoh puzzle yang lebih besar dan tidak penting?
isaacg
@isaacg Nah dari contoh yang diilustrasikan, tampaknya kisi-kisi asli dibuat dengan menempatkan pohon terlebih dahulu (dalam pola ksatria dengan perubahan kecil dalam contoh itu, tapi saya kira pola apa pun dengan 2 pohon per baris & kolom akan berfungsi) kemudian paskan daerah di sekitar sehingga masing-masing daerah mengandung 2 pohon. Sepertinya itu harus menjadi metode yang cukup sederhana untuk diikuti manusia untuk grid besar yang sewenang-wenang.
Dave
Bahkan, melihat lagi, itu bukan pola ksatria dengan perubahan kecil, tetapi pola pembungkus di mana setiap pohon diimbangi (1,2) dari sebelumnya. Setelah Anda memiliki pola, Anda dapat mengubah urutan baris dan kolom untuk membuat solusi yang kurang terstruktur, asalkan tidak meninggalkan pohon yang berdekatan.
Dave
5

Java (OpenJDK 8) , Waktu Resmi: 1.2s pada 12x12

sunting: tidak ada lagi kode golf

import java.util.*;

// Callable method, takes an int[][] and modifies it
static void f(int[][] areas){
    List<List<BitSet>> areaBitSets = new ArrayList<>();
    List<List<BitSet>> areaTreeBitSets = new ArrayList<>();
    for(int i = 0; i < areas.length; i++){
        areaBitSets.add(new ArrayList<BitSet>());
        areaTreeBitSets.add(new ArrayList<BitSet>());
    }

    // Add a bitset to our list representing each possible square, grouped by area
    for(int i=0; i < areas.length; i++){
        for(int j=0; j < areas.length; j++){
            BitSet b = new BitSet();
            b.set(i*areas.length + j);
            areaBitSets.get(areas[i][j]).add(b);
        }
    }

    // Fold each set onto itself so each area bitset has two trees
    for(int i=0; i < areas.length; i++){
        for(int j=0; j<areaBitSets.get(i).size()-1; j++){
            for(int k=j+1; k <areaBitSets.get(i).size(); k++){
                if(canFoldTogether(areaBitSets.get(i).get(j),areaBitSets.get(i).get(k), areas.length)){
                    BitSet b = (BitSet)areaBitSets.get(i).get(j).clone();
                    b.or(areaBitSets.get(i).get(k));
                    areaTreeBitSets.get(i).add(b);
                }
            }
        }
    }

    // Starting with area 0 add each area one at a time doing Cartesian products
    Queue<BitSet> currentPossibilities = new LinkedList<>();
    Queue<BitSet> futurePossibilities = new LinkedList<>();
    currentPossibilities.addAll(areaTreeBitSets.get(0));

    for(int i=1; i < areaTreeBitSets.size(); i++){
        while(!currentPossibilities.isEmpty()){
            BitSet b= (BitSet)currentPossibilities.poll().clone();

            for(BitSet c: areaTreeBitSets.get(i)){
                if(canFoldTogether(b,c,areas.length)){
                    BitSet d=(BitSet)b.clone();
                    d.or(c);
                    futurePossibilities.add(d);
                }
            }
        }
        currentPossibilities.addAll(futurePossibilities);
        futurePossibilities.clear();
    }

    // Get final output and modify the array
    BitSet b = currentPossibilities.poll();
    for(int i=0; i<areas.length*areas.length; i++){
        areas[i/areas.length][i%areas.length] = b.get(i)?1:0;
    }
}

// Helper method which determines whether combining two bitsets
// will still produce a valid output
static boolean canFoldTogether(BitSet a, BitSet b, int size){

    // See if there are trees too close to each other
    int c=-1;
    while((c=a.nextSetBit(c+1))>=0){
        int d=-1;
        while((d=b.nextSetBit(d+1))>=0){
            int r1=c/size;
            int r2=d/size;
            int c1=c%size;
            int c2=d%size;

            int rDifference = r1>r2 ? r1-r2 : r2-r1;
            int cDifference = c1>c2 ? c1-c2 : c2-c1;
            if(rDifference<2 && cDifference<2)
                return false;
        }
    }

    // Check for row and column cardinality
    BitSet f,g;
    for(int i=0; i<size; i++){
        f = new BitSet();
        f.set(i*size,(i+1)*size);
        g=(BitSet)f.clone();
        f.and(a);
        g.and(b);
        f.or(g);
        if(f.cardinality()>2){
            return false;
        }


        f=new BitSet();
        for(int j = 0; j<size; j++){
            f.set(j*size+i);
        }
        g=(BitSet)f.clone();
        f.and(a);
        g.and(b);
        f.or(g);
        if(f.cardinality()>2){
            return false;
        }
    }

    return true;
}

Cobalah online!

TIO link adalah untuk test case 12x12. TIO melaporkan 2,429 untuk jangka waktu berjalan.

Mengambil array bilangan bulat sebagai input dan memodifikasi array berisi 1s untuk pohon dan 0s untuk non-pohon.

Ini berjalan untuk semua testcases. Testcase terbesar berjalan pada mesin saya dalam waktu kurang dari satu detik, meskipun saya memiliki mesin yang cukup kuat

Kode uji untuk 12x12, dapat dimodifikasi untuk orang lain

public static void main(String[] args){
    int[][] test = {{0,  0,  0,  0,  0,  1,  2,  2,  2,  2,  3,  3}, 
            {0,  0,  0,  0,  0,  1,  2,  2,  2,  2,  3,  3}, 
            {0,  0,  0,  0,  0,  1,  1,  1,  1,  3,  3,  3}, 
            {4,  4,  4,  0,  5,  5,  5,  6,  1,  6,  7,  7}, 
            {4,  4,  0,  0,  5,  5,  5,  6,  1,  6,  7,  7}, 
            {4,  4,  5,  5,  5,  5,  5,  6,  6,  6,  7,  7}, 
            {4,  4,  4,  5,  8,  9,  5,  5,  6,  7,  7,  7}, 
            {8,  8,  4,  8,  8,  9,  9,  9,  9,  10,  7,  7}, 
            {8,  8,  8,  8,  8,  9,  9,  9,  9,  10,  7,  10}, 
            {11,  11,  9,  9,  9,  9,  9,  9,  9,  10,  10,  10}, 
            {11,  11,  11,  11,  11,  11,  10,  10,  10,  10,  10,  10}, 
            {11,  11,  11,  11,  11,  11,  10,  10,  10,  10,  10,  10}};

    long l = System.currentTimeMillis();
    f(test);
    System.out.println("12x12: " + (System.currentTimeMillis() - l) + "ms");

    for(int[] t : test){
        System.out.println(Arrays.toString(t));
    }

}

Menghasilkan ini di mesin saya:

12x12: 822ms
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1]
[0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0]
[0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0]
PunPun1000
sumber
Catatan OP: Pengajuan ini dibuat ketika tantangannya adalah tantangan kode-golf. Karena itu sangat valid, meskipun tidak (hanya) dioptimalkan untuk kriteria kemenangan saat ini!
Stewie Griffin
@StewieGriffin terima kasih atas komentarnya. Ketika saya mendapat kesempatan, saya akan berusaha membersihkannya karena ini bukan kode golf lagi dan lihat apakah saya dapat mengoptimalkannya dengan cepat
PunPun1000
Waktu resmi: 1,2 detik pada 12x12.
isaacg
Kami sedang dalam acar, mungkin Anda bisa membantu. Bisakah Anda memikirkan cara apa pun untuk menghasilkan contoh puzzle yang lebih besar dan tidak penting?
isaacg
4

Clingo , ≈ 7 ms untuk 12 × 12, 116 byte

{t(X,Y):c(X,Y,Z)}=2:-Z=1..n.
:-X=1..n,{t(X,1..n)}!=2.
:-Y=1..n,{t(1..n,Y)}!=2.
:-t(X,Y),t(X+1,Y;X+1,Y+1;X,Y+1;X-1,Y+1).

(Baris baru bersifat opsional dan tidak dihitung.)

Jalankan dengan di clingo plant.lp - -c n=<n>mana <n>ukuran kisi. Format masukan adalah daftar c(X,Y,Z).pernyataan untuk setiap sel ( X, Y) berwarna Z, dengan 1 ≤ X, Y, Zn, dipisahkan oleh spasi opsional. Output termasuk t(X,Y)untuk setiap pohon di ( X,Y ).

Waktu ini sangat tidak berarti karena ini pada dasarnya hanya waktu startup, jadi pertimbangkan ini suara untuk kasus uji yang lebih besar.

Demo

$ clingo plant.lp -c n=12 - <<EOF
> c(1,1,1). c(2,1,1). c(3,1,1). c(4,1,1). c(5,1,1). c(6,1,2). c(7,1,3). c(8,1,3). c(9,1,3). c(10,1,3). c(11,1,4). c(12,1,4).
> c(1,2,1). c(2,2,1). c(3,2,1). c(4,2,1). c(5,2,1). c(6,2,2). c(7,2,3). c(8,2,3). c(9,2,3). c(10,2,3). c(11,2,4). c(12,2,4).
> c(1,3,1). c(2,3,1). c(3,3,1). c(4,3,1). c(5,3,1). c(6,3,2). c(7,3,2). c(8,3,2). c(9,3,2). c(10,3,4). c(11,3,4). c(12,3,4).
> c(1,4,5). c(2,4,5). c(3,4,5). c(4,4,1). c(5,4,6). c(6,4,6). c(7,4,6). c(8,4,7). c(9,4,2). c(10,4,7). c(11,4,8). c(12,4,8).
> c(1,5,5). c(2,5,5). c(3,5,1). c(4,5,1). c(5,5,6). c(6,5,6). c(7,5,6). c(8,5,7). c(9,5,2). c(10,5,7). c(11,5,8). c(12,5,8).
> c(1,6,5). c(2,6,5). c(3,6,6). c(4,6,6). c(5,6,6). c(6,6,6). c(7,6,6). c(8,6,7). c(9,6,7). c(10,6,7). c(11,6,8). c(12,6,8).
> c(1,7,5). c(2,7,5). c(3,7,5). c(4,7,6). c(5,7,9). c(6,7,10). c(7,7,6). c(8,7,6). c(9,7,7). c(10,7,8). c(11,7,8). c(12,7,8).
> c(1,8,9). c(2,8,9). c(3,8,5). c(4,8,9). c(5,8,9). c(6,8,10). c(7,8,10). c(8,8,10). c(9,8,10). c(10,8,11). c(11,8,8). c(12,8,8).
> c(1,9,9). c(2,9,9). c(3,9,9). c(4,9,9). c(5,9,9). c(6,9,10). c(7,9,10). c(8,9,10). c(9,9,10). c(10,9,11). c(11,9,8). c(12,9,11).
> c(1,10,12). c(2,10,12). c(3,10,10). c(4,10,10). c(5,10,10). c(6,10,10). c(7,10,10). c(8,10,10). c(9,10,10). c(10,10,11). c(11,10,11). c(12,10,11).
> c(1,11,12). c(2,11,12). c(3,11,12). c(4,11,12). c(5,11,12). c(6,11,12). c(7,11,11). c(8,11,11). c(9,11,11). c(10,11,11). c(11,11,11). c(12,11,11).
> c(1,12,12). c(2,12,12). c(3,12,12). c(4,12,12). c(5,12,12). c(6,12,12). c(7,12,11). c(8,12,11). c(9,12,11). c(10,12,11). c(11,12,11). c(12,12,11).
> EOF
clingo version 5.1.0
Reading from plant.lp ...
Solving...
Answer: 1
c(1,1,1) c(2,1,1) c(3,1,1) c(4,1,1) c(5,1,1) c(6,1,2) c(7,1,3) c(8,1,3) c(9,1,3) c(10,1,3) c(11,1,4) c(12,1,4) c(1,2,1) c(2,2,1) c(3,2,1) c(4,2,1) c(5,2,1) c(6,2,2) c(7,2,3) c(8,2,3) c(9,2,3) c(10,2,3) c(11,2,4) c(12,2,4) c(1,3,1) c(2,3,1) c(3,3,1) c(4,3,1) c(5,3,1) c(6,3,2) c(7,3,2) c(8,3,2) c(9,3,2) c(10,3,4) c(11,3,4) c(12,3,4) c(1,4,5) c(2,4,5) c(3,4,5) c(4,4,1) c(5,4,6) c(6,4,6) c(7,4,6) c(8,4,7) c(9,4,2) c(10,4,7) c(11,4,8) c(12,4,8) c(1,5,5) c(2,5,5) c(3,5,1) c(4,5,1) c(5,5,6) c(6,5,6) c(7,5,6) c(8,5,7) c(9,5,2) c(10,5,7) c(11,5,8) c(12,5,8) c(1,6,5) c(2,6,5) c(3,6,6) c(4,6,6) c(5,6,6) c(6,6,6) c(7,6,6) c(8,6,7) c(9,6,7) c(10,6,7) c(11,6,8) c(12,6,8) c(1,7,5) c(2,7,5) c(3,7,5) c(4,7,6) c(5,7,9) c(6,7,10) c(7,7,6) c(8,7,6) c(9,7,7) c(10,7,8) c(11,7,8) c(12,7,8) c(1,8,9) c(2,8,9) c(3,8,5) c(4,8,9) c(5,8,9) c(6,8,10) c(7,8,10) c(8,8,10) c(9,8,10) c(10,8,11) c(11,8,8) c(12,8,8) c(1,9,9) c(2,9,9) c(3,9,9) c(4,9,9) c(5,9,9) c(6,9,10) c(7,9,10) c(8,9,10) c(9,9,10) c(10,9,11) c(11,9,8) c(12,9,11) c(1,10,12) c(2,10,12) c(3,10,10) c(4,10,10) c(5,10,10) c(6,10,10) c(7,10,10) c(8,10,10) c(9,10,10) c(10,10,11) c(11,10,11) c(12,10,11) c(1,11,12) c(2,11,12) c(3,11,12) c(4,11,12) c(5,11,12) c(6,11,12) c(7,11,11) c(8,11,11) c(9,11,11) c(10,11,11) c(11,11,11) c(12,11,11) c(1,12,12) c(2,12,12) c(3,12,12) c(4,12,12) c(5,12,12) c(6,12,12) c(7,12,11) c(8,12,11) c(9,12,11) c(10,12,11) c(11,12,11) c(12,12,11) t(1,7) t(1,9) t(2,3) t(2,11) t(3,5) t(3,8) t(4,10) t(4,12) t(5,5) t(5,8) t(6,2) t(6,10) t(7,4) t(7,12) t(8,2) t(8,6) t(9,4) t(9,11) t(10,1) t(10,6) t(11,3) t(11,9) t(12,1) t(12,7)
SATISFIABLE

Models       : 1+
Calls        : 1
Time         : 0.009s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

Untuk membuat format input / output lebih mudah ditangani, berikut adalah program Python untuk mengkonversi dari dan ke format yang diberikan dalam tantangan.

Memasukkan

import sys
print(' '.join("c({},{},{}).".format(x + 1, y + 1, ord(cell) - ord('a') + 1) for y, row in enumerate(sys.stdin.read().splitlines()) for x, cell in enumerate(row)))

Keluaran

import re
import sys
for line in sys.stdin:
    c = {(int(x), int(y)): int(z) for x, y, z in re.findall(r'\bc\((\d+),(\d+),(\d+)\)', line)}
    if c:
        t = {(int(x), int(y)) for x, y in re.findall(r'\bt\((\d+),(\d+)\)', line)}
        n, n = max(c)
        for y in range(1, n + 1):
            print(''.join(chr(ord('aA'[(x, y) in t]) + c[x, y] - 1) for x in range(1, n + 1)))
        print()
Anders Kaseorg
sumber
Sepertinya kita akan membutuhkan test case yang lebih besar. Btw, Anda akan memenangkan versi golf dari pertanyaan ini - hanya perlu 2s berubah menjadi 1s.
Dave
Waktu resmi adalah 18 milidetik pada 12x12, saya minta maaf. 1 karakter salah ketik, itulah masalah dengan singkatan.
isaacg
Kami sedang dalam acar, mungkin Anda bisa membantu. Bisakah Anda memikirkan cara apa pun untuk menghasilkan contoh puzzle yang lebih besar dan tidak penting?
isaacg