0
\$\begingroup\$

Description:

The task involves navigating a haunted wasteland on a desert island using a camel. The objective is to escape from the current position (AAA) to the destination (ZZZ) by following left/right instructions. Nodes in the network have connections, and instructions guide the traversal. If instructions run out, the sequence repeats. The goal is to determine the number of steps needed to reach ZZZ.

For example:

RL

AAA = (BBB, CCC)
BBB = (DDD, EEE)
CCC = (ZZZ, GGG)
DDD = (DDD, DDD)
EEE = (EEE, EEE)
GGG = (GGG, GGG)
ZZZ = (ZZZ, ZZZ)

Starting with AAA, you need to look up the next element based on the next left/right instruction in your input. In this example, start with AAA and go right (R) by choosing the right element of AAA, CCC. Then, L means to choose the left element of CCC, ZZZ. By following the left/right instructions, you reach ZZZ in 2 steps.

#!/usr/bin/env python3

from pathlib import Path
from typing import Iterable

import typer


def navigate(instructions: str, network: dict[str, list[str]]) -> int:
    pos = "AAA"
    ins_count = 0

    while True:
        for instruction in instructions:
            pos = network[pos][0] if instruction == "L" else network[pos][1]
            ins_count += 1

            if pos == "ZZZ":
                return ins_count


def parse_family(line: str) -> tuple[str, ...]:
    # Parent = (left_child, right_child)
    parent, children = line.split(" = ")
    children = children.translate(str.maketrans("", "", "()"))
    return parent, *children.strip().split(", ")


def total_instructions(lines: Iterable[str]) -> int:
    instructions = next(lines).strip()
    next(lines)  # Discard the empty line
    network = {
        parent: children for line in lines for parent, *children in [parse_family(line)]
    }
    return navigate(instructions, network)


def main(network_document: Path) -> None:
    with open(network_document) as f:
        print(total_instructions(f))


if __name__ == "__main__":
    typer.run(main)

Review request:

General coding comments, style, etc.

What are some possible simplifications? What would you do differently?

\$\endgroup\$
2
  • \$\begingroup\$ The code is very optimistic. It assumes that the goal is reachable. However, there is a possibility of an infinite loop. \$\endgroup\$
    – vnp
    Commented Dec 29, 2023 at 16:33
  • \$\begingroup\$ @vnp That's an interesting observation. Thank you. \$\endgroup\$
    – Harith
    Commented Dec 30, 2023 at 8:56

1 Answer 1

2
\$\begingroup\$

Your code looks perfectly fine as is. But ask a thousand people for their suggestions and you just might get a thousand different responses. So let me offer a few of my own. I will be making successive iterative changes to the code below to make it easier to see how I arrived at my final destination.

Simplify parse_family and total_instructions

Since the parent and children fields occupy fixed offsets and fixed lengths within the input line, why not just ...


def parse_family(line: str) -> tuple[str, list[str]]:
    # Parent = (left_child, right_child)
    return line[0:3], [line[7:10], line[12:15]]

... instead of creating a translate table, doing a translation, doing two splits, etc.?

But note that this function is now returning a tuple consisting of a string and a list of two strings instead of the original tuple of 3 strings. This will enable another simplification in total_instructions, which now is:

def total_instructions(lines: Iterable[str]) -> int:
    instructions = next(lines).strip()
    next(lines)  # Discard the empty line
    network = {parent: children
        for line in lines
            for parent, children in [parse_family(line)]
    }
    return navigate(instructions, network)

The only real difference is that we are now creating the list of children that the values in the network dictionary need to be in function parse_family instead of total_instructions. This is a matter of taste but for me the creation of the list of two children is now occurring in the function that is the more logical choice (not a big deal either way).

But you are ultimately creating a list of a single element consisting of the returned tuple from the call to parse_family with the expression [parse_family(line)] just so you can use a comprehension with two for clauses. Since parse_family now is so simple, I favor removing this function altogether and code total_instructions to be:

def total_instructions(lines: Iterable[str]) -> int:
    instructions = next(lines).strip()
    next(lines)  # Discard the empty line
    # Create a dictionary whose key is the "parent" and whose value
    # is a list of its "children". These values are extracted from
    # the input line at fixed offsets and field lengths.
    network = {line[0:3]: [line[7:10], line[12:15]] for line in lines}
    return navigate(instructions, network)

I have rolled two functions into one but have reduced the total number of lines of code from 7 to 4. So I believe that the result is in the end is clearer to a reader (such as me!).

An Alternate navigate Implementation

You have (in part):

def navigate(instructions: str, network: dict[str, list[str]]) -> int:
    ...

    while True:
        for instruction in instructions:
    ...

This is because instructions needs to be considered to repeat indefinitely as needed until we arrive at a position of interest. You could instead replace the double loop with:

...

from itertools import cycle
...

def navigate(instructions: str, network: dict[str, list[str]]) -> int:
    pos = "AAA"
    ins_count = 0

    for instruction in cycle(instructions):
        pos = network[pos][0] if instruction == "L" else network[pos][1]
        ins_count += 1

        if pos == "ZZZ":
            return ins_count

This makes explicit the repeating nature of instructions.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.