You are hereProgramming Problems / 2012 Programming Problems

# 2012 Programming Problems

By - Posted on 11 December 2012

# toc_collapse=0; Table of contents  Print Diamond Palindrome Prime Numbers DNA Sequence Zero Duplicates Averages Cube Chaos

Discussion Forum: http://aispc.computing.dcu.ie/forums/1st-round-problem1-print-diamonds

Write a program called Diamond which will ask the user to enter a positive odd integer n that is between 3 and 19.

The program will use this information to print out a diamond shape of asterisks (ie *) shown below where n is the
width of a diamond (ie number of asterisks in the central line).

The program can be written in c, c++, java, perl, python, ruby or shell. If the program was written
in java it would be compiled and run as described below;

>javac Diamond.java

>java Diamond
Enter the diamond width, which must be a positive odd integer: 3

*
* *
* * *
* *
*

>java Diamond
Enter the diamond width, which must be a positive odd integer: 9

*
* *
* * *
* * * *
* * * * *
* * * * * *
* * * * * * *
* * * * * * * *
* * * * * * * * *
* * * * * * * *
* * * * * * *
* * * * * *
* * * * *
* * * *
* * *
* *
*

## Palindrome

Discussion Forum: http://aispc.computing.dcu.ie/forums/1st-round-problem2-palindrome

A palindrome is a word, phrase, number, or other sequence of units that can be read the same way
backwards as it can be forwards. Write a program called Palindrome that will be able to detect if
the word entered is a palindrome or not.

The program should work when there is an even and odd number of characters, for example
a palindromes with an even number of character would be noon and palindrome with an odd
number of character would be racecar.

The program can be written in c, c++, java, perl, python, ruby or shell. If the program was written
in java it would be compiled and run as described below;

>javac Palindrome.java

>java Palindrome
Please enter a word: noon
The word noon is a palindrome

>java Palindrome
Please enter a word: moon
The word moon is not a palindrome

>java Palindrome
Please enter a word: racecar
The word racecar is a palindrome

>java Palindrome
Please enter a word: racecars
The word racecars is not a palindrome

## Prime Numbers

Discussion Forum: http://aispc.computing.dcu.ie/forums/problem1-prime-numbers

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

A natural number greater than 1 that is not a prime number is called a composite number. For example, 5 is prime, as only 1 and 5 divide into it, whereas 6 is composite, since it has the divisors 2 and 3 in addition to 1 and 6.

Write a program called p1 that will read in two positive integers where the first interger will be between 10 and 50 and the second integer will between 50 and 100. The program should print the sum of all the prime numbers between the two numbers.

If the first number is not between 10 and 50 it should just display the message "The first number is not between 10 and 50".

A similar check should be done to make sure that the second number is between 50 and 100 and print the message "The second number is not between 50 and 100" if it was less than 50 or greater than 100.

The program can be written in c , c++ , java  or python and should be named p1.c, p1.cpp , p1.java or p1.py respectively.

If the input file was that shown below, the correct output will be the sum of all the prime numbers between 15 and 62 which are

17 19 23 29 31 37 41 43 47 53 59 61.

p1_input.txt
------------
15 62

If the the program was written in java it would be compiled and run as described below;

>javac p1.java

>java p1 < p1_input.txt
460

or

>java p1 < p1_input.txt > p1_output.txt

when you open the p1_output.txt file it should contain the number below the dashed lines;

p1_output.txt
-------------
460

## DNA Sequence

Discussion Forum: http://aispc.computing.dcu.ie/forums/problem2-dna-sequence

Write a program called p2 that will read in a dna sequence for example GTTCAG .

Then the program will search for this dna sequence in a String in the p2 program called dnaDatabase.

It will print out the characters that occur directly before and after this sequence whenever it occurs
in the dnaDatabase String.

The program can be written in c , c++ , java  or python and should be named p2.c, p2.cpp , p2.java
or p2.py respectively.

String dnaDatabase =  "CCTGTATTAGGTTCAGAATTCGTTCAGCAGCAGATTCGATTAGCTTTACAACAATTCAATA"+
"AAATAGCTTCGCGCTAAATTTTTAACTTTTCTCTGTCGTCGCACAATCGACTTTCTCTGTT"+
"TTCTTGTTCAGGGGTTTACCGGAATTGTTTCTGCTGCGATGAGGTATTGCTCGTCAGCCTG"+
"AGGCTGAAAATAAAATCCGTGGTCACACCCAATAAGTTAGAGAGAGTACTTTGACTTGGAG"+
"CTGGAGGAATTTGACATAGTCGAGTTCAGTTCTTCTCCAAGACGCATCCACGTGAACCGTT"+
"GTAACTATGTTCTGTGCCCACACCAAAAAAACTTTCCACGTGAACCGAAAACGAAAGTCTT"+
"TGGTTTTAATCAATAAGTGCTCTCTTCTCGGAGAGAGAAGGTGGGCTGCTTGTCTGCCGAT"+
"GTACTTTATTAAATCCAATAACCACACCAAAAAAACTTTCCACGTGTGAACTATACTCCAA"+
"AAACGAAGTATTGGTTTATCATAATCTGAAAAGTGCAAAGAACGATGATGATGATGATAGA"+
"GGAACCTGAGCAGCCATGTCTGAACCTATAGCGTATTGGTCGTCGTGCGACTAAATTAGGT"+
"AAAAAAGTAGTTCTAAGAGATTTTGATGATTCAATGCAAAGTTCTATTAATCGTTCAATTG";

