Pick the longest stick

Question

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.

1. You will be given a 2D matrix, where each column represents a stick.
2. In each column, 1 represents a portion of the stick and 0 is an empty space
3. 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 1 only
4. 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.
5. 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, O(m+n) where m is the number of rows and n the number of columns.

Input can be either one of the following formats:

2D array:

[ [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 :)

Answer 1

GolfScript, 45 chars

:^,:y;0:x{^y(=x=2%y*{y(:y;x\}{x):x}if^0=,<}do

Takes input as an array of strings, returns (0-based) index of tallest column. It runs in O(rows + columns) iterations, and each iteration should take essentially constant time (at least assuming constant-time arithmetic). The only array/string operations done within the loop are element lookups (=) and taking the length of a string (,), both of which take constant time in GolfScript.

Try it online.

Explanation:

Like most of the solutions here, this code works by starting at the lower left corner of the matrix, walking up or right depending on whether the current element of the matrix is 1 or 0, and keeping track of the column where it last moved up.

At the beginning of the program, I assign the input array to the variable ^, its length (i.e. the number of rows) to y, and 0 to x. The value 0 is also left on the stack; during the following loop, it will be replaced by the index of the tallest column.

Within the main loop, ^y(=x= extracts the x-th character of the y-1-th row in ^. This actually returns the ASCII code of the character, so 2% is needed to drop all but the last bit. As a special case, if y equals 0 (which can happen if the tallest column found so far reaches all the way to the top row), the bit looked up will actually come from the last row in the matrix (index -1), but the following y* forces it to zero, thus effectively creating a virtual all-zeros row at the top of the matrix.

The following if will then execute one of the two code blocks preceding it, depending on whether the looked-up bit is non-zero (true) or zero (false). If non-zero, y is decremented by one, and the current value of x replaces the tallest column index on the stack (with the old value temporarily left on top of it). If zero, x is simply incremented by one (and temporarily left on the stack, on top of the tallest column index).

Finally, ^0= extracts the first row of the matrix, , returns its length, and < compares it with the column index temporarily left on the stack (which will equal x if it was just incremented) If the index is less that the length of the row, the loop repeats.

Ps. Based on my testing, it should be possible to shorten this program by one character by replacing the string length test ,< at the end of the loop with >, which cuts the string at the given index and returns the end portion (which will be empty, and thus false, at the end of the loop). However, while cutting a string like that appears to be implemented as a constant-time operation in GolfScript (or, rather, in Ruby, which GolfScript runs on top of), I have not found any official documentation saying so. Just to be safe, I've chosen to feature the slightly longer, but definitely O(1), version above.

Answer 2

Ruby, 83 75 68 66 63 bytes

f=->m{m[b=c=i=0].map{(c=i;b-=1)while(r=m[b-2])&&r[i]>0;i+=1};c}

Defines a function f which takes the 2D array form as input.

I'm starting at the bottom left, keeping track of maximum stick length (actually, minus that) and the corresponding column. In each column, if there are still 1s above the previous maximum stick length, I walk up the stick to the end and remember the new maximum length and column. That means that I'm iterating once along the columns and at most once along the rows (specifically I'm iterating as far as the maximum stick length), which is precisely O(m+n).

Answer 3

Python 2 - 71, 69, 73, 75 81

j=i=-1
M=input()
for m in M[0]:
 j+=1
 while-i<len(M)and M[i][j]:i-=1;J=j
print J

Answer 4

C, 64 bytes

Edit: I learned that the question asks for the location of the longest column and not its length.

The first line is the golfed code and the rest is the sample invocation.

g(int m,int n,int**a,int*r){for(*r=n;n*m;a[m][n]?m--,*r=n:--n);}

/* usage:
    m = number of rows
    n = number of columns
    a = 1-based 2D array such that a[i][j] gives the value at the ith row and jth column
    r = address of return value 
    Returns (to r) the 1-indexed location of a column with the longest length, or 0 if n=0
    */

int main()
{
    int flat[4*4] = {1, 0, 0, 0,
                     1, 0, 0, 1,
                     1, 1, 0, 1,
                     1, 1, 1, 1};
    int*twoD[4] = {flat-1,flat+3,flat+7,flat+11};
    int ret;
    g(4,4,twoD-1,&ret);
    printf("%d", ret);
    return 0;
}

// old function which determines longest length (65 bytes)
f(int m,int n,int**a,int*r){for(*r=m;n*m;a[m][n]?m--:--n);*r-=m;}

Answer 5

C++ :: 78

Unlike the other C solution, this is the whole program. (no invocation needed, no need to tell the function the size of the array). Unfortunately this means it is longer as main must be used instead of a single character function name, I have to interpret the input and then output the answer, where the other solution handles that "elsewhere". Also my first code golf.
compiled with g++ file.cpp -include iostream, run with ./a 000 010 110 111 (for example) == array of strings (I believe this is allowed in the question spec)

int c;main(int r,char**v){for(r--;r*v[r][c];v[r][c]-48?std::cout<<c,r--:++c);}

The above version outputs the current best found so far on each iteration. The final output digit is the answer. Switching from processing from bottom left instead of bottom right and 0 indexing reduced this solution by 10(!) characters.
switching to c++ drops submission by one more character as std::cout<< is shorter than putchar(-48) and it should also explicitly support more than 9 sticks with proper output (though it may get harder to differentiate each output)
Removing the answer field and outputting it direcly cut another 6 characters. It now only outputs the current best when it moves up which cuts out some output at least.
Entire file is now only 78 bytes in size - approaching the function only solution that the other C submission uses. (with lots of extra code to support said function).

As below description is out of date:

c is global so is initialised with 0
r is the number of inputs (rows) +1 (name of program)
v is the array of strings with v[0] being invalid (name of program)
As it is 0 indexed, r is out of bounds, so decrement.
While r!=0 (pointing at valid string) and character c in the string is not the null terminator '\0'
if character is not '0'
go up a row (r) and output the column (c)
else go to next column (c)

done

Can I even golf this further?

Ungolfed code (with extra output):

#include <stdio.h>
#include <string.h>

int main(int argc, char* argv[])
{
  int rows = argc-1;
  int cols = strlen(argv[1]);
  int ans;

  printf("rows: %d, cols: %d\n",rows, cols);

  while((rows)&&cols)
  {
    if (argv[rows][cols-1]-'0')
    {
      printf("stick @%d,%d\n",cols,rows);
      ans = cols;
      rows--;
    }
    else
    {
      printf("no stick @%d,%d\n",cols,rows);
      cols--;
    }
  }
  printf("%d",ans);
}

It uses the length of the strings to find out the number of columns and argc to find the number of rows. Starting in the bottom right corner, it follows these simple rules: If cell is a stick, then move up, set answer to current column. If cell is not a stick, then move to the left. O(n+m): as it only moves up and left, it can only have max n+m reads. It exits early if it falls off the top or left of the array.

Answer 6

PHP 5.4 - 108 bytes

(113 if you include the <?php)

Input format: Array will be read as a JSON string.

php longest_stick.php "[[0, 0, 0, 0],[1, 0, 0, 0],[1, 1, 0, 1],[1, 1, 1, 1]]"

Whitespace added for readability - all newlines and leading spaces can be removed.

<?php
$t=count($s=json_decode($argv[1]))-1;
foreach($s[0] as $k=>$_)
    while($s[$t][$k]) {
        $t--;
        $l = $k;
    }
echo $l?:0;

Minified version:

<?php $t=count($s=json_decode($argv[1]))-1;foreach($s[0] as $k=>$_)while($s[$t][$k]){$t--;$l=$k;}echo $l?:0;

Kind of stealing the algorithm from Martin here, but it's nice to play around with languages that aren't seen as often here XD

Answer 7

C#: 236 Chars

int p(int[,] a){int y=0,s=0,i=0,x;for(;++y<=a.GetUpperBound(0);)for(x=i;x<=a.GetUpperBound(1);){if(a[y,x++]==0)break;s=y;i++;}return s;}

ungolfed:

int p(int[,] a)
{
    int selectedRow=0;
    int maxLength=0;
    for(var y = 0; y<=a.GetUpperBound(0); y++)
        for(var x=maxLength; x<=a.GetUpperBound(1); x++)
        {
            if(a[y,x++]==0)
                break;
            selectedRow=y;
            maxLength++;
        }
    return selectedRow;
}

Answer 8

Cobra - 98

def f(a)
    s,x,y=0,0,a.count-1
    while y+1and x<a[0].count
        while a[y][x],y,s=y-1,x
        x+=1
    print s

Answer 9

OCaml - 144 characters

let s a=Array.(let rec f i j m=if i=0then m else if a.(i).(j)=0then if j=length a.(i)-1then m else f i(j+1)m else f(i-1)j j in f(length a-1)0 0)

Takes an int array array as input, and starts from below left, moving up or right if it sees a 1 or a 0. Column count starts at 0.

Usage

 s [| [| 0; 0; 0; 0 |]; [| 0; 0; 1; 0|]; [| 1; 0; 1; 0 |]; [| 1; 1; 1; 0 |]; [| 1; 1; 1; 1 |] |];;
 - : int = 2

Ungolfed

let s a = Array.(
  let rec f i j m = (* m is the longest stick seen so far *)
    if i=0 then m (* A column is full: this is the longest possible stick and j=m anyway *)
    else if a.(i).(j)=0 then (* current column is shorter than a previously seen stick *)
      if j=length a.(i)-1 then m (* we have examined all columns, just return m *)
      else f i(j+1) m (* start examining next column *)
    else f (i-1) j j (* current column is longer than all the ones previously seen. Check how long the stick is *)
  in
  f (length a-1) 0 0)

Answer 10

T-SQL - 71 64

Takes table A as input

SELECT IDENTITY(INT, 1, 1) R, A INTO A
FROM (VALUES
 ('0000')
,('1000')
,('1101')
,('1111')
) AS A(A)

And the query is

SELECT TOP(1)CHARINDEX('1',A)FROM A WHERE A LIKE'%1%' ORDER BY R

SQLFiddle

This returns the first row from the table a ordered by r where there is a 1 in string a.

TOP(1) restricts the result to the first row returned.

CHARINDEX('1',A) returns the position of the first 1 in the string or zero if it isn't found.

WHERE A LIKE'%1%' filters to rows where A contains a 1

ORDER BY R ensures the table is read from top down

Answer 11

Delphi 122 chars

Sigh...it is such a voluminous language.

Update: had to add 6 characters in changing function the return type from I to integer. The function still compiled as the test program had a "type I=integer;" statement left over from an earlier version of the program.

function S(A:array of string):integer;var n,c:integer;begin n:=0; repeat c:=Pos('1',A[n]);inc(n) until c>0; result:=c;end;

Answer 12

scheme - 236 chars

Even longer than the delphi version...there is probably a way to do this much more efficiently with scheme. And even worse - I just noticed it is order m*n.

(define (s l) (cond ((eq? (cdr l) '()) (car l)) (else (map + (car l) (s (cdr l)))))) (define (u l) (define (t n p q l) (cond ((eq? l '()) p) ((< n (car l)) (t (car l) q (+ 1 q) (cdr l))) (else (t n p (+ 1 q) (cdr l))))) (t 0 0 1 (s l)))

l is a list of the form '((0 0 0 0) (1 0 0 0) (1 1 0 1) (1 1 1 1)). I think that is a fair representation of a 2D array input for scheme.

(s l) sums the n-th elements of each of the sub-lists of a list of lists of nuimbers, so (s '((0 0 0 0) (1 0 0 0) (1 1 0 1) (1 1 1 1))) would return (3 2 1 2).

(u l) returns the 'index' of the largest entry of a list of numbers (using the helper function t), so (u '(3 2 1 2)) will return 1 (as the largest element '3 in the list '(3 2 1 2) is at position 1).

Answer 13

Racket 70

Golfed:

(define(h m)(for/last([r m]#:final(memv 1 r))(length(takef r even?))))

Assumes input is a two-dimensional array, which in Racket would be a list of lists:

(define m 
  '((0 0 0 0)
    (1 0 0 0)
    (1 1 0 1)
    (1 1 1 1)))

Ungolfed:

(define (h m)
  ;; step through rows, stopping at the first that contains a 1
  (for/last ([r m] #:final (memv 1 r)) 
    (length (takef r even?)))) ; pop off the leading zeroes to get the column index

Returns the column index with the longest stick.

Answer 14

JavaScript, ES6, 76 characters

W=a=>(j=>{for(k=i=a.length-1;~i&~j;)a[i][j]?(k=j,i--):j--})(a[0].length-1)|k

Takes array of array input.

Answer 15

JavaScript ES6, 65 bytes

Takes both input formats

f=(a,t)=>a.reduceRight((p,c)=>t+1?t:(x=c.indexOf(1,p))+1?x:t=p,0)

Explained:

Iterates from bottom to top. Uses String.prototype.indexOf() or Array.prototype.indexOf() depending on the input on each value. Finds the first index of each row with a 1 from the previous offset, if it finds none then it sets the t variable to the last offset and doesn't perform anymore indexOf calls.