Q and A System - Take 2

I have spent the past few days revamping the Q and A system. I have created new classes, made others obsolete, and created a much more flexible and powerful interface than the prior system. I will walk you through this system so that you can understand exactly how it does what it does. 

To begin, I will explain the type of question and answer structure we will be dealing with. This system will contain a set of categories, each category containing a set of questions, and each question containing a set of answers. In theory, this could be done using a database or an XML file. For this example, I will use an XML file. 

The XML file will be formatted like so:

<questions>

   <category name="category1">

      <question text="This is a question?" minLevel="0" image="">

             <answer text="Option1" correct="0" />

             <answer text="Option2" correct="0" />

             <answer text="Option3" correct="1" />

             <answer text="Option4" correct="0" />

      </question>

   ...

   </category>

   ...

</questions>

I will explain later what minLevel, correct, and all of the other attributes are. 

The goal for our Q and A system is to turn this XML file into an identical data structure. Originally, I had omitted creating a structure for the categories since they can be represented easily as simply a text string. However, I later found myself wanting my program to want to have the ability to answer questions such as, "for the given difficulty level, how many questions does this category contain?" In order to answer this question, a category structure had to be built. 

So, we want to have a list of categories with varying length (assume we want this system to be used for various q and a games). Each category in the list has a list of questions which also vary in quantity. And each question has a set of answers (in this case, we set an upper bound on how many potential answers can exist). So it looks like the structures we will need to define are:

Category - The name of the category, an array of integers representing how many questions the category contains at varying difficulty settings, and a Queue<T> of question objects. 

Question - An array of possible answers, the index of the correct answer, the difficulty level of the question, and a drawable image.

Queue<T> - This class will create of list of T objects. If you are unfamiliar with Java generics, this will offer you a quick glance at how they work. This class will operate just like you would expect a queue to behave... you can push items on, pop them off, get items by index (not an array so this is a bit deceiving), or retrieve them by matching the Object's toString() method call. 

SO, lets begin...

Continue to Category class definition >

Question Node Class

This class is also fairly straightforward. These class represents a node in a linked list of Question objects. Each node stores a boolean value indicating whether or not the node's question has ever been accessed, a reference to the next QuestionNode in the list, and a Question object. This class will be located within the QuestionQueue class since only the QuestionQueue will need to access it. 

private class QuestionNode
/*** Description ***
* This class represents a single node in a one directional list of questions. 
* 
*** Notes ***
* There is no setter method for 'next'. Instead, the outer class
* directly sets this variable value (ex: thisNode.next = ...). 
* This is because passing an entire Question object is pointless 
* since this is already a private class. 
* 
* Accessor methods are still used simply for code clarification.
*
*** Variables ***
*
* q - the Question object this node holds
* next - the next QuestionNode in the list
* used - tracks whether the Question this node holds has been used or not
* 
*** Methods ***
*
* Constructor - Expects a Question object to hold. 
* 
* getQuestion - Accessor method for q. Also sets used to true.
* used   - Accessor method for used.
* getNext   - Accessor method for next.
* 
* setNext(QuestionNode) - Setter method for next. 
*/
{
private Question q;
private QuestionNode next;
private boolean used;

public QuestionNode (Question q)
{
this.q = q;
this.next = null;
}

public Question getQuestion()
{
this.used = true;
return q; 
}

public boolean used()
{
return used;
}

public QuestionNode getNext()
{
return next;
}

}

Question Class

This class is the most straightforward of all that will be used to construct this Q&A system. The class simply represents a trivia question. 


Each question has the following attributes:

• Question text
• An array of possible answers 
• The index in the array of the correct answer
• A drawable image for image related questions (not implemented yet)

The class has simple getter and setter methods with access each of the fields. 

private class Question
/*** Description *** 
* This class represents a single question/answer.
* 
*** Variables *** 
* cAnswer  - Index (in answers[]) of correct answer to question
* answers  - Array of strings representing a set of possible answers
* question - String representing the question text
* image - Drawable image created from imageSrc passed in constructor
* 
*** Methods ***
* Constructor - intitializes all items to default values
* 
* checkAnswer - returns true when submitted integer representing an array index
* matches cAnswer
* 
* setQuestion, setCAnswer, setImage, addAnswer - setter methods
* 
* getAnswers  - Accessor method which returns answers
* getQuestion - Accessor method which returns question
* getImage    - Accessor method which returns image
* getCAnswer  - Accessor method which returns cAnswer
*/
{
private int cAnswer;  
private int answerIndex;
private String [] answers; 
private String question;
private Drawable image;

public Question ()
{
this.cAnswer = -1; 
this.question = null;
this.image = null;
this.answers = new String[MAX_ANSWERS];
this.answerIndex = 0;
}

public void setQuestion(String q)
{
this.question = q;
}

public void setCAnswer(int i)
{
this.cAnswer = i;
}

public void setImage (String imagePath)
/* NOT FUNCTIONAL YET */
{
this.image = null;
}

public void addAnswer (String a)
{
this.answers[answerIndex++] = a;
}

public boolean checkAnswer(int answer)
{
return (cAnswer == answer);
}

public String [] getAnswers()
{
return answers;
}

public String getQuestion()
{
return question;
}

public Drawable getImage()
{
return image;
}

public int getCAnswer()
{
return cAnswer;
}


}

Question and Answer System for Android

The next few posts will be spent creating a question and answer system for an android device. I will cover the underlying data structures used to serve questions to the calling application on an Android device. 


These structures will include:


