31:T5b8,rank_matchups = notebook({ get_matchup_v_matchup_matrix, normalize_vector, multiply_vector_with_vector, multiply_matrix_with_vector, run_generation, dedent, _ })` matchups = null dedent(md)\` Create a matrix of all the matchups pitted against eachother. It will contain 0 at the position if the matchups can't exist in the same round, 1 if it does. \` matchup_v_matchup = get_matchup_v_matchup_matrix(matchups) dedent(md)\` Get the scores that the judge function assigned to the individual matchups. We also normalize them, which puts them all between 0 and 1. Every index in any "scores" array from now on, will have their index matched in the matchups array: initial_scores[0] is a score for matchups[0], current_scores[100] is a score for matchups[100] \` generation_0 = _.sortBy(_.zip(matchups, initial_scores), ([teams, score]) => -score) initial_scores = matchups.map(x => x.score); viewof generation_1 = run_generation({ initial_scores, current_scores: initial_scores, matchup_v_matchup, }); viewof generation_2 = run_generation({ initial_scores, current_scores: generation_1.result_scores, matchup_v_matchup, }); viewof generation_3 = run_generation({ initial_scores, current_scores: generation_2.result_scores, matchup_v_matchup, }); result = [generation_1.result_generation, generation_2.result_generation, generation_3.result_generation] `32:T6cd,run_generation = notebook({ multiply_matrix_with_vector, multiply_vector_with_vector, normalize_vector, matchups })` initial_scores = null current_scores = null matchup_v_matchup = null // Mathematical matrix-vector mulitplication, // the "could be in the same round" matrix with the last scores we got for every matchup raw_scores = multiply_matrix_with_vector( matchup_v_matchup, current_scores ); // This gives us the new rank, but it misses something. I tried just the above before, but that made // all the results were strange. School were pitted against eachother, even with penalties in the 1000s. // I think that is because when we just multiply with the last scores, // the "I can co-exist with X other matchups" easily outperforms any "I am actually a good matchup" metric. // To counter that, I take the new score for every matchup, and multiply it with the initial ones we saved. with_initial_scores = multiply_vector_with_vector( raw_scores, initial_scores ); // Set and yield the new scores so we can apply those in the next generation. // The fact we keep updating the scores is the power move of this algorithm. result_scores = normalize_vector(with_initial_scores); // _.zip is really cool, it takes two arrays and "zips" them together in one new array: // _.zip([1, 2, 3, 4], ["one", "two", "three", "four"]) // = [ [1, "one"], [2, "two"], [3, "three"], [4, "four"] ] matchups_with_their_ranking_score = _.zip(matchups, result_scores); // We use the score we just zipped with the matchups to sort them, and we save the whole thing :D result_generation = _.sortBy( matchups_with_their_ranking_score, ([teams, score]) => -score ); `33:T46d,demo_teams = [ { id: 1, name: "Pantarijn #1", school: "Pantarijn", level: 5, seen: [6] }, { id: 2, name: "Pantarijn #2", school: "Pantarijn", level: 3, seen: [5] }, { id: 3, name: "Pantarijn #3", school: "Pantarijn", level: 4, seen: [10] }, { id: 12, name: "Marnix #1", school: "Marnix", level: 2, seen: [8] }, { id: 4, name: "Marnix #2", school: "Marnix", level: 1, seen: [9] }, { id: 5, name: "Streek #1", school: "Streek", level: 3, seen: [2] }, { id: 6, name: "Streek #2", school: "Streek", level: 3, seen: [1] }, { id: 7, name: "Streek #3", school: "Streek", level: 2, seen: [11, 10, 9] }, { id: 8, name: "SGN #1", school: "Stedelijk Gymnasium Nijmegen", level: 1, seen: [12] }, { id: 9, name: "SGN #2", school: "Stedelijk Gymnasium Nijmegen", level: 2, seen: [4, 7] }, { id: 10, name: "SGN #3", school: "Stedelijk Gymnasium Nijmegen", level: 4, seen: [3, 7] }, ..._.range(0, 50).map(i => { return { id: i + 10, name: `Team:${i % 5} #${i}`, school: `School:${i % 5}`, level: i % 5, seen: [] }; }) ]34:T455,judge_matchup = ({ team_in_favor, team_against }) => { let score = 0; // Same school? SHAME if (team_in_favor.school === team_against.school) { score += SAME_SCHOOL_PENALTY; // SAME_SCHOOL_PENALTY is a negative number } // Different levels? SHAME (proportional to the difference in level) // The `** 1.2` is to make a higher level difference be more-more impactful than two small differences let level_difference = Math.abs(team_in_favor.level - team_against.level); score += -( level_difference ** LEVEL_DIFFERENCE_EXPONENT * LEVEL_DIFFERENCE_MULTIPLIER ); // I'm just assuming debating in favor of a subject is harder than against, // so being higher level when in favor is favorable for now // (This makes the results a lot more stable, as it used to flicker a lot between A vs B and B vs A) // (And shows that small score changes, like 0.1 do have an effect too!) if (team_in_favor.level >= team_against.level) { score += 0.1; } // Filter out previous matches if (team_in_favor.seen.includes(team_against.id)) { score += -5; } return score; }35:T452,{ let algorithm_map = { // Thourough: `round_by_thourough_search, Naive: round_by_naive_search }; let round = algorithm_map[SELECTION_ALGORITHM]; return dedent(md)` | | In favor | Opposed | Score | Judge score | | -- | -------- | ------ | ----- | ----------- | ${round.results.map(matchup => { let index = matchups .indexOf(matchup) .toString() .padStart(3, '0'); let { team_in_favor, team_against, score, raw_score } = matchup; // prettier-ignore return md_row([ index, team_as_string(team_in_favor), team_as_string(team_against), score.toFixed(5), `

${raw_score.toFixed(2)}

` ]) })} Average score: **${_.mean(round.results.map(x => x.score)).toFixed(5)}** Use this with caution, as it is pretty tightly linked to the judge function. Meaning, if you increase the relative score for features that are present in the current round, this average will also go up slightly. `; }36:T826,{ let naive_and_thourough_are_basically_the_same = _.difference(round_by_naive_search, round_by_thourough_search).length === 0; let naive_score = _.mean(round_by_naive_search.map(x => x.score)); let thourough_score = _.mean(round_by_thourough_search.map(x => x.score)); let score_difference = Math.abs(naive_score - thourough_score); let better_algorithm = naive_score > thourough_score ? 'Naive' : 'Thourough'; let score_table = dedent()` | Algorithm | Score | | --------- | ------------------------------ | | Thourough | ${thourough_score.toFixed(10)} | | Naive | ${naive_score.toFixed(10)} | `; if (naive_and_thourough_are_basically_the_same) { return dedent(md)` The naive and thourough selection algorithms might deliver different results, but they contain the same set of matchups for the current configuration. So they are basically the same for these parameters. `; } else { if (naive_score === thourough_score) { return md` There is a difference between the naive and throurough selection algorithms results, but the total score is exactly the same. `; } if (score_difference > 0.2) { return dedent(md)` Pretty big score difference between the naive and thourough selection algorithms. ${better_algorithm} got a score that is ${score_difference.toFixed(2)} better! ${score_table} `; } if (score_difference > 0.1) { return dedent(md)` Significant score difference between the selection algorithms, but it is not too big either. ${better_algorithm} got a score that is ${score_difference.toFixed(4)} better. ${score_table} `; } return dedent(md)` Small score difference: ${score_difference.toFixed(10)} ${score_table} `; } }37:T43c,md` ## Selection algorithms I made up this term, don't @-me. The naive search takes *one ranking* and uses that to create the whole round. It goes from the top ranked matchup through the ranking to the bottom ranked matchup, and for every matchup that does not conflict with an already selected one, will put it in the round selection. Thourough is a bit more sophisticated. It will take the best matchup from the initial ranking, but then takes only the matchups that do not conflict with this matchup, and **runs the ranking again**. It will then again take the first, and repeat untill it has matched all the teams. Right now this does not make much a difference (see "Very technical options" above), but the throurough algorithm provides an example of how we could do user guided scheduling. We could show the rankings to a user, and when the user selects one they like (based on human instincts we can not automate), we run the ranking again, and show them the best options with the selected matchup in mind. I did this before actually and it worked pretty awesomely then. `38:[{"id":"dd419e75956124755da07d7ade8d4a3b1df0af140a605700719b3bcf73545af03fdb8dd04f46f8fc6dd8b371d2c9e5ca71c153ddce16cab6da511fe6c187a0ad","href":"https://static.observableusercontent.com/files/dd419e75956124755da07d7ade8d4a3b1df0af140a605700719b3bcf73545af03fdb8dd04f46f8fc6dd8b371d2c9e5ca71c153ddce16cab6da511fe6c187a0ad","name":"debat.jpg","type":"image/jpeg","lastModified":1590883590195.679,"size":47689}] 2f:{"title":"Sub-notebook example: Debate Round Scheduler / Matcher","cells":[{"id":1508,"value":"md`# Sub-notebook example: Debate Round Scheduler / Matcher`","pinned":false,"hidden":false,"mode":"ojs"},{"id":0,"value":"md`\nVersion of [@dralletje/debate-matcher](https://observablehq.com/@dralletje/debate-matcher) that uses [@dralletje/functions-are-notebooks](https://observablehq.com/@dralletje/functions-are-notebooks-with-inline-editing) to see how the notebook function works with an algorithm I actually used.\n\nIf you think _\"Wow, what's this algorithm, this page seems incomplete?!\"_, look at the original notebook 🙃, the main show here is the \\`notebook\\` function from [functions-are-notebook](https://observablehq.com/@dralletje/functions-are-notebooks-with-inline-editing)\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":329,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":1425,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":233,"value":"viewof round_by_naive_search = notebook({\n teams,\n rank_matchups,\n matchups,\n matchups_do_conflict\n})`\n eventual_matchup_count = teams.length / 2;\n\n viewof generations = rank_matchups({ matchups: matchups })\n matchups_with_scores = _.last(generations.result);\n\n results = {\n let selected_matchups = [];\n for (let matchup of matchups_with_scores.map(([teams, score]) => teams)) {\n if (selected_matchups.length >= eventual_matchup_count) {\n break;\n }\n if (selected_matchups.some(x => matchups_do_conflict(x, matchup))) {\n continue;\n }\n selected_matchups.push(matchup);\n }\n return selected_matchups;\n }\n`('round_by_naive_search')","pinned":true,"hidden":false,"mode":"ojs"},{"id":1388,"value":"import {\n notebook,\n notebook_styles\n} from \"@dralletje/functions-are-notebooks-with-inline-editing\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":1407,"value":"notebook_styles","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":23,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":582,"value":"viewof team_count = slider({\n title: \"Team count\",\n description: \"Takes the first x teams from the demo_teams array\",\n min: 2,\n max: demo_teams.length,\n step: 2,\n value: Math.min(10, demo_teams.length)\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":595,"value":"teams = demo_teams.slice(0, team_count)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1360,"value":"md`### Judge Function parameters`","pinned":false,"hidden":false,"mode":"ojs"},{"id":304,"value":"viewof SAME_SCHOOL_PENALTY = slider({\n min: -1000,\n max: 0,\n step: 10,\n value: -100,\n title: \"Same school penalty\",\n description:\n \"How much should be reduced from a matchups score if teams come from the same school\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":310,"value":"viewof LEVEL_DIFFERENCE_MULTIPLIER = slider({\n min: 0,\n max: 10,\n step: 0.1,\n value: 1,\n title: \"Level difference multiplier\",\n description: \"Use 0 to remove the effect of level difference altogether\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":964,"value":"viewof LEVEL_DIFFERENCE_EXPONENT = slider({\n min: 0,\n max: 4,\n step: 0.1,\n value: 2,\n title: \"Level difference exponent\",\n description:\n \"Where the `Level Difference Multiplier` is linear, this one punishes bigger differences exponentially more\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":140,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":857,"value":"md`### Very technical options`","pinned":false,"hidden":false,"mode":"ojs"},{"id":845,"value":"viewof MATCHUP_SELF_COUNTS = select({\n title: \"Matchup vs self works\",\n options: [\"Yes\", \"No\"],\n description: \"I have not really an idea what kind of effect this has\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":746,"value":"viewof SELECTION_ALGORITHM = select({\n title: \"Selection algorithms\",\n description: \"The algorithms that orchestrates the whole search\",\n options: [\"Thourough\", \"Naive\"],\n value: \"Naive\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":773,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":133,"value":"md`## Algorithm fluff`","pinned":false,"hidden":false,"mode":"ojs"},{"id":944,"value":"md`\n#### Matchups\nArray with every possible \\`{ team_in_favor: Team, team_against: Team }\\` combination we can make from the teams list. It also adds the scores, and normalizes these (so they make sense to compare)\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":5,"value":"matchups = {\n let matchups_with_only_raw_score = _.flatten(\n teams.map(team_in_favor => {\n return teams\n .filter(team_against => team_against !== team_in_favor)\n .map(team_against => {\n return {\n team_in_favor: team_in_favor,\n team_against: team_against,\n raw_score: judge_matchup({ team_in_favor, team_against })\n };\n });\n })\n );\n\n let normalized_scores = normalize_vector(\n matchups_with_only_raw_score.map(matchup => matchup.raw_score)\n );\n return _.zip(matchups_with_only_raw_score, normalized_scores).map(\n ([matchup, score]) => {\n return {\n ...matchup,\n score: score\n };\n }\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":954,"value":"md`\n#### Matchups do conflict\nTakes two matchups (items like we have in the \\`matchups\\` array) and checks if they share a team (thus can not co-exist in one round, as a team can only play in one matchup per round)\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":36,"value":"matchups_do_conflict = (matchup_1, matchup_2) => {\n // let isEqual = (x, y) => x === y;\n let isEqual = (team1, team2) => team1.name === team2.name;\n\n if (\n isEqual(matchup_1.team_in_favor, matchup_2.team_in_favor) ||\n isEqual(matchup_1.team_in_favor, matchup_2.team_against) ||\n isEqual(matchup_1.team_against, matchup_2.team_in_favor) ||\n isEqual(matchup_1.team_against, matchup_2.team_against)\n ) {\n return true;\n } else {\n return false;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":924,"value":"$37","pinned":false,"hidden":false,"mode":"ojs"},{"id":327,"value":"round_by_thourough_search = {\n precondition(teams.length % 2 === 0);\n\n const eventual_matchup_count = teams.length / 2;\n let selected_matchups = [];\n\n let available_matchups = matchups;\n\n for (let i of _.range(0, eventual_matchup_count)) {\n let [best_matchup, ...other_matchups] = _.last(\n rank_matchups(available_matchups, GENERATIONS)\n );\n let [matchup, score] = best_matchup;\n\n selected_matchups.push(matchup);\n available_matchups = available_matchups.filter(\n x => !matchups_do_conflict(matchup, x)\n );\n }\n\n return selected_matchups;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":830,"value":"md`\n## The actual Algorithm\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":331,"value":"get_matchup_v_matchup_matrix = matchups => {\n return matchups.map(matchup_1 => {\n return matchups.map(matchup_2 => {\n if (matchup_1 === matchup_2) {\n if (MATCHUP_SELF_COUNTS === \"Yes\") {\n return 1;\n } else {\n return 0;\n }\n }\n return matchups_do_conflict(matchup_1, matchup_2) ? 0 : 1;\n });\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":523,"value":"md`\n## Display helpers\n\nVery specific helpers to transform our data into html\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1147,"value":"long_score_as_html = (score, digits = 20) => {\n return html.fragment`${score\n .toFixed(digits)\n .split('')\n .map(\n (part, index, array) =>\n html.fragment`${part}`\n )}`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1151,"value":"team_to_html = team => {\n return html.fragment`\n \n ${md`${team_as_string(team)}`}\n \n `;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":379,"value":"color_for_team = ({ name, school, level }) => {\n let LEVEL_UPPER_BOUND = 20;\n let hue = number_from_string(school) % 360;\n let saturation = (level / LEVEL_UPPER_BOUND) * 30 + 30;\n let lightness = (level / LEVEL_UPPER_BOUND) * 40 + 30;\n return `hsl(${hue}, ${saturation}%, ${lightness}%)`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":314,"value":"team_as_string = team => {\n return `${team.name} - *lvl ${team.level}*`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":568,"value":"md_row = list => `| ${list.join(' | ')} |\\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":55,"value":"md`\n ## Appendix\n\n Collection of methods that are basically re-usable\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":480,"value":"md`\n#### Linear algebra\n\nI need some vector and matrix stuff, but I don't feel like importing a whole library for that 😅\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":65,"value":"multiply_matrix_with_vector = (matrix, vector) => {\n precondition(matrix.length === vector.length);\n\n return matrix.map(row => {\n precondition(row.length === vector.length);\n\n let result = 0;\n for (let i of _.range(row.length)) {\n result += row[i] * vector[i];\n }\n return result;\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":403,"value":"multiply_vector_with_vector = (vector1, vector2) => {\n return vector1.map((_, index) => vector1[index] * vector2[index]);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":52,"value":"normalize_vector = vector => {\n let highest = _.max(vector);\n let lowest = _.min(vector);\n let size = Math.abs(highest - lowest);\n\n return vector.map(x => (x - lowest) / size);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":483,"value":"md`\n#### Precondition\n\nChecks a \"condition\", and throws when it is false.\nI use this often when I want to make sure there is no error in my inputs or some intermediate value.\n\n~~~js\nprecondition(argument1.length < 10); // Will throw if argument1.length is bigger or equal to 10\nprecondition(list.every(x => x.type != null)); // Will throw if any item in the list does not have a type property\n~~~\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":67,"value":"precondition = (condition, message = \"Precondition failed\") => {\n if (!condition) {\n throw new Error(message);\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":784,"value":"md`\n#### Generator to array\n\nLike the above, it helps with generator functions. Now instead of taking only the last result, this gives you an array of all the results emitted along the way.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":468,"value":"md`\n#### Number from string\n\nI often want to color-code data pseudo-randomly, where the same value will always yield the same color, but similar strings don't generate similar colors. This will (try) to do just that\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":423,"value":"number_from_string = string => {\n var hash = 0;\n for (var i = 0; i < string.length; i++) {\n hash = string.charCodeAt(i) ** 2 + ((hash << 5) - hash);\n hash = hash & hash;\n }\n return hash;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":474,"value":"md`#### Imports`","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"_ = require('lodash')","pinned":false,"hidden":false,"mode":"ojs"},{"id":297,"value":"import { slider, number, select } from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":604,"value":"import { Scrubber } from \"@mbostock/scrubber\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":627,"value":"import { form } from \"@mbostock/form-input\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":637,"value":"html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":1257,"value":"import { html, svg } from \"@observablehq/htl\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":1277,"value":"import { dedent } from \"@dralletje/dedent-for-template-strings\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":1309,"value":"import { with_title } from \"@dralletje/compose-viewof\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W38","stdlib":"1","titling":"auto"}