Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given an image, output the [width in pixels of a full vertical section]1 (if one exists). If no vertical section exists, output 0.

Input may be provided as a local file or a nested array. If you choose to take input as a nested array, white pixels should be represented by a truthy value while non-white pixels should be represented by a falsey value.

1. the number of contiguous, all-white columns


You can assume that

  • no image will be larger than 1000 square pixels

  • there will be no more than one full vertical section per image


Examples

Inputs:

Outputs:

50
57
0
0

Here are the first two examples, highlighted (in yellow) to show their sections:

share|improve this question
    
Can there be islands of black in the middle so that there's multiple vertical sections? – xnor Feb 29 at 22:41
    
@xnor: There will only ever be one full vertical section per image. I'll add that to the spec. – Zach Gates Feb 29 at 22:43
    
My code is outputting 50 for the first test case, but correct numbers for the last 3, with the vertical slice from columns 233 to 282 (=50 pixels across). Can you confirm 48 is the correct number? – David Feb 29 at 23:03
    
@David: I see the correct slice from columns 232 to 282 (exclusive). I believe you're right. – Zach Gates Feb 29 at 23:10
2  
I don't think anyone's having problems, but it might be worth explicitly mentioning that you're looking for the number of contiguous, all-white columns. It's clear from the example, but it's generally preferred to not rely on examples or test cases. – MichaelS Mar 1 at 2:04

11 Answers 11

up vote 34 down vote accepted

Jelly, 2 bytes

PS

Try it here!

If I encode an image like so:

0000111111111100000
0000000111111111000
0000000001111100000
0000000011111000000
0001111111111111100
0000001111110000000
0000000111111110000
0000111111111100000

Into a nested array like this:

[[0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0],...]

Then P takes the element-wise product of all of the row vectors, and S sums all of the ones in the result, yielding the length of the vertical slice. (This works only because there’s guaranteed to be only one contiguous slice.) In our case, the answer is 3.

share|improve this answer
19  
ಠ_ಠ This level of golf astounds me. – VTCAKAVSMoACE Feb 29 at 23:09
    
What is the output for when there is no contiguous slices? (valid input) – VTCAKAVSMoACE Feb 29 at 23:12
3  
ps works in MATL too! – David Feb 29 at 23:13
    
Then there will be no column of all 1s, meaning the result of P will be [0,0,0...0], of which the Sum is 0, as expected. – Lynn Feb 29 at 23:13
    
@David Post it then? You might need Xps, though, if the image can be a single row (or ask the OP if there's a minimum size) – Luis Mendo Mar 1 at 0:16

APL, 4 bytes

+/×⌿

Try it here.

This is my first APL answer!

Thanks to @jimmy23013 and @NBZ for saving bytes!

share|improve this answer
    
This is not a function. (+/×/⍉) doesn't work. – jimmy23013 Mar 1 at 10:40
    
But you can use (+/×⌿) and that's 1 byte shorter. – jimmy23013 Mar 1 at 10:41
    
Save another 2 bytes by removing the parentheses. Lots of other APL answers have just an anonymous function train that must named or parenthesized to be used: +/×⌿ f←+/×⌿ f picture – Adám Mar 2 at 1:23

Bash + common utilities, 17

rs -Tc|grep -vc 0

If you're not using grep for , then you're doing it wrong ;-).

This uses the rs utility to do transposition. rs is bundled in OSX, but will need installing in most linux with something like sudo apt-get install rs.

Input columns are TAB separated, and rows are newline separated:

0   0   0   0   1   1   1   1   1   1   1   1   1   1   0   0   0   0   0   
0   0   0   0   0   0   0   1   1   1   1   1   1   1   1   1   0   0   0   
0   0   0   0   0   0   0   0   0   1   1   1   1   1   0   0   0   0   0   
0   0   0   0   0   0   0   0   1   1   1   1   1   0   0   0   0   0   0   
0   0   0   1   1   1   1   1   1   1   1   1   1   1   1   1   1   0   0   
0   0   0   0   0   0   1   1   1   1   1   1   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   1   1   1   1   1   1   1   1   0   0   0   0   
0   0   0   0   1   1   1   1   1   1   1   1   1   1   0   0   0   0   0

If you like, you can preprocess the example input images into this format with imagemagick and (GNU) sed. E.g:

$ for img in "AmXiR.jpg" "vb2Yt.jpg" "1V7QD.jpg" "MqcDJ.jpg" ; do
>     convert -depth 1 "$img" xpm:- | \
>     sed -nr '/pixels/{:l;n;/}/q;s/^"(.*)",?$/\1/;y/ ./01/;s/./&\t/g;p;bl}' | \
>     rs -Tc|grep -vc 0
> done
50
57
0
0
$
share|improve this answer

Perl, 21 22 bytes

Fixed version

Includes +2 for -lp (-l can be omitted and would still be a valid solution, but it's ugly without the final newline)

Give sequences of 1's and 0's on 0 or more lines on STDIN. You can add spaces or commas or whatever between the digits if you want as long as the usage is.consistent on all lines.

$a|=~$_}{$_=$a=~y;\xce;

This works as shown, but replace \xce by the literal byte value to get the claimed score

If there are multiple vertical sections this returns the sum of all section widths. If you want the width of a vertical section use

$a|=~$_}{$a=~/\xce+/;$_="@+"-"@-"

Old version

I originally misunderstood the challenge and implemented a program that gives true or false based on if a vertical line exists at all. Code and explanation here are for this old version

$a|=~$_}{$_|=~$a=~1

If only I could add 1=~ at the left for almost perfect symmetry... I suppose the closest would be

1=>$a|=~$_}{$_|=~$a=~1

Explanation

$a|=~$_     The bitwise operators in perl (&, |, ^, ~) also work on strings by 
            working on the sequence of byte values. The digits "0" and "1" happen
            to have the same ASCII value differing only in the last bit which is
            0 for "0" and 1 for "1". So I would really like to do an "&" here.
            Unfortunately "&" of two different length strings shortens the result
            to the shortest of the strings and my accumulator starts as an empty 
            string. The "|" of two strings however extends to the longest string.
            So instead I will apply De Morgan's law and use "|" on the
            complemented byte string 
}{          Standard perl golf trick. "-p code" transforms to (simplified)
            "while (<>) { code; print }". So if code is "code1 } { code2" this
            becomes "while (<>) { code1 } {code2; print }". So you can use code1
            for the loop operation, use code2 for the final calculation and get a
            free print by assigning to $_
$_|=~$a=~1  I would like to match the accumulator with the bit complement of "1",
            but $a=~~1 doesn't work because the 1 is not a string but a number.
            $a=~~"1" would work but is too long. Next up is complementing $a back
            and matching with 1, so $_=~$a=~1. That also doesn't work since the
            first =~ will be interpreted as a string match insteads of equals
            followed by complement. Easily solved by writing it as $_= ~a=~1. But
            if I am going to give up a byte I can at least have some fun with it.
            Using $_|= also makes the parse work and has the advantage that the
            failure case will give 0 instead of an empty string, which looks
            nicer. It also makes the code look very symmetric. I can also bring
            out the symmetry more by putting 1=> in front (which evaluates 1
            before the assignment and then immediately discards it)
share|improve this answer

Python 2, 30 bytes

There is a surprisingly elegant solution using many of my favourite built-in functions chained together.

lambda c:sum(map(all,zip(*c)))

Using the test image from @Lynn:

>>> image = [[0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0], [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0]]
>>> func = lambda c:sum(map(all,zip(*c)))
>>> func(image)
3
share|improve this answer

Pyth, 5

s*VFQ

Try it here

This uses Lynn's algorithm, but I decided to post it just to show how to golf vector operations in Pyth. The trick here is to chain the "sugar" syntax helpers V and F so that the fold is applied as a vector operation. The operator that is folded is of course multiplication, and then the result is summed to get the final answer.

share|improve this answer

J, 5 bytes

+/&*/

This is my first J answer!

share|improve this answer

CJam, 7 bytes

q~:.*:+

Try it online!

q~      e# read input and evaluate: push nested array
:.*     e# fold vectorized product over nested array: element-wise product of rows
:+      e# fold addition over array: compute its sum
share|improve this answer

JavaScript (ES6), 54 45 43 bytes

a=>a[s=0].map((_,i)=>s+=a.every(b=>b[i]))|s
a=>a[s=0].map((_,i)=>s+=!a.some(b=>b[i]))|s

Based on @Lynn's Jelly answer, though since golfed by using every or some instead of reduce. The first version encodes black = 0 while the second encodes black = 1.

Edit: Saved 2 further bytes thanks to @edc65.

share|improve this answer
3  
Try using map – CalculatorFeline Mar 1 at 1:51
    
It's 45 in my count. And you did not tried hard enough because it could be 43. – edc65 Mar 1 at 22:19
    
a=>a[s=0].map((_,i)=>s+=!a.some(b=>b[i]))|s – edc65 Mar 1 at 22:35
1  
@edc65 Well, you know the two hard problems of computing are cache invalidation, naming and off-by-one errors... – Neil Mar 2 at 0:26

Mathematica 24

Length@Cases[Total@#,0]&

Takes an array in the following form:

{{1, 0, 0, 0, 1, 0},
{1, 0, 0, 1, 1, 1},
{1, 1, 0, 0, 0, 0},
{1, 1, 0, 0, 1, 1},
{1, 0, 0, 1, 1, 1}}

And in this case outputs:

1
share|improve this answer
    
Or Length[Total@#~Cases~0]& but same byte count – CalculatorFeline Mar 1 at 1:51
    
1 and 0 are not truthy or falsy in Mathematica (and if they were the assignment would probably be the other way round). – Martin Ender Mar 1 at 12:46

𝔼𝕊𝕄𝕚𝕟, 7 chars / 9 bytes

⨭МƟïⓜ⨴$

Try it here (Firefox only).

This is @Lynn's great algorithm, but I found it independently. (I thought there was a builtin for this somewhere, still looking :P)

Explanation

МƟï transposes the input array, ⓜ⨴$ turns each inner vector into its product, and sums the resulting array.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.