Boggle Board Compression

Работая над непалиндромной полиглотой Boggle , я счел весьма утомительным максимально эффективно упаковывать коды на доску Boggle, даже используя только две строки. Но мы программисты, верно? Мы знаем, как автоматизировать вещи.

Имея список строк, вы должны создать доску Boggle, на которой можно найти каждую из этих строк (независимо от других). Задача состоит в том, чтобы сделать доску Boggle как можно меньше. Поскольку это (надеюсь) довольно сложная задача, это сложная задача для кода : требования к оптимальности не требуются - задача состоит в том, чтобы сделать это как можно лучше.

правила

Доска Boggle будет прямоугольной и содержать только заглавные буквы. Поэтому входные строки также будут содержать только заглавные буквы.
Применяются обычные правила Boggle: строка является частью доски, если, начиная с любого места, вы можете найти строку, многократно перемещаясь к смежным символам (по горизонтали, вертикали или диагонали). Чтобы сформировать одну строку, вы не можете использовать любую ячейку доски более одного раза. Однако символы могут быть повторно использованы в разных строках.
У вас есть 30 минут для обработки тестовых данных, и ваш код не должен использовать более 4 ГБ памяти. Я немного расскажу об ограничении памяти, но если ваша программа постоянно использует более 4 ГБ или резко превышает ее, я (временно) дисквалифицирую ее.
Я протестирую все заявки на своем компьютере под управлением Windows 8. У меня есть виртуальная машина Ubuntu, но если мне придется протестировать ее, вы не сможете использовать эти 30 минут так же часто, как иначе. Пожалуйста, включите ссылку на бесплатный переводчик / компилятор для выбранного вами языка, а также инструкции о том, как скомпилировать / запустить ваш код.
Ваша оценка будет равна размеру доски Boggle для данных теста ниже (не считая перевода строки). В случае ничьей (например, из-за того, что нескольким людям удалось найти оптимальное решение), победителем будет представление, которое даст это оптимальное решение быстрее.
Вы не должны оптимизировать свой код специально для тестовых данных. Если я подозреваю кого-либо в этом, я оставляю за собой право создавать новые тестовые данные.

пример

Учитывая строки

FOO
BAR
BOOM

Однажды можно было просто положить их на доску 4x3 Boggle:

FOOX
BARX
BOOM

Используя тот факт, что строки не обязательно должны быть прямыми, мы можем сжать их до 5x2:

BORFO
OMABO

Но мы можем сделать его еще меньше, повторно используя символы между различными строками и поместив строки в 4x2:

FOOM
BARX

Теперь Bиспользуется для обоих BOOMи BAR, и OOиспользуется для обоих BOOMи FOO.

Тестовые данные

Ваша заявка будет проверена на следующих 50 строк. Для целей тестирования вы можете просто использовать меньшие подмножества этих данных, которые затем должны выполняться быстрее. Я считаю, что абсолютной нижней границей для этих тестовых данных является доска с 120 символами, хотя это не обязательно достижимо.

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

контрольник

Вы можете использовать следующий фрагмент стека, чтобы проверить, содержит ли доска Boggle все строки в данном списке. Я перенес код поиска Boggle из ответа edc65 здесь . Дайте мне знать, если что-то кажется глючным.

Показать фрагмент кода

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>

Развернуть фрагмент

code-challenge compression boggle Мартин Эндер
источник

Ответы:

С ++ 11, оценка = 992 1024

Алгоритм действительно глуп, но до сих пор никто не сделал серьезного, поэтому я выложу его. Он более или менее случайно помещает слова на квадратную доску, а затем начинает заново, если ему не удается подобрать их. Это своего рода попытка максимизировать совпадение с существующими словами, но на самом деле неэффективно.

Изменить: Улучшен счет, добавив 1 к длине стороны и попробовав прямоугольник после неудачного 50 раз. Также сортируются входные строки по размеру вместо рандомизации порядка.

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

