Kompresi Papan Boggle

Ketika mengerjakan Non-Palindromic Polyglot Boggle , saya merasa cukup membosankan untuk mengemas kode seefisien mungkin ke papan Boggle, bahkan dengan hanya dua string. Tapi kami programmer, kan? Kami tahu cara mengotomatisasi sesuatu.

Diberikan daftar string, Anda akan menghasilkan papan Boggle di mana masing-masing string dapat ditemukan (terlepas dari yang lain). Tantangannya adalah membuat papan Boggle sekecil mungkin. Karena ini (semoga) tugas yang agak sulit, ini adalah tantangan kode : tidak ada persyaratan untuk optimalitas - tantangannya adalah melakukannya sebaik yang Anda bisa.

Aturan

Papan Boggle akan berbentuk persegi panjang dan hanya berisi huruf besar. Oleh karena itu, string input juga hanya akan berisi huruf besar.
Aturan Boggle yang biasa berlaku: string adalah bagian dari papan jika, mulai dari mana saja, Anda dapat menemukan string dengan berulang kali berpindah ke karakter yang berdekatan (horizontal, vertikal, atau diagonal). Untuk membentuk string tunggal, Anda tidak dapat menggunakan sel papan apa pun lebih dari sekali. Namun, karakter dapat digunakan kembali di antara string yang berbeda.
Anda punya waktu 30 menit untuk memproses data pengujian, dan kode Anda tidak boleh menggunakan lebih dari 4 GB memori. Saya akan memberikan sedikit kelonggaran pada batas memori, tetapi jika program Anda secara konsisten menggunakan lebih dari 4 GB atau lonjakan secara signifikan di atasnya, saya akan (sementara) mendiskualifikasi itu.
Saya akan menguji semua kiriman di mesin saya sendiri, yang menjalankan Windows 8. Saya memang memiliki Ubuntu VM, tetapi jika saya harus mengujinya Anda tidak akan dapat menggunakan sebanyak 30 menit sebanyak sebaliknya. Harap sertakan tautan ke juru bahasa gratis / kompiler untuk bahasa pilihan Anda, serta instruksi tentang cara menyusun / menjalankan kode Anda.
Skor Anda akan menjadi ukuran papan Boggle untuk data tes di bawah ini (tidak termasuk baris baru). Dalam kasus seri (mis. Karena banyak orang berhasil menghasilkan solusi optimal), pemenangnya adalah pengajuan yang menghasilkan solusi optimal ini lebih cepat.
Anda tidak boleh mengoptimalkan kode Anda secara khusus terhadap data pengujian. Jika saya mencurigai ada yang melakukannya, saya berhak untuk menghasilkan data pengujian baru.

Contoh

Diberikan string

FOO
BAR
BOOM

Sekali mudah bisa menempatkan mereka di papan Boggle 4x3:

FOOX
BARX
BOOM

Dengan memanfaatkan fakta bahwa string tidak harus lurus, kita dapat mengompresnya menjadi 5x2:

BORFO
OMABO

Tapi kita bisa membuatnya lebih kecil dengan menggunakan kembali karakter di antara string yang berbeda, dan menyesuaikan string di 4x2:

FOOM
BARX

Sekarang Bdigunakan untuk keduanya BOOMdan BAR, dan OOdigunakan untuk keduanya BOOMdan FOO.

Data Uji

Kiriman Anda akan diuji pada 50 string berikut. Untuk tujuan pengujian Anda cukup menggunakan himpunan bagian kecil dari data ini yang kemudian harus berjalan lebih cepat. Saya percaya bahwa batas bawah absolut untuk data tes ini adalah papan dengan 120 karakter, meskipun ini belum tentu dapat dicapai.