note: the String variable dnaDatabase can also be a character array.

p2_input.txt
------------
GTTCAG

If the input file was that shown above and the program was written in java it would be compiled
and run as described below;

>javac p2.java

>java p2 < p2_input.txt
G A
C C
T G
A T

or

>java p2 < p2_input.txt > p2_output.txt

when you open the p2_output.txt file it should contain the text below the dashed lines;

p2_output.txt
-------------
G A
C C
T G
A T

------------------------------------------------------------------------------------------
To check this select Edit -> Find, Find What GTTCAG

CCTGTATTAG GTTCAG AATTC GTTCAG CAGCAGATTCGATTAGCTTTACAACAATTCAATA

AAATAGCTTCGCGCTAAATTTTTAACTTTTCTCTGTCGTCGCACAATCGACTTTCTCTGTT

TTCTT GTTCAG GGGTTTACCGGAATTGTTTCTGCTGCGATGAGGTATTGCTCGTCAGCCTG

AGGCTGAAAATAAAATCCGTGGTCACACCCAATAAGTTAGAGAGAGTACTTTGACTTGGAG

CTGGAGGAATTTGACATAGTCGA GTTCAG TTCTTCTCCAAGACGCATCCACGTGAACCGTT

you can see below the dna sequence with letters that occur before and after it.
G GTTCAG A
C GTTCAG C
T GTTCAG G
A GTTCAG T
-----------------------------------------------------------------------------------------

## Zero Duplicates

Discussion Forum: http://aispc.computing.dcu.ie/forums/problem3-zero-duplicates

Write a program called p3 that will read in a list of numbers and will then print out the same list
except numbers that have already been printed will be printed as a zero instead.

The program can be written in c , c++ , java  or python and should be named p3.c, p3.cpp , p3.java or p3.py respectively.

p3_input.txt
------------
1 2 2 3 3 4 5 5 3 2 6

If the input file was that shown above and the program was written in java it would be compiled and run as described below;

>javac p3.java

>java p3 < p3_input.txt

1 2 0 3 0 4 5 0 0 0 6

or

>java p3 < p3_input.txt > p3_output.txt

when you open the p3_output.txt file it should contain the text below the dashed lines;

p3_output.txt
-------------
1 2 0 3 0 4 5 0 0 0 6

## Averages

Discussion Forum: http://aispc.computing.dcu.ie/forums/problem4-averages

The mean, median, and mode are three kinds of "averages". There are many "averages" in statistics,

but these are the three most common.

The mean is what is usually called the average, where you add up all the numbers and then divide by the
number of numbers.

The median is the middle value in the list of numbers. To find the median, you will first have to
rewrite the list in numerical order (ie ascending order). If there is an odd number of numbers the
median will be the middle value but if there is an even number of numbers then the median will be
the mean of the middle two values, so you sum the two middle values and divided by 2.

The mode is the number that is repeated the most often.But if there is no one number that is repeated
more than any other numbers then the mode can be a list of numbers that are repeated the most often
provided that they occur more than once in the list.If there is no mode for the list then print
the word none.

The range is just the difference between the largest and smallest values.

Write a program called p4 that will read in a list of numbers with a minus 1 to indicate the end of the
input. It will then print out values for the mean, median, mode and range of the list of numbers.

Your program should work with an even and odd number of numbers in the list.

Example 1:
----------
To find the mean, median, mode, and range for the following list of values;
13, 18, 13, 14, 13, 16, 14, 21, 13

mean     =  (13 + 18 + 13 + 14 + 13 + 16 + 14 + 21 + 13) / 9 = 135 / 9 = 15

median   =  13, 13, 13, 13, 14, 14, 16, 18, 21
=  13, 13, 13, 13,        14,       14, 16, 18, 21
=  14

mode     =  13 (because 13 occurs 4 times)

range    =  largest value in the list is 21, and the smallest is 13, so the range is  21 - 13
=  8

Example 2:
----------
To find the mean, median, mode, and range for the following list of values:
8, 9, 10, 10, 10, 11, 11, 11, 12, 13

