Stepwise Refinement

Objective

To 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

2) 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

2) 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 Niklaus Wirth


Related Articles


Ace the Technical Interview

  • Easily find the gaps in your knowledge
  • Get customized lessons based on where you are
  • Take consistent action everyday
  • Builtin accountability to keep you on track
  • You will solve bigger problems over time
  • Get the job of your dreams

Take the 30 Day Coding Skills Challenge

Gain confidence to attend the interview

No spam ever. Unsubscribe anytime.