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-23-2018, 03:28 PM   #35401
iversonian
Carpal \'Tunnel
 
iversonian's Avatar
 
Join Date: Sep 2003
Location: Donkversonian
Posts: 20,813
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

doesn't DFS do the job just as well?
iversonian is offline   Reply With Quote
Old 09-23-2018, 05:51 PM   #35402
Barrin6
Carpal \'Tunnel
 
Barrin6's Avatar
 
Join Date: Dec 2005
Location: beyond legal blindness
Posts: 6,878
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by Victor View Post
ya, in hindsight I should have just sat on my hands and waited for her to finish and go from there but jfc.
So this happens to us as well. One ticket someone is working on is required for the ticket you are doing. For our team we would had moved that ticket to ďblockedĒ and then picked up the next ticket. If there was no next ticket, I would reach out to the ticket owner and offered help. If nothing, thatís when I would pull the next ticket in the backlog.

Quote:
Originally Posted by iversonian View Post
doesn't DFS do the job just as well?
Yea DFS would had worked as well.
Barrin6 is offline   Reply With Quote
Old 09-23-2018, 08:24 PM   #35403
Larry Legend
Celtic Pride
 
Larry Legend's Avatar
 
Join Date: Jul 2009
Location: Kyrie's earth
Posts: 42,695
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Not speaking of how to handle this particular situation, but speaking to the optimal handling of this common scenario.

A slack message "Hey x, I'm working on TICKET#(link to ticket) and it is blocked by your TICKET#(link to ticket)".

Quickly discuss civilly the status of the blocking ticket.

If after convo you are still blocked, work on something else.


The civil discussion from the other persons side should basically always be 1) I'm working on it and want to continue, time is X or 2) I haven't got to it yet, have at it.
Larry Legend is offline   Reply With Quote
Old 09-23-2018, 08:35 PM   #35404
goofyballer
Carpal \'Tunnel
 
goofyballer's Avatar
 
Join Date: Jun 2005
Posts: 66,891
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by RustyBrooks View Post
Think of each cell in the grid as having all it's neighbors as children in a tree. So you can keep BFS searching your neighbors until there are no more leaves (land is leaves, water is dead ends). While doing the first BFS search mark every land you see as visited.

So you can start in cell 0, 0 and do a search. Then try 0,1 - if 0,1 is marked, then you can skip it. Keep going until you've marked the whole grid.

That's my first thought. It's O(n^2) though so I bet there's something better.
Quote:
Originally Posted by iversonian View Post
doesn't DFS do the job just as well?
None of this really makes sense to me, because I visualize trees as being very different from grids. Like, for this:

Quote:
Originally Posted by RustyBrooks View Post
Think of each cell in the grid as having all it's neighbors as children in a tree.
1,0 and 0,1 both have 1,1 as children, so that becomes weird in the context of traversal algorithms.

Going back to the potential solution I described earlier:

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
Would you describe this as BFS, DFS, or neither? (I think it's O(n) for some multiple of n but I'm not positive)
goofyballer is offline   Reply With Quote
Old 09-23-2018, 08:51 PM   #35405
Grue
Pooh-Bah
 
Grue's Avatar
 
Join Date: Mar 2004
Location: It is pitch black.
Posts: 5,638
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

How is it like 1/2 of the people ITT work at terrible places with awful people? Weird. My place isn't amazing but its certainly not a ****show. We just have people that do their jobs. IDK.
Grue is offline   Reply With Quote
Old 09-23-2018, 09:28 PM   #35406
OmgGlutten!
Pooh-Bah
 
OmgGlutten!'s Avatar
 
Join Date: Aug 2016
Posts: 4,996
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Ok, so it sounds like she is busy with whatever she thinks is important and is pissed that you don't understand the pecking order, which is that if your issue is being blocked by her issue, you stfu and remain silent until she submits her code and unblocks your issue because she is more senior and already knows that your issue is being blocked by her issue and has prioritized better uses of her time. And on top of that, she disagrees with the code you wrote to unblock the issue yourself.

I would find some outside mentors and have them review the code that you wrote and then the changes that she requested (for this issue and other issues) and try to determine if they agree with you or her and maybe they can have some insight into what you might be doing wrong or if she is just OCD.
OmgGlutten! is offline   Reply With Quote
Old 09-23-2018, 09:30 PM   #35407
suzzer99
Save the Cheerleader, Save the World
 
