Programming question/exercise

Different55 · 2015-07-26 19:15:18

Okay so I'm working on a personal project at the moment and I'm just a little bit stuck. I've got this:

################################################################################
#################..##########.....#########...##......##.######...............##
###..#######........#######.......########............##..######...............#
##....#####.........#######........######..........#####..######...............#
##....#####.........#######........######.........##############...............#
##.....####.........########........######.........############................#
##.....####........##########..........####.........##########.................#
##.....####.......###############.......##..........##########.................#
##....#####.......################..................###########................#
##...#####........#################.................###########...............##
#.................########..########...............############..............###
#.................#######....########.............#############..........##.####
#..................######.....########...........##############.........########
#....................####.....########...........##############.........########
##...##...............###.....########...........##############..........#######
##....................###....#########..........################..........######
##.....................##...#########...........#################..........#####
##.....................##############..........##################..........#####
##......................#############.....#######################..........#####
##..............##.......############....#########################.........#####
#..............####.......############..###########################.........####
#..............#####........###..#####################################......####
#...............#####............#####################################.....#####
#..................###...........#####################################.....#####
##..................###...........####################################.....#####
##..................####...........###################################.....#####
#...................####............###################################....#####
##............##....#####...........###################################....#####
###..........##############...###..#####################################..######
################################################################################

This is a map represented by a 2D array. My program generates these, but sometimes it leaves isolated areas.
I need to connect those areas and I'm not entirely sure how.
I can identify the different areas by flood filling, but I need to find the closest 2 points in each area and draw a line of '.' between them. Preferably without bruteforcing every tile.

eeisol · 2015-07-27 00:01:29

Honestly, I have no idea.
These masses look like continents. Am I to figure that you want to build bridge-like objects between your continents? (I find this metaphor easier to understand than your truthful explanation)

I'm not an expert, but all that comes to mind for me is the brute force.
Well, someone can take this and run with it.
Assuming you already have the masses separated into ... masses.
Pick two random points from each mass.
Calculate the distance. If taking one point and going North shrinks the distance AND is still on the 'mass', then do so. If not, try South. If not, try East. If not, try West.
Then do the same process for the other.
Now, this process fails if there is a remote alternative.

Perhaps consider deciding which face each is in relation to the other.
E.g., A is west of B, B is east of A.
Take all the points on the far west side of B. Take all the points on the East side of A.
Then do the "brute force" approach.
This is slightly less brute force. It takes care of the "remote area" that is actually closer. In fact, I'm not sure if there is a fault here. (Someone help wrong me! Lol)

However, I can agree that matching up every possible point everywhere is rather inefficient. (O(n^2)?) At the same time, it's the easiest and guaranteed solution.

Edit: does this shed some light? Haven't read it, but is strikingly similar.
Edit2: Planar case seems to be a curious one. It relates two points. Sadly, we have two blobs. It can't be applied directly because the masses would meet themselves.

Different55 · 2015-07-27 03:17:46

eeisol wrote:

Honestly, I have no idea.
These masses look like continents. Am I to figure that you want to build bridge-like objects between your continents? (I find this metaphor easier to understand than your truthful explanation)
I'm not an expert, but all that comes to mind for me is the brute force.
Well, someone can take this and run with it.
Assuming you already have the masses separated into ... masses.
Pick two random points from each mass.
Calculate the distance. If taking one point and going North shrinks the distance AND is still on the 'mass', then do so. If not, try South. If not, try East. If not, try West.
Then do the same process for the other.
Now, this process fails if there is a remote alternative.
Perhaps consider deciding which face each is in relation to the other.
E.g., A is west of B, B is east of A.
Take all the points on the far west side of B. Take all the points on the East side of A.
Then do the "brute force" approach.
This is slightly less brute force. It takes care of the "remote area" that is actually closer. In fact, I'm not sure if there is a fault here. (Someone help wrong me! Lol)
However, I can agree that matching up every possible point everywhere is rather inefficient. (O(n^2)?) At the same time, it's the easiest and guaranteed solution.
Edit: does this shed some light? Haven't read it, but is strikingly similar.
Edit2: Planar case seems to be a curious one. It relates two points. Sadly, we have two blobs. It can't be applied directly because the masses would meet themselves.

