Advent of Code 2019 馃く (讬讜诐 6)

砖专砖讜专 Advent of Code 讬讜诐 1 谞讞诇 讛爪诇讞讛 讙讚讜诇讛, 讜爪诇讞谞讜 讙诐 讗转 讬诪讬诐 2 , 3, 4 讜志5. 讘讜讗讜 谞转拽讚诐 :slight_smile:

讗谞讬 诪谞讬讞 砖讛讗转讙专 讛讝讛 讬砖讗专 驻讛 诇驻讞讜转 诇讬讜诪讬讬诐 砖诇讜砖讛, 讗讝 拽讞讜 讗转 讛讝诪谉 :slight_smile:
讜讗诐 诇讗 讛住驻拽转诐 诇驻转讜专 讗转 讛讬诪讬诐 讛拽讜讚诪讬诐 鈥 诇讗 讞讜讘讛, 讗讘诇 诇讻讜 注诇 讝讛! 讗诇讜 转专讙讬诇讬诐 谞讞诪讚讬诐 诪讗讜讚 砖讬砖驻专讜 讗转 讛讬讻讜诇讜转 砖诇讻诐 诪讗讜讚.

讗讝 拽讚讬诪讛, 驻专住诪讜 驻讛 讗转 讛驻转专讜谞讜转 砖诇讻诐 诇讬讜诐 讛砖讬砖讬 砖诇 Advent of Code!

2 诇讬讬拽讬诐
1

2

诇讬讬拽 1

诪讻讗谉 讛讛砖专讗讛 诇注抓 驻讬诇讜讙谞讟讬? :palm_tree:
:star2: :star2:

讞诇拽 1 讜-2
#day 6

def get_puzzle_input(puzzle):
    orbit_map = {}
    with open(puzzle, "r") as orbits:
        for orbit in orbits.readlines():
            center, around = orbit.replace("\n","").split(")")
            orbit_map[around] = center
    return orbit_map


def direct_indirect_orbits(puzzle):
    orbit_map = get_puzzle_input(puzzle)
    indirect = 0
    for orb in orbit_map:
        while orbit_map[orb] in orbit_map:
            indirect += 1
            orb = orbit_map[orb]
    return indirect + len(orbit_map)


def me_and_san(puzzle):
    path_create = set()
    orbit_map = get_puzzle_input(puzzle)
    counter = 0
    for orb in ["YOU", "SAN"]:
        while orbit_map[orb] in orbit_map:
            if orbit_map[orb] in path_create:
                path_create.remove(orbit_map[orb])
            else:
                path_create.add(orbit_map[orb])
            orb = orbit_map[orb]
    return len(path_create)

        

print(direct_indirect_orbits("resources//day6.txt"))  # part 1
print(me_and_san("resources//day6.txt"))  # part 2
2 诇讬讬拽讬诐

讻谉 :slightly_smiling_face:

诇讬讬拽 1

拽爪转 讘注讬讻讜讘, 讛诪讞砖讘 砖诇讬 讘转拽诇讛 :frowning:

Advent of Code, Day 6
# Advent of Code, Day 6
def get_inputs(path):
   """Create a dictionary of planets and their center.
   
   Args:
       path (str): The source file path.

   Returns:
       A dictionary of planets and their center as values.
   
   Raises:
       FileNotFoundError: If the file path is invalid.
   """
   with open(path, 'r') as file:
       orbits = file.read().splitlines()
       orbits = map(lambda o: o.split(")"), orbits)
       return {planet: center for center, planet in orbits}


def count_orbits(path):
   """Count the number of direct and indirect orbits.
   
   Args:
       path (str): The source file path.

   Returns:
       The number of orbits.
   
   Raises:
       FileNotFoundError: If the file path is invalid.
   """
   orbits = get_inputs(path)
   count = 0
   for planet in orbits:
       while orbits.get(planet) != 'COM':
           planet = orbits[planet]
           count += 1
   return count + len(orbits)


