PNP_200_Sample_PSS_River_Crossing_Problem.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "toc_visible": true,
      "authorship_tag": "ABX9TyN1z7R2Z9Ze5XyrikINUtYY",
      "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/michaelbarkasi/Intro_Cog_Sci_Examples/blob/main/PNP_200_Sample_PSS_River_Crossing_Problem.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Sample Physical Symbol System\n",
        "\n",
        "CC Michael Barkasi 2024\n",
        "\n",
        "[Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/) //\n",
        "[BSD (3-Clause) License](https://opensource.org/licenses/BSD-3-Clause)\n",
        "\n",
        "## Intro\n",
        "\n",
        "What is this? Sample code and walkthrough of a Physical Symbol System -- a virtual one, of course. My Python is rusty, so I asked ChatGPT to write me some of the first few (simple) chunks of Python code used below. I checked and cleaned them. The second half of the code is more me writing from scratch.\n",
        "\n",
        "Note: All code chunks must be run in order. Rerunning chunks in different orders might change results, because variables get be redefined with new input.\n",
        "\n",
        "## Physical Symbol Systems\n",
        "\n",
        "In 1975, Herbert Simon and Allen Newell proposed the *physical symbol system hypothesis*: A physical symbol system has the necessary and sufficient means for general intelligent action. They defined a physical symbol system as a physical device or other physical system:\n",
        "1. with physical patterns (the symbols)\n",
        "2. that can be combined to form complex symbol structures\n",
        "3. such that the system contains processes or mechanisms for manipulating those complex symbol structures\n",
        "4. and such that the processes for generating and transforming those complex symbol structures can themselves be represented by complex symbol structures within the system.\n",
        "\n",
        "Simon and Newell don't have a precise definition of \"intelligent action\", but instead think of it on the model of problem solving via a search space.\n",
        "\n",
        "## River Crossing Problem\n",
        "\n",
        "This CoLab will simulate a physical symbol system (PSS), using Python, which demonstrates \"intelligent action\" by solving one version of the *River Crossing Problem*. The problem goes: Kirk, Spock, and McCoy (three officers) and three “red shirts” are on one side of a river with a small boat that holds at most two people. Gorn are lurking on both river banks, and if one or two of the red shirts ever finds themselves outnumbered by officers (“odd ones out”), the Gorn attack. How can all six get to the other side of the river without inviting a Gorn attack? (This version of the problem is inspired by chapter 4 of [Bermúdez's textbook, _Cognitive Science_](https://www.cambridge.org/core/resources/cognitive-science-4/).)\n",
        "\n",
        "We can think of the problem as involving an initial state, a solution state, and a set of constraints on how to get from one to the other. The initial state is all six people on one bank, the solution state is all six on the opposite bank, the constraints are that only at most two people can fit in the boat, someone always has to pilot the boat across the river (of course), and if there are red shirts on a bank, they can’t be outnumbered by officers.\n",
        "\n",
        "For those interested, read about the original / classic River Crossing Problem here: [Wikipedia](https://en.wikipedia.org/wiki/Wolf,_goat_and_cabbage_problem)\n",
        "\n",
        "## Basic Parameters\n",
        "\n",
        "**Symbols:** o, r, b, /\n",
        "\n",
        "**Complex Symbol Structures:** Any string with exactly 8 characters that has 0-3 o followed by 0-3 r, followed possibly by 0-1 b, followed by /, followed by 0-3 o, followed by 0-4 r, followed by 0-1 b.\n",
        "\n",
        "**Manipulation Processes:** Move at least one and at most two other characters and the b to the opposite side of the /, such that if there’s an r on a side of the /, the number of o never exceeds the number of r on that side.\n",
        "\n",
        "**Initial State:** ooorrrb/\n",
        "\n",
        "**Solution State:** /ooorrrb"
      ],
      "metadata": {
        "id": "6-FFiFp1FB41"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "1cZpheeWDX76"
      },
      "outputs": [],
      "source": [
        "# @title CoLab Reset\n",
        "# Want to reset loaded code?\n",
        "%reset -f"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# @title Initiate State Variables\n",
        "\n",
        "# Initialize the State variable as an empty 1D array of length 8\n",
        "State = [''] * 8\n",
        "\n",
        "# Initialize the Initial State variable with the specified characters\n",
        "Initial_State = list(\"ooorrrb/\")\n",
        "\n",
        "# Initialize the Solution State variable with the specified characters\n",
        "Solution_State = list(\"/ooorrrb\")\n",
        "\n",
        "'''\n",
        "  Explanation: The \"/\" represents the river. \"o\" represents an officer, \"r\" a red shirt, and \"b\" the boat.\n",
        "    If an \"o\", \"r\", or \"b\" is on the left side of the \"/\", that represents it as being on the left side of the river.\n",
        "    If an \"o\", \"r\", or \"b\" is on the right side of the \"/\", that represents it as being on the right side of the river.\n",
        "'''\n",
        "\n",
        "# Printing the initialized variables for verification\n",
        "print(\"State:\", State)\n",
        "print(\"Initial State:\", Initial_State)\n",
        "print(\"Solution State:\", Solution_State)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "XKpSP3MpI1Nr",
        "outputId": "b66f496a-a4f5-4b27-e958-67c2421c2225"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "State: ['', '', '', '', '', '', '', '']\n",
            "Initial State: ['o', 'o', 'o', 'r', 'r', 'r', 'b', '/']\n",
            "Solution State: ['/', 'o', 'o', 'o', 'r', 'r', 'r', 'b']\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# @title Manipulation Functions: Boat Side Check\n",
        "\n",
        "'''\n",
        " Next, we need to define functions which simulate the manipulation processes of our PSS,\n",
        "  while respecting the constraints of the problem.\n",
        "'''\n",
        "\n",
        "# First we need a function to check which side of the river the boat is on\n",
        "def boat_on_left_of_river(State):\n",
        "    try:\n",
        "        # A state variable is a string of 8 characters.\n",
        "        # Begin by finding the place (the \"index\") of of the river character (/) and the boat character (b).\n",
        "        slash_index = State.index('/')\n",
        "        b_index = State.index('b')\n",
        "\n",
        "        # If the boat character index is less than the river character index,\n",
        "        #   then that represents the boat as being on the left side of the river.\n",
        "        if b_index < slash_index:\n",
        "            return True # yes, boat is on the left side of river\n",
        "        else:\n",
        "            return False # no, boat is not on the left side of river\n",
        "    except ValueError:\n",
        "        # Handle the case where either 'b' or '/' is not found in State\n",
        "        return False\n",
        "\n",
        "# Example usage:\n",
        "State = list(\"ooorr/orb\")  # Replace with your State variable\n",
        "test_result = boat_on_left_of_river(State)\n",
        "print(f'In State {State}:')\n",
        "if test_result:\n",
        "    print(\"The boat is on the left side of the river.\")\n",
        "else:\n",
        "    print(\"The boat is on the right side of the river.\")\n",
        "\n",
        "State = list(\"ooorrrb/o\")  # Replace with your State variable\n",
        "test_result = boat_on_left_of_river(State)\n",
        "print(f'\\nIn State {State}:')\n",
        "if test_result:\n",
        "    print(\"The boat is on the left side of the river.\")\n",
        "else:\n",
        "    print(\"The boat is on the right side of the river.\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "PCI0-mIMLve0",
        "outputId": "f08d74b3-c54a-4607-f78b-0862847a31e4"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "In State ['o', 'o', 'o', 'r', 'r', '/', 'o', 'r', 'b']:\n",
            "The boat is on the right side of the river.\n",
            "\n",
            "In State ['o', 'o', 'o', 'r', 'r', 'r', 'b', '/', 'o']:\n",
            "The boat is on the left side of the river.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# @title Manipulation Functions: Cross River\n",
        "\n",
        "'''\n",
        " We'll also need a function which simulates a river crossing.\n",
        " Remember: If the boat is on the left side, it can carry at most two people (but must have at least one, a pilot).\n",
        "           If the boat is on the right side (and we're not in the solution state), someone will have to pilot it back to the left side\n",
        "            to pick up another person. Of course, two can go back as well (this is important, to avoid leaving an odd redshirt out).\n",
        "'''\n",
        "\n",
        "# We need to important the random function\n",
        "import random\n",
        "\n",
        "# Helper function\n",
        "def identity_function2(x,y):\n",
        "    return x\n",
        "def identity_function3(x,y,z):\n",
        "    return x\n",
        "\n",
        "def cross_river(State,\n",
        "                heuristics_func_left=identity_function2,\n",
        "                heuristics_func_right=identity_function3):\n",
        "\n",
        "    print(f\"Current state: {State}.\")\n",
        "    # Check if 'b' is on the left or right of '/'\n",
        "    if boat_on_left_of_river(State):\n",
        "        print(\"Boat is on left.\")\n",
        "        left_side = State[:State.index('/')] # array indexes of all characters to the left of slash\n",
        "        right_side = State[State.index('/')+1:] # ... and to the right\n",
        "\n",
        "        # Randomly select 1 or 2 characters from the left side\n",
        "        num_to_move = random.randint(1, 2)\n",
        "        left_side.remove('b') # 'b' is on the left side, but isn't a character (person), so don't want it randomly selected.\n",
        "        if len(left_side) == 1:\n",
        "          num_to_move = 1\n",
        "        characters_to_move = random.sample(left_side, num_to_move)\n",
        "        # We won't be using heuristics for now, but, defining this here for use later\n",
        "        characters_to_move = heuristics_func_left(characters_to_move,left_side)\n",
        "        print(f\"Crossing river with characters: {', '.join(characters_to_move)}\")\n",
        "\n",
        "        # Move the selected characters to the right side\n",
        "        right_side.extend(characters_to_move)\n",
        "        for char in characters_to_move:\n",
        "            left_side.remove(char)\n",
        "\n",
        "        # Update the State\n",
        "        State = left_side + ['/'] + right_side\n",
        "        State.append('b') # Have to put 'b' back, so it gets moved as well.\n",
        "    else:\n",
        "        print(\"Boat is on right.\")\n",
        "        left_side = State[:State.index('/')]\n",
        "        right_side = State[State.index('/')+1:]\n",
        "\n",
        "        # Randomly select 1 or 2 characters from the right side\n",
        "        num_to_move = random.randint(1, 2)\n",
        "        right_side.remove('b')\n",
        "        if len(right_side) == 1:\n",
        "          num_to_move = 1\n",
        "        characters_to_move = random.sample(right_side, num_to_move)\n",
        "        # We won't be using heuristics for now, but, defining this here for use later\n",
        "        characters_to_move = heuristics_func_right(characters_to_move,left_side,right_side)\n",
        "        print(f\"Crossing river with characters: {', '.join(characters_to_move)}\")\n",
        "\n",
        "        # Move the selected characters to the left side\n",
        "        left_side.extend(characters_to_move)\n",
        "        for char in characters_to_move:\n",
        "            right_side.remove(char)\n",
        "\n",
        "        # Update the State\n",
        "        State = left_side + ['b'] + ['/'] + right_side\n",
        "\n",
        "    return State\n",
        "\n",
        "# Example usage:\n",
        "State = list(\"ooorrrb/\")\n",
        "new_state = cross_river(State)\n",
        "print(f\"New State after crossing: {new_state}\\n\")\n",
        "\n",
        "State = list(\"or/oorrb\")\n",
        "new_state = cross_river(State)\n",
        "print(f\"New State after crossing: {new_state}\\n\")\n",
        "\n",
        "State = list(\"oob/orrr\")\n",
        "new_state = cross_river(State)\n",
        "print(f\"New State after crossing: {new_state}\\n\")\n",
        "\n",
        "State = list(\"ro/oorrb\")\n",
        "new_state = cross_river(State)\n",
        "print(f\"New State after crossing: {new_state}\\n\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "epjbfPQ2O2WI",
        "outputId": "b46d2adc-58cd-4f5c-d5e5-64150404c2bc"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Current state: ['o', 'o', 'o', 'r', 'r', 'r', 'b', '/'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: r, o\n",
            "New State after crossing: ['o', 'o', 'r', 'r', '/', 'r', 'o', 'b']\n",
            "\n",
            "Current state: ['o', 'r', '/', 'o', 'o', 'r', 'r', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: r, o\n",
            "New State after crossing: ['o', 'r', 'r', 'o', 'b', '/', 'o', 'r']\n",
            "\n",
            "Current state: ['o', 'o', 'b', '/', 'o', 'r', 'r', 'r'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: o\n",
            "New State after crossing: ['o', '/', 'o', 'r', 'r', 'r', 'o', 'b']\n",
            "\n",
            "Current state: ['r', 'o', '/', 'o', 'o', 'r', 'r', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: r, o\n",
            "New State after crossing: ['r', 'o', 'r', 'o', 'b', '/', 'o', 'r']\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# @title Manipulation Functions: Red Shirt Check\n",
        "\n",
        "'''\n",
        " The final constraint of the problem is that if there are red shirts on a bank, they can’t be outnumbered by officers.\n",
        " So we need a check function which looks to see if a given output state has more 'o' than 'r' on one side.\n",
        "'''\n",
        "\n",
        "def odd_redshirt_out(State):\n",
        "\n",
        "    # Begin by grabbing lists of the characters on each side of the river\n",
        "    left_side = State[:State.index('/')]\n",
        "    right_side = State[State.index('/')+1:]\n",
        "\n",
        "    # Check if 'r' is present on either side\n",
        "    left_has_r = 'r' in left_side\n",
        "    right_has_r = 'r' in right_side\n",
        "\n",
        "    # Count 'o' and 'r' on each side\n",
        "    left_o_count = left_side.count('o')\n",
        "    left_r_count = left_side.count('r')\n",
        "\n",
        "    right_o_count = right_side.count('o')\n",
        "    right_r_count = right_side.count('r')\n",
        "\n",
        "    # Check if there is 'r' and more 'o' than 'r' on either sides\n",
        "    left_condition = left_has_r and left_o_count > left_r_count\n",
        "    right_condition = right_has_r and right_o_count > right_r_count\n",
        "\n",
        "    return left_condition or right_condition # This will be a Boolean value (TRUE or FALSE) telling us whether a redshirt is outnumbred by officers.\n",
        "\n",
        "# Example usage:\n",
        "State1 = list(\"ooorrrb/\")  # Replace with your State variable\n",
        "State2 = list(\"rooo/rrb\")\n",
        "State3 = list(\"oorrrb/o\")\n",
        "State4 = list(\"ooorrb/r\")\n",
        "\n",
        "print(f'Any odd redshirts out State1? {odd_redshirt_out(State1)}.\\n')\n",
        "print(f'Any odd redshirts out State2? {odd_redshirt_out(State2)}.\\n')\n",
        "print(f'Any odd redshirts out State3? {odd_redshirt_out(State3)}.\\n')\n",
        "print(f'Any odd redshirts out State4? {odd_redshirt_out(State4)}.\\n')"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "XGN7HeJEWCH2",
        "outputId": "5f9322c4-04ab-4d1f-cfa2-abf100f37e0a"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Any odd redshirts out State1? False.\n",
            "\n",
            "Any odd redshirts out State2? True.\n",
            "\n",
            "Any odd redshirts out State3? False.\n",
            "\n",
            "Any odd redshirts out State4? True.\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# @title Random Brute-Force Solution Finder\n",
        "\n",
        "# To keep output tidy\n",
        "from IPython.display import clear_output\n",
        "keep_tidy = True\n",
        "\n",
        "'''\n",
        " Finally, we're ready to put these functions together in a way which solves the problem!\n",
        "\n",
        " Because we're not being systematic, sometimes dead ends happen: e.g., we end up in a state like ro/oorrb in which\n",
        "  all possible crossings leave an odd redshirt out. If we do nothing, the PSS will get stuck in an infinite loop at these\n",
        "  points. So, we need it to check that it's not in a loop, and, if in a loop, to halt and report a failed search.\n",
        "'''\n",
        "\n",
        "def River_crossing_solution_finder(Initial_State_,\n",
        "                                   Final_State_,\n",
        "                                   cross_func,\n",
        "                                   heuristics_func_left=identity_function2,\n",
        "                                   heuristics_func_right=identity_function3,\n",
        "                                   max_crossings=50):\n",
        "\n",
        "  # Initiate variables to keep track of the number of crossings made,\n",
        "  #  and also the number of failed crossings (crossings which leave a redshirt as the odd one out).\n",
        "  failed_crossings = 0\n",
        "  crossings = 0\n",
        "\n",
        "  # Initiate a variable to keep track of the current state and initiate it in the problem's Initial State.\n",
        "  State = Initial_State\n",
        "\n",
        "  print(f\"\\nBeginning in Initial State: {State}\\n\")\n",
        "\n",
        "  # Continually loop until a return is triggered\n",
        "  while True:\n",
        "\n",
        "    # Step 1: Perform a random river crossing\n",
        "    #   ... store in a temporary variable, until we check that the crossing didn't fail.\n",
        "    State_new = cross_func(State, heuristics_func_left, heuristics_func_right)\n",
        "\n",
        "    # Step 2: Check if this crossing left any odd redshirts out (i.e., if it failed)\n",
        "    #   ... if not, update State\n",
        "    if not odd_redshirt_out(State_new):\n",
        "      State = State_new\n",
        "      crossings += 1\n",
        "      print(f\"Crossing {crossings}, New State after crossing: {State}\\n\")\n",
        "    else:\n",
        "      failed_crossings += 1\n",
        "      print(f\"Aborting attempt! Would be failed crossing / leave red shirt odd-one-out, Gorn attack!\")\n",
        "\n",
        "    # Step 3: Check if we're in the solution state\n",
        "    '''\n",
        "      We're cheating a little here; instead of comparing the whole \"complex symbol\" State to Solution_State,\n",
        "      we're just comparing their first character. This is because, really, the \"solution\" is just to have the slash\n",
        "      as the first character (i.e., to get all characters to the right of the slash).\n",
        "    '''\n",
        "    if State[0] == Solution_State[0]:\n",
        "      print(f\"Solution State Found!\\n\")\n",
        "      print(f\"Number of crossings used (length of solution path): {crossings}\\n\")\n",
        "      return(True)\n",
        "\n",
        "    # Check if we're stuck. (If more than 10 failed crossings, abort and start over.)\n",
        "    if failed_crossings > 10 or crossings > max_crossings:\n",
        "      return(False)\n",
        "\n",
        "found_solution = False\n",
        "Try = 0\n",
        "\n",
        "# Loop the solution_finder until a solution is found.\n",
        "while not found_solution:\n",
        "\n",
        "  # Keep track of how many times we have to run the solution finder until it succeeds.\n",
        "  Try += 1\n",
        "\n",
        "  # Run solution_finder and check if it finds a solution.\n",
        "  if River_crossing_solution_finder(Initial_State,Solution_State,cross_river):\n",
        "    found_solution = True\n",
        "    print(f'Total number of paths searched to find solution: {Try}\\n')\n",
        "  else:\n",
        "    print(\"\\nTrapped by Gorn! Failed search path.\")\n",
        "    if keep_tidy:\n",
        "      clear_output()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "_W3C-eTBZExG",
        "outputId": "3363b618-efa9-41b3-ac80-b252fa0b785f"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\n",
            "Beginning in Initial State: ['o', 'o', 'o', 'r', 'r', 'r', 'b', '/']\n",
            "\n",
            "Current state: ['o', 'o', 'o', 'r', 'r', 'r', 'b', '/'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: o, r\n",
            "Crossing 1, New State after crossing: ['o', 'o', 'r', 'r', '/', 'o', 'r', 'b']\n",
            "\n",
            "Current state: ['o', 'o', 'r', 'r', '/', 'o', 'r', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: r\n",
            "Crossing 2, New State after crossing: ['o', 'o', 'r', 'r', 'r', 'b', '/', 'o']\n",
            "\n",
            "Current state: ['o', 'o', 'r', 'r', 'r', 'b', '/', 'o'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: o\n",
            "Crossing 3, New State after crossing: ['o', 'r', 'r', 'r', '/', 'o', 'o', 'b']\n",
            "\n",
            "Current state: ['o', 'r', 'r', 'r', '/', 'o', 'o', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: o\n",
            "Crossing 4, New State after crossing: ['o', 'r', 'r', 'r', 'o', 'b', '/', 'o']\n",
            "\n",
            "Current state: ['o', 'r', 'r', 'r', 'o', 'b', '/', 'o'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: o, o\n",
            "Crossing 5, New State after crossing: ['r', 'r', 'r', '/', 'o', 'o', 'o', 'b']\n",
            "\n",
            "Current state: ['r', 'r', 'r', '/', 'o', 'o', 'o', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: o\n",
            "Crossing 6, New State after crossing: ['r', 'r', 'r', 'o', 'b', '/', 'o', 'o']\n",
            "\n",
            "Current state: ['r', 'r', 'r', 'o', 'b', '/', 'o', 'o'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: r, r\n",
            "Crossing 7, New State after crossing: ['r', 'o', '/', 'o', 'o', 'r', 'r', 'b']\n",
            "\n",
            "Current state: ['r', 'o', '/', 'o', 'o', 'r', 'r', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: r\n",
            "Aborting attempt! Would be failed crossing / leave red shirt odd-one-out, Gorn attack!\n",
            "Current state: ['r', 'o', '/', 'o', 'o', 'r', 'r', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: o\n",
            "Aborting attempt! Would be failed crossing / leave red shirt odd-one-out, Gorn attack!\n",
            "Current state: ['r', 'o', '/', 'o', 'o', 'r', 'r', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: r\n",
            "Aborting attempt! Would be failed crossing / leave red shirt odd-one-out, Gorn attack!\n",
            "Current state: ['r', 'o', '/', 'o', 'o', 'r', 'r', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: r, r\n",
            "Crossing 8, New State after crossing: ['r', 'o', 'r', 'r', 'b', '/', 'o', 'o']\n",
            "\n",
            "Current state: ['r', 'o', 'r', 'r', 'b', '/', 'o', 'o'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: r, r\n",
            "Crossing 9, New State after crossing: ['o', 'r', '/', 'o', 'o', 'r', 'r', 'b']\n",
            "\n",
            "Current state: ['o', 'r', '/', 'o', 'o', 'r', 'r', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: o\n",
            "Aborting attempt! Would be failed crossing / leave red shirt odd-one-out, Gorn attack!\n",
            "Current state: ['o', 'r', '/', 'o', 'o', 'r', 'r', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: r\n",
            "Aborting attempt! Would be failed crossing / leave red shirt odd-one-out, Gorn attack!\n",
            "Current state: ['o', 'r', '/', 'o', 'o', 'r', 'r', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: o\n",
            "Aborting attempt! Would be failed crossing / leave red shirt odd-one-out, Gorn attack!\n",
            "Current state: ['o', 'r', '/', 'o', 'o', 'r', 'r', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: r, o\n",
            "Crossing 10, New State after crossing: ['o', 'r', 'r', 'o', 'b', '/', 'o', 'r']\n",
            "\n",
            "Current state: ['o', 'r', 'r', 'o', 'b', '/', 'o', 'r'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: o, r\n",
            "Crossing 11, New State after crossing: ['r', 'o', '/', 'o', 'r', 'o', 'r', 'b']\n",
            "\n",
            "Current state: ['r', 'o', '/', 'o', 'r', 'o', 'r', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: r, o\n",
            "Crossing 12, New State after crossing: ['r', 'o', 'r', 'o', 'b', '/', 'o', 'r']\n",
            "\n",
            "Current state: ['r', 'o', 'r', 'o', 'b', '/', 'o', 'r'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: r, r\n",
            "Crossing 13, New State after crossing: ['o', 'o', '/', 'o', 'r', 'r', 'r', 'b']\n",
            "\n",
            "Current state: ['o', 'o', '/', 'o', 'r', 'r', 'r', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: r\n",
            "Aborting attempt! Would be failed crossing / leave red shirt odd-one-out, Gorn attack!\n",
            "Current state: ['o', 'o', '/', 'o', 'r', 'r', 'r', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: o\n",
            "Crossing 14, New State after crossing: ['o', 'o', 'o', 'b', '/', 'r', 'r', 'r']\n",
            "\n",
            "Current state: ['o', 'o', 'o', 'b', '/', 'r', 'r', 'r'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: o, o\n",
            "Crossing 15, New State after crossing: ['o', '/', 'r', 'r', 'r', 'o', 'o', 'b']\n",
            "\n",
            "Current state: ['o', '/', 'r', 'r', 'r', 'o', 'o', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: r\n",
            "Crossing 16, New State after crossing: ['o', 'r', 'b', '/', 'r', 'r', 'o', 'o']\n",
            "\n",
            "Current state: ['o', 'r', 'b', '/', 'r', 'r', 'o', 'o'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: r\n",
            "Crossing 17, New State after crossing: ['o', '/', 'r', 'r', 'o', 'o', 'r', 'b']\n",
            "\n",
            "Current state: ['o', '/', 'r', 'r', 'o', 'o', 'r', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: o\n",
            "Crossing 18, New State after crossing: ['o', 'o', 'b', '/', 'r', 'r', 'o', 'r']\n",
            "\n",
            "Current state: ['o', 'o', 'b', '/', 'r', 'r', 'o', 'r'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: o, o\n",
            "Crossing 19, New State after crossing: ['/', 'r', 'r', 'o', 'r', 'o', 'o', 'b']\n",
            "\n",
            "Solution State Found!\n",
            "\n",
            "Number of crossings used (length of solution path): 19\n",
            "\n",
            "Total number of paths searched to find solution: 1205\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Conclusion\n",
        "\n",
        "There you go! Because the algorithm is randomly selecting characters to move at each \"crossing\", each time it's run it will take a different number of path searches to find a solution path, and it will find different solution paths of different lengths."
      ],
      "metadata": {
        "id": "-32nYmH9-tAO"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Exercise: Improve Algorithm with Heuristics\n",
        "\n",
        "The above solution used a brute-force method to solve the problem. In essence, it randomly searches all possible paths in the \"crossing space\" until it finds a crossing which solves the problem. Because it's random, the solutions it finds are normally longer (more crossings) than a person could devise with reason, and it often takes many tries until it finds a solution, because its random selection often leads it into dead ends in which a red shirt is always left outnumbered by officers. (For example, I solved the problem by hand in 12 crossings, as outlined in the lecture slides.)\n",
        "\n",
        "What we want to do now is program two heuristic rules which will help speed up our search and shorten the solution found to 15 or less crossings.\n",
        "\n",
        "To ensure we have 15 or fewer crossings, we will simply set the solution_finder so that it exits as a failed attempt if there are more than 15 crossings.\n",
        "\n",
        "More importantly, we will now set a heuristic rule, one for how to handle crossing left-to-right, and one for how to handle crossing right-to-left. In English, the heuristics we'll use are:\n",
        "\n",
        "**Left-to-Right:** If a passenger can be taken, then take them. (Never cross with just a boat pilot, if there are more than two people on the left.)\n",
        "\n",
        "**Right-to-Left:** If all three red shirts are on the right side of the river and there is also an officer on this side of the river who can pilot the boat back to the left side, then the officer should pilot the boat back alone.\n",
        "\n",
        "Exercise instructions: Fill in the code below to define precise functions for these heuristic rules. Then, run the code to see what the algorithm finds."
      ],
      "metadata": {
        "id": "IwFhSa7NYkZ-"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "\n",
        "# Define heuristic functions for crossing left-to-right and right-to-left\n",
        "\n",
        "maximum_crossings = 15\n",
        "\n",
        "def force_passenger(original_list,people_left):\n",
        "  if FILL-IN-CONDITION-HERE:\n",
        "    return FILL-IN-WHAT-TO-RETURN\n",
        "  else:\n",
        "    return original_list\n",
        "\n",
        "def keep_redshirts_right(original_list,people_left,people_right):\n",
        "  if FILL-IN-CONDITION-HERE:\n",
        "    return FILL-IN-WHAT-TO-RETURN\n",
        "  else:\n",
        "    return original_list\n",
        "\n",
        "# Now rerun the solution finder using these heuristics\n",
        "found_solution = False\n",
        "Try = 0\n",
        "\n",
        "# Loop the solution_finder until a solution is found.\n",
        "while not found_solution:\n",
        "\n",
        "  # Keep track of how many times we have to run the solution finder until it succeeds.\n",
        "  Try += 1\n",
        "\n",
        "  # Run solution_finder and check if it finds a solution.\n",
        "  if River_crossing_solution_finder(Initial_State,Solution_State,cross_river,\n",
        "                                    heuristics_func_left=force_passenger,\n",
        "                                    heuristics_func_right=keep_redshirts_right,\n",
        "                                    max_crossings=maximum_crossings):\n",
        "    found_solution = True\n",
        "    print(f'Total number of paths searched to find solution: {Try}\\n')\n",
        "  else:\n",
        "    print(\"\\nTrapped by Gorn! Failed search path.\")\n",
        "    if keep_tidy:\n",
        "      clear_output()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "c9Bvjm8keh0U",
        "outputId": "dbf87bc2-bdd2-4fab-cfcc-857f548f732c"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\n",
            "Beginning in Initial State: ['o', 'o', 'o', 'r', 'r', 'r', 'b', '/']\n",
            "\n",
            "Current state: ['o', 'o', 'o', 'r', 'r', 'r', 'b', '/'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: o, o\n",
            "Crossing 1, New State after crossing: ['o', 'r', 'r', 'r', '/', 'o', 'o', 'b']\n",
            "\n",
            "Current state: ['o', 'r', 'r', 'r', '/', 'o', 'o', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: o, o\n",
            "Crossing 2, New State after crossing: ['o', 'r', 'r', 'r', 'o', 'o', 'b', '/']\n",
            "\n",
            "Current state: ['o', 'r', 'r', 'r', 'o', 'o', 'b', '/'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: r, r\n",
            "Aborting attempt! Would be failed crossing / leave red shirt odd-one-out, Gorn attack!\n",
            "Current state: ['o', 'r', 'r', 'r', 'o', 'o', 'b', '/'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: r, r\n",
            "Aborting attempt! Would be failed crossing / leave red shirt odd-one-out, Gorn attack!\n",
            "Current state: ['o', 'r', 'r', 'r', 'o', 'o', 'b', '/'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: o, o\n",
            "Crossing 3, New State after crossing: ['r', 'r', 'r', 'o', '/', 'o', 'o', 'b']\n",
            "\n",
            "Current state: ['r', 'r', 'r', 'o', '/', 'o', 'o', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: o\n",
            "Crossing 4, New State after crossing: ['r', 'r', 'r', 'o', 'o', 'b', '/', 'o']\n",
            "\n",
            "Current state: ['r', 'r', 'r', 'o', 'o', 'b', '/', 'o'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: r, r\n",
            "Aborting attempt! Would be failed crossing / leave red shirt odd-one-out, Gorn attack!\n",
            "Current state: ['r', 'r', 'r', 'o', 'o', 'b', '/', 'o'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: o, o\n",
            "Crossing 5, New State after crossing: ['r', 'r', 'r', '/', 'o', 'o', 'o', 'b']\n",
            "\n",
            "Current state: ['r', 'r', 'r', '/', 'o', 'o', 'o', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: o\n",
            "Crossing 6, New State after crossing: ['r', 'r', 'r', 'o', 'b', '/', 'o', 'o']\n",
            "\n",
            "Current state: ['r', 'r', 'r', 'o', 'b', '/', 'o', 'o'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: r, r\n",
            "Crossing 7, New State after crossing: ['r', 'o', '/', 'o', 'o', 'r', 'r', 'b']\n",
            "\n",
            "Current state: ['r', 'o', '/', 'o', 'o', 'r', 'r', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: o, o\n",
            "Aborting attempt! Would be failed crossing / leave red shirt odd-one-out, Gorn attack!\n",
            "Current state: ['r', 'o', '/', 'o', 'o', 'r', 'r', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: o\n",
            "Aborting attempt! Would be failed crossing / leave red shirt odd-one-out, Gorn attack!\n",
            "Current state: ['r', 'o', '/', 'o', 'o', 'r', 'r', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: r, o\n",
            "Crossing 8, New State after crossing: ['r', 'o', 'r', 'o', 'b', '/', 'o', 'r']\n",
            "\n",
            "Current state: ['r', 'o', 'r', 'o', 'b', '/', 'o', 'r'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: r, r\n",
            "Crossing 9, New State after crossing: ['o', 'o', '/', 'o', 'r', 'r', 'r', 'b']\n",
            "\n",
            "Current state: ['o', 'o', '/', 'o', 'r', 'r', 'r', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: o\n",
            "Crossing 10, New State after crossing: ['o', 'o', 'o', 'b', '/', 'r', 'r', 'r']\n",
            "\n",
            "Current state: ['o', 'o', 'o', 'b', '/', 'r', 'r', 'r'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: o, o\n",
            "Crossing 11, New State after crossing: ['o', '/', 'r', 'r', 'r', 'o', 'o', 'b']\n",
            "\n",
            "Current state: ['o', '/', 'r', 'r', 'r', 'o', 'o', 'b'].\n",
            "Boat is on right.\n",
            "Crossing river with characters: o\n",
            "Crossing 12, New State after crossing: ['o', 'o', 'b', '/', 'r', 'r', 'r', 'o']\n",
            "\n",
            "Current state: ['o', 'o', 'b', '/', 'r', 'r', 'r', 'o'].\n",
            "Boat is on left.\n",
            "Crossing river with characters: o, o\n",
            "Crossing 13, New State after crossing: ['/', 'r', 'r', 'r', 'o', 'o', 'o', 'b']\n",
            "\n",
            "Solution State Found!\n",
            "\n",
            "Number of crossings used (length of solution path): 13\n",
            "\n",
            "Total number of paths searched to find solution: 9\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Conclusion\n",
        "\n",
        "You should see how the new algoritm, using heuristics, is much faster and returns a shorter crossing path (always under 15 crossings long) than the original, brute-force random search algorithm!"
      ],
      "metadata": {
        "id": "ZAuFa_XNnwBK"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Solution Code\n",
        "\n",
        "See below for a possible solution (two heuristic functions which will work)."
      ],
      "metadata": {
        "id": "HGuYzmBF7s4i"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# @title Solution\n",
        "\n",
        "def force_passenger(original_list,people_left):\n",
        "  if len(people_left) > 1:\n",
        "    return random.sample(people_left, 2)\n",
        "  else:\n",
        "    return original_list\n",
        "\n",
        "def keep_redshirts_right(original_list,people_left,people_right):\n",
        "  if 'r' not in people_left and 'o' in people_right:\n",
        "    return list(\"o\")\n",
        "  else:\n",
        "    return(original_list)"
      ],
      "metadata": {
        "id": "c_XzrwIh5KGl"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}