Project Euler #68: Magic N-gon ring

  • + 0 comments

    python 100%

    import itertools
    N, S = map(int, input().split())
    # N, S = 3, 9
    
    def format_solution(outers, inners):
        s = ''
        for i in range(len(outers)):
            s += str(outers[i]) + str(inners[i]) + str(inners[(i + 1) % len(outers)])
        return s
    
    def check_solution(outers, inners, S):
        return all(map(lambda a, b, c: a + b + c == S, outers, inners, inners[1:] + inners[0:1]))
    
    
    def generate_solutions(N, S):
        outer_candidates = [set(combo) for combo in itertools.combinations(range(1, 2*N + 1), N)
                            if sum(combo) == N*(4*N+2-S)]
        solutions = []
    
        def complete(sol_outers, sol_inners, outers, inners):
            for new_outer in outers:
                new_sol_outers = sol_outers + [new_outer]
                new_outers = outers - set([new_outer])
                new_inner = S - new_outer - sol_inners[-1]
                if new_inner in inners:
                    new_sol_inners = sol_inners + [new_inner]
                    new_inners = inners - set([new_inner])
                    if new_inners == set([]):
                        new_sol_outers.append(list(new_outers)[0])
                        if check_solution(new_sol_outers, new_sol_inners, S):
                            solutions.append(format_solution(new_sol_outers, new_sol_inners))
                            return
                    complete(new_sol_outers, new_sol_inners, new_outers, new_inners)
    
        for outers in outer_candidates:
            inners = set(range(1, 2*N+1)) - outers
            a = min(outers)
            outers.remove(a)
            for b in inners:
                new_inners = inners.copy()
                new_inners.remove(b)
                c = S - a - b
                if c in new_inners:
                    new_inners.remove(c)
                    complete([a], [b, c], outers, new_inners)
        return sorted(solutions)
    
    
    solutions = generate_solutions(N, S)
    for solution in solutions:
        print(solution)