fork download
copy 
  1. """
  2. Python basics and search algorithms
  3. ===================================
  4.  
  5. This single file is a small, beginner-friendly reference for:
  6. 1. Basic Python, NumPy, and pandas
  7. 2. UCS, BFS, and DFS search
  8. 3. Greedy Best-First Search and A*
  9.  
  10. Run this file with:
  11.     python python_and_search_algorithms.py
  12.  
  13. The examples use fixed values so the file can run without waiting for input.
  14. An input() example is included in basic_python_demo().
  15. """
  16.  
  17. from __future__ import annotations
  18.  
  19. from collections import deque
  20. import heapq
  21. from statistics import mean, median
  22.  
  23.  
  24. def basic_python_demo() -> None:
  25.     """Show common Python ideas with simple examples."""
  26.     print("\n" + "=" * 60)
  27.     print("1. BASIC PYTHON")
  28.     print("=" * 60)
  29.  
  30.     # -------------------- Data types --------------------
  31.     age = 20                       # int: a whole number
  32.     height = 1.75                   # float: a decimal number
  33.     name = "Amina"                 # str: text
  34.     is_student = True              # bool: True or False
  35.     nothing = None                 # None: no value
  36.  
  37.     print("\nData types:")
  38.     print(age, type(age))
  39.     print(height, type(height))
  40.     print(name, type(name))
  41.     print(is_student, type(is_student))
  42.     print(nothing, type(nothing))
  43.  
  44.     # Collections: list, tuple, set, and dictionary
  45.     scores = [80, 95, 72, 88]                  # mutable ordered collection
  46.     coordinates = (10, 20)                    # immutable ordered collection
  47.     unique_numbers = {1, 2, 2, 3}             # duplicate values disappear
  48.     student = {"name": name, "age": age}      # key-value pairs
  49.  
  50.     print("\nCollections:")
  51.     print("List:", scores)
  52.     print("Tuple:", coordinates)
  53.     print("Set:", unique_numbers)
  54.     print("Dictionary:", student)
  55.  
  56.     # -------------------- Output and input --------------------
  57.     print("\nOutput:")
  58.     print(f"{name} has an average score of {mean(scores):.2f}.")
  59.  
  60.     # This is the normal way to read text from a user:
  61.     # user_name = input("What is your name? ")
  62.     # print("Hello,", user_name)
  63.     #
  64.     # The line is commented out so this teaching file can run automatically.
  65.     sample_input = "  python  "
  66.     print("Input example after strip and upper:", sample_input.strip().upper())
  67.  
  68.     # -------------------- Conditions --------------------
  69.     print("\nConditional statements:")
  70.     if mean(scores) >= 80:
  71.         print("The student is doing very well.")
  72.     elif mean(scores) >= 50:
  73.         print("The student passed.")
  74.     else:
  75.         print("The student needs more practice.")
  76.  
  77.     # -------------------- Loops and filtering --------------------
  78.     print("\nLoops and filtering:")
  79.     for score in scores:
  80.         print("Score:", score)
  81.  
  82.     # A list comprehension creates a new list in one readable line.
  83.     passed_scores = [score for score in scores if score >= 80]
  84.     print("Scores >= 80:", passed_scores)
  85.  
  86.     # -------------------- Functions --------------------
  87.     def square(number: float) -> float:
  88.         """Return the square of a number."""
  89.         return number * number
  90.  
  91.     def average(values: list[float]) -> float:
  92.         """Return the arithmetic mean of a non-empty list."""
  93.         if not values:
  94.             raise ValueError("average() needs at least one value")
  95.         return sum(values) / len(values)
  96.  
  97.     print("\nFunctions:")
  98.     print("square(5) =", square(5))
  99.     print("average(scores) =", average(scores))
  100.     print("statistics.mean(scores) =", mean(scores))
  101.     print("statistics.median(scores) =", median(scores))
  102.  
  103.     # -------------------- Class, methods, and objects --------------------
  104.     class Student:
  105.         """A simple class that stores a student's data."""
  106.  
  107.         def __init__(self, student_name: str, student_scores: list[float]) -> None:
  108.             self.name = student_name       # attribute
  109.             self.scores = student_scores   # attribute
  110.  
  111.         def get_average(self) -> float:
  112.             """A method that calculates this student's average."""
  113.             return average(self.scores)
  114.  
  115.         def describe(self) -> str:
  116.             """A method that returns a sentence about the object."""
  117.             return f"{self.name} has an average of {self.get_average():.2f}."
  118.  
  119.     # student_one is an object created from the Student class.
  120.     student_one = Student("Amina", [80, 95, 72, 88])
  121.     print("\nClass and object:")
  122.     print("Object attribute name:", student_one.name)
  123.     print("Object attribute scores:", student_one.scores)
  124.     print("Calling a method:", student_one.describe())
  125.  
  126.     # -------------------- NumPy and pandas --------------------
  127.     print("\nNumPy and pandas:")
  128.     try:
  129.         import numpy as np
  130.         import pandas as pd
  131.     except ImportError:
  132.         print("NumPy/pandas are not installed in this Python environment.")
  133.         print("Install them with: python -m pip install numpy pandas")
  134.         return
  135.  
  136.     # NumPy arrays are useful for fast numerical operations.
  137.     numbers = np.array([10, 20, 30, 40])
  138.     print("NumPy array:", numbers)
  139.     print("Array multiplied by 2:", numbers * 2)
  140.     print("NumPy mean:", numbers.mean())
  141.     print("NumPy median:", np.median(numbers))
  142.  
  143.     # A DataFrame is a table with rows and named columns.
  144.     data = {
  145.         "name": ["Amina", "Bilal", "Chloe", "David"],
  146.         "age": [20, 22, 19, 21],
  147.         "score": [88, 75, 95, 60],
  148.     }
  149.     frame = pd.DataFrame(data)
  150.     print("\nComplete DataFrame:")
  151.     print(frame)
  152.  
  153.     # Select one column, one row, and one specific cell.
  154.     print("\nOnly the score column:")
  155.     print(frame["score"])
  156.     print("\nFirst row with iloc:")
  157.     print(frame.iloc[0])
  158.     print("\nSpecific value (row 1, score column):")
  159.     print(frame.loc[1, "score"])
  160.  
  161.     # Conditions in a DataFrame return only matching rows.
  162.     high_scores = frame[frame["score"] >= 80]
  163.     adults_with_high_scores = frame[(frame["age"] >= 20) & (frame["score"] >= 80)]
  164.     print("\nStudents with score >= 80:")
  165.     print(high_scores)
  166.     print("\nStudents age >= 20 and score >= 80:")
  167.     print(adults_with_high_scores)
  168.  
  169.  
  170. # A graph is represented as: node -> [(neighbor, cost), ...].
  171. WeightedGraph = dict[str, list[tuple[str, float]]]
  172.  
  173.  
  174. def ucs(graph: WeightedGraph, start: str, goal: str) -> tuple[list[str], float]:
  175.     """Uniform Cost Search: find the least-cost path in a weighted graph."""
  176.     queue: list[tuple[float, str, list[str]]] = [(0, start, [start])]
  177.     best_cost: dict[str, float] = {start: 0}
  178.  
  179.     while queue:
  180.         cost, node, path = heapq.heappop(queue)
  181.         if node == goal:
  182.             return path, cost
  183.         if cost > best_cost.get(node, float("inf")):
  184.             continue
  185.  
  186.         for neighbor, edge_cost in graph.get(node, []):
  187.             new_cost = cost + edge_cost
  188.             if new_cost < best_cost.get(neighbor, float("inf")):
  189.                 best_cost[neighbor] = new_cost
  190.                 heapq.heappush(queue, (new_cost, neighbor, path + [neighbor]))
  191.  
  192.     return [], float("inf")
  193.  
  194.  
  195. def bfs(graph: WeightedGraph, start: str, goal: str) -> list[str]:
  196.     """Breadth-First Search: find a path with the fewest edges."""
  197.     queue = deque([(start, [start])])
  198.     visited = {start}
  199.  
  200.     while queue:
  201.         node, path = queue.popleft()
  202.         if node == goal:
  203.             return path
  204.  
  205.         for neighbor, _ in graph.get(node, []):
  206.             if neighbor not in visited:
  207.                 visited.add(neighbor)
  208.                 queue.append((neighbor, path + [neighbor]))
  209.  
  210.     return []
  211.  
  212.  
  213. def dfs(graph: WeightedGraph, start: str, goal: str) -> list[str]:
  214.     """Depth-First Search: explore one branch deeply before another."""
  215.     stack = [(start, [start])]
  216.     visited: set[str] = set()
  217.  
  218.     while stack:
  219.         node, path = stack.pop()
  220.         if node in visited:
  221.             continue
  222.         visited.add(node)
  223.  
  224.         if node == goal:
  225.             return path
  226.  
  227.         # Reverse keeps the example's left-to-right order predictable.
  228.         for neighbor, _ in reversed(graph.get(node, [])):
  229.             if neighbor not in visited:
  230.                 stack.append((neighbor, path + [neighbor]))
  231.  
  232.     return []
  233.  
  234.  
  235. def heuristic(node: str, goal: str) -> float:
  236.     """An example heuristic: estimated remaining cost.
  237.  
  238.     A real heuristic uses problem knowledge, such as straight-line distance.
  239.     Here, the values are hand-written only to keep the example easy to read.
  240.     """
  241.     estimates = {
  242.         "A": 7,
  243.         "B": 6,
  244.         "C": 2,
  245.         "D": 3,
  246.         "E": 1,
  247.         "F": 0,
  248.     }
  249.     return estimates.get(node, 0) if node != goal else 0
  250.  
  251.  
  252. def greedy_best_first(
  253.     graph: WeightedGraph, start: str, goal: str
  254. ) -> tuple[list[str], float]:
  255.     """Greedy Best-First Search: choose the smallest h(n) first."""
  256.     queue: list[tuple[float, float, str, list[str]]] = [
  257.         (heuristic(start, goal), 0, start, [start])
  258.     ]
  259.     visited: set[str] = set()
  260.  
  261.     while queue:
  262.         _, cost, node, path = heapq.heappop(queue)
  263.         if node in visited:
  264.             continue
  265.         visited.add(node)
  266.         if node == goal:
  267.             return path, cost
  268.  
  269.         for neighbor, edge_cost in graph.get(node, []):
  270.             if neighbor not in visited:
  271.                 heapq.heappush(
  272.                     queue,
  273.                     (
  274.                         heuristic(neighbor, goal),
  275.                         cost + edge_cost,
  276.                         neighbor,
  277.                         path + [neighbor],
  278.                     ),
  279.                 )
  280.  
  281.     return [], float("inf")
  282.  
  283.  
  284. def a_star(graph: WeightedGraph, start: str, goal: str) -> tuple[list[str], float]:
  285.     """A*: choose the smallest f(n) = g(n) + h(n)."""
  286.     queue: list[tuple[float, float, str, list[str]]] = [
  287.         (heuristic(start, goal), 0, start, [start])
  288.     ]
  289.     best_cost: dict[str, float] = {start: 0}
  290.  
  291.     while queue:
  292.         _, cost, node, path = heapq.heappop(queue)
  293.         if node == goal:
  294.             return path, cost
  295.         if cost > best_cost.get(node, float("inf")):
  296.             continue
  297.  
  298.         for neighbor, edge_cost in graph.get(node, []):
  299.             new_cost = cost + edge_cost
  300.             if new_cost < best_cost.get(neighbor, float("inf")):
  301.                 best_cost[neighbor] = new_cost
  302.                 estimated_total = new_cost + heuristic(neighbor, goal)
  303.                 heapq.heappush(
  304.                     queue,
  305.                     (estimated_total, new_cost, neighbor, path + [neighbor]),
  306.                 )
  307.  
  308.     return [], float("inf")
  309.  
  310.  
  311. def search_algorithms_demo() -> None:
  312.     """Run all search algorithms on the same small graph."""
  313.     print("\n" + "=" * 60)
  314.     print("2. UCS, BFS, DFS, GREEDY BEST-FIRST, AND A*")
  315.     print("=" * 60)
  316.  
  317.     graph: WeightedGraph = {
  318.         "A": [("B", 2), ("C", 5)],
  319.         "B": [("D", 4), ("E", 10)],
  320.         "C": [("E", 1)],
  321.         "D": [("F", 3)],
  322.         "E": [("F", 2)],
  323.         "F": [],
  324.     }
  325.  
  326.     print("\nGraph edges:")
  327.     for node, edges in graph.items():
  328.         print(f"{node} -> {edges}")
  329.  
  330.     path, cost = ucs(graph, "A", "F")
  331.     print("\nUCS:", path, "cost =", cost)
  332.     print("BFS:", bfs(graph, "A", "F"), "(fewest edges, ignores costs)")
  333.     print("DFS:", dfs(graph, "A", "F"), "(first deep path found)")
  334.  
  335.     greedy_path, greedy_cost = greedy_best_first(graph, "A", "F")
  336.     a_star_path, a_star_cost = a_star(graph, "A", "F")
  337.     print("Greedy Best-First:", greedy_path, "cost =", greedy_cost)
  338.     print("A*:", a_star_path, "cost =", a_star_cost)
  339.  
  340.     print("\nComparison:")
  341.     print("- UCS uses g(n), the cost already travelled. It finds an optimal path.")
  342.     print("- BFS uses depth. It is optimal only when every edge has equal cost.")
  343.     print("- DFS uses depth-first exploration. It may find a non-optimal path.")
  344.     print("- Greedy uses h(n), the estimated distance to the goal. It can be fast")
  345.     print("  but is not always optimal.")
  346.     print("- A* uses g(n) + h(n). With a good admissible heuristic, it is both")
  347.     print("  efficient and optimal.")
  348.  
  349.  
  350. def main() -> None:
  351.     basic_python_demo()
  352.     search_algorithms_demo()
  353.  
  354.  
  355. if __name__ == "__main__":
  356.     main()
  357.  
Success #stdin #stdout 2.23s 78576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
============================================================
1. BASIC PYTHON
============================================================

Data types:
20 <class 'int'>
1.75 <class 'float'>
Amina <class 'str'>
True <class 'bool'>
None <class 'NoneType'>

Collections:
List: [80, 95, 72, 88]
Tuple: (10, 20)
Set: {1, 2, 3}
Dictionary: {'name': 'Amina', 'age': 20}

Output:
Amina has an average score of 83.75.
Input example after strip and upper: PYTHON

Conditional statements:
The student is doing very well.

Loops and filtering:
Score: 80
Score: 95
Score: 72
Score: 88
Scores >= 80: [80, 95, 88]

Functions:
square(5) = 25
average(scores) = 83.75
statistics.mean(scores) = 83.75
statistics.median(scores) = 84.0

Class and object:
Object attribute name: Amina
Object attribute scores: [80, 95, 72, 88]
Calling a method: Amina has an average of 83.75.

NumPy and pandas:
NumPy array: [10 20 30 40]
Array multiplied by 2: [20 40 60 80]
NumPy mean: 25.0
NumPy median: 25.0

Complete DataFrame:
    name  age  score
0  Amina   20     88
1  Bilal   22     75
2  Chloe   19     95
3  David   21     60

Only the score column:
0    88
1    75
2    95
3    60
Name: score, dtype: int64

First row with iloc:
name     Amina
age         20
score       88
Name: 0, dtype: object

Specific value (row 1, score column):
75

Students with score >= 80:
    name  age  score
0  Amina   20     88
2  Chloe   19     95

Students age >= 20 and score >= 80:
    name  age  score
0  Amina   20     88

============================================================
2. UCS, BFS, DFS, GREEDY BEST-FIRST, AND A*
============================================================

Graph edges:
A -> [('B', 2), ('C', 5)]
B -> [('D', 4), ('E', 10)]
C -> [('E', 1)]
D -> [('F', 3)]
E -> [('F', 2)]
F -> []

UCS: ['A', 'C', 'E', 'F'] cost = 8
BFS: ['A', 'B', 'D', 'F'] (fewest edges, ignores costs)
DFS: ['A', 'B', 'D', 'F'] (first deep path found)
Greedy Best-First: ['A', 'C', 'E', 'F'] cost = 8
A*: ['A', 'C', 'E', 'F'] cost = 8

Comparison:
- UCS uses g(n), the cost already travelled. It finds an optimal path.
- BFS uses depth. It is optimal only when every edge has equal cost.
- DFS uses depth-first exploration. It may find a non-optimal path.
- Greedy uses h(n), the estimated distance to the goal. It can be fast
  but is not always optimal.
- A* uses g(n) + h(n). With a good admissible heuristic, it is both
  efficient and optimal.
https://ideone.com/SYtf9G
language:
Python 3 (python  3.12)
created:
2 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!