Thursday, June 16, 2016

PuzzlOR Cell Towers, Part I

PuzzlOR_CellTowers

PuzzlOR Cell Tower Problem, Part I

http://puzzlor.com/2016-04_CellTowers.html

This Jupyter Notebook can be found at https://github.com/kariheedots/DevJupyter

The goal is to find the minimum number of cell towers to that will achieve at least 70% coverage of the 41 neighborhoods.

In [1]:
41*.70
Out[1]:
28.7

We need to cover at least 29 Neighborhoods. A little experimentation shows that four towers are not going to be enough. Five towers might be enough. There are about 75 million different ways to place 5 towers on the 10x10 grid.

In [2]:
from math import factorial
print("100 choose 5 = ",factorial(100)/(factorial(95)*factorial(5)))

100 choose 5 =  75287520.0
$${100\choose 5} = 75287520$$

The code below examines all possible ways to place 5 towers. There are five different arrangements of 5 towers that cover 27 neighborhoods, but that is the best we can do. To cover 29 neighborhoods, we will have to place at least 6 towers, but that is too many combinations for a brute force search...

In [3]:
from itertools import combinations
In [4]:
def coverage(j):
    
    row0,col0=divmod(j-1,10)
    
    if (j==1):
        return([1,2,11,12]) 
    if (j==10):
        return([9,10,19,20])
    if (j==91):
        return([81,82,91,92])
    if (j==100):
        return([89,90,99,100])
    
    if (j<10):
        return([j-1,j,j+1,j+9,j+10,j+11])
    if (j>91):
        return([j-11,j-10,j-9,j-1,j,j+1])
    
    if (col0==0):
        return([j-10,j-9,j,j+1,j+10,j+11])
    if (col0==9):
        return([j-11,j-10,j-1,j,j+9,j+10])
    
    return([j-11,j-10,j-9,j-1,j,j+1,j+9,j+10,j+11])
In [5]:
neighborhoods={3,5,6,8,11,15,24,26,27,29,30,35,37,39,43,
               46,47,48,49,51,54,55,57,61,62,63,64,65,
               70,75,77,81,83,87,88,90,91,95,96,99,100}
len(neighborhoods)
Out[5]:
41
In [6]:
for indexes in combinations(range(1,101), 5):
    coverlist = []
    coverset = {}
    for i in indexes:
        coverlist += coverage(i)
        
    coverset=set(coverlist)
    inset = coverset.intersection(neighborhoods)
    if (len(inset)>26):
        print("Tower Locations: ", indexes, "\nCoverage: ", len(inset), "Neighborhoods: ", inset, "\n")
        
    

Tower Locations:  (15, 38, 52, 55, 86) 
Coverage:  27 Neighborhoods:  {5, 6, 15, 24, 26, 27, 29, 37, 39, 43, 46, 47, 48, 49, 51, 54, 55, 61, 62, 63, 64, 65, 75, 77, 87, 95, 96} 

Tower Locations:  (15, 38, 54, 72, 86) 
Coverage:  27 Neighborhoods:  {5, 6, 15, 24, 26, 27, 29, 37, 39, 43, 47, 48, 49, 54, 55, 61, 62, 63, 64, 65, 75, 77, 81, 83, 87, 95, 96} 

Tower Locations:  (15, 38, 54, 86, 89) 
Coverage:  27 Neighborhoods:  {5, 6, 15, 24, 26, 27, 29, 37, 39, 43, 47, 48, 49, 54, 55, 63, 64, 65, 75, 77, 87, 88, 90, 95, 96, 99, 100} 

Tower Locations:  (15, 38, 54, 86, 99) 
Coverage:  27 Neighborhoods:  {5, 6, 15, 24, 26, 27, 29, 37, 39, 43, 47, 48, 49, 54, 55, 63, 64, 65, 75, 77, 87, 88, 90, 95, 96, 99, 100} 

Tower Locations:  (15, 38, 55, 72, 86) 
Coverage:  27 Neighborhoods:  {5, 6, 15, 24, 26, 27, 29, 37, 39, 46, 47, 48, 49, 54, 55, 61, 62, 63, 64, 65, 75, 77, 81, 83, 87, 95, 96}
Posted by at