def get_orbits(orbits, planet):
   """Create a list of orbits from planet to COM.
   
   Args:
       orbits (dict): The orbits map.
       planet (str): The planet to start from.

   Returns:
       List of planets from planet to COM based on the orbits map.
   """
   if planet == "COM":
       return ["COM"]
   return [planet] + get_orbits(orbits, orbits[planet])


def get_orbital_distance(path):
   """Calculate the orbital distance between YOU and SAN.
   
   Args:
       path (str): The source file path.

   Returns:
       The orbital distance between YOU and SAN.
   
   Raises:
       FileNotFoundError: If the file path is invalid.
   """
   orbits = get_inputs(path)
   count = 0
   you_orbits = set(get_orbits(orbits, "YOU")[1:])
   san_orbits = set(get_orbits(orbits, "SAN")[1:])
   return len(you_orbits ^ san_orbits)
           
   

print(count_orbits("input.txt"))
print(get_orbital_distance("input.txt"))
诇讬讬拽 1
讛诇讱 诇讬 讛住讜驻砖
FILE_LOCATION = 'resources/input.txt'

def get_info():
    with open(FILE_LOCATION, 'r') as file:
        orbits = file.read().split()
    all_orbits = {}
    for couple in orbits:
        star, orbitstar = couple.split(')')
        if star in all_orbits:
            all_orbits[star].append(orbitstar)
        else:
            all_orbits[star] = [orbitstar]
    return all_orbits


def path(all_orbits, star, lvl=0):
    orbitstars = all_orbits.get(star)
    if orbitstars is None:
        return 0
    lvl += 1
    if len(orbitstars) == 1:
        return path(all_orbits, orbitstars[0], lvl) + lvl
    else:
        return path(all_orbits, orbitstars[0], lvl) + path(all_orbits, orbitstars[1], lvl) + lvl * 2


def get_key(all_orbits, star):
    for orbit, orbitstars  in all_orbits.items():
        if star in orbitstars:
            return orbit

def find_split_points(all_orbits, position):
    counter = 0
    split_points = {}
    while position != 'COM':
        counter += 1
        position = get_key(all_orbits, position)
        if len(all_orbits.get(position)) > 1:
            split_points[position] = counter
    return split_points

def find_shortest_path(all_orbits, x, y):
    point_x = find_split_points(all_orbits, get_key(all_orbits, x))
    point_y = find_split_points(all_orbits, get_key(all_orbits, y))
    shortest = len(all_orbits)

    for key, value in point_y.items():
        if key in point_x:
            s = value + point_x.get(key)
            if s < shortest:
                shortest = s
    return shortest


all_orbits = get_info()
path(all_orbits, 'COM')
find_shortest_path(all_orbits, 'YOU', 'SAN')

诇讗 注砖讬转讬 驻讬讬谉 讟讬讜谞讬谞讙 讘砖诇 诪讙讘诇讜转 讝诪谉 :slight_smile:

2 诇讬讬拽讬诐

诪讞专 讗住讙讜专 讗转 讛讗转讙专 :slight_smile:

砖谞讬 讛讞诇拽讬诐
def build_orbit_map(orbit_list):
    orbit_map = {}
    for orbit in orbit_list:
        mass, obj = orbit.split(')')
        if mass not in orbit_map:
            orbit_map[mass] = [obj]
        else:
            orbit_map[mass].append(obj)
    return orbit_map


def get_distance(orbit_map, mass):
    distance = 0
    temp = orbit_map.copy()
    if mass == 'COM':
        return 0
    for obj in orbit_map:
        if mass in orbit_map[obj]:
            temp.pop(obj)
            distance += 1 + get_distance(temp, obj)
    return distance


def count_orbits(orbit_map):
    count = 0
    orbits = [mass for orbits in orbit_map.values() for mass in orbits]
    for mass in orbits:
        count += get_distance(orbit_map, mass)
    return count


def get_orbit_path(orbit_map, mass, path=None):
    if path is None:
        path = set()
    for obj in orbit_map:
        if mass in orbit_map[obj]:
            path.add(obj)
            path.update(get_orbit_path(orbit_map, obj, path))
    return path


