Two Plus Two Publishing LLC
Two Plus Two Publishing LLC
 

Go Back   Two Plus Two Poker Forums > >

Notices

Programming Discussions about computer programming

Reply
 
Thread Tools Display Modes
Old 09-24-2018, 04:16 PM   #35426
Larry Legend
Celtic Pride
 
Larry Legend's Avatar
 
Join Date: Jul 2009
Location: Kyrie's earth
Posts: 42,763
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

The only thing I can think is if there is somehow some trick as to knowing the width and height that you could create some type of key to determine how many islands there are based on the number of land spaces. Like "this is a 5x5 island with 11 land spaces, check these 10 spaces to see if they are land or island and you'll know how many islands total there are"

But I'm sure that's a terrible idea.
Larry Legend is offline   Reply With Quote
Old 09-24-2018, 04:19 PM   #35427
goofyballer
Carpal \'Tunnel
 
goofyballer's Avatar
 
Join Date: Jun 2005
Posts: 66,953
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by Wolfram View Post
re: the island problem.

What about something like this:

1. Pick a random unvisited point on the grid
2. If it is water, mark it as visited and goto 1
3. If it is land, mark it as visited then:
3.1 walk north and mark each land point as visited until you reach the water
3.2 walk south and mark each land point as visited until you reach the water
3.3 move east one square and repeat 3.1 and 3.2, repeat until you reach the eastern "shore"
3.4 move west and repeat 3.1 and 3.2, repeat until you reach the western "shore"
4. When you've exhausted that current island of visited land, increment the island counter by 1
Take this grid:

Code:
xxxx
___x
_xxx
_xxx
If you start in the bottom part of the island, this misses the top. You'd have to iterate in all directions from all tiles in order to get weird formations like that.
goofyballer is offline   Reply With Quote
Old 09-24-2018, 04:24 PM   #35428
goofyballer
Carpal \'Tunnel
 
goofyballer's Avatar
 
Join Date: Jun 2005
Posts: 66,953
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

From a complexity standpoint, this feels more O(n) to me, especially if the "recursive" part is implemented iteratively:

Quote:
Originally Posted by goofyballer View Post
With no regard for complexity/speed, first thing that comes to mind is...
- for each spot in the grid, mark if it's visited/unvisited
- iterate over the grid, if you hit an unvisited land piece, do islands++ and then recursively mark every bordering land piece "visited" to exhaust that island
It needs more memory space too, and generally feels sloppier than the n log n solution discussed above. But...it might be faster, because the number of repeated iterations over squares (to mark all of an island as "visited" when you first encounter it) should be constant, making it O(n)?

I'm glad we're having this discussion here because I'm sure I'd sound like an idiot if it was instead happening in an interview room
goofyballer is offline   Reply With Quote
Old 09-24-2018, 04:30 PM   #35429
jjshabado
Carpal Tunnel
 
jjshabado's Avatar
 
Join Date: Jul 2006
Posts: 22,571
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

I agree that it feels like there's an O(n) solution - maybe around clever "merging" of islands.

goofy, I don't think your solution is necessarily O(n) because of pathological cases like circular islands with water and islands inside of them. So you have to look at every point at least once and you'd need some really clever way to know when there are unexplored spaces in the middle of the island (as opposed to just looking again).
jjshabado is offline   Reply With Quote
Old 09-24-2018, 04:32 PM   #35430
well named
poorly undertitled
 
well named's Avatar
 
Join Date: Jun 2007
Location: esse est coesse
Posts: 76,609
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

One question I had is whether or not it needs to count islands which are interior to some land surface, e.g. there's a big chunk of land with a lake in the middle and an island in the lake.

If not, then I think you could potentially (at least in some cases?) avoid visiting every cell by following edges. If you do need to count them, then you probably have to visit every cell? Although there if you work from the outside edges in, there might be some way of avoiding visiting a couple of the most central cells.