I've read that article, but it didn't help me a whole lot. I thought the planar case section sounded like it might have worked, but I wasn't able to get a good enough idea of what it actually is.

But I think I've thought of something that'll be at least a little bit faster than brute forcing every pair of coordinates. Since what I really want is to build a bridge, and all bridges have to start on the shore, I can create a list of every # that marks the edge of a continent, and bruteforce my way through the much shorter list of shore coordinates.

eeisol · 2015-07-27 03:19:52

^Part of my suggestion was take the shore that's closest to the other shore.
That's closer than the whole shore.
Again, if your map is this large, the effects of the O(n^2) won't be quite so bad on average processors.

Different55 · 2015-07-27 03:29:45

Yeah, I'm just not sure how to determine the general location of each continent, and I'm not sure how that would work out in cases where there isn't just one side that's particularly closer than another to the other continent, like

..........
........##
....######
..###....#
...###...#
.....#####
..........

Sadly, this is a very small map. I didn't want to go posting a full-sized map (haven't settled on a definite size yet, but it'll be many times larger than this) on the forums.

eeisol · 2015-07-27 03:46:43

Well, the complexity of measuring each shore-pixel of A and B is shore(A)*shore(B) (where shore() is the count of pixels)
Now, if we average all the pixels to find a general location, we're left to add shore(A) and shore(B) as we looped through once.

EDIT: I re-read your point about not knowing which side. My answer is this
When you've determined whether you want left or right, you loop Y=0 to Height. -- Then you get the left/right extreme block. Lumping those together gets your "east/west shore"

I'm not sure what extremes we could find with this program. At best, one side of shore is very small (1, 2, 3%), at worst it's 100%. (Vertical lines? Horizontal lines? They rain on my parade) -- But, let's go 50% up the middle.

(0.5)(shore(A)*shore(B)) + shore(A) + shore(B)

