Count the crossing words

10

1

Consider the following standard 15×15 crossword puzzle grid.

Crossword grid

We can represent this in ASCII art by using # for blocks and (space) for white squares.

     #    #    
     #    #    
          #    
   #   #       
###     ##   ##

     ##   #    
   #       #   
    #   ##     

##   ##     ###
       #   #   
    #          
    #    #     
    #    #     

Given a crossword grid in the ASCII art format above, determine how many words it holds. (The above grid has 78 words. It happens to be last Monday's New York Times puzzle.)

A word is a group of two or more consecutive spaces running vertically or horizontally. A word starts and ends with either a block or the edge of the grid and always runs top to bottom or left to right, never diagonally or backwards. Note that words can span the whole width of the puzzle, as in the sixth row of the puzzle above. A word does not have to be connected to another word.

Details

  • Input will always be a rectangle containing the characters # or (space), with rows separated by a newline (\n). You can assume the grid is made of any 2 distinct printable ASCII characters instead of # and .
  • You may assume there is an optional trailing newline. Trailing space characters DO count, as they affect the number of words.
  • The grid will not always be symmetrical, and it may be all spaces or all blocks.
  • Your program should theoretically be able to work on a grid of any size, but for this challenge it will never be larger than 21×21.
  • You may take the grid itself as input or the name of a file containing the grid.
  • Take input from stdin or command line arguments and output to stdout.
  • If you prefer, you may use a named function instead of a program, taking the grid as a string argument and outputting an integer or string via stdout or function return.

Test cases

  1. Input:

        #
        #
        #
    

    Output: 7 (There are four spaces before each #. The result would be the same if each number sign were removed, but Markdown strips spaces from otherwise empty lines.)

  2. Input:

    ##
     #
    ##
    

    Output: 0 (One-letter words don't count.)

  3. Input:

    ######
    #    #
      ####
    # ## #
    # ## #
    #### #
    

    Output: 4

  4. Input: (May 10's Sunday NY Times puzzle)

       #    ##   #       
       #    #    #       
       #         #       
           #     ###   ##
        #       #        
    ##   #   #           
            #       ##   
          #   ##         
       #        ##      #
             #   ###   ##
    #   ##         ##   #
    ##   ###   #         
    #      ##        #   
             ##   #      
       ##       #        
               #   #   ##
            #       #    
    ##   ###     #       
           #         #   
           #    #    #   
           #   ##    #   
    

    Output: 140

Scoring

Shortest code in bytes wins. Tiebreaker is oldest post.

NinjaBearMonkey

Posted 2015-06-05T14:05:37.590

Reputation: 9 925

Answers

7

CJam, 18 17 13 11 bytes

2 bytes saved by Dennis.

Uses spaces for filled cells and 1 for empty cells:

qN/_z+:~1-,

Test it here.

Explanation

q    e# Read the entire input.
N/   e# Split into lines.
_z   e# Make a copy and transpose it.
+    e# Add the lines of the two grids together.
:~   e# Evaluate each line which will push a rep-digit number for each empty-cell chunk.
1-   e# Remove all the 1s as these correspond to individual empty cells.
,    e# Get the length of the array.

Martin Ender

Posted 2015-06-05T14:05:37.590

Reputation: 184 808

9

Slip, 18 + 3 = 21 bytes

>? ( +(X|$^)<<){2}

Run with the flags no (hence the +3), and uses space/X instead of space/#. Annoyingly this is longer than CJam/Pyth, but I guess Slip wasn't designed to be particular golfy...

Try it online. Note that the first example is missing spaces on a few lines.

Explanation

>?           Optionally turn right, hence matching either horizontally or vertically
[space]      Match a space
(    ){2}    Group, twice:
[space]+       Match 1+ spaces
(X|$^)         Either an X or the boundary of the grid
<<             Reverse the match pointer by turning left twice

The n flag makes output print the number of matches, and the o flag enables overlapping matches starting from the same square. The reason for the back-and-forth is because Slip tries matches starting from every square, and we want to make sure we only match a full row rather than a partial one. Slip only returns unique matches, even if they started from different positions.

Note: Originally I had >?( +(X|$^)<<){2}, with the first space on the inside. This would miss some cases with 2 space long words at the edge, since the pointer would go like this:

XXX       XXX       XXX       XXX
X>        X >       X<        <
XXX       XXX       XXX       XXX

[sp]    [sp]+$^    <<[sp]    [sp]+   (uh oh match fails)

Sp3000

Posted 2015-06-05T14:05:37.590

Reputation: 58 729

Why are the two flags three bytes? – lirtosiast – 2015-06-05T15:45:07.340

@ThomasKwa I think the current policy with command line flags is this meta post, which counts the number of bytes as the difference from the usual invocation of the code. So here the difference is between py -3 slip.py regex.txt input.txt and py -3 slip.py regex.txt input.txt no, which is three bytes (including the space before n)

– Sp3000 – 2015-06-05T16:06:22.213

That makes sense. I was thinking about it from an entropy perspective; sometimes I forget that it's characters we count. – lirtosiast – 2015-06-05T16:32:33.560

4

Haskell, 81 bytes

import Data.List
m x=sum[1|(_:_:_)<-words x]
f x=m x+m(unlines$transpose$lines x)

Uses spaces as block characters and any other (non whitespace) character as an empty cell.

How it works: split input into list of words at spaces. Take a 1 for every word with at lease 2 characters and sum those 1s. Apply the same procedure to the transposition (split at \n) of the input. Add both results.

nimi

Posted 2015-06-05T14:05:37.590

Reputation: 34 639

4

JavaScript (ES6) 87 121 147

Build the transposition of input string and append it to input, then count the strings of 2 or more spaces.

Run the snippet in Firefox to test.

Credits @IsmaelMiguel, a solution for ES5 (122 bytes):

function F(z){for(r=z.split(/\n/),i=0;i<r[j=0][L='length'];i++)for(z+='#';j<r[L];)z+=r[j++][i];return~-z.split(/  +/)[L]};

F=z=>
(
  r=z.split(/\n/),
  [r.map(r=>z+=r[i],z+='#')for(i in r[0])],
  ~-z.split(/  +/).length
)

// TEST
out=x=>O.innerHTML += x + '\n';

[
'     #    #    \n     #    #    \n          #    \n   #   #       \n###     ##   ##\n               \n     ##   #    \n   #       #   \n    #   ##     \n               \n##   ##     ###\n       #   #   \n    #          \n    #    #     \n    #    #     ', '##\n #\n##', '    #\n    #\n    #',
 '######\n#    #\n  ####\n# ## #\n# ## #\n#### #',
 '   #    ##   #       \n   #    #    #       \n   #         #       \n       #     ###   ##\n    #       #        \n##   #   #           \n        #       ##   \n      #   ##         \n   #        ##      #\n         #   ###   ##\n#   ##         ##   #\n##   ###   #         \n#      ##        #   \n         ##   #      \n   ##       #        \n           #   #   ##\n        #       #    \n##   ###     #       \n       #         #   \n       #    #    #   \n       #   ##    #   '  
].forEach(x=>out(x.replace(/ /g,'.')+'\n'+F(x)+'\n'))
<pre id=O></pre>

edc65

Posted 2015-06-05T14:05:37.590

Reputation: 31 086

1What about F=z=>{for(r=z.split(/\n/),i=0;i<r[j=0][L='length'];i++)for(z+='#';j<r[L];)z+=r[j++][i];return~-z.split(/ +/)[L]}? It is 113 bytes long. Your regex was replaced with / +/ (2 spaces), The j=0 was added in the 'parent' for loop and instead of using the syntax obj.length, I changed to use L='length'; ... obj[L], which is repeated 3 times. – Ismael Miguel – 2015-06-06T01:30:29.053

I got it to work on http://www.es6fiddle.net/iakdcpdh/ (instead of F=z=>, I had to use var F=(z,i,L,j,r)=>). I tested it on IE11 and it works!

– Ismael Miguel – 2015-06-06T01:36:52.487

@IsmaelMiguel well done! and best fit for ES5. Looking at it again, I found something more ES6ish and shorter. Maybe you could publish your solution for ES5. – edc65 – 2015-06-06T06:20:00.910

No, it's alright. It was your solution, I just reduced it. I don't find it fair to answer as if it was my own. – Ismael Miguel – 2015-06-06T14:10:13.007

Now that I think about it, you can replace /\n/ with a template string with a real newline between. That saves 1 byte since you don't have to write the escape sequence. – Ismael Miguel – 2015-06-06T14:17:57.930

@IsmaelMiguel right, thx. It's a pity that it compromise (even more!) the readability of code, having a significant newline that must be counted and some other newlines just for pretty printing. And 87 or 86 does not matter when competition is at 11..20 – edc65 – 2015-06-06T15:31:02.027

You get more functionality. /\n/ can only handle 1 newline style, while the template string can handle the browser's default. – Ismael Miguel – 2015-06-06T15:55:48.810

3

Pyth, 15 14 13 bytes

lftTcjd+.zC.z

I'm using as seperator and # as fill characters instead of their opposite meaning from the OP. Try it online: Demonstration

Instead of # as fill character this accepts also letters. So you could actually take the solved crossword puzzle, and it would print the number of words. And if you remove the l command, it even prints all words. Test it here: May 10's Sunday NY Times puzzle

Explanation

        .z      all input rows
          C.z   all input columns (C transposes)
       +        add them (all rows and columns)
     jd         join by spaces
    c           split by spaces
 f              filter for pieces T, which satisfy:
  tT              len(T) > 1
l               length, implicitly printed

Jakube

Posted 2015-06-05T14:05:37.590

Reputation: 21 462