Find the rectangle

Question

Overview

Given a 2 dimensional array of values with a filled in rectangle, find the position and size of the rectangle. Do it in the fewest array accesses as possible.

Requirements

• The x and y values in the output must be 0-indexed. The top left corner is (0, 0).
• The output should be the 4-tuple (x, y, width, height).
• This is a fastest-algorithm challenge, so do it in as few array accesses as possible. An "array access" is the use of abc[x][y], .indexOf, or .contains. Getting the bounds of the array is free.
• You may not copy the array to another format.
• You may not store any information about the inputs into your program ahead of time. That's cheating. It should be completely general. The inputs are fixed so everyone is on an equal playing field, and so your program isn't given a bad score from simple bad luck.
• While not strictly a requirement, to keep track of "array accesses", you can have a counter that is incremented after every access.

Example Inputs and Outputs

Given the following 2D array

((0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 1, 1, 1, 1, 1, 0, 0),
 (0, 0, 0, 1, 1, 1, 1, 1, 0, 0),
 (0, 0, 0, 1, 1, 1, 1, 1, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0))

Your program should return (3, 2, 5, 3), specifying that the rectangle starts at x=3 and y=2 and is 5 units wide and 3 units tall.

Input:

((1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
 (1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
 (1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0))

Output: (0, 0, 3, 3)

Input:

((0, 0, 0, 0, 0, 1, 1, 1, 1),
 (0, 0, 0, 0, 0, 1, 1, 1, 1),
 (0, 0, 0, 0, 0, 1, 1, 1, 1),
 (0, 0, 0, 0, 0, 1, 1, 1, 1),
 (0, 0, 0, 0, 0, 1, 1, 1, 1))

Output: (5, 0, 4, 5)

Input:

((0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 1, 1, 0, 0),
 (0, 0, 0, 0, 0, 0, 1, 1, 0, 0),
 (0, 0, 0, 0, 0, 0, 1, 1, 0, 0),
 (0, 0, 0, 0, 0, 0, 1, 1, 0, 0))

Output: (6, 2, 2, 4)

Input:

((0, 0, 0, 0, 0, 0),
 (0, 1, 1, 1, 1, 0),
 (0, 1, 1, 1, 1, 0),
 (0, 1, 1, 1, 1, 0),
 (0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0))

Output: (1, 1, 4, 3)

Input:

((0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 1, 0, 0, 0, 0))

Output: (3, 7, 1, 1)

Scoring

Your program's score is determined by the sum of the number of array accesses it takes to solve all 6 of those examples. For example, if it takes 20 accesses to solve the first 5, and 15 for the last, your program's score will be 115. Lower score is better.

Answer 1

JavaScript, 40 operations

function findRect(arr) {
  var found = false;
  var c = 0;
  for (i = 0; i < arr.length; i++) {
    if (!found) {
      first = arr[i].indexOf(1);
      c++;
      if (~first) {
        found = true;
        x = first;
        y = i;
      }
    }
    if (found) {
      last = arr[i].lastIndexOf(1);
      c++;
      if (~last) {
        width = last - x + 1;
        height = i - y + 1;
      } else {
        console.log(c);
        return [x,y,width,height];
      }
    }
  }
  console.log(c);
  return [x,y,width,height];
}

var globalC = 0;

function findRect(arr) {
  var found = false;
  var c = 0;
  for (i = 0; i < arr.length; i++) {
    if (!found) {
      first = arr[i].indexOf(1);
      c++;
      if (~first) {
       found = true;
        x = first;
        y = i;
      }
    }
    if (found) {
      last = arr[i].lastIndexOf(1);
      c++;
      if (~last) {
       width = last - x + 1;
        height = i - y + 1;
      } else {
       console.log(c);
        globalC += c;
        return [x,y,width,height];
      }
    }
  }
  console.log(c);
  globalC += c;
  return [x,y,width,height];
}

console.log(findRect([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 1, 1, 1, 1, 1, 0, 0],
 [0, 0, 0, 1, 1, 1, 1, 1, 0, 0],
 [0, 0, 0, 1, 1, 1, 1, 1, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]));
 
 console.log(findRect([[1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
 [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
 [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]));
 
 console.log(findRect([[0, 0, 0, 0, 0, 1, 1, 1, 1],
 [0, 0, 0, 0, 0, 1, 1, 1, 1],
 [0, 0, 0, 0, 0, 1, 1, 1, 1],
 [0, 0, 0, 0, 0, 1, 1, 1, 1],
 [0, 0, 0, 0, 0, 1, 1, 1, 1]]));
 
 console.log(findRect([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 1, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 1, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 1, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 1, 0, 0]]));
 
 console.log(findRect([[0, 0, 0, 0, 0, 0],
 [0, 1, 1, 1, 1, 0],
 [0, 1, 1, 1, 1, 0],
 [0, 1, 1, 1, 1, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0]]));
 
 console.log(findRect([[0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 1, 0, 0, 0, 0]]));
 
 console.log(globalC);

Answer 2

PowerShell, 34 50 Operations

I was doing some string manipulation earlier. I removed any string manipulation, as it was clarified as forbidden, at the cost of some extra operations.

function Get-SquareCoordinates{
    param(
        [array]$array    
    )

    $count = 0             # Record the count
    $flag = $false         # Loop exit flag
    $rowIndex = -1         # Row location in array

    # Find the top left corner
    do{

        $rowIndex++
        # Check if this row contains 1
        $result = $array[$rowIndex].IndexOf(1)

        # If there is no 1 then -1 would be in $result
        if($result -ge 0){$x,$y=$result,$rowIndex;$flag=$true}

        # Increase the counter
        $count++
    } while(!$flag)

    # Start from the back of the array and find the last index of 1
    $w,$h = 0,0              # To store the width and height of the rectangle
    $flag = $false         # Loop exit flag
    $rowIndex = $array.Count          # Row location in array

    # Find the bottom right corner
    # Start checking the rows backwards
    do{
        $rowIndex--
        # Check if this row contains 1 and add the count of all the ones to the index of the first one found
        $result = $array[$rowIndex].IndexOf(1) + ($array[$rowIndex]-match1).Count - 1

        # If there is no 1 then -1 would be in $result
        if($result -ge 0){
            $w,$h= ($result-$x+1),($rowIndex-$y+1)
            $flag=$true
        }

        # Increase the counter by 2. First to find the one and the second to count the 1's on the line
        $count=$count+2
    } while(!$flag)

    Write-Host "Determined using $count array operations" -ForegroundColor Green
    $x,$y,$w,$h
}

Using the inputs exactly as in the questions, where each is saved as a variable it would net me the answers as an array of integers and spit out a console line containing the amount of operations it took to find the dimensions.

$array1, $array2, $array3,$array4,$array5,$array6 | ForEach-Object{
    (Get-SquareCoordinates $_) -join ", " 
}

Determined using 9 array operations
3, 2, 5, 3
Determined using 11 array operations
0, 0, 3, 3
Determined using 3 array operations
5, 0, 4, 5
Determined using 5 array operations
6, 2, 2, 4
Determined using 12 array operations
1, 1, 4, 3
Determined using 10 array operations
3, 7, 1, 1