Доска:

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
источник

Python 3, оценка = 1225

В этом решении мы используем только 1 строку. Начиная с пустой строки на каждом шаге мы добавляем слово, которое гарантирует максимально возможное перекрытие. (Слова проверяются во всех 4 возможных направлениях.)

Это дает 1225 баллов, что на 50 баллов меньше, чем 1275 баллов за объединение всех слов без наложения друг на друга.

Результат:

CBJLNCAFCYEIKQQAEQWEBHMZHJAHDKYVYQPBJBZSFQDNYHALSUVWESQVVEUIQCMFGJCWAFBIMXBKWOLJPIHVRDYRHUGPINDQRQPSPBWFCIDWIPVXCPZKVHSXHAIKCFOSPEBXIFUXLGLWSMKFXTECWSBSFYZAEGWIVGNPVJWLIUYFHITTUYKDVQOZPNGZLWOZSRJTCTZPUHDSHZFEURBNZTFBKXCDPYRELIAFMUWDIQTYWXGUWZBBHMWSKMQPHJAPDQKKHGTIPJCLMHICCEUVZVAGUITAYRTDVMCAWQFLQQEGZOQXTECGDKICYYGPDIOHJCGDGBEHDBVHECZIWKXVITMAAGKVSEKNJDGOSUNSXNQEBGMFBSITLRPNUJDSLXVHMOMLUXVHCNOJCBBRPVYBZSANEJNJWWNUJLJLPNHFDUWPDMVRJGAZVATNIAWWHLAIYSSFNYRLGSBJVLMSNPSCPEGBAIZDFTFFPNEBIYGVNTZHINICBXBXLBNBALQUTYFZBLMEQYZPREDZDQTHNTMHWAYIAJPFKOAGEQLXCMISSVEARWAPVYMRDCLSLPJOMQQFYQRRMLWTNHVVFXLFNQDIGCPALCHVLHDNZAVOTVMCTBBQNXTWUUCGCEBYVHNRERPMOSLMHGVKVAQHVCLHWPYPSMXEMGBFWNMMXJMJQWSWADGUKIHUUFVRVUIBFUXQIOLAWIXAUMJRGRZEMKCJQSCVYJLRVHIBJWVJOJQIGMJTHARGKDDKVWCNMNPLEYFTQHXBVBFPBAWTPQHNCPQEXVDBMDQWDEVZKJRAFQIYSBSXORTSHXHBESUFCCECHNSTQGDUZPQRBSKQNTPVUAVBXZGHVZCOUCRGCYISGFGYASYNSHJNOIWESMKWTBIANYUAUNRZOSVOFLKVDCGYSEXBRTSQBSERKHMQMPODSCOJAVWAEJHMPTWTGDBLQLBMRJGMEIHMJXEPZMPHEULULBIRVSAJQJYFEVFMFGKKLLYZVHPVOGMRTXYIHYXGJXKOUOIZANVDUCVXBPIZVRAXEBFEJOHSYKEKBIJELPIWEYXKHDVTXKAOYYYRBVAVPSUAOYHIPPWNFJIKJROQSFSZUCGOOFJIEHBZREEUUSZWOLYFPCYHUSMRABJCCDJYMYDCYPZSGPGIAIKZQBYTZFDWYUZQBOESDSDGOYIIHKTVPJNJDBCBOHCIYOPBKOVVKGNAKBDKEEKYIPRPHZOMF

Код:

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
источник

С, оценка 1154

