Surface puzzle discussion

The « No Land » problem is an optimisation one. « NoLand » is a good test case for the performance of your flood fill method, because it gives you the worst case scenario (ie maximum recursion depth, or max number of iteration).

Recursion for a BFS? :neutral_face:
Maybe but it might be ugly.

What’s the name of the maze generating algorithm that keeps track of un-connected sections with different ID numbers, and then joins them up when they connect? I remember reading about it somewhere. It scans down through a grid, row by row, and cell by cell to update its data structure. I was thinking something like that might be fun to implement, but can’t remember the name of it.

Edit:
Nevermind, found what I was looking for. The general class of algorithms is https://en.wikipedia.org/wiki/Connected-component_labeling. And one of the data structures used is https://en.wikipedia.org/wiki/Disjoint-set_data_structure. Looking forward to trying them out!

I used this algorithm for this puzzle. In fact, I did not know it before do the puzzle. It’s funny that I have done exactly as shown in the article by myself.
Thanks for the articles!

With the default code on test cases (except test #2), the number of coordinates to test given by " int N" is set to 32768 wich is wrong and not the case in others languages .

Instead of doing the BFS route, I focused on the “flood fill” and implemented a union-find solution.
Union-find is an algorithm that is used on Disjointed sets, which is perfect for flood fill scenarios.

Each “lake piece” is a node, and everytime a lake piece is found you connect the root of the found node to the roots of the nodes above, and/or to the left of it.
Connecting to roots will increase the size of root1. Root2’s root then becomes root1.
Doing this allowed me to read in and connect all the nodes in one swoop. There are some speed improvements that can be made here but even in an inefficient state, union-find is still quite fast.

2 Likes

How do you calculate the size of the region with union-find? Do you update it as you scan the data, or find it afterward?

1 Like

Is there a recursion limit? I get an error like the following only for test case #9:

at Answer.py. not in a function on line 19
at Answer.py. in expand on line 19
...
at Answer.py. in expand on line 19
at Answer.py. in <module> on line 37

(expand is the name of my recursive function)

In Python, yes, it’s internal.

There may be something no one has noticed before. The first four cases are symmetric in the sense that if someone accidentally switches the indices of the double indexed array (definitely not me, for the fifth time :frowning:), but has an otherwise working algorithm, will perfectly pass. I spent about the same time trying to figure out why my program doesn’t work as the time I spent writing it. Good advice: map[i,j] != map[j,i] in general. :slight_smile:

1 Like

Hi, just got 100% in C++ with plain BFS without any optimizations.
Feel like I have cheated :slight_smile:

Look at the other solutions, you are not the only one who “cheated” this way :slight_smile:

This puzzle IMHO is too easy for 250xp. Simple BFS gets it done, whereas even skynet 1 required a more careful algo for 150xp

2 Likes

If that’s true, then my code should do very well on it, because it uses an RLE representation of the landscape. Big areas of water are ideal for it, and it runs very fast on the big test cases in the IDE. The slowest one is “100 tests on a 1000x1000 map” at 177ms, due simply to the large number of points tested; “large map, large lake” completes in only 6ms.

Yet “No Land” in the validation suite fails for my Lua solution, and I have no idea why.

I just wrote another solution in C++, and that passes all the tests. (It uses a different algorithm based on sets instead of flood-filling.) I’m left wondering if there’s something funny about that particular test case that mis-parses in Lua.

Can someone please check this code. I implemented the floodfill using the Queues. It shows TLE in the last testcase

import java.util.*;
import java.io.*;
import java.math.*;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
class Solution {

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int L = in.nextInt();
        int H = in.nextInt();
        
        char[][]  q  = new char[H][L];
        int ctr;
        ArrayDeque<Integer[]> aq = new ArrayDeque<Integer[]>();
        ArrayList<Integer[]> checked = new ArrayList<Integer[]>();
        
        
        if (in.hasNextLine()) {
            in.nextLine();
        }
        for (int i = 0; i < H; i++) {
            q[i] = in.nextLine().toCharArray();
        }
        
        int N = in.nextInt();
        int[][] cood = new int[N][2];
        
        for (int i = 0; i < N; i++) {
            cood[i][1] = in.nextInt();
            cood[i][0] = in.nextInt();
        }
        int[] co = new int[]{-1,0,1};
        
        
        
        //System.err.println(N);
        
        for (int k = 0; k < N; k++) {
        aq.clear();
        Integer[] SI = new Integer[]{cood[k][0],cood[k][1]};
        checked.clear();
        ctr = 0;
        //System.err.println(q[SI[0]][SI[1]]);
        if(q[SI[0]][SI[1]]=='O'){ctr++;checked.add(SI);
        
        aq.push(SI);
        do
        {
            
            SI = aq.pollLast();
            
            for(int i = 0;i<3;i++)
            for(int j = 0;j<3;j++)
            
            {
                Integer[] tmp = null;
                if(Math.abs(co[i])!=Math.abs(co[j]))
                {
                    tmp = new Integer[]{SI[0]+co[i],SI[1]+co[j]};
                    try
                    
                    {
                        if(q[tmp[0]][tmp[1]]=='O' && notIn(checked,tmp))
                        {
                            
                            //System.err.println("Trying : "+(SI[0]+co[i])+","+(SI[1]+co[j]));
                            aq.push(tmp);
                            checked.add(tmp);
                            ctr++;
                        }
                    }
                    catch(Exception e)
                    {}
                    
                }
                    
                }
                
                
            
            }
        while(aq.peekLast()!=null);
        }
        System.out.println(ctr);
        }
            }
        
    
    
    public static boolean notIn(ArrayList<Integer[]> a, Integer[] q)
    {
        for(Integer[] i : a)
        {
            if(Arrays.equals(i,q))
            return false;
            }
            return true;
        }
}

