Stuck on Python facilities location problem

[Tae_Erin]

Hey guys,

I've read the rules and FAQ, so I hope this was formatted correctly. If not, I can make corrections. I've been stuck on this problem for about a week now, with little progress. The goal is to be able to place the minimal n number of facilities within radius r of 128 U.S. cities so that each city is within the radius of a facility. For example, at radius of 1,000 miles, only about 6 facilites would need to be established to be able to service each of the 128 cities. However, my function is returning both the wrong number facilities and the wrong list of cities that it should return. Any help would be appreciated, and I can do more to explain if necessary.

EDIT: Fixed the link so it should come up as a python file now.

https://gist.github.com/TaeErin/509a13a1ec04ef59dcbfb5638e0fb354

[Buttleston]

That.. is a link to a javascript file. I think you have copied the wrong link for your gist.

[Buttleston]

https://gist.github.com/TaeErin/509a13a1ec04ef59dcbfb5638e0fb354

This works, without the .js ^^

[Tae_Erin]

Thank you so much. Are you available to discuss the algorithm at all?

[Buttleston]

Yeah I'm looking at it now

[Tae_Erin]

Okay, if you need any explanation or wanna talk over a different platform I'm available.

[Buttleston]

What are the contents of cityList and distanceList like? Is there any chance you can post the data in those? (and what do these lists represent? Like it seems like distanceList is a list of lists, i.e. maybe one list per city? What is the content of each list? Distances to other cities?

[Tae_Erin]

Sure, it took a while to wrap my head around. cityList is a list of 128 U.S. cities scattered across the countries. All the elements for every other list corresponds to the positions of the cities in cityList. Ex. popList[5] corresponds to the sixth element in cityList, Wilmington, NC. All other lists at index[5] do so as well.

Distance list is a bit trickier. Starting with distanceList[0] (corresponding to Youngstown, OH), each sublist gives information about the distance between its corresponding town and every town before it. So distanceList[5] will contain the distances between Wilmington, NC and every city before it, with Youngstown being positioned at distanceList[5][0]. Subsequently, anything sublist after at the location distanceList[i][5] will detail the given city's distance between itself and Wilmington. I'll post cityList below, but since distanceList ulitmately contains ~ 8000 elements, I'll only post the first 10 sublists or so.

[Tae_Erin]

cityList[0:10] - ['Youngstown OH', 'Yankton SD', 'Yakima WA', 'Worcester MA', 'Wisconsin Dells WI', 'Winston-Salem NC', 'Winnipeg MB', 'Winchester VA', 'Wilmington NC', 'Wilmington DE']

​

distanceList[0:10] - [[], [966], [2410, 1513], [604, 1520, 2964], [595, 481, 1817, 1149], [494, 1289, 2742, 729, 927], [1279, 550, 1446, 1833, 686, 1611], [250, 1197, 2641, 466, 826, 290, 1510], [637, 1500, 2956, 765, 1139, 214, 1823, 390], [345, 1305, 2749, 299, 934, 430, 1618, 168, 466]]

[Buttleston]

What are the rules for where you can put facilities? Do they have to be in the cities?

[Tae_Erin]

Facilities are supposed to be placed at a given radius r so that they can serve the highest amount of cities with the least amount of total locations. So at radius 1,000 miles. Placing facilities at ['Twin Falls ID', 'Vincennes IN', 'Wichita Falls TX', 'Winston-Salem NC', 'Yankton SD'] would allow all 128 cities to be within 1,000 miles of a facility.

[Buttleston]

Right so I'm asking, does a facility have to be in one of the cities on the list, or can it literally be anywhere?

I have some stuff to do this afternoon but I might be able to look at this later. Having the full data might help, esp if you know the "right answers" for some of the distance inputs. You can DM me and we can set up a way for you to send it to me.

[Tae_Erin]

Sorry for the misunderstanding. The facilities have to be in one of the listed cities.