mean     =  ( 8 + 9 + 10 + 10 + 10 + 11 + 11 + 11 + 12 + 13 ) / 10 = 105 / 10 = 10.5

median   =  8, 9, 10, 10, 10, 11, 11, 11, 12, 13
=  8, 9, 10, 10,    10, 11,    11, 11, 12, 13
=  (10 + 11) / 2 = ( 21 ) / 2
=  10.5

mode     =  10 11 (these two values are repeated three times)

range    =  largest value in the list is 13, and the smallest is 8, so the range is  13 - 8
=  5

The program can be written in c , c++ , java  or python and should be named p4.c, p4.cpp , p4.java or p4.py respectively.

If the program was written in java it would be compiled and run as described below;

Example 1:
==========
The list of number in the file p4_input_ex1.txt below will have the following averages;
The mean    =  15
The median  =  14
The mode    =  13
The range   =   8

p4_input_ex1.txt
----------------
13 18 13 14 13 16 14 21 13 -1

>javac p4.java

>java p4 < p4_input_ex1.txt
15
14
13
8

or

>java p4 < p4_input_ex1.txt > p4_output_ex1.txt

when you open the p4_output_ex1.txt file it should  contain the text below the dashed lines;

p4_output_ex1.txt
-----------------
15
14
13
8

Example 2:
==========
The list of number in the file p4_input_ex2.txt below will have the following averages;
The mean    =  10.5
The median  =  10.5
The mode    =  10 11
The range   =  5

p4_input_ex2.txt
----------------
8 9 10 10 10 11 11 11 12 13 -1

>javac p4.java

>java p4 < p4_input_ex2.txt
10.5
10.5
10 11
5

>java p4  < p4_input_ex2.txt > p4_output_ex2.txt

when you open the p4_output_ex2.txt file it should contain the text below the dashed lines;

p4_output_ex2.txt
-----------------
10.5
10.5
10 11
5

## Cube Chaos

Discussion Forum: http://aispc.computing.dcu.ie/forums/problem5-cube-chaos

Little Matty liked playing with his blocks very much. He always constructed his `buildings' in the same way: he made stacks of one or more blocks, and he put those stacks on a square table that was exactly K blocks wide (K = 8 for his largest table, so it could contain up to 8 x 8 block stacks). He didn't put the stacks randomly on the table. No, he always made a nice `square' pattern. In most buildings, there was no pattern visible in the heights of the stacks. However, since Little Matty himself was only eight blocks tall, a single stack of blocks never consisted of more than eight blocks.

This is an example of one of his buildings. It was built on a table that could contain 4 x 4 block stacks. He liked drawing too. To record his block buildings for future generations, he would draw them on paper. Since drawing a three-dimensional block building just was too hard for him, he made two drawings of a building: one straight from the front (you could only see the front of the blocks), and one from the right (you could only see the right side of the blocks). The drawings were in fact two-dimensional projections of the block building, showing only its outline on the front or on the right side.

These are the drawings he made of the building shown above. Front                                                                          Right side

He thought that such a pair of drawings would give enough information to be able to re-build the block building later (but he never tried it).

Years later, looking again at the drawings, he realized that this was not the case: from most pairs of drawings, he was able to construct more than one building that had the same outlines (front and right side) as the original one. He found out that from every (front, side)-pair of drawings that he had made, he could construct a `minimal' building, one that has the same outlines as the original building and contains a minimal number of blocks N (so it was not possible to construct a building with the same outlines with less than N blocks). Furthermore, he could add more blocks to this minimal building, so that the outlines remained the same, up to the point that he had added M () blocks and he had a `maximal' building, one that still had the same outlines as his minimal one, and adding one extra block would result in a building with a different outline (so there are no buildings with the same outlines that contain more than N + M blocks).

As an example, these are minimal and maximal buildings for the drawings shown above. In this case, N = 7 and M = 10. Minimal Building                                                                      Maximal Building

Matty started determining the N and M for every pair of drawings he had made, but soon he found this task to be tedious. Now he asks you to write a program that does the job for him!

Input Specification

The input contains on the first line the number of test cases. Each test case starts with a line containing only the size of the table K. The next pair of lines each contain the description of one drawing. Each description consists of K non-negative integers separated by spaces. Each number indicates the height of the corresponding projection of a stack of blocks in the drawing. The description of the front drawing always precedes the description of the right side drawing. From each pair of drawings at least one block building can be constructed.

Output specification

For each test case output the following line:

Matty needs at least N blocks, and can add at most M extra blocks.

Sample Input

2
4
2 0 3 1
1 1 2 3
1
1
1

Sample Output

Matty needs at least 7 blocks, and can add at most 10 extra blocks.
Matty needs at least 1 blocks, and can add at most 0 extra blocks.