1. Most popular name

As in the fifth lecture, we use the data of the National Data on the relative frequency of given names in the population of U.S. births, stored in a subdirectory named names of the working directory, in files named yobxxxx.txt with xxxx (the year of birth) ranging from 1880 to 2013. Write a program most_popular_name.py that prompts the user for a first name, and finds out the first year when this name was most popular in terms of frequency of names being given, as a female name and as a male name.
本题分析Eric的解法，他的单次运行效率较高，程序相对简单。相比之下，我自己的写法单次效率低，适合做大量查询。主要思路区别是我的写法将所有文件遍历后输出一个庞大的字典，包括了年份、性别、名字、计数、频率信息，程序复杂，单次运行效率低，胜在字典建立后多次查询速度快。

import os 
first_name = input('Enter a first name: ')
min_male_frequency, min_female_frequency = 0, 0
male_first_year, female_first_year = None, None
tallies = {'F': {}, 'M': {}}
records = {'F': {}, 'M': {}}
#字典的嵌套，第一个字典实现性别分类，第二个字典分别实现题目要求

for filename in os.listdir('names'):
    if not filename.endswith('.txt'):
        continue
    year = int(filename[3:7])
    with open('names' + '/' + filename) as name:
        for gender in {'F', 'M'}:
            tallies[gender][year] = 0   
        for line in name:
            name, gender, count = line.split(',')
            count = int(count)
            tallies[gender][year] += count
            if name == first_name:
                records[gender][year] = count
    #遍历了所有文件，获得了所有年份的总计数tallies，{'F': {1880: XXX, 1881:XXX...}, 'M': {1880:XXX...}}
    #获得了所有年份要查询名字的records，{'F': {1880: XXX, 1881:XXX...}, 'M': {1880:XXX...}}

frequencies = dict.fromkeys(('M', 'F'))
#以M和F作为key，创建新的字典，{'F': None, 'M': None}
for gender in {'F','M'}:
    frequencies[gender] = [(records[gender][year] * 100 / tallies[gender][year], year) for year in records[gender]]
    frequencies[gender].sort(reverse = True)
#生成frequencies的dict，方法是逐年查询records和tallies字典，例如1880年，records中查到那一年该名字的计数records[gender][year]
#tallies中查到那一年所有名字的总计数，相除取百分比得到frequencies的数据。并由大到小排序。
#{'F':[(XX.XX, 1880), (XX.XX, 1881)...], 'M':[(XX.XX, 1880), (XX.XX, 1881)...]}
if frequencies['F']:
    min_female_frequency, female_first_year = frequencies['F'][0][0], frequencies['F'][0][1]
if frequencies['M']:
    min_male_frequency, male_first_year = frequencies['M'][0][0], frequencies['M'][0][1]
if not female_first_year:
    print(f'In all years, {first_name} was never given as a female name.')
else:
    print(f'In terms of frequency, {first_name} was the most popular as a female name '
                                                         f'first in the year {female_first_year}.\n'
                            f'It then accounted for {min_female_frequency:.2f}% of all female names'
         )
if not male_first_year:
    print(f'In all years, {first_name} was never given as a male name.')
else:
    print(f'In terms of frequency, {first_name} was the most popular as a male name'
                                                           f'first in the year {male_first_year}.\n'
                                f'It then accounted for {min_male_frequency:.2f}% of all male names'
         )

2. The 9 puzzle

Dispatch the integers from 0 to 8, with 0 possibly changed to None, as a list of 3 lists of size 3, to represent a 9 puzzle. For instance, let
[[4, 0, 8], [1, 3, 7], [5, 2, 6]]
OR
[[4, None ,8], [1, 3, 7], [5, 2, 6]]
represent the 9 puzzle

4   8
1 3 7
5 2 6

with the 8 integers being printed on 8 tiles that are placed in a frame with one location being tile free. The aim is to slide tiles horizontally or vertically so as to eventually reach the configuration

1 2 3
4 5 6
7 8

It can be shown that the puzzle is solvable iff the permutation of the integers 1, . . . , 8, determined by reading those integers off the puzzle from top to bottom and from left to right, is even. This is clearly a necessary condition since:
--sliding a tile horizontally does not change the number of inversions;
--sliding a tile vertically changes the number of inversions by -2, 0 or 2;
--the parity of the identity is even.
Write a program nine_puzzle.py with a function:
--validate_9_puzzle(grid) that prints out whether or not grid is a valid representation of a solvable 9 puzzle

def test(grid):
    if len(grid) != 3:
        return
    test = []
    for row in grid:
        for column in row:
            test.append(column)
    #把所有grid里面的element放在一个list中
    if None in test:
        test[test.index(None)] = 0
    #如果有None，改成0
    if sorted(test) != list(range(9)):
        return
    #如果不是1-8的数字和0/None构成，则不成立。这里不要用.sort()，那样会改变原来的grid顺序
    permutation = 0
    for i in range(8):
        for j in range(i + 1, 9):
            if test[i] and test[j] and test[i] > test[j]:
                permutation += 1
    #判断从前向后所有非零数字（0在题中代表可以和任何相邻数字互换位置），如果前面的数字比后面的大，则记录加1
    if permutation % 2:
        return 
    else:
        return grid

def validate_9_puzzle(grid):
    if test(grid):
        print('This is a valid 9 puzzle, and it is solvable')
    else:
        print('This is an invalid or unsolvable 9 puzzle')