If what I figure is accurate, most of the time this is efficient. My math skills are failing me (if they haven't already) and I'm stuck with this.
So how helpful this really is increases exponentially as your map blobs get larger. (However, if one is small enough, then this is actually less helpful. Probably like 1 or 2 in dimension)

reedit: "If it can haz cod, put it in here."
this contradicts the criteria of "EE-related programming"
so 50% of this thread should be in the programming subfo

Different55 · 2015-07-27 07:47:42

So this is what I've ended up with so far. It's buggy and slow, but it's the first version of the thing so I'll give it a pass on that for now.

Before connecting code:

##################################################################################################################################################################################################################
##################################################################################################################################################################################################################
##################################################################################..################################################################.....####################################...##############.###
###################################..#####################################.#######.....###########..###############################################.......####################################.###############..##
##################################....###..##############################...#######.....#########....###########.....#######...###################.........###########################################..######..##
###############.....##############..........##############################.#########....##########...##########.........###.....##################.........##########################################....#########
##########.###.......##############.........#########################################..############...########..................#################.........############################################..##########
#########...###......###############........#######################################################...########.............##....###############........##########################################################
#########...######...################........######################################################..#########............#####......##########........###########################################################
#########....#####....################........########..##########################################...#########............######.....##########.......############################################################
##########...######...###################......######........#################################################.............########.############..#####################..#########################################
###########..#######...###################......#####.........############...#################################.............###########################################....########################################
#####################...##################.......####.........###########.....#################################...........###########################################......#######################################
#####################...###################........###.........#########.......################################...........######..##################################.......#######################################
####################....#######################.....#####.......#######........#################################...........#####...#################################........######################################
###################.....########################....######.......#####.........#################################............####....#########################.#######........#####################################
####################....#######################......#####.......#####.........##################################............####....#######################...#######........###..###############################
############################################.........####........#####.........#############...########.....########.........####....#######################....#######..##..###...###..##########################
############################################..........##.........######.......##############....######.......########....#######....###########...##########....################...###..##########################
########.###################################....##................######...#################......####.......########....########..###########.....#########...##################..###############################
#############################################..####................##########################.....####.......#########...######################.......###########################...##############################
################################################################..####################################...##.###########.###########################...############################.###############################
######################################################################################################...#########################################################################################################
######################################################..################.....#########################....############################.....#######################################################################
##########...................#########....##..#####.....#######...######......###............########.......................##..#####.......#####......#######.....###########......#######################.....##
#########......................######..........###############.......####.....................####....................................#.................#####..........######.........###############...........##
#########.......................####...........###############........######...................##.......#########....................###.................####...........#####..........#############............##
#########..###..#####.....###...####...........#######.#######.........######.......####...............###########.....###........######..........###....####............####...#........##########...###......###
######################...#####...##....##.......#####...#######..#.....######...############..........#############...######.....#######.........#####...####.............###..###.......#########...#####...#####
######################..######........########...####...###########....######..##############........########################...########.........######..#####............########......##########...#####..######
#####################...######.......##########...##...#############....####....#############.......####################################..........#####...#####...........########....############....####..######
#####################...#######.....############......###############...####.......##########.......###################################...........#####....######.........#########..############......##..#######
######################..################.########....########################.......#########........##################################...........######....######.........###################.............##.####
#######################################...#######....###########################.....#########........##################...############..........########...######.........##################.............##...###
#######################################...#####......############################.....#########..........##############....#############........#########...######.........##################........#######...###
#######################################....##.........######...####################...############........############....###############....#############..#####.........####################...############..###
####...################################..........##....######...####################..################....############....###############.....############...###.....#...#########################################
####....###############################.........####....######..####################..################....#############...###############........##########.........###..############.##########.....#############
#####..#######..#######################.........####....######...##################...#####.#########.....###############################.............######.......####...##########...########........###########
#############...#######################..........###....######...#################.....###..########.....###############################....#..........######.....#####.....#######....#########........##########
##############.#######################....#......###.....######.#################.......#...########....##############################...#####.....##.########...######......######.....##########......##########
#################################..###...###.....###.......######################............#######....##############################..#######...############...#####.........####........#######......##########
################################.........####...............#####################.............######....#######################################...####################..........####........######......##########
#################################.......######..............####################..............#######..#########################################.######################.....##..#####........######....###########
###############################################....#.....###########################..##################################################################################....##########........#######.############
#####################################################...##################################################################################################################..###########.......####################
###########################################################################################################################################################..#############...#########.........###################
#######################.........#############################...#############.........########..#############....##########.....##########################.........................................#####.......###
#########........###.............##################......###......########.............######......#####.............#######......................#####.........................................................##
##########.......................###############..................########............#######.......####................#####....................................................####..######...................##
##############...............##.############....................###########..........########.......####.....####.........######.........##...........................##........##############...###............##
##############..............###############..................########..#####.........#########.....######...#########......######.......####.........####........#######........#####################...........##
#############...............#######....####............##...########....####..........#########..########..############.....#####.......####.........#####...###########........#####...#############...........##
####..######......##........########....##.............#############....####..........##################...#############.....####.......#####.........####..###########..........###.....############...........##
####...####......####.......#########..................##############...###...........##################...#############.....####.......###########....###..##########....................###########...........##
####....##......#####........#########.................###############..###...........##################....############.....#####......############...##...###########...................###########..........###
#####...........######........########........####.....###############..######....##.####################....###########.....#######....#############..##....###########..........####################......######
######...........#######......########.......######.....#############....######..########################.....###########....########...#############..###....###########..........#####################...#######
######.....##....########....#########.......######.....#############......####..#########.###############.....#####..####....#######....############...##.....##############........#############################
######.....###..#########....#########......######......##############...........########...###.###########....####....###.....######.....###########...##.....###############........############################
######.....##############.....#########......####........#################.......########........##########....###......###....######......#########....###....################........###########################
#######....##############......#########.......#..........#################......#########........##########...###......####....#####......#########...######.#####################....###########################
########...#####..########.....#########..................##################.....###########......##########....##......####.....###........########...############################....###########################
########..####.....#########...########...................######################..###########....##########.....###......##.................########....###########################...############################
########...##......##########.########....##..............#######################...##########..##########.....#####........................#######....###########################....############################
########...........###################...####..............#######################...####################.....#######..........##....##....########...###########################.....############################
#########..........###########################........###.#########################.####################.......########.......####..###############...##########################......############################
##########.........###############################...####################################################.......###########..#######################.###########################.....#############################
###############...########################################################################################.....##################################################################...##############################
##################################################################################################################################################################################################################

After connecting code:

##################################################################################################################################################################################################################
##########.......##......#######..........###################...########..###################......##########################################..########....################################....###################
#######...................##...............##################....######....###############..........########..#######...#############..##...................######.###################..........##################
######.....................................####...###########.......##......####...######............#####....######.....#########...........................##.....#################............#################
######........................##............##.....###########......................#####..............##....#######.....########...................................######......####..............################
######.......................####..................############.....................#####...................#######.....#########...................................#####..........................###############
#####........................#####..................###########......................#####.................#######.....#########....................................####............................##############
####........................#######..................##########.......................####.............###########.....#########.....................................##..............................#############
###.....................###########..................##########....####................###............############.....########......................................................................#############
###....................############..................##########...######...............###............#############....########......................................................................#############
###....................############...................########...########..............###............##############...#########................##....................................................############
###....................###########.....................######...##########.............###............####.....######...#########..............####..................##.........##.....................###########
###....................##########...............##.....####....#############...........####............##.......######...#########.............####..............########......#####...................###########
####....................########....####.......####.....##.....##############...........####.....................######....########...........####...........#############.....######..................##.##..####
####....................########...######......####...........################...........###.....................#######....#######..........#####.........###############......#####..........................###
#####....................########.########....######..........################....................................######.....######.........######........###############.......####...........................###
#####.....................##########################..........################....................................######......#####...###...######........#############.#........###..........................####
#####........................##########..###########...........###############....................................#####.......#####..#####..#######.......#######..###...........####.....................#.######
#####.........................########....###########...........###############....................................####.......####...#####..#########....########...#.............####.....................#######
#####..........................#######.....##########............##############....................................#####......####...#####...#########..#########..................####....................#######
#####..............##..........######.......#########.............#############...................................########.....##....######...####################........###......######..................#######
######............####........######.........##..###..............#############...................................#########...........######.....#################.....#.######....######...................######
######............####......########.............................###############...................................##########.........#######.....###############......#########....#####....................#####
######.............###.....#########.............................################...................................###..#####.........######......##############.....##########.....###......................####
#######............##......########...............................###############....######.................###.....##....####..........######......##############..#############.............................####
########...........##.......##..##................................###############....#######...............#####....##.....####..........#####......##############################...........................#####
########...........###...........................................######....######.....######..............######....##.....####..........#####......##############################..........................######
########...........####..........................................#####......#####.......#####.............#####....####.....###..........#####.......############################...........................######
########..........######.........................................#####......######.......#####.............###.....#####.....###.........####.........##########################............................######
#######..........########..........##............................#####.......######......########..................#####......###.........###..........#########################.....#................##.....#####
#######......#############........####..........................#######.......######.....#########..................###.......####.........###.........##########################...###..............####....#####
########......############........####............##............########......######.....#########..........##................#####.........####.......##########################...###..............####...######
############...###########........####...........#####.........##########.....#######...###########..##....####...............#####..........####......##########################...####.............####...######
#############...##########.........##............######........##########......#########################..######...............#####..##.......###.....##########################...####............#####...######
#############....##########.....................#######........###########......########################..######...............##########.......####...##########################....###.............####....#####
#############....###########...................#########......##############....########################..######..............###########........###...##########################.....###...##...............#####
#############.....###########..##..............#########......###############....########################..#####.............############.........#....###########################.....########...............####
#########.##.......###############.............########.......###############.....#######################...####.............############...............###########################......#######...............###
########............##############.....##.......######.......###############.......#####################....#####.............###########................###########..##############......#######...............##
###..####............############.#...####........####.....#################........####################.....#####..............########.................##########....##############.....#######...............##
##....####...........###########......#####........##.....###################.......#######..##########.......#####..............######......##.........###########......############......#####................##
##....#####.#.......###########.....########..............#####################....#######....########........######.............#####......####........##########.......############......####.................##
##...#########.......###########.....############.........#####################....#######....#######..........#####............#####.......######.......#######........#############.......##..................##
##...##########.........#########...##############.........####################...########...########............##.............####........#######.......#####........##############...........................##
##...##########...........########.###############.........###################....########...#########...........................##.........########.......##..........####.#########...........................##
##...##########............#####.#################........###################.....########....#########.....................................########....................##..#########...........................##
##...##########............####...#################.......###################......#######........######.....................................########.......................#########...........................##
###.##########............#####.....################......###################.......######.........######.....................................#######......................##########..........................###
###########.#............#####.......################....#####################.......#####..........######.....................................#######..##.................##########..........................###
#########...........##..#####........#################...#######################.....#####...........######.......###...........................###########...........##..###########.........................####
########...........##########........#################....#######################.....####.............##.#......#####...............##.............#######..........################.....#####...............####
#########......#..############.......##################...#######################......##........................#########..........########.........................###############.....#######...............###
##########....###################....##################....#############..#######.......................#........##########.........#########...................##...##############.....#########...............##
#######...#.######################....##################.......########....#####.........................#......###########.........##########.................#####################...############.............##
######.....########################.....#################.......#######....####..........................##....############.........###########...............#######################...############.............#
#####.......########################.....#################.......#####.....####..........................################.#..........###########..............########################.#############............##
###.........########################......################.......#####......###..........................###############..............##########.............#######################################.........#####
##...........#######################......################......######.......#.....####..................###########...##...............#######.............########################################........######
##............#####################.......################......#######...........######.................##########......................######............#######################...################......#######
##........##...###################........################......###########.......######.................######.............#............#######...........#######.##############.....############################
##.......####...#################.........#################......###########.......#####.................#####.............###...........########..........######..##############.....############################
##.......#####..#################.........##################......###########.......####..................####.............###...........########..........######..##############.....############################
###.....#####....####.############.........##################......############......##....................###........##..#####.........#########...........####...###############....############################
###.....#####..........###..######..........###################....#############............##.............####......##########.........########............####...##.######..####.....###########################
##......######..........#....####............###################....#############..........########.........######..###########..........#######............####...#...####....##.......##########################
##......##########...........####.............###################......###########.........##########...........###############............#####...........######...#....................#########################
##.....############..##.#....#####...##.......###################.......##########.........###########..........###############............######.........########.###...................#########################
###...###################....###########.....####################......############.......#############.........################........############...################.................##########################
##########################..######################################..#################..###################.....#####################...#################################...#######################################
##################################################################################################################################################################################################################

There are still a few small isolated blobs that for some reason my automagical midget killing loop isn't killing but some day I will figure it out.

eeisold · 2015-07-28 00:06:34

Maybe your automagical killing loop is killing the wrong part. It seems that you're successful in not killing them, but the bridging system thinks they have died.

Also, this no longer looks like a world map. How sad. Though curious.

Different55 · 2015-07-28 03:35:14

Huh, I didn't notice it before but yeah that first image does look like a world map. It's supposed to be a cave but those definitely look like landmasses in the first picture.

Official Everybody Edits Forums

#1 2015-07-26 19:15:18, last edited by Different55 (2015-07-26 19:28:56)

Programming question/exercise

#2 2015-07-27 00:01:29, last edited by eeisol (2015-07-27 00:09:09)

Re: Programming question/exercise

#3 2015-07-27 03:17:46

Re: Programming question/exercise

#4 2015-07-27 03:19:52

Re: Programming question/exercise

#5 2015-07-27 03:29:45

Re: Programming question/exercise

#6 2015-07-27 03:46:43, last edited by eeisol (2015-07-27 04:46:50)

Re: Programming question/exercise

#7 2015-07-27 07:47:42

Re: Programming question/exercise

#8 2015-07-28 00:06:34

Re: Programming question/exercise

#9 2015-07-28 03:35:14

Re: Programming question/exercise

Board footer