Dungeon Game: Data Structures and Algorithms for Beginners 🎯

Welcome to the exciting world of Dungeon Game! In this lesson, we'll learn about essential Data Structures and Algorithms using a fun and practical approach. Let's dive right in! 🤓

What is a Dungeon Game? 📝

A Dungeon Game is a fictional game that we'll use to understand and practice various Data Structures and Algorithms. The game will be built upon simple concepts, making it an engaging and practical way to learn these important programming tools.

Basic Data Structures 💡

Arrays

An array is a collection of elements, each identified by an index. Arrays are useful for storing and manipulating a fixed number of items of the same type.

python

# Example of an array in Python
items = ["sword", "shield", "potion"]
print(items[0])  # Output: sword

Linked Lists

A linked list is a sequence of nodes where each node contains data and a reference to the next node. Linked lists are useful when the number of items is not fixed.

python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Example of a linked list in Python
head = Node("sword")
head.next = Node("shield")
head.next.next = Node("potion")

Algorithms 💡

Linear Search

Linear Search is an algorithm used to find an element in an array by repeatedly comparing the target element with each element in the array.

python

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# Example of linear search in Python
items = [1, 2, 3, 4, 5]
print(linear_search(items, 3))  # Output: 1

Binary Search

Binary Search is an efficient search algorithm that works on sorted arrays by repeatedly dividing the search interval in half.

python

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# Example of binary search in Python
items = [1, 2, 3, 4, 5]
print(binary_search(items, 3))  # Output: 1

Putting It All Together: The Dungeon Game 💡

Now that we have a basic understanding of Data Structures and Algorithms, let's build a simple Dungeon Game to practice our new skills. The game will involve searching for items, adding new items to a linked list, and sorting items for easier management.

python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Dungeon:
    def __init__(self):
        self.head = None

    def add_item(self, item):
        if not self.head:
            self.head = Node(item)
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = Node(item)

    def linear_search(self, target):
        current = self.head
        index = 0
        while current:
            if current.data == target:
                return index
            current = current.next
            index += 1
        return -1

    def binary_search(self, target):
        if not self.head:
            return -1

        current = self.head
        low = 0
        high = len(self) - 1

        while low <= high:
            mid = (low + high) // 2
            current = self.head
            for i in range(mid):
                current = current.next

            if current.data == target:
                return mid
            elif current.data < target:
                low = mid + 1
            else:
                high = mid - 1

        return -1

    def __len__(self):
        current = self.head
        count = 0
        while current:
            current = current.next
            count += 1
        return count

# Example usage of the Dungeon Game
dungeon = Dungeon()
dungeon.add_item("sword")
dungeon.add_item("shield")
dungeon.add_item("potion")

print(dungeon.linear_search("potion"))  # Output: 2
print(dungeon.binary_search("potion"))  # Output: 2

Quiz 📝

Congratulations! You've successfully learned about Data Structures and Algorithms using the Dungeon Game. Keep practicing and exploring to improve your programming skills! 🚀