P4-M 4/24 Big Idea 3
Introduction: Zeen
Hello, my name is zeen and today we will be presenting big idea 3. Our topics include 2d arrays, iteration, and lists and dictionaries.
Objectives
Master the concepts of iteration, list, 2d-arrays, Dictionaries, and APIs
Vocab
Here is some vocab during the lesson, you should be familar with them already no need for me to read these out, now I will pass the speaking off to Kush
- Iteration: A process that repates itself
- Array: Sometimes called a list, can keep strings and intergers inside it
- 2D-Array: A collection of data elements arranged in a grid-like structure with rows and columns
- Mutable: the ability to be changed or modified
- Key: A Singular identifier that is associated with a certin value
1: 2D Array
Tic Tac Toe:Kush Sirohi
- What are some examples of 2d Arrays An example of a 2D array is an image with a width and a height. Each row of pixels in the image represents a row in the 2D array.
- What is a modern day game that could be classified as a 2D array All video games (Minecraft, for example), use 2D arrays to manage the current framebuffer and display pixels to the computer screen.
array = ["Hello", "Hi", "Whats up"]
twoDArray = [["Name", "ID", "Age"], ["Kush", "1", "16"], ["Finn", "2", "16"]]
print(f"This is a normal array: {array}")
print("This is a 2D array")
for row in twoDArray:
print(row)
board = [[' ', ' ', ' '],
[' ', ' ', ' '],
[' ', ' ', ' ']]
# Function to print the current state of the game board
def print_board():
print(" 0 1 2")
for i in range(3):
print(i, end=' ')
for j in range(3):
print(board[i][j], end=' ')
print()
# Function to check if a player has won the game
def check_win(player):
# Check rows for a win
for i in range(3):
if board[i][0] == player and board[i][1] == player and board[i][2] == player:
return True
# Check columns for a win
for j in range(3):
if board[0][j] == player and board[1][j] == player and board[2][j] == player:
return True
# Check diagonals for a win
if board[0][0] == player and board[1][1] == player and board[2][2] == player:
return True
if board[0][2] == player and board[1][1] == player and board[2][0] == player:
return True
# If no win condition is met, return False
return False
# Function to check if the game is a tie
def check_tie():
for i in range(3):
for j in range(3):
if board[i][j] == ' ':
return False
return True
# Function to play the game
def play_game():
# Initialize player and turn counter
player = 'X'
turns = 0
# Loop until the game is over
while True:
# Print the current state of the board
print_board()
# Get the player’s move
row = int(input(f"{player}'s turn. Enter row (0-2): "))
col = int(input(f"{player}'s turn. Enter column (0-2): "))
# Check if the move is valid
if board[row][col] == ' ':
board[row][col] = player
turns += 1
# Check if the player has won
if check_win(player):
print_board()
print(f"{player} wins!")
return
# Check if the game is a tie
if check_tie():
print_board()
print("It's a tie!")
return
# Switch players
player = 'O' if player == 'X' else 'X'
else:
print("That space is already taken. Try again.")
# Start the game
play_game()
times = 0
numbers = [1, 2, 3, 4, 5]
## Loops
for i in range(5):
print("hi")
while times <= 5:
print("hello")
times = times + 1
## Function with a parameters
def print_numbers(x):
for num in x:
print(num)
print_numbers(numbers)
Iteration Game
- Link to the game
- Play the levels (only play the first 2 in class) Levels completed in ticket
- Explain how the game relates to itertation The game relates to iteration because certain tasks such as moving the robot up, down, left, and right are repeated over and over again.
function run() {
// Read input values from the HTML document and convert them to integers.
UPinput = parseInt(document.getElementById("up").value);
DOWNinput = parseInt(document.getElementById("down").value);
LEFTinput = parseInt(document.getElementById("left").value);
RIGHTinput = parseInt(document.getElementById("right").value);
looper = parseInt(document.getElementById("loop").value);
runner.style.opacity = 0;
// Create an array to hold the movements.
let movements = [];
// Push 'up' movements to the array.
for (let l = 0; l < looper; l++) {
for (let k = 0; k < UPinput; k++) {
movements.push(up);
}
// Push 'down' movements to the array.
for (let i = 0; i < DOWNinput; i++) {
movements.push(down);
}
// Push 'left' movements to the array.
for (let a = 0; a < LEFTinput; a++) {
movements.push(left);
}
// Push 'right' movements to the array.
for (let c = 0; c < RIGHTinput; c++) {
movements.push(right);
}
}
// Set the initial index to 0 and execute each movement in sequence with a delay of 800 milliseconds.
let index = 0;
let intervalId = setInterval(() => {
// If the end of the movements array has been reached, stop executing movements.
if (index >= movements.length) {
clearInterval(intervalId);
win(); // Call the win function.
return;
}
movements[index](); // Execute the movement at the current index.
index++; // Increment the index.
}, 800);
}
List = [1, 2, 3, 4, 5]
Dict = {
1: "Hi",
2: "Hello",
3: "Whats Up"
}
# Why Do I call 0 for the first thing in a list, but 1 for Dict
#
print(List[0])
print(Dict[1])
How I used a dictonary to make a game
Memory Game:James- Link
How I used List to make a game
- Explain which parts of the code use lists
The
random.choiceuses thewordbecause it selects a random word from the list. - Explain what list manipulation is happening in that part
The list is manipulated by generating a random number between the list index min/max, selecting a random item, and storing it in
word.
import random
word_list = ["python", "computer", "programming", "algorithm", "database", "function", "variable", "loop", "iteration", "array", "mutable", "insertion", "deletion", "key", "API"]
word = random.choice(word_list)
scrambled_word = "".join(random.sample(word, len(word)))
print(f"Unscramble the following Computer Science Word: {scrambled_word}")
hints = 1
guesses = 1
guess = ""
while guess != word and guesses <= 4:
guess = input("What's the unscrambled word? ").lower()
if guess != word:
print("Sorry, that's not the word. Try again!")
if guesses == 1:
guesses += 1
elif guesses == 2:
print(f"Hint 1: The first letter of the word is '{word[0]}'")
guesses += 1
elif guesses == 3:
print(f"Hint 2: The second letter of the word is '{word[1]}'")
guesses += 1
else:
print(f"All 4 Guesses have been used, you didn't unscramble the word, the word was {word}")
guesses += 1
else:
print("Congratulations, you unscrambled the word!")
Hacks: Your Score/1
General 0.3
- Copy this noteboook into your personal fastpages
- Answer all questions
Iteration 0.2 (can get up to 0.23)
- Get to level 5
- Take ScreenShots of your name inside the box an put them in your ticket
- Create a code segment with iteration that does something cool
2D array 0.2 (can get up to 0.23)
- Explain how the tic tac toe game works
- Give 3 Examples of games that can be made from 2D arrays
List and Dictionaries 0.2 (can get up to 0.23)
- Explain the differences between Lists and Dictionaries
- Make a code block that manipulates either a list or a dictionary
General hacks
See above for all questions answered
Iteration
Levels: see ticket Code segment:
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "queue.h"
typedef struct bst_map_node {
struct bst_map_node* left;
struct bst_map_node* right;
void* key;
void* value;
} bst_map_node_t;
// 0: lhs == rhs
// > 0: lhs > rhs
// < 0: lhs < rhs
typedef int (*comparator_t)(void* lhs, void* rhs);
typedef struct {
bst_map_node_t* root;
comparator_t comparator;
} bst_map_t;
void bst_map_init(bst_map_t* bst_map, comparator_t comparator) {
bst_map->root = NULL;
bst_map->comparator = comparator;
}
bst_map_node_t** bst_map_insert2(bst_map_node_t** comparand_ptr,
void* key,
comparator_t comparator) {
bst_map_node_t* comparand = *comparand_ptr;
if (!comparand)
return comparand_ptr;
int result = comparator(key, comparand->key);
// data > comparand
if (result < 0) {
return bst_map_insert2(&comparand->left, key, comparator);
}
// data < comparand
else if (result > 0) {
return bst_map_insert2(&comparand->right, key, comparator);
}
// data == comparand
else
return comparand_ptr;
}
void bst_map_insert(bst_map_t* bst_map, void* key, void* value) {
bst_map_node_t* node = malloc(sizeof(bst_map_node_t));
node->left = NULL;
node->right = NULL;
node->key = key;
node->value = value;
if (!bst_map->root) {
bst_map->root = node;
} else {
bst_map_node_t** slot = bst_map_insert2(&bst_map->root, node->key, bst_map->comparator);
*slot = node;
}
}
// breadth-first traversal
void bst_map_print(bst_map_t* bst_map) {
queue_t nodes;
queue_init(&nodes);
queue_push(&nodes, bst_map->root);
bst_map_node_t* node;
while ((node = queue_pop(&nodes)) != NULL) {
printf("%s : %s\n", (char*)node->key, (char*)node->value);
if (node->left)
queue_push(&nodes, node->left);
if (node->right)
queue_push(&nodes, node->right);
}
}
// breadth-first search
void* bst_map_get(bst_map_t* bst_map, void* key) {
queue_t nodes;
queue_init(&nodes);
queue_push(&nodes, bst_map->root);
bst_map_node_t* node;
while ((node = queue_pop(&nodes)) != NULL) {
if (strlen(key) == strlen(node->key) && strcmp(key, node->key) == 0)
return node->value;
if (node->left)
queue_push(&nodes, node->left);
if (node->right)
queue_push(&nodes, node->right);
}
return NULL;
}
int compare_int(void* s1, void* s2) {
int i1 = atoi(s1);
int i2 = atoi(s2);
return i1 - i2;
}
int main() {
bst_map_t bst_map;
bst_map_init(&bst_map, (comparator_t)compare_int);
bst_map_insert(&bst_map, "8", "a");
bst_map_insert(&bst_map, "3", "b");
bst_map_insert(&bst_map, "10", "c");
bst_map_insert(&bst_map, "1", "d");
bst_map_insert(&bst_map, "6", "e");
bst_map_insert(&bst_map, "14", "f");
bst_map_insert(&bst_map, "4", "h");
bst_map_insert(&bst_map, "7", "i");
bst_map_insert(&bst_map, "13", "i");
bst_map_print(&bst_map);
char* c = bst_map_get(&bst_map, "10");
printf("\nGET:\n10 : %s\n", c);
}
The bst_map_get function includes a while loop that is important in the BFS traversal because it allows nodes to be processed one at a time. It constantly checks whether the current queue is not empty and pops the next node to print from it.
2D array
The given Python code is an implementation of a two-player Tic Tac Toe game on the command line. The game board is represented using a 2D array of size 3x3. The print_board() function prints the current state of the board, while the check_win(player) and check_tie() functions determine if a player has won or if the game is tied, respectively. The play_game() function handles the main game loop, prompting players to enter their moves and updating the board state accordingly. 2D arrays are used extensively in the code to represent and manipulate the game board, with nested loops used to iterate over the rows and columns of the board to print its state and check for wins and ties.
Games that can be made using 2D arrays: chess, crosswords, mazes, battleship, connect-4, minesweeper, reversi, sokoban, snake, tetris
List and Dictionaries
Differences between list and dictionary:
- Lists are collections of a single data type, while dictionaries are collections of key-value pairs, where the keys and values can be of two distinct types
- List elements are accessed using a numeric index, while dictionary values are accessed using a key
- Lists are ordered, while dictionaries are unordered (Binary Tree maps can be used to preserve order)
- Lists are mutable, while dictionaries are mutable too
Implementation of dictionary (hash map) from scratch using low-level memory semantics (full code):
#include <math.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include "debug.h"
#include "hash_map.h"
#include "types.h"
void hash_map_init(hash_map_t* hash_map) {
hash_map_bucket_t empty_bucket;
empty_bucket.head = NULL;
hash_map->buckets = (hash_map_bucket_t*)calloc(INIT_BUCKETS, sizeof(hash_map_bucket_t));
hash_map->num_buckets = INIT_BUCKETS;
}
u64 hash_map_len(hash_map_t* hash_map) {
u64 len = 0;
for (int i = 0; i < hash_map->num_buckets; i++) {
len += hash_map_bucket_len(&hash_map->buckets[i]);
}
return len;
}
float hash_map_load_factor(hash_map_t* hash_map) {
return (float)hash_map_len(hash_map) / hash_map->num_buckets;
}
void hash_map_resize(hash_map_t* hash_map) {
u64 new_size = (u64)ceil((hash_map_len(hash_map) + 1) / MAGIC_LOAD_FACTOR);
hash_map_bucket_t* new_buckets =
(hash_map_bucket_t*)calloc(new_size, sizeof(hash_map_bucket_t));
for (int i = 0; i < hash_map->num_buckets; i++) {
hash_map_entry_t* entry_ptr = hash_map->buckets[i].head;
while (entry_ptr) {
u64 hash = djb2a(entry_ptr->key);
hash_map_entry_t* entry =
hash_map_bucket_insert(&new_buckets[hash % new_size], entry_ptr);
entry->next = NULL;
entry_ptr = entry_ptr->next;
}
}
free(hash_map->buckets);
hash_map->num_buckets = new_size;
hash_map->buckets = new_buckets;
DEBUG_PRINT("hash_map_resize() to size %lu with load factor %f\n", new_size,
hash_map_load_factor(hash_map));
}
hash_map_entry_t* hash_map_insert(hash_map_t* hash_map, char* key, char* value) {
float load_factor = hash_map_load_factor(hash_map);
if (fabs(load_factor) > MAGIC_LOAD_FACTOR + EPSILON) {
hash_map_resize(hash_map);
}
hash_map_entry_t* entry = (hash_map_entry_t*)malloc(sizeof(hash_map_entry_t));
entry->key = key;
entry->value = value;
entry->next = NULL;
u64 hash = djb2a(entry->key);
u64 bucket = hash % hash_map->num_buckets;
DEBUG_PRINT("hash_map_insert(%s, %s) into bucket (%lu)\n", entry->key, entry->value, bucket);
hash_map_bucket_insert(&hash_map->buckets[bucket], entry);
return entry;
}
hash_map_entry_t* hash_map_get(hash_map_t* hash_map, char* key) {
u64 hash = djb2a(key);
hash_map_entry_t* entry_ptr = hash_map->buckets[hash % hash_map->num_buckets].head;
while (entry_ptr) {
if (strlen(key) == strlen(entry_ptr->key) && strcmp(key, entry_ptr->key) == 0) {
return entry_ptr;
}
entry_ptr = entry_ptr->next;
}
return NULL;
}
u64 hash_map_bucket_len(hash_map_bucket_t* bucket) {
u64 len = 0;
hash_map_entry_t* entry_ptr = bucket->head;
while (entry_ptr) {
len++;
entry_ptr = entry_ptr->next;
}
return len;
}
u64 hash_map_bucket_collisions(hash_map_t* hash_map) {
u64 collisions = 0;
for (int i = 0; i < hash_map->num_buckets; i++) {
if (hash_map_bucket_len(&hash_map->buckets[i]) > 1)
collisions++;
}
return collisions;
}
hash_map_entry_t* hash_map_bucket_insert(hash_map_bucket_t* hash_map_bucket,
hash_map_entry_t* entry) {
hash_map_entry_t** head = &hash_map_bucket->head;
hash_map_entry_t* entry_ptr = *head;
if (!entry_ptr) {
*head = entry;
} else {
while (entry_ptr->next) {
entry_ptr = entry_ptr->next;
}
entry_ptr->next = entry;
}
return entry;
}