13
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ I'd argue that this can't be done in O(n+m), since each cell could contain the crucial value (i.e. the first "1" of the longest stick/column). So you need to look at each cell, which takes O(n*m). \$\endgroup\$ – Falko Sep 10 '14 at 9:32
  • \$\begingroup\$ Could there be empty columns? \$\endgroup\$ – Martin Ender Sep 10 '14 at 9:48
  • \$\begingroup\$ @Optimizer: Oh, I see. You're right. :) \$\endgroup\$ – Falko Sep 10 '14 at 9:50
  • 11
    \$\begingroup\$ It can't be done in O(n+m). Once the input has been converted into a format which allows random access then the remaining processing can be O(n+m), but you require writing a program, and in the worst case that the only 1 in the input is the very last cell then it's necessary to read the entire input. Even if a language's standard library fakes random access to stdin, under the scenes it's buffering it and so the time taken is Omega(n*m). \$\endgroup\$ – Peter Taylor Sep 10 '14 at 10:26
  • 2
    \$\begingroup\$ If you want to allow people to "simply make a function which accepts an array", the question shouldn't state that they must write a program. And if you require solutions which are in O(N^0.5) where N is the size of the input, you shouldn't ask for linear time solutions. A linear time solution can read the entire input. \$\endgroup\$ – Peter Taylor Sep 10 '14 at 10:37

15 Answers 15

4
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ @Optimizer I didn't see your second edit until after I posted it, so it was in the edit history anyway. That's why I just put it in a spoiler for people who want to figure it out themselves. \$\endgroup\$ – Martin Ender Sep 10 '14 at 10:23
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Is this intended to run in Python 2 or 3? What is the input supposed to look like? \$\endgroup\$ – feersum Sep 10 '14 at 12:35
  • 1
    \$\begingroup\$ @feersum Python 2, the array of arrays. \$\endgroup\$ – Justin Sep 10 '14 at 13:22
  • \$\begingroup\$ @feersum: Quincunx is right. Input is a 2D array of ints, as you suggested. \$\endgroup\$ – Falko Sep 10 '14 at 13:49
  • \$\begingroup\$ Won't i go out of bounds if a stick takes up a whole column? \$\endgroup\$ – xnor Sep 10 '14 at 18:21
  • 1
    \$\begingroup\$ Sorry, but it looks like changing j to count from 0 breaks the loop condition i*j. \$\endgroup\$ – xnor Sep 10 '14 at 21:44
2
\$\begingroup\$

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;}
\$\endgroup\$
  • \$\begingroup\$ Impressive! Can you ditch the ints in the function signature by any chance or does that not work due to the pointers in there? \$\endgroup\$ – Martin Ender Sep 10 '14 at 12:44
  • 1
    \$\begingroup\$ The input should only contain the array. You cannot tell the program about the size of the array. \$\endgroup\$ – Optimizer Sep 10 '14 at 12:47
  • \$\begingroup\$ Wait, does that actually work? This seems to be returning the length of the longest stick and not its position: ideone.com/YEzqzl \$\endgroup\$ – Martin Ender Sep 10 '14 at 12:48
  • 2
    \$\begingroup\$ @Optimizer that is basically impossible in C. \$\endgroup\$ – Martin Ender Sep 10 '14 at 12:48
  • \$\begingroup\$ Might be, but that is the question :) \$\endgroup\$ – Optimizer Sep 10 '14 at 12:50
