Day_7_The_Sum_of_Its_Parts.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyNFpPeZijH7E4DMFsByufwy",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/elichen/aoc2018/blob/main/Day_7_The_Sum_of_Its_Parts.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "n9l0o3YL_JCr"
      },
      "outputs": [],
      "source": [
        "data = \"\"\"Step C must be finished before step A can begin.\n",
        "Step C must be finished before step F can begin.\n",
        "Step A must be finished before step B can begin.\n",
        "Step A must be finished before step D can begin.\n",
        "Step B must be finished before step E can begin.\n",
        "Step D must be finished before step E can begin.\n",
        "Step F must be finished before step E can begin.\"\"\".split('\\n')"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "data = [x.rstrip() for x in open(\"input.txt\").readlines()]"
      ],
      "metadata": {
        "id": "WNWEAtRGEIXl"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Define a function to parse the list of strings and create a dictionary of dependencies\n",
        "\n",
        "def parse_dependencies(statements):\n",
        "    deps = {}\n",
        "    for statement in statements:\n",
        "        # Split the statement to extract the steps involved\n",
        "        parts = statement.split()\n",
        "        step_before = parts[1]\n",
        "        step_after = parts[-3]\n",
        "\n",
        "        # Add the dependency to the dictionary\n",
        "        if step_after in deps:\n",
        "            deps[step_after].append(step_before)\n",
        "        else:\n",
        "            deps[step_after] = [step_before]\n",
        "\n",
        "    return deps\n",
        "\n",
        "deps = parse_dependencies(data)"
      ],
      "metadata": {
        "id": "8lgKkG-I_Kth"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def order_steps(deps):\n",
        "    taken_steps = []\n",
        "    remaining_steps = sorted(set(deps.keys()).union(*deps.values()))\n",
        "\n",
        "    # Repeat until all letters have been tried\n",
        "    while remaining_steps:\n",
        "        for step in remaining_steps.copy():\n",
        "            # Check if step has no entry in deps dict or all dependencies are met\n",
        "            if step not in deps or all(dep in taken_steps for dep in deps[step]):\n",
        "                taken_steps.append(step)\n",
        "                remaining_steps.remove(step)\n",
        "                break\n",
        "\n",
        "    return taken_steps\n",
        "\n",
        "order = order_steps(deps)\n",
        "\"\".join(order)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "id": "1JvhVIuEIeZi",
        "outputId": "00a5ddb3-ab94-4600-be2d-ec33d07b7f35"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'FMOXCDGJRAUIHKNYZTESWLPBQV'"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 97
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def complete_tasks(deps, num_workers, base_seconds):\n",
        "    def task_time(task):\n",
        "        return base_seconds + ord(task) - ord('A') + 1\n",
        "\n",
        "    remaining_steps = sorted(set(deps.keys()).union(*deps.values()))\n",
        "    in_progress = set()\n",
        "    taken_steps = []\n",
        "    workers = [{'task': None, 'time_left': 0} for _ in range(num_workers)]\n",
        "    total_time = 0\n",
        "\n",
        "    # Loop until all tasks are completed\n",
        "    while remaining_steps or any(worker['task'] for worker in workers):\n",
        "        # Assign tasks to available workers\n",
        "        for worker in workers:\n",
        "            if worker['task'] is None:\n",
        "                for step in remaining_steps:\n",
        "                    if step not in in_progress and (step not in deps or all(dep in taken_steps for dep in deps[step])):\n",
        "                        worker['task'] = step\n",
        "                        worker['time_left'] = task_time(step)\n",
        "                        in_progress.add(step)\n",
        "                        break\n",
        "\n",
        "        total_time += 1\n",
        "\n",
        "        # Update workers' tasks\n",
        "        for worker in workers:\n",
        "            if worker['task']:\n",
        "                worker['time_left'] -= 1\n",
        "                if worker['time_left'] == 0:\n",
        "                    taken_steps.append(worker['task'])\n",
        "                    remaining_steps.remove(worker['task'])\n",
        "                    in_progress.remove(worker['task'])\n",
        "                    worker['task'] = None\n",
        "\n",
        "    return total_time\n",
        "\n",
        "# Test the function\n",
        "num_workers_test = 15\n",
        "base_seconds_test = 60\n",
        "time_to_complete = complete_tasks(deps, num_workers_test, base_seconds_test)\n",
        "time_to_complete"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "jI6aK07RWYYH",
        "outputId": "2ff94ed1-bec3-4f7a-cab7-82daaaaa62f9"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1053"
            ]
          },
          "metadata": {},
          "execution_count": 98
        }
      ]
    }
  ]
}