def count_transfers(orbit_map, origin, destination):
    return len(get_orbit_path(orbit_map, origin) ^ get_orbit_path(orbit_map, destination))


with open('Day 6.txt', 'r') as file_handler:
    challenge_input = file_handler.read()

orbit_list = challenge_input.split()
orbit_map = build_orbit_map(orbit_list)

print(count_orbits(orbit_map))
print(count_transfers(orbit_map, 'YOU', 'SAN'))
诇讬讬拽 1
讛驻转专讜谉 砖诇讬
import functools
from collections import defaultdict


def get_input():
    with open('input.txt', 'r') as challenge_input:
        return map(str.strip, challenge_input.readlines())


def parse_input(inputs):
    planets = defaultdict(list)
    for line in inputs:
        planet, _, orbiter = line.partition(')')
        planets[orbiter].append(planet)
    return planets


def map_flatter(starmap):
    @functools.lru_cache(maxsize=None)
    def flat_map(start):
        if start not in starmap:
            return []
        stars = [s for star in starmap[start] for s in flat_map(star)]
        return starmap[start] + stars
    return {star: flat_map(star) for star in starmap}


# Part 1
data = parse_input(get_input())
flat_orbiters = map_flatter(data)
print(sum(map(len, flat_orbiters.values())))

# Part 2
print(len(set(flat_orbiters['YOU']) ^ set(flat_orbiters['SAN'])))

?? 诪讛 讝讛 讛讚讘专 讛讝讛 鈥 ??

讛砖讟专讜讚诇 讛讝讛 谞拽专讗 decorator.
转讻诇鈥欁 诇讗 讞讬讬讘讬诐 讗讜转讜 砖诐 讻讚讬 砖讝讛 讬注讘讜讚.
住驻爪讬驻讬转 讛砖讜专讛 讛讝讜 讙讜专诪转 诇讝讛 砖驻讬讬转讜谉 讬讘谞讛 诪讗讞讜专讬 讛拽诇注讬诐 诪讬诇讜谉, 砖讘讜 讛讜讗 讝讜讻专 讗讬讝讛 驻专诪讟专讬诐 讛讜注讘专讜 诇志flat_map (讗诇讜 讛诪驻转讞讜转 砖诇 讛诪讬诇讜谉) 讜诪讛 讛讜讞讝专 讻诇 驻专诪讟专 砖讛讜注讘专 (讗诇讜 讛志values 砖诇 讛诪讬诇讜谉).
驻注诐 讛讘讗讛 讻砖志flat_map 谞拽专讗转 注诐 驻专诪讟专 砖讻讘专 拽讬讬诐 讻诪驻转讞 讘诪讬诇讜谉, 讘诪拽讜诐 诇讛专讬抓 讗转 讛驻讜谞拽爪讬讛 诪讞讚砖 讛讜讗 驻砖讜讟 讬讞讝讬专 讗转 诪讛 砖砖诪讜专 诇讜 讘志value 砖诇 讗讜转讜 key.
讛拽讜谞住驻讟 注爪诪讜 谞拽专讗 memoization, 讛诪讬诪讜砖 讛住驻爪讬驻讬 谞拽专讗 lru cache. 讝讛 讙讜专诐 诇讚讘专讬诐 诇讝讜讝 讬讜转专 诪讛专 :slight_smile:

2 诇讬讬拽讬诐

砖诪转讬 诇讘 注讻砖讬讜 砖讬砖 转讙讬转 advent-of-code 讗讘诇 诇讗 讻诇 讛驻讜住讟讬诐 谞诪爪讗讬诐 讘讛, 讜讞讘诇.
诪讜讚讛 砖诇讗 诪诪砖 讛讘谞转讬 讗诐 诇讛讜住讬祝 转讙讬讜转 诇驻讜住讟讬诐 拽讬讬诪讬诐 讝讛 诪砖讛讜 砖讗谞讬 讬讻讜诇 诇注砖讜转 讗讜 诇讗, 讗讝 讗讙诇讙诇 讗转 讝讛 讛诇讗讛. :upside_down_face:

