Prolog: Determine answers to Multiple Choice Question test where students' answers and grades are known

Question

This is a prolog problem that I have to solve. I can't seem to find a starting point.

In a MCQ test where:

• each question has 4 choices [a,b,c,d]
• each question has only one correct answer (choice)
• there are 10 questions
• all questions have the same grade value (1 point, totalling 10 points)

4 students have taken this test and we have their grades:

• student1: [b, c, b, a, c, c, c, d, c, c] Grade: 7/10
• student2: [b, d, c, a, d, d, c, c, a, b] Grade: 6/10
• student3: [d, a, b, b, d, d, c, d, a, b] Grade: 5/10
• student4: [c, d, c, b, d, b, b, c, a, a] Grade: 3/10

From the informations above I need to write a prolog script that can determine the set of questions that are correct to get a 10/10 grade

Answer 1

We can branch over the possible choices, and do bookkeeping on the score of the students. When we reach the end of the list, then the users need to have the correct score.

We thus can generate lists of choices with:

option(a).
option(b).
option(c).
option(d).

sequence(N, L) :-
    length(L, N),
    maplist(option, L).

For example for a sequence of two items, we get:

?- sequence(2, L).
L = [a, a] ;
L = [a, b] ;
L = [a, c] ;
L = [a, d] ;
L = [b, a] ;
L = [b, b] ;
L = [b, c] ;
L = [b, d] ;
L = [c, a] ;
L = [c, b] ;
L = [c, c] ;
L = [c, d] ;
L = [d, a] ;
L = [d, b] ;
L = [d, c] ;
L = [d, d].

Next we can make a predicate mark/3 that calculates the score given the hypothetical correct sequence, and the sequence of a student. We thus need to implement something like:

mark([], [], 0).
mark(…, …, …) :-
    ….

I leave the implementation of mark/3 as an exercise.

Then we thus can find the sequence of correct answers with:

correct(C) :-
    sequence(10, C),
    mark(C, [b, c, b, a, c, c, c, d, c, c], 7),
    mark(C, [b, d, c, a, d, d, c, c, a, b], 6),
    mark(C, [d, a, b, b, d, d, c, d, a, b], 5),
    mark(C, [c, d, c, b, d, b, b, c, a, a], 3).

You can later optimize the approach to an interleaved generate-and-test and not first generating sequences and then testing these. But I would first start with a simple solution that works.

When I implement this myself, there is exactly one solution. That solution has b as first answer.