README.md

Python Kata

2 kyu

• Symbolic differentiation of prefix expressions
  • Symbolic differentiation of prefix expressions with a fixed set of unary functions and binary operations in single variable
  • Abstract classes, dataclass, meta-classes, recursion, parsing
  • Implemented in module differentiation

3 kyu

• Binomial Expansion
  • Expands an expression of the form (ax+b)^n using the Binomial formula
  • Implemented in module binomial_expansion
• Closest pair of points in linearithmic time
  • Finds the closest pair of points in a list of n 2D points in O(n*log(n)) time
  • Divide and conquer algorithm
  • Implemented in module closest_points
• GET TO THE CHOPPA!
  • Implements A* with Manhattan distance heuristic to find the shortest path in a gridworld environment
  • Implemented in module grid_path
• Huffman Encoding
  • ImplementsHuffman coding
  • Implemented in module huffman
• The Millionth Fibonacci
  • Calculates the n-th Fibonacci number in O(log(n)) time
  • Implemented in module fibonacci
• Sudoku Solver
  • Implements a CSP-based Sudoku solver with AC3 checking and MRV heuristic
  • Implemented in module sudoku_solver

4 kyu

• Conway's Game of Life
  • Simulates given number of iterations of Conway's Game of Life with an infinite universe and cropping to the area containing living cells
  • Implemented in module game_of_life
• Decode the Morse code, advanced
  • Implements an advanced Morse code decoder from a binary message with an unknown transmission rate
  • Implemented in module decode_morse_adv
• Matrix Determinant
  • Computes the determinant of given square matrix via the Laplace expansion
  • Implemented in module determinant
• parseInt() reloaded
  • Converts given string representing a number in words into an integer
  • Implemented in module parse_int
• Range Extraction
  • Format a list of integers and shorten it by replacing consecutive sequences by a range
  • Stateful iteration, yield and yield from generator functions
  • Implemented in module range_extraction
• Shortest Knight Path
  • Finds shortest path of a knight piece on a chess board between two positions
  • Implements Dijkstra's SP algorithm (Uniform-cost Search)
  • Implemented in module knight_path
• Sort binary tree by levels
  • Traverses given tree in BFS order yielding its values
  • Implements Breadth-first search
  • Implemented in module tree_by_levels
• Strip Comments
  • Strips end of line comments from given text and a set of comment markers
  • Implemented in module strip_comments
• Strongly connected components
  • Finds strongly connected components in given directed graph
  • Implements Tarjan's SCC algorithm
  • Implemented in module scc
• Sum of Intervals
  • Compute the total length of n overlapping intervals in O(n*log(n)) time
  • Implemented in module sum_intervals
• The learning game - Machine Learning #1
  • Implements a machine which learns how to respond to a set of commands by selecting correct action to handle them
  • Implements a simple greedy actor for deterministic environments and (Bernoulli) MAB (UCB-1) for stochastic environments/actions
  • Implemented in module learning_game
• The observed PIN
  • Finds all possible pins on a numpad given observed sequence where each observed digit might be wrong
  • Implements a recursive Depth-first Search
  • Implemented in module pins

5 kyu

• Directions Reduction
  • Shortens given path of North, East, South, West directions by removing directly opposite pairs
  • Comprehension, Deque and IntEnum
  • Implemented in module directions_reduction
• Human Readable Time
  • Converts given number of seconds into a string in HH:MM:SS format
  • Implemented in module readable_time
• Intro to Statistics - Part 1: A Five figure summary
  • Computes the five-number summary over a series of samples
  • The usage of numpy/pandas is disallowed for this Kata
  • Implemented in module five_figure_summary
• Mean without outliers
  • Computes the mean of given sample stripped from outliers defined as a multiple of standard deviations form the sample mean.
  • Implemented in module clean_mean
• Number of trailing zeros of N!
  • Computes the number of trailing zeros in n! without evaluating it
  • Implemented in module factorial_zeros
• RGB To Hex Conversion
  • Formats given RGB triplet as a hexadecimal string
  • Implemented in module rgb_hex
• Simple assembler interpreter
  • A simple interpreter of assembler which supports: mov x y, inc x, dec x, and jnz x y
  • Implemented in module simple_assembler
• Valid Parentheses
  • Checks whether given expression has balanced (matching) parentheses
  • Implemented in module parentheses
• What's a Perfect Power anyway?
  • Checks whether given integer is a perfect power
  • Iteration, binary search, fast exponentiation
  • Implemented in module perfect_power
• Where my anagrams at?
  • Finds all anagrams of a word from a list
  • List comprehension and word frequency via Counter
  • Implemented in module anagrams

6 kyu

• 1RM Calculator
  • Calculates projected one-repetition maximum (1RM)
  • Implemented in module rm_calculator
• Build a pile of Cubes
  • Calculates no. cubes in hierarchical structure of given its volume
  • Implemented in module cube_pile
• Decode the Morse code
  • Morse code decoder
  • String parsing and manipulation, join, map and comprehensions
  • Implemented in module decode_morse
• Detect Pangram
  • Checks whether given string is a pangram
  • Dictionary comprehension and efficient occurrence checking
  • Implemented in module pangram
• Elimination Tournament
  • Simulates a rank-based elimination tournament
  • List manipulation, comprehension and aggregation
  • Implemented in module tourney
• Format a string of names like 'Bart, Lisa & Maggie'
  • Simple List, Dict and str manipulation
  • Implemented in module name_list
• Is a number prime?
  • Checks whether given number is a prime number
  • Implemented in module prime
• Meeting
  • Sorting and simple string manipulation
  • Implemented in module meeting
• Simple Fun #83: MineSweeper
  • Given a flagged MineSweeper board, count the number of neighboring mines for each board position
  • Implemented in module minesweeper
• Sums of Parts
  • Computes all cumulative sums of given list of numbers
  • Simple enumeration and aggregation
  • Implemented in module parts_sums
• Who likes it?
  • Converts list of names to Facebook's "like" text
  • Simple list manipulation, matching cases and string formatting
  • Implemented in module likes