Skip to content

Instantly share code, notes, and snippets.

@Debilski

Debilski/Tournament_knockout_bonus.ipynb

Created August 19, 2015 22:13
Show Gist options
  • Save Debilski/a978a42cfb4060be5c42 to your computer and use it in GitHub Desktop.
Save Debilski/a978a42cfb4060be5c42 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
Tournament_knockout_bonus.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"\n",
"from collections import namedtuple\n",
"import math\n",
"\n",
"import numpy as np\n",
"\n",
"def show_team(team, *, prefix=None, postfix=None, size=None, padLeft=\"\", padRight=\"\", fillElem=\"─\"):\n",
" if prefix is None:\n",
" prefix = \"\"\n",
" if postfix is None:\n",
" postfix = \"\"\n",
"\n",
" if size is None:\n",
" size = 0\n",
" else:\n",
" size = size - len(prefix) - len(postfix)\n",
" padded = \"{padLeft}{team}{padRight}\".format(team=team, padLeft=padLeft, padRight=padRight)\n",
" return \"{prefix}{team:{fillElem}<{size}}{postfix}\".format(team=padded, prefix=prefix, postfix=postfix, size=size, fillElem=fillElem)\n",
"\n",
"class MatrixElem:\n",
" def size(self):\n",
" return len(self.to_s())\n",
"\n",
"class Team(namedtuple(\"Team\", [\"name\"]), MatrixElem):\n",
" def to_s(self, size=None):\n",
" return show_team(self.name, size=size, padLeft=\" \", padRight=\" \")\n",
"\n",
"class Bye(namedtuple(\"Bye\", [\"team\"]), MatrixElem):\n",
" def to_s(self, size=None):\n",
" prefix = \"──\"\n",
" return show_team(\"…\", prefix=prefix, padLeft=\" \", padRight=\" \", size=size)\n",
"\n",
"class Match(namedtuple(\"Match\", [\"t1\", \"t2\", \"winner\"]), MatrixElem):\n",
" def to_s(self, size=None):\n",
" prefix = \"├─\"\n",
" name = self.winner if self.winner else \"unknown\"\n",
" return show_team(name, prefix=prefix, padLeft=\" \", padRight=\" \", size=size)\n",
"\n",
"class FinalMatch(namedtuple(\"FinalMatch\", [\"t1\", \"t2\", \"winner\"]), MatrixElem):\n",
" def to_s(self, size=None):\n",
" prefix = \"├──┨\"\n",
" postfix = \"┃\"\n",
" fillElem = \" \"\n",
" name = self.winner if self.winner else \"unknown\"\n",
" return show_team(name, prefix=prefix, postfix=postfix, padLeft=\" \", padRight=\" \", fillElem=fillElem, size=size)\n",
"\n",
"class Element(namedtuple(\"Element\", [\"char\"]), MatrixElem):\n",
" def to_s(self, size=None):\n",
" return show_team(self.char, size=size, fillElem=\" \")\n",
"\n",
"class Empty(namedtuple(\"Empty\", []), MatrixElem):\n",
" def to_s(self, size=None):\n",
" return show_team(\" \", size=size, fillElem=\" \")\n",
"\n",
"class BorderTop(namedtuple(\"BorderTop\", [\"team\", \"tight\"]), MatrixElem):\n",
" def to_s(self, size=None):\n",
" prefix = \"│ \" if not self.tight else \"┐ \"\n",
" padRight = \"\"\n",
" padLeft = \"┏\"\n",
" postfix = \"┓\"\n",
" fillElem = \"━\"\n",
" return show_team(\"\", prefix=prefix, postfix=postfix, padLeft=padLeft, padRight=padRight, fillElem=fillElem, size=size)\n",
"\n",
"class BorderBottom(namedtuple(\"BorderBottom\", [\"team\", \"tight\"]), MatrixElem):\n",
" def to_s(self, size=None):\n",
" prefix = \"│ \" if not self.tight else \"┘ \"\n",
" padRight = \"\"\n",
" padLeft = \"┗\"\n",
" postfix = \"┛\"\n",
" fillElem = \"━\"\n",
" return show_team(\"\", prefix=prefix, postfix=postfix, padLeft=padLeft, padRight=padRight, fillElem=fillElem, size=size)\n",
"\n",
"\n",
"def knockout_matrix(*teams):\n",
" \"\"\"\n",
" For now teams is a list (cols) of list (rows) of teams\n",
" \"\"\"\n",
"\n",
" initial_teams = teams[0]\n",
" N = len(initial_teams)\n",
" height = N * 2 - 1\n",
" width = math.ceil(math.log(N, 2)) + 1\n",
" matrix = np.empty([height, width], dtype=np.object_)\n",
"\n",
" matrix.fill(Empty())\n",
"\n",
" matrix[::2, 0] = [Team(t) for t in initial_teams]\n",
"\n",
" for col in range(1, width):\n",
" start = None\n",
" end = None\n",
" last_match = None\n",
" rowIdx = 0\n",
" for row in range(height):\n",
" left_elem = matrix[row, col - 1]\n",
" if isinstance(left_elem, Team) or isinstance(left_elem, Match) or isinstance(left_elem, Bye):\n",
" # left of us is a team\n",
" if start is None:\n",
" start = row\n",
" else:\n",
" end = row\n",
" middle = math.floor(start + (end - start) / 2)\n",
" t1 = matrix[start, col - 1]\n",
" t2 = matrix[end, col - 1]\n",
" match = Match(t1=t1, t2=t2, winner=teams[col][rowIdx])\n",
" rowIdx += 1\n",
" matrix[start:end, col].fill(Element('│'))\n",
" matrix[start, col] = Element('┐')\n",
" matrix[end, col] = Element('┘')\n",
" matrix[middle, col] = match\n",
" last_match = (middle, col)\n",
" start = end = None\n",
" else:\n",
" if start is not None:\n",
" team = matrix[start, col - 1]\n",
" matrix[start, col] = Bye(team=team)\n",
" last_match = (start, col)\n",
"\n",
" # Decorate the winner column\n",
" isMatch = np.vectorize(lambda elem: not isinstance(elem, Empty))\n",
"\n",
" return matrix, last_match\n",
"\n",
"def print_knockout(*teams, bonusmatch=False):\n",
" if bonusmatch:\n",
" bonus_team = teams[0][-1]\n",
" bonus_final = teams[-1][0]\n",
"\n",
" teams = [t[:] for t in teams]\n",
" del teams[0][-1]\n",
" del teams[-1]\n",
" matrix, final_match = knockout_matrix(*teams)\n",
" winner_row = final_match[0]\n",
"\n",
" enlarged_height = matrix.shape[0] + 2\n",
" enlarged_width = matrix.shape[1] + 1\n",
" enlarged_matrix = np.empty([enlarged_height, enlarged_width], dtype=np.object_)\n",
" enlarged_matrix.fill(Empty())\n",
" for row in range(matrix.shape[0]):\n",
" for col in range(0, matrix.shape[1]):\n",
" enlarged_matrix[row, col] = matrix[row, col]\n",
" matrix = enlarged_matrix\n",
"\n",
" matrix[-1, 0] = Team(bonus_team)\n",
" matrix[-1, 1:-1].fill(Bye(team=matrix[-1, 0]))\n",
"\n",
" col = -1\n",
" start = winner_row\n",
" end = matrix.shape[0] - 1\n",
" middle = math.floor(start + (end - start) / 2)\n",
"\n",
" matrix[start:end, col].fill(Element('│'))\n",
" matrix[start, col] = Element('┐')\n",
" matrix[end, col] = Element('┘')\n",
" matrix[middle, col] = Match(\".\", \".\", bonus_team)\n",
"\n",
" final_match = (middle, col)\n",
" else:\n",
" matrix, final_match = knockout_matrix(*teams)\n",
"\n",
" winner_row = final_match[0]\n",
" winner = matrix[final_match] = FinalMatch(* matrix[final_match])\n",
"\n",
" def is_tight(elem):\n",
" return not isinstance(elem, Empty) and not isinstance(elem, Element)\n",
"\n",
" matrix[winner_row - 1, -1] = BorderTop(winner, is_tight(matrix[winner_row - 1, -2]))\n",
" matrix[winner_row + 1, -1] = BorderBottom(winner, is_tight(matrix[winner_row + 1, -2]))\n",
"\n",
" maxsize = max(elem.size() for elem in matrix.flatten())\n",
"\n",
" for row in range(matrix.shape[0]):\n",
" for col in range(0, matrix.shape[1]):\n",
" try:\n",
" print(matrix[row, col].to_s(maxsize), end=\"\")\n",
" except AttributeError:\n",
" print(\"Here:\", end=\"\")\n",
" print(row, col, matrix[row, col])\n",
" raise\n",
" print()\n"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" a ─────┐ \n",
" ├─ b ───┐ \n",
" b ─────┘ ├─ c ───┐ \n",
" │ │ ┏━━━┓\n",
" c ─────── … ───┘ ├──┨ d ┃\n",
" │ ┗━━━┛\n",
" d ─────── … ───── … ───┘ \n"
]
}
],
"source": [
"print_knockout([\"a\", \"b\", \"c\", \"d\"], [\"b\"], [\"c\"], [\"d\"], bonusmatch=True)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" a ─────┐ \n",
" ├─ b ───┐ \n",
" b ─────┘ │ \n",
" ├─ d ───┐ \n",
" c ─────┐ │ │ \n",
" ├─ d ───┘ ├─ d ───┐ \n",
" d ─────┘ │ │ ┏━━━┓\n",
" │ ├──┨ f ┃\n",
" e ─────── … ───── … ───┘ │ ┗━━━┛\n",
" │ \n",
" f ─────── … ───── … ───── … ───┘ \n"
]
}
],
"source": [
"print_knockout([\"a\", \"b\", \"c\", \"d\", \"e\", \"f\"], [\"b\", \"d\"], [\"d\", \"e\"], [\"d\"], [\"f\"], bonusmatch=True)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" a ──────┐ \n",
" ├─ b ────┐ \n",
" b ──────┘ │ \n",
" ├─ b ────┐ \n",
" c ──────┐ │ │ \n",
" ├─ d ────┘ │ \n",
" d ──────┘ ├─ se7en ┐ \n",
" │ │ \n",
" eeeee ──┐ │ │ \n",
" ├─ eeeee ┐ │ │ ┏━━━━┓\n",
" Team 6 ─┘ ├─ se7en ┘ ├──┨ 8 ┃\n",
" │ │ ┗━━━━┛\n",
" se7en ──── … ────┘ │ \n",
" │ \n",
" 8 ──────── … ────── … ────── … ────┘ \n"
]
}
],
"source": [
"print_knockout([\"a\", \"b\", \"c\", \"d\", \"eeeee\", \"Team 6\", \"se7en\", \"8\"], [\"b\", \"d\", \"eeeee\"], [\"b\", \"se7en\"], [\"se7en\"], [\"se7en\"], bonusmatch=True)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.4.3"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment