pytils

Not to be confused with the pytils library for Russian-specific string utilities.

My collection of Python utility codes primarily designed for solving Kattis and Advent of Code (AoC) problems. It is intended to be as fast as possible, if not as short as possible. Feel free to use and customize them for your own use as you see fit.

Treasure List

Classification taken from cp-algorithms.

Algebra and Number Theory

Prime Numbers

• number_theory_prime_sieve

  The classic Eratosthenes prime sieve that runs in $O(n\log\log n)$ time. Makes use of an array that stores the smallest prime factor.

• number_theory_prime_factorization

  Applications of the prime sieve:

  • prime factorization of $n$
  • number of divisors of $n$
  • Euler's totient function, $\phi(n)$.

  Kattis problem(s) to try on: productdivisors, trickyfactoring

• number_theory_miller_rabin

  Checks if a number $n$ is probable prime. Works well in tandem with Pollard-Rho for integer factorization.

  Kattis problem(s) to try on: goldbach3, goldbach4

• number_theory_pollard_rho

  Finds a trivial factor of an integer $n$. Also includes Brent modification for faster version. Expected to run in $O(n^\frac{1}{4})$ time.

  Kattis problem(s) to try on: atrivialpursuit, bigfactoring, divisorsofasum, batchgcd

• number_theory_prime_counting

  Counts the number of prime numbers up to $n$ in $O(\sqrt{n})$ time. Also includes Meissel-Lehmer algorithm that runs in $O(n^\frac{2}{3})$ time.

  Kattis problem(s) to try on: primecount, frumtolutalning

Modular Arithmetic

• number_theory_gcd_lcm

  Basic GCD and LCM.

• number_theory_chinese_remainder

  Classic Chinese Remainder Theorem.

  Kattis problem(s) to try on: chineseremainder, generalchineseremainder

• number_theory_lucas_theorem

  Lucas' theorem, mainly used to compute a large binomial coefficient modulo some integer.

  Kattis problem(s) to try on: ghostbusters3, lights, countingtrees, classicalcounting

Miscellaneous

• fast_fourier_transform

  Fast Fourier Transform (FFT) used mainly for multiplying two polynomials, runs in $O(n\log n)$ time, where $n$ is the polynomial degree.

  Kattis problem(s) to try on: polymul1, polymul2, fastfouriertransform, allmodulopythagorean, allpairsums

• number_theory_mobius_function

  Computes the Möbius function and stores them in an array, runs in $O(n\log\log n)$ time.

  Kattis problem(s) to try on: yule, coprimeintegers, anothercoinweighingpuzzle

• number_theory_tonelli_shanks_cornacchia

  Solves $r^2 \equiv n \pmod p$ given an integer $n$ and prime number $p$, then uses the solution $r$ to solve $x^2 + dy^2 = p$.

  Kattis problem(s) to try on: gausssquares, allsquaresums

Data Structures

Lists

• circular_linked_list

  Simple implementation of circular linked list.

  Kattis problem(s) to try on: congaline, interviewqueue

• sliding_window

  Four variants of sliding windows mentioned in CP Book (all run in $O(n)$ time)

  • smallest subarray size whose sum is >= K
  • smallest subarray size where all numbers in range [1..K] are within
  • max(sum(A[i:i+K]) for i in range(len(A)-K+1))
  • [min(A[i:i+K]) for i in range(len(A)-K+1)]

  Kattis problem(s) to try on: slidecount, martiandna, treeshopping

• next_greater_element

  Computes the next greater element for each element in an array. Runs in $O(n)$ time.

  Kattis problem(s) to try on: whostheboss, flowingfountain

Trees

• avl_tree

  AVL tree implementation, including the self-rebalancing part. All queries are done in $O(\log n)$ time, except inorder traversal that takes $O(n)$ time.

  Kattis problem(s) to try on: hiredhelp, gcpc, physicalmusic, distributingseats, excellentengineers