Last edited by well named; 09-24-2018 at 04:33 PM. Reason: jinx
well named is offline   Reply With Quote
Old 09-24-2018, 04:42 PM   #35431
jmakin
 
jmakin's Avatar
 
Join Date: Jan 2008
Location: Streaming
Posts: 28,690
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by RustyBrooks View Post
A constant factor times n is O(n), regardless of what the constant is.



What's the O(n) solution for this?


You just naively visit every tile in the grid.
jmakin is offline   Reply With Quote
Old 09-24-2018, 04:43 PM   #35432
jmakin
 
jmakin's Avatar
 
Join Date: Jan 2008
Location: Streaming
Posts: 28,690
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by RustyBrooks View Post
A constant factor times n is O(n), regardless of what the constant is.



What's the O(n) solution for this?


Iím aware how logarithmic complexity works, thanks.
jmakin is offline   Reply With Quote
Old 09-24-2018, 04:48 PM   #35433
plexiq
veteran
 
Join Date: Apr 2007
Location: Vienna
Posts: 2,030
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by jmakin View Post
You just naively visit every tile in the grid.
That's not a solution by itself. The chessboard pattern example just shows that it's a requirement for any possible solution to visit all tiles, at least for some inputs.

Agree that this feels more like O(n) in any case. I guess you can simply build an undirected graph of land connections from the given grid in O(n) and then count the number of connected components in that graph, again at O(n). That's no fun though

Last edited by plexiq; 09-24-2018 at 04:54 PM.
plexiq is offline   Reply With Quote
Old 09-24-2018, 05:01 PM   #35434
Craggoo
culled
 
Craggoo's Avatar
 
Join Date: Sep 2006
Location: R.I.P. ItzPenzoo 12-09-11
Posts: 12,533
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

My solution (not one I said during interview):

Code:
var visited = {}
var map = [
	[0, 1, 0, 1, 1, 1, 0],
	[1, 0, 0, 1, 1, 0, 1],
	[1, 1, 0, 0, 1, 1, 0]
]
var count = 0

function traverse(x, y) {
	visited[x + ',' + y] = true
	/** Checking right nodes */
	if ((x + 1 < map.length) && map[x + 1][y] === 1 && !visited[(x + 1) + ',' + y]) {
		traverse(x + 1, y)
	}
	/** Checking left nodes */
	if ((x - 1 >= 0) && map[x -1][y] === 1 && !visited[(x - 1) + ',' + y]) {
		traverse(x - 1, y)
	}
	/** Checking top nodes */
	if ((y + 1 < map[x].length) && map[x][y + 1] === 1 && !visited[x + ',' + (y + 1)]) {
		traverse(x, y + 1)
	}
	/** Checking bottom nodes */
	if ((y - 1 >= 0) && map[x][y - 1] === 1 && !visited[x + ',' + (y - 1)]) {
		traverse(x, y - 1)
	}
}

for (var i=0; i<map.length; i++) {
	for (var j=0; j<map[i].length; j++) {
		/** This node has been visited by traverse already or is not part of an island. Can be skipped */
		if (visited[i + ',' + j] || map[i][j] === 0) {
			continue;
		}
		/** This would indicate a new island that hasn't been traversed */
		if (!visited[i + ',' + j] && map[i][j] === 1) {
			count ++
			traverse(i, j)
		}
	}
}
Craggoo is offline   Reply With Quote
Old 09-24-2018, 05:22 PM   #35435
jjshabado
Carpal Tunnel
 
jjshabado's Avatar
 
Join Date: Jul 2006
Posts: 22,571
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by well named View Post
If not, then I think you could potentially (at least in some cases?) avoid visiting every cell by following edges. If you do need to count them, then you probably have to visit every cell? Although there if you work from the outside edges in, there might be some way of avoiding visiting a couple of the most central cells.
My intuition is to think of this problem in the case of edges. So I think you need to visit every tile because of the crazy scenarios, but if you think about edges it seems like you could pretty easily build up and count islands as you go through the grid from top-bottom, left-right.

