is-even.cc

bool isEven(int n) {
    return (n & 1) == 0;
}

sieveOfEratosthenes.cc

/*
 * Sieve of Eratosthenes: An efficient algorithm to find all prime numbers up to a given limit.
 * Time complexity: O(n log(log n))
 * Space complexity: O(n)
 */
#include <iostream>
#include <vector>
#include <cstdlib>

std::vector<bool> sieveOfEratosthenes(int n) {
  std::vector<bool> primes(n + 1, true);
  primes[0] = primes[1] = false;

  for (int i = 2; i * i <= n; i++) {
    if (primes[i]) {
      for (int j = i * i; j <= n; j += i) {
        primes[j] = false;
      }
    }
  }

  return primes;
}

bool isPrime(int number) {
  if (number <= 1) return false;
  for (int i = 2; i * i <= number; i++) {
    if (number % i == 0) return false;
  }
  return true;
}

int main() {
  {
    int n = 100, i = 1, count = 0;

    std::vector<bool> primes = sieveOfEratosthenes(n);

    for (int i = 2; i <= primes.size(); i++) {
      if (primes[i]) {
        std::cout << i << ' ';
      }
    }
  }

  std::cout << std::endl;

  {
    int n = 100, count = 0, number = 2;

    while (count < n) {
      if (isPrime(number)) {
        std::cout << number << " ";
        count++;
      }
      number++;
    }
  }

  std::cout << std::endl;

  return EXIT_SUCCESS;
}

swap.cc

