// Numbas version: finer_feedback_settings
{"name": "Find all codewords with given Hamming distance", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"functions": {"random_word": {"definition": "var s = '';\nvar all_digits_same = new RegExp('^(\\\\d)\\\\1{'+(word_length-1)+'}$');\nvar fail;\n\nwhile(fail || s=='') {\n  s = '';\n  for(var i=0;i<word_length;i++) {\n    s += Numbas.math.randomint(field_size);\n  }\n  fail = all_digits_same.test(s);\n}\n\nreturn s;", "type": "string", "language": "javascript", "parameters": [["field_size", "number"], ["word_length", "number"]]}, "join": {"definition": "return list.join(separator);", "type": "string", "language": "javascript", "parameters": [["list", "list"], ["separator", "string"]]}, "hamming_ball": {"definition": "// return all codewords with desired distance from given base word\n\n// we want to change n digits between the given start and end positions in each of the given words\nfunction hamming_ball_recursive(start,end,n,words) {\n  var out = [];\n  // if n=0, output the words we've produced\n  if(n==0) {\n    return words;\n  }\n  // next digit to change must be between start and end-n\n  // for each one, ...\n  for(var i=start;i<=end-n;i++) {\n    // compute all the words we can get by changing the given words at this place\n    var nwords = [];\n    for(var j=0;j<field_size;j++) {\n      if(j!=base_word[i]) {\n        words.map(function(word){\n          nwords.push(word.slice(0,i)+j+word.slice(i+1));\n        });\n      }\n    }\n    // now change n-1 digits in those words, in the positions after the one we just changed\n    var changed_words = hamming_ball_recursive(i+1,end,n-1,nwords);\n    out = out.concat(changed_words);\n  }\n  return out;\n}\n\n// find all the words with desired number of digits changed from the base word\nreturn hamming_ball_recursive(0,base_word.length,desired_distance,[base_word]);", "type": "number", "language": "javascript", "parameters": [["base_word", "string"], ["desired_distance", "number"], ["field_size", "number"]]}}, "name": "Find all codewords with given Hamming distance", "tags": ["Hamming distance", "codes", "codewords", "coding theory", "hamming distance"], "type": "question", "advice": "<p>The code words are:</p>\n<p>{ball_text}</p>", "rulesets": {}, "parts": [{"prompt": "<p>Write down all words $w \\in \\mathbb{Z}^{\\var{word_length}}_{\\var{field_size}}$ for which $d_H(w,\\var{latex(base_word)}) = \\var{distance}$.</p>\n<p>Enter your answer as a list of codewords separated by commas, e.g. <code>0000,1111,...</code></p>\n<p>[[0]]</p>", "marks": 0, "gaps": [{"marks": "1", "showCorrectAnswer": true, "displayAnswer": "{join(ball,',')}", "scripts": {"validate": {"order": "instead", "script": "// If the student's answer had a syntax error, give them a warning with a hint\nif(this.failSyntax) {\n  this.giveWarning('You have not written a valid answer. Your answer should be a list of codewords separated by commas.');\n  return false;\n}\n\nreturn true;"}, "mark": {"order": "instead", "script": "var p = this;\nvar field_size = variables.field_size;\nvar word_length = variables.word_length;\nvar base_word = variables.base_word;\nvar desired_distance = variables.distance;\n\nvar number_of_words = variables.number_of_words;\n\nvar studentAnswer = this.cleanAnswer(this.studentAnswer);\n\n// check the student has written a list of codewords separated by commas\nthis.failSyntax = !(/^\\d+(,\\d+)*$/.test(studentAnswer));\nif(this.failSyntax) {\n  return;\n}\n\n//split string into individual words\nvar list = studentAnswer.split(',');\n\n// remove duplicates\nwords = question.functions.set(list);\n\n// tell the student if they repeated a word\n// could give 0 credit and abandon marking at this point\nif(words.length<list.length) {\n  this.markingComment('You have repeated a word.');\n}\n\nfunction hamming_distance(a,b) {\n  var l = a.length;\n  var d = 0;\n  for(var i=0;i<l;i++) {\n    if(a[i]!=b[i]) {\n      d += 1;\n    }\n  }\n  return d;\n}\n\nvar num_incorrect = 0;\nvar num_valid = 0;\nvar valid_codeword = new RegExp('^[0-'+(field_size-1)+']{'+word_length+'}$');\nwords.map(function(word,i) {\n  //check that entries lie in the correct field - look for codewords which use a number not in the range 0-(field_size-1)\n  if(!valid_codeword.test(word)) {\n    p.markingComment('$'+word+'$ is not a codeword in $\\\\mathbb{Z}_{'+field_size+'}^{'+word_length+'}$.');\n    num_incorrect += 1;\n  } else {\n    //if a codeword belongs to the right field, then check its Hamming distance from the base\n    var distance = hamming_distance(base_word,word);\n    if(distance!=desired_distance) {\n      p.markingComment('$'+word+'$ has Hamming distance $'+distance+'$ from $'+base_word+'$, not $'+desired_distance+'$.');\n      num_incorrect += 1;\n    } else {\n      num_valid += 1;\n    }    \n  }\n});\n\n\n// Tell the student if they missed any words\nif(num_valid<number_of_words){\n  this.setCredit(0,'You have not entered every codeword with distance $'+desired_distance+'$ from $'+base_word+'$.');\n  return;\n}\n\n// If the student didn't give any wrong answers, and they gave every codeword, give them the mark\nif(num_incorrect==0){ \n  this.setCredit(1);\n} else { \n  this.setCredit(0,\"You entered one or more incorrect codewords.\");\n}\n"}, "constructor": {"order": "after", "script": "var p = this;\n\nthis.cleanAnswer = function(studentAnswer) {\n  // remove spaces\n  return studentAnswer.replace(/\\s/g,'');\n}\n\n// clean the student's answer and check for any input errors before submission\nthis.display.cleanStudentAnswer = ko.computed(function() {\n  var studentAnswer = p.cleanAnswer(this.studentAnswer());\n  this.removeWarnings();\n  \n  if(studentAnswer=='') {\n    return '';\n  }\n  \n  if(!studentAnswer.match(/^\\d+(,\\d+)*$/)) {\n    this.warning('This is not a valid list of codewords. Enter codewords separated by commas.');\n    return '';\n  }\n  \n  return studentAnswer;\n  \n},this.display);"}}, "answer": "1", "type": "patternmatch"}], "showCorrectAnswer": true, "scripts": {}, "type": "gapfill"}], "statement": "", "variable_groups": [], "progress": "in-progress", "preamble": {"css": "", "js": "question.functions = {};\n\n//finds the distinct elements in an array\nquestion.functions.set = function(arr) {\n  return arr.slice().sort().reduce(function(arr,b){\n    if(!arr.length || arr[arr.length-1]!=b){\n      arr.push(b);\n    }\n    return arr;\n  },[]);\n}"}, "variables": {"distance": {"definition": "if(word_length>3,1,random(1,2))", "templateType": "anything", "group": "Ungrouped variables", "name": "distance", "description": "<p>Desired distance of codewords from the base word</p>"}, "field_size": {"definition": "3", "templateType": "anything", "group": "Ungrouped variables", "name": "field_size", "description": "<p>Number of digits in the code.</p>"}, "ball": {"definition": "hamming_ball(base_word,distance,field_size)", "templateType": "anything", "group": "Ungrouped variables", "name": "ball", "description": "<p>List of the codewords the given distance from the base word</p>"}, "ball_text": {"definition": "'$'+join(ball,'$, $')+'$'", "templateType": "anything", "group": "Ungrouped variables", "name": "ball_text", "description": "<p>A list of the codewords, wrapped in LaTeX.</p>\n<p>Done in this convoluted way because MathJax doesn't do linebreaking very well, and if there are lots of code words then the line will be too wide for the page.</p>\n<p>Instead, each codeword is its own bit of LaTeX, and they're separated by plaintext commas.</p>"}, "word_length": {"definition": "random(2..5)", "templateType": "anything", "group": "Ungrouped variables", "name": "word_length", "description": "<p>Length of codewords</p>"}, "base_word": {"definition": "random_word(field_size,word_length)", "templateType": "anything", "group": "Ungrouped variables", "name": "base_word", "description": "<p>The base word given to the student</p>"}, "number_of_words": {"definition": "comb(word_length,distance)*(field_size-1)^distance", "templateType": "anything", "group": "Ungrouped variables", "name": "number_of_words", "description": "<p>The number of codewords which are the desired distance away from the base word</p>"}}, "metadata": {"notes": "<p>Gives some interactive help in writing the list as easy make mistakes.</p>", "description": "<p>Given a codeword in $w=\\mathbb{Z}^4_3$ find and list all codewords at Hamming distance $1$ from $w$.</p>", "licence": "Creative Commons Attribution 4.0 International"}, "showQuestionGroupNames": false, "question_groups": [{"name": "", "pickingStrategy": "all-ordered", "pickQuestions": 0, "questions": []}], "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}]}]}], "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}]}