3
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:
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:
is boxed in, but:
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]
sam-pyt
Posted 2019-02-08T04:23:36.973
Reputation: 131
3I see the input for the position of the circle, but how do we determine where the purple squares are? – Jo King – 2019-02-08T05:02:31.437
2
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 https://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
– Level River St – 2019-02-08T07:46:49.3601I 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. – Level River St – 2019-02-08T07:50:13.190
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 – sam-pyt – 2019-02-08T12:17:43.060
1i 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 [tag:code-challenge] and [tag:fastest-algorithm]. I assume you just want [tag:fastest-algorithm] – Jo King – 2019-02-08T12:31:14.953