QandA - This is the class the user will use to create the question and answer list. 
QuestionQueue - This structure will hold the actual queue of questions. 
QuestionNode - Will serve as a node in the QuestionQueue
Question - The question and answer text and information. 


First stop, the Question class. Stay tuned. 

Project Euler #5 - Java

Question:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Answer:

I'll admit I had to spend some serious time thinking about the best way to tackle this one. Then, it just sort of came to me. The answer is practically hidden within the question! One important fact is given: 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What this means is that the number we are looking for MUST be a multiple of 2520! So all we have to do, is check each and every multiple of 2520 to see if the integers 11-20 divide it evenly. If they all divide in, we found the number! 

With that in mind, I believe the code speaks for itself and does not require further explanation. 

public class euler_05 
{
    final static int multiple = 2520;
    
    public static void main(String[] args) 
    {
            
        int smallest = 2520; 
        boolean done = false;     
        
        while (!done)
        {
            for (int i = 11; i <= 20; i++)
            {
                if ( smallest % i > 0 )
                {
                    smallest += multiple; 
                    break;
                }
                
                if ( i == 20 )
                    done = true;
            }
        }
           
        System.out.printf("The smallest multiple divisible by 1-20 is %d\n",  smallest);
    }
}

Project Euler #4 - Java

Question:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91  99.

Find the largest palindrome made from the product of two 3-digit numbers.

Solution:

So, a there are two basic facts about this problem to keep in mind. One, any two 3-digit numbers will have a 6 digit product. Second, a 6-digit palindrome will be in the form ijkkji, where j and k are integers from 0-9 and i is an integer from 1-9. We know that i cannot be zero because of the fact that the product must be a 6-digit number. If i were 0, the product would only contain 5 digits (ie: leading zeroes do not count). 

So with this in mind, this problem is simple. Since we are looking for the largest palindrome with two 3-digit products, begin at 999999 and check whether this number is the product of two 3 digit numbers. If it is not, we must decrement our palindrome from the inside out. In other words, our loop is structured as i -> j -> k. We decrement k, then j, then i as we loop through our possible palindromes. 

Lets put these ideas in concrete with some code. 

public class euler_04 {


    final static int MIN3 = 100;
    final static int MAX3 = 999;
    
    public static void main (String args[])
    {
        int i, j, k, m;
        int subj; 


        for (i = 9; i > 0; i--)
        {
            for (j = 9; j >= 0; j--)
            {
                for (k = 9; k >= 0; k--)
                {
                    subj = k*1100 + j*10010 + i*100001; // create our test subject
                    
                    for (m = MAX3; m >= MIN3 ; m--) 
                    {
                        if ( (subj % m) > 0) // if the number is not divisible go to the next value of m
                            continue;
     
                        int div = subj / m; 
                        if (div >= 100 && div <= 999) // we found our subject!
                        {
                            System.out.printf("Largest palindrome with 3 digit multipliers is %d\n", subj);
                            System.exit(1);
                        }
                    }
                }
            }
        }  
    }
}

Project Euler #3 - Java

Question:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Solution:

We are going to assume that a list of prime numbers is NOT available to solve this problem. Still, this question is simple as long as you know one basic law of mathematics: all composite numbers can be written as a product of primes. I'm going to omit the proof (by contradiction) and ask you to just trust me on this. For example,

8 = 2*2*2 

9 = 3*3 

10 = 2*5 

147 = 3*7*7

So now with that little nugget tucked away we can tackle this problem. The solution is to loop through 2 and every odd integer and check whether the integer divides evenly into our subject number. If it does, divide the subject by that integer repeatedly until a remainder is found. Once a remainder is found, continue on to the next integer. Finally, we stop looking for a new integer when our subject equals 1. 

You might be thinking, "wait, does that really work?" I assure you, it does. Let's look at our previous examples.

Subject: 8

Integer: 2

Iteration 1: Does 2 divide 8? Yes, so divide 8 by 2.

Iteration 2: Does 2 divide 4? Yes, so divide 4 by 2. 

Iteration 3: Does 2 divide 2? Yes, so divide by 2. 

Iteration 4: Does 2 divide 1? Nope!... subject equals 1. 

Highest prime that divides 8 is 2.  

   

Subject: 147

Integer: 2

Iteration 1: Does 2 divide 147? No, increase Integer. 

Iteration 2: Does 3 divide 147? Yes, so divide by 3. 

Iteration 3: Does 3 divide 49? No, increase Integer.

Iteration 5: Does 5 divide 49? No, increase Integer. 

Iteration 7: Does 7 divide 49? Yes, so divide by 7. 

Iteration 8: Does 7 divide 7? Yes, so divide by 7.

Iteration 9: Does 7 divide 1? No. Subject equals 1. 

Highest prime that divides 147 is 7. 

This algorithm works for ALL numbers. So without further adieu, my solution. With all this in mind, I do not believe my code needs any further explanation.

import java.math.BigInteger;


public class euler_03
{
    public static void main(String[] args)
    {
        BigInteger dividend = new BigInteger("600851475143");
        BigInteger divisor = new BigInteger("3"); // Skip 2 since this is an odd number
        int high = 3;
       
        while(true)
        {
            // Continually divide until no remainder
            while (dividend.remainder(divisor).equals(BigInteger.ZERO))
            {
                dividend = dividend.divide(divisor);
                high = divisor.intValue();
            }
           
            divisor = divisor.add(BigInteger.valueOf(2));
           
            if (dividend.equals(BigInteger.ONE))
                break;
        }
       
        System.out.printf("The highest prime factor is %d\n", high);
    }
}