Advent of Code 7th December 2022. Solution from ChatGPT.

AdventOfCode.md

To solve this problem, we need to find all of the directories with a total size of at most 100000. This can be done by traversing the directory tree and keeping track of the total size of each directory.

To implement this, we can use a dictionary to store the total size of each directory. As we traverse the tree, we can update the total size of each directory in the dictionary. When we encounter a file, we can add its size to the total size of the current directory. When we encounter a directory, we can move into it and repeat the process until we reach the end of the tree.

Once we have calculated the total size of each directory, we can simply iterate through the dictionary and sum the sizes of all the directories with a total size of at most 100000.

Here is some pseudocode that outlines the steps to solve this problem:

# create an empty dictionary to store the total size of each directory
dir_sizes = {}

# initialize the current directory to the root directory '/'
current_dir = '/'

# traverse the directory tree
for each line in the terminal output:
    if the line starts with 'cd':
        # update the current directory
        if the line contains '..':
            move up one level in the directory tree
        else if the line contains '/':
            move to the root directory
        else:
            move into the specified directory
    else if the line starts with 'ls':
        # process the files and directories in the current directory
        for each file or directory in the current directory:
            if the item is a file:
                add its size to the total size of the current directory
            else if the item is a directory:
                create an entry in the dir_sizes dictionary for the directory
                if the directory doesn't already have an entry, set its size to 0

# find all of the directories with a total size of at most 100000
sum = 0
for each directory in the dir_sizes dictionary:
    if the directory's size is at most 100000:
        add its size to the sum

# print the sum of the total sizes of the directories with size at most 100000
print(sum)

This algorithm should be able to find all of the directories with a total size of at most 100000 and calculate the sum of their total sizes.

*Can you give that to me using typescript, and with a unit test?

Sure, here is an implementation of the algorithm in TypeScript with a unit test:

// a file or directory in the directory tree
type FileOrDirectory = {
    name: string,
    size: number,
}

// the directory tree
type DirectoryTree = {
    name: string,
    files: FileOrDirectory[],
    directories: FileOrDirectory[],
}

// find all of the directories with a total size of at most 100000
// and return the sum of their total sizes
function findDirectoriesWithTotalSizeOfAtMost100000(tree: DirectoryTree): number {
    // create an empty dictionary to store the total size of each directory
    const dirSizes: { [key: string]: number } = {};

    // traverse the directory tree
    function traverseTree(dir: DirectoryTree) {
        // process the files and directories in the current directory
        for (const fileOrDirectory of dir.files) {
            if (fileOrDirectory.size) {
                // add the file's size to the total size of the current directory
                dirSizes[dir.name] += fileOrDirectory.size;
            }
        }

        for (const fileOrDirectory of dir.directories) {
            if (fileOrDirectory.name) {
                // create an entry in the dirSizes dictionary for the directory
                if (!dirSizes[fileOrDirectory.name]) {
                    dirSizes[fileOrDirectory.name] = 0;
                }

                // move into the directory and repeat the process
                traverseTree({ name: fileOrDirectory.name, files: [], directories: [] });
            }
        }
    }

    traverseTree(tree);

    // find all of the directories with a total size of at most 100000
    let sum = 0;
    for (const [dir, size] of Object.entries(dirSizes)) {
        if (size <= 100000) {
            sum += size;
        }
    }

    return sum;
}

// create a directory tree
const tree: DirectoryTree = {
    name: '/',
    files: [
        { name: 'b.txt', size: 14848514 },
        { name: 'c.dat', size: 8504156 },
    ],
    directories: [
        {
            name: 'a',
            files: [
                { name: 'f', size: 29116 },
                { name: 'g', size: 2557 },
                { name: 'h.lst', size: 62596 },
            ],
            directories: [
                {
                    name: 'e',
                    files: [
                        { name: 'i', size: 584 },
                    ],
                    directories: [],
                },
            ],
        },
        {
            name: 'd',
            files: [
                { name: 'j', size: 4060174 },
                { name: 'd.log', size: 8033020 },
                { name: 'd.ext', size: 5626152 },
                { name: 'k', size: 7214296 },
            ],
            directories: [],
        },
    ],
};

// test the findDirectoriesWithTotalSizeOfAtMost100000 function
const sum = findDirectoriesWithTotalSizeOfAtMost100000(tree);