AVOTVMCTBBQNXTWUUCGCEBYVHNRERPMOSLMHGVKVAQHVCLHWPYGOSUNSXNQEBGMFBSITLRPNUJDXJMHIEMGJRMBLQLBDGTWTWVJOJQIGMJTHARYPDCXKBFTZNBRUEFZHSDHUPZTCUZSFSQORJKIJFYNDQFSZOWLZGNPZOQVDKYUTTIHFYUILHWWAINTAVZAGJRVMDPWPQRBEAWVAJOCSDOPMQMHKRESBQSTRBXESYGCDVKLFOVSOYNUAUYNAIBTWKMSEWIONJHSNYSKYVYQPBJBZSOHCIYOPBKOVVKGNAKBDKEEKYIPRPHZOMFGJCWAFBIMXBKWOLJPIHVRDYRHUGPINDQRQPSPBWFCIDWIVPAWRAEVSSIMCXLQEGAOKFPFFTFDZIWLMRRQYFQSXORTSHLUXVHCNOJCBBRPVYBMKSNTPVUAVBXZGHVZCOUCRGCYISGFGYASOZGEQQLFQWACMVDTRYATIAJPVUECCYFSBSWCETXFKMSWLGFUUHIKUGDAWIYXCPZKVHSXHAIKCFOSPEBXIFUXLGLJNHFDUWSWQJMJXWSMXEMGBFWNMMGOVPHVZY
NDUCVXBPIZVRAEBFEJOHSYKEKBIJLPIWEYXKKXITMAGKSEKNJDFMFVEFYJQJASVRILULUEHMZPEUMRGRZKCJQSCVYJRVHIBJUGXWYTDWUFAILERMSUHYCPYLOWZSUERBEIJFOOGQIEVVQEWVUSLAHZTCTJRIABGEPCSNSMLJBSGLRYNFSSYAXHBESUFCCECHNSTQGUZTMHJABJCCDYMYDCYZSGPGIAIKZBYZFDWYUZQBOESDSDGZRCBJLNCAFCYEIQQAQEBHMZJAHDIIHKTVJNDCBNWPPHAUSPVABRYYYOAKXTVDWQDMBDVXCRGKDDKVWCNNPLEYFTQHXBBFPBAWTPQHCPEQMOJLSLCDRMYLABNBLXBXBCNIHZTNVYIBENLXVVHNTVZKJAFISBDLVHMOMCJPITGHKKQDPAJHPQBSQKWIZCEHDHEBDGCJHIDDPYYCKDCETXQZBLMYZPREDZDQTHNMHWYUGVZIWGAZUAXIWALOIQUBIUVRVAZIOUOXJXYHPVAZNDHLCLAPCGDQNBZANJNJWWNUJLPGPVJWLGUZBBHMYPHICQUTYZXTRVIXGKKLL

Используйте две строки, чтобы вновь добавленные слова могли повторно использовать буквы из верхней строки.

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
источник

CJam, 1122 1089 букв

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*

Программа строит прямоугольник из его центра, спирально наружу. Пока это довольно простой подход. Есть еще возможности для улучшения.

Код сейчас большой беспорядок. Я уберу это, когда я буду доволен своим счетом.

Попробуйте онлайн в интерпретаторе CJam .

доска

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

Деннис
источник

Python 3, оценка = 1014

Начиная с области нулевого размера, мы добавляем слова по буквам в область таким образом, что область всегда будет прямоугольной спиралью:

Мы сохраняем 10 кандидатов в советы на протяжении всего расчета. На каждом шаге к каждому кандидату мы стараемся добавлять каждое слово, оставленное доской, всеми возможными законными способами, сохраняя спираль. Мы оцениваем каждую из полученных новых досок на основе total used word length / total area usedдоли. Мы сохраняем 10 лучших досок и повторяем шаг, пока не осталось слов.

Чтобы минимизировать неиспользуемое пространство в конце спирали, мы стараемся сделать несколько шагов вперед, прежде чем закручивать спирали, чтобы создать неквадратные спирали. Например:

98765
.1234
..

Список слов дан в стандартном вводе. (Довольно некрасивый) код занимает около 30 минут на моем медленном ноутбуке. (Если вы хотите меньше ждать, вы можете выбрать, nonspiral_length=13а не перебирать возможные значения.)

Полученная доска:

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

Генерирующий код:

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
источник