<jupyter_start><jupyter_text>Day 1: No Time for a Taxicabauthor: <NAME>license: [MIT](https://opensource.org/licenses/MIT)[link to problem statement](http://adventofcode.com/2016/day/1) Santa's sleigh uses a very high-precision clock to guide its movements, and the clock's oscillator is regulated by stars. Unfortunately, the stars have been stolen... by the Easter Bunny. To save Christmas, Santa needs you to retrieve all fifty stars by December 25th.Collect stars by solving puzzles. Two puzzles will be made available on each day in the advent calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. Good luck!You're airdropped near Easter Bunny Headquarters in a city somewhere. "Near", unfortunately, is as close as you can get - the instructions on the Easter Bunny Recruiting Document the Elves intercepted start here, and nobody had time to work them out further.The Document indicates that you should start at the given coordinates (where you just landed) and face North. Then, follow the provided sequence: either turn left (L) or right (R) 90 degrees, then walk forward the given number of blocks, ending at a new intersection.There's no time to follow such ridiculous instructions on foot, though, so you take a moment and work out the destination. Given that you can only walk on the street grid of the city, how far is the shortest path to the destination?For example:Following R2, L3 leaves you 2 blocks East and 3 blocks North, or 5 blocks away.R2, R2, R2 leaves you 2 blocks due South of your starting position, which is 2 blocks away.R5, L5, R5, R3 leaves you 12 blocks away.How many blocks away is Easter Bunny HQ?  Solution logicThis looks to be a simple trace the path sort of problem.Assume we start at origin `(0,0)`,then use counters to keep track of where we areon a virtual grid. Also need to keep track of direction.Read the input, then parse it to read whether to go left or right.Keep a variable direction to indicate where we are currently moving.Direction is a `vector (x,y)`to represent the math to do when calculcating thenext point on the grid.`North(0,1); South(0,-1); East(1,0); West(-1,0)`**Tricky:** how to convert north to west by reading in left?_North_ is `(0,1)` and West is `(-1,0)`Similarly, `West --left--> South`,which can be written as `(-1,0)--L-->(0,-1)`Drawing up a table to see if I can find a pattern or a formula  **Table: Turning LEFT**  Direction   Value       Turned      Value  North       (0,1)       West        (-1,0)  West        (-1,0)      South       (0,-1)  South       (0,-1)      East        (1,0)  East        (1,0)       North       (0,1)  **Table: Turning RIGHT**  Direction   Value       Turned      Value  North       (0,1)       East        (1,0)  West        (-1,0)      North       (0,1)  South       (0,-1)      West        (-1,0)  East        (1,0)       South       (0,-1)Looking at the table, it is apparent that on every turn, there is a changein the field which contain a non-zero value (x or y)So we always swap the active (that's what I'll call the non-zero field) fieldThe trick here is the sign of the values. It is not true that the sign alwayschanges. For e.g. East--Left-->NorthTurn left: - swap (x,y = y,x) - apply mask (-1,1)Turn right: - swap (x,y = y,x) - apply mask (1,-1) Algorithm - Initialise starting direction as North - Read the input - For every input:   - based on turn, get new direction   - multiply the direction vector by distance in input   - add the new vector to point on graph Block distance / Taxicab distanceThat is simply the number of block we need to walk to get thereThat is the total x distance + total y distanceSo the formula is to take the absolute values of both co-ordinates,and add them`abs(x) + abs(y)` Get the input data from a file in the inputs folder.The file contains the tokens seperated by comma(,).<jupyter_code>with open('../inputs/day01.txt', 'r') as f:
    data = [x.strip() for x in f.read().split(',')]<jupyter_output><empty_output><jupyter_text>Use namedtuples, because they're so nice ;)Actually, use them because they are still tuples, look like class-objects,and give more semantic context to the code.In this case, the Turn is LEFT and RIGHT.<jupyter_code>from collections import namedtuple
Turns = namedtuple('Turns', ('left', 'right'))
turns = Turns('L', 'R')<jupyter_output><empty_output><jupyter_text>A VectorPoint is a point with a directionI use them to plot the point on the graph, and also to represent thedirection of movement.<jupyter_code>VectorPoint = namedtuple('VectorPoint', ('x', 'y'))<jupyter_output><empty_output><jupyter_text>When turning, we apply this mask (the logic if above).<jupyter_code>mask_left = VectorPoint(-1, 1)
mask_right = VectorPoint(1, -1)<jupyter_output><empty_output><jupyter_text>The direction is the starting face, which the problem describes as being **NORTH**.<jupyter_code>direction = VectorPoint(0, 1)<jupyter_output><empty_output><jupyter_text>The point to be tracked, this is the position on graph.<jupyter_code>point = VectorPoint(0, 0)<jupyter_output><empty_output><jupyter_text>- Tokenize the token into turn and number of blocks     - The first letter represents the direction to turn to, and will only be 'L' for left, and 'R' for right.      - The numbers after that are the number of blocks to walk. - Get mask based on direction to turn - The direction is the swapped direction, with the mask applied. So the previous `(x,y)` becomes `(y,x) * mask(x,y)`. - The point is now the number of blocks added with the direction applied.<jupyter_code>for token in data:
    turn, blocks = token[:1], int(token[1:])
    
    if turn == turns.left:
        mask = mask_left
    if turn == turns.right:
        mask = mask_right
    # 
    direction = VectorPoint(direction.y * mask.x, direction.x * mask.y)
    point = VectorPoint(
        point.x + blocks * direction.x,
        point.y + blocks * direction.y)<jupyter_output><empty_output><jupyter_text>The final distance from origin is the distance of x and y axis.<jupyter_code>distance = abs(point.x) + abs(point.y)
# print(distance)<jupyter_output><empty_output><jupyter_text>Part TwoThen, you notice the instructions continueon the back of the Recruiting Document.Easter Bunny HQ is actually at the first location you visit twice.For example, if your instructions are`R8, R4, R4, R8`,the first location you **visit twice** is `4 blocks away, due East`._How many blocks away is the first location you visit twice?_  Solution logicAs per the previous solution, this looks to be a trivial problem.We only have to check when we visit the place twice, so there has to besome way to check whether we have been to the place, which means we needto store the point we have been on the graph.For this, we will use a `set` to store the points, and check at everyiteration, whether we have been to that point.The naive solution would be to store every point we visit, so it merelybecomes a problem of sifting through searches (binary search would suffice).But to make it more efficient, we only store the **paths**,and check if the current movement cross any of the previous paths. Basic GeometryLet's use the property of points lying on a line segment. Suppose we have theline segment `AB`, and a point `P` lies on the line, then the sum of thedistance of `P` from `A` and `P` to `B`is equal to the distance from `A` to `B`. Or specified as:  `AB` = `AP` + `PB`So we save every point we end up at, as endpoints, and check if the movementis along the path by checking for every point in the saved set.Another interesting observation in terms of optimisation, is that if thepoint does lie on the line, then one of the axis co-ordinates will be thesame in all three points `(A, B, C)`. This is true in this case because allmovesments are in the single direction along a grid. So we can eliminatepoints which do not satisfy this condition. A path contains two points, `A` and `B`. Create a path namedtuple to hold them.<jupyter_code>Path = namedtuple('Path', ('A', 'B'))<jupyter_output><empty_output><jupyter_text>Paths will save all visited paths, but we do not need the constraint that they must be unique, since we are checking for intersecting points.<jupyter_code>paths = []<jupyter_output><empty_output><jupyter_text>`last_point` was the last point traversed<jupyter_code>point = VectorPoint(0, 0)
last_point = point<jupyter_output><empty_output><jupyter_text>- Tokenize the token into turn and number of blocks     - The first letter represents the direction to turn to, and will only be 'L' for left, and 'R' for right.      - The numbers after that are the number of blocks to walk. - Get mask based on direction to turn - The direction is the swapped direction, with the mask applied. So the previous `(x,y)` becomes `(y,x) * mask(x,y)`. - The point is now the number of blocks added with the direction applied. - **Part Two** Check if we have visited the path. To do that, we must first identify whether we have moved along the X-axis or the Y-axis.    - The `movement_mask` represents the mask applied to the last point to iterate over to the current point. This gives us every point along the path. The mask takes care of negatives and direction, and helps keep the logic clear.    - If the x co-ordinates do not change, this is along the Y-axis.        - Check whether we are moving towards the top or the bottom.        - If the y attribute is increasing, we are moving towards the top, otherwise towards bottom.    - If the y co-ordinates do not change, this is along the X-axis.        - Check whether we are moving towards the right or the left.        - If the x attribute is increasing, we are moving towards the right, otherwise towards left. - Now iterate through each point along the path     - Check if there are any common co-ordinates on this path.    - If the condition is satisfied, found a point lying in the intersecting path<jupyter_code>for token in data:
    turn, blocks = token[:1], int(token[1:])
    if turn == turns.left:
        mask = mask_left
    if turn == turns.right:
        mask = mask_right

    direction = VectorPoint(direction.y * mask.x, direction.x * mask.y)

    point = VectorPoint(
        point.x + blocks * direction.x,
        point.y + blocks * direction.y)

    if point.x == last_point.x:
        if point.y > last_point.y:
            movement_mask = VectorPoint(0, 1)
        else:
            movement_mask = VectorPoint(0, -1)
    else:
        if point.x > last_point.x:
            movement_mask = VectorPoint(1, 0)
        else:
            movement_mask = VectorPoint(-1, 0)

    last_point_holder = last_point
    
    while last_point.x != point.x or last_point.y != point.y:

        last_point = VectorPoint(
            last_point.x + movement_mask.x,
            last_point.y + movement_mask.y)

        for path in paths:

            if path.A.x == last_point.x and path.B.x == last_point.x:
                if abs(path.A.y - last_point.y)\
                        + abs(last_point.y - path.B.y)\
                        == abs(path.A.y - path.B.y):
                    break
            if path.A.y == last_point.y and path.B.y == last_point.y:
                if abs(path.A.x - last_point.x)\
                        + abs(last_point.x - path.B.x)\
                        == abs(path.A.x - path.B.x):
                    break
        else:
            # No paths match, move ahead.
            continue
        # Some path is found. Stop searching.
        break
    else:
        # Save the path.
        # `last_point = point` at this juncture
        path = Path(last_point_holder, point)
        last_point = point
        paths.append(path)
        continue
    # We found a path that has been visited
    distance = abs(last_point.x) + abs(last_point.y)
#     print(distance)
    break
else:
    print(0)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08324924318869828, 'fraction_numerical': 0.009249915909855366, 'mean_word_length': 3.2611967036904335, 'pattern_counts': {'":': 0, '<': 50, '<?xml version=': 0, '>': 55, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '261341', 'license': 'MIT', 'n_tokens_mistral': 3417, 'n_tokens_neox': 3318, 'n_words': 1577, 'path': '2016/python3/Day01.ipynb', 'repo_name': 'coolharsh55/advent-of-code', 'size': '11905'}