I have a 3D array with booleans and I need to check if there are \"lines\" that
ID: 645888 • Letter: I
Question
I have a 3D array with booleans and I need to check if there are "lines" that all contain true or false. With lines I mean horizontally, vertically and diagonally within the array. However I only need to check this when an element changes and I know the location of the changed element. The array is always equal on all 3 sides/dimensions.
I am looking for an efficient way to traverse the possible direction from the element that changed. What I'm currently doing is to first check the straight lines x, y and z which are easy. Then i check for the 2 horizontal diagonals:
if (element.x + element.y == arraySize || element.x == element.y)
//Only now there can be a full diagonal line
And that for each side (x, y and z). Now I only need the 4 complete diagonals accros the array. But I'm wondering if there is a clever trick to make this more efficient.
Explanation / Answer
From a theoretical standpoint, there's not a whole lot you can do because whether or not one line contains all trues or all falses doesn't tell you much about whether the other lines do, i.e. you have to "check all of them" no matter what.
What you can do is make sure you don't check anything twice. If you check whether there's a line from (0,0,0) to (8,8,8), then you should not also check whether there's a line from (8,8,8) to (0,0,0) later in your algorithm. For example, when checking for horizontal and vertical lines, only do the checks for three of the six sides of your cube.
The data structure you use is probably the most important factor in practice. You obviously need random access since the "lines" go in several different directions, so an ArrayList would be a lot better than a LinkedList (though I'm guessing you knew that already).
If those generic tips aren't enough, then we'd have to start talking about things like the actual size of your cube, the exact code you've tried, how you measured its performance, how the trues or falses tend to be distributed, and so on.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.