void swap(int &a, int &b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

Sure! I'd be happy to provide detailed information on both the Blockchain Prototype and the Maze Solver Visualization projects. Below, I'll break down each project, explain how the data structures are utilized, and provide implementation details to help you get started.

---

1. Blockchain Prototype

Project Overview

• Objective: Build a simplified blockchain model where each block is a node in a linked list.
• Key Data Structures:
  • Linked List: To chain the blocks together, forming the blockchain.
  • Stack: To manage a pool of pending transactions.
  • Merkle Tree: To efficiently store and verify transactions within a block.

Understanding the Components

a. Blockchain as a Linked List

• Blocks: Each block contains data, a timestamp, a nonce (for mining), a hash of its contents, and the hash of the previous block.
• Chaining Blocks: The blockchain is essentially a linked list where each block points to the previous block via the previous hash.
• Genesis Block: The first block in the chain, which has no previous hash.

b. Transaction Pool as a Stack

• Transaction Pool: A stack where new transactions are added (pushed) to the top.
• Mining Process: Transactions are popped from the stack when creating a new block.
• LIFO Behavior: Ensures that the most recent transactions are prioritized.

c. Merkle Trees for Transaction Verification

• Merkle Tree Structure: A binary tree where each leaf node is a hash of a transaction, and non-leaf nodes are hashes of their child nodes.
• Root Hash: The topmost hash that represents all transactions in the block.
• Verification: Efficiently verify the presence of a transaction without storing all transaction data.

Implementation Details

1. Define the Block Structure

class Block:
    def __init__(self, index, timestamp, transactions_root, previous_hash, nonce=0):
        self.index = index
        self.timestamp = timestamp
        self.transactions_root = transactions_root
        self.previous_hash = previous_hash
        self.nonce = nonce
        self.hash = self.compute_hash()

    def compute_hash(self):
        # Combine the block's contents and hash them
        block_string = f"{self.index}{self.timestamp}{self.transactions_root}{self.previous_hash}{self.nonce}"
        return hashlib.sha256(block_string.encode()).hexdigest()

2. Implement the Linked List (Blockchain)

class Blockchain:
    def __init__(self):
        self.chain = []
        self.create_genesis_block()

    def create_genesis_block(self):
        genesis_block = Block(0, datetime.now(), "0", "0")
        self.chain.append(genesis_block)

    def add_block(self, new_block):
        new_block.previous_hash = self.chain[-1].hash
        new_block.hash = new_block.compute_hash()
        self.chain.append(new_block)

3. Transaction Pool Using Stack

class TransactionPool:
    def __init__(self):
        self.stack = []

    def add_transaction(self, transaction):
        self.stack.append(transaction)

    def get_transactions(self, num_transactions):
        transactions = []
        for _ in range(num_transactions):
            if self.stack:
                transactions.append(self.stack.pop())
            else:
                break
        return transactions

4. Implement the Merkle Tree

class MerkleTree:
    def __init__(self, transactions):
        self.transactions = transactions
        self.root = self.build_merkle_tree(transactions)

    def build_merkle_tree(self, transactions):
        # Base case
        if len(transactions) == 1:
            return hashlib.sha256(transactions[0].encode()).hexdigest()

        # Recursive case
        new_level = []
        for i in range(0, len(transactions), 2):
            left = transactions[i]
            right = transactions[i + 1] if i + 1 < len(transactions) else transactions[i]
            combined_hash = hashlib.sha256((left + right).encode()).hexdigest()
            new_level.append(combined_hash)
        return self.build_merkle_tree(new_level)

5. Block Creation and Mining

def mine_block(blockchain, transaction_pool):
    index = len(blockchain.chain)
    timestamp = datetime.now()
    transactions = transaction_pool.get_transactions(5)  # Get 5 transactions
    merkle_tree = MerkleTree(transactions)
    transactions_root = merkle_tree.root
    previous_hash = blockchain.chain[-1].hash

    new_block = Block(index, timestamp, transactions_root, previous_hash)
    blockchain.add_block(new_block)

Additional Considerations

• Hashing and Security: Use cryptographic hashing functions like SHA-256.
• Proof-of-Work: Implement a simple PoW algorithm by finding a nonce that results in a hash with a certain number of leading zeros.
• Validation: Ensure that each block's previous_hash matches the hash of the previous block.

Extensions

• User Interface: Create a simple CLI or GUI to interact with the blockchain.
• Network Simulation: Simulate multiple nodes adding blocks to the blockchain.
• Consensus Mechanism: Implement basic consensus algorithms to handle forks.

---

2. Maze Solver Visualization

Project Overview

• Objective: Implement a maze-solving algorithm (DFS or BFS) and visualize the pathfinding process.
• Key Data Structures:
  • 2D Array or Linked List: To represent the maze grid.
  • Stack (for DFS) or Queue (for BFS): To keep track of the nodes to visit.

Understanding the Components

a. Maze Representation

• Grid-Based Maze: Represent the maze as a 2D grid where cells can be walls or paths.
• Cells:
  • 0: Open path.
  • 1: Wall or obstacle.

b. Pathfinding Algorithms

• Depth-First Search (DFS):
  • Explores as far as possible along each branch before backtracking.
  • Uses a stack to keep track of the path.
• Breadth-First Search (BFS):
  • Explores all neighbors at the current depth before moving to the next level.
  • Uses a queue and is guaranteed to find the shortest path in an unweighted maze.

c. Visualization

• Real-Time Updates: Show the algorithm's progress as it explores the maze.
• Color Coding:
  • Unvisited Cells: Default color (e.g., white).
  • Visited Cells: Marked with a different color (e.g., blue).
  • Current Path: Highlighted (e.g., green).
  • Solution Path: Final path from start to finish (e.g., red).

Implementation Details

1. Maze Grid Creation

• Static Maze: Use a predefined maze for simplicity.
• Random Maze Generation (Optional): Implement algorithms like Recursive Division or Prim's Algorithm.

maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [1, 1, 0, 0, 0],
]

2. Implement DFS Algorithm Using a Stack

def dfs(maze, start, end):
    stack = [start]
    visited = set()
    parent = {}

    while stack:
        current = stack.pop()
        if current == end:
            break
        visited.add(current)
        neighbors = get_neighbors(maze, current)
        for neighbor in neighbors:
            if neighbor not in visited and neighbor not in stack:
                stack.append(neighbor)
                parent[neighbor] = current
                visualize_step(maze, current, neighbor)  # Visualization function

    return reconstruct_path(parent, start, end)

3. Implement BFS Algorithm Using a Queue

def bfs(maze, start, end):
    queue = deque([start])
    visited = set()
    parent = {}

    while queue:
        current = queue.popleft()
        if current == end:
            break
        visited.add(current)
        neighbors = get_neighbors(maze, current)
        for neighbor in neighbors:
            if neighbor not in visited and neighbor not in queue:
                queue.append(neighbor)
                parent[neighbor] = current
                visualize_step(maze, current, neighbor)  # Visualization function

    return reconstruct_path(parent, start, end)