2
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ @MartinBüttner I've "stolen" your algorithm, so it should be O(n+m) now. I think it's right XD \$\endgroup\$ – Niet the Dark Absol Sep 10 '14 at 14:20
  • \$\begingroup\$ You can replace $s=json_decode($argv[1]);$t=count($s)-1; with $t=count($s=json_decode($argv[1]))-1; (-3 bytes). \$\endgroup\$ – Blackhole Sep 10 '14 at 16:09
  • \$\begingroup\$ @Blackhole Indeed you can. Thank you! \$\endgroup\$ – Niet the Dark Absol Sep 10 '14 at 20:18
  • \$\begingroup\$ @Blackhole I think that would break functionality. It will perform the assignments even if the condition isn't met. \$\endgroup\$ – Niet the Dark Absol Sep 10 '14 at 20:55
  • \$\begingroup\$ @Blackhole Still breaks it, I'm afraid XD $t-- must only happen if the condition is met. \$\endgroup\$ – Niet the Dark Absol Sep 10 '14 at 23:15
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Can you explain what's going on in that code ? :D No experience with T-SQL \$\endgroup\$ – Optimizer Sep 10 '14 at 21:45
  • \$\begingroup\$ I see, so isn't the filtering on each row part an O(n*m) operation ? i.e. not linear time complexity. \$\endgroup\$ – Optimizer Sep 10 '14 at 22:04
  • \$\begingroup\$ Difficult to say. The SQL engine will check all the rows for a 1 in the column. It will only return only the first row from the top down that qualifies. So in this situation it scans the entire table. Filters the rows with the column containing 1. Sorts the results on the identity column and returns the first result. \$\endgroup\$ – MickyT Sep 10 '14 at 22:13
  • \$\begingroup\$ Look at it like this : What if your rows are like "0000","0000","0000","0001" . In this case, it will have to go till the last row and till the last character of the row to figure out the presence of 1 \$\endgroup\$ – Optimizer Sep 10 '14 at 22:17
  • 1
    \$\begingroup\$ So yeah, it is O(m*n) then :) \$\endgroup\$ – Optimizer Sep 10 '14 at 22:30
0
\$\begingroup\$

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;
\$\endgroup\$
  • \$\begingroup\$ Are you doing the Pos() call on each row (in your case, string) of the Array ? \$\endgroup\$ – Optimizer Sep 11 '14 at 0:07
  • \$\begingroup\$ @Optimiser Yes, the program searches each string in the array (using 'inc(n)') until it finds a '1'. The first '1' found will be the highest (or equal highest) '1', so its position in the string (strings are 1-ndexed in delphi) will be the position of the longest column. Routine fails if there are no '1's in the array, but I believe that this would be broken input as there would then not be a "longest stick" to be found. \$\endgroup\$ – Penguino Sep 11 '14 at 1:12
  • 1
    \$\begingroup\$ So first of all, this is a valid input: "0000", "0010", "1111" , secondly, your answer is not meeting the linear time complexity requirement \$\endgroup\$ – Optimizer Sep 11 '14 at 6:21
  • \$\begingroup\$ @Optimizer Yes, that would be valid input and correctly identifies the 3rd stick. But I realised after making the post that I had converted my valid order N program that used arrays, into an invalid order N^2 program that used strings (chasing a reduction from ~160 characters). \$\endgroup\$ – Penguino Sep 14 '14 at 21:14
0
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ Summing all sublists is an O(m*n) operation. \$\endgroup\$ – Martin Ender Sep 11 '14 at 11:03
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ So basically you are going through each column and counting the number of 1's ? \$\endgroup\$ – Optimizer Sep 11 '14 at 7:09
  • \$\begingroup\$ I see your point. Algorithm updated. \$\endgroup\$ – Matthew Butterick Sep 11 '14 at 8:09
  • \$\begingroup\$ This still has a worst-case complexity of O(m*n) (for the case in which there is no 1 in the matrix, or only in the bottom row). \$\endgroup\$ – Martin Ender Sep 11 '14 at 11:01
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ indexOf works in either O(log n) or O(n), so the overall algorithm will never be in O(m + n) \$\endgroup\$ – Optimizer Aug 8 '15 at 16:26
  • \$\begingroup\$ @Optimizer Yeah realised that was its O(m*n) wasn't thinking straight. \$\endgroup\$ – George Reith Aug 8 '15 at 22:25
  • \$\begingroup\$ @Optimizer Updated to be O(m+n) \$\endgroup\$ – George Reith Aug 8 '15 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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