suzzer99's Avatar
 
Join Date: Nov 2005
Location: on top of the bell curve
Posts: 92,116
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Also breaking down tasks to the level of "you write a switch statement that calls templates" and "you write the template html" feels like it could be a little over-agile. If they're really that intertwined maybe just have one person handle it.
suzzer99 is offline   Reply With Quote
Old 09-23-2018, 09:40 PM   #35408
RustyBrooks
Carpal \'Tunnel
 
RustyBrooks's Avatar
 
Join Date: Feb 2006
Location: Austin, TX
Posts: 24,354
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by goofyballer View Post
None of this really makes sense to me, because I visualize trees as being very different from grids. Like, for this:



1,0 and 0,1 both have 1,1 as children, so that becomes weird in the context of traversal algorithms.
It's really a graph rather than a tree

Quote:
Going back to the potential solution I described earlier:

Would you describe this as BFS, DFS, or neither? (I think it's O(n) for some multiple of n but I'm not positive)
Whether this is BFS or DFS sort of depends on the nature of your recursion. You can reorder recursive visiting functions to turn them from BFS to DFS and back.

I honestly go back and forth a bit on whether it's O(n^2) or maybe it's better. Naively it's O(n^2) because you have to visit n cells and for each cell you have to find all connected pieces which is coupled to the size of n also. For a signifcant number of searches, you'll get to quit early - a lot of the ones you quit early, you get to quit in constant time (if the cell is already covered, or if all it's neighbors are covered). So the question is, are the constant-time cell visits proportional to n? So the real answer might be O(nlogn) or O(n sqrtn) or something. I don't think it can be O(n) though

On the ****ty job front: I mostly think of myself as having a "good job" and I sort of think of that of a lot of my past jobs too. But also, I have quit almost all the jobs I had because I didn't want to work there any more, so at least at some times, I've thought almost every job I had sucked. For me I guess I go through cycles, if other people are the same then I guess at some point a percentage of us will describe our jobs as ****ty.
RustyBrooks is offline   Reply With Quote
Old 09-23-2018, 09:47 PM   #35409
jjshabado
Carpal Tunnel
 
jjshabado's Avatar
 
Join Date: Jul 2006
Posts: 22,554
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by suzzer99 View Post
Also breaking down tasks to the level of "you write a switch statement that calls templates" and "you write the template html" feels like it could be a little over-agile. If they're really that intertwined maybe just have one person handle it.
Lol, yeah this part seems pretty crazy to me.
jjshabado is offline   Reply With Quote
Old 09-24-2018, 01:52 AM   #35410
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 interviewer didn't steer me towards implementing any recursive logic for this grid problem fwiw.
Craggoo is offline   Reply With Quote
Old 09-24-2018, 02:19 AM   #35411
goofyballer
Carpal \'Tunnel
 
goofyballer's Avatar
 
Join Date: Jun 2005
Posts: 66,891
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

I don't necessarily mean "recursive" literally, though it could be implemented that way - just that once you find an island, you check all neighbors (and their neighbors, and their neighbors) until you exhaust that island. You could do it iteratively with a queue of points to check also.

Thinking about it a little more, you could split the solution into two parts where the first part is straight O(n) - iterate over the whole grid, tag land squares with an ID from a rising counter you keep track of, if neighboring land tiles are already marked you can use the same ID as the neighbors - but, instead of exhausting an island when you hit it, just keep iterating linearly. Then have a second map that tracks the relationships between separate IDs, such that if you tag one peninsula of an island and then hit another peninsula that you tag with a different ID, eventually you run into a point where those IDs neighbor each other and you mark that they're part of the same island.

Then, when you finish iterating, you collapse the different IDs you've tagged into the number of islands, based on which ones border each other. I'm not sure exactly what that algorithm looks like without thinking more but it's probably not very complex.
goofyballer is offline   Reply With Quote
Old 09-24-2018, 04:47 AM   #35412
plexiq
veteran
 
Join Date: Apr 2007
Location: Vienna
Posts: 2,003
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Getting O(n log n) looks reasonably straightforward to me with the approach goofy mentioned, idk if it's possible to do better than that.

Rough idea for O(n log n): Assign an id to every land tile and keep track of connections to direct neighbors. Then iteratively merge connected tiles into blobs, keeping track of connections with other blobs. The minimum size of connected-but-not-yet-merged blobs doubles in each iteration, so we need O(log n) iterations to ensure we merge everything possible. Keeping an iteration at O(n) overall seems straightforward as both # tiles and # connections are clearly O(n).

Last edited by plexiq; 09-24-2018 at 04:55 AM.
plexiq is offline   Reply With Quote
Old 09-24-2018, 05:12 AM   #35413
Victor
Carpal \'Tunnel
 
Victor's Avatar
 
Join Date: Jul 2003
Posts: 61,322
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by suzzer99 View Post
Also breaking down tasks to the level of "you write a switch statement that calls templates" and "you write the template html" feels like it could be a little over-agile. If they're really that intertwined maybe just have one person handle it.
Yes this is the genesis of the issue. But you can guess who's idea that is and where I stand on it.
Victor is offline   Reply With Quote
Old 09-24-2018, 07:36 AM   #35414
Wolfram
Carpal \'Tunnel
 
Wolfram's Avatar
 
Join Date: Jan 2006
Location: You can be my wingman any time
Posts: 14,733
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

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

Not sure of the O-complexity. You're only visiting each square on the grid once and marking them, but I don't know how fast the "visit a random unvisited square" part is.
Wolfram is offline   Reply With Quote
Old 09-24-2018, 07:44 AM   #35415
plexiq
veteran
 
Join Date: Apr 2007
Location: Vienna
Posts: 2,003
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

The following is O(n log n):
Code:
Data structures:
	island_map: Simple array where island_map[tile] points to the corresponding island structure for that tile
	island:  a simple linked list of the tiles that are part of this island

initialize island_map to point to a separate 1x1 island object for each land tile
	
for each land tile:
	for each direct land neighbor of tile:
		if neighbor points to a different island:
			merge(island_map[tile], island_map[neighbor])
			
			
merge smaller island into bigger island, per # of tiles:
	larger.tiles.addAll(smaller.tiles)
	foreach tile : smaller.tiles
		update map[tile] pointer to the larger island
Maximum # of merge calls is O(n) as it's linear with the # of tiles, the merge itself consists of a constant time merge of the linked lists, and the update of the island pointer.

Complexity: Since only the tiles of the smaller merged island are updated, the size of the merged island is always at least twice as big as the number of updated tiles. This means any given tile can be updated at most log2(n) times, as the resulting island for the next merge would be larger than the # of total tiles. So we have at most O(n log n) tile updates total.
plexiq is offline   Reply With Quote
Old 09-24-2018, 10:30 AM   #35416
OmgGlutten!
Pooh-Bah
 
OmgGlutten!'s Avatar
 
Join Date: Aug 2016
Posts: 4,996
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

gl victor.
OmgGlutten! is offline   Reply With Quote
Old 09-24-2018, 10:37 AM   #35417
well named
poorly undertitled
 
well named's Avatar
 
Join Date: Jun 2007
Location: esse est coesse
Posts: 75,947
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by goofyballer View Post
Thinking about it a little more, you could split the solution into two parts where the first part is straight O(n) - iterate over the whole grid, tag land squares with an ID from a rising counter you keep track of, if neighboring land tiles are already marked you can use the same ID as the neighbors - but, instead of exhausting an island when you hit it, just keep iterating linearly. Then have a second map that tracks the relationships between separate IDs, such that if you tag one peninsula of an island and then hit another peninsula that you tag with a different ID, eventually you run into a point where those IDs neighbor each other and you mark that they're part of the same island.

Then, when you finish iterating, you collapse the different IDs you've tagged into the number of islands, based on which ones border each other. I'm not sure exactly what that algorithm looks like without thinking more but it's probably not very complex.
Quote:
Originally Posted by plexiq View Post
Getting O(n log n) looks reasonably straightforward to me with the approach goofy mentioned, idk if it's possible to do better than that.
Quote:
Originally Posted by plexiq View Post
The following is O(n log n)...
Nice!
well named is offline   Reply With Quote
Old 09-24-2018, 11:04 AM   #35418
jmakin
 
jmakin's Avatar
 
Join Date: Jan 2008
Location: Streaming
Posts: 28,506
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

The island problem wouldve been one of the more trivial problems in my computational geometry class but I canít think of a solution that isnít trivially much better than O(n)
jmakin is offline   Reply With Quote
Old 09-24-2018, 11:29 AM   #35419
plexiq
veteran
 
Join Date: Apr 2007
Location: Vienna
Posts: 2,003
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by jmakin View Post
The island problem wouldve been one of the more trivial problems in my computational geometry class but I can’t think of a solution that isn’t trivially much better than O(n)
Not sure what you mean here. The problem has a trivial lower bound at O(n), it's obvious that you can't possibly do any better than that because you already get there by merely processing the input definition for your n grid tiles.
plexiq is offline   Reply With Quote
Old 09-24-2018, 11:30 AM   #35420
jmakin
 
jmakin's Avatar
 
Join Date: Jan 2008
Location: Streaming
Posts: 28,506
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

I donít think itís obvious at all that you canít do better than that.
jmakin is offline   Reply With Quote
Old 09-24-2018, 11:46 AM   #35421
plexiq
veteran
 
Join Date: Apr 2007
Location: Vienna
Posts: 2,003
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

You propose that there may be an algorithmic solution where the worse case is better than O(n), meaning you can find the # of islands without at least reading a constant fraction of the input grid?

Counter example: If your input grid is a chessboard pattern, you clearly need to read every single tile, because flipping any given tile would change the # of islands. This already limits your worst case to be at least O(n).
plexiq is offline   Reply With Quote
Old 09-24-2018, 11:47 AM   #35422
suzzer99
Save the Cheerleader, Save the World
 
suzzer99's Avatar
 
Join Date: Nov 2005
Location: on top of the bell curve
Posts: 92,116
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

I'm fascinated by these kinds of problems that a kid can do with their eyes in a few seconds but telling a computer how do it is hard. It feels like there be some easier way to simulate what our brains can do. The bar graph holding water thing I posted is similar.

I guess the main issue is that when a kid starts the board already exists and land vs. sea is known to the kid. Whereas a computer has to ask about each square individually.

Well maybe not. If you assume the grid is created and the program already knows which is land and sea - why can't it find some way to "eyeball" it, like a kid would?
suzzer99 is offline   Reply With Quote
Old 09-24-2018, 11:48 AM   #35423
jmakin
 
jmakin's Avatar
 
Join Date: Jan 2008
Location: Streaming
Posts: 28,506
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

I said trivial better than O(n) Ė meaning by a constant factor. Lol. I wasnít implying or saying there is a log n solution even though there may be, I havenít thought about the ****ing problem enough clearly.
jmakin is offline   Reply With Quote
Old 09-24-2018, 12:37 PM   #35424
Wolfram
Carpal \'Tunnel
 
Wolfram's Avatar
 
Join Date: Jan 2006
Location: You can be my wingman any time
Posts: 14,733
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by suzzer99 View Post
I'm fascinated by these kinds of problems that a kid can do with their eyes in a few seconds but telling a computer how do it is hard. It feels like there be some easier way to simulate what our brains can do. The bar graph holding water thing I posted is similar.

I guess the main issue is that when a kid starts the board already exists and land vs. sea is known to the kid. Whereas a computer has to ask about each square individually.

Well maybe not. If you assume the grid is created and the program already knows which is land and sea - why can't it find some way to "eyeball" it, like a kid would?
I think you're underestimating how much went into teaching the kid how to do it. The billions of years of evolution for our eyes and brains to create the pattern recognition and reasoning ability to recognize distinct shapes and count them. And then the hundreds/thousands of days where the kid is constantly exposed to an environment that reinforces those evolutionary traits.

If you had a computer with a built in neural network, then it would figure it out for itself pretty quickly given the input/output parameters of the problem and a tester that would judge the output.

Last edited by Wolfram; 09-24-2018 at 12:47 PM.
Wolfram is offline   Reply With Quote
Old 09-24-2018, 01:54 PM   #35425
RustyBrooks
Carpal \'Tunnel
 
RustyBrooks's Avatar
 
Join Date: Feb 2006
Location: Austin, TX
Posts: 24,354
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by jmakin View Post
I said trivial better than O(n) Ė meaning by a constant factor. Lol. I wasnít implying or saying there is a log n solution even though there may be, I havenít thought about the ****ing problem enough clearly.
A constant factor times n is O(n), regardless of what the constant is.

What's the O(n) solution for this?
RustyBrooks 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 01:56 AM.


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