4. Neighbor Retrieval Function

def get_neighbors(maze, position):
    rows, cols = len(maze), len(maze[0])
    row, col = position
    neighbors = []
    for delta_row, delta_col in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        new_row, new_col = row + delta_row, col + delta_col
        if 0 <= new_row < rows and 0 <= new_col < cols:
            if maze[new_row][new_col] == 0:
                neighbors.append((new_row, new_col))
    return neighbors

5. Path Reconstruction

def reconstruct_path(parent, start, end):
    path = [end]
    while path[-1] != start:
        path.append(parent[path[-1]])
    path.reverse()
    return path

6. Visualization

• Using Libraries: Libraries like matplotlib, pygame, or tkinter can be used for visualization.
• Visualization Function:

def visualize_step(maze, current, neighbor):
    # Update the display to show the current cell and neighbor
    # Implement a short delay to visualize the process
    time.sleep(0.1)
    draw_maze(maze, current, neighbor)

• Drawing the Maze:

def draw_maze(maze, current=None, neighbor=None, path=None):
    for row in range(len(maze)):
        for col in range(len(maze[0])):
            cell = maze[row][col]
            # Determine the color based on the cell state
            # Draw the cell using the chosen library

Additional Considerations

• Handling Large Mazes: Optimize visualization updates to handle larger mazes without significant lag.
• User Interaction:
  • Start/Stop/Pause: Allow users to control the simulation.
  • Maze Editing: Enable users to design their own mazes.
• Algorithm Selection: Provide options to switch between DFS and BFS.

Extensions

• Heuristic Search (A* Algorithm):
  • Implement A* for faster pathfinding using heuristics.
• 3D Mazes:
  • Extend the project to handle three-dimensional mazes.
• Mobile App:
  • Develop the project as a mobile application for interactive learning.

---

Next Steps

1. Choose a Programming Language:

   • Python: Excellent for rapid development and has rich libraries for GUI (tkinter, pygame) and cryptography (hashlib).
   • Java: Offers strong object-oriented features and GUI capabilities with Swing or JavaFX.
   • C++: Provides fine-grained control over memory and performance.

2. Set Up the Development Environment:

   • Install necessary tools and libraries.
   • Set up version control with Git.

3. Plan the Project Structure:

   • Break down the project into modules (e.g., data structures, algorithms, visualization).
   • Define classes and interfaces.

4. Implement Incrementally:

   • Start with core functionalities.
   • Test each component thoroughly before moving on.

5. Documentation and Testing:

   • Write clear documentation for your code.
   • Implement unit tests to ensure reliability.

6. Seek Feedback:

   • Share your progress with peers or mentors.
   • Participate in forums or communities related to your project.

---

Additional Resources

• Blockchain Resources:

  • Mastering Bitcoin: A free book on Bitcoin and blockchain technology.
  • Blockchain Demo: Visual demos explaining blockchain concepts.

• Maze Solver Resources:

  • Red Blob Games: In-depth guides on pathfinding algorithms.
  • Mazegen: A maze generator and solver in Python.

---

Feel free to ask if you need more specific code examples, explanations on certain parts, or guidance on how to proceed with any aspect of these projects. Good luck with your implementation!

function findMatchingWords(words, pattern) {
    // Convert the pattern to a regular expression
    // Replace '?' with '.' (matches any single character)
    // Replace '_' with '.' (matches any single character)
    const regexPattern = pattern.replace(/\?/g, '.').replace(/_/g, '.');
    const regex = new RegExp(`^${regexPattern}$`); // Anchors the regex to match the whole word

    // Filter the words that match the regex
    return words.filter(word => regex.test(word));
}

// Example usage
const wordsList = ['cat', 'bat', 'hat', 'heat', 'helt', 'help', 'hell', 'he'll', 'heatwave'];
const pattern1 = '?at'; // Matches 'cat', 'bat', 'hat'
const pattern2 = 'he_l'; // Matches 'help', 'hell'

const matches1 = findMatchingWords(wordsList, pattern1);
const matches2 = findMatchingWords(wordsList, pattern2);

console.log(`Matches for '${pattern1}':`, matches1);
console.log(`Matches for '${pattern2}':`, matches2);