T
WP
GVI
CIHM
EGWIV
QUTYFZ
LWJVPNG
XJMJQWSW
JLPNHFDUW
SWMHBBZWUG
XVDBMDQWDEV
TIUGAVZVUECC
IWDICFWBPSPQR
MMNWFBGMEXMSPY
YIHYXGJXKOUOIZA
BZSANEJNJWWNUJLJ
XTRMGOVPHVZYLLKKG
FLXFVVHNTWLMRRQYFQ
VZKJRAFQIYSBSXORTSH
FNQDIGCPALCHVLHDNZAV
GEAZYFSBSWCETXFKMSWLG
KWIZCEHVBDHEBGDGCJHOID
SKMQPHJAPDQKKHGTIPJCLMH
ZSFQDNYHALSUVWESQVVEUIQC
HXHBESUFCCECHNSTQGDUZPQRB
DSLXVHMOMLUXVHCNOJCBBRPVYB
DVTXKAOYYYRBVAVPSUAOYHIPPWN
PJAIYAWHMTNHTQDZDERPZYQEMLBZ
SYNSHJNOIWESMKWTBIANYUAUNRZOS
WADGUKIHUUFVRVUIBFUXQIOLAWIXAU
LGLXUFIXBEPSOFCKIAHXSHVKZPCXVPI
LIUYFHITTUYKDVQOZPNGZLWOZSRJTCTZ
IZDFTFFPNEBIYGVNTZHINICBXBXLBNBAL
BSKQNTPVUAVBXZGHVZCOUCRGCYISGFGYAS
DPGYYCIKDGCETXQOZGEQQLFQWACMVDTRYAT
RQDNIPGUHRYDRVHIPJLOWKBXMIBFAWCJGFMC
PFKOAGEQLXCMISSVEARWAPVYMRDCLSLPJOMQQ
EQPCNHQPTWABPFBVBXHQTFYELPNMNCWVKDDKGR
RAHTJMGIQJOJVWJBIHVRLJYVCSQJCKMEZRGRJMU
SZBJBPQYVYKDHAJHZMHBEWQEAQQKIEYCFACNLJBC
ANVDUCVXBPIZVRAXEBFEJOHSYKEKBIJELPIWEYXKH
DJUNPRLTISBFMGBEQNXSNUSOGDJNKESVKGAAMTIVXK
TZPUHDSHZFEURBNZTFBKXCDPYRELIAFMUWDIQTYWXGU
FJIKJROQSFSZUCGOOFJIEHBZREEUUSZWOLYFPCYHUSMR
TPMHJEAWVAJOCSDOPMQMHKRESBQSTRBXESYGCDVKLFOVS
ABJCCDJYMYDCYPZSGPGIAIKZQBYTZFDWYUZQBOESDSDGOY
IIHKTVPJNJDBCBOHCIYOPBKOVVKGNAKBDKEEKYIPRPHZOMF
IABGEPCSPNSMLVJBSGLRYNFSSYIALHWWAINTAVZAGJRVMDPW
GFMFVEFYJQJASVRIBLULUEHPMZPEXJMHIEMGJRMBLQLBDGTWT
YPWHLCVHQAVKVGHMLSOMPRERNHVYBECGCUUWTXNQBBTCMVTOVA

Penguji

Anda dapat menggunakan Cuplikan Stack berikut untuk memverifikasi apakah papan Boggle berisi semua string dalam daftar yang diberikan. Saya porting kode pencarian Boggle dari jawaban edc65 di sini . Beri tahu saya jika ada yang bermasalah.

Tampilkan cuplikan kode

function verify() {
  var strings = document.getElementById("strings").value;
  var board = document.getElementById("board").value;
  strings = strings.match(/[A-Z]+/g) || [];
  board = board.split('\n');
  var valid = true;
  var len = board[0].length;
  var result = 'Valid';
  for (var i = 0; i < board.length; ++i)
  {
    if (board[i].length != len)
    {
      valid = false;
      result = 'Invalid: Board not rectangular.';
    }
    if (/[^A-Z]/.test(board[i]))
    {
      valid = false;
      result = 'Invalid: Board contains invalid character on line '+i+'.';
    }
    if (!valid) break;
  }
  if (valid)
    for (i = 0; i < strings.length; ++i) {
      if (!findInBoard(board, strings[i]))
      {
        valid = false;
        result = 'Invalid: String "'+strings[i]+'"not found in board.';
        break;
      }
    }
  document.getElementById("output").innerHTML = result;
}

function findInBoard(b, w) {
  var l = b[0].length;
  var r = 0;
  var Q = function(p, n) {
    return (r |= !w[n]) || 
    (
      b[p] = 0,
      [1,l,l+1,l+2,-1,-l,-l-1,-l-2].map( function(q) { return b[q+=p]==w[n] && Q(q,n+1) }),
      b[p] = w[n-1]
    );
  }
  b = (b+'').split('');
  b.map(function(e, p) { return e==w[0] && Q(p,1) });
  return r;
}

Strings that should be part of the Boggle board:
<br>
<textarea id="strings" cols="60" rows="10"></textarea>
<br>
Boggle board:
<br>
<textarea id="board" cols="60" rows="10"></textarea>
<br>
<input type="button" value="Verify" onclick="verify()" />
<br>
<br>
<div id="output"></div>

Luaskan cuplikan

code-challenge compression boggle Martin Ender
sumber

Jawaban:

C ++ 11, skor = 992 1024

Algoritma ini benar-benar bodoh, tetapi sejauh ini tidak ada yang membuat yang serius juga, jadi saya akan mempostingnya. Ini kurang lebih secara acak menempelkan kata-kata di papan persegi, dan kemudian memulai kembali jika tidak berhasil membuatnya cocok. Ini semacam mencoba memaksimalkan tumpang tindih dengan kata-kata yang ada, tetapi dengan cara yang sangat tidak efisien.

Sunting: Peningkatan skor dengan menambahkan 1 panjang sisi dan mencoba persegi panjang setelah gagal 50 kali. Juga mengurutkan string input berdasarkan ukuran alih-alih mengacak urutan.

#include <iostream>
#include <cstring>
#include <string>
#include <random>
#include <algorithm>
using namespace std;