• fenwick_tree_rsq

  Classic Fenwick tree to answer range sum queries (RSQ). Both PURQ (point update, range query) and RURQ (range update, range query) versions are available. Updates and queries all run in $O(\log n)$ time.

  Kattis problem(s) to try on: fenwick, supercomputer, taxtherich, hringvegurinn, tonlistarlisti

• fenwick_tree_rmq

  Binary-indexed tree but to answer range minimum/maximum queries (RMQ). Updates and queries all run in $O(\log n)$ time.

• segment_tree_general

  General recursive implementation of segment tree, which can be customized to handle different aggregate functions. Updates and queries all run in $O(\log n)$ time.

  Kattis problem(s) to try on: stigavordur

• segment_tree_dynamic

  Recursive implementation of the dynamic segment tree, which is currently optimized only for summation as aggregate. Updates and queries all run in $O(\log n)$ time.

  Kattis problem(s) to try on: japaneselottery, queryonarray

• treap

  Quick implementation of a treap data structure.

• wavelet_tree

  Incomplete implementation of the wavelet tree.

Miscellaneous

• sqrt_decomposition

  Sqrt-based data structure to support updates and sum queries in $O(\sqrt{n})$ time.

  Kattis problem(s) to try on: modulodatastructures

• ufds

  Classic union-find disjoint set (UFDS), also known as disjoint set union (DSU). Equipped with rank heuristics and path-compression, making both merging/union and querying run in $O(\alpha(n))$ time.

  Kattis problem(s) to try on: unionfind, reachableroads, skolavslutningen, busnumbers, tildes

Dynamic Programming

Knapsack

• knapsack

  0-1 Knapsack with given capacity and list of weights and values. Runs in $O(nW)$ time where $n$ is the number of items and $W$ is the maximum capacity.

  Kattis problem(s) to try on: knapsack, muzicari, ninepacks, orders, networking

Convex Hull Trick

• convex_hull_trick

  Convex hull optimization to optimize a specific $O(n^2)$ DP problem into an $O(n\log n)$ one. Here, we assume that the queries and slopes are sorted, thus reducing the problem into a sliding window after sorting.

  Kattis problem(s) to try on: coveredwalkway

• dynamic_convex_hull_trick_line_container

  Dynamic convex hull optimization, also known as the line container, solves a more general problem where lines and queries are not necessarily given in sorted order. Due to list insertion and deletion being $O(n)$, each operation should run in $O(n)$ time instead of $O(\log n)$, but should still be fast enough in most cases.

  Kattis problem(s) to try on: quintessentialbirthdaysurprise, yatp

Miscellaneous

• longest_increasing_subsequence

  Finds the LIS length and outputs any of them. Another variant counts the number of distinct LIS in an array of $n$ numbers. Both functions run in $O(n\log n)$ time.

  Kattis problem(s) to try on: increasingsubsequence, longincsubseq, manhattanmornings, growingupishardtodo

• travelling_salesman_problem_dp

  Finds the TSP cost in a graph of $n$ vertices and prints the TSP tour when needed. Both run in $O(n^2 2^n)$ time.

  Kattis problem(s) to try on: beepers, maximizingyourpay, stystiskogarleidangurinn, errands

String Processing

Suffix Array

• suffix_array_lcp

  Suffix array data structure alongside the longest common prefix (LCP) array for a string of length $n$. Suffix array construction runs in $O(n \log n)$ time.

  Kattis problem(s) to try on: suffixsorting, burrowswheeler, dvaput, repeatedsubstrings

String Matching

• string_matching_kmp

  The Knuth-Morris-Pratt (KMP) algorithm to find all matches of a string within the target string of length $n$. Runs in $O(n)$ time.

  Kattis problem(s) to try on: stringmatching, powerstrings, radiotransmission, clockpictures

• string_multimatching_aho_corasick

  The Aho-Corasick algorithm to find all matches of all query strings within the target string.

  Kattis problem(s) to try on: stringmultimatching

• string_multimatching_suffix_array

  Suffix array can also be used to find all matches of all query strings within the target string.

  Kattis problem(s) to try on: stringmultimatching

Miscellaneous

• manacher_subpalindromes

  Enumerates all palindromic substrings of a given string with length $n$ in $O(n)$ time.

  Kattis problem(s) to try on: genefolding, palindromes

• lexicographically_minimum_string_rotation_booth

  Booth's lexicographically minimum string rotation algorithm that runs in $O(n)$ time where $n$ is the length of the string.

  Kattis problem(s) to try on: passwordrotation

• z_function

  Computes the Z-function where z = [lcp(s, s[i:]) for i in range(len(s))].

Linear Algebra

• matrix_exponentiation_determinant_kirchoff

  Basic matrix (fast) exponentiation, determinant computation, and Kirchoff's tree theorem. The last two run in $O(N^3)$ time where $N$ is the size of the (square) matrix.

  Kattis problem(s) to try on: statetransfer, numbers2, organising, unicycliccount

• rref_gaussian_elimination

  Converts a matrix $A$ into its reduced row-echelon form (RREF). Very useful for Gaussian elimination.

  Kattis problem(s) to try on: circumsphere, stoichiometry, whiterabbit, equationsolver, equationsolverplus

• simplex_linear_programming

  Simplex algorithm for linear programming, supports both maximization and minimization.

  Kattis problem(s) to try on: cheeseifyouplease, roadtimes

Numerical Methods

• binary_search

  Binary search for both lower bound and upper bound. Function has to be monotonic. Runs in $O(\log(b-a))$ time given two starting bounds $[a, b]$.

  Kattis problem(s) to try on: financialplanning

• ternary_search

  Ternary search on both integer cases and double/float cases. Finds the minimum of a decreasing-then-increasing function. Runs in $O(\log(b-a))$ time given two starting bounds $[a, b]$.

  Kattis problem(s) to try on: reconnaissance, infiniteslides, tricktreat, euclideantsp, bottleflip

Geometry

2D

• compgeo_2d_polygon_area_centroid

  Area and centroid of a 2D-polygon consisting of $n$ vertices. Runs in $O(n)$ time.

  Kattis problem(s) to try on: convexpolygonarea, polygonarea, greedypolygons2

• compgeo_2d_point_in_polygon

  Checks if a point is within a polygon using two different approaches: angle calculation and ray intersection.

  Kattis problem(s) to try on: pointinpolygon

• compgeo_2d_intersect

  Line segment intersection.

  Kattis problem(s) to try on: segmentintersection, target, carlsvacation

• compgeo_2d_closest_pair

  Closest pair problem. Given $n$ 2D-coordinates, find the closest pair among all $O(n^2)$ possible pairs. Runs in $O(n\log n)$ time.

  Kattis problem(s) to try on: closestpair1, closestpair2

• compgeo_2d_convex_hull

  Given $n$ 2D-coordinates, compute its convex hull (smallest polygon that contains all points). Runs in $O(n\log n)$ time.

  Kattis problem(s) to try on: convexhull, convexhull2, humanobservation

• compgeo_2d_half_plane

  Half-plane intersection. Given $n$ half-planes in 2D, find the polygon that is contained within all the half-planes.

  Kattis problem(s) to try on: marshlandrescues, bigbrother

• compgeo_2d_minkowski_polygon_sum

  Compute the Minkowski sum of two convex polygons. In mathematical terms, ${a+b \forall a \in A, b \in B}$ for two convex polygons $A$ and $B$. Runs in $O(|A|+|B|)$ time.

  Kattis problem(s) to try on: geometryisfun, takeonmeme

3D

• compgeo_3d_projection_intersection

  Solves different simple queries in 3D coordinate system:

  • point-to-segment projection
  • point-to-plane projection
  • point-line distance
  • point-plane distance
  • line-plane intersection

• compgeo_3d_convex_hull

  Given $n$ 3D-coordinates where no four points lie on the same plane, compute its convex hull (smallest polyhedron that contains all points). Runs in $O(n^2)$ time.

  Kattis problem(s) to try on: worminapple

• compgeo_3d_minimum_enclosing_circle

  Smallest circle/sphere (2D/3D) that covers all the given points. Outputs the center and the radius.

  Kattis problem(s) to try on: starsinacan

Graph Algorithms

Graph Representation

• graph_adjacency_list

  Basic implementation of an adjacency list as a list of lists/dictionaries.

Graph Traversal

• traversal_bfs

  Simple BFS implementation. Runs in $O(V+E)$ time.

• traversal_dfs

  Simple iterative DFS implementation using stacks (because recursion is slow in Python). Runs in $O(V+E)$ time.

Connected Components & Graph Properties

• tarjan_bridges_cut_vertices

  Tarjan's algorithm to find bridges and cut vertices. Runs in $O(V+E)$ time.

  Kattis problem(s) to try on: birthday, caveexploration

• topological_sorting

  Topological sorting using Kahn's algorithm or using the DFS approach. Runs in $O(V+E)$ time.

  Kattis problem(s) to try on: namsleid, rodun, brexitnegotiations, pachinkoprobability

• scc_kosaraju

  Extension of DFS topological sorting, Kosaraju's algorithm, to enumerate the strongly connected components (SCC). Runs in $O(V+E)$ time.

  Kattis problem(s) to try on: dominos, equivalences

Minimum Spanning Trees

• minimum_spanning_tree_prim

  Prim's algorithm to compute the minimum spanning tree (MST) and its cost. Both sparse graph and dense graph variants are available. Former runs in $O(E\log V)$ time, but latter runs in $O(V^2)$.

  Kattis problem(s) to try on: minimumspanningtree, freckles, lostmap, naturereserve

• minimum_spanning_tree_kruskal

  Kruskal's algorithm to compute the minimum spanning tree (MST) and its cost using UFDS. Runs in $O(E\log E)$ time.

  Kattis problem(s) to try on: minimumspanningtree, freckles, lostmap, treehouses, gridmst

Shortest Paths

• sssp_bellman_ford

  Single-source shortest path (SSSP) using Bellman-Ford's algorithm, which also includes negative cycle detection. Runs in $O(VE)$ time.

  Kattis problem(s) to try on: shortestpath3, shortestpath4, hauntedgraveyard

• sssp_dijkstra

  Single-source shortest path (SSSP) using modified Dijkstra's algorithm. Runs in $O(E\log E)$ time.

  Kattis problem(s) to try on: shortestpath1, shortestpath2, getshorty, fendofftitan, invasion, xentopia, hopscotch50, visualgo, catchingnoodles

• apsp_floyd_warshall

  All-pairs shortest path (APSP) using Floyd-Warshall's algorithm. Runs in $O(V^3)$ time. Different variants are also available.

  • minimax/maximin (useful for min/maximum spanning trees)
  • transitive closure
  • +ve/-ve cycle detection
  • enumerate shortest path from anywhere to anywhere

  Kattis problem(s) to try on: allpairspath, arbitrage, speedyescape, assembly

Lowest Common Ancestor

• tarjan_offline_lca

  Tarjan's algorithm to compute the LCA of some query pair of vertices on a tree rooted at vertex $0$. Runs in $O(V+Q)$ time.

  Kattis problem(s) to try on: rootedsubtrees, treehopping, tourists, easyascab

Network Flows

• max_flow_ford_fulkerson

  Ford-Fulkerson's algorithm to compute the maximum flow of a graph. Runs in $O(Ef)$ time, where $f$ is the maximum flow itself.

  Kattis problem(s) to try on: conveyorbelts

• max_flow_dinic

  Dinic's algorithm to compute the maximum flow of a graph. Runs in $O(V^2E)$ time.

  Kattis problem(s) to try on: maxflow, mincut, waif, avoidingtheapocalypse, gravamen

• min_cost_max_flow

  Two different approaches to compute the minimum cost maximum flow of a graph, including the shortest-path fast algorithm (SPFA). Maximize flow, then among all solutions of that same flow, find the minimum cost.

  Kattis problem(s) to try on: mincostmaxflow, ragingriver, tourist, catering, aqueducts,

