This repository contains my solutions to the Week-2 coding challenge, which includes two challenges: the Fourier Transform challenge and the Word Ladder challenge.
The Fourier Transform challenge involves implementing a function to perform a Fourier transform on a sequence of complex numbers using the Fast Fourier Transform (FFT) algorithm.
I implemented the FFT algorithm in Python using a recursive approach. The function takes a sequence of complex numbers as input and returns the Fourier transform of the input sequence. The main steps of the FFT algorithm are:
- Divide the sequence into even and odd indices.
- Recursively compute the FFT of the even and odd subsequences.
- Combine the results using twiddle factors to compute the final Fourier transform.
The solution is implemented in the fft() function in the app.py file.
The Word Ladder challenge involves finding the length of the shortest sequence of transformations from a start word to an end word, where only one letter can be changed at a time and each transformed word must exist in a given list of words.
I implemented a breadth-first search (BFS) algorithm to solve the Word Ladder problem. The function takes the start word, end word, and a list of words as input and returns the length of the shortest sequence of transformations. The algorithm explores all possible transformations using one-letter changes until it reaches the end word.
The solution is implemented in the word_ladder_length() function in the app.py file.
To use the solutions:
- Clone this repository to your local machine.
- Navigate to the repository directory.
- Run the
app.pyfile. - Choose between the Fourier Transform and Word Ladder challenges from the menu.
- Follow the prompts to input the required information.
- View the output.
The solutions do not require any external dependencies and should work with a standard Python installation.