struct grid {
    char *g;
    int h,w;
    grid(int h, int w):h(h),w(w) {
        g = new char[h*w];
        memset(g,0,h*w*sizeof(*g));
    }
    grid(const grid &o) {
        h=o.h, w=o.w;
        g = new char[h*w];
        memcpy(g,o.g,h*w*sizeof(*g));
    }
    grid(grid &&o) {
        h=o.h, w=o.w;
        g = o.g;
        o.g = 0;
    }
    grid& operator=(const grid &o) {
        h=o.h, w=o.w;
        memcpy(g,o.g,h*w*sizeof(*g));
        return*this;
    }
    grid& operator=(grid &&o) {
        h=o.h, w=o.w;
        g = o.g;
        o.g = 0;
        return*this;
    }
    char& operator()(int i, int j) {
        return g[i*w+j];
    }
    ~grid() { delete []g; }
};
typedef struct { int n, i, j; grid g; } ng;


const int qmax = 140;
const bool sizesort = true;
const int maxtries = 50;

inline int sq(int x){return x*x;}
bool operator<(const ng &a, const ng& b) {return a.n < b.n;}
void search(vector<string>& s) {
    int tl = 0;
    for(auto&x: s) tl += x.size();
    int l = 0;
    while(l*l < tl) l++;
    vector<string*> v;
    for(size_t i = 0; i < s.size(); i++) v.push_back(&s[i]);
    struct{bool operator()(string*a,string*b){return a->size()>b->size();}} scmp;
    if(sizesort) sort(v.begin(), v.end(), scmp);
    mt19937 rng;
    for(;;l--) {
        int tries = 0;
        int side2 = l;
        retry:
        tries++;
        if(!sizesort) shuffle(v.begin(), v.end(), rng);

        if(tries == maxtries) cout<<"rectangle",side2++;
        grid g(l,side2);

        for(string* x: v) {
            string& z = *x;
            vector<ng> p;
            for(int i = 0; i < g.h; i++)
            for(int j = 0; j < g.w; j++) {
                if(g(i,j) && g(i,j) != z[0]) continue;
                p.push_back({!g(i,j), i,j, g});
                p.back().g(i,j) = z[0]|32;
            }
            for(size_t zi = 1; zi < z.size(); zi++) {
                vector<ng> p2;
                for(ng &gg: p) {
                    for(int i = max(gg.i-1,0); i <= min(gg.i+1,g.h-1); i++)
                    for(int j = max(gg.j-1,0); j <= min(gg.j+1,g.w-1); j++) {
                        if(!gg.g(i,j) || gg.g(i,j) == z[zi]) {
                            p2.push_back({gg.n+!g(i,j),i,j,gg.g});
                            p2.back().g(i,j) = z[zi]|32;
                        }
                    }
                }
                shuffle(p2.begin(), p2.end(), rng);
                sort(p2.begin(), p2.end());
                if(p2.size() > qmax) p2.erase(p2.begin() + qmax, p2.end());
                p = move(p2);
            }
            if(p.empty()) goto retry;
            g = p[0].g;
            for(int i = 0; i < g.h; i++)
            for(int j = 0; j < g.w; j++)
                g(i,j) &= ~32;
        }
        cout<<g.w*g.h;
        for(int i = 0; i < g.h; i++) {
            cout<<'\n';
            for(int j = 0; j < g.w; j++)
                cout<<(g(i,j)?g(i,j):'X');
        }
        cout<<endl;
    }
}

int main()
{
    vector<string> v = {"T","WP","GVI","CIHM","EGWIV","QUTYFZ","LWJVPNG","XJMJQWSW","JLPNHFDUW","SWMHBBZWUG","XVDBMDQWDEV","TIUGAVZVUECC","IWDICFWBPSPQR","MMNWFBGMEXMSPY","YIHYXGJXKOUOIZA","BZSANEJNJWWNUJLJ","XTRMGOVPHVZYLLKKG","FLXFVVHNTWLMRRQYFQ","VZKJRAFQIYSBSXORTSH","FNQDIGCPALCHVLHDNZAV","GEAZYFSBSWCETXFKMSWLG","KWIZCEHVBDHEBGDGCJHOID","SKMQPHJAPDQKKHGTIPJCLMH","ZSFQDNYHALSUVWESQVVEUIQC","HXHBESUFCCECHNSTQGDUZPQRB","DSLXVHMOMLUXVHCNOJCBBRPVYB","DVTXKAOYYYRBVAVPSUAOYHIPPWN","PJAIYAWHMTNHTQDZDERPZYQEMLBZ","SYNSHJNOIWESMKWTBIANYUAUNRZOS","WADGUKIHUUFVRVUIBFUXQIOLAWIXAU","LGLXUFIXBEPSOFCKIAHXSHVKZPCXVPI","LIUYFHITTUYKDVQOZPNGZLWOZSRJTCTZ","IZDFTFFPNEBIYGVNTZHINICBXBXLBNBAL","BSKQNTPVUAVBXZGHVZCOUCRGCYISGFGYAS","DPGYYCIKDGCETXQOZGEQQLFQWACMVDTRYAT","RQDNIPGUHRYDRVHIPJLOWKBXMIBFAWCJGFMC","PFKOAGEQLXCMISSVEARWAPVYMRDCLSLPJOMQQ","EQPCNHQPTWABPFBVBXHQTFYELPNMNCWVKDDKGR","RAHTJMGIQJOJVWJBIHVRLJYVCSQJCKMEZRGRJMU","SZBJBPQYVYKDHAJHZMHBEWQEAQQKIEYCFACNLJBC","ANVDUCVXBPIZVRAXEBFEJOHSYKEKBIJELPIWEYXKH","DJUNPRLTISBFMGBEQNXSNUSOGDJNKESVKGAAMTIVXK","TZPUHDSHZFEURBNZTFBKXCDPYRELIAFMUWDIQTYWXGU","FJIKJROQSFSZUCGOOFJIEHBZREEUUSZWOLYFPCYHUSMR","TPMHJEAWVAJOCSDOPMQMHKRESBQSTRBXESYGCDVKLFOVS","ABJCCDJYMYDCYPZSGPGIAIKZQBYTZFDWYUZQBOESDSDGOY","IIHKTVPJNJDBCBOHCIYOPBKOVVKGNAKBDKEEKYIPRPHZOMF","IABGEPCSPNSMLVJBSGLRYNFSSYIALHWWAINTAVZAGJRVMDPW","GFMFVEFYJQJASVRIBLULUEHPMZPEXJMHIEMGJRMBLQLBDGTWT","YPWHLCVHQAVKVGHMLSOMPRERNHVYBECGCUUWTXNQBBTCMVTOVA"};
    search(v);
    return 0;
}

