6
\$\begingroup\$

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

\$\endgroup\$

closed as unclear what you're asking by xnor, Sriotchilism O'Zaic, NoOneIsHere, Mego, Destructible Lemon Jun 1 '17 at 4:41

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ @StephenS It can be assumed that every input will have exactly one rectangle. Anything else need not be considered. arr[x][y] is an access, .indexOf is an access, .contains also is, but getting the bounds of the array is not. I'm not sure what you mean by hidden test cases. \$\endgroup\$ – Daffy Jun 1 '17 at 2:39
  • 1
    \$\begingroup\$ @StephenS It should be valid for every 2 dimensional array with exactly one rectangle. Though I see what you mean, that would prevent cheating, though it makes it easy for me to cheat. I'm not sure how I'd get around that. \$\endgroup\$ – Daffy Jun 1 '17 at 2:47
  • 2
    \$\begingroup\$ If I convert the input into another format how do the operations count then? ie a string \$\endgroup\$ – Matt Jun 1 '17 at 2:53
  • 2
    \$\begingroup\$ I think counting a single array access for .indexOf is a deviation from what I'd understand an array access to be. If you intend it, I suggest prominently mentioning it in the spec so that reading comments doesn't give an advantage. Exactly what built-ins count as an access though? For example, what about finding the first instance from a starting index, or from the right? Counting? \$\endgroup\$ – xnor Jun 1 '17 at 2:54
  • 1
    \$\begingroup\$ I think the cleanest way to define this is to have a black-box function that, given a pair of coordinates, outputs the value at that coordinate of the array. The function is a black-box oracle that the code can query, but cannot access to the internals of. Then, each function call is an access. \$\endgroup\$ – xnor Jun 1 '17 at 3:00
2
\$\begingroup\$

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

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

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
\$\endgroup\$
  • \$\begingroup\$ My algorithm is more efficient when the box is near the beginning of a lengthy array, but yours crushes mine otherwise. I don't know how to get rid of my .lastIndexOf for every line of the box (other than coming from the end like you do). \$\endgroup\$ – Stephen Jun 1 '17 at 12:45
  • \$\begingroup\$ @StephenS I don't have access to a lastindexof method so I had to do something different. Before an edit I turned the array row into a string and used the string lastindexof() method. Now I just count the ones in the row. Are you able to count your ones instead of using lastindex of? \$\endgroup\$ – Matt Jun 1 '17 at 13:23
  • \$\begingroup\$ Oh, wait, I think I found the difference. It was bugging me. You have $result = $array[$rowIndex].IndexOf(1) as one operation, I have it as two - we'll need to get OP's decision on that. I have it as an access separate from an indexOf, you have them together counted as one access. (and you have the same thing here: $result = $array[$rowIndex].IndexOf(1) + ($array[$rowIndex]-match1).Count - 1 - you count that as 2, I'm counting that as 3 - two accesses, one indexOf) \$\endgroup\$ – Stephen Jun 1 '17 at 13:30
  • \$\begingroup\$ @StephenS.. hmmmm. You are right that is grey for me as well. I am just calling the indexof method on part of the array. The arrays used in this question are jagged arrays in powershell. an array of arrays. not a true 2d. So I don't see it as 2 ops. Either way the Q is closed so perhaps a new one will show up with more concrete guidelines \$\endgroup\$ – Matt Jun 1 '17 at 13:33
  • \$\begingroup\$ Yep, I understand - we'd need OP to clarify first. If it gets reopened we can worry about it. If I called indexOf and access together (and it counted as only one access) I'd save an operation a line. If OP clarifies and it gets reopened we can worry about it then \$\endgroup\$ – Stephen Jun 1 '17 at 13:37

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