3
\$\begingroup\$

Pretty simple challenge here. Who can make the fastest algorithm (lowest time complexity) to determine whether or not the circle is "boxed in" given the following setup?

Input: Your program receives a pair of numbers (a,b) that denotes the position of a circle on a grid like this with arbitrary dimensions:

The grid

Where a-1 is the number of units from the right, and b-1 is the number of units from the bottom. Assume that (a,b) is always a white square. The program should work for arbitrary arrangements of purple squares .

Definition of "boxed in": A circle at S=(a,b) is "boxed in" if there is no path from S consisting of vertical, horizontal, and diagonal one space moves that reaches a white square on the edge of the grid without going on a purple space. This means that:

boxed in

is boxed in, but:

not boxed in

is not because of the open diagonal.

Output: A Boolean - is in boxed in, or not?

You can choose whatever data structure you want to represent the grid. Remember though, the goal is speed so keep that in mind.

[please note this is my first post on this SE site, so if I need to fix something let me know]

|improve this question
\$\endgroup\$
  • 3
    \$\begingroup\$ I see the input for the position of the circle, but how do we determine where the purple squares are? \$\endgroup\$ – Jo King Feb 8 '19 at 5:02
  • 2
    \$\begingroup\$ Welcome to PPCG. This is an interesting question but it needs to be more rigorously defined in order to run as a challenge here. In future you might want to post your challenge ideas to codegolf.meta.stackexchange.com/q/2140/15599 I would suggest that answering a few challenges would also help to identify what needs to be included in a spec \$\endgroup\$ – Level River St Feb 8 '19 at 7:46
  • 1
    \$\begingroup\$ I would also suggest that fastest algorithm is going to be difficult to tie break. What you are effectively looking for is a fill algorithm, and there are only a few fast ones out there. Time complexity rarely makes a good winning criterion. Fastest code is also unlikely to work unless you can provide very large test cases. I personally think codegolf (shortest code) would work best. \$\endgroup\$ – Level River St Feb 8 '19 at 7:50
  • \$\begingroup\$ OK thanks guys I'll fix the question after school. But to address @JoKing the input format for the purple squares is intended to be up to you (whatever is fastest for your program). Obviously I did not make this clear, that's my bad \$\endgroup\$ – sam-pyt Feb 8 '19 at 12:17
  • 1
    \$\begingroup\$ i think the problem is that you seemed to specify that the only input is a pair of numbers (a,b). I also just noticed you have two winning criterion tags code-challenge and fastest-algorithm. I assume you just want fastest-algorithm \$\endgroup\$ – Jo King Feb 8 '19 at 12:31