Here is a representation of a graph:
edges = {
1: [2,3,4],
2: [5,6],
4: [7,8],
5: [9,10],
7: [11,12],
}
Draw this graph on paper.
Implement BFS and DFS on this graph and output the order of traversal of the nodes.
The tower of Hanoi is a puzzle game with three rods and $n$ disks, each a different size. All the disks start of on the first rod in a stack. They are ordered by size, with the largest on the bottom and the smallest one at the top. The goal of this puzzle is to move all the disks from the first rod to the last rod while following these rules:
Write a function that prints out all the steps necessary to complete the Tower of Hanoi. You should assume that the rods are numbered, with the first rod being $1$, the second (auxiliary) rod being $2$, and the last (goal) rod being $3$. For example, with $n$ = $3$, we can do this in 7 moves:
Implement regular expression matching with the following special characters:
. (period) which matches any single character* (asterisk) which matches zeo or more of the preceding elementThat is, implement a function that takes in a string and a valid regular expression and return whether or not the string matches the regular expression.
For example, given the regular expression ra. and the string ray, your function should return True. The same regular expression on the string raymond should return False.
Given the regular epxression .*at and the string chat, your finction should return True. The same regular expression on the string chats should return False.
Given an array of numbers of length $n$, find both the minimum and maximum using less than $2 * (n-2)$ comparisons.
The game of Nim is played as follows. Starting with three heaps, each containing a variable numbers of items, two players take turns removing one or more items from a single pile. the player who eventually is forced to take the last stone loses. For example, if the initial heap sizes are $3$, $4$ and $5$, a game could be played as shown below:
| A | B | C | Action |
|---|---|---|---|
| 3 | 4 | 5 | Player 1 takes 3 items from B |
| 3 | 1 | 5 | Player 2 takes 2 items from C |
| 3 | 1 | 3 | Player 1 takes 3 items from A |
| 0 | 1 | 3 | Player 2 takes 3 items from C |
| 0 | 1 | 0 | Player 1 takes 1 item from A |
| 0 | 0 | 0 | Player 1 loses |
In other words, to start, the first player takes thress items from pile $B$. The second player responds by removing two stones from pile $C$. The game continues in this way until player one takes the last stone and loses.
Given a list of non-zero starting values [a, b, c], and assuming optimal play, determine whether the first player has a forced win.
The N-Queens problem asks you to find an arrangment so that $N$ queens can be placed on a $N \cdot N$ chess board without being able to directly attack each other. Write a program that displays one possible arrangment for the N-Queens problem.
You can use the following function to display your solution:
def print_board(queens):
board = [["." for i in range(len(queens))] for i in range(len(queens))]
for i in range(len(queens)):
board[queens[i]][i] = "Q"
for l in board:
for c in l:
print(c, end=" ")
print()
One way to unlock an Android phone is by swiping in a specific pattern across a $1$ - $9$ keypad, which looks like this:
For a pattern to be valid, it must satisfy the following criteria:
For example, $4$ - $2$ - $1$ - $7$ is a valid pattern, whereas $2$ - $1$ - $7$ is not. Find the total number of valid unlock patterns of lenght $n$ where $1$ $\leq$ $n$ $\leq$ $9$.
Sudoku is a puzzle where you're given a 9 by 9 grid partially filled with digits. The objective is to fill the grid subject to the constraint that every row, colum, and box (3 by 3 subgrid) must contain all of the digits from 1 to 9. Implement an efficient sudoku solver.