Two Plus Two Poker Forums ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **
 Register FAQ Search Today's Posts Mark Forums Read TwoPlusTwo.com

 Notices The Theory of Poker Applied to No-Limit now available For those of you here in Las Vegas, The Theory of Poker Applied to No-Limit by David Sklansky is now available at Gambler’s General Store/ GAMBLER'S BOOK CLUB in downtown Las Vegas. Their address is 727 S Main St, Las Vegas, NV 89101 and their phone number is (702) 382-9903. We also have this title available in several special poker book promotions directly from Two Plus Two Publishing. For more info or to ask questions check out this thread in the books and publications forum: Sklansky Invites Reviews, Comments, And Questions, About Theory of Poker Applied To No Limit .

 09-24-2018, 04:16 PM #35426 Larry Legend Celtic Pride     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.
09-24-2018, 04:19 PM   #35427
goofyballer
Carpal \'Tunnel

Join Date: Jun 2005
Posts: 66,953
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
 Originally Posted by Wolfram 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.

09-24-2018, 04:24 PM   #35428
goofyballer
Carpal \'Tunnel

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 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

 09-24-2018, 04:30 PM #35429 jjshabado Carpal Tunnel     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).
 09-24-2018, 04:32 PM #35430 well named poorly undertitled     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
09-24-2018, 04:42 PM   #35431
jmakin

Join Date: Jan 2008
Location: Streaming
Posts: 28,690
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
 Originally Posted by RustyBrooks 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.

09-24-2018, 04:43 PM   #35432
jmakin

Join Date: Jan 2008
Location: Streaming
Posts: 28,690
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
 Originally Posted by RustyBrooks 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.

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 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.

 09-24-2018, 05:01 PM #35434 Craggoo culled     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
09-24-2018, 05:22 PM   #35435
Carpal Tunnel

Join Date: Jul 2006
Posts: 22,571
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
 Originally Posted by well named 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..
........```

09-24-2018, 06:01 PM   #35436
goofyballer
Carpal \'Tunnel

Join Date: Jun 2005
Posts: 66,953
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
 Originally Posted by jjshabado 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.

09-24-2018, 06:58 PM   #35437
Carpal Tunnel

Join Date: Jul 2006
Posts: 22,571
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
 Originally Posted by goofyballer 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.

09-24-2018, 07:19 PM   #35438
RustyBrooks
Carpal \'Tunnel

Join Date: Feb 2006
Location: Austin, TX
Posts: 24,485
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
 Originally Posted by jmakin You just naively visit every tile in the grid.
And do what?

09-24-2018, 07:23 PM   #35439
RustyBrooks
Carpal \'Tunnel

Join Date: Feb 2006
Location: Austin, TX
Posts: 24,485
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
 Originally Posted by goofyballer 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

09-24-2018, 07:25 PM   #35440
PJo336
THRILLHOUSE!

Join Date: Mar 2007
Posts: 21,945
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
 Originally Posted by RustyBrooks And do what?
So naive

09-24-2018, 07:59 PM   #35441
jmakin

Join Date: Jan 2008
Location: Streaming
Posts: 28,690
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
 Originally Posted by RustyBrooks 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

 09-24-2018, 08:06 PM #35442 well named poorly undertitled     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
 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; }```
 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.)
 09-24-2018, 09:12 PM #35445 jmakin debauchery and general idiocy     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.
 09-24-2018, 09:18 PM #35446 jmakin debauchery and general idiocy     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.
 09-24-2018, 09:21 PM #35447 RustyBrooks Carpal \'Tunnel     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.
09-24-2018, 10:48 PM   #35448
goofyballer
Carpal \'Tunnel

Join Date: Jun 2005
Posts: 66,953
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
 Originally Posted by RustyBrooks 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.

 09-24-2018, 11:35 PM #35449 RustyBrooks Carpal \'Tunnel     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 ****...
 09-24-2018, 11:42 PM #35450 jjshabado Carpal Tunnel     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.

 Thread Tools Display Modes Linear Mode

 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 Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Links to Popular Forums     News, Views, and Gossip     Beginners Questions     Marketplace & Staking     Casino & Cardroom Poker     Internet Poker     NL Strategy Forums     Poker Goals & Challenges     Las Vegas Lifestyle     Sporting Events     Other Other Topics Two Plus Two     About the Forums     Two Plus Two Magazine Forum     The Best of Two Plus Two Marketplace & Staking     Commercial Marketplace     General Marketplace     Staking - Offering Stakes     Staking         Staking - Offering Stakes         Staking - Seeking Stakes         Staking - Selling Shares - Online         Staking - Selling Shares - Live         Staking Rails         Transaction Feedback & Disputes     Transaction Feedback & Disputes Coaching & Training     Coaching Advice     Cash Game Poker Coach Listings     Tournament/SNG Poker Coach Listings Poker News & Discussion     News, Views, and Gossip     Poker Goals & Challenges     Poker Beats, Brags, and Variance     That's What She Said!     Poker Legislation & PPA Discussion hosted by Rich Muny     Twitch - Watch and Discuss Live Online Poker     Televised Poker General Poker Strategy     Beginners Questions     Books and Publications     Poker Tells/Behavior, hosted by: Zachary Elwood     Poker Theory     Psychology No Limit Hold'em Strategy     Medium-High Stakes PL/NL     Micro-Small Stakes PL/NL     Medium-High Stakes Full Ring     Micro-Small Stakes Full Ring     Heads Up NL     Live Low-stakes NL Limit Texas Hold'em Strategy     Mid-High Stakes Limit     Micro-Small Stakes Limit Tournament Poker Strategy     STT Strategy     Heads Up SNG and Spin and Gos     Mid-High Stakes MTT     Small Stakes MTT     MTT Community     Tournament Events Other Poker Strategy     High Stakes PL Omaha     Small Stakes PL Omaha     Omaha/8     Stud     Draw and Other Poker Live Poker     Casino & Cardroom Poker         Venues & Communities         Regional Communities     Venues & Communities     Tournament Events         WPT.com     Home Poker     Cash Strategy     Tournament Strategy Internet Poker     Internet Poker         Global Poker         MPN – Microgaming Poker Network         BetOnline.ag Online Poker     Commercial Software     Software         Commercial Software         Free Software General Gambling     Backgammon Forum hosted by Bill Robertie.     Probability     Sports Betting     Other Gambling Games 2+2 Communities     Other Other Topics         OOTV         Game of Thrones     The Lounge: Discussion+Review     EDF     Las Vegas Lifestyle     BBV4Life         omg omg omg     House of Blogs Sports and Games     Sporting Events         Single-Team Season Threads         Fantasy Sports     Fantasy Sports         Sporting Events     Wrestling     Golf     Chess and Other Board Games     Video Games         League of Legends         Hearthstone     Puzzles and Other Games Other Topics     Politics and Society     History     Business, Finance, and Investing     Science, Math, and Philosophy     Religion, God, and Theology     Travel     Health and Fitness     Laughs or Links!     Computer Technical Help     Programming

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

 Contact Us - Two Plus Two Publishing LLC - Privacy Statement - Top