Finally on time for once. But this will be my last one on-time for about a week before I travel to Vegas. So it better count.

It looks like today's is going to be the first real complex one. At least complex enough to justify a struct. Basically needing to reconstruct a file structure based on a series of commands and responses.

As far as I can tell, there's three different possible lines, somewhat pertaining to a state machine:

• $ - contains a command; cd changes what the 'current directory' is; ls can be ignored outright
• dir - defines a directory existing in the current directory
• ### - defines a file, starting with a numerical size

So I'll probably just do some sort of state-like machine? Directory objects that have references to other directories, as well as files it contains.

switch(line[0])
{
    case '$':
        {
            // Navigate dir (if necessary)
        }

    case 'd':
        {
            // Add dir to current dir
        }

    default: // Assumed file
        {
            // Add file to dir
        }
}

Seemed to work pretty fine, even if it was a headache string splitting. Other languages are so much easier to just str.split(). But regardless, now that I have the parsing done, it's pretty trivial to just figure out the sum of the directories, and put it all together into a sum!

struct File {
    string name;
    int64_t size;
};

struct Dir {
    string name;
    string parent;
    vector<Dir> subDirs;
    vector<File> files;
};

int calculateSize(Dir dir)
{
    int size = 0;
    for (File f: dir.files) size += f.size;
    for (Dir d: dir.subDirs) size += calculateSize(d);
    return size;
};

After a bit of debugging, realizing I had some bad references in my code, I managed to get the full answer. It looks like an ugly block of declarations, with a global object... and it doesn't work, because I made some bad assumptions. Ugh. Taking an extra half hour to fix all your "pointers" to real pointers sucks. But this is my fault, I tried to be 'clever' or something.

Ah well. Changed to using pointers everywhere, no globals, and it magically worked otherwise. woo. I'm tired already.

This makes sense considering the problem. Delete a directory; rather, figure out which one to delete; A little bit tricky to think of, but not too difficult. Find the smallest directory that, when it's size is added to existing free space, equals at least the number needed to be free.

int64_t avaliable = TOTAL_SPACE - calculateSize(*rootDir);
int64_t smallest = TOTAL_SPACE;    

queue<Dir*> dirs;
dirs.push(rootDir);

while (dirs.size() > 0)
{
    Dir* dir = dirs.front();
    dirs.pop();

    for (pair<string, Dir*> d: dir->subDirs) dirs.push(d.second);
    int64_t dirSize = calculateSize(*dir);

    if ((dirSize + avaliable) > NEEDED_SPACE)
    {
        smallest = min(dirSize, smallest);
    }
}