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?

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:

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

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?