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\$

closed as unclear what you're asking by NoOneIsHere, Jo King, Sriotchilism O'Zaic, Οurous, Level River St Feb 8 at 7:47

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.

  • 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 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 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 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 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 at 12:31