Click here to Skip to main content
65,938 articles
CodeProject is changing. Read more.
Articles / Languages / C

ACM Problem of (AARC'98) - Parkinson

3.50/5 (5 votes)
16 Jun 2008CPOL3 min read 1   65  
Solving old ACM problems

Introduction

I wrote this code while I was studying. I was testing for the ACM exam, and solved some of the problems. I solved those problems a while ago, the code is not perfect, but it solves the problems.

Background

The ACM is a big problem which depends on the algorithmic skills to solve it. It requires C, C++, or Java in solving the actual problem, and some IO to receive input and produce output.

The Problem Statement

Parkinson
Source file : parkinson.{c|cpp}
Input file: parkinson.in
Output file: parkinson.out

In medical diagnosis, a number of problems occur concerning the correct assignment of symptoms to a specific disease.

In a clinical study, some neurologists specialized in the Parkinsons disease assigned a letter value (A,B,C..) for each one of 9 Parkinson symptoms (swinging arms, speech, independence ...) for different patients.

Each patient record is a sequence of 9 letter values. $’s are included at various places in the records to make them easier to read, but have no other significance.
The sample input and expected output shown below illustrate many valid, and some invalid, record formats.

An algorithm is set to check the development of the disease for each patient based on the patient's record (The collection of the 9 values). 3 sets of 3 values represent some inter-related symptoms, and are represented as the 3 corners of a triangle. The first letter value is the first corner of the first triangle, the second value is the first corner of the second one ...
The length of each triangle edge is then computed according to a pre-defined schema:

The unit step between A and B is 1,
between B and C is 2,
between C and D is 3,
between D and E is 4,
...
between A and G is 21.

Each of the triangle's edge is then used to compute the value of the triangle.

Value of the triangle = (edge1)² + (edge2)² + (edge3)² + 1 

The 3 values of the symptom groups are then summed up. The patient is considered to have the Parkinsons disease if the final value is a prime number. Otherwise, the patient is in good health.

To better understand the procedure, consider the correct patient's record A$AA$$BB$AC$BA. First look at the symptom groups, and the calculations performed:

example

The final value of this record is 19, which is a prime number; thus showing that the patient has the Parkinsons disease.

Input File

The sample input file contains a single data record per line, possibly preceded and/or followed by spaces. No line may contain more than 70 characters, but the data record might contain illegal characters, and more or fewer than 9 letter values. The input file is terminated by an end of file.

Output File

The output file should include the display of the data record and a statement of invalid record in case it is so. If the record is legal, the output should specify if the patient is in good health, or has the Parkinsons disease.

Sample Input

ABCD 
ABCDEFGH 
A$$$BCD$HJUY$Q 
AFW#GFDGFD 
ABCD$EFG$$KP 
AAABBACBA 

Sample Output

The data sequence ABCD is invalid. 
The data sequence ABCDEFGH is invalid. 
The data sequence A$$$BCD$HJUY$Q signals that patient has Parkinson disease. 
The data sequence AFW#GFDGFD is invalid. 
The data sequence ABCD$EFG$$KP signals that patient is in good health. 
The data sequence AAABBACBA signals that patient has Parkinson disease. 

The Code and Explanation

Notes

  1. The $ character has no meaning.
  2. After filtering out the $s, the resulting string must be of length 9, exactly since it will give the edges of three triangles.
  3. The letters define the similar edges fist, means AFD => the first edge of triangle1 is A, the first edge of triangle2 is F, and so on.
  4. From this: The unit step between A and B is 1, between B and C is 2, between C and D is 3, between D and E is 4. It is obvious that the steps between the letters are increasing meaning that A-B is 1, but B-C is 2, therefore A-C is 1 + 2 = 3.
  5. The value we want is the sum of the squares of the differences between the corners.
  6. If this number is prime, then the patient has Parkinsons disease.

The code is as follows:

C++
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

//defining the letters to check if the letters is in alphabet or not.
//[I know there is simpler way, 
//but I've done this when I wasn't so good in C]
char stepsValues[27]={'A','B','C','D','E','F','G','H','I','J','K','L','M'
,'N','O','P','Q','R','S','T','U','V','W','X','Y','Z','$'};

//Computes the steps and the differences between them.
//Using the algorithm of the math for cumulative sum : Sn = [(n)*(n+1)]/2
//It gets the sum from 1 to the fist letter and the sum from 1 to the second, 
//and subtracts them to get the diff between the 2nd and the 1st.
int GetSteps(int stIndex, int ndIndex)
{
    if(stIndex==ndIndex)
        return 0;
    int stResult = (stIndex*(stIndex+1))/2;
    int ndResult = (ndIndex*(ndIndex+1))/2;
    return (ndResult - stResult);
}
//Gets the index of the letter.
int IndexOF(char c)
{
    for(int i=0;i<26;i++)
    {
        if(c==stepsValues[i])
            return i;
    }
    return -1;
}

//This function checks if the char is in the permitted chars.
bool IsInChars(char c)
{
    for(int i=0;i<27;i++)
        if(c == stepsValues[i])
            return true;
    return false;
}

//This method cleans up the [CORRECT] record and remove any $ from it.
//Cleans up the [CORRECT] record and remove any $ from it.
string ExcludeLetters(char* record)
{
    string refinedRecord = "";
    for(int i=0;i<strlen(record);i++) rdtriangle="ComputeTriangle(t3_1,t3_2,t3_3);
	" ndtriangle="ComputeTriangle(t2_1,t2_2,t2_3);" 
	sttriangle="ComputeTriangle(t1_1,t1_2,t1_3);" 
	t3_3="GetSteps(IndexOF(refinedRecord[5]),IndexOF(refinedRecord[8]));" 
	t3_2="GetSteps(IndexOF(refinedRecord[2]),IndexOF(refinedRecord[8]));" 
	t3_1="GetSteps(IndexOF(refinedRecord[2]),IndexOF(refinedRecord[5]));" 
	t2_3="GetSteps(IndexOF(refinedRecord[4]),IndexOF(refinedRecord[7]));" 
	t2_2="GetSteps(IndexOF(refinedRecord[1]),IndexOF(refinedRecord[7]));" 
	t2_1="GetSteps(IndexOF(refinedRecord[1]),IndexOF(refinedRecord[4]));" 
	t1_3="GetSteps(IndexOF(refinedRecord[3]),IndexOF(refinedRecord[6]));" 
	t1_2="GetSteps(IndexOF(refinedRecord[0]),IndexOF(refinedRecord[6]));" 
	t1_1="GetSteps(IndexOF(refinedRecord[0]),IndexOF(refinedRecord[3]));" 
	if((number%i)="=0)" i="0;i<strlen(record);i++)" if(letters.length()!="9)" 
	letters="ExcludeLetters(record);" +="record[i];" 
	if(isinchars(record[i])&&!(record[i]="='$'))">>line;
        if(!IsCorrect(line))
        {
            outFile<<"The data sequence " <<line << " is invalid\n";
            continue;
        }
        int result = FinalResult(ExcludeLetters(line));
        if(IsPrime(result))
        {
            outFile<<"The data sequence " <<line << " signals that 
				the patient has Parkinson disease\n";
            continue;
        }
        else
        {
            outFile<<"The data sequence " <<line << " signals that 
				the patient is in good health\n";
            continue;
        }
    }
    return 0;
}

At Last

This problem is the first, and I will write articles about the next problems that I managed to solve. Thanks.

History

  • 16th June, 2008: Initial post

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)