10
\$\begingroup\$

Challenge

Given a grid like this,

  1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .

write a piece of code that can determine the size of the largest square that does not include a '#'. (The answer to this input is 5x5 as the bottom right 5x5 grid is the biggest square possible).

The square must have sides parallel to the x and y axes.

As some small details: the original grid is always a square and its side length is given to you. The coordinates of the '#' symbols are also given to you.

Input Details

First line: N (1 <= N <= 1000), the side length of the square grid, and T (1 <= T <= 10,000) the number of '#' signs.

Next T Lines: The coordinates of each of the T #'s

Test Cases

Input #1:

8 3
2 2
2 6
6 3

Result #1: 5

================

Input #2:

8 4
1 1
1 8
8 1
8 8

Result #2: 6

================

Input #3:

5 1
3 3

Result #3: 2

This is a problem, so the fastest code tested on the rextester compiler wins.

Have fun!

\$\endgroup\$

closed as off-topic by Dennis Feb 20 '18 at 10:06

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – Dennis
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ Related. \$\endgroup\$ – user202729 Jan 2 '18 at 3:57
  • 3
    \$\begingroup\$ For fastest-code 1000x1000 is too small, though \$\endgroup\$ – l4m2 Jan 2 '18 at 4:07
  • 1
    \$\begingroup\$ But rextester doesn't support Jelly or Hexagony. \$\endgroup\$ – user202729 Jan 2 '18 at 4:08
  • 6
    \$\begingroup\$ As capable as rextester is, may I recommend using try it online instead? It contains many more langauges, and is community run. \$\endgroup\$ – ATaco Jan 2 '18 at 4:10
  • 1
    \$\begingroup\$ "the fastest code tested on the rextester compiler wins" - fastest on what input? \$\endgroup\$ – Nathaniel Feb 12 '18 at 5:45
1
\$\begingroup\$

Node.js

Takes input as (w, l), where w is the width and l is an array of coordinates [x, y]. (This may be changed if the input format really is as strict as described.) Works in O(w²).

f = (w, l) => {
  var x, y,
      W = w * w,
      a = new Uint16Array(W),
      best = 0;

  l.forEach(([x, y]) => a[(y - 1) * w + x - 1] = 1);

  for(y = w; y < W; y += w) {
    for(x = y + 1; x < y + w; x++) {
      if(a[x]) {
        a[x] = 0;
      }
      else {
        best = Math.max(
          best,
          a[x] = Math.min(a[x - 1], a[x - w], a[x - w - 1]) + 1
        );
      }
    }
  }

  return best;
}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ console.log(f( 1000, [...Array(10000)].map(_=>[Math.random()*1000+1|0,Math.random()*1000+1|0]) )); cost 114ms, though it might be the language's low efficiency \$\endgroup\$ – l4m2 Jan 3 '18 at 6:29
  • \$\begingroup\$ It's more like 8ms inside f() after JIT compilation. (But yeah... answers are not going to be scored that way.) \$\endgroup\$ – Arnauld Jan 3 '18 at 11:54
  • \$\begingroup\$ I doubt the OP will add a more objective winning criteria... \$\endgroup\$ – user202729 Jan 4 '18 at 0:27
1
\$\begingroup\$

C (gcc)

No fancy algorithm here, just almost-bruteforce... but hey, C is fast.

Input: Takes input from stdin.

Output: Writes output to stdout.

#include <stdio.h>
#include <stdint.h>

int main(void) {
    uint_fast16_t n, t, i, j, h, x, y, flag, biggest = 0;
    scanf("%hi %hi", &n, &t);
    uint_fast8_t m[n][n];
    for (uint_fast16_t c = 0; c < t; ++c) {
        scanf("%hi %hi", &i, &j);
        m[i-1][j-1] = '#';
    }
    for (i = 0; i < n - 1; ++i) {
        for (j = 0; j < n - 1; ++j) {
            flag = 1;
            for (h = 1; flag && i + h < n + 1 && j + h < n + 1; ++h) {
                for (y = i; flag && y < i + h; ++y) {
                    for (x = j; flag && x < j + h; ++x) {
                        if (m[y][x] == '#') flag = 0;
                    }
                }
                if (flag && h > biggest) biggest = h;
            }
        }
    }
    printf("%d", biggest);
}

Try it online!

\$\endgroup\$

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