You need a clever "merging" approach though to make sure you handle cases like below - but I think you could do it in constant time with sets/mapping tables or something.


Code:
 ........
 ..x..x..
 ..x..x..
 ..xxxx..
 ........
jjshabado is offline   Reply With Quote
Old 09-24-2018, 06:01 PM   #35436
goofyballer
Carpal \'Tunnel
 
goofyballer's Avatar
 
Join Date: Jun 2005
Posts: 66,953
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by jjshabado View Post
goofy, I don't think your solution is necessarily O(n) because of pathological cases like circular islands with water and islands inside of them. So you have to look at every point at least once and you'd need some really clever way to know when there are unexplored spaces in the middle of the island (as opposed to just looking again).
You'd definitely have to look at every point multiple times, but O(xn) is still O(n). Internal islands wouldn't be a problem, the outer island would be hit first and covered, then further iteration (ignoring visited land tiles, like the outer island you already marked) would eventually run into the inner island, which would still be unvisited.
goofyballer is offline   Reply With Quote
Old 09-24-2018, 06:58 PM   #35437
jjshabado
Carpal Tunnel
 
jjshabado's Avatar
 
Join Date: Jul 2006
Posts: 22,571
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by goofyballer View Post
You'd definitely have to look at every point multiple times, but O(xn) is still O(n). Internal islands wouldn't be a problem, the outer island would be hit first and covered, then further iteration (ignoring visited land tiles, like the outer island you already marked) would eventually run into the inner island, which would still be unvisited.


Yeah, I was thinking you could be visiting tiles many times, but it would just be twice.
jjshabado is offline   Reply With Quote
Old 09-24-2018, 07:19 PM   #35438
RustyBrooks
Carpal \'Tunnel
 
RustyBrooks's Avatar
 
Join Date: Feb 2006
Location: Austin, TX
Posts: 24,485
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by jmakin View Post
You just naively visit every tile in the grid.
And do what?
RustyBrooks is offline   Reply With Quote
Old 09-24-2018, 07:23 PM   #35439
RustyBrooks
Carpal \'Tunnel
 
RustyBrooks's Avatar
 
Join Date: Feb 2006
Location: Austin, TX
Posts: 24,485
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by goofyballer View Post
You'd definitely have to look at every point multiple times, but O(xn) is still O(n). Internal islands wouldn't be a problem, the outer island would be hit first and covered, then further iteration (ignoring visited land tiles, like the outer island you already marked) would eventually run into the inner island, which would still be unvisited.
Yeah I think your solution works. I thought this would be worse than O(n) because the size of islands is unknown, but there can't be more than N island spaces, so your "recursive" island search should never happen more than n times cumulatively. There's never a case where you need to visit a square more than twice
RustyBrooks is offline   Reply With Quote
Old 09-24-2018, 07:25 PM   #35440
PJo336
THRILLHOUSE!
 
PJo336's Avatar
 
Join Date: Mar 2007
Posts: 21,945
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by RustyBrooks View Post
And do what?
So naive
PJo336 is offline   Reply With Quote
Old 09-24-2018, 07:59 PM   #35441
jmakin
 
jmakin's Avatar
 
Join Date: Jan 2008
Location: Streaming
Posts: 28,690
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by RustyBrooks View Post
And do what?


Note if itís an island tile or not? Sorry, Iím probably misunderstanding the problem. Iím juggling too many things at once
jmakin is offline   Reply With Quote
Old 09-24-2018, 08:06 PM   #35442
well named
poorly undertitled
 
well named's Avatar
 
Join Date: Jun 2007
Location: esse est coesse
Posts: 76,609
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

It would be appropriate if it at least one of those things were a PiŮa Colada
well named is offline   Reply With Quote
Old 09-24-2018, 08:31 PM   #35443
caringfleece
newbie
 
