Stepwise Refinement

In this chapter, you will learn about Stepwise Refinement.

Problem

I am the laziest professor ever. I've given a multiple choice test (A-D are valid answers) but I lost my test key. I'll assume that whatever answer was most popular for a question is the correct answer.

I've included a file that contains the students quiz answers. Each row represents one student. Write code that figures out the most popular answer to each question and then prints out the key.

Example

Given:

ABCCADCB
DDDCAACB
ABDDABCB
AADCAACC
BBDDAACB
ABDCCABB
ABDDCACB

Output:

ABDCAACB

Analysis

Question # : 1 2 3 4 5 6 7 8 Answers : ?

There are seven students. There are eight questions.

Steps

Step 1

1. Figure out the most popular answer to each question
2. Print out the key

Step 2

1. Figure out the most popular answer to each question

for each of the 8 questions
  Find the most popular answer
  Save the answer
end

1. Print out the key Print the answer for each question in the saved answer key

Step 3

1. Figure out the most popular answer to each question

for each of the 8 questions
  Find the most popular answer
        Possible Answers are : A, B, C, D
        Initialize the number of answers to 0 for all the possible answers
        For each of the 7 students
          Check the answer by the student
          Increment the count for the answer
        end  
  Save the answer
end

1. Print out the key Print the answer for each question in the saved answer key

This is the blueprint for our program. This blueprint can be used to code the solution in any language.

Step 4

What is the structure of the input? Let's assume an array of answers arranged by students:

['ABCCADCB','DDDCAACB', 'ABDDABCB', 'AADCAACC', 'BBDDAACB', 'ABDCCABB', 'ABDDCACB']

Step 5

@submissions = ['ABCCADCB','DDDCAACB', 'ABDDABCB', 'AADCAACC', 'BBDDAACB', 'ABDCCABB', 'ABDDCACB']
answer_key = []

def find_most_popular_answer_for(question)
  key = Hash.new(0)  

  for submission in @submissions
    key[submission[question]] += 1
  end
  key.max_by{|k,v| v}
end

for question in (0..7).to_a 
  answer_key << find_most_popular_answer_for(question)
end

puts answer_key

After I wrote the program, I had to add max_by to retain only the highest scoring answer for the given question. You can always go back and refine the step when required.

Summary

Stepwise Refinement is a useful technique for solving problems. We can start with the 'What' and gradually move towards the 'How' and finally code the solution for a given problem.

Resources

• Lazy Professor
• Program Development by Stepwise Refinement by Niklaus Wirth