// Numbas version: exam_results_page_options
{"name": "Isomorphisms of a binary tree", "extensions": ["eukleides", "permutations"], "custom_part_types": [{"source": {"pk": 133, "author": {"name": "Christian Lawson-Perfect", "pk": 7}, "edit_page": "/part_type/133/edit"}, "name": "Write an equivalent word", "short_name": "write-a-word-producing-a-given-permutation", "description": "<p>The student must write a word on the given generators which is equivalent to the given word.</p>\n<p>The generators are given as a dictionary mapping letters to permutations.</p>", "help_url": "", "input_widget": "string", "input_options": {"correctAnswer": "settings[\"correctWord\"]", "hint": {"static": true, "value": ""}, "allowEmpty": {"static": true, "value": false}}, "can_be_gap": true, "can_be_step": true, "marking_script": "generator_dict:\nsettings[\"generators\"]\n\nstudent_letters:\nsplit(replace_regex(\"[^a-z]\",\"\",lower(studentanswer),\"g\"),\"\")\n\nvalid_letters:\nassert(all(map(x in generator_dict,x,student_letters)),\n  warn(\"Your word is invalid. You must only use letters corresponding to generators.\");\n  fail(\"Your word is invalid. You must only use letters corresponding to generators.\")\n)\n\nstudent_word:\nmap(generator_dict[x],x,student_letters)\n\nstudent_perm:\niterate_until([p*word[-1],word[0..-1]],[p,word],[permutation(\"\"),student_word],len(word)=0)[-1][0]\n\ncorrect_letters:\nsplit(replace_regex(\"[^a-z]\",\"\",lower(settings[\"correctWord\"]),\"g\"),\"\")\n\ncorrect_word:\nmap(generator_dict[x],x,correct_letters)\n\ncorrect_perm:\niterate_until([p*word[-1],word[0..-1]],[p,word],[permutation(\"\"),correct_word],len(word)=0)[-1][0]\n\nperm_is_correct:\nif(student_perm=correct_perm,\n  correct()\n, incorrect(\"Your answer is incorrect: your word produced the ordering \"+join(list(student_perm),' ')+\".\")\n)\n\nmark:\napply(valid_letters);\napply(perm_is_correct)\n\ninterpreted_answer:\nstudent_letters", "marking_notes": [{"name": "generator_dict", "description": "", "definition": "settings[\"generators\"]"}, {"name": "student_letters", "description": "<p>The letters in the student's word. Any non-letter characters are removed.</p>", "definition": "split(replace_regex(\"[^a-z]\",\"\",lower(studentanswer),\"g\"),\"\")"}, {"name": "valid_letters", "description": "<p>Are all of the letters in the student's word in the generator dictionary? Fail if not.</p>", "definition": "assert(all(map(x in generator_dict,x,student_letters)),\n  warn(\"Your word is invalid. You must only use letters corresponding to generators.\");\n  fail(\"Your word is invalid. You must only use letters corresponding to generators.\")\n)"}, {"name": "student_word", "description": "", "definition": "map(generator_dict[x],x,student_letters)"}, {"name": "student_perm", "description": "<p>The permutation produced by the student's word.</p>", "definition": "iterate_until([p*word[-1],word[0..-1]],[p,word],[permutation(\"\"),student_word],len(word)=0)[-1][0]"}, {"name": "correct_letters", "description": "", "definition": "split(replace_regex(\"[^a-z]\",\"\",lower(settings[\"correctWord\"]),\"g\"),\"\")"}, {"name": "correct_word", "description": "", "definition": "map(generator_dict[x],x,correct_letters)"}, {"name": "correct_perm", "description": "", "definition": "iterate_until([p*word[-1],word[0..-1]],[p,word],[permutation(\"\"),correct_word],len(word)=0)[-1][0]"}, {"name": "perm_is_correct", "description": "", "definition": "if(student_perm=correct_perm,\n  correct()\n, incorrect(\"Your answer is incorrect: your word produced the ordering \"+join(list(student_perm),' ')+\".\")\n)"}, {"name": "mark", "description": "This is the main marking note. It should award credit and provide feedback based on the student's answer.", "definition": "apply(valid_letters);\napply(perm_is_correct)"}, {"name": "interpreted_answer", "description": "A value representing the student's answer to this part.", "definition": "student_letters"}], "settings": [{"name": "generators", "label": "Generators", "help_url": "", "hint": "A dictionary mapping letters to elements of the group.", "input_type": "code", "default_value": "", "evaluate": true}, {"name": "correctWord", "label": "Correct word", "help_url": "", "hint": "The word that the student must produce.", "input_type": "string", "default_value": "", "subvars": true}], "public_availability": "restricted", "published": false, "extensions": ["permutations"]}], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Isomorphisms of a binary tree", "tags": [], "metadata": {"description": "<p>Consider a binary tree with $2^n$ nodes.</p>\n<p>We give generators for the isomorphisms of the tree: at each non-leaf vertex, swap the branches descending from that node.</p>\n<ul>\n<li>What is the action of a given word?</li>\n<li>Write a word which produces the required isomorphism</li>\n<li>Which generators commute?</li>\n<li>What is the order of each generator?</li>\n<li>Write one of the (non-root) generators in terms of the others.</li>\n<li>Which permutations of the leaves are possible?</li>\n<li>What is the order of the group of isomorphisms?</li>\n<li>What is the order of the quotient group obtained by identifying all the leaves of one branch?</li>\n</ul>", "licence": "Creative Commons Attribution 4.0 International"}, "statement": "<p>Consider the binary tree $B_\\var{depth}$ with $2^\\var{depth}$ leaves.</p>\n<p>{tree_diagram(depth,1..2^depth)}</p>\n<p>In the diagram, each dashed line represents the action of swapping the two branches of the tree on either side of the line, in place.</p>\n<p>For example, the letter $b$ corresponds to this action on the tree:</p>\n<p>{tree_diagram(depth,list(generator_dict[\"b\"]))}</p>\n<p>The letters $\\var{latex(join(generator_names,', '))}$ generate the group of isomorphisms $\\Gamma(B_\\var{depth})$ of this graph.</p>", "advice": "", "rulesets": {}, "extensions": ["eukleides", "permutations"], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"word_to_apply": {"name": "word_to_apply", "group": "Ungrouped variables", "definition": "repeat(random(generator_names),5)", "description": "", "templateType": "anything", "can_override": false}, "generators": {"name": "generators", "group": "Ungrouped variables", "definition": "let(\n  n, 2^depth,\n  fn,expression(\"[flip(a,b,n)]+if(b-a>2, eval(fn,['a':a,'b':(a+b)/2])+eval(fn,['a':(a+b)/2,'b':b]),[])\"),\n  eval(fn,['a':0,'b':n])\n)", "description": "<p>Generators for the isomorphism group of</p>", "templateType": "anything", "can_override": false}, "list_generators": {"name": "list_generators", "group": "Ungrouped variables", "definition": "html(\"<ul>\"+join(map(\"<li>$\"+letterordinal(j)+\": \"+show(generators[j])+\"$</li>\",j,0..len(generators)-1),'\\n')+\"</ul>\")", "description": "", "templateType": "anything", "can_override": false}, "commutes": {"name": "commutes", "group": "Ungrouped variables", "definition": "matrix(\n  map(map(award(1,a*b=b*a),b,generators),a,generators)\n)", "description": "<p>Which of the generators commute with each other? 1 if they commute, 0 otherwise.</p>", "templateType": "anything", "can_override": false}, "depth": {"name": "depth", "group": "Ungrouped variables", "definition": "3", "description": "", "templateType": "anything", "can_override": false}, "generator_names": {"name": "generator_names", "group": "Ungrouped variables", "definition": "map(letterordinal(j),j,0..len(generators)-1)", "description": "<p>The names of each generator. The root node is called <em>a</em>, then the ones directly under it are called <em>b</em> and <em>c</em>, and so on.</p>", "templateType": "anything", "can_override": false}, "generator_dict": {"name": "generator_dict", "group": "Ungrouped variables", "definition": "dict(zip(generator_names,generators))", "description": "<p>A dictionary mapping generator names to the corresponding permutation of the leaves.</p>", "templateType": "anything", "can_override": false}, "permutation_to_produce": {"name": "permutation_to_produce", "group": "Ungrouped variables", "definition": "apply_word(word_to_produce)", "description": "<p>A permutation to be produced by a word given by the student.</p>", "templateType": "anything", "can_override": false}, "word_to_produce": {"name": "word_to_produce", "group": "Ungrouped variables", "definition": "shuffle(generator_names)[0..3]", "description": "<p>A word corresponding to the permutation that the student must produce.</p>\n<p>Chosen so that the student's word is at least 3 letters long.</p>", "templateType": "anything", "can_override": false}, "generator_to_reproduce": {"name": "generator_to_reproduce", "group": "Ungrouped variables", "definition": "random(generator_names[1..len(generator_names)])", "description": "<p>A generator that the student must write in terms of the other generators. $a$ is excluded, since it can't be written in terms of the others.</p>", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["depth", "generators", "generator_names", "generator_dict", "word_to_apply", "list_generators", "commutes", "word_to_produce", "permutation_to_produce", "generator_to_reproduce"], "variable_groups": [], "functions": {"flip": {"parameters": [["a", "number"], ["b", "number"], ["n", "number"]], "type": "permutation", "language": "jme", "definition": "permutation(let(\n  l,(b-a)/2,\n  map(\n    switch(\n      a<=j<a+l, j+l,\n      a+l<=j<b, j-l,\n      j\n    ),\n    j,\n    0..n-1\n  )\n))"}, "apply_word": {"parameters": [["word", "list of string"]], "type": "anything", "language": "jme", "definition": "iterate_until([p*generator_dict[word[-1]],word[0..-1]],[p,word],[permutation(\"\"),word],len(word)=0)[-1][0]"}, "list": {"parameters": [["p", "permutation"]], "type": "list", "language": "jme", "definition": "map(p[j],j,1..2^depth)"}, "tree_diagram": {"parameters": [["depth", "integer"], ["leaf_labels", "list"]], "type": "eukleides_drawing", "language": "jme", "definition": "let(\n  x_spread, 0.5,\n  y_spread, 0.5,\n  depth,3,\n  fn, expression(safe(\"\"\"\n    [ a..b ] + if(n>0,[\n      b..point(x(b),(-depth-2)*y_spread) dashed gray description(\"reflection line through node {letterordinal(j)}\")\n    , b label(letterordinal(j),deg(if(n=depth,45,90))) description(\"node {letterordinal(j)}\")\n    ],[\n      let(x,k+1-2^depth,leaf, leaf_labels[x],b label(leaf,deg(-90)) description(\"leaf labelled {leaf}\"))\n    ])\n    + if(n>0,\n          eval(fn,['a':b,'b':b+vector(-x_spread*2^(n-1),-y_spread),'n':n-1,'j':j+1,'k':2k+1])\n        + eval(fn,['a':b,'b':b+vector(x_spread*2^(n-1),-y_spread),'n':n-1,'j':j+2^(n-1),'k':2k+2])\n      ,[]\n      )\n  \"\"\")),\n  max_width(30,eukleides(\"A binary tree with depth {depth}\",eval(fn,['a':point(0,0),'b':point(0,-y_spread),'n':min(depth,5),'j':0,'k':0]))\n))\n        "}}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "matrix", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>What are each of the leaves mapped to under the action of the word $\\var{latex(join(word_to_apply,' '))}$?</p>", "correctAnswer": "matrix(list(apply_word(word_to_apply)))", "correctAnswerFractions": false, "numRows": 1, "numColumns": "2^depth", "allowResize": false, "tolerance": 0, "markPerCell": false, "allowFractions": false, "minColumns": 1, "maxColumns": 0, "minRows": 1, "maxRows": 0}, {"type": "write-a-word-producing-a-given-permutation", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>Write a word which produces the following ordering of the leaves:</p>\n<p>{join(list(permutation_to_produce),' ')}</p>", "settings": {"generators": "generator_dict", "correctWord": "{join(word_to_produce,\"\")}"}}, {"type": "write-a-word-producing-a-given-permutation", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "is_right_length: \n  assert(len(student_letters)>=6,\n    incorrect(\"Your word must contain at least 6 letters.\")\n  )\n\nmark:\n  apply(base_mark);\n  apply(is_right_length)", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>Write another word which produces that ordering of the leaves, of length at least 6.</p>", "settings": {"generators": "generator_dict", "correctWord": "{join(word_to_produce,\"\")}"}}, {"type": "m_n_x", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>Which generators commute?</p>", "minMarks": 0, "maxMarks": 0, "minAnswers": 0, "maxAnswers": 0, "shuffleChoices": false, "shuffleAnswers": false, "displayType": "checkbox", "warningType": "none", "showCellAnswerState": true, "markingMethod": "sum ticked cells", "choices": "generator_names", "matrix": "commutes", "layout": {"type": "lowertriangle", "expression": ""}, "answers": "generator_names"}, {"type": "write-a-word-producing-a-given-permutation", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "didnt_use_target:\n  assert(not (settings[\"correctWord\"] in student_letters),\n    incorrect(\"You must not use the letter $\"+settings[\"correctWord\"]+\"$ in your word.\")\n  )\n\nmark:\n  apply(base_mark);\n  apply(didnt_use_target)", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>Write a word equivalent to the generator $\\var{latex(generator_to_reproduce)}$, without using $\\var{latex(generator_to_reproduce)}$.</p>", "settings": {"generators": "generator_dict", "correctWord": "{generator_to_reproduce}"}}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>What is the order of each of the generators?</p>", "minValue": "2", "maxValue": "2", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>What is the order of the group $\\Gamma(B_\\var{depth})$?</p>", "minValue": "2^(2^(depth)-1)", "maxValue": "2^(2^(depth)-1)", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>Give an expression for the order of $\\Gamma(B_n)$.</p>", "answer": "2^(2^n-1)", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "valuegenerators": [{"name": "n", "value": ""}]}, {"type": "write-a-word-producing-a-given-permutation", "useCustomName": true, "customName": "Experimentation", "marks": "0", "scripts": {}, "customMarkingAlgorithm": "note: feedback(\"This word produces the ordering: \"+join(list(student_perm),' '))\n\nmark:\n  apply(valid_letters);\n  apply(note)", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": false, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>You can use this part to see how different words act on the graph.</p>\n<p>Each time you submit this part, you will be shown the order of the leaves under the action of the word you typed.</p>", "settings": {"generators": "generator_dict", "correctWord": "a"}}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}, {"name": "Andrew Duncan", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/409/"}, {"name": "George Stagg", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/930/"}, {"name": "Sam Mutter", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/9360/"}]}]}], "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}, {"name": "Andrew Duncan", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/409/"}, {"name": "George Stagg", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/930/"}, {"name": "Sam Mutter", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/9360/"}]}