Looks like your code does not store the lake size. That might be what you are missing. So if a lake is composed of 3 squares (0, 0), (0, 1), (1,0) and you are asked to check the size of lake starting at (0, 0) and (0, 1) … are you going to run your flood-fill algorithm twice?

Hi all.
I didn’t have to do anything special for very large lakes. My approach was able to calculate them all.
I also didn’t calculate anything that wasn’t requested.
I have an array of request numbers initialized to 0 (in C), and an array of integers for map cells, but I store the area in the request array and I store the request number in the map array.
If a cell has water, its map cell is set to -1.
As soon as a cell is requested, if its value is still -1, it is set to the request number. Its neighbors are all checked (via queue / circular buffer), and any that are -1 are added to the queue and set to the request number, and the area is incremented by 1 (being stored in the request array at [reqnumber].
So all cells connected to any cell that has previously been searched will send you to the same value.
Worked on all tests and submission without the need to check for >97% water or such tricks.
Have fun!

1 Like

Passing the last test on this one was not easy for me. I was using a recursive function going from the target coordinates and propagating to the neighboors until there is no water with a system of cache to avoid doing the recalculations for area I explored already, but it was way to heavy.

I had to start again from the beginning and I changed completly my approach, making a first scan of the full map to generate all the cluster via two dictionnaries: one that memorise the label attributed to a coordinate (x,y), and one that cache the list of all coordinates linked to a label.

This method was way more efficient than my original approach.

TBH I’m not sure if the tag “Recursion” is appropriate for this puzzle. It’s perfectly solvable without and rarely (only on specific languages/with specific optimizations) solvable with recursion.

Also, I agree with Surface puzzle discussion - #55 by CyberLemonade - this puzzle looks a bit too easy for 250xp. Not that I’m complaining… :slight_smile:

1 Like

Has anyone solved this puzzle using Python ?
I coded BFS (using list and then using dictionary) but i can not pass the final test due to time limit…
And i dont see how to optimize my code…