Matchings

• mcbm_unweighted_augmenting_path

  Minimum cardinality bipartite matching (MCBM) on an unweighted bipartite graph using augmenting paths. Also known as the Hopcroft-Karp algorithm, which runs in $O(\sqrt{V}E)$ time.

  Kattis problem(s) to try on: pianolessons, catvsdog, bioferd, talltowers, bookclub, bookcircle, gopher2, codenames, superdoku, linije, elementarymath, taxicab, guardianofdecency, paintball, antennaplacement, borders, escapeplan, latinsquare

• mcbm_weighted_hungarian_kuhn_munkres

  Minimum (cost and) cardinality bipartite matching (MCBM) on a weighted bipartite graph using the Hungarian algorithm. Also known as the Kuhn-Munkres algorithm, which runs in $O(V^3)$ time. Rows are a single partition, then columns for the other partition.

  Kattis problem(s) to try on: hungarianservices, bond, cheatingatwar, hexagon

• mcm_unweighted_edmonds

  Minimum cardinality matching on general unweighted graphs using Edmond's blossom algorithm. Runs in $O(EV^2)$ time.

  Kattis problem(s) to try on: translatorsdinner, debellatio

• mcm_weighted_dp_bitmask

  Minimum cost matching on general weighted graphs using DP and bitmask. Runs in $O(V2^V)$ time.

  Kattis problem(s) to try on: hidingchickens

Miscellaneous

• 2sat

  Check for 2-satisfiability of conjunctive normal forms (CNF). On top of checking if it's satisfiable, also finds such boolean assignment if any. Makes use of Kosaraju's algorithm.

  Kattis problem(s) to try on: palindromicdna

• chinese_postman_problem

  Shortest circuit on a weighted undirected graph that visits every edge at least once (as opposed to TSP that requires visiting every vertex other than starting node exactly once). Makes use of Floyd-Warshall's APSP algorithm.

  Kattis problem(s) to try on: joggingtrails

• hierholzer_eulerian_cycle

  Prints the Eulerian circuit given a directed Eulerian graph (visits every edge exactly once).

  Kattis problem(s) to try on: eulerianpath

• min_path_cover_dag

  You can use Hopcroft Karp's algorithm to find the minimum number of paths needed to cover the edges of a directed acyclic graph (DAG).

• maximum_clique_bron_kerbosch

  Finds the maximum number such that exists a complete subgraph (clique) consisting of this many vertices using Bron-Kerbosch's algorithm, which is supposes to run in $O(3^\frac{V}{3})$ time.

  Kattis problem(s) to try on: maxclique, letterballoons

• minimum_vertex_cover_bipartite

  Minimum number of vertices needed to cover all edges of the graph using Kőnig's theorem.

  Kattis problem(s) to try on: bilateral

• min_clique_cover_backtracking

  Minimum number of cliques needed to cover the entire graph, simply using the plain old backtracking.

  Kattis problem(s) to try on: busplanning, committeeassignment

Advent of Code

• grid_template

  Just a grid template.

• game_of_life

  Simulation of the well-known Conway's game of life.

• intcode

  Advent of Code's signature esoteric language to "annoy" whoever is attempting AoC 2019.

Miscellaneous

• cryptarithm

  Backtracking with optimized prunings to solve cryptarithm.

  Kattis problem(s) to try on: greatswercporto, sendmoremoney

• inverse_index

  Computes the number of pairs on an array with switched orders, also interpretable as the number of swaps needed when performing bubble sort on the array of size $n$. Runs in $O(n\log n)$ time.

  Kattis problem(s) to try on: excursion, ultraquicksort, froshweek, bread, bilskurar, camels, vudu

• sprague_grundy_mex

  Sprague-Grundy theorem to find the Grundy value of a game state using minimum excluded value (MEX).

  Kattis problem(s) to try on: snim, cuboidslicinggame, wheelgame