Day_5_Alchemical_Reduction.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyP2JALT/M15YgV52ZCashLZ",
      "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_5_Alchemical_Reduction.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": "MP76-BIT9oPw"
      },
      "outputs": [],
      "source": [
        "data = \"dabAcCaCBAcCcaDA\""
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "data = open(\"input.txt\").read().strip()"
      ],
      "metadata": {
        "id": "VauwQV5w-3bR"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def reduce_string_stack(s):\n",
        "    stack = []\n",
        "\n",
        "    for char in s:\n",
        "        # Check if the stack is not empty and the top element is the same letter but opposite case\n",
        "        if stack and char.swapcase() == stack[-1]:\n",
        "            stack.pop()\n",
        "        else:\n",
        "            stack.append(char)\n",
        "\n",
        "    # Convert the stack back to a string\n",
        "    return ''.join(stack)\n",
        "\n",
        "# Testing the stack-based function with the same input\n",
        "reduced_string_stack = reduce_string_stack(data)\n",
        "len(reduced_string_stack)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "sw5RVdXpPz7m",
        "outputId": "64c65b3e-510e-476c-c43a-cfacc92ac842"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "11108"
            ]
          },
          "metadata": {},
          "execution_count": 34
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def remove_letter(s, letter):\n",
        "    # Remove both uppercase and lowercase occurrences of the letter\n",
        "    s = s.replace(letter.lower(), '').replace(letter.upper(), '')\n",
        "    return s"
      ],
      "metadata": {
        "id": "c41TXiXzOATE"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "import string\n",
        "\n",
        "shortest = 10**9\n",
        "for letter in string.ascii_lowercase:\n",
        "  s = remove_letter(data, letter)\n",
        "  reduced_string = reduce_string_stack(s)\n",
        "  if len(reduced_string) < shortest:\n",
        "    shortest = len(reduced_string)\n",
        "shortest"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "T3EAZHr-N53F",
        "outputId": "c59073b8-4a63-4f8b-e794-ac23aad9e37f"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5094"
            ]
          },
          "metadata": {},
          "execution_count": 35
        }
      ]
    }
  ]
}