When working on Non-Palindromic Polyglot Boggle, I found it quite tedious to pack the codes as efficiently as possible onto the Boggle board, even with only two strings. But we're programmers, right? We know how to automate things.
Given a list of strings, you're to generate a Boggle board on which each of those strings can be found (independently of the others). The challenge is to make the Boggle board as small as possible. As this is (hopefully) a rather difficult task, this is a code-challenge: there is no requirement for optimality - the challenge is to do it as well as you can.
Rules
- The Boggle board will be rectangular and contain only upper case letters. Therefore, the input strings will also contain only upper case letters.
- The usual Boggle rules apply: a string is part of the board if, starting anywhere, you can find the string by repeatedly moving to adjacent characters (horizontally, vertically, or diagonally). To form a single string, you cannot use any cell of the board more than once. However, characters may be reused between different strings.
- You've got 30 minutes to process the test data, and your code must not use more than 4 GB of memory. I will give a little bit of leeway on the memory limit, but if your program consistently uses more than 4 GB or spikes significantly above it, I will (temporarily) disqualify it.
- I will test all submissions on my own machine, which is running Windows 8. I do have a Ubuntu VM, but if I have to test on that you won't be able to make as much use of the 30 minutes as otherwise. Please include a link to a free interpreter/compiler for your chosen language, as well as instructions on how to compile/run your code.
- Your score will be the size of the Boggle board for the test data below (not counting the newlines). In the case of a tie (e.g. because multiple people managed to produce an optimal solution), the winner will be the submission that produces this optimal solution faster.
- You must not optimise your code specifically towards the test data. If I suspect anyone of doing so, I reserve the right to generate new test data.
Example
Given the strings
FOO
BAR
BOOM
Once could trivially put them in a 4x3 Boggle board:
FOOX
BARX
BOOM
By making use of the fact that strings don't have to be straight, we can compress it to 5x2:
BORFO
OMABO
But we can make it even smaller by reusing characters between different strings, and fit the strings in 4x2:
FOOM
BARX
Now the B is used for both BOOM and BAR, and the OO is used for both BOOM and FOO.
Test Data
Your submission will be tested on the following 50 strings. For testing purposes you can simply use smaller subsets of this data which should then run more quickly. I believe that the absolute lower bound for this test data is a board with 120 characters, although this is not necessarily achievable.
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
Verifier
You can use the following Stack Snippet to verify whether a Boggle board contains all strings in a given list. I ported the Boggle search code from edc65's answer over here. Let me know if anything seems buggy.
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>