Papan:

TGBHXEXMPYTECWBSFYOXKXKXFSQJXKXX
UZBWMLJKSXXPIXSVYYXATVDLVOCVCXMT
WWPSJGBUFWPOUHPAKRZMXIPCHHXJYEAX
SQPBNXFQNMLAYSQVBGAESYGWQJOVXJZY
RJXWJJDWMNSGFUQXSEAWXBMIJAYWLRTR
XMXFEIWIHTIHIGMOJTKVARJNPSVFJVDG
XJHNCGCCQXTYLSJHVNOJXHTSCKERBHMR
XVCLACEDGTCCDGLPMCJXXMQMQPVGIAJC
DLZSFPURZYUGRKENTWSDPVLSHBFFHBMA
HNBUQYZPDOKNMYDDVBBOGJBQGKSMLUWQ
XXZRSEBQNCQDPVFNKSSQNCDLXERPMSLF
XKVAIHMHTGZVUXPTQUSXXGEBRXEZHOUQ
XRJUXYNLQFJLHAVQPNNXTCXYMRJPKEQH
FAPIHATDBSWXWGBHCQHPBWUVNMJGKGVP
XQVVWMLJRZZOVRZXESFQTAUFHIMLLYZV
XIWXUSOQTXTLSEABVBIPXGXSYEAEMGOX
WEYQCBIUXCNSJKGRFZXTBXXSMFLIRYPQ
XGSBIPFLPAMIBEEMVEJLXDWDUBHTYXDX
XQSUXIZQGFOCPLKSUOAREVYQDWDVXCTA
XXVEBKXLEKCIOFYYHCBJPCTKIAWKIMZE
ORVEUGVIXYEWFPCCDJCNUDANHIBODFCI
XTOFPUSHKQXAZYDYIYOBJZVZBFMXLGOU
SZNSCXHLWQQSGCTQMBPDGAXXTRACJJXO
HRUAUKIAXEUOPGUIKWRJMNKKDGUWPBGK
ZVEYNGDNBUEOJIAZQORVGBDSEEOYIYXX
VMHCCAIBHRHFAESSBXVJKQOSKYFZHVPB
ALEVJPTWLMZJHXXFJYXIZUEFLIGUSRRB
GZCBDHPKMXXBXDSBTZJDUYVXNQPPHDYC
UIPJQKEQSBNICKYPNEFHWVHFDFRUZOJX
KWTGKXGBEOIJHNVQFBTLNTNMYXLTXNMX
DIOHJCXDGWHZTSGYIFJPMRRQOMXVHCFX

feersum
sumber

Python 3, skor = 1225

Dalam solusi ini kami hanya menggunakan 1 baris. Mulai dari string kosong di setiap langkah kami menambahkan kata yang menjamin tumpang tindih terbesar. (Kata-kata itu dicentang di semua 4 orientasi yang mungkin.)

Ini memberikan skor 1225 yang 50 lebih rendah dari skor 1275 untuk menggabungkan semua kata bersama tanpa tumpang tindih.

Hasil:

CBJLNCAFCYEIKQQAEQWEBHMZHJAHDKYVYQPBJBZSFQDNYHALSUVWESQVVEUIQCMFGJCWAFBIMXBKWOLJPIHVRDYRHUGPINDQRQPSPBWFCIDWIPVXCPZKVHSXHAIKCFOSPEBXIFUXLGLWSMKFXTECWSBSFYZAEGWIVGNPVJWLIUYFHITTUYKDVQOZPNGZLWOZSRJTCTZPUHDSHZFEURBNZTFBKXCDPYRELIAFMUWDIQTYWXGUWZBBHMWSKMQPHJAPDQKKHGTIPJCLMHICCEUVZVAGUITAYRTDVMCAWQFLQQEGZOQXTECGDKICYYGPDIOHJCGDGBEHDBVHECZIWKXVITMAAGKVSEKNJDGOSUNSXNQEBGMFBSITLRPNUJDSLXVHMOMLUXVHCNOJCBBRPVYBZSANEJNJWWNUJLJLPNHFDUWPDMVRJGAZVATNIAWWHLAIYSSFNYRLGSBJVLMSNPSCPEGBAIZDFTFFPNEBIYGVNTZHINICBXBXLBNBALQUTYFZBLMEQYZPREDZDQTHNTMHWAYIAJPFKOAGEQLXCMISSVEARWAPVYMRDCLSLPJOMQQFYQRRMLWTNHVVFXLFNQDIGCPALCHVLHDNZAVOTVMCTBBQNXTWUUCGCEBYVHNRERPMOSLMHGVKVAQHVCLHWPYPSMXEMGBFWNMMXJMJQWSWADGUKIHUUFVRVUIBFUXQIOLAWIXAUMJRGRZEMKCJQSCVYJLRVHIBJWVJOJQIGMJTHARGKDDKVWCNMNPLEYFTQHXBVBFPBAWTPQHNCPQEXVDBMDQWDEVZKJRAFQIYSBSXORTSHXHBESUFCCECHNSTQGDUZPQRBSKQNTPVUAVBXZGHVZCOUCRGCYISGFGYASYNSHJNOIWESMKWTBIANYUAUNRZOSVOFLKVDCGYSEXBRTSQBSERKHMQMPODSCOJAVWAEJHMPTWTGDBLQLBMRJGMEIHMJXEPZMPHEULULBIRVSAJQJYFEVFMFGKKLLYZVHPVOGMRTXYIHYXGJXKOUOIZANVDUCVXBPIZVRAXEBFEJOHSYKEKBIJELPIWEYXKHDVTXKAOYYYRBVAVPSUAOYHIPPWNFJIKJROQSFSZUCGOOFJIEHBZREEUUSZWOLYFPCYHUSMRABJCCDJYMYDCYPZSGPGIAIKZQBYTZFDWYUZQBOESDSDGOYIIHKTVPJNJDBCBOHCIYOPBKOVVKGNAKBDKEEKYIPRPHZOMF

Kode:

import sys

def com_len(a,b):
    for i in range(min(len(a),len(b)),-1,-1):
        if (a[-i:] if i else '')==b[:i]:
            return i

def try_s(a,b,sn,mv):
    v=com_len(a,b)
    if v>mv:
        return a+b[v:],v
    return sn,mv

ws=[w.rstrip() for w in sys.stdin.readlines()]
s=''
while ws:
    mv=-1
    sn=None
    mi=None
    for i in range(len(ws)):
        mvo=mv
        for a in [s,s[::-1]]:
            for b in [ws[i],ws[i][::-1]]:
                sn,mv=try_s(a,b,sn,mv)
        if mvo<mv:
            mi=i
    s=sn
    del ws[mi]
print(s)

randomra
sumber

C, skor 1154

AVOTVMCTBBQNXTWUUCGCEBYVHNRERPMOSLMHGVKVAQHVCLHWPYGOSUNSXNQEBGMFBSITLRPNUJDXJMHIEMGJRMBLQLBDGTWTWVJOJQIGMJTHARYPDCXKBFTZNBRUEFZHSDHUPZTCUZSFSQORJKIJFYNDQFSZOWLZGNPZOQVDKYUTTIHFYUILHWWAINTAVZAGJRVMDPWPQRBEAWVAJOCSDOPMQMHKRESBQSTRBXESYGCDVKLFOVSOYNUAUYNAIBTWKMSEWIONJHSNYSKYVYQPBJBZSOHCIYOPBKOVVKGNAKBDKEEKYIPRPHZOMFGJCWAFBIMXBKWOLJPIHVRDYRHUGPINDQRQPSPBWFCIDWIVPAWRAEVSSIMCXLQEGAOKFPFFTFDZIWLMRRQYFQSXORTSHLUXVHCNOJCBBRPVYBMKSNTPVUAVBXZGHVZCOUCRGCYISGFGYASOZGEQQLFQWACMVDTRYATIAJPVUECCYFSBSWCETXFKMSWLGFUUHIKUGDAWIYXCPZKVHSXHAIKCFOSPEBXIFUXLGLJNHFDUWSWQJMJXWSMXEMGBFWNMMGOVPHVZY
NDUCVXBPIZVRAEBFEJOHSYKEKBIJLPIWEYXKKXITMAGKSEKNJDFMFVEFYJQJASVRILULUEHMZPEUMRGRZKCJQSCVYJRVHIBJUGXWYTDWUFAILERMSUHYCPYLOWZSUERBEIJFOOGQIEVVQEWVUSLAHZTCTJRIABGEPCSNSMLJBSGLRYNFSSYAXHBESUFCCECHNSTQGUZTMHJABJCCDYMYDCYZSGPGIAIKZBYZFDWYUZQBOESDSDGZRCBJLNCAFCYEIQQAQEBHMZJAHDIIHKTVJNDCBNWPPHAUSPVABRYYYOAKXTVDWQDMBDVXCRGKDDKVWCNNPLEYFTQHXBBFPBAWTPQHCPEQMOJLSLCDRMYLABNBLXBXBCNIHZTNVYIBENLXVVHNTVZKJAFISBDLVHMOMCJPITGHKKQDPAJHPQBSQKWIZCEHDHEBDGCJHIDDPYYCKDCETXQZBLMYZPREDZDQTHNMHWYUGVZIWGAZUAXIWALOIQUBIUVRVAZIOUOXJXYHPVAZNDHLCLAPCGDQNBZANJNJWWNUJLPGPVJWLGUZBBHMYPHICQUTYZXTRVIXGKKLL

