Have you tried this horrible-looking puzzle?
2/6 forall(answer_list): bad = False for testing_question in [1,2,3,4,5,6,7,8,9,10]: for testing_option in ["a","b","c","d","e"]: # your answer should be correct if testing_option == answer_list[testing_question] and check(testing_question, testing_option) == False: bad = True # other options must be incorrect if testing_option != answer_list[testing_question] and check(testing_question, testing_option) == True: bad = True if not bad: print answer_list Here “answer_list” is a list of letters (subscript is 1-based), where the i-th letter is the answer to the i-th question. Believe or not, the only answer is: “cdebeedcba” (if you prefer to add the question index before each answer, it is “1c2d3e4b5e6e7d8c9b10a”) Amazing, huh? There’s more. You wish that your program could solve some other puzzles, but first of all, you need to formulate the puzzle in a formal language. Formalizing the Puzzle This problem uses a LISP dialect to represent the puzzle. Don’t worry if you don’t know LISP, it has a very simple syntax. (f a b) means calling a function f with parameters a and b. That’s like f(a, b) in C/C++/Java. Similarly, (f a (g b c) d) is like f(a, g(b, c), d) in C/C++/Java. Here is an example of how to describe a question of the puzzle: 3. (equal (answer 3) (answer (option-value))) a. 1 b. 2 c. 4 d. 7 e. 6 There are two very important built-in functions involved: (answer idx) returns answer_list[idx] in the pseudo-code above. In the example above, if testing_option is “c”, then (option-value) returns 4 (an integer) because 4 is the expression presented in the option “c” of this question. Note that testing_option’s text can be a complex expression instead of a simple value. Refer to Sample Input. The function “check(testing_question, testing_option)” above can be implemented as fol- lows: check(testing_question, testing_option):
3/6 There is one special option expression: ”none-of-above”. The result of ”none-of-above” depends on other options’ evaluation results. In this problem, there can be at most one ”none-of-above” for each question, and it must be the last option. Details Here are the details of the LISP dialect used in this problem: • There are four datatypes: integer, string, boolean and functions. • There are only two boolean values: true and false. Note that there are no ”boolean literal”, so you don’t care whether to use #t and #f (like in Scheme), or t and nil (like in Common Lisp) to represent boolean constants. • Integers are always non-negative integers. • String literals are always enclosed by double quotes, like “a string”. • There is no variable. All the so-called “identifiers” (consisting of letters and hyphens) are always pre-defined functions. Below is a list of pre-defined functions. Functions starting with ‘!’ means it may throw an exception, and functions starting with ‘@’ means it can handle exceptions. Like C++/Java/Python, once an exception is raised, the evaluation process is stopped unless a function handles the exception. In the text below, ‘iff’ means “if and only if”. Basic functions (option-value) iscussed above. Predicates Predicate is a special kind of function. It always takes a value of any type and returns a boolean value. prime-p returns true iff the parameter is a positive prime factorial-p self-explanatory square-p self-explanatory cubic-p self-explanatory vowel-p returns true iff the parameter is a single letter and is a vowel consonant-p self-explanatory (equal a b) return true iff a and b are of the same type and are equal. In this problem, you’ll never need to compare two functions. !(answer idx) discussed above. If idx is not an integer or is not in 1...n (where n is the number of questions), then raises an exception !(answer-value idx) Returns the “evaluation result” of option answer_list[idx] of question idx. Also raises an exception on error. Queries and statistics !@(first-question pred) !@(last-question pred) !@(only-question pred) @(count-question pred) Return id of the first question that satisfies ‘pred‘. Raises an exception if not found. Return id of the last question that satisfies ‘pred‘. Raises an exception if not found. Return id of the only question that satisfies ‘pred‘. Raises an exception if not found or more than one question found. Return the number of questions that satisfies ‘pred‘. !(diff-answer idx1 idx2) The difference of answers of question idx1 and idx2. Raises an exception on error, otherwise the return value is always 0...m − 1, where m is the number of options for each question.
4/6 Note that in the first four functions (those with a ‘@’ flag), if an exception was raised when evaluating the predicate, the exception is handled and the predicate is not considered satisfied. For example, if answer_list is “abc”, (count-question (make-answer-diff-next-equal 0)) re- turns 0 and doesn’t raise an exception, even though evaluating the predicate for question 3, i.e. ((make-answerdiff-next-equal 0) 3) raised an exception. However, all other functions will not handle exceptions. For example, if there are only 3 questions, (factorial-p (answer-value 5)) will raise an exception instead of returning false. Predicate generators There are also functions that can create predicates on-the-fly: !(make-answer-diff-next- equal num) returns a predicate (p idx) which evaluates (diff-answer idx idx+1) and returns true if the result equals to num. Raises an exception if num is not an integer. (make-answer-equal a) (make-answer-is pred) (make-answer-value-equal a) (make-answer-value-is pred) (make-not pred) returns a predicate (p idx) which evaluates (answer idx) and returns true if the result equals a. returns a predicate (p idx) which evaluates (answer idx) and returns true if the result satisfies ‘pred‘. self-explanatory. The predicate evaluates (answer-value idx) self-explanatory. The predicate evaluates (answer-value idx) returns a predicate (p v) which returns true iff (pred v) is false. !(make-is-multiple num) returns a predicate (p i) which returns true iff i is an integer and is a multiple of num. Raises an exception if num is not an integer. !(make-equal val) returns a predicate (p v) which returns true iff (equal v val) is true. Raises an exception if val is neither an integer nor a string. (make-and pred1 pred2) returns a predicate (p v) which returns true iff (pred1 v) and (pred2 v) are both true. Both pred1 and pred2 need to be evaluated. No short-circuit operation should be done. (make-or pred1 pred2) returns a predicate (p v) which returns true iff at least one of (pred1 v) and (pred2 v) is true. Both pred1 and pred2 need to be evaluated. No short-circuit operation should be done. For example, (make-is-multiple 3) returns a predicate “is a multiple of 3”, so ((make-is-multiple 3) 6) returns true and ((make-is-multiple 3) 10) returns false. Similarly (make-not (make-or square-p prime-p)) returns a predicate “neither a square nor a prime”. Input There will be at most 50 test cases. Each test case begins with two integers n and m (2 ≤ n ≤ 10, 2 ≤ m ≤ 5), the number of questions and the number of options per question. Each question is described with m + 1 lines: the question’s expression and the options. Questions are numbered 1 . . . n, and options are labeled ‘a’..‘e’. Options are valid expressions and will not call option-value (calling optionvalue makes it recursive!). Each question is followed by a blank line. Most test cases are easy. Output For each test case, print the case number in the first line, and a list of answers, one per line, sorted in ascending order. There will always be at least one answer. Note: This problem is complex. If you have any questions, email me: rujia.liu@gmail.com
5/6 Sample Input 33 (equal (option-value) (count-question (make-answer-equal "a"))) 3 0 1 (equal (option-value) "a") "c" "b" "a" ((option-value) (count-question (make-answer-equal "c"))) (make-and (make-is-multiple 2) (make-or factorial-p prime-p)) (make-not prime-p) "none-of-above" 32 (equal (option-value) (answer 2)) "a" "none-of-above" (equal (option-value) (first-question (make-answer-diff-next-equal 0))) 1 2 ((option-value) (last-question (make-answer-equal "b"))) (make-is-multiple 2) (make-not (make-is-multiple 2)) 32 (equal (option-value) (answer 1)) "a" "b" ((option-value) (last-question (make-answer-diff-next-equal 0))) (make-equal 2) "none-of-above" ((option-value) (only-question (make-answer-equal "b"))) (make-is-multiple 2) "none-of-above" 25 ((option-value) (diff-answer 1 2)) factorial-p prime-p (make-not square-p) (make-not cubic-p) "none-of-above" (equal (only-question (option-value)) 1) (make-answer-is consonant-p) (make-answer-is vowel-p) (make-answer-value-equal 1) (make-answer-value-is square-p) "none-of-above" 22 (option-value) (equal (first-question (make-answer-diffnext-equal 2)) (first-question (makeanswer-diff-next-equal 2))) "none-of-above" (equal (option-value) 1) 1 2 Sample Output Case 1:
6/6 bcb cca Case 2: aab Case 3: aba Case 4: ab ee Case 5: ba