Join Date: Sep 2018
Posts: 29
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Craggoo posted the depth first solution. Here is the breadth first. Uses a queue instead of recursion. It also uses a 2d array to store the visited squares instead of a hashmap. The solution is O(n).

Code:
function countIslands(islandGrid) {
    let islandCount = 0;

    let visitedGrid = [];

    islandGrid.forEach(row => {
        zeroRow = row.map(elm => 0);
        visitedGrid.push(zeroRow);
    });

    for (let row = 0; row < islandGrid.length; row++) {
        for (let col = 0; col < islandGrid[row].length; col++) {
            //if square is land and not visited
            if  (islandGrid[row][col] === 1 && visitedGrid[row][col] === 0) {
                islandCount += 1;
                let queue = [[row, col]];
                
                while (queue.length > 0) {
                    let current = queue.shift();
                    let currentRow = current[0];
                    let currentCol = current[1];


                    //mark square as visited
                    visitedGrid[currentRow][currentCol] = 1;

                    //check if square is on grid, is land, is not visited

                    //e
                    if (currentCol + 1 < islandGrid[currentRow].length 
                            && islandGrid[currentRow][currentCol + 1] === 1 
                            && visitedGrid[currentRow][currentCol + 1] === 0) {
                        queue.push([currentRow, currentCol + 1]);
                    }

                    //s
                    if (currentRow + 1 < islandGrid.length
                            && islandGrid[currentRow + 1][currentCol] === 1
                            && visitedGrid[currentRow + 1][currentCol] === 0) {
                        queue.push([currentRow + 1, currentCol]);
                    }

                    //w
                    if (currentCol - 1 >= 0 
                        && islandGrid[currentRow][currentCol - 1] === 1 
                        && visitedGrid[currentRow][currentCol -1] === 0) {
                    queue.push([currentRow, currentCol -1]);
                    }

                    //n
                    if (currentRow - 1 >= 0 
                        && islandGrid[currentRow -1][currentCol] === 1
                        && visitedGrid[currentRow - 1][currentCol] === 0) {
                        queue.push([currentRow - 1, currentCol]);
                    }


                }
            }
        }
    }
    
    return islandCount;
}
caringfleece is offline   Reply With Quote
Old 09-24-2018, 08:43 PM   #35444
caringfleece
newbie
 
Join Date: Sep 2018
Posts: 29
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

From a naming point of view I would make a distinction between an "island" and "land". An island is made up of land but they are not the same.


(The problem is to count how many islands there are.
Each tile can be land or water.)
caringfleece is offline   Reply With Quote
Old 09-24-2018, 09:12 PM   #35445
jmakin
 
jmakin's Avatar
 
Join Date: Jan 2008
Location: Streaming
Posts: 28,690
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

If you visit every tile once you have all the information you need to determine how many islands there are. That should be obvious, unless I'm REALLY missing something.

On each tile visit you can just note if it has an adjacent unvisited island tile. give them a label. You're basically just trying to find how many connected components in a graph there are, which is a very old and very solved problem.
jmakin is offline   Reply With Quote
Old 09-24-2018, 09:18 PM   #35446
jmakin
 
jmakin's Avatar
 
Join Date: Jan 2008
Location: Streaming
Posts: 28,690
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

So I pushed really hard the last several weeks to refactor the way we do our CI/CD pipeline. We use jenkins. We have full on, 200+ line test scripts that we put directly into the jenkins build UI. Needless to say they are a nightmare to maintain, there is some rudimentary version control but it's all through the UI and impossible to alter via command line.

After spending 2 ****ing weeks fixing a problem that should have taken me 20 minutes, me and my deskmate decided we desperately needed to refactor this ****. So, he had a good idea for creating a repo just for our test scripts. He has it staged in a really great way that makes script development/maintenance a breeze. So we can just dump all our testing scripts into that repo, and on Jenkins, just have 4-5 liners of code using that repo that run off our triggers. Super easy to maintain and honestly is how we should've been doing it all along.

