DEV Community: johnsone emett

greedy challenges

johnsone emett — Thu, 27 Mar 2025 03:16:36 +0000


# Problem Statement:
# Given a set of cities and the distances between them, find the shortest possible route that visits each city
# exactly once and returns to the origin city.

import random

def calc_total_distance(route, distance_matrix):
    total_distance = 0
    for i in range(len(route) - 1):
        total_distance += distance_matrix[route[i]][route[i + 1]]
    total_distance += distance_matrix[route[-1]][route[0]]  # Return to start
    return total_distance

def two_opt(route, distance_matrix):
    best_route = route[:]
    best_distance = calc_total_distance(route, distance_matrix)

    for i in range(1, len(route) - 1):
        for j in range(i + 1, len(route)):
            new_route = route[:i] + route[i:j+1][::-1] + route[j+1:]
            new_distance = calc_total_distance(new_route, distance_matrix)

            if new_distance < best_distance:
                best_route = new_route
                best_distance = new_distance

    return best_route, best_distance

# Test TSP
distance_matrix = [[0, 1, 2, 3], [1, 0, 4, 5], [2, 4, 0, 6], [3, 5, 6, 0]]
route = [0, 1, 2, 3]
best_route, best_distance = two_opt(route, distance_matrix)
print("Best Route:", best_route)
print("Best Distance:", best_distance)


# Problem Statement:
# Given a set of cities and the distances between them, find the shortest possible route that visits each city
# exactly once and returns to the origin city.

import random

def calc_total_distance(route, distance_matrix):
    total_distance = 0
    for i in range(len(route) - 1):
        total_distance += distance_matrix[route[i]][route[i + 1]]
    total_distance += distance_matrix[route[-1]][route[0]]  # Return to start
    return total_distance

def two_opt(route, distance_matrix):
    best_route = route[:]
    best_distance = calc_total_distance(route, distance_matrix)

    for i in range(1, len(route) - 1):
        for j in range(i + 1, len(route)):
            new_route = route[:i] + route[i:j+1][::-1] + route[j+1:]
            new_distance = calc_total_distance(new_route, distance_matrix)

            if new_distance < best_distance:
                best_route = new_route
                best_distance = new_distance

    return best_route, best_distance

# Test TSP
distance_matrix = [[0, 1, 2, 3], [1, 0, 4, 5], [2, 4, 0, 6], [3, 5, 6, 0]]
route = [0, 1, 2, 3]
best_route, best_distance = two_opt(route, distance_matrix)
print("Best Route:", best_route)
print("Best Distance:", best_distance)




# Problem Statement:
# Given a set of jobs, each with a processing time, you need to schedule them on a set of machines to minimize 
# the total completion time.

def schedule_jobs(jobs, num_machines):
    jobs.sort(reverse=True)  # Sort jobs by descending order of time
    machines = [0] * num_machines  # Machines start with 0 time

    for job in jobs:
        # Assign the job to the machine with the minimum current load
        machine_id = machines.index(min(machines))
        machines[machine_id] += job

    return machines

# Test Job Scheduling
jobs = [10, 15, 20, 25, 30]
num_machines = 3
machines = schedule_jobs(jobs, num_machines)
print("Job Distribution across Machines:", machines)




# Problem Statement:
# Place `N` queens on an `N x N` chessboard such that no two queens threaten each other (i.e., no two queens
# are in the same row, column, or diagonal).

def is_safe(board, row, col):
    for i in range(row):
        if board[i] == col or board[i] - i == col - row or board[i] + i == col + row:
            return False
    return True

def solve_n_queens(board, row, n):
    if row == n:
        return [board[:]]

    solutions = []
    for col in range(n):
        if is_safe(board, row, col):
            board[row] = col
            solutions += solve_n_queens(board, row + 1, n)
            board[row] = -1  # Backtrack
    return solutions

# Test N-Queens
n = 4
board = [-1] * n  # -1 means no queen placed
solutions = solve_n_queens(board, 0, n)
print("Solutions:", solutions)




# Problem Statement:
# You are given an amount and a set of coin denominations. Find the fewest number of coins that make up that amount.

def coin_change(coins, amount):
    coins.sort(reverse=True)
    result = []

    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)

    return result if amount == 0 else "Not possible"

# Test Coin Change
coins = [1, 5, 10, 25, 50]
amount = 63
coins_used = coin_change(coins, amount)
print("Coins Used:", coins_used)



# Problem Statement:
# Given a set of integers, find a subset whose sum is equal to a target value.

def subset_sum(nums, target):
    nums.sort(reverse=True)
    current_sum = 0
    subset = []

    for num in nums:
        if current_sum + num <= target:
            subset.append(num)
            current_sum += num

    return subset if current_sum == target else "No solution"

# Test Subset Sum
nums = [1, 2, 3, 4, 5, 6]
target = 10
subset = subset_sum(nums, target)
print("Subset:", subset)





# Problem Statement:
# You are given an optimization problem where the search space is too large to check all possible solutions.
# How can you find a good solution in a reasonable amount of time?

import random
import math

def simulated_annealing(initial_state, evaluate, neighbor, temperature=1000, cooling_rate=0.995, min_temp=0.1):
    current_state = initial_state
    current_value = evaluate(current_state)

    while temperature > min_temp:
        next_state = neighbor(current_state)
        next_value = evaluate(next_state)

        if next_value < current_value or random.random() < math.exp((current_value - next_value) / temperature):
            current_state = next_state
            current_value = next_value

        temperature *= cooling_rate

    return current_state, current_value

# Example Test Problem
def evaluate(state):
    return sum(state)  # Just a simple example, can be replaced

def neighbor(state):
    next_state = state[:]
    next_state[random.randint(0, len(state)-1)] = random.randint(1, 10)  # Modify randomly
    return next_state

# Test Simulated Annealing
initial_state = [random.randint(1, 10) for _ in range(5)]
best_state, best_value = simulated_annealing(initial_state, evaluate, neighbor)
print("Best State:", best_state)
print("Best Value:", best_value)

# Problem Statement:
# Given a graph with vertices and edges, assign colors to each vertex such that no two adjacent vertices have
# the same color, using the smallest number of colors possible.

def is_valid_coloring(graph, coloring):
    for node in graph:
        for neighbor in graph[node]:
            if coloring[node] == coloring[neighbor]:
                return False
    return True

def graph_coloring(graph, num_colors):
    coloring = {node: -1 for node in graph}  # -1 means no color assigned
    nodes = list(graph.keys())

    def assign_colors(node_idx):
        if node_idx == len(nodes):
            return True

        node = nodes[node_idx]
        for color in range(num_colors):
            coloring[node] = color
            if is_valid_coloring(graph, coloring) and assign_colors(node_idx + 1):
                return True
            coloring[node] = -1  # Backtrack

        return False

    assign_colors(0)
    return coloring

# Test Graph Coloring
graph = {0: [1, 2], 1: [0, 2], 2: [0, 1]}
colors = graph_coloring(graph, 2)
print("Graph Coloring:", colors)





# Problem Statement:
# Given a graph and a subset of vertices, find the minimum weight tree that connects the subset of vertices.

# A simple greedy solution to Steiner Tree isn't feasible.
# A complex algorithm is needed like Minimum Spanning Tree with Steiner points.
# But for the sake of simplicity, here's a sample greedy approach:

def steiner_tree(graph, terminals):
    # Simple greedy approach (not optimal)
    # Start with a terminal node and greedily add the nearest neighbors
    tree = set(terminals)
    while len(tree) < len(graph):
        best_edge = None
        best_distance = float('inf')
        for node in tree:
            for neighbor in graph[node]:
                if neighbor not in tree and graph[node][neighbor] < best_distance:
                    best_edge = (node, neighbor)
                    best_distance = graph[node][neighbor]
        tree.add(best_edge[1])
    return tree

# Test Steiner Tree
graph = {0: {1: 1, 2: 2}, 1: {0: 1, 2: 1}, 2: {0: 2, 1: 1}}
terminals = [0, 2]
tree = steiner_tree(graph, terminals)
print("Steiner Tree:", tree)

# Problem Statement:
# Given a graph, partition the vertices into two sets such that the number of edges between the sets is maximized.

import random

def max_cut(graph):
    cut = random.choice([0, 1])
    partitions = {node: cut for node in graph}

    # Simple greedy approach (not optimal)
    for node in graph:
        if any(partitions[neighbor] != partitions[node] for neighbor in graph[node]):
            partitions[node] = 1 - partitions[node]  # Flip to opposite partition

    cut_value = sum(1 for node in graph for neighbor in graph[node] if partitions[node] != partitions[neighbor])
    return cut_value, partitions

# Test Max Cut
graph = {0: [1, 2], 1: [0, 2], 2: [0, 1]}
cut_value, partitions = max_cut(graph)
print("Max Cut Value:", cut_value)
print("Partitions:", partitions)





# Problem Statement:
# Given a partially filled Sudoku grid, fill in the missing numbers such that each row, column, and 3x3 subgrid 
# contains every number from 1 to 9.

def is_safe(board, row, col, num):
    for i in range(9):
        if board[row][i] == num or board[i][col] == num:
            return False
    start_row, start_col = row - row % 3, col - col % 3
    for i in range(3):
        for j in range(3):
            if board[i + start_row][j + start_col] == num:
                return False
    return True

def solve_sudoku(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                for num in range(1, 10):
                    if is_safe(board, row, col, num):
                        board[row][col] = num
                        if solve_sudoku(board):
                            return True
                        board[row][col] = 0
                return False
    return True

# Test Sudoku Solver
board = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]
solve_sudoku(board)
print("Solved Sudoku:")
for row in board:
    print(row)


# Problem Statement:
# Given an array of integers, find the contiguous subarray with the maximum sum.

def max_subarray(nums):
    max_sum = current_sum = nums[0]
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

# Test Maximum Subarray
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum = max_subarray(nums)
print("Maximum Subarray Sum:", max_sum)

#Code starts here
def tsp_greedy_rec(city, visited, dist, route):
    visited[city] = True
    route.append(city)

    # Find the nearest unvisited city
    next_city = None
    shortest = float('inf')
    for i in range(len(dist)):
        if not visited[i] and dist[city][i] < shortest:
            shortest = dist[city][i]
            next_city = i

    # If all cities are visited, return to starting city
    if next_city is None:
        route.append(route[0])  # Complete the loop
        return route

    # Recurse with the next closest city
    return tsp_greedy_rec(next_city, visited, dist, route)

#How to use the code below:
# Sample distance matrix (symmetric)
distances = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

n = len(distances)
visited = [False] * n
path = []

# Start from city 0
result = tsp_greedy_rec(0, visited, distances, path)
print("Greedy TSP path:", result)

counter

johnsone emett — Thu, 27 Mar 2025 02:10:43 +0000



from collections import Counter

# Example 1: Basic usage of Counter
# A Counter is a dictionary subclass that counts the occurrences of elements.
sample_list = ['apple', 'banana', 'apple', 'orange', 'banana', 'banana']
counter = Counter(sample_list)

print("Counter object:", counter)
# Output: Counter({'banana': 3, 'apple': 2, 'orange': 1})

# Example 2: Accessing individual counts
print("Count of 'apple':", counter['apple'])  # Output: 2
print("Count of 'grape':", counter['grape'])  # Output: 0 (default for non-existing keys)

# Example 3: Most common elements (returns a list of (element, count) tuples)
print("Most common elements:", counter.most_common(2))
# Output: [('banana', 3), ('apple', 2)]

# Example 4: Update the counter with additional data
additional_data = ['apple', 'grape', 'orange']
counter.update(additional_data)

print("Updated Counter:", counter)
# Output: Counter({'banana': 3, 'apple': 3, 'orange': 2, 'grape': 1})

# Example 5: Subtract elements from another counter or iterable
counter.subtract(['banana', 'apple'])

print("Counter after subtraction:", counter)
# Output: Counter({'banana': 2, 'apple': 2, 'orange': 2, 'grape': 1})

# Example 6: Elements method (returns an iterator of repeated elements)
elements = list(counter.elements())
print("Elements (expanded):", elements)
# Output: ['apple', 'apple', 'banana', 'banana', 'banana', 'orange', 'orange', 'grape']

# Example 7: Clearing the counter (removes all items)
counter.clear()
print("Counter after clear:", counter)
# Output: Counter()

# Example 8: Using Counter with a string
string = "hello world"
counter = Counter(string)

print("Counter for the string:", counter)
# Output: Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, ' ': 1, 'w': 1, 'r': 1, 'd': 1})

# Example 9: Arithmetic operations (add, subtract, etc.)
counter1 = Counter(a=3, b=2, c=1)
counter2 = Counter(a=1, b=1, c=1, d=4)

# Addition of counters
counter3 = counter1 + counter2
print("Counter after addition:", counter3)
# Output: Counter({'a': 4, 'b': 3, 'c': 2, 'd': 4})

# Subtraction of counters
counter4 = counter1 - counter2
print("Counter after subtraction:", counter4)
# Output: Counter({'a': 2, 'b': 1})

# Intersection of counters (minimum counts)
counter5 = counter1 & counter2
print("Intersection of counters:", counter5)
# Output: Counter({'a': 1, 'b': 1, 'c': 1})

# Union of counters (maximum counts)
counter6 = counter1 | counter2
print("Union of counters:", counter6)
# Output: Counter({'a': 3, 'b': 2, 'c': 1, 'd': 4})

# Example 10: Using Counter with a defaultdict (helpful in some cases)
from collections import defaultdict
counter = defaultdict(int)

# Increment the count of elements
counter['apple'] += 1
counter['banana'] += 2
counter['apple'] += 3

print("Counter using defaultdict:", counter)
# Output: defaultdict(<class 'int'>, {'apple': 4, 'banana': 2})

# Example 11: Converting Counter back to a regular dictionary
normal_dict = dict(counter)
print("Converted to regular dictionary:", normal_dict)
# Output: {'apple': 4, 'banana': 2}

regex

johnsone emett — Wed, 26 Mar 2025 10:49:24 +0000


import re

# 1. Match Lowercase Letters
# This will match any string containing only lowercase letters
def match_lowercase(text):
    pattern = r'^[a-z]+$'  # ^ indicates start of string, $ indicates end, [a-z]+ matches one or more lowercase letters
    if re.match(pattern, text):
        print(f"'{text}' contains only lowercase letters.")
    else:
        print(f"'{text}' does not contain only lowercase letters.")

# 2. Match Uppercase Letters
# This will match any string containing only uppercase letters
def match_uppercase(text):
    pattern = r'^[A-Z]+$'  # [A-Z]+ matches one or more uppercase letters
    if re.match(pattern, text):
        print(f"'{text}' contains only uppercase letters.")
    else:
        print(f"'{text}' does not contain only uppercase letters.")

# 3. Match Numbers (Integers)
# This will match a string consisting only of digits
def match_numbers(text):
    pattern = r'^\d+$'  # ^\d+$ matches one or more digits (0-9)
    if re.match(pattern, text):
        print(f"'{text}' is a number.")
    else:
        print(f"'{text}' is not a number.")

# 4. Match Odd Numbers (Example: 1, 3, 5, 7, 9, etc.)
# This will check if the number is odd by matching digits ending with 1, 3, 5, 7, or 9
def match_odd_number(text):
    pattern = r'^[13579]$'  # ^[13579]$ matches a single odd digit
    if re.match(pattern, text):
        print(f"'{text}' is an odd number.")
    else:
        print(f"'{text}' is not an odd number.")

# 5. Match Even Numbers (Example: 0, 2, 4, 6, 8, etc.)
# This checks if the number is even by matching digits ending with 0, 2, 4, 6, or 8
def match_even_number(text):
    pattern = r'^[02468]$'  # ^[02468]$ matches a single even digit
    if re.match(pattern, text):
        print(f"'{text}' is an even number.")
    else:
        print(f"'{text}' is not an even number.")

# 6. Validate Email Address
# This will validate a basic email address using a regex pattern
def validate_email(text):
    pattern = r'^[a-zA-Z0-9_.+-]+@[a-zA-Z0-9-]+\.[a-zA-Z0-9-.]+$'  # Basic email format pattern
    if re.match(pattern, text):
        print(f"'{text}' is a valid email.")
    else:
        print(f"'{text}' is not a valid email.")

# 7. Validate Phone Number (US Format: (XXX) XXX-XXXX)
# This checks if the phone number is in the format (123) 456-7890
def validate_phone_number(text):
    pattern = r'^\(\d{3}\) \d{3}-\d{4}$'  # (\d{3}) matches 3 digits in parentheses, followed by space, 3 digits, hyphen, and 4 digits
    if re.match(pattern, text):
        print(f"'{text}' is a valid phone number.")
    else:
        print(f"'{text}' is not a valid phone number.")

# 8. Find All Occurrences of a Word in a Text
# This will find all occurrences of the word 'Python' (case-insensitive)
def find_word_occurrences(text):
    pattern = r'python'  # Matching the word 'python'
    results = re.findall(pattern, text, re.IGNORECASE)  # re.IGNORECASE allows case-insensitive matching
    print(f"Found {len(results)} occurrences of 'python'.")

# 9. Extract Dates from Text (Format: DD-MM-YYYY)
# This will match and extract all dates in the form of dd-mm-yyyy
def extract_dates(text):
    pattern = r'\b\d{2}-\d{2}-\d{4}\b'  # \b ensures we match a complete date (not part of a longer number)
    dates = re.findall(pattern, text)
    print("Extracted dates:", dates)

# 10. Replace All Spaces with Hyphens
# This will replace all spaces in the input text with hyphens
def replace_spaces_with_hyphens(text):
    pattern = r'\s+'  # \s+ matches one or more whitespace characters
    modified_text = re.sub(pattern, '-', text)  # re.sub replaces the matched pattern with '-'
    print(f"Modified text: {modified_text}")

# 11. Check for a Hexadecimal Color Code
# This will match a hexadecimal color code like #FF5733
def validate_hex_color(text):
    pattern = r'^#[0-9A-Fa-f]{6}$'  # # followed by exactly 6 hexadecimal characters
    if re.match(pattern, text):
        print(f"'{text}' is a valid hex color code.")
    else:
        print(f"'{text}' is not a valid hex color code.")

# Example Usage
if __name__ == "__main__":
    match_lowercase("hello")  # Expected: contains only lowercase
    match_uppercase("HELLO")  # Expected: contains only uppercase
    match_numbers("123456")  # Expected: is a number
    match_odd_number("3")     # Expected: is an odd number
    match_even_number("4")    # Expected: is an even number
    validate_email("example@gmail.com")  # Expected: valid email
    validate_phone_number("(123) 456-7890")  # Expected: valid phone number
    find_word_occurrences("Python is great. I love python.")  # Expected: 2 occurrences
    extract_dates("The event is on 25-12-2023, and the next is on 01-01-2024.")  # Expected: 2 dates
    replace_spaces_with_hyphens("This is a test.")  # Expected: This-is-a-test.
    validate_hex_color("#FF5733")  # Expected: valid hex color code

sort

johnsone emett — Wed, 26 Mar 2025 10:11:24 +0000



# 1. Sorting by Length of Strings
words = ["apple", "banana", "kiwi", "grape"]
sorted_words = sorted(words, key=lambda x: len(x))  # Sort by length of strings
print("Sorted by length:", sorted_words)

# 2. Sorting Strings Alphabetically (Default)
sorted_words = sorted(words, key=lambda x: x)  # Default alphabetical sorting
print("Alphabetically sorted:", sorted_words)

# 3. Sorting by Last Character of Strings
sorted_words = sorted(words, key=lambda x: x[-1])  # Sort by last character of each word
print("Sorted by last character:", sorted_words)

# 4. Sorting Tuples by Second Element
tuples = [(1, 2), (3, 1), (5, 4), (2, 3)]
sorted_tuples = sorted(tuples, key=lambda x: x[1])  # Sort by second element of each tuple
print("Sorted by second element of tuple:", sorted_tuples)

# 5. Sorting by Sum of Elements in Tuples
sorted_tuples = sorted(tuples, key=lambda x: sum(x))  # Sort by sum of elements in each tuple
print("Sorted by sum of elements:", sorted_tuples)

# 6. Sorting a List of Dictionaries by a Specific Key (Age)
students = [{"name": "Alice", "age": 25}, {"name": "Bob", "age": 22}, {"name": "Charlie", "age": 23}]
sorted_students = sorted(students, key=lambda x: x["age"])  # Sort by age
print("Sorted by age:", sorted_students)

# 7. Sorting by Multiple Criteria (Age then Name)
sorted_students = sorted(students, key=lambda x: (x["age"], x["name"]))  # Sort by age, then name
print("Sorted by age and name:", sorted_students)

# 8. Sorting by Absolute Value of Numbers
numbers = [-5, 3, -2, 8, -1]
sorted_numbers = sorted(numbers, key=lambda x: abs(x))  # Sort by absolute value
print("Sorted by absolute value:", sorted_numbers)

# 9. Sorting by Custom Object Attribute (Age)
class Athlete:
    def __init__(self, name, age):
        self.name = name
        self.age = age

athletes = [Athlete("Alice", 25), Athlete("Bob", 22), Athlete("Charlie", 23)]
sorted_athletes = sorted(athletes, key=lambda x: x.age)  # Sort by age of Athlete object
print("Sorted by athlete age:")
for athlete in sorted_athletes:
    print(athlete.name, athlete.age)

# 10. Sorting in Reverse Order
sorted_numbers = sorted(numbers, key=lambda x: x, reverse=True)  # Sort in reverse order
print("Sorted in reverse order:", sorted_numbers)

# 11. Sorting by Length of Words in Sentences
sentence = "The quick brown fox jumps over the lazy dog"
words = sentence.split()
sorted_words = sorted(words, key=lambda x: len(x))  # Sort words by their length
print("Sorted by length of words in sentence:", sorted_words)

# 12. Sorting by First Character of Each Word
sorted_words = sorted(words, key=lambda x: x[0])  # Sort words by their first character
print("Sorted by first character:", sorted_words)

# 13. Sorting by Decimal Value (Floats)
numbers = [3.14, 1.59, 2.65, 7.29]
sorted_numbers = sorted(numbers, key=lambda x: x - int(x))  # Sort by decimal part of floats
print("Sorted by decimal value:", sorted_numbers)

# 14. Sorting by Date (using datetime objects)
from datetime import datetime

dates = [
    datetime(2021, 5, 10),
    datetime(2020, 6, 15),
    datetime(2022, 3, 5),
]

sorted_dates = sorted(dates, key=lambda x: x)  # Sort dates in ascending order
print("Sorted by date:")
for date in sorted_dates:
    print(date.strftime("%Y-%m-%d"))

# 15. Sorting by Multiple Columns for Complex Objects (Age, then Name)
students = [{"name": "Alice", "age": 25}, {"name": "Bob", "age": 22}, {"name": "Alice", "age": 22}]
sorted_students = sorted(students, key=lambda x: (x['age'], x['name']))  # Sort by age, then name
print("Sorted by age and name (complex object):", sorted_students)

# 16. Sorting by Custom Function (Handling Complex Sorting)
students = [{"name": "Alice", "age": 25}, {"name": "Bob", "age": 22}, {"name": "Charlie", "age": 22}]
sorted_students = sorted(students, key=lambda x: (x['age'], len(x['name'])))  # Sort by age, then length of name
print("Sorted by age, then length of name:", sorted_students)

remove duplicates

johnsone emett — Tue, 25 Mar 2025 10:50:32 +0000




# Get the distinct words in the order of their first appearance
    distinct_words = list(dict.fromkeys(words))


def remove_duplicates(data):
    # For list type
    if isinstance(data, list):
        seen = set()
        result = []
        for item in data:
            if item not in seen:
                result.append(item)
                seen.add(item)
        return result  # Return as list

    # For tuple type
    elif isinstance(data, tuple):
        seen = set()
        result = []
        for item in data:
            if item not in seen:
                result.append(item)
                seen.add(item)
        return tuple(result)  # Return as tuple

    # For set type
    elif isinstance(data, set):
        return list(data)  # Return as list (or tuple if needed)

    # For string type
    elif isinstance(data, str):
        seen = set()
        result = []
        for char in data:
            if char not in seen:
                result.append(char)
                seen.add(char)
        return ''.join(result)  # Return as string

    # For unsupported types, return the data as is (like integers)
    return data

# Example usage:
# For a list
input_list = [1, 2, 2, 3, 4, 4, 5]
print(remove_duplicates(input_list))  # Output: [1, 2, 3, 4, 5]

# For a tuple
input_tuple = (1, 2, 2, 3, 4, 4, 5)
print(remove_duplicates(input_tuple))  # Output: (1, 2, 3, 4, 5)

# For a set
input_set = {1, 2, 2, 3, 4, 4, 5}
print(remove_duplicates(input_set))  # Output: [1, 2, 3, 4, 5]

# For a string
input_string = "abcabcdeabc"
print(remove_duplicates(input_string))  # Output: "abcde"

Simulated Annealing TSP

johnsone emett — Sun, 23 Mar 2025 12:26:11 +0000

import math
import random

# Function to calculate Euclidean distance for cities with coordinates
def calculate_distance_between_coordinates(city1, city2):
    return math.sqrt((city2[0] - city1[0])**2 + (city2[1] - city1[1])**2)

# Function to calculate the distance from a distance matrix
def calculate_distance_between_matrix(i, j, dist_matrix):
    return dist_matrix[i][j]

def simulated_annealing_tsp(cities=None, dist_matrix=None, city_names=None, temp=1000, temp_decay=0.995, max_iter=10000, start_city=None, end_city=None, circular=True):
    """
    Solve TSP using Simulated Annealing while including city names in the result.

    Args:
    - cities (list): List of cities (x, y) coordinates (only if using coordinates).
    - dist_matrix (list): Distance matrix (only if distances between cities are provided directly).
    - city_names (list): List of city names corresponding to the cities.
    - temp (float): Initial temperature for simulated annealing.
    - temp_decay (float): Decay factor for temperature after each iteration.
    - max_iter (int): Maximum number of iterations.
    - start_city (int): Optional starting city index. If None, the best start will be chosen.
    - end_city (int): Optional end city index. If None, the best end will be chosen.
    - circular (bool): If True, the route will return to the starting city. If False, it will not.

    Returns:
    - tuple: The best distance and the best path (list of city names).
    """
    # Choose the appropriate distance calculation based on input format
    if cities is not None:
        def calculate_distance(i, j):
            return calculate_distance_between_coordinates(cities[i], cities[j])
    else:
        def calculate_distance(i, j):
            return calculate_distance_between_matrix(i, j, dist_matrix)

    def calculate_total_distance(path):
        total_distance = 0
        for i in range(len(path) - 1):
            total_distance += calculate_distance(path[i], path[i+1])
        if circular:
            total_distance += calculate_distance(path[-1], path[0])  # Return to the starting city
        return total_distance

    def neighbor(path):
        # Create a neighbor by swapping two cities in the path (except the start and end cities)
        new_path = path[:]
        unvisited = path[1:-1]  # Exclude start and end cities
        i, j = random.sample(range(len(unvisited)), 2)
        unvisited[i], unvisited[j] = unvisited[j], unvisited[i]
        # Rebuild the path including start and end cities
        new_path[1:-1] = unvisited
        return new_path

    # If start_city or end_city are not provided, default to the first city
    n = len(cities) if cities is not None else len(dist_matrix)
    if start_city is None:
        start_city = random.randint(0, n - 1)  # Random start city if not specified
    if end_city is None:
        end_city = start_city  # End city is the same as start if not specified

    # Initialize the path (fixed start and end cities)
    current_path = list(range(n))
    current_path = [start_city] + [i for i in range(n) if i != start_city] + [end_city]  # Ensure start and end cities are fixed
    current_distance = calculate_total_distance(current_path)
    best_path = current_path[:]
    best_distance = current_distance

    # Perform simulated annealing
    for _ in range(max_iter):
        temp *= temp_decay
        if temp <= 0:
            break

        new_path = neighbor(current_path)
        new_distance = calculate_total_distance(new_path)

        # Accept the new solution if it's better, or with probability if it's worse
        if new_distance < current_distance or random.random() < math.exp((current_distance - new_distance) / temp):
            current_path = new_path
            current_distance = new_distance

            if current_distance < best_distance:
                best_path = current_path[:]
                best_distance = current_distance

    # Convert the best path from indices to city names
    city_path = [city_names[city] for city in best_path]
    return best_distance, city_path

# Example usage for Simulated Annealing with City Names:

# City names
city_names = ["City A", "City B", "City C", "City D"]

# Example distance matrix (distances between cities)
dist_matrix = [
    [0, 2, 4, 1],
    [2, 0, 3, 5],
    [4, 3, 0, 6],
    [1, 5, 6, 0]
]

# Example: Simulated Annealing TSP with circular route
best_distance, best_path = simulated_annealing_tsp(dist_matrix=dist_matrix, city_names=city_names, temp=1000, temp_decay=0.995, max_iter=10000, circular=True)
print("Simulated Annealing Best Distance:", best_distance)
print("Simulated Annealing Best Path:", " -> ".join(best_path))

# Example: Simulated Annealing TSP with non-circular route
best_distance, best_path = simulated_annealing_tsp(dist_matrix=dist_matrix, city_names=city_names, temp=1000, temp_decay=0.995, max_iter=10000, circular=False)
print("Simulated Annealing Best Distance (Non-Circular):", best_distance)
print("Simulated Annealing Best Path (Non-Circular):", " -> ".join(best_path))

tsp greedy

johnsone emett — Sun, 23 Mar 2025 12:03:57 +0000

#TSP greedy
import math
import random

# Function to calculate Euclidean distance for cities with coordinates
def calculate_distance_between_coordinates(city1, city2):
    return math.sqrt((city2[0] - city1[0])**2 + (city2[1] - city1[1])**2)

# Function to calculate the distance from a distance matrix
def calculate_distance_between_matrix(i, j, dist_matrix):
    return dist_matrix[i][j]

def greedy_tsp(cities=None, dist_matrix=None, city_names=None, start_city=None, end_city=None, circular=True):
    """
    Solve TSP using a greedy approach while including city names in the result.

    Args:
    - cities (list): List of cities (x, y) coordinates (only if using coordinates).
    - dist_matrix (list): Distance matrix (only if distances between cities are provided directly).
    - city_names (list): List of city names corresponding to the cities.
    - start_city (int): Optional starting city index. If None, the best start will be chosen.
    - end_city (int): Optional end city index. If None, the best end will be chosen.
    - circular (bool): If True, the route will return to the starting city. If False, it will not.

    Returns:
    - tuple: The best distance and the best path (list of city names).
    """
    # Choose the appropriate distance calculation based on input format
    if cities is not None:
        def calculate_distance(i, j):
            return calculate_distance_between_coordinates(cities[i], cities[j])
    else:
        def calculate_distance(i, j):
            return calculate_distance_between_matrix(i, j, dist_matrix)

    def calculate_total_distance(path):
        total_distance = 0
        for i in range(len(path) - 1):
            total_distance += calculate_distance(path[i], path[i+1])
        if circular:
            total_distance += calculate_distance(path[-1], path[0])  # Return to the starting city
        return total_distance

    # Initialize start and end cities if not provided
    n = len(cities) if cities is not None else len(dist_matrix)

    if start_city is None:
        start_city = random.randint(0, n - 1)  # Random start city if not specified
    if end_city is None:
        end_city = start_city  # End city is the same as start if not specified

    # Initialize unvisited cities and the tour
    unvisited = list(range(n))
    path = [unvisited.pop(start_city)]  # Start with the start city
    total_distance = 0

    while unvisited:
        last_city = path[-1]
        next_city = min(unvisited, key=lambda city: calculate_distance(last_city, city))
        unvisited.remove(next_city)
        path.append(next_city)
        total_distance += calculate_distance(last_city, next_city)

    # Close the tour if circular is True
    if circular:
        total_distance += calculate_distance(path[-1], path[0])  # Return to the starting city
        path.append(path[0])

    # Convert path from indices to city names
    city_path = [city_names[city] for city in path]
    return total_distance, city_path

# Example usage for Greedy TSP with City Names:
city_names = ["City A", "City B", "City C", "City D"]
dist_matrix = [
    [0, 2, 4, 1],
    [2, 0, 3, 5],
    [4, 3, 0, 6],
    [1, 5, 6, 0]
]

# Example: Greedy TSP with circular route
best_distance, best_path = greedy_tsp(dist_matrix=dist_matrix, city_names=city_names, circular=True)
print("Greedy Best Distance:", best_distance)
print("Greedy Best Path:", " -> ".join(best_path))

# Example: Greedy TSP with non-circular route
best_distance, best_path = greedy_tsp(dist_matrix=dist_matrix, city_names=city_names, start_city=2, circular=False)
print("Greedy Best Distance (Non-Circular):", best_distance)
print("Greedy Best Path (Non-Circular):", " -> ".join(best_path))

heuristics

johnsone emett — Sun, 23 Mar 2025 11:48:45 +0000



def greedy_coin_change(coins, target):
    """
    Greedy algorithm to find the minimum number of coins for a given target.

    Args:
    - coins (list): List of available coin denominations.
    - target (int): The target value to reach using the coins.

    Returns:
    - list: A list of coins that sum up to the target, or a message if it's impossible.

    Example:
    >>> coins = [1, 5, 10, 25]
    >>> target = 63
    >>> greedy_coin_change(coins, target)
    [25, 25, 10, 1, 1, 1]
    """
    coins.sort(reverse=True)  # Sort coins in descending order for greedy choice
    result = []

    for coin in coins:
        while target >= coin:
            target -= coin
            result.append(coin)

    return result if target == 0 else "Not possible"

# Example usage:
coins = [1, 5, 10, 25]
target = 63
print(greedy_coin_change(coins, target))  # Output: [25, 25, 10, 1, 1, 1]





import random

def fitness_function(solution):
    """
    Simple fitness function for a binary solution.

    Args:
    - solution (list): A list of binary values representing a solution.

    Returns:
    - int: The fitness value, calculated as the sum of the elements (e.g., how many 1's are in the solution).

    Example:
    >>> fitness_function([1, 1, 0, 1])
    3
    """
    return sum(solution)  # Count how many 1's in the solution

def mutate(solution):
    """
    Randomly mutate a solution by flipping one bit (0 to 1 or 1 to 0).

    Args:
    - solution (list): The solution to mutate.

    Returns:
    - list: The mutated solution.

    Example:
    >>> mutate([1, 0, 1])
    [1, 1, 1]
    """
    idx = random.randint(0, len(solution) - 1)
    solution[idx] = random.randint(0, 1)  # Flip a random bit
    return solution

def crossover(parent1, parent2):
    """
    Perform crossover between two parents to generate two children.

    Args:
    - parent1 (list): The first parent solution.
    - parent2 (list): The second parent solution.

    Returns:
    - tuple: Two children produced by crossover.

    Example:
    >>> crossover([1, 0, 1], [0, 1, 0])
    ([1, 0, 0], [0, 1, 1])
    """
    point = random.randint(1, len(parent1) - 1)
    child1 = parent1[:point] + parent2[point:]
    child2 = parent2[:point] + parent1[point:]
    return child1, child2

def genetic_algorithm(pop_size, num_gen, mutation_rate):
    """
    Basic Genetic Algorithm for optimization problems.

    Args:
    - pop_size (int): Population size.
    - num_gen (int): Number of generations to run the algorithm.
    - mutation_rate (float): Probability of mutation for each generation.

    Returns:
    - list: The best solution found by the algorithm.

    Example:
    >>> genetic_algorithm(50, 100, 0.1)
    [1, 1, 1, 0, 1, 1, 0, 1, 1]
    """
    population = [[random.randint(0, 1) for _ in range(10)] for _ in range(pop_size)]  # Initialize random population
    for gen in range(num_gen):
        population.sort(key=lambda x: fitness_function(x), reverse=True)  # Sort by fitness (descending)
        next_generation = population[:2]  # Keep the top 2 best solutions
        while len(next_generation) < pop_size:
            parent1, parent2 = random.sample(population[:10], 2)  # Select parents from top 10
            child1, child2 = crossover(parent1, parent2)
            next_generation.append(child1)
            next_generation.append(child2)
        population = next_generation

        # Mutate with a certain probability
        if random.random() < mutation_rate:
            population[random.randint(0, pop_size - 1)] = mutate(population[random.randint(0, pop_size - 1)])

    return max(population, key=lambda x: fitness_function(x))

# Example usage:
best_solution = genetic_algorithm(pop_size=50, num_gen=100, mutation_rate=0.1)
print("Best solution:", best_solution, "Fitness:", fitness_function(best_solution))












import heapq

def a_star(start, goal, grid):
    """
    A* algorithm to find the shortest path in a 2D grid.

    Args:
    - start (tuple): Starting position (row, col).
    - goal (tuple): Goal position (row, col).
    - grid (list of list): A 2D grid with 0 as open cells and 1 as obstacles.

    Returns:
    - list: The path from start to goal, or "No path found" if no path exists.

    Example:
    >>> grid = [
    >>>     [0, 0, 0, 0],
    >>>     [0, 1, 1, 0],
    >>>     [0, 0, 0, 0],
    >>>     [0, 1, 0, 0]
    >>> ]
    >>> start = (0, 0)
    >>> goal = (3, 3)
    >>> a_star(start, goal, grid)
    [(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (3, 3)]
    """
    def heuristic(a, b):
        return abs(a[0] - b[0]) + abs(a[1] - b[1])  # Manhattan distance

    open_set = []
    heapq.heappush(open_set, (0 + heuristic(start, goal), 0, start))
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}

    while open_set:
        _, current_cost, current = heapq.heappop(open_set)

        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]  # Return reversed path

        for neighbor in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            neighbor_cell = (current[0] + neighbor[0], current[1] + neighbor[1])
            if 0 <= neighbor_cell[0] < len(grid) and 0 <= neighbor_cell[1] < len(grid[0]) and grid[neighbor_cell[0]][neighbor_cell[1]] != 1:
                tentative_g_score = current_cost + 1  # Assume cost to neighbor is 1
                if neighbor_cell not in g_score or tentative_g_score < g_score[neighbor_cell]:
                    came_from[neighbor_cell] = current
                    g_score[neighbor_cell] = tentative_g_score
                    f_score[neighbor_cell] = tentative_g_score + heuristic(neighbor_cell, goal)
                    heapq.heappush(open_set, (f_score[neighbor_cell], tentative_g_score, neighbor_cell))

    return "No path found"

# Example usage:
grid = [
    [0, 0, 0, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0],
    [0, 1, 0, 0]
]
start = (0, 0)
goal = (3, 3)
print(a_star(start, goal, grid))  # Output: [(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (3, 3)]

itertools

johnsone emett — Sun, 23 Mar 2025 06:01:04 +0000

import itertools

# 1. count() - Infinite iterator that counts from a given number
def test_count():
    count_iter = itertools.count(5, 2)  # Start at 5, increment by 2
    count_list = [next(count_iter) for _ in range(5)]  # Get the first 5 numbers
    print("count:", count_list)

# 2. cycle() - Infinite iterator that repeats the input iterable
def test_cycle():
    cycle_iter = itertools.cycle([1, 2, 3])  # Repeats the list [1, 2, 3]
    cycle_list = [next(cycle_iter) for _ in range(7)]  # Get 7 elements
    print("cycle:", cycle_list)

# 3. repeat() - Repeats an element a fixed number of times
def test_repeat():
    repeat_iter = itertools.repeat("hello", 3)  # Repeat "hello" 3 times
    repeat_list = list(repeat_iter)
    print("repeat:", repeat_list)

# 4. permutations() - Generates all permutations of an iterable
def test_permutations():
    perm_iter = itertools.permutations([1, 2, 3])  # Generate permutations of [1, 2, 3]
    perm_list = list(perm_iter)
    print("permutations:", perm_list)

# 5. combinations() - Generates all combinations of an iterable of a given length
def test_combinations():
    comb_iter = itertools.combinations([1, 2, 3], 2)  # 2-combinations of [1, 2, 3]
    comb_list = list(comb_iter)
    print("combinations:", comb_list)

# 6. product() - Computes the cartesian product of input iterables
def test_product():
    prod_iter = itertools.product([1, 2], ['a', 'b'])  # Cartesian product of [1, 2] and ['a', 'b']
    prod_list = list(prod_iter)
    print("product:", prod_list)

# 7. combinations_with_replacement() - Generates combinations with replacement
def test_combinations_with_replacement():
    comb_with_replacement_iter = itertools.combinations_with_replacement([1, 2, 3], 2)  # 2-combinations with replacement
    comb_with_replacement_list = list(comb_with_replacement_iter)
    print("combinations_with_replacement:", comb_with_replacement_list)

# 8. chain() - Combines multiple iterables into a single iterable
def test_chain():
    chain_iter = itertools.chain([1, 2], ['a', 'b'])  # Chain [1, 2] and ['a', 'b']
    chain_list = list(chain_iter)
    print("chain:", chain_list)

# 9. islice() - Iterates over a range of elements (like slicing)
def test_islice():
    islice_iter = itertools.islice([1, 2, 3, 4, 5], 1, 4)  # Slice from index 1 to 3
    islice_list = list(islice_iter)
    print("islice:", islice_list)

# 10. starmap() - Applies a function to items in iterables
def test_starmap():
    starmap_iter = itertools.starmap(lambda x, y: x + y, [(1, 2), (3, 4), (5, 6)])  # Add pairs of numbers
    starmap_list = list(starmap_iter)
    print("starmap:", starmap_list)

# 11. groupby() - Groups consecutive elements in an iterable by a key
def test_groupby():
    group_iter = itertools.groupby([1, 1, 2, 3, 3, 3, 4])  # Group consecutive elements
    group_list = [(key, list(group)) for key, group in group_iter]
    print("groupby:", group_list)

# 12. tee() - Returns multiple iterators from a single iterable
def test_tee():
    tee_iter1, tee_iter2 = itertools.tee([1, 2, 3], 2)  # Create two iterators
    tee_list1 = list(tee_iter1)
    tee_list2 = list(tee_iter2)
    print("tee:", tee_list1, tee_list2)

# 13. filterfalse() - Returns elements from the iterable for which the predicate is False
def test_filterfalse():
    filterfalse_iter = itertools.filterfalse(lambda x: x % 2 == 0, [1, 2, 3, 4, 5])  # Filter out even numbers
    filterfalse_list = list(filterfalse_iter)
    print("filterfalse:", filterfalse_list)

# 14. compress() - Filters elements from an iterable based on a selector
def test_compress():
    compress_iter = itertools.compress([1, 2, 3, 4, 5], [1, 0, 1, 0, 1])  # Keep elements where selector is 1
    compress_list = list(compress_iter)
    print("compress:", compress_list)

# 15. dropwhile() - Drops elements from the iterable until the predicate is False
def test_dropwhile():
    dropwhile_iter = itertools.dropwhile(lambda x: x < 3, [1, 2, 3, 4, 5])  # Drop elements until 3 is reached
    dropwhile_list = list(dropwhile_iter)
    print("dropwhile:", dropwhile_list)

# 16. takewhile() - Takes elements from the iterable while the predicate is True
def test_takewhile():
    takewhile_iter = itertools.takewhile(lambda x: x < 3, [1, 2, 3, 4, 5])  # Take elements while less than 3
    takewhile_list = list(takewhile_iter)
    print("takewhile:", takewhile_list)

# Test all the functions
def run_tests():
    test_count()
    test_cycle()
    test_repeat()
    test_permutations()
    test_combinations()
    test_product()
    test_combinations_with_replacement()
    test_chain()
    test_islice()
    test_starmap()
    test_groupby()
    test_tee()
    test_filterfalse()
    test_compress()
    test_dropwhile()
    test_takewhile()

# Run the tests
run_tests()

graph

johnsone emett — Sat, 22 Mar 2025 04:52:13 +0000

from collections import deque

class Graph:
    def __init__(self, directed=False, weighted=False):
        self.graph = {}  # Adjacency list
        self.directed = directed  # Whether the graph is directed or undirected
        self.weighted = weighted  # Whether the graph is weighted or not

    def add_vertex(self, vertex):
        """Add a vertex to the graph."""
        if vertex not in self.graph:
            self.graph[vertex] = []

    def remove_vertex(self, vertex):
        """Remove a vertex from the graph and its associated edges."""
        if vertex in self.graph:
            del self.graph[vertex]
            for v in self.graph:
                # Remove the vertex from other vertex's adjacency list
                self.graph[v] = [neighbor for neighbor in self.graph[v] if neighbor[0] != vertex]

    def add_edge(self, vertex1, vertex2, weight=None):
        """Add an edge between vertex1 and vertex2 (directional or not, weighted or not)."""
        if vertex1 not in self.graph:
            self.add_vertex(vertex1)
        if vertex2 not in self.graph:
            self.add_vertex(vertex2)

        if self.weighted:
            # If the graph is weighted, store (neighbor, weight)
            self.graph[vertex1].append((vertex2, weight))
            if not self.directed:
                self.graph[vertex2].append((vertex1, weight))
        else:
            # If the graph is unweighted, just store the neighbor
            self.graph[vertex1].append(vertex2)
            if not self.directed:
                self.graph[vertex2].append(vertex1)

    def remove_edge(self, vertex1, vertex2):
        """Remove the edge between vertex1 and vertex2."""
        if vertex1 in self.graph:
            self.graph[vertex1] = [neighbor for neighbor in self.graph[vertex1] if neighbor[0] != vertex2]
        if vertex2 in self.graph:
            self.graph[vertex2] = [neighbor for neighbor in self.graph[vertex2] if neighbor[0] != vertex1]

    def display(self):
        """Display the graph as an adjacency list."""
        for vertex, edges in self.graph.items():
            if self.weighted:
                # For weighted graphs, print edges with their weights
                edge_list = [(neighbor, weight) for neighbor, weight in edges]
                print(f"{vertex}: {edge_list}")
            else:
                # For unweighted graphs, print only the neighbors
                print(f"{vertex}: {edges}")


    def dfs(self, start):
        """Depth-First Search (DFS) traversal from start vertex."""
        visited = set()
        self._dfs_recursive(start, visited)
        print()

    def _dfs_recursive(self, vertex, visited):
        """Recursive DFS helper."""
        visited.add(vertex)
        print(vertex, end=" ")
        for neighbor in self.graph[vertex]:
            if self.weighted:
                neighbor = neighbor[0]  # Get the vertex from (neighbor, weight) tuple
            if neighbor not in visited:
                self._dfs_recursive(neighbor, visited)

    def bfs(self, start):
        """Breadth-First Search (BFS) traversal from start vertex."""
        visited = set()
        queue = deque([start])
        visited.add(start)

        while queue:
            vertex = queue.popleft()
            print(vertex, end=" ")

            for neighbor in self.graph[vertex]:
                if self.weighted:
                    neighbor = neighbor[0]  # Get the vertex from (neighbor, weight) tuple
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        print()

    def has_cycle(self):
        """Check if the graph contains a cycle."""
        visited = set()
        recursion_stack = set()

        for vertex in self.graph:
            if vertex not in visited:
                if self._has_cycle_recursive(vertex, visited, recursion_stack):
                    return True
        return False

    def _has_cycle_recursive(self, vertex, visited, recursion_stack):
        """Helper for cycle detection."""
        visited.add(vertex)
        recursion_stack.add(vertex)

        for neighbor in self.graph[vertex]:
            if self.weighted:
                neighbor = neighbor[0]  # Get the vertex from (neighbor, weight) tuple
            if neighbor not in visited:
                if self._has_cycle_recursive(neighbor, visited, recursion_stack):
                    return True
            elif neighbor in recursion_stack:
                return True

        recursion_stack.remove(vertex)
        return False
 # 3. Dijkstra's Algorithm (Shortest Path for Weighted Graphs)
    def dijkstra(self, start):
        """Dijkstra’s Algorithm to find the shortest path in a weighted graph."""
        # Distance from start node to all other nodes
        distances = {vertex: float('inf') for vertex in self.graph}
        distances[start] = 0

        # Priority queue to store vertices to be processed, ordered by distance
        pq = [(0, start)]  # (distance, vertex)

        while pq:
            current_distance, current_vertex = heapq.heappop(pq)

            # Skip processing if we already found a shorter path
            if current_distance > distances[current_vertex]:
                continue

            for neighbor in self.graph[current_vertex]:
                if self.weighted:
                    neighbor_vertex, weight = neighbor
                else:
                    neighbor_vertex, weight = neighbor, 1

                distance = current_distance + weight
                # If a shorter path is found
                if distance < distances[neighbor_vertex]:
                    distances[neighbor_vertex] = distance
                    heapq.heappush(pq, (distance, neighbor_vertex))

        return distances

    # 4. A* Algorithm (Shortest Path with Heuristic)
    def a_star(self, start, goal, heuristic):
        """A* Algorithm to find the shortest path using heuristic for weighted graphs."""
        # Distance from start node
        g_costs = {vertex: float('inf') for vertex in self.graph}
        g_costs[start] = 0

        # Estimated total cost from start to goal through each vertex
        f_costs = {vertex: float('inf') for vertex in self.graph}
        f_costs[start] = heuristic[start]

        # Priority queue to store vertices to be processed, ordered by f_cost (g_cost + heuristic)
        pq = [(f_costs[start], start)]  # (f_cost, vertex)

        came_from = {}  # To track the best path

        while pq:
            _, current_vertex = heapq.heappop(pq)

            if current_vertex == goal:
                # Reconstruct the path from start to goal
                path = []
                while current_vertex in came_from:
                    path.append(current_vertex)
                    current_vertex = came_from[current_vertex]
                path.append(start)
                path.reverse()
                return path

            for neighbor in self.graph[current_vertex]:
                if self.weighted:
                    neighbor_vertex, weight = neighbor
                else:
                    neighbor_vertex, weight = neighbor, 1

                tentative_g_cost = g_costs[current_vertex] + weight
                if tentative_g_cost < g_costs[neighbor_vertex]:
                    came_from[neighbor_vertex] = current_vertex
                    g_costs[neighbor_vertex] = tentative_g_cost
                    f_costs[neighbor_vertex] = g_costs[neighbor_vertex] + heuristic[neighbor_vertex]
                    heapq.heappush(pq, (f_costs[neighbor_vertex], neighbor_vertex))

        return None  # No path found
        # 4. Topological Sort (Using DFS)
    def topological_sort(self):
        """Perform a topological sort using DFS."""
        visited = set()
        stack = []

        # Helper function for DFS-based topological sort
        def dfs(vertex):
            visited.add(vertex)
            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    dfs(neighbor)
            stack.append(vertex)

        # Perform DFS for all vertices to make sure we get all components
        for vertex in self.graph:
            if vertex not in visited:
                dfs(vertex)

        # The stack will contain the topological order in reverse
        stack.reverse()  # Reverse to get the correct topological order
        return stack