Gunakan dua baris sehingga kata-kata yang baru ditambahkan dapat menggunakan kembali huruf-huruf dari baris atas.

char l[2][2000];
char s[2][2000];
char w[100][200];
int d[200];
void pri() {
    puts(l[0]);
    puts(l[1]);
}
void sav() { memcpy(s,l,sizeof(l)); }
void res() { memcpy(l,s,sizeof(l)); }
int fit(char *t, int l0, int l1) {
    if (!*t) return 0;
    if (l[0][l0] == *t && (l0 <= l1 || l[1][l1])) return 1+fit(t+1,l0+1,l1+(l1<l0));
    if (l[1][l1] == *t && (l1 <= l0 || l[0][l0])) return 1+fit(t+1,l0+(l0<l1),l1+1);
    if (!l[0][l0]) {
    strcpy(l[0]+l0,t);
    return 0;
    }
    if (!l[0][l1]) {
    strcpy(l[0]+l1,t);
    return 0;
    }
    if (!l[1][l1]) {
    l[1][l1] = *t;
    return fit(t+1,l0+(l0<l1),l1+1);
    }
    return 1000;
}
int main(){
    int j,i,n,best,besti,bestk,c,tot = 0;
    for (i = 0; scanf("%s ",w[i])>0; i+=2) {
    int j = strlen(w[i]);
    for (c = 0; c < j; c++) w[i+1][c] = w[i][j-c-1];
    }
    n = i;
    pri();
    for (j = 0; j < n/2; j++) {
    int k = -1;
    best = -1;
    for (k = 0; k <= strlen(l[1]); k++) {
    for (i = 0; i<n; i++) if (!d[i/2]) {
    sav();
    c = fit(w[i],k,k);
    if (c < 1000 && c >= best) best = c, besti = i, bestk = k;
    res();
    }
    }
    fit(w[besti],bestk,bestk);
    d[besti/2] = 1; tot += best;
    }
    pri();
    printf("%d - %d\n",tot, strlen(l[0])+strlen(l[1]));
    return 0;
}

nutki
sumber

CJam, 1122 1089 surat

