Using Binary Search Tree and Trie data structures to store and retrieve a Movie Catalogue

guachilimbo — Thu, 27 Jan 2022 19:25:17 +0000

I created this code to have a go at data structure and algorithms on Python after taking the data structure & algorithms module in Codecademy.

GitHub link to code: https://github.com/guachilimbo/movie_recommendation

Data Structures Used

The program uses a database of the top 250 movies on IMDb which I found in Kaggle (https://www.kaggle.com/ramjasmaurya/top-250s-in-imdb)

It stores this information in two different data structures: A Binary Search Tree, and a Trie.

Binary Search Tree

When the data base is read, each movie entry is stored as a Binary Search Tree (BST). The tree is sorted alphabetically depending on the title of each movie. This allows for quick storage and retrieval with a running time performance of O(logN), where N is the number of levels in the tree.

However, in order to implement an autocomplete functionality, I thought this was not a good data structure, since for a given prefix (str) of length M, the runtime to find all the movies that match the string will be O(MlogN).

This is why as the data was read from the database, a Trie() structure containing the titles of each movie is created.

Trie

There are M + 1 Trie() classes created in this program, where M is the number of unique genres detected in the database. This allows to apply the autocomplete function to all the catalogue, or just the movies within an user chosen genre.

The nice thing about applying the autocomplete function, which searches all movies that start with a prefix input by the user, to a Trie is that search complexities are brought to optimal limit, this is, the prefix length.

Program Execution:

Download folder and run python main.py on the command line.
The program will ask for choice between two running modes:

a) Genre search: The program will display the genres found in the data base. The user will then choose one of the genres. The films that belong to this category will be displayed. The user will then be asked to enter part of the title of one of those films and a autocomplete method will be invoked on that string.

b) General search: The user will be asked to input the beginning of a movie title and the autocomplete method will be called on that string.
If a match is found, the movie's Title, Year, Genre and Duration will be displayed alongside the option to display a description of the movie.
Perform another search or exit the program.

Please any suggestions or improvements are greatly appreciated since this is my first time dealing with data structures and algorithms!

Battleship!... On Command Line

guachilimbo — Sat, 30 Oct 2021 17:11:35 +0000

As part of the course I am taking to improve my programming skills, I have decided to code a Battleship game to be played using the command line.

Github link to code: https://github.com/guachilimbo/battleship

What is Battleship?

Battleship is a two player board game where the objective is to sink all of your opponent's ships. Each turn, the players will "bomb" a grid cell (e.g. "C7"). If a boat is occupying the cell, the boat will be "hit". Otherwise it will be a "miss".

Game set up

For my game, I have decided to create a 10x10 alphanumerical grid. Each player will have 5 different boats with different lengths:

Carrier - 5 cells
Battleship - 4 cells
Cruiser - 3 cells
Submarine - 3 cells
Destroyer - 2 cells

The game is played against the CPU. Upon inisialisation, the user will be given a prompt to choose the initial cell the boat will occupy, and whether you want to position the boat vertically or horizontally. This process is repeated for each boat:

The CPU board is set up using Python's random library:

columns = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J"]
rows = list(range(10))
def random_cell(self):
  return "".join([random.choice(Play.columns),str(random.choice(Play.rows))])

Playing the game
Using a similar logic as the set up, the CPU will randomly choose a cell to bomb. If there is a boat on that cell of the player's grid, the cell will be updated with an "x" to show that the boat has been hit. Otherwise, the cell will be updated with a "~" to show the bomb missed.

The player logic is the same but the user has to input the desired cell. The code will warn the user if an already bombed cell has been chosen.

A list keeps track of the number of hits a boat has received. When the number of hits equals the length of the boat (i.e. number of lives), the number of boats left displayed under the grids, changes. Allowing the user to know how many (and which) boats are left.

End game

The game end when one side has lost all of the boats. The code terminates and outputs a message to restart if the user wishes to.

Future improvements