CS Ed Week Programming Challenge 2014
Purdue University's Computer Science K-12 Outreach program held its second high school programming challenge during the week of December 8th-14th, 2014. The week was chosen in support of the events of Computer Science Education Week.
Computer Science Education Week was started as an attempt to help raise the profile of computer science in K-12 classrooms. The dates in December were selected in order to honor the birthday of Grace Murray Hopper, the woman who first developed a high-level programming language, as well as a compiler for converting code written in that language to instructions that a computer processor can understand.
The programming challenge offered three programming problems for students to solve during the week. These problems were designed to challenge students' abilities to think algorithmically and write solutions that address the four tenets of software design. These include a program's correctness, design, style and efficiency.
Listed below are the solutions for each of the winners from this year's competition along with their names, schools and sponsoring teacher. Each winning student will receive a Purdue Computer Science t-shirt and a certificate for their accomplishment.
Problem 1: Sortence
Purdue alumnus Norman Numbers (class of ’78) has dedicated his life to finding the “most valuable sentence ever written”. Norman’s philosophy is that a sentence has a numerical value based on the sum of all individual number values that appear within it. If a sentence contains no numbers, it is ranked below all sentences that include numbers, and then placed in order by the total number of letters that it contains. Write a function that takes a string representing a paragraph of text and returns a string representing the comma separated positions of each sentence appearing in that paragraph in order from greatest to least.
Best solution by Justin Garrard and Griffin Steffy from Lebanon High School in Lebanon, IN. Sponsored by Ms. Vicki Davis. Solution written in Python.
def sortence(stin = ""):
nums = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
rnums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sentences = []
rankin = []
order = []
shifted = []
ind = 0
for i in range(len(stin)):
if(stin[i] == "." or stin[i] == "?" or stin[i] == "!"):
sentences.append(stin[ind:i+1])
ind = i + 1
for x in sentences:
c = 0
svalue = 0
value = 0
while (c < len(x)):
wvalue = ""
if(x[c] in nums):
while(x[c] in nums):
wvalue = wvalue + x[c]
c = c + 1
else:
c = c + 1
if(len(wvalue) > 0):
exp = 0
for t in range(len(wvalue)-1, -1, -1):
value = value + rnums[nums.index(wvalue[t])] * 10**exp
exp = exp + 1
svalue = svalue + value
value = 0
rankin.append((svalue, sentences.index(x), len(x)))
for q in range(0,100):
sorted = False
while not sorted:
sorted = True
for a in range(0, len(rankin)-1):
if rankin[a][0] > rankin[a + 1][0]:
sorted = False # We found two elements in the wrong order
hold = rankin[a + 1]
rankin[a + 1] = rankin[a]
rankin[a] = hold
elif rankin[a][0] == rankin[a+1][0]:
if rankin[a+1][2] < rankin[a][2]:
sorted = False
hold2 = rankin[a+1]
rankin[a+1] = rankin[a]
rankin[a] = hold2
for x in rankin:
order.append(x[1]+1)
return(order)
Other solutions: Megan McCullough (Lebanon HS - Lebanon, IN); Dallas Heil, Spencer Lanman, and Dustin Swonder (Richmond HS - Richmond, IN)
Problem 2: PIN Numbers
The First National Boiler Bank offers debit cards that are secured using a four-digit PIN. When signing up for a new account, users must select a number, but many people struggle with this choice. Write a function that generates a 4-digit PIN for a customer based on the following strategy. The user will input three numbers. Find the largest factor (not including the original number) for each number and multiply them together. If the result is greater than 9999, return the remainder when dividing by 10,000; otherwise return the product.
Best solution by Dallas Heil, Spencer Lanman, and Dustin Swonder from Richmond High School in Richmond, IN. Sponsored by Ms. Denise Selm. Solution written in Java.
public class PIN {
public static String pin(int a, int b, int c) {
int pin = largestFactor(a) * largestFactor(b) * largestFactor(c);
if (pin > 9999) {
pin %= 10000;
}
return String.format("%04d", pin);
}
private static int largestFactor(int n) {
int factor = 0;
for(int i = 2; i <= n; i++){
factor = n / i;
if (n % factor == 0) {
break;
}
}
return factor;
}
}
Other solutions: Bryan Battles, Andrew Bostock and Keith Jackson (New Albany HS - New Albany, IN); Justin Garrard and Griffin Steffy (Lebanon HS - Lebanon, IN); Megan McCullough (Lebanon HS - Lebanon, IN)
Problem 3: Trinary Numbers
The trinary number system involves three symbols (0, 1, 2) where each successive position is a lower power of 3. Write a function that takes two trinary numbers and produces the sum of these numbers in trinary as output.
Best solution #1 by Megan McCullough from Lebanon High School in Lebanon, IN. Sponsored by Ms. Vicki Davis. Solution written in Python.
test = 1
while test != 0:
count = 0
num1 = int(input("Enter first trinary number: "))
while num1 <0: num1="" a="" positive="" trinary="" number:="" for="" let="" in="" str="" :="" if="" 0="" and="" 1="" 2="" count="" 0:="" print="" input="" needs="" to="" be="" number="" else:="" test="0" makes="" sure="" the="" entered="" numbers="" are="" both="" while="" loops="" num2="" second="" making="" them="" same="" of="" slots="" first="" sec="len(str(num2))"> sec:
dif = first-sec
num2 = ('0'*dif) + str(num2)
elif sec > first:
dif = sec-first
num1 = ('0'*dif) + str(num1)
num1 = str(num1)[::-1]
num2 = str(num2)[::-1]
print()
sum = ''
z = 0
for slot in range (0, len(str(num1))):
x = int(num1[slot]) #takes the value for each number at that slot
y = int(num2[slot]) #this works only because num1 and num2 were made into strings with the same length
add = x+y+z
if add == 3:
sumpart = '0' # 3 --> 10
sum = sum + sumpart
z = 1
elif add == 4:
sumpart= '1' # 4 --> 11
sum = sum + sumpart
z = 1
elif add == 5:
sumpart= '2' # 5 --> 12
sum = sum + sumpart
z = 1
else:
sum = sum + str(add)
z = 0
#if it reaches the end and some of the value is a 1 carried it prints the what is carried
if z != 0 and add == 3 or add == 4:
sumpart = '1' #10 backward
sum = sum + sumpart
sum = sum[::-1]
num1 = num1[::-1]
num2 = num2[::-1]
print()
print("Trinary sum: " + sum)
Best solution #2 by Bryan Battles, Andrew Bostock, and Keith Jackson from New Albany High School in New Albany, IN. Sponsored by Ms. Mindy Johns. Solution written in Java.
import java.util.Scanner;
public class Trinary_Bostock_Battles_Jackson
{
public static void main(String[]args)
{
Scanner scan = new Scanner(System.in);
int num1, num2;
System.out.println("Enter two numbers in Trinary (seperated by a space).");
num1 = scan.nextInt();
num2 = scan.nextInt();
System.out.println("The sum in Trinary is: " + trinarySum(num1,num2));
}
public static int trinarySum(int x, int y)
{
int sum = 0;
int temp = x + y;
int loop = 0;
while (temp>0)
{
if (temp%10>=3)
{
sum += ((temp%10)-3)*Math.pow(10,loop);
temp +=10;
}
else
{
sum +=(temp%10)*Math.pow(10,loop);
}
temp/=10;
loop++;
}
return sum;
}
}
Other solutions: Justin Garrard and Griffin Steffy (Lebanon HS - Lebanon, IN); Dallas Heil, Spencer Lanham, and Dustin Swonder (Richmond HS - Richmond, IN)