转讜讚讛, 讟讜驻诇 :slight_smile:

讗谞讞谞讜 谞诇诪讚 讗转 讛谞讜砖讗讬诐 讛讗诇讛, 砖诇 讛讚拽讜专讬讬讟讜专住 讜讛诪诪讜专讬讬讝 ?

诇驻讬 讛住讬诇讘讜住 讘砖讘讜注 讛讘讗 :pray:

3 诇讬讬拽讬诐

讬砖 讛讬转专讜谉 诪住讜讬讬诐 讘砖讬诪讜砖 讘 str.partition 注 诇 str.split ?
讻讬 讻讗讬诇讜 讘诪拽专讛 讛讝讛 讗转讛 爪专讬讱 诇讬爪讜专 讗转 讛诪砖转谞讛 讛专讬拽 _

转诪讬讚 诪讞讝讬专 3 讞诇拽讬诐, 讙诐 讗诐 诪爪讗/诇讗 诪爪讗/诪爪讗 讬讜转专 诪志1

2 诇讬讬拽讬诐

讘讙讚讜诇 讗诐 谞转讜谉 诇谞讜 砖讬砖 砖诇砖讛 讞诇拽讬诐 讗讝 讗驻砖专 诇讛谞讬讞 砖讬诪讜砖 讘 split 讘讙讚讜诇 谞讻讜谉 ?

:man_shrugging:
讛讞讬讬诐 讛讗诪讬转讬讬诐 讬讜转专 拽砖讜讞讬诐 诪转专讙讬诇讬诐 砖讗谞砖讬诐 诪谞拽讬诐 注讘讜专诐 讗转 讛拽诇讟, 讗谞讬 讘讻"诪 转诪讬讚 诇讜拽讞 诪砖谞讛 讝讛讬专讜转

3 诇讬讬拽讬诐

讗讞讚 讛讻讬驻讬讬诐!

讞诇拽讬诐 1 讜- 2
def get_input(path):
    with open(path, 'r') as puzzle_input:
        return puzzle_input.readlines()


def get_son_and_father(relationship):
    return relationship.split(')')[1].strip(), relationship.split(')')[0].strip()


def insert_into_relationships(relationships, father, son):
    if father not in relationships:
        relationships[father] =  {'Father': None, 'Sons': [son], 'Depth': 0}
    else:
        relationships[father]['Sons'].append(son)

    if son not in relationships:
        relationships[son] =  {'Father': father, 'Sons': [], 'Depth': 0}
    else:
        relationships[son]['Father'] = father

    return relationships


def get_relationships(puzzle_input):
    relationships = {}
    for relationship in puzzle_input:
        son, father = get_son_and_father(relationship)
        relationships = insert_into_relationships(relationships, father, son)
    return relationships


def traverse(relationships, root, depth):
    count = 0
    if not root:
        return

    sons = relationships[root]['Sons']
    for son in sons:
        relationships[son]['Depth'] = depth + 1
        traverse(relationships, son, depth + 1)

    return relationships


def get_path_to_root(relationships, x):
    obj = x
    path = set()
    while obj != 'COM':
        obj = relationships[obj]['Father']
        path.add(obj)
    return path


def part_one(traversal_result):
    res = 0
    for item in traversal_result:
        res += traversal_result[item]['Depth']
    return res


def part_two(relationships, first, second):
    path_from_you_to_root = get_path_to_root(relationships, first)
    path_from_san_to_root = get_path_to_root(relationships, second)
    part_two_result = len(path_from_you_to_root ^ path_from_san_to_root)
    return part_two_result


def main():
    puzzle_input = get_input('input.txt')
    relationships = get_relationships(puzzle_input)
    traversal_result = traverse(relationships, 'COM', 0)
    part_one_result = part_one(traversal_result)
    print(f'part_one_result: {part_one_result}')
    part_two_result = part_two(relationships, 'YOU', 'SAN')
    print(f'part_two_result: {part_two_result}')


main()
诇讬讬拽 1