Python for finding the minimum number of place names to fill the alphabet

README.md

Once I asked a question on gis.stackexchange.com which lead to a chunk of the UK academic production being lost for the day. But anyway we decided that we needed to vectorise the font typeface.

This led me to think about how many towns (or county boroughs) we actually needed to get all the letters of the alphabet, this code answers the question - 6. 'Newcastle upon Tyne', 'Wolverhampton', 'Kingston upon Hull', 'West Bromwich', 'Merthyr Tydfil', 'Halifax' Provided that you don't care about J, Q & Z!

Update

With some more thought I've improved the code and the answer is now 5 towns: 'Newcastle upon Tyne', 'Edinburgh', 'Halifax', 'Wolverhampton', 'Birkenhead'

alphabet.py

def char_range(c1, c2):                                                         
    """Generates the characters from `c1` to `c2`, inclusive."""                
    for c in range(ord(c1), ord(c2)+1):                                         
        yield chr(c)                                                            
                                                                                
                                                                                
chars = {}                                                                      
towns = {}                                                                      
with open("counties.txt", "r") as f:                                            
    for x in f:                                                                 
        town = x.upper().strip().replace(" ", "").replace("upon", "")           
        towns[town] = x.strip()                                                 
        chars[town] = set(town)                                                 
                                                                                
# cover the alphabet                                                            
                                                                                
covered = set()                                                                 
res = []                                                                        
# sort by number of unique letters                                              
                                                                                
while towns:                                                                    
    town_candidates = sorted(towns.keys(), key=lambda t: len(chars[t]), reverse=True)
    t = town_candidates[0]                                                      
    if not chars.get(t, None):                                                  
        continue                                                                
    print("", towns[t], '\t', sorted(chars[t]))                                 
    res.append(towns[t])                                                        
    covered |= chars[t]                                                         
    del towns[t]                                                                
    del chars[t]                                                                
    rem = []                                                                    
    for x in sorted(chars.keys(), key=lambda k: len(chars[k]), reverse=True):   
        print(x, chars[x])                                                      
        chars[x] -= covered                                                     
    rem = [k for k in chars if not chars[k]]                                    
    for k in rem:                                                               
        del chars[k]                                                            
        del towns[k]                                                            
    print("covered ", sorted(covered))                                          
    print(res)                                                                  
    if not len(chars):                                                          
        break   

counties.txt

Aberdeen
Dundee
Edinburgh
Glasgow
Barnsley
Barrow
Bath
Birkenhead
Birmingham
Blackburn
Blackpool
Bolton
Bootle
Bournemouth
Bradford
Brighton
Bristol
Burnley
Burton upon Trent
Bury
Canterbury
Cardiff
Carlisle
Chester
Coventry
Darlington
Derby
Dewsbury
Doncaster
Dudley
Eastbourne
Exeter
Gateshead
Gloucester
Grimsby
Halifax
Hartlepool
Hastings
Huddersfield
Ipswich
Kingston upon Hull
Leeds
Leicester
Lincoln
Liverpool
Luton
Manchester
Merthyr Tydfil
Newcastle upon Tyne
Newport
Northampton
Nottingham
Norwich
Oldham
Oxford
Plymouth
Portsmouth
Preston
Reading
Rochdale
Rotherham
St Helens
Salford
Sheffield
Solihull
Southampton
Southend on Sea
Southport
South Shields
Stockport
Stoke on Trent
Sunderland
Swansea
Teesside
Torbay
Tynemouth
Wakefield
Wallasey
Walsall
Warley
Warrington
West Bromwich
Wigan
Wolverhampton
Worcester
Yarmouth
York