Man it was a ****ing hard sell. But I got us to do it and it's working SO well. I am so proud, and my desk mate is totally over the moon about it. People don't usually listen to him but he's our main devops guy and he actually is pretty savvy so I figured we should start listening to him. I helped develop a lot of the supporting scripts and spent a lot of time on it. Super nervous it'll break but the abstraction seems really good and easy to understand so I think it'll be fine. It's extremely modular and well designed.
jmakin is offline   Reply With Quote
Old 09-24-2018, 09:21 PM   #35447
RustyBrooks
Carpal \'Tunnel
 
RustyBrooks's Avatar
 
Join Date: Feb 2006
Location: Austin, TX
Posts: 24,485
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

You algorithm won't entirely work - you'll have to go back and fix some islands after the fact. Let's say X is land and . is water. Consider this graph

Code:
X.X
X.X
XXX
If you go left to right you'll conclude that the Xs in the first row constitute 2 different islands, because they don't yet appear connected. That's why you'd want to do a search.

I think you could use your approach and then go over it again and resolve/merge islands, but it's not as straightforward as you laid out. I haven't thought about it too much but I think just a second pass would be required.

Actually, no, you know what, the 2nd pass would need to do a DFS or BFS to rename all the components that needed renaming. Like consider, with your algorithm after the first pass, you'd have

Code:
1.2
1.2
112
(or maybe the bottom right would be a 1, but you see what I mean, just depends on how you write it)

You could go through and look for adjacent squares that have different numbers, but as in this case, you'd have to expand to find all the "2"s that needed changing.
RustyBrooks is offline   Reply With Quote
Old 09-24-2018, 10:48 PM   #35448
goofyballer
Carpal \'Tunnel
 
goofyballer's Avatar
 
Join Date: Jun 2005
Posts: 66,953
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by RustyBrooks View Post
Actually, no, you know what, the 2nd pass would need to do a DFS or BFS to rename all the components that needed renaming. Like consider, with your algorithm after the first pass, you'd have

Code:
1.2
1.2
112
(or maybe the bottom right would be a 1, but you see what I mean, just depends on how you write it)

You could go through and look for adjacent squares that have different numbers, but as in this case, you'd have to expand to find all the "2"s that needed changing.
The second solution solution I came up with was basically like this, except that at the point where the 1 intersects the 2, you'd note the intersection, store it in a map of island connectivity, and have a step at the end where you merge your connected IDs into distinct island groups (so, here, your data structure for connections would note that 1 and 2 are connected and thus represent a single island). I don't think going back and renaming things is useful.

I suspect this is O(n) for the iteration plus a log(n) merge at the end.
goofyballer is offline   Reply With Quote
Old 09-24-2018, 11:35 PM   #35449
RustyBrooks
Carpal \'Tunnel
 
RustyBrooks's Avatar
 
Join Date: Feb 2006
Location: Austin, TX
Posts: 24,485
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

This may be obvious to those of you who use AWS, but, although I knew "reserved EC2 instances" were cheaper, I did not quite realize they were like... 2/3 cheaper. So today I reserved 2 of them for personal project. I opted to spend the same amount but get about 4x the performance. I was using t2.smalls and running out of CPU credits a lot.

If you're using AWS and you feel confident about what instances you need, reserve that ****...
RustyBrooks is offline   Reply With Quote
Old 09-24-2018, 11:42 PM   #35450
jjshabado
Carpal Tunnel
 
jjshabado's Avatar
 
Join Date: Jul 2006
Posts: 22,571
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

This is where the google model is way better. No up front capacity planning and reservations necessary and instead you get good usage based discounts.
jjshabado is offline   Reply With Quote

Reply
      

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off


Forum Jump


All times are GMT -4. The time now is 10:15 PM.


Powered by vBulletin®
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright © 2008-2017, Two Plus Two Interactive
 
 
Poker Players - Streaming Live Online