I was eating some godforsaken amalgamation of food I call dinner when one of my housemates came downstairs to our shared living room and said something that piqued my interest.
“The Bills beat the Chiefs. The Circle of Suck has been completed,” he stated to the three of us eating and/or watching TV. After asking for some elaboration, he explained that it was the phenomenon in a sports league where if team A beats Team B, team B beats Team C, and then Team C beats Team A, where every team in the league has been included in this circle, then it is called a completed Circle of Suck™ because, well, everyone sucks. After thinking about what this implies, I wondered whether it was common for a Circle of Suck to be completed in a regular NFL season, and which seasons saw a completed circle.
The Problem
This interesting question sounds straightforward, but it is actually an NP-Complete problem with no worst-case polynomial-time algorithm to solve it. In other words, it has an answer that is easy to check, but intense to derive. What’s worse is that the number of NFL teams (max 32) is large enough that most exponential-time brute force algorithms break down. To solve it, we will transform our question into a graph problem. We’ll make every NFL team a node in a graph, and every regular-season game an edge, where a connection from team to team indicates that team has beaten team at some point in the regular season. We’ll exclude ties, cancelled games, and other edge cases. In a directed graph, it means that translates to being able to travel from node to node , but not from to . Then, this problem is whether an arbitrary graph with nodes admits a Hamiltonian cycle of size .
Borrowing a definition from Wolfram MathWorld:
A Hamiltonian cycle, also called a Hamiltonian circuit, Hamilton cycle, or Hamilton circuit, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once (Skiena 1990, p. 196).
Before trying to find a Circle of Suck programmatically, we can eliminate a few years through common sense. Because a Hamiltonian cycle requires a node to have an edge going in and going out, any regular season where a team wins or loses all its games cannot have a Circle of Suck. A few years have seen this happen. The 1972 Miami Dolphins had a perfect season, winning all regular season and postseason games. The 2007 Patriots also won every regular season game, but lost the super bowl. Meanwhile, the 2017 Browns and 2008 Lions have had a perfect losing season, to name a few. Thus, we expect these years to not admit a Hamiltonian cycle with every team and lack a Circle of Suck encompassing all teams.
I found a Kaggle dataset of NFL game results going back to 1966, wrote a quick Rust script implementing a DP solution for the Hamiltonian cycle detection problem, and hit a brick wall.
There’s a reason NP-Complete problems are called intractable. Even after performance measuring my code, implementing unsafe, using AHash to reduce the hashing time for my hashmaps, and running with compiler optimizations, my DP solution was really slow. This is expected because we have to check combinations, which gets really nasty when .
- For a graph with 22 teams, it takes about 1.58 seconds
- For 25, 10.98 seconds
- For 27, 42.27 seconds
- For 29, 160.61 seconds
- For 32, that’s projected to be 1,280 seconds or about 20 minutes
At most, we have 32 teams, and we want to compute the existence of a Hamiltonian cycle in 57 seasons. At this rate the program would take about 19 hours to run. We also wouldn’t know what the Hamiltonian cycle is, only that one exists.
My solution was to use a SAT solver. What’s a SAT solver? It takes in giant boolean expressions in the form like “(A or B) and (B or C)” and spits out states for all the variables which lead to the entire expression returning true. The nice thing is that many computationally intractable problems could be turned into giant boolean satisfiability problems. I landed on a python SAT solver called pysat, and quickly wrote code that loads all regular season scores, builds a graph, and finds a Hamiltonian cycle. I followed the reduction from here.
Results
To my surprise, nearly every year without a perfect losing or winning team admits a complete Circle of Suck, only 10 years from 1966 through 2023 fail to admit a complete Circle of suck, and five of those are before 1975. Those ten years are:
- 1966
- 1967
- 1968
- 1969
- 1972 (Dolphins perfect season)
- 1976
- 1982 (Strike season w/ abbreviated schedule)
- 2007 (Patriots perfect season)
- 2008 (Lions lost every game)
- 2017 (Browns lost every game)
I’ve listed every Circle of Suck below. I’ve done my best to double check the accuracy of everything, but if you notice an error, please let me know.
Postscript
This piece has been sitting in my drafts for a while. Writing, like any skill, requires regular practice, and I’m going to try to make it a more regular thing because I don’t want my writing abilities to atrophy. We’ll see how that goes. :)
Appendix
My Python Code w/ Sat-Solver
from itertools import product
import numpy as np
import pandas as pd
from pysat.formula import CNF
from pysat.solvers import Solver
# py-sat relies on natural number identifiers
# but the reduction uses double-indexed variables
# let n be the total number of vertices in the graph
# n = 35, because we at most have 32 teams
def idx(pos_idx, vertex_idx, n=35):
return vertex_idx * n + pos_idx + 1
def invert(edges: set[tuple[int, int]], n: int, bidi=False):
inv = set()
for (u, v) in product(range(n), range(n)):
if u == v or (u,v) in edges or (bidi and (v, u) in edges):
continue
inv.add((u, v))
return inv
def hamiltonian_sat(edges: set[tuple[int, int]], n: int, bidi=False) -> list[int] | None:
cnf = CNF()
# for each vertex it must appear in one position
for v in range(n):
cnf.append([idx(i, v) for i in range(n)])
# for each vertex, it must appear in only one position
for v, l in product(range(n), range(n)):
for r in range(l + 1, n):
cnf.append([-idx(l, v), -idx(r, v)])
# for each position, there must be one vertex
for pos in range(n):
cnf.append([idx(pos, v) for v in range(n)])
# no two vertices share the same position
for pos, u in product(range(n), range(n)):
for v in range(u + 1, n):
cnf.append([-idx(pos, u), -idx(pos, v)])
# consecutive vertices must be adjacent
inv = invert(edges, n, bidi=bidi)
for pos, edge in product(range(n), inv):
cnf.append([-idx(pos, edge[0]), -idx((pos + 1) % n, edge[1])])
with Solver(bootstrap_with=cnf) as solver:
has_solution = solver.solve()
if has_solution:
model = solver.get_model()
cycle = [None] * n
for pos, v in product(range(n), range(n)):
if model[idx(pos, v) - 1] > 0:
cycle[pos] = v
return cycle
return None
def verify_hamiltonian_cycle(cycle: list[int], edges: set[tuple[int, int]]):
for s in range(len(cycle)):
i, j = cycle[s], cycle[(s + 1) % len(cycle)]
if (i, j) not in edges:
return False
return True
if __name__ == "__main__":
# load score data
df = pd.read_csv('./spreadspoke_scores.csv')
# group by season, get all season years
season_grouped = df.groupby("schedule_season")
seasons = season_grouped.groups.keys()
no_circle = []
# We run our analysis per-season
for season in seasons:
# skip 2024
if season == 2024 or season < 1970:
continue
scores = season_grouped.get_group(season)
# get team names
teams = set([*scores["team_home"].unique(), *scores["team_away"].unique()])
n = len(teams)
# assign int to each team
team_map = {k: idx for idx, k in enumerate(teams)}
index_map = {idx: k for k, idx in team_map.items()}
# 1. is there a circle of parity this season?
edges = set()
# now, we define each graph with each team being a node, and if team a beats team b,
# then there's an edge from node a to node b. Each game add ones edge
# we also filter out post-season games
for row in scores[scores["schedule_playoff"] == False].itertuples():
# skip ties
if row.score_away == row.score_home:
continue
away_idx = team_map[row.team_away]
home_idx = team_map[row.team_home]
if row.score_away > row.score_home:
edges.add((away_idx, home_idx))
else:
edges.add((home_idx, away_idx))
cycle = hamiltonian_sat(edges, n)
if cycle:
circle = list(map(index_map.get, cycle))
verify = verify_hamiltonian_cycle(cycle, edges)
assert verify
print(f"### {season}")
print(" $\\rightarrow$ ".join(circle + [f"{circle[0]}..."]))
else:
no_circle.append(season)
print(no_circle)Every Circle of Suck (from 1970 to 2023)
1970
San Diego Chargers Denver Broncos New Orleans Saints Detroit Lions Oakland Raiders Kansas City Chiefs Baltimore Colts Chicago Bears Green Bay Packers Pittsburgh Steelers Buffalo Bills Boston Patriots Miami Dolphins Atlanta Falcons San Francisco 49ers Los Angeles Rams St. Louis Cardinals Washington Redskins Philadelphia Eagles New York Giants New York Jets Minnesota Vikings Dallas Cowboys Cleveland Browns Houston Oilers Cincinnati Bengals San Diego Chargers…
1971
Oakland Raiders San Diego Chargers Kansas City Chiefs Buffalo Bills New England Patriots Miami Dolphins Los Angeles Rams Chicago Bears Minnesota Vikings Atlanta Falcons San Francisco 49ers New Orleans Saints Dallas Cowboys Washington Redskins St. Louis Cardinals New York Jets Cincinnati Bengals Philadelphia Eagles Detroit Lions Houston Oilers Pittsburgh Steelers New York Giants Green Bay Packers Denver Broncos Cleveland Browns Baltimore Colts Oakland Raiders…
1973
Pittsburgh Steelers Cincinnati Bengals Minnesota Vikings New York Giants Houston Oilers Baltimore Colts Detroit Lions Atlanta Falcons Los Angeles Rams Dallas Cowboys New Orleans Saints Chicago Bears Green Bay Packers New York Jets New England Patriots San Diego Chargers Buffalo Bills Philadelphia Eagles St. Louis Cardinals Washington Redskins San Francisco 49ers Denver Broncos Kansas City Chiefs Oakland Raiders Miami Dolphins Cleveland Browns Pittsburgh Steelers…
1974
San Diego Chargers Denver Broncos Oakland Raiders Cleveland Browns Houston Oilers Buffalo Bills New England Patriots Minnesota Vikings Chicago Bears Detroit Lions Cincinnati Bengals Pittsburgh Steelers New Orleans Saints St. Louis Cardinals Philadelphia Eagles New York Giants Dallas Cowboys Washington Redskins Los Angeles Rams San Francisco 49ers Atlanta Falcons Green Bay Packers Baltimore Colts New York Jets Miami Dolphins Kansas City Chiefs San Diego Chargers…
1975
Oakland Raiders San Diego Chargers Kansas City Chiefs Denver Broncos Philadelphia Eagles Washington Redskins St. Louis Cardinals New York Jets New England Patriots Baltimore Colts Miami Dolphins Chicago Bears New Orleans Saints Atlanta Falcons San Francisco 49ers Los Angeles Rams Detroit Lions Minnesota Vikings Green Bay Packers Dallas Cowboys New York Giants Buffalo Bills Pittsburgh Steelers Cleveland Browns Cincinnati Bengals Houston Oilers Oakland Raiders…
1977
Cleveland Browns Houston Oilers Pittsburgh Steelers Dallas Cowboys Denver Broncos Oakland Raiders Buffalo Bills New York Jets New Orleans Saints Chicago Bears Los Angeles Rams Philadelphia Eagles New York Giants Washington Redskins Atlanta Falcons Tampa Bay Buccaneers St. Louis Cardinals Minnesota Vikings Cincinnati Bengals Green Bay Packers San Francisco 49ers Detroit Lions Baltimore Colts New England Patriots Kansas City Chiefs San Diego Chargers Miami Dolphins Seattle Seahawks Cleveland Browns…
1978
Oakland Raiders Kansas City Chiefs San Diego Chargers Seattle Seahawks Chicago Bears Green Bay Packers New Orleans Saints New York Giants San Francisco 49ers Cincinnati Bengals Cleveland Browns Los Angeles Rams Minnesota Vikings Detroit Lions Tampa Bay Buccaneers Buffalo Bills Baltimore Colts New England Patriots New York Jets Miami Dolphins Dallas Cowboys Philadelphia Eagles Washington Redskins St. Louis Cardinals Atlanta Falcons Houston Oilers Pittsburgh Steelers Denver Broncos Oakland Raiders…
1979
Oakland Raiders Miami Dolphins Seattle Seahawks Cleveland Browns Kansas City Chiefs Baltimore Colts New England Patriots San Diego Chargers New Orleans Saints Detroit Lions Chicago Bears Los Angeles Rams St. Louis Cardinals Houston Oilers Cincinnati Bengals Pittsburgh Steelers Denver Broncos Atlanta Falcons San Francisco 49ers Tampa Bay Buccaneers New York Giants Washington Redskins Dallas Cowboys Philadelphia Eagles Green Bay Packers Minnesota Vikings Buffalo Bills New York Jets Oakland Raiders…
1980
Cincinnati Bengals Kansas City Chiefs Houston Oilers Tampa Bay Buccaneers New York Giants St. Louis Cardinals Philadelphia Eagles New Orleans Saints New York Jets Atlanta Falcons Chicago Bears Green Bay Packers Minnesota Vikings Detroit Lions Los Angeles Rams Dallas Cowboys Oakland Raiders Seattle Seahawks Washington Redskins San Diego Chargers Denver Broncos Cleveland Browns Pittsburgh Steelers Miami Dolphins San Francisco 49ers New England Patriots Baltimore Colts Buffalo Bills Cincinnati Bengals…
1981
Oakland Raiders Seattle Seahawks San Diego Chargers Kansas City Chiefs Tampa Bay Buccaneers Green Bay Packers New Orleans Saints Los Angeles Rams Chicago Bears Denver Broncos Cleveland Browns Cincinnati Bengals New York Jets New York Giants St. Louis Cardinals Buffalo Bills Miami Dolphins Pittsburgh Steelers Atlanta Falcons Minnesota Vikings Philadelphia Eagles Washington Redskins Detroit Lions San Francisco 49ers Dallas Cowboys Baltimore Colts New England Patriots Houston Oilers Oakland Raiders…
1983
Dallas Cowboys Kansas City Chiefs Denver Broncos Baltimore Colts New York Jets Los Angeles Rams New Orleans Saints Chicago Bears Tampa Bay Buccaneers Minnesota Vikings Cleveland Browns New England Patriots Pittsburgh Steelers San Diego Chargers New York Giants Philadelphia Eagles Atlanta Falcons San Francisco 49ers St. Louis Cardinals Seattle Seahawks Los Angeles Raiders Miami Dolphins Buffalo Bills Cincinnati Bengals Houston Oilers Detroit Lions Green Bay Packers Washington Redskins Dallas Cowboys…
1984
Minnesota Vikings Tampa Bay Buccaneers Detroit Lions Green Bay Packers Los Angeles Rams Cincinnati Bengals Cleveland Browns Atlanta Falcons New Orleans Saints St. Louis Cardinals New York Giants Dallas Cowboys Chicago Bears Los Angeles Raiders Houston Oilers New York Jets Kansas City Chiefs Denver Broncos San Diego Chargers Miami Dolphins Washington Redskins Philadelphia Eagles New England Patriots Seattle Seahawks Buffalo Bills Indianapolis Colts Pittsburgh Steelers San Francisco 49ers Minnesota Vikings…
1985
St. Louis Cardinals Cleveland Browns New England Patriots Seattle Seahawks San Diego Chargers Denver Broncos Pittsburgh Steelers Kansas City Chiefs Indianapolis Colts Buffalo Bills Houston Oilers Cincinnati Bengals Dallas Cowboys Washington Redskins Atlanta Falcons Los Angeles Rams Tampa Bay Buccaneers Detroit Lions Miami Dolphins Chicago Bears Minnesota Vikings San Francisco 49ers Los Angeles Raiders New York Jets Green Bay Packers New York Giants New Orleans Saints Philadelphia Eagles St. Louis Cardinals…
1986
Seattle Seahawks Kansas City Chiefs Cincinnati Bengals Green Bay Packers Cleveland Browns Miami Dolphins New York Jets New England Patriots New Orleans Saints Los Angeles Rams Chicago Bears Detroit Lions Minnesota Vikings Tampa Bay Buccaneers Buffalo Bills Pittsburgh Steelers Houston Oilers Indianapolis Colts Los Angeles Raiders Dallas Cowboys New York Giants San Francisco 49ers Atlanta Falcons St. Louis Cardinals Philadelphia Eagles San Diego Chargers Denver Broncos Washington Redskins Seattle Seahawks…
1987
San Francisco 49ers Los Angeles Rams St. Louis Cardinals New York Giants Philadelphia Eagles New Orleans Saints Atlanta Falcons Washington Redskins Detroit Lions Dallas Cowboys New England Patriots New York Jets Seattle Seahawks Chicago Bears Tampa Bay Buccaneers Green Bay Packers Minnesota Vikings Denver Broncos San Diego Chargers Cleveland Browns Houston Oilers Cincinnati Bengals Kansas City Chiefs Los Angeles Raiders Buffalo Bills Indianapolis Colts Miami Dolphins Pittsburgh Steelers San Francisco 49ers…
1988
Denver Broncos Los Angeles Rams New York Giants Kansas City Chiefs Seattle Seahawks Houston Oilers New England Patriots Chicago Bears Buffalo Bills New York Jets Detroit Lions Atlanta Falcons Los Angeles Raiders San Diego Chargers Pittsburgh Steelers Miami Dolphins Cleveland Browns Cincinnati Bengals Washington Redskins Philadelphia Eagles Dallas Cowboys Phoenix Cardinals San Francisco 49ers New Orleans Saints Tampa Bay Buccaneers Green Bay Packers Minnesota Vikings Indianapolis Colts Denver Broncos…
1989
Cincinnati Bengals Kansas City Chiefs Dallas Cowboys Washington Redskins Tampa Bay Buccaneers Phoenix Cardinals Seattle Seahawks New England Patriots Houston Oilers Pittsburgh Steelers Detroit Lions New Orleans Saints Los Angeles Rams New York Giants Minnesota Vikings Green Bay Packers San Francisco 49ers New York Jets Atlanta Falcons Buffalo Bills Indianapolis Colts Miami Dolphins Cleveland Browns Chicago Bears Philadelphia Eagles Denver Broncos San Diego Chargers Los Angeles Raiders Cincinnati Bengals…
1990
Atlanta Falcons Los Angeles Rams Cleveland Browns Pittsburgh Steelers New England Patriots Indianapolis Colts Kansas City Chiefs Detroit Lions Minnesota Vikings Chicago Bears Green Bay Packers Los Angeles Raiders Miami Dolphins Buffalo Bills New York Giants Phoenix Cardinals Philadelphia Eagles Washington Redskins Dallas Cowboys San Diego Chargers Denver Broncos Seattle Seahawks Houston Oilers New Orleans Saints San Francisco 49ers Cincinnati Bengals New York Jets Tampa Bay Buccaneers Atlanta Falcons…
1991
New England Patriots Houston Oilers Denver Broncos Seattle Seahawks Indianapolis Colts New York Jets Miami Dolphins Chicago Bears Green Bay Packers Tampa Bay Buccaneers Philadelphia Eagles Washington Redskins Detroit Lions Dallas Cowboys Phoenix Cardinals Los Angeles Rams New York Giants San Francisco 49ers Kansas City Chiefs Buffalo Bills Pittsburgh Steelers Cleveland Browns San Diego Chargers New Orleans Saints Minnesota Vikings Atlanta Falcons Los Angeles Raiders Cincinnati Bengals New England Patriots…
1992
New York Jets Buffalo Bills Miami Dolphins Houston Oilers Kansas City Chiefs Philadelphia Eagles Dallas Cowboys Seattle Seahawks Denver Broncos Cleveland Browns Chicago Bears Green Bay Packers Los Angeles Rams New England Patriots Indianapolis Colts Cincinnati Bengals Los Angeles Raiders New York Giants Washington Redskins Atlanta Falcons Tampa Bay Buccaneers Detroit Lions Minnesota Vikings Pittsburgh Steelers San Diego Chargers Phoenix Cardinals San Francisco 49ers New Orleans Saints New York Jets…
1993
Phoenix Cardinals New York Giants Miami Dolphins Philadelphia Eagles Green Bay Packers Detroit Lions New England Patriots Cleveland Browns New Orleans Saints Los Angeles Rams Chicago Bears Kansas City Chiefs Cincinnati Bengals Los Angeles Raiders Buffalo Bills Houston Oilers Pittsburgh Steelers Atlanta Falcons San Francisco 49ers Minnesota Vikings Tampa Bay Buccaneers Denver Broncos Seattle Seahawks San Diego Chargers Indianapolis Colts New York Jets Washington Redskins Dallas Cowboys Phoenix Cardinals…
1994
Chicago Bears Arizona Cardinals Houston Oilers Cincinnati Bengals Philadelphia Eagles San Francisco 49ers San Diego Chargers Denver Broncos Cleveland Browns Dallas Cowboys New York Giants Washington Redskins Los Angeles Rams Kansas City Chiefs Seattle Seahawks Pittsburgh Steelers Buffalo Bills New England Patriots Detroit Lions Green Bay Packers New York Jets Indianapolis Colts Miami Dolphins Los Angeles Raiders New Orleans Saints Atlanta Falcons Tampa Bay Buccaneers Minnesota Vikings Chicago Bears…
1995
Oakland Raiders San Diego Chargers Arizona Cardinals Seattle Seahawks New York Giants New Orleans Saints Miami Dolphins New England Patriots New York Jets Jacksonville Jaguars Cleveland Browns Kansas City Chiefs Washington Redskins Detroit Lions Tampa Bay Buccaneers Cincinnati Bengals Chicago Bears Carolina Panthers Atlanta Falcons St. Louis Rams Green Bay Packers Minnesota Vikings Pittsburgh Steelers Houston Oilers Buffalo Bills Indianapolis Colts San Francisco 49ers Dallas Cowboys Philadelphia Eagles Denver Broncos Oakland Raiders…
1996
St. Louis Rams Cincinnati Bengals Atlanta Falcons Carolina Panthers Houston Oilers Baltimore Ravens Pittsburgh Steelers Jacksonville Jaguars Seattle Seahawks Buffalo Bills Philadelphia Eagles Dallas Cowboys Miami Dolphins New England Patriots New York Giants Detroit Lions Tampa Bay Buccaneers Oakland Raiders New York Jets Arizona Cardinals New Orleans Saints Chicago Bears San Diego Chargers Indianapolis Colts Kansas City Chiefs Denver Broncos Minnesota Vikings Green Bay Packers San Francisco 49ers Washington Redskins St. Louis Rams…
1997
Oakland Raiders San Diego Chargers Baltimore Ravens Seattle Seahawks Indianapolis Colts Green Bay Packers Miami Dolphins Buffalo Bills New York Jets Cincinnati Bengals Tennessee Oilers Washington Redskins Chicago Bears St. Louis Rams New York Giants Detroit Lions Atlanta Falcons New Orleans Saints Carolina Panthers Dallas Cowboys Arizona Cardinals Philadelphia Eagles Pittsburgh Steelers Denver Broncos Kansas City Chiefs San Francisco 49ers Minnesota Vikings Tampa Bay Buccaneers New England Patriots Jacksonville Jaguars Oakland Raiders…
1998
New York Jets Atlanta Falcons San Francisco 49ers New York Giants Denver Broncos Jacksonville Jaguars Miami Dolphins Oakland Raiders Arizona Cardinals New Orleans Saints Carolina Panthers Indianapolis Colts Cincinnati Bengals Pittsburgh Steelers Green Bay Packers Chicago Bears Tennessee Oilers Baltimore Ravens Detroit Lions Tampa Bay Buccaneers Minnesota Vikings Dallas Cowboys Seattle Seahawks Washington Redskins San Diego Chargers Buffalo Bills New England Patriots Kansas City Chiefs Philadelphia Eagles St. Louis Rams New York Jets…
1999
New York Jets Denver Broncos Detroit Lions St. Louis Rams Atlanta Falcons San Francisco 49ers Tennessee Titans Jacksonville Jaguars Cincinnati Bengals Pittsburgh Steelers Baltimore Ravens Cleveland Browns New Orleans Saints Carolina Panthers Green Bay Packers San Diego Chargers Oakland Raiders Minnesota Vikings Tampa Bay Buccaneers Seattle Seahawks Chicago Bears Kansas City Chiefs New England Patriots Arizona Cardinals Dallas Cowboys Miami Dolphins Indianapolis Colts Buffalo Bills Philadelphia Eagles Washington Redskins New York Giants New York Jets…
2000
Indianapolis Colts Jacksonville Jaguars Pittsburgh Steelers Baltimore Ravens San Diego Chargers Kansas City Chiefs Carolina Panthers Green Bay Packers Minnesota Vikings Detroit Lions Chicago Bears Tampa Bay Buccaneers Miami Dolphins Cincinnati Bengals Denver Broncos New Orleans Saints Arizona Cardinals Cleveland Browns New England Patriots Buffalo Bills Tennessee Titans New York Giants Philadelphia Eagles Atlanta Falcons San Francisco 49ers Dallas Cowboys Washington Redskins St. Louis Rams Seattle Seahawks Oakland Raiders New York Jets Indianapolis Colts…
2001
Minnesota Vikings Tampa Bay Buccaneers Baltimore Ravens Denver Broncos Seattle Seahawks Oakland Raiders Indianapolis Colts New York Jets New England Patriots Miami Dolphins Atlanta Falcons New Orleans Saints St. Louis Rams San Francisco 49ers Buffalo Bills Jacksonville Jaguars Cleveland Browns Detroit Lions Dallas Cowboys New York Giants Kansas City Chiefs San Diego Chargers Cincinnati Bengals Pittsburgh Steelers Tennessee Titans Green Bay Packers Chicago Bears Arizona Cardinals Philadelphia Eagles Washington Redskins Carolina Panthers Minnesota Vikings…
2002
Oakland Raiders Arizona Cardinals Seattle Seahawks Kansas City Chiefs Miami Dolphins Baltimore Ravens Denver Broncos New England Patriots Detroit Lions New Orleans Saints Chicago Bears Minnesota Vikings Green Bay Packers Carolina Panthers Cleveland Browns Cincinnati Bengals Houston Texans Jacksonville Jaguars New York Jets Buffalo Bills San Diego Chargers San Francisco 49ers Washington Redskins Tennessee Titans Pittsburgh Steelers Tampa Bay Buccaneers Atlanta Falcons New York Giants Indianapolis Colts Philadelphia Eagles Dallas Cowboys St. Louis Rams Oakland Raiders…
2003
Chicago Bears Denver Broncos Oakland Raiders San Diego Chargers Cleveland Browns Arizona Cardinals Cincinnati Bengals Houston Texans Buffalo Bills New England Patriots Indianapolis Colts Miami Dolphins Dallas Cowboys Detroit Lions St. Louis Rams Green Bay Packers Minnesota Vikings Kansas City Chiefs Pittsburgh Steelers Baltimore Ravens Jacksonville Jaguars Tampa Bay Buccaneers Philadelphia Eagles Atlanta Falcons Carolina Panthers New York Giants New York Jets Tennessee Titans New Orleans Saints Washington Redskins Seattle Seahawks San Francisco 49ers Chicago Bears…
2004
Pittsburgh Steelers New England Patriots Indianapolis Colts Detroit Lions Chicago Bears San Francisco 49ers Arizona Cardinals New Orleans Saints Oakland Raiders Buffalo Bills Cleveland Browns Washington Redskins Tampa Bay Buccaneers Atlanta Falcons New York Giants Minnesota Vikings Tennessee Titans Cincinnati Bengals Philadelphia Eagles Green Bay Packers Dallas Cowboys Seattle Seahawks Miami Dolphins St. Louis Rams New York Jets Houston Texans Jacksonville Jaguars Denver Broncos San Diego Chargers Carolina Panthers Kansas City Chiefs Baltimore Ravens Pittsburgh Steelers…
2005
New England Patriots Buffalo Bills Kansas City Chiefs San Diego Chargers Indianapolis Colts Cincinnati Bengals Chicago Bears Baltimore Ravens Pittsburgh Steelers Tennessee Titans Houston Texans Arizona Cardinals St. Louis Rams Dallas Cowboys Philadelphia Eagles Green Bay Packers Detroit Lions New Orleans Saints Carolina Panthers New York Jets Oakland Raiders Washington Redskins Seattle Seahawks New York Giants Denver Broncos Jacksonville Jaguars San Francisco 49ers Tampa Bay Buccaneers Atlanta Falcons Minnesota Vikings Cleveland Browns Miami Dolphins New England Patriots…
2006
St. Louis Rams Green Bay Packers Chicago Bears San Francisco 49ers Seattle Seahawks Denver Broncos Pittsburgh Steelers Kansas City Chiefs San Diego Chargers Cincinnati Bengals Baltimore Ravens Atlanta Falcons Washington Redskins Jacksonville Jaguars Tennessee Titans Indianapolis Colts New England Patriots Miami Dolphins Detroit Lions Buffalo Bills Minnesota Vikings Carolina Panthers New Orleans Saints Dallas Cowboys New York Giants Tampa Bay Buccaneers Philadelphia Eagles Houston Texans Cleveland Browns New York Jets Oakland Raiders Arizona Cardinals St. Louis Rams…
2009
Philadelphia Eagles Chicago Bears Minnesota Vikings Cincinnati Bengals Green Bay Packers St. Louis Rams Detroit Lions Cleveland Browns Jacksonville Jaguars New York Jets Houston Texans New England Patriots Tennessee Titans Buffalo Bills Indianapolis Colts Baltimore Ravens Kansas City Chiefs Pittsburgh Steelers Miami Dolphins Carolina Panthers New Orleans Saints Atlanta Falcons Tampa Bay Buccaneers Seattle Seahawks San Francisco 49ers Arizona Cardinals New York Giants Dallas Cowboys Washington Redskins Oakland Raiders Denver Broncos San Diego Chargers Philadelphia Eagles…
2010
Denver Broncos Kansas City Chiefs Buffalo Bills Miami Dolphins Cincinnati Bengals Baltimore Ravens New York Jets Pittsburgh Steelers Carolina Panthers San Francisco 49ers Arizona Cardinals New Orleans Saints Atlanta Falcons Tampa Bay Buccaneers Cleveland Browns New England Patriots Minnesota Vikings Detroit Lions St. Louis Rams San Diego Chargers Tennessee Titans Dallas Cowboys Indianapolis Colts Washington Redskins Green Bay Packers New York Giants Houston Texans Oakland Raiders Seattle Seahawks Chicago Bears Philadelphia Eagles Jacksonville Jaguars Denver Broncos…
2011
Philadelphia Eagles Dallas Cowboys San Francisco 49ers Pittsburgh Steelers New England Patriots San Diego Chargers Buffalo Bills Denver Broncos Kansas City Chiefs Green Bay Packers Atlanta Falcons Indianapolis Colts Tennessee Titans Houston Texans Cincinnati Bengals Seattle Seahawks St. Louis Rams New Orleans Saints Carolina Panthers Washington Redskins New York Giants New York Jets Jacksonville Jaguars Baltimore Ravens Cleveland Browns Miami Dolphins Oakland Raiders Chicago Bears Detroit Lions Tampa Bay Buccaneers Minnesota Vikings Arizona Cardinals Philadelphia Eagles…
2012
New York Giants Green Bay Packers Houston Texans Chicago Bears Detroit Lions Seattle Seahawks Buffalo Bills New York Jets Miami Dolphins Oakland Raiders Kansas City Chiefs New Orleans Saints Dallas Cowboys Carolina Panthers Atlanta Falcons Arizona Cardinals Philadelphia Eagles Baltimore Ravens Cleveland Browns Pittsburgh Steelers Washington Redskins Tampa Bay Buccaneers San Diego Chargers Tennessee Titans Jacksonville Jaguars Indianapolis Colts Minnesota Vikings St. Louis Rams San Francisco 49ers New England Patriots Denver Broncos Cincinnati Bengals New York Giants…
2013
Washington Redskins San Diego Chargers Indianapolis Colts Denver Broncos Kansas City Chiefs Dallas Cowboys Oakland Raiders Houston Texans Tennessee Titans New York Jets New Orleans Saints Carolina Panthers San Francisco 49ers Seattle Seahawks Jacksonville Jaguars Cleveland Browns Buffalo Bills Miami Dolphins Cincinnati Bengals New England Patriots Pittsburgh Steelers Baltimore Ravens Minnesota Vikings Philadelphia Eagles Chicago Bears New York Giants Green Bay Packers Atlanta Falcons St. Louis Rams Arizona Cardinals Tampa Bay Buccaneers Detroit Lions Washington Redskins…
2014
Oakland Raiders Buffalo Bills New England Patriots Denver Broncos Miami Dolphins Jacksonville Jaguars Cleveland Browns New Orleans Saints Carolina Panthers Detroit Lions Minnesota Vikings Tampa Bay Buccaneers Pittsburgh Steelers Cincinnati Bengals Tennessee Titans Kansas City Chiefs St. Louis Rams San Francisco 49ers New York Giants Washington Redskins Philadelphia Eagles Dallas Cowboys Indianapolis Colts Houston Texans Baltimore Ravens Atlanta Falcons Arizona Cardinals San Diego Chargers Seattle Seahawks Green Bay Packers Chicago Bears New York Jets Oakland Raiders…
2015
New Orleans Saints Indianapolis Colts Denver Broncos Oakland Raiders San Diego Chargers Miami Dolphins Washington Redskins Tampa Bay Buccaneers Dallas Cowboys Philadelphia Eagles New England Patriots Houston Texans Cincinnati Bengals Seattle Seahawks Chicago Bears Kansas City Chiefs Buffalo Bills New York Jets Cleveland Browns Baltimore Ravens Pittsburgh Steelers St. Louis Rams Arizona Cardinals Detroit Lions Green Bay Packers Minnesota Vikings New York Giants San Francisco 49ers Atlanta Falcons Carolina Panthers Jacksonville Jaguars Tennessee Titans New Orleans Saints…
2016
Oakland Raiders New Orleans Saints Arizona Cardinals Seattle Seahawks Miami Dolphins Pittsburgh Steelers Baltimore Ravens Cleveland Browns San Diego Chargers Denver Broncos Jacksonville Jaguars Chicago Bears San Francisco 49ers Los Angeles Rams Tampa Bay Buccaneers Kansas City Chiefs Carolina Panthers Washington Redskins Green Bay Packers New York Giants Dallas Cowboys Cincinnati Bengals New York Jets Buffalo Bills New England Patriots Houston Texans Indianapolis Colts Minnesota Vikings Tennessee Titans Detroit Lions Philadelphia Eagles Atlanta Falcons Oakland Raiders…
2018
Pittsburgh Steelers Cleveland Browns Baltimore Ravens Buffalo Bills Detroit Lions Carolina Panthers Dallas Cowboys Jacksonville Jaguars Miami Dolphins Tennessee Titans New England Patriots Chicago Bears Green Bay Packers New York Jets Indianapolis Colts Oakland Raiders Arizona Cardinals San Francisco 49ers Denver Broncos Cincinnati Bengals Atlanta Falcons New York Giants Houston Texans Washington Redskins Tampa Bay Buccaneers New Orleans Saints Minnesota Vikings Philadelphia Eagles Los Angeles Rams Los Angeles Chargers Seattle Seahawks Kansas City Chiefs Pittsburgh Steelers…
2019
Washington Redskins Detroit Lions Philadelphia Eagles Buffalo Bills Denver Broncos Houston Texans Tennessee Titans Jacksonville Jaguars Oakland Raiders Cincinnati Bengals Cleveland Browns Baltimore Ravens San Francisco 49ers Pittsburgh Steelers Los Angeles Chargers Green Bay Packers Chicago Bears Minnesota Vikings Atlanta Falcons New Orleans Saints Indianapolis Colts Kansas City Chiefs New England Patriots Dallas Cowboys Los Angeles Rams Seattle Seahawks Carolina Panthers Tampa Bay Buccaneers Arizona Cardinals New York Giants Miami Dolphins New York Jets Washington Redskins…
2020
Buffalo Bills New York Jets Cleveland Browns Tennessee Titans Baltimore Ravens Washington Football Team Cincinnati Bengals Pittsburgh Steelers Dallas Cowboys Minnesota Vikings Green Bay Packers New Orleans Saints Chicago Bears Tampa Bay Buccaneers Detroit Lions Atlanta Falcons Carolina Panthers Los Angeles Chargers Kansas City Chiefs Houston Texans Jacksonville Jaguars Indianapolis Colts Las Vegas Raiders Denver Broncos New England Patriots Miami Dolphins Los Angeles Rams New York Giants Seattle Seahawks Philadelphia Eagles San Francisco 49ers Arizona Cardinals Buffalo Bills…
2021
Pittsburgh Steelers Cleveland Browns Detroit Lions Arizona Cardinals Seattle Seahawks Indianapolis Colts Buffalo Bills Carolina Panthers Atlanta Falcons New Orleans Saints Tampa Bay Buccaneers Chicago Bears Cincinnati Bengals Jacksonville Jaguars Miami Dolphins New England Patriots Los Angeles Chargers Las Vegas Raiders Baltimore Ravens Kansas City Chiefs Denver Broncos Dallas Cowboys Washington Football Team New York Giants Philadelphia Eagles New York Jets Houston Texans Tennessee Titans San Francisco 49ers Los Angeles Rams Minnesota Vikings Green Bay Packers Pittsburgh Steelers…
2022
Philadelphia Eagles Detroit Lions Minnesota Vikings New York Giants Green Bay Packers New England Patriots New York Jets Chicago Bears San Francisco 49ers Arizona Cardinals Carolina Panthers New Orleans Saints Cleveland Browns Tampa Bay Buccaneers Dallas Cowboys Cincinnati Bengals Kansas City Chiefs Jacksonville Jaguars Baltimore Ravens Atlanta Falcons Seattle Seahawks Los Angeles Rams Denver Broncos Los Angeles Chargers Miami Dolphins Buffalo Bills Pittsburgh Steelers Indianapolis Colts Las Vegas Raiders Houston Texans Tennessee Titans Washington Commanders Philadelphia Eagles…
2023
New York Jets Philadelphia Eagles Dallas Cowboys Los Angeles Rams Arizona Cardinals Pittsburgh Steelers Tennessee Titans Miami Dolphins New England Patriots Denver Broncos Cleveland Browns Baltimore Ravens Seattle Seahawks Detroit Lions Los Angeles Chargers Minnesota Vikings Green Bay Packers Kansas City Chiefs Cincinnati Bengals San Francisco 49ers Tampa Bay Buccaneers Chicago Bears Las Vegas Raiders New York Giants Washington Commanders Atlanta Falcons New Orleans Saints Indianapolis Colts Carolina Panthers Houston Texans Jacksonville Jaguars Buffalo Bills New York Jets…
Rust Code
If someone who is smarter than me gets this to work with 32 teams in a reasonable amount of time please let me know and I will link your solution here.
use ahash::AHashSet;
use csv::Reader;
use indicatif::ProgressBar;
use serde::Deserialize;
use std::{
collections::{HashMap, HashSet},
fs::File,
vec,
};
#[derive(Deserialize, Debug)]
struct GameRecord {
pub schedule_date: String,
pub schedule_season: u64,
pub schedule_week: String,
pub schedule_playoff: String,
pub team_home: String,
pub score_home: Option<u16>,
pub score_away: Option<u16>,
pub team_away: String,
}
fn cycle_solver(adj_matrix: Vec<Vec<bool>>, n: usize) -> bool {
let mut adj_map: Vec<Vec<usize>> = vec![Vec::new(); n];
for (idx, row) in adj_matrix.iter().enumerate() {
adj_map[idx] = row
.iter()
.enumerate()
.filter(|(_, val)| **val)
.map(|(col, _)| col)
.collect::<Vec<usize>>()
}
let mut dp: Vec<AHashSet<u64>> = vec![AHashSet::with_capacity(100); n];
dp.iter_mut().enumerate().take(n).for_each(|(idx, map)| {
map.insert(1 << idx);
});
let bar = ProgressBar::new(1 << n);
// begin loop of every potential subset of n vertices <-- very slow!
for combination in 0u64..(1 << n) {
bar.inc(1);
unsafe {
for (idx, neighbors) in adj_map
.iter()
.enumerate()
.filter(|(idx, _)| combination >> idx & 1 == 1)
{
for v in neighbors {
if combination >> v & 1 == 1
&& dp.get_unchecked(*v).contains(&(combination ^ (1 << idx)))
{
dp.get_unchecked_mut(idx).insert(combination);
break;
}
}
}
}
}
bar.finish();
dp.iter()
.enumerate()
.any(|(idx, set)| set.contains(&((1 << n) - 1)) && adj_matrix[idx][0])
}
fn main() {
let csv_file = File::open("./src/spreadspoke_scores.csv").unwrap();
let mut rdr = Reader::from_reader(csv_file);
let hdr = rdr.headers().unwrap().clone();
// get all records, filter up to 2023, only regular season games
let games: Vec<GameRecord> = rdr
.records()
.map(|r| r.unwrap().deserialize(Some(&hdr)).unwrap())
.filter(|row: &GameRecord| {
row.schedule_season < 2024
&& row.schedule_playoff == "FALSE"
&& row.schedule_season > 2013
})
.collect::<Vec<GameRecord>>();
let mut years: Vec<u64> = Vec::from_iter(
games
.iter()
.map(|r: &GameRecord| r.schedule_season)
.collect::<HashSet<u64>>(),
);
years.sort();
// go through year by year
for year in &years {
// get all reg. season games for that year
let year_games = games
.iter()
.filter(|r| r.schedule_season == *year)
.collect::<Vec<&GameRecord>>();
// get team -> idx mapping
let teams = Vec::from_iter(
year_games
.iter()
.flat_map(|r| vec![r.team_home.clone(), r.team_away.clone()])
.collect::<HashSet<String>>(),
);
let team_idx: HashMap<String, usize> = teams
.iter()
.enumerate()
.map(|(idx, team)| (team.clone(), idx))
.collect();
// check if there was a completed circle of parity
// construct adj matrix, where adj[i][j] is true if and only if team i beat team j
let n = teams.len();
let mut season_adj_matrix: Vec<Vec<bool>> = vec![vec![false; n]; n];
for game in &year_games {
if game.score_home > game.score_away {
season_adj_matrix[*team_idx.get(&game.team_home).unwrap()]
[*team_idx.get(&game.team_away).unwrap()] = true;
} else if game.score_away > game.score_home {
season_adj_matrix[*team_idx.get(&game.team_away).unwrap()]
[*team_idx.get(&game.team_home).unwrap()] = true;
}
}
let had_cycle = cycle_solver(season_adj_matrix, teams.len());
println!("{}: {}", year, had_cycle);
}
}