// Numbas version: exam_results_page_options
{"name": "Hungarian algorithm", "extensions": ["optimisation"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"variable_groups": [{"variables": ["worker", "job", "workers", "jobs"], "name": "Text"}, {"variables": ["num_workers", "num_jobs", "costs"], "name": "Setup"}, {"variables": ["solution", "total_cost"], "name": "Solution"}], "variables": {"solution": {"templateType": "anything", "group": "Solution", "definition": "hungarian(costs)", "description": "", "name": "solution"}, "costs": {"templateType": "anything", "group": "Setup", "definition": "matrix(\n  repeat(\n    repeat(\n      random(1..9),\n      num_jobs\n    ),\n    num_workers\n  )\n)", "description": "", "name": "costs"}, "job": {"templateType": "string", "group": "Text", "definition": "safe(\"school\")", "description": "", "name": "job"}, "num_jobs": {"templateType": "anything", "group": "Setup", "definition": "num_workers", "description": "", "name": "num_jobs"}, "worker": {"templateType": "string", "group": "Text", "definition": "safe(\"inspector\")", "description": "", "name": "worker"}, "jobs": {"templateType": "string", "group": "Text", "definition": "safe(\"schools\")", "description": "", "name": "jobs"}, "workers": {"templateType": "string", "group": "Text", "definition": "safe(\"school inspectors\")", "description": "", "name": "workers"}, "total_cost": {"templateType": "anything", "group": "Solution", "definition": "sum(map(\n  let(x,p[0],y,p[1],\n    costs[x][y]*solution[x][y]\n  ),\n  p,\n  product(list(0..num_workers-1),list(0..num_jobs-1))\n))", "description": "", "name": "total_cost"}, "num_workers": {"templateType": "anything", "group": "Setup", "definition": "5//random(3..5)", "description": "", "name": "num_workers"}}, "ungrouped_variables": [], "name": "Hungarian algorithm", "functions": {"calculate_cost": {"type": "string", "language": "javascript", "definition": "var o = [];\nfor(var i=0;i<costs.rows;i++) {\n  for(var j=0;j<costs.columns;j++) {\n    if(solution[i][j]) {\n      o.push(costs[i][j]);\n    }\n  }\n}\nvar s = new Numbas.jme.types.TString(o.join(' + '));\ns.latex = true;\nreturn s;", "parameters": [["costs", "matrix"], ["solution", "matrix"]]}}, "parts": [{"displayType": "radiogroup", "showCellAnswerState": false, "useCustomName": false, "prompt": "<p>Find an assignment of {workers} to {jobs} which minimises the total distance travelled.</p>", "minAnswers": 0, "maxAnswers": 0, "shuffleChoices": false, "warningType": "none", "showCorrectAnswer": true, "type": "m_n_x", "minMarks": 0, "shuffleAnswers": false, "variableReplacements": [], "layout": {"type": "all", "expression": ""}, "choices": ["{capitalise(worker)} 1", "{capitalise(worker)} 2", "{capitalise(worker)} 3", "{capitalise(worker)} 4", "{capitalise(worker)} 5"], "extendBaseMarkingAlgorithm": true, "matrix": "solution", "customMarkingAlgorithm": "student_cost:\n  sum(map(if(studentAnswer[x][y],costs[y][x],0),[x,y],tick_indexes))\n\noptimal_cost:\n  correctif(student_cost<=total_cost)\n\nanyone_unassigned:\n  assert(all(map(some(studentAnswer[row]),row,0..numAnswers-1)),\n    warn(\"You have not assigned an inspector to every school.\");\n    fail(\"You have not assigned an inspector to every school.\");\n    true\n  )\n\nschools_unassigned:\n  assert(all(map(some(map(studentAnswer[row][col],row,0..numAnswers-1)),col,0..numChoices-1)),\n    warn(\"You have not assigned every inspector to a school.\");\n    fail(\"You have not assigned every inspector to a school.\");\n    true\n  )\n\nmark:\n  assert(marks>0,correct());  // any answer is correct when 0 marks are available\n  assert(numTicks>0,\n    warn(translate(\"part.marking.nothing entered\"));\n    fail(translate(\"part.marking.nothing entered\"))\n  );\n  apply(anyone_unassigned);\n  apply(schools_unassigned);\n  apply(optimal_cost)", "customName": "", "unitTests": [], "answers": ["{capitalise(job)} 1", "{capitalise(job)} 2", "{capitalise(job)} 3", "{capitalise(job)} 4", "{capitalise(job)} 5"], "scripts": {}, "maxMarks": 0, "variableReplacementStrategy": "originalfirst", "marks": 0, "showFeedbackIcon": true}, {"prompt": "<p>How many miles will the {workers} have to travel, in total?</p>\n<p>[[0]] miles.</p>", "showCorrectAnswer": true, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "useCustomName": false, "customName": "", "unitTests": [], "sortAnswers": false, "scripts": {}, "gaps": [{"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "total_cost", "useCustomName": false, "customName": "", "unitTests": [], "showFractionHint": true, "correctAnswerStyle": "plain", "mustBeReducedPC": 0, "scripts": {}, "type": "numberentry", "notationStyles": ["plain", "en", "si-en"], "showFeedbackIcon": true, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1, "maxValue": "total_cost"}], "type": "gapfill", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}], "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "<p>{num_workers} {workers}&nbsp;have to decide who will attend each of {num_jobs} {jobs}&nbsp;on a particular day. The distances, in miles, that each {worker}&nbsp;would have to travel to each {job}&nbsp;are given below.</p>\n<p>{job_cost_table(costs,capitalise(worker),capitalise(job))}</p>", "tags": [], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": ""}, "extensions": ["optimisation"], "advice": "<h4>a)</h4>\n<p>Use the Hungarian algorithm to find the assignment giving the minimum total&nbsp;distance.</p>\n<p>{hungarian_display(costs)}</p>\n<h4>b)</h4>\n<p>The total distance&nbsp;is $\\var{calculate_cost(costs,solution)} = \\var{total_cost}$ miles.</p>", "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}, {"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}]}]}], "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}, {"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}]}