You are a young programming geek living with your 2 other best friends. Every week, one of you has to do all the chores of the house and you decide whose turn it is by picking a stick. The one who picks the shortest stick loses and does all the chores.
As all of you are programmers and love creating puzzles, you have modified the "Pick the shortest stick" into a computer puzzle.
Here are the rules of the puzzle.
- You will be given a 2D matrix, where each column represents a stick.
- In each column, 1 represents a portion of the stick and 0 is an empty space
- When going from top to bottom in each column, initially you have
0's and as soon as you hit a
1, the stick has started and rest of the column will be filled with
- You can write your program to pick one column. The size of the stick in that column determines the winner/loser. Size of stick == number of 1s in that column.
- However, that program can only have a linear worst-case time complexity.
As all of you are programmers, you will know if someone else's program is shooting the time complexity limit.
Your job is to:
- Write a program or function that accepts input in either a 2D format or array of strings.
- Input can be taken from STDIN/prompt/console or a function argument.
- If you are reading the input from STDIN/prompt then you can assume that the reading of input and converting it to an array takes 0 time (even though the code to do so has to be there in your answer)
- Determine the column with the longest stick in it.
- Output can be the function's return value or to STDOUT/console/alert.
- The program/function must have linear worst-case time complexity,
mis the number of rows and
nthe number of columns.
Input can be either one of the following formats:
[ [0, 0, 0, 0], [1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 1, 1] ]
Array of Strings:
[ "0000", "1000", "1101", "1111" ]
The input will have following properties:
- Size of the array is unknown, assume a rectangle of any size
- In any column, coming top down, if you see a 1, then everything below will be a one
- Empty-columns (i.e. 0-length) sticks are allowed.
This is a code-golf so shortest code wins!*
Please explain your code, or give the ungolfed version (to verify time complexity) along with which of the two input formats you expect.
UPDATE Linear time complexity here means O(n+m) where n is column size and m is row size. (For those who were unclear)
UPDATE 2 This definitely can be done in linear time. And if you are posting an answer, feel free to delay posting the logic/algorithm by a couple of days for a fair fight :)
UPDATE 3 I'll go over all answers in couple of hours to validate time complexity and the program :)