qN%{,}$__W%Wf%+:A;s[,mQ)__2#_S*:B;+2/:P;:DX1$W*W]:M;1:L;{BQCelt:B;}:T;
{A,,{B:G;P:H;D:I;L:J;A=:Z{:C;PL+D-:QB=C=
{T}{QD+:QB=C={T}{BPCelt:B;PD+:PL+B=' ={MD#)M=:D;ML#)M=:L;}&}?}?}/BS-,Z,-G:B;H:P;I:D;J:L;}$
0=:KA={:C;PL+D-:QB=C={T}{QD+:QB=C=
{T}{BPCelt:B;PD+:PL+B=' ={MD#)M=:D;ML#)M=:L;}&}?}?}/Beu:B;AKWtK~WtW-:A}g
{PL+B=' -PD-L+B=' -e&}{BP'Zt:B;PD+:P;}w
BM0=/Sf-Oa-N*

Program ini membangun persegi panjang dari pusatnya, berputar ke luar. Sejauh ini, ini adalah pendekatan yang sederhana. Masih ada ruang untuk perbaikan.

Kode ini berantakan besar sekarang. Saya akan membersihkannya ketika saya puas dengan skor saya.

Cobalah online di juru bahasa CJam .

Naik

GXVDBDQDEVGPVJWLWSWQJMJMHCFNQDIGC
UIWESMKWBIANYUANRZOLGLXUFIXBEPSOP
WOPZUDGQTSHCCCUSEBHSKMQHJADKKHGFA
ZNQDKVWCMNPLEYFTQHXBVBPBATPQHNTCL
BJRDOWLZNPZQVDKYUTTIHFYILWADGCIKH
BHBKZXZGHZCOUCGCIGFGYSUGXYQIUPJAV
MSNGSBSMLVJSGLRYNSSIALHWWNTDKQCHL
WYWPRVNDSEBQZUYWFZTYBQZIAIAWIELXD
GSPAJAPSDIOHJDGHDBECZIWKSGVUHQMSN
VTHITUCGAWUUCGEBYVHNERPMZPZMUQHVZ
EIOYCVPONTFOOCUZSSQORJKOBGAFUMDKA
WGUAZTEYVXJYGDVKLFOSFMISJSJIVOPZV
IASWRNGTDNISBCBDJJPVTOJLBZRLRJGCS
IVPHDQBWUQHEOGOSUNNQKZFMPYVEVPYXF
WZVMNKATCBBXHDTROXSEHHTHQCMRULYVQ
DUATISIGVTZBCJSVZFBGIPMGYDPYISCPD
IEVNPBSDXCERINHKTYSMIRHVYMWDBLIYN
FCBHGRXLBMETYKDJQUIFKPJKDJGCFCKHA
WCRTUAVQPVUSOEURAFQBXIEVHDFXUDGYL
BQYQHTHLITUQPSNPLTISVYAQACMKQRCXS
PFYDRJMBZOZSBVKGAAMTIKWHJCFBIMEGU
SQYZYGOMRVWEKOVNKBDKEEVCHJVFOYTJV
PROEDILJXAORHMQMPOSCOJALZBETLVXKW
QRAPRQUGECLYFPCYHUMRYPWHMAFZAPQOE
WMKZVJXMFBJNCAFEIKQQAEQEBHYNWROUS
ULXYHOVIEJOHSYKKBJELPIWYXKJBIAZIQ
DWTQIJCHMXEPZMPHEULUBRVSAJQRXEGAV
FNVEPVNOJCBBRPVYBTZPHDSHZFEUAVQGV
PHDMJWJBIHVRLJYCSQJCKMEZRGRJMSQKE
LVMBLOKXMBFAWCGFMCPFOAGQLXCMISLKU
JVNZGEAZYFSBSETXKSWLGTYRTDVAWQFLI
WFWFBMXMSPYZANJNJWNUJLJXMGOPHVZYQ
PXLLANBLXBXBCIIHZTVGYIBENPFFTFDIC

Dennis
sumber

Python 3, skor = 1014

Mulai dari area berukuran nol, kami menambahkan kata-kata huruf demi huruf ke area sedemikian rupa sehingga area tersebut akan selalu berbentuk spiral persegi panjang:

Kami menyimpan 10 kandidat dewan selama penghitungan. Pada setiap langkah untuk setiap kandidat kami mencoba untuk menambahkan setiap kata yang telah ditinggalkan dewan dalam setiap cara hukum yang mungkin menjaga tata letak spiral. Kami menilai setiap papan baru yang dihasilkan berdasarkan total used word length / total area usedfraksi. Kami menyimpan 10 papan terbaik dan mengulangi langkahnya hingga tidak ada kata yang tersisa.

Untuk meminimalkan ruang yang tidak digunakan pada akhir spiral, kami mencoba mengambil beberapa langkah di depan sebelum berputar untuk membuat spiral non-persegi. Misalnya:

98765
.1234
..

Daftar kata diberikan di stdin. Kode (cukup jelek) membutuhkan waktu sekitar 30 menit pada laptop saya yang lambat. (Jika Anda ingin menunggu lebih sedikit, Anda dapat memilih nonspiral_length=13daripada mengulangi nilai yang mungkin.)

Papan yang dihasilkan:

JFOOGCUZSFSQORKIJFYGDSDSEOQZUYWDFZTYBQZ
ISDHUZTIIHKTJNJDBCBOHIYOPBKVVGNAKBDKEEK
EHOJPSLCDRMYVPAWESSIMCLQEGAOKFPJLCAFCKI
BZMFYLPNMNKDKGRAVMCTBBXTWUUCGCBYHNREYPA
RFQTXESYGCDVKLFOVSSFQNYHALSVWESQVEQRIRI
EELQBZNGZLWOZSRJTCTZWDGUIHUUFVRVUICPKPG
UUAHROPSCPGBAVXCPZVHXAIKCOSPBXIFUBTMQHG
SRBXTQNSXYEIPLJIBKKYSHOJEFBEXRIPXFAOQZS
WZNBSVMAHKWZCEHVDHEGDGHIDTIGAVZBLQYSAOZ
OTLVQDLYXMTIVXKBYVRBCJONHVXULMVXGIRLEMP
LFXFBKVGHAFBGEXMSPSPBWFCIDWIMOUCLOTMQFY
YKBPSYJFBAWNTMRRQYNQDIGPALCHXLEDTADHWTC
FDXBEUBGEGMHJWLSMKFXTECBSFYVDSCVXWVGEWD
HPCARTLSSKMVVGUWZBBHMWSGEAZLBJCNKIMKBTY
UYIWKTRIUVZFPNQTYFXJJQWIVNDHMLPAOXCVHGM
SRNTHINYFSKXLFYIHXGKOUOZAEWQDJNIYAWAMDY
MEIPMHFGCEJRASBSXORTSHBSJNJWNUHTYUQHZBJ
XLZHQYSRCKNDGOUNNQEBGMFITLRPUDFGYXFVJLD
XITNMNSUECHSTQGDUZPSKQPHJAPDQKKHRTLCAQC
XAVCPHYOCZVGZXBVAVTNQNWPYOUSPVAVBMQHDLC
XFGQOJIALHWWAINTAGJRVMDGKKLLYZHPOGQWKBJ
XMYEDNOWESMKTBAYUUNZOSYYCIDGCETXQZEPYMA
XUICSCJAVJHPJAIWHMTHTQDZDERPZYQEMLBYVRA
XWBMFGWFBIMXBKWOLJPIVRYRHUGINDRSZBJPQJH
XDENPFTDZGFFVEFYJQASIBLULPMZPEXJMHIEMGT
XIQTYWXGUMJRGRZEMKCJQSCVYJLRVHIBWVJOJQI

Kode penghasil:

import sys

class b:
    def __init__(s,l,ws):
        s.d=[' ']*(l*l)
        s.x,s.y=l//2,l//2
        s.l=l
        s.dir=1j
        s.ws=ws[:]
        # last char pos, remaining word part, used positions
        s.wx,s.wy,s.wp,s.wu=None,None,None,None

    def copy(s):
        #print('copy',s.x,s.y,s.wp)
        c=b(s.l,s.ws)
        c.d=s.d[:]
        c.x,c.y=s.x,s.y
        c.dir=s.dir*1
        c.wx,c.wy=s.wx,s.wy
        c.wp=s.wp[:] if s.wp!=None else None
        c.wu=s.wu[:] if s.wu!=None else None
        return c#copy.deepcopy(s) is very slow

    def score(s):
        placed_chars=allwlen-sum([len(w) for w in s.ws])
        used_cells=0
        for i in range(s.l):
            for j in range(s.l):
                if s.d[i*s.l+j]!=' ':
                    used_cells+=1
        return placed_chars/used_cells

    def get_next_bs(s):
        bl=[]
        for wi in range(len(s.ws)):
            bl+=s.get_b_for_w(wi)
        return bl

    def get_b_for_w(s,wi):
        w=s.ws[wi]        
        bl=[]
        for i in range(1,s.l-1,3):
            for j in range(1,s.l-1,3):
                for reversed in True,False:
                    if abs(i-s.x)+abs(j-s.y)>5:
                        continue
                    bn=s.copy()
                    bn.wx,bn.wy=i,j
                    bn.wp=w if not reversed else w[::-1]
                    del bn.ws[wi]
                    bn.wu=[]
                    bnr=bn.get_bs_for_wp()
                    bl+=bnr        
        # only use the best for a given word
        best_b=max(bl,key=lambda b:b.score())
        return [best_b]

    def get_bs_for_wp(s):
        if len(s.wp)==0:
            return [s]
        bl=[]
        for ir in -1,0,1:
            for jr in -1,0,1:
                i=s.wx+ir
                j=s.wy+jr
                if (i,j) not in s.wu and (s.d[i*s.l+j]==s.wp[0] or (i==s.x and j==s.y)):
                    bn=s.copy()
                    assert bn.d[i*bn.l+j] in (bn.wp[0],' ')
                    #add/owerwrite char
                    bn.d[i*bn.l+j]=bn.wp[0]
                    bn.wp=bn.wp[1:]
                    bn.wu+=[(i,j)]
                    bn.wx,bn.wy=i,j
                    if (i==bn.x and j==bn.y):              
                        spiraling=not (bn.x==bn.l//2 and bn.l//2+nonspiral_length>bn.y>=bn.l//2 )
                        #turn
                        nd=bn.dir*1j
                        if bn.d[int(bn.x+nd.real)*bn.l+int(bn.y+nd.imag)]==' ' and spiraling:
                            bn.dir=nd
                        #move
                        bn.x+=bn.dir.real
                        bn.y+=bn.dir.imag

                    #add bs from new state
                    bl+=bn.get_bs_for_wp()
        return bl        

    def __repr__(s):
        #borders
        x1,x2,y1,y2=s.l,0,s.l,0
        for i in range(s.l):
            for j in range(s.l):
                if s.d[i*s.l+j]!=' ':
                    x1=min(i,x1)
                    x2=max(i,x2)
                    y1=min(j,y1)
                    y2=max(j,y2)
        r=''
        for i in range(x1,x2+1):
            for j in range(y1,y2+1):
                r+=s.d[i*s.l+j] if s.d[i*s.l+j]!=' ' else 'X'
            r+='\n'
        return r

progress_info=False # toggle to print progress info

allws=[w.rstrip() for w in sys.stdin.readlines()]
allws=allws[:]
allwlen=sum([len(w) for w in allws])
max_nonspiral_length=16
best_score=allwlen*2+1 # maxint
best_b=None

for nonspiral_length in range(1,max_nonspiral_length+1,3):

    length=int(allwlen**0.5)+nonspiral_length*2+5 #size with generous padding

    bl=[b(length,allws)]

    for wc in range(len(allws)):
        bln=[]
        for be in bl:
            bln+=be.get_next_bs()

        bln.sort(key=lambda b:b.score(),reverse=True)
        bl=bln[:10]
        if progress_info:
            print(wc,end=' ')
            sys.stdout.flush()
        #print(bl[0].score(),wc)

    real_score=len(repr(bl[0]))-repr(bl[0]).count('\n')
    #print(bl[0])
    if progress_info:
        print()
        print(nonspiral_length,'score =',real_score)

    if real_score<best_score:
        best_b=bl[0]
        best_score=real_score

if progress_info:
    print()
print(best_b)
if progress_info:
    print('score =',best_score)

randomra
sumber