![\"\"](\"https:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/boggle.png\")
<\/a><\/div>\nBetter late than never? This was a blog post I started to write during COVID-19 and now I’ve finally gotten around to finishing it.<\/p>\n
In the 2019 APL Problem Solving Competition<\/a>, we presented a problem to solve the Boggle game<\/a>\u00a0. In Boggle, a player tries to make as many words as possible from contiguous letters in a 4\u00d74 grid, with the stipulation that you cannot reuse a position on the board.<\/p>\n Rich Park’s webinar from 17 October 2019<\/a> presents, among other things, a very good discussion and comparison of two interesting solutions submitted by Rasmus Pr\u00e9centh and Torsten Grust. As part of that discussion, Rich explores the performance of their solutions.\u00a0After seeing that webinar, I was curious about how my solution might perform.<\/p>\n Please take note that performance was not mentioned as one of the criteria for this problem other than the implicit expectation that code completes in a reasonable amount of time. As such, this post is in no way intended to criticize anyone’s solutions \u2013 in fact, in many cases I’m impressed by the elegance of the solutions and their application of array-oriented thinking. I have no doubt that had we made performance a primary judging criterion, people would have taken it into consideration and possibly produced somewhat different code.<\/p>\n I started writing APL in 1975 at the age of 14 and “grew up” in the days of mainframe APL when CPU cycles and memory were precious commodities. This made me develop an eye towards writing efficient code. In developing my solution and writing this post, I had a few goals in mind:<\/p>\n The task was to write a function called where:<\/p>\n Although the actual Boggle game uses only words of 3 letters or more, for this problem we permit words of 2 or more letters.<\/p>\n Here’s an example of a 2\u00d72 board:<\/p>\n First, let’s define some variables that we’ll use in our exploration:<\/p>\n If you’re using Dyalog v20.0 or later, you can represent this using array notation<\/a><\/em>:<\/p>\n The representation does not affect the performance or the result:<\/p>\n There were 9 correct solutions submitted for this problem. We’ll call them To make it easier to run timings, I wrote a simple function to call This allows me to compare any 2 or more solutions, or by default, all solutions on a given board variable name.<\/p>\n If we try to run on the 6\u00d76 sample<\/p>\n Why is Intuitively, this felt like an iterative problem. A mostly-array-oriented solution might be to generate character vectors made up from the contents of all paths in I decided to use two parallel structures to keep track of progress:<\/p>\n First, I need to find the adjacent cells for each cell in You might recognize line I wrote a helper function A contributor to improved performance is set up next. I created a parallel transposed matrix copy of Why create another version of Smaller searches are generally faster than larger ones. If we pare down For board Append any Because a cell can have more than one letter, we might have stubs of different lengths, so we need to iterate over each unique length:<\/p>\n Because we’re doing prefix searching, the inner product We then use our two Boolean arrays, As an experiment, I decided to write a version, Interestingly, There are a couple of other optimizations I could have implemented:<\/p>\n When thinking about performance and optimization:<\/p>\n In case you were wondering, the two solutions Rich Park looked at in his webinar were If you’re curious to look at the code for the submissions, this .zip<\/strong>\u00a0file<\/a>\u00a0includes namespaces You can then examine the code, run your own timings, and so on. One interesting thing to explore is which submissions properly handle 1\u00d71 and 0\u00d70 boards.<\/p>\n When I started to write the explanation of my code, it occurred to me: “This is 2026 and we have LLMs that might be able to explain the code. Let’s give them a try…”<\/p>\n So, I asked each of Anthropic’s Claude Opus 4.6 Extended, Google’s Gemini Pro, and Microsoft’s Copilot Think Deeper the following:<\/p>\n Explain the attached code. Note that a cell in board can have multiple letters like “qu” or “ough”. Also note that the words list is the official scrabble words list and has no single letter words.<\/p>\n The results were interesting and, in several places, a more concise and coherent explanation than I might produce. But how accurate and useful were their explanations? Stay tuned for a blog post about how well different LLMs explain APL code!<\/p>\n","protected":false},"excerpt":{"rendered":" Or is it Minding Boggle Performance? Better late than never? This was a blog post I started to write during COVID-19 and now I’ve finally gotten around to finishing it. In the 2019 APL Problem Solving Competition, we presented a … Continue reading Disclaimer<\/h4>\n
Goals<\/h4>\n
\n
\nFindWords<\/code> that has the syntax:<\/p>\n found\u2190words FindWords board<\/pre>\n
\n
words<\/code> is a vector of words. We used Collins Scrabble Words<\/a>, a \u2248280,000-word word list used by tournament Scrabble\u2122 players. We store this in a variable called AllWords<\/code>. Note that single letter words like “a” and “I” are not legitimate Scrabble words.<\/li>\nboard<\/code> is a matrix where each cell contains one or more letters. A standard Boggle board is 4\u00d74.<\/li>\nfound<\/code> is a vector that is a subset of words<\/code> containing the words that can be made from board<\/code> without revisiting any cells.<\/li>\n<\/ul>\n AllWords FindWords \u2395\u2190 b2\u2190 2 2\u2374'th' 'r' 'ou' 'gh'\r\n\u250c\u2500\u2500\u252c\u2500\u2500\u2510\r\n\u2502th\u2502r \u2502\r\n\u251c\u2500\u2500\u253c\u2500\u2500\u2524\r\n\u2502ou\u2502gh\u2502\r\n\u2514\u2500\u2500\u2534\u2500\u2500\u2518\r\n\u250c\u2500\u2500\u252c\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2510\r\n\u2502ou\u2502our\u2502thou\u2502rough\u2502routh\u2502though\u2502through\u2502\r\n\u2514\u2500\u2500\u2534\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2518\r\n<\/pre>\n
b4\u2190 4 4\u2374 't' 'p' 'qu' 'a' 's' 'l' 'g' 'i' 'r' 'u' 't' 'e' 'i' 'i' 'n' 'a' \u235d 4\u00d74 board\r\n b6\u2190 6 6\u2374'jbcdcmvueglxriybgeiganuylvonxkfeoqld' \u235d 6\u00d76 board\r\n<\/code><\/pre>\n\u235d using array notation with single-line input:\r\n b4\u2190['t' 'p' 'qu' 'a' \u22c4 's' 'l' 'g' 'i' \u22c4 'r' 'u' 't' 'e' \u22c4 'i' 'i' 'n' 'a']\r\n b6\u2190['jbcdcm' \u22c4 'vueglx' \u22c4 'riybge' \u22c4 'iganuy' \u22c4 'lvonxk' \u22c4 'feoqld']\r\n\r\n\u235d or, using array notation with multi-line input:\r\n b4\u2190['t' 'p' 'qu' 'a'\r\n 'slgi'\r\n 'rute'\r\n 'iina']\r\n\r\n b6\u2190['jbcdcm'\r\n 'vueglx'\r\n 'riybge'\r\n 'iganuy'\r\n 'lvonxk'\r\n 'feoqld']\r\n<\/code><\/pre>\n b4 b6\r\n\u250c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u2500\u2510\r\n\u2502\u250c\u2500\u252c\u2500\u252c\u2500\u2500\u252c\u2500\u2510\u2502jbcdcm\u2502\r\n\u2502\u2502t\u2502p\u2502qu\u2502a\u2502\u2502vueglx\u2502\r\n\u2502\u251c\u2500\u253c\u2500\u253c\u2500\u2500\u253c\u2500\u2524\u2502riybge\u2502\r\n\u2502\u2502s\u2502l\u2502g \u2502i\u2502\u2502iganuy\u2502\r\n\u2502\u251c\u2500\u253c\u2500\u253c\u2500\u2500\u253c\u2500\u2524\u2502lvonxk\u2502\r\n\u2502\u2502r\u2502u\u2502t \u2502e\u2502\u2502feoqld\u2502\r\n\u2502\u251c\u2500\u253c\u2500\u253c\u2500\u2500\u253c\u2500\u2524\u2502 \u2502\r\n\u2502\u2502i\u2502i\u2502n \u2502a\u2502\u2502 \u2502\r\n\u2502\u2514\u2500\u2534\u2500\u2534\u2500\u2500\u2534\u2500\u2518\u2502 \u2502\r\n\u2514\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2500\u2518\r\n<\/code><\/pre>\nf1<\/code> through f9<\/code>\u00a0\u2013 my solution is f0<\/code>. Now let’s run some comparative timings using cmpx<\/code> from the dfns workspace. cmpx<\/code> will note whether the result of any of the latter expressions returns a different result from the first expression. We take the tally (\u2262<\/code>) of the resulting word lists to make sure the expressions all return the same result. We assume that the sets of words are the same if the counts are the same. These timings were done using Dyalog v20.0 with a maximum workspace (MAXWS<\/code>) of 1GB running under Windows 11 Pro. To keep the expressions brief I bound AllWords<\/code> as the left argument to each of the solution functions:<\/p>\n f0\u2190\u2262AllWords\u2218#.Brian.Problems.FindWords<\/code><\/pre>\ncmpx<\/code> with the solutions of my choosing (the default is all solutions).<\/p>\n )copy dfns cmpx\r\n time\u2190{\u237a\u2190\u00af1+\u237310 \u22c4 cmpx('f',\u2355,' ',\u2375\u2368)\u00a8\u237a}<\/code><\/pre>\n time 'b4' \u235d try a \"standard\" 4\u00d74 Boggle board\r\n f0 b4 \u2192 1.2E\u00af2 | 0%\r\n f1 b4 \u2192 2.3E\u00af1 | +1791% \u2395\u2395\r\n f2 b4 \u2192 4.3E\u00af1 | +3491% \u2395\u2395\u2395\r\n f3 b4 \u2192 7.3E\u00af1 | +5941% \u2395\u2395\u2395\u2395\u2395 \r\n f4 b4 \u2192 5.6E0 | +46600% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395 \r\n f5 b4 \u2192 1.1E0 | +8758% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395 \r\n f6 b4 \u2192 8.9E\u00af1 | +7325% \u2395\u2395\u2395\u2395\u2395\u2395 \r\n f7 b4 \u2192 1.1E0 | +9275% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395 \r\n f8 b4 \u2192 4.2E0 | +34750% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395 \r\n f9 b4 \u2192 2.0E0 | +16291% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395 \r\n<\/code><\/pre>\n 0 1 2 3 4 5 6 7 9 time'b6'\r\n f0 b6 \u2192 2.2E\u00af2 | 0% \r\n f1 b6 \u2192 3.7E\u00af1 | +1577% \r\n f2 b6 \u2192 1.0E0 | +4581% \r\n f3 b6 \u2192 1.5E0 | +6872% \r\n f4 b6 \u2192 1.6E2 | +705950% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395 \r\n f5 b6 \u2192 2.3E0 | +10409% \u2395 \r\n f6 b6 \u2192 1.9E0 | +8463% \r\n f7 b6 \u2192 2.0E0 | +9131% \u2395\r\n f9 b6 \u2192 2.4E0 | +10822% \u2395\r\n<\/code><\/pre>\nf8<\/code> is excluded as it would cause a WS FULL<\/code> in my 1GB workspace.<\/p>\nf0<\/code> about 16-18 times faster than the next fastest solution, f1<\/code>? I didn’t set out to make FindWords<\/code> fast, it just turned out that way. Let’s take a look at the code…<\/p>\n \u2207 r\u2190words FindWords board;inds;neighbors;paths;stubs;nextcells;mwords;mask;next;found;lens;n;m;map\r\n[1] inds\u2190\u2373\u2374board \u235d board indices\r\n[2] neighbors\u2190(,inds)\u2218\u2229\u00a8\u2193inds\u2218.+(,\u00af2+\u23733 3)~\u22820 0 \u235d matrix of neighbors for each cell\r\n[3] paths\u2190\u2282\u00a8,inds \u235d initial paths\r\n[4] stubs\u2190,\u00a8,board \u235d initial stubs of words\r\n[5] nextcells\u2190neighbors\u2218{\u2282\u00a8(\u2283\u237a[\u00af1\u2191\u2375])~\u2375} \u235d append unused neighbors to path\r\n[6] mwords\u2190\u2349\u2191words \u235d matrix of candidate words, use a columnar matrix for faster \u2227.=\r\n[7] mask\u2190mwords[1;]\u220a\u2283\u00a8,board \u235d mark only those beginning with a letter on the board\r\n[8] mask\u2190mask\\\u2227\u233f(mask\/mwords)\u220a' ',\u220aboard \u235d further mark only words containing only letters found on the board\r\n[9] words\/\u2368\u2190mask \u235d keep those words\r\n[10] mwords\/\u2368\u2190mask \u235d keep them in the matrix form as well\r\n[11] r\u2190words\u2229stubs \u235d seed result with any words that may already be formed from single cell\r\n[12] :While (0\u220a\u2374paths)\u23710\u220a\u2374words \u235d while we have both paths to follow and words to look at\r\n[13] next\u2190nextcells\u00a8paths \u235d get the next cells for each path\r\n[14] paths\u2190\u2283,\/(\u2282\u00a8paths),\u00a8\u00a8next \u235d append the next cells to each path\r\n[15] stubs\u2190\u2283,\/stubs{\u237a\u2218,\u00a8board[\u2375]}\u00a8next \u235d append the next letters to each stub\r\n[16] r,\u2190words\u2229stubs \u235d add any matching words\r\n[17] mask\u2190(\u2262words)\u23740 \u235d build a mask to remove word beginnings that don't match any stubs\r\n[18] found\u2190(\u2262stubs)\u23740 \u235d build a mask to remove stubs that no words begin with\r\n[19] lens\u2190\u2262\u00a8stubs \u235d length of each stub\r\n[20] :For n :In \u222alens \u235d for each unique stub length\r\n[21] m\u2190n=lens \u235d mark stubs of this length\r\n[22] map\u2190(\u2191m\/stubs)\u2227.=n\u2191mwords \u235d map which stubs match which word beginnings\r\n[23] mask\u2228\u2190\u2228\u233fmap \u235d words that match\r\n[24] found[(\u2228\/map)\/\u2378m]\u21901 \u235d stubs that match\r\n[25] :EndFor\r\n[26] paths\/\u2368\u2190found \u235d keep paths that match\r\n[27] stubs\/\u2368\u2190found \u235d keep stubs that match\r\n[28] words\/\u2368\u2190mask \u235d keep words that may yet match\r\n[29] mwords\/\u2368\u2190mask \u235d keep matrix words that may yet match\r\n[30] :EndWhile\r\n[31] r\u2190\u222ar\r\n \u2207\r\n<\/code><\/pre>\nAttacking the Problem<\/h2>\n
board<\/code> and then do a set intersection with words<\/code>. But that would be horrifically inefficient \u2013 there are over 12-million paths in a 4\u00d74 matrix and, in the case of b4<\/code>, there are only 188 valid words. What about a recursive solution (many of the submissions used recursion)? I tend to avoid recursion unless there are clear advantages to using it, and in this case I didn’t see any advantages, clear or otherwise. So, iteration it was…<\/p>\n\n
paths<\/code>\u00a0\u2013 the paths traversed through the board<\/li>\nstubs<\/code>\u00a0\u2013 the word “stubs” built from the contents of the cells in paths<\/code><\/li>\n<\/ul>\npaths<\/code> is initialized to the indices of the board, and stubs<\/code> is initialized to the contents of each cell. Then iterate:<\/p>\n\n
stubs<\/code> that are in words<\/code><\/li>\nSetup<\/h4>\n
board<\/code>.<\/p>\n[1] inds\u2190\u2373\u2374board \u235d board indices\r\n[2] neighbors\u2190(,inds)\u2218\u2229\u00a8\u2193inds\u2218.+(,\u00af2+\u23733 3)~\u22820 0 \u235d matrix of neighbors for each cell\r\n<\/code><\/pre>\n[2]<\/code> as a stencil<\/em>-like (\u233a<\/code>) operation. Why, then, didn’t I use stencil? To be honest, it didn’t occur to me at the time \u2013 I knew how to code what I needed without using stencil. As it turns out, for this application, stencil is slower. The stencil expression is shorter, more “elegant”, and possibly more readable (assuming you know how stencil works), but it takes more than twice the time. Granted, this line only runs once per invocation so the performance improvement from not using it is minimal.<\/p>\n inds\u2190\u23734 4\r\n ]RunTime -c '(,inds)\u2218\u2229\u00a8\u2193inds\u2218.+(,\u00af2+\u23733 3)~\u22820 0' '{\u2282(,\u237a\u2193\u2375)~(\u2375[2;2])}\u233a3 3\u22a2inds'\r\n \r\n (,inds)\u2218\u2229\u00a8\u2193inds\u2218.+(,\u00af2+\u23733 3)~\u22820 0 \u2192 2.2E\u00af5 | 0% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395 \r\n {\u2282(,\u237a\u2193\u2375)~(\u2375[2;2])}\u233a3 3\u22a2inds \u2192 5.0E\u00af5 | +127% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395 \r\n<\/code><\/pre>\nnextcells<\/code> which, given a path, returns the unvisited cells adjacent to the last cell in the path. For example, if we have a path that starts at board[1;1]<\/code> and continues to board[2;2]<\/code>, then the next unvisited cells for this path are given by:<\/p>\n nextcells (1 1)(2 2)\r\n\u250c\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u2510\r\n\u2502\u250c\u2500\u2500\u2500\u2510\u2502\u250c\u2500\u2500\u2500\u2510\u2502\u250c\u2500\u2500\u2500\u2510\u2502\u250c\u2500\u2500\u2500\u2510\u2502\u250c\u2500\u2500\u2500\u2510\u2502\u250c\u2500\u2500\u2500\u2510\u2502\u250c\u2500\u2500\u2500\u2510\u2502\r\n\u2502\u25021 2\u2502\u2502\u25021 3\u2502\u2502\u25022 1\u2502\u2502\u25022 3\u2502\u2502\u25023 1\u2502\u2502\u25023 2\u2502\u2502\u25023 3\u2502\u2502\r\n\u2502\u2514\u2500\u2500\u2500\u2518\u2502\u2514\u2500\u2500\u2500\u2518\u2502\u2514\u2500\u2500\u2500\u2518\u2502\u2514\u2500\u2500\u2500\u2518\u2502\u2514\u2500\u2500\u2500\u2518\u2502\u2514\u2500\u2500\u2500\u2518\u2502\u2514\u2500\u2500\u2500\u2518\u2502\r\n\u2514\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2518\r\n<\/code><\/pre>\nwords<\/code>.<\/p>\n[6] mwords\u2190\u2349\u2191words \u235d matrix of candidate words, use a columnar matrix for faster \u2227.=<\/code><\/pre>\nwords<\/code> and why is it transposed?<\/p>\n\n
\n<\/a><\/li>\n<\/ul>\nThings Run Faster If You Do Less Work<\/h4>\n
words<\/code> and stubs<\/code> as we progress, we will perform smaller searches. The first pass at minimizing the data to be searched is done during setup \u2013 we remove any words<\/code> that don’t begin with a first letter of any of board<\/code>‘s cells as well as words that contain letters not found in board<\/code>:<\/p>\n[7] mask\u2190mwords[1;]\u220a\u2283\u00a8,board \u235d mark only those beginning with a letter on the board\r\n[8] mask\u2190mask\\\u2227\u233f(mask\/mwords)\u220a' ',\u220aboard \u235d further mark only words containing only letters found on the board\r\n[9] words\/\u2368\u2190mask \u235d keep those words\r\n[10] mwords\/\u2368\u2190mask \u235d keep them in the matrix form as well\r\n<\/code><\/pre>\nb4<\/code>, this reduces the number of words<\/code> to be searched from 267,752 to 16,247 – a ~94% reduction. Then we iterate, appending each path’s next unvisited cells and creating new stubs<\/code> from the updated paths:<\/p>\n[13] next\u2190nextcells\u00a8paths \u235d get the next cells for each path\r\n[14] paths\u2190\u2283,\/(\u2282\u00a8paths),\u00a8\u00a8next \u235d append the next cells to each path\r\n[15] stubs\u2190\u2283,\/stubs{\u237a\u2218,\u00a8board[\u2375]}\u00a8next \u235d append the next letters to each stub\r\n<\/code><\/pre>\nstubs<\/code> that are in words<\/code> to the result:<\/p>\n[16] r,\u2190words\u2229stubs \u235d add any matching words\r\n<\/code><\/pre>\n[19] lens\u2190\u2262\u00a8stubs \u235d length of each stub\r\n[20] :For n :In \u222alens \u235d for each unique stub length\r\n<\/code><\/pre>\n\u2227.=<\/code> can tell us which stubs<\/code> match prefixes of which words<\/code>. Now we can see the reason for creating mwords<\/code>. Since the data in mwords<\/code> is stored in “ravel<\/em>ed” format, n\u2191mwords<\/code> quickly returns a matrix of all n-length prefixes of words<\/code>:<\/p>\n[21] m\u2190n=lens \u235d mark stubs of this length\r\n[22] map\u2190(\u2191m\/stubs)\u2227.=n\u2191mwords \u235d map which stubs match which word beginnings\r\n[23] mask\u2228\u2190\u2228\u233fmap \u235d words that match\r\n[24] found[(\u2228\/map)\/\u2378m]\u21901 \u235d stubs that match\r\n[25] :EndFor\r\n<\/code><\/pre>\nfound<\/code> and mask<\/code>, to pare down paths<\/code>\/stubs<\/code> and words<\/code>\/mwords<\/code> respectively. If we look at the number of words<\/code> and stubs<\/code> at each step, we can see that the biggest performance gain is realized by doing less work:<\/p>\n\u250c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u2500\u2510\r\n\u2502Phase \u2502\u2262words \u2502\u2262stubs\u2502\r\n\u251c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2524\r\n\u2502Initial List \u2502267,752\u2502 0\u2502\r\n\u251c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2524\r\n\u2502After Initial Cull\u2502 16,247\u2502 16\u2502\r\n\u251c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2524\r\n\u2502After 2-cell Cull \u2502 7,997\u2502 56\u2502\r\n\u251c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2524\r\n\u2502After 3-cell Cull \u2502 2,736\u2502 152\u2502\r\n\u251c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2524\r\n\u2502After 4-cell Cull \u2502 1,159\u2502 178\u2502\r\n\u251c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2524\r\n\u2502After 5-cell Cull \u2502 371\u2502 119\u2502\r\n\u251c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2524\r\n\u2502After 6-cell Cull \u2502 87\u2502 42\u2502\r\n\u251c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2524\r\n\u2502After 7-cell Cull \u2502 16\u2502 10\u2502\r\n\u251c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2524\r\n\u2502After 8-cell Cull \u2502 2\u2502 1\u2502\r\n\u251c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2524\r\n\u2502All Done \u2502 0\u2502 0\u2502\r\n\u2514\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2500\u2518\r\n<\/pre>\n<\/div>\n
Does
mwords<\/code> Make Much of a Difference?<\/h4>\nf10<\/code>, that does not used transposed word matrix mwords<\/code> (it still does the words<\/code> and stubs<\/code> culling). I compared it to my original version,f0<\/code>, and the fastest submitted version, f1<\/code>:<\/p>\n 0 1 10 time 'b4'\r\n f0 b4 \u2192 1.4E\u00af2 | 0% \u2395\u2395 \r\n f1 b4 \u2192 2.2E\u00af1 | +1551% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\r\n f10 b4 \u2192 2.1E\u00af1 | +1422% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395 <\/code><\/pre>\nf10<\/code> performed remarkably close to f1<\/code>. When I looked at the code for f1<\/code>, I saw that the author had implemented a similar culling approach and had commented in several places that the construct was to improve performance. Good job! But this does demonstrate that maintaining a parallel, simple, copy of words<\/code> makes the solution run about 15\u00d7 faster.<\/p>\nTakeaways<\/h2>\n
\n
\u2262\u220aboard<\/code>.<\/li>\nFindWords<\/code> was used a lot, and I could be fairly certain that words<\/code> was static (unchanging), then I could create mwords<\/code> outside of FindWords<\/code>. The line that creates mwords<\/code> consumes about half of total time of the function.<\/li>\n<\/ul>\n\n
words<\/code> as a vector of words is convenient, readable, and there aren’t those extra spaces that might occur in a matrix format. But as we saw, it performs poorly compared to a simple matrix format. Don’t be afraid to make the data conform to a more performant organization.<\/li>\n
\nf4<\/code> and f7<\/code> in the timings above. The fastest submission, f1<\/code>, was submitted by Julian Witte. Please remember that we did not specify performance as a criterion for the problem, so this is in no way a criticism of any of the submissions.<\/p>\nf0<\/code>–f9<\/code>, each of which contains a FindWords<\/code> function and any needed subordinate functions (in addition to the solution namespaces, the .zip<\/strong> file also includes AllWords<\/code>, the time<\/code> function and 4 sample boards \u2013 b2<\/code>,b3<\/code>,b4<\/code>, and b6<\/code>). You can extract and use the code as follows:<\/p>\n\n
\n ]Link.Import # {the directory you chose}\/Submissions<\/code>
\nThis step might take several seconds when Link.Import<\/code> brings in AllWords<\/code><\/li>\n<\/ol>\nPostscript<\/h2>\n