# Example usage:

# Test 1: Undirected, Unweighted Graph
print("Test 1: Undirected Unweighted Graph")
graph_undirected_unweighted = Graph(directed=False, weighted=False)

# Add vertices and edges (undirected and unweighted)
graph_undirected_unweighted.add_edge("A", "B")
graph_undirected_unweighted.add_edge("A", "C")
graph_undirected_unweighted.add_edge("B", "D")
graph_undirected_unweighted.add_edge("C", "D")

# Display the graph
print("Graph adjacency list:")
graph_undirected_unweighted.display()

# Perform DFS and BFS
print("\nDFS on undirected unweighted graph starting from A:")
graph_undirected_unweighted.dfs("A")

print("\nBFS on undirected unweighted graph starting from A:")
graph_undirected_unweighted.bfs("A")

# Check for cycles
print("\nDoes the undirected unweighted graph have a cycle?")
print(graph_undirected_unweighted.has_cycle())  # Expected output: True (A-B-D-C-A)

# Test 2: Directed, Unweighted Graph
print("\nTest 2: Directed Unweighted Graph")
graph_directed_unweighted = Graph(directed=True, weighted=False)

# Add directed edges (unweighted)
graph_directed_unweighted.add_edge("A", "B")
graph_directed_unweighted.add_edge("A", "C")
graph_directed_unweighted.add_edge("B", "D")
graph_directed_unweighted.add_edge("C", "D")

# Display the graph
print("Graph adjacency list:")
graph_directed_unweighted.display()

# Perform DFS and BFS
print("\nDFS on directed unweighted graph starting from A:")
graph_directed_unweighted.dfs("A")

print("\nBFS on directed unweighted graph starting from A:")
graph_directed_unweighted.bfs("A")

# Check for cycles
print("\nDoes the directed unweighted graph have a cycle?")
print(graph_directed_unweighted.has_cycle())  # Expected output: False (no cycle)

# Test 3: Undirected, Weighted Graph
print("\nTest 3: Undirected Weighted Graph")
graph_undirected_weighted = Graph(directed=False, weighted=True)

# Add weighted, undirected edges
graph_undirected_weighted.add_edge("A", "B", 5)
graph_undirected_weighted.add_edge("A", "C", 10)
graph_undirected_weighted.add_edge("B", "D", 3)
graph_undirected_weighted.add_edge("C", "D", 7)

# Display the graph
print("Graph adjacency list with weights:")
graph_undirected_weighted.display()

# Perform DFS and BFS
print("\nDFS on undirected weighted graph starting from A:")
graph_undirected_weighted.dfs("A")

print("\nBFS on undirected weighted graph starting from A:")
graph_undirected_weighted.bfs("A")

# Check for cycles
print("\nDoes the undirected weighted graph have a cycle?")
print(graph_undirected_weighted.has_cycle())  # Expected output: True (A-B-D-C-A)

# Test 4: Directed, Weighted Graph
print("\nTest 4: Directed Weighted Graph")
graph_directed_weighted = Graph(directed=True, weighted=True)

# Add weighted, directed edges
graph_directed_weighted.add_edge("A", "B", 5)
graph_directed_weighted.add_edge("A", "C", 10)
graph_directed_weighted.add_edge("B", "D", 3)
graph_directed_weighted.add_edge("C", "D", 7)

# Display the graph
print("Graph adjacency list with weights:")
graph_directed_weighted.display()

# Perform DFS and BFS
print("\nDFS on directed weighted graph starting from A:")
graph_directed_weighted.dfs("A")

print("\nBFS on directed weighted graph starting from A:")
graph_directed_weighted.bfs("A")

# Check for cycles
print("\nDoes the directed weighted graph have a cycle?")
print(graph_directed_weighted.has_cycle())  # Expected output: False (no cycle)

# Test Dijkstra and A* algorithm
print("\nDijkstra's shortest path from A:")
print(graph_directed_weighted.dijkstra("A"))

# Heuristic for A* algorithm (simple example: goal is to get to D)
heuristic = {"A": 10, "B": 8, "C": 5, "D": 0}  # Just an example of heuristic values
print("\nA* algorithm path from A to D:")
print(graph_directed_weighted.a_star("A", "D", heuristic))

queue

johnsone emett — Sat, 22 Mar 2025 04:51:14 +0000

from collections import deque
import heapq

# Basic Queue Implementation using deque
class Queue:
    def __init__(self):
        self.queue = deque()

    def enqueue(self, item):
        """Enqueue an item to the queue."""
        self.queue.append(item)

    def dequeue(self):
        """Dequeue an item from the queue. Returns None if the queue is empty."""
        if not self.is_empty():
            return self.queue.popleft()
        return None

    def front(self):
        """Return the front item of the queue."""
        if not self.is_empty():
            return self.queue[0]
        return None

    def is_empty(self):
        """Check if the queue is empty."""
        return len(self.queue) == 0

    def size(self):
        """Return the size of the queue."""
        return len(self.queue)

    def clear(self):
        """Clear all items in the queue."""
        self.queue.clear()

    def print_queue(self):
        """Print all elements in the queue."""
        print(list(self.queue))


# Queue Implementation using Two Stacks
class QueueWithTwoStacks:
    def __init__(self):
        self.stack1 = Stack()
        self.stack2 = Stack()

    def enqueue(self, item):
        """Enqueue an item to the queue."""
        self.stack1.push(item)

    def dequeue(self):
        """Dequeue an item from the queue."""
        if self.stack2.is_empty():
            while not self.stack1.is_empty():
                self.stack2.push(self.stack1.pop())
        return self.stack2.pop() if not self.stack2.is_empty() else None


# Circular Queue Implementation (Fixed-size Queue)
class CircularQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = self.rear = -1

    def enqueue(self, item):
        if (self.rear + 1) % self.capacity == self.front:
            print("Queue is full")
            return
        if self.front == -1:  # First element
            self.front = 0
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = item

    def dequeue(self):
        if self.front == -1:
            print("Queue is empty")
            return None
        item = self.queue[self.front]
        if self.front == self.rear:  # Single element
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % self.capacity
        return item

    def peek(self):
        if self.front == -1:
            print("Queue is empty")
            return None
        return self.queue[self.front]

    def is_empty(self):
        return self.front == -1

    def size(self):
        if self.front == -1:
            return 0
        return (self.rear - self.front + 1) % self.capacity


# Priority Queue Implementation using a heap
class PriorityQueue:
    def __init__(self):
        self.queue = []
        self.counter = 0  # To maintain order for equal priorities

    def enqueue(self, item, priority):
        heapq.heappush(self.queue, (priority, self.counter, item))
        self.counter += 1

    def dequeue(self):
        if self.is_empty():
            return None
        return heapq.heappop(self.queue)[-1]

    def peek(self):
        if self.is_empty():
            return None
        return self.queue[0][-1]

    def is_empty(self):
        return len(self.queue) == 0

    def size(self):
        return len(self.queue)


# Helper Function: Reverse a Queue using a stack
def reverse_queue(queue):
    """
    Reverse the elements of a queue using a stack.
    :param queue: The queue (using deque).
    :return: The reversed queue.
    """
    stack = []
    # Dequeue all elements and push them onto a stack
    while queue:
        stack.append(queue.popleft())

    # Push all elements back into the queue
    while stack:
        queue.append(stack.pop())

    return queue


# Example Use Cases

# 1. Basic Queue operations
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print("Queue operations:")
print(queue.front())  # Output: 10
print(queue.dequeue()) # Output: 10
print(queue.size())    # Output: 2
queue.print_queue()    # Output: [20, 30]

# 2. Queue with Two Stacks
queue2 = QueueWithTwoStacks()
queue2.enqueue(10)
queue2.enqueue(20)
queue2.enqueue(30)
print("\nQueueWithTwoStacks operations:")
print(queue2.dequeue())  # Output: 10
print(queue2.dequeue())  # Output: 20

# 3. Circular Queue operations
circular_queue = CircularQueue(3)
circular_queue.enqueue(10)
circular_queue.enqueue(20)
circular_queue.enqueue(30)
print("\nCircularQueue operations:")
print(circular_queue.dequeue())  # Output: 10
circular_queue.enqueue(40)
print(circular_queue.peek())    # Output: 20
print(circular_queue.size())    # Output: 3

# 4. Priority Queue operations
priority_queue = PriorityQueue()
priority_queue.enqueue("task1", 2)
priority_queue.enqueue("task2", 1)
priority_queue.enqueue("task3", 3)
print("\nPriorityQueue operations:")
print(priority_queue.dequeue())  # Output: task2
print(priority_queue.peek())     # Output: task1

# 5. Reverse a Queue
queue = deque([1, 2, 3, 4, 5])
print("\nReversing the queue:")
reversed_queue = reverse_queue(queue)
print(reversed_queue)  # Output: deque([5, 4, 3, 2, 1])

stacks

johnsone emett — Sat, 22 Mar 2025 03:30:55 +0000

from collections import deque

class Stack:
    def __init__(self, data=None):
        """Initialize the stack, optionally converting a data type into a stack."""
        self.stack = []
        if data is not None:
            self.convert_to_stack(data)
    def convert_to_stack(self, data):
        """Convert a data type (string, list, tuple, etc.) into a stack."""
        if isinstance(data, str):
            # If it's a string, treat it as a sequence of characters
            self.stack = list(data)
        elif isinstance(data, (list, tuple)):
            # If it's a list or tuple, directly convert it to a stack
            self.stack = list(data)
        elif isinstance(data, dict):
            # If it's a dictionary, treat it as key-value pairs
            self.stack = list(data.items())
        elif isinstance(data, set):
            # If it's a set, convert it to a list
            self.stack = list(data)
        else:
            # Handle other types of data by converting them into a list
            self.stack = [data]  # Wrap the data into a list if it's not iterable
        print(f"Stack initialized with: {self.stack}")

    def push(self, item):
        """Push an item onto the stack."""
        self.stack.append(item)

    def pop(self):
        """Pop an item from the stack. Returns None if the stack is empty."""
        if not self.is_empty():
            return self.stack.pop()
        return None

    def peek(self):
        """Peek at the top item of the stack without removing it."""
        if not self.is_empty():
            return self.stack[-1]
        return None

    def is_empty(self):
        """Check if the stack is empty."""
        return len(self.stack) == 0

    def size(self):
        """Return the size of the stack."""
        return len(self.stack)

    def clear(self):
        """Clear all items in the stack."""
        self.stack.clear()

    def print_stack(self):
        """Print all elements in the stack."""
        print(self.stack)


def reverse_stack(stack):
    """Reverse a stack using recursion."""
    if stack.is_empty():
        return
    top = stack.pop()
    reverse_stack(stack)
    insert_at_bottom(stack, top)

def insert_at_bottom(stack, item):
    """Helper function to insert an item at the bottom of the stack."""
    if stack.is_empty():
        stack.push(item)
    else:
        top = stack.pop()
        insert_at_bottom(stack, item)
        stack.push(top)


def is_balanced(expression):
    """Check if the parentheses in the expression are balanced."""
    stack = Stack()
    for char in expression:
        if char in '([{':
            stack.push(char)
        elif char == ')' and (stack.is_empty() or stack.pop() != '('):
            return False
        elif char == ']' and (stack.is_empty() or stack.pop() != '['):
            return False
        elif char == '}' and (stack.is_empty() or stack.pop() != '{'):
            return False
    return stack.is_empty()


def dfs_stack(graph, start):
    """
    Perform DFS traversal of a graph using a stack.
    :param graph: A dictionary representing the graph (adjacency list).
    :param start: The starting node for DFS traversal.
    :return: A list of nodes in the order they were visited.
    """
    visited = set()
    stack = [start]
    traversal_order = []

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            traversal_order.append(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

    return traversal_order


def bfs_queue(graph, start):
    """
    Perform BFS traversal of a graph using a queue.
    :param graph: A dictionary representing the graph (adjacency list).
    :param start: The starting node for BFS traversal.
    :return: A list of nodes in the order they were visited.
    """
    visited = set()
    queue = deque([start])
    traversal_order = []

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            traversal_order.append(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

    return traversal_order


def is_palindrome(s):
    """
    Check if a string is a palindrome using a stack.
    :param s: The string to check.
    :return: True if the string is a palindrome, False otherwise.
    """
    stack = []
    # Push each character onto the stack
    for char in s:
        stack.append(char)

    # Check if the string is a palindrome by comparing characters
    for char in s:
        if char != stack.pop():
            return False
    return True


def sort_stack(stack):
    """
    Sort a stack using only another stack for auxiliary storage.
    :param stack: The stack to be sorted.
    :return: The sorted stack.
    """
    auxiliary_stack = []

    while stack:
        current = stack.pop()

        # Move elements from auxiliary stack back to stack if they are greater than current
        while auxiliary_stack and auxiliary_stack[-1] > current:
            stack.append(auxiliary_stack.pop())

        # Push the current element to the auxiliary stack
        auxiliary_stack.append(current)

    # Move all elements back to the original stack
    while auxiliary_stack:
        stack.append(auxiliary_stack.pop())

    return stack


class MinStack:
    def __init__(self):
        """
        Initialize the stack and the auxiliary stack to keep track of minimum elements.
        """
        self.stack = []
        self.min_stack = []

    def push(self, x):
        """
        Push an element onto the stack.
        :param x: The element to be pushed onto the stack.
        """
        self.stack.append(x)
        # Push the minimum element onto the min_stack
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self):
        """
        Pop the top element from the stack.
        :return: The popped element.
        """
        if self.stack:
            popped_value = self.stack.pop()
            if popped_value == self.min_stack[-1]:
                self.min_stack.pop()
            return popped_value
        return None

    def top(self):
        """
        Get the top element of the stack.
        :return: The top element of the stack.
        """
        return self.stack[-1] if self.stack else None

    def get_min(self):
        """
        Retrieve the minimum element in constant time.
        :return: The minimum element in the stack.
        """
        return self.min_stack[-1] if self.min_stack else None


# Example Use Cases

# 1. Test the Stack class
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print("Stack operations:")
print(stack.peek())  # Output: 30
print(stack.pop())   # Output: 30
print(stack.size())  # Output: 2
stack.print_stack()  # Output: [10, 20]

# 2. Test DFS
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
print("\nDFS traversal:", dfs_stack(graph, 'A'))  # Output: ['A', 'C', 'F', 'E', 'B', 'D']

# 3. Test BFS
print("\nBFS traversal:", bfs_queue(graph, 'A'))  # Output: ['A', 'B', 'C', 'D', 'E', 'F']

# 4. Test Palindrome Check
print("\nIs 'racecar' a palindrome?", is_palindrome('racecar'))  # Output: True
print("Is 'hello' a palindrome?", is_palindrome('hello'))  # Output: False

# 5. Test Reversing a Stack
print("\nReversing stack:")
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
reverse_stack(stack)
stack.print_stack()  # Output: [3, 2, 1]

# 6. Test Balanced Parentheses
expression = "{[()()]}"
print("\nIs the expression balanced?", is_balanced(expression))  # Output: True
expression = "{[(])}"
print("Is the expression balanced?", is_balanced(expression))  # Output: False

# 7. Test Sorting a Stack
stack = [5, 2, 9, 1, 5, 6]
print("\nSorted stack:", sort_stack(stack))  # Output: [1, 2, 5, 5, 6, 9]

# 8. Test MinStack
min_stack = MinStack()
min_stack.push(3)
min_stack.push(4)
min_stack.push(2)
min_stack.push(5)
print("\nMinStack get_min:", min_stack.get_min())  # Output: 2
min_stack.pop()
print("MinStack get_min after pop:", min_stack.get_min())  # Output: 2
min_stack.pop()


# 1. Test the Stack class with different data types using convert_to_stack

# Test with a string
stack1 = Stack("abcd")
print("\nStack with string 'abcd':")
stack1.print_stack()  # Output: ['a', 'b', 'c', 'd']

# Test with a list
stack2 = Stack([1, 2, 3, 4])
print("\nStack with list [1, 2, 3, 4]:")
stack2.print_stack()  # Output: [1, 2, 3, 4]

# Test with a tuple
stack3 = Stack((5, 6, 7, 8))
print("\nStack with tuple (5, 6, 7, 8):")
stack3.print_stack()  # Output: [5, 6, 7, 8]

# Test with a dictionary (key-value pairs)
stack4 = Stack({'a': 1, 'b': 2, 'c': 3})
print("\nStack with dictionary {'a': 1, 'b': 2, 'c': 3}:")
stack4.print_stack()  # Output: [('a', 1), ('b', 2), ('c', 3)]

# Test with a set
stack5 = Stack({9, 10, 11, 12})
print("\nStack with set {9, 10, 11, 12}:")
stack5.print_stack()  # Output: [9, 10, 11, 12] (order may vary due to set properties)

# Test with an integer (wrapped in a list for other non-iterable types)
stack6 = Stack(42)
print("\nStack with integer 42 (wrapped as a list):")
stack6.print_stack()  # Output: [42]