CS Ed Week Programming Challenge 2017
Purdue University's Computer Science K-12 Outreach program held its fifth high school programming challenge during the week of December 4th-10th, 2017. 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.
This year we received 24 solutions from 45 students at 6 different schools from across Indiana. The students wrote solutions using Java, Python and Javascript.
In particular, we'd like to thank all of the teachers for their support of their students and their efforts in the classroom. This year's group of teachers with students submitting solutions included Summer Ehresman, Peter Morey, Seth Pizzo, Karen Podell, Kristin Scott, and Mike Spock.
Listed below are the solutions for each of the winners from this year's competition along with their names, schools and sponsoring teacher. Each student that correctly solves one of the problems will receive some Purdue Computer Science swag and a certificate for their accomplishment.
Problem 1: Math Magic
Purdue Alumnus Abbie Cadabra (class of ’03) is an aspiring magician as well as a computer scientist. Among her famous tricks are the “Amazing Overflowing Integer”, the “Vanishing Object Reference”, and the “Saw the String in Half” trick. Abbie would like to develop a new trick that uses math and an algorithm to wow her audience. In the trick, she asks three volunteers to produce a random three digit number. The volunteers then create a six-digit number by repeating the digits. Abbie then asks each volunteer to pick a card and has them divide their number by whichever card they pick (the numbers on the cards are 77, 143, and 91). The volunteers are amazed when they discover that these three numbers divide their 6-digit numbers evenly! Abbie then multiplies these three integer results together and divides by 1001, while asking the volunteers to multiply their original 3-digit numbers together. The volunteers are amazed again when the two independent results are the same! Write a program that performs Abbie’s trick. Your output will reveal the calculations to the “Howie Doodats” running the program.
Best solution by TJ Gregory from Bloomington South High School in Bloomington, IN. Sponsored by Mr. Seth Pizzo. Solution written in JavaScript.
var CARDLIST = [77,143,91];
function start(){
CARDLIST.sort(() => Math.random() * 2 - 1); //shuffles Deck
var numThreePerson1 = getThreeDigitNumber();
var numThreePerson2 = getThreeDigitNumber();
var numThreePerson3 = getThreeDigitNumber();
print("\n");
magicDivision(numThreePerson1,numThreePerson2,numThreePerson3);
}
function magicDivision(numThreePerson1,numThreePerson2,numThreePerson3){
var numSixPerson1 = createASixDigitNumberByRepeatingTheDigits(numThreePerson1); //repeats person 1's Number to get a six digit number
print("\n");
var numSixPerson2 = createASixDigitNumberByRepeatingTheDigits(numThreePerson2); //repeats person 2's Number to get a six digit number
print("\n");
var numSixPerson3 = createASixDigitNumberByRepeatingTheDigits(numThreePerson3); //repeats person 3's Number to get a six digit number
print("\n");
var cardPerson1 = pickCard(); //person 1 picks a card
println("Persons one's card is "+cardPerson1);
var ans1 = divideNumberByCard(numSixPerson1,cardPerson1);
print("\n");
var cardPerson2 = pickCard(); //person 2 picks a card
println("Persons two's card is "+cardPerson2);
var ans2 = divideNumberByCard(numSixPerson2,cardPerson2);
print("\n");
var cardPerson3 = pickCard(); //person 3 picks the last card
println("Persons three's card is "+cardPerson3);
var ans3 = divideNumberByCard(numSixPerson3,cardPerson3);
var ans3 = divideNumberByCard(numSixPerson3,cardPerson3);
println("\nNow we will multiply these results together and divide the answer by 1001");
multiplyResultsAndDivide(ans1,ans2,ans3);
println("\nNow lets multiply the original numbers.");
multiplyBaseNumbers(numThreePerson1,numThreePerson2,numThreePerson3);
print("Wow. They are the same");
}
function getThreeDigitNumber(){ //asks for a three digit number won't allow any number that does not have three digits
var num = readInt("Please input a three digit number: ");
var i = 0;
while(num.toString().length!=3){
if(i>=10){
println("A three digit number is a number which has 3 numbers in it. Ex:123 ");
}
num = readInt("Please input a three digit number: ");
i++;
}
return num;
}
function createASixDigitNumberByRepeatingTheDigits(num){
var sixDigit = num+""+num;
println("Your number combinded is "+sixDigit);
return sixDigit;
}
function pickCard(){
var card = CARDLIST.pop();
return card;
}
function divideNumberByCard(num,card){
println(num+" / "+card+" = "+num/card+ "\nWow! Much divisable!");
return num/card;
}
function multiplyResultsAndDivide(a,b,c){
var mult = a*b*c;
var divi = mult/1001;
println(a+" * "+b+" * "+c+" = "+mult);
println(mult + " / " + "1001" + " = " + divi);
println("\nRemember the number: "+divi);
}
function multiplyBaseNumbers(a,b,c){
var mult = a*b*c;
println(a+" * "+b+" * "+c+" = "+mult);
}
Other solutions: None.
Problem 2: Closest Prime
Your archnemesis, the nefarious Dr. Indivisible, has recently knocked you hard on your noggin. When you awaken, you find yourself stuck in a labyrinth of sorts, consisting of a long hallway with numbered doors. The only way to escape is to find the closest door that is a prime number in either direction. If you choose incorrectly, the door opens to a fiery trap. In the case of a tie, you should continue on to the door with the next closest prime, as Dr. Indivisible has rigged each of the two closest primes’ doors with a fiery trap. Write a program that gives you the closest prime given a starting room number, n, thus avoiding death.
Best solution by Cade Henschen and Jacob Schmitt from NorthWood HS in Nappannee, IN. Sponsored by Mr Peter Morey. Solution written in Python.
#Import Declarations
from math import floor, sqrt
#Method asking for the n value, and thusly sending them to be checked.
def Input():
num = raw_input("Please enter the 'n' value. ")
#This try, except, else block is data validation to check for anything but integers
try:
int(num)
except ValueError:
print ("Sorry, that's not an integer. Please try again.")
Input()
else:
num = int(num)
if num != 1:
RightCheck(num, num)
LeftCheck(num, num)
#Catch statement to ensure one isn't processed
elif num == 1:
print ("Technically one isn't a number to be considered in prime number determination, please try again with a integer greater than one.")
Input()
#Method to find the closest prime number to the right of n, using the PrimeCheck method and counting distance
def RightCheck(RightNum, n):
if PrimeCheck(RightNum) == True:
global RightDistance
RightDistance = RightNum - n
global Right #This global variable is used later so the flexibility of RightNum can stay versitile.
Right = RightNum
else:
RightDistance = RightNum - n
RightCheck(RightNum + 1, n)
#Method to find the closest prime number to the left of n, using the PrimeCheck method and counting distance
def LeftCheck(LeftNum, n):
if PrimeCheck(LeftNum) == True:
global LeftDistance
LeftDistance = n - LeftNum
global Left #This global variable is used later so the flexibility of LeftNum can stay versitile.
Left = LeftNum
else:
LeftDistance = n - LeftNum
LeftCheck(LeftNum - 1, n)
pass
#Method which is referenced in LeftCheck and RightCheck to validate the integer's condition of being prime
def PrimeCheck(n):
numEnd = int(floor(sqrt(n)) + 1)
for i in range(2, int(numEnd + 1)):
if i == numEnd and int(n) % i != 0:
return True
elif int(n) % i == 0:
return False
break
else:
pass
#Method that ultimately gives the feedback to the user of closest number.
def CheckClosest(DistRight, DistLeft, PrimeRight, PrimeLeft):
#Since 1 is not prime, the program will reference the closet prime on the right, since going beyond zero invalidates finding prime numbers.
if PrimeLeft == 1:
print ("The number %s is your closest prime number.") % (PrimeRight)
#If the resulting prime numbers are equal in distance, this case repeats the process till it returns with a definitively closer prime number.
elif DistLeft == DistRight:
TiePrime(PrimeRight, PrimeLeft)
Input()
CheckClosest(RightDistance, LeftDistance, Right, Left)
#The following two cases simply spit back
elif DistLeft > DistRight:
print("The number %s is your closest prime number.") % (PrimeRight)
Input()
CheckClosest(RightDistance, LeftDistance, Right, Left)
elif DistLeft < DistRight:
print("The number %s is your closest prime number.") % (PrimeLeft)
Input()
CheckClosest(RightDistance, LeftDistance, Right, Left)
#This case just ensures the n value isn't prime already and returns to the original input method.
elif DistLeft == 0 and DistRight == 0:
print("You already have a prime number, %s.") % (num)
Input()
CheckClosest(RightDistance, LeftDistance, Right, Left)
#This method processes a tie till
def TiePrime(PriRight, PriLeft):
RightCheck(PriRight + 1, PriRight)
LeftCheck(PriLeft - 1, PriLeft)
CheckClosest(RightDistance, LeftDistance, Right, Left)
#Code to kickstart the program, the rest is self-contained till the program is executed.
Input()
CheckClosest(RightDistance, LeftDistance, Right, Left)Other solutions: None
Problem 3: Word Remix
Remixing Romil is one of the most promising students at Purdue, but he often finds himself bored during lecture. Reflecting on advice his dad gave him once (“Remember, ‘hired’ and ‘fired’ are only one letter apart!”), Romil decides to challenge himself with a puzzle. The goal is to transform one word into another by adding and removing letters. The rules for transforming a word are as follows. A letter can be added or removed from the front or end of the existing word, or any letter can be moved from inside of the word to the front or end of the word. Each of these counts as a single step. Write a program that transforms one word to a second word following these rules in as few steps as you can, returning output detailing the steps taken.
Best solution by Benjamin Tait from Bloomington South High School in Bloomington, IN. Sponsored by Mr. Seth Pizzo. Solution written in JavaScript.
var stepNumber = 0;
var previousStep = "";
function start() {
//get imput for the start and end words
var word1 = readLine("What is the starting word? ");
var word2 = readLine("What is the final word? ");
//print the steps to change word1 into word2
println(wordRemix(word1, word2));
}
function wordRemix(word1, word2) {
// create a variable to store the solution
var solution = "";
// create arrays for the words
var currentWord = createArray(word1);
var goalWord = createArray(word2);
//add the 0th step to the solution string
var currentStep = step(stepNumber, currentWord);
if (currentStep != previousStep) {
solution += step(stepNumber, currentWord) + ", ";
previousStep = step(stepNumber, currentWord);
}
//remove all letters from the current word that are not in the goal word
for (var i=currentWord.length -1; i >= 0; i--) {
//check if letter is in goal word
if (goalWord.indexOf(currentWord[i]) == -1) {
//if it is not in goal word, move the letter to the end of the word
currentWord.push(currentWord.remove(i));
//add the step to the solution
var currentStep = step(stepNumber, currentWord);
if (currentStep != previousStep) {
stepNumber++;
solution += step(stepNumber, currentWord) + ", ";
previousStep = step(stepNumber, currentWord);
}
//delete the letter
currentWord.pop();
//add the step to the solution
var currentStep = step(stepNumber, currentWord);
if (currentStep != previousStep) {
stepNumber++;
solution += step(stepNumber, currentWord) + ", ";
previousStep = step(stepNumber, currentWord);
}
}
}
//add letters to the current word so that it contains the same letters as the goal word
if (currentWord != goalWord) {
//loop through the goal word
for (var i=0; i < goalWord.length; i++) {
//check if the number of a certain letter in the goal word is equal
//to the number of that letter in the current word
if (count(goalWord[i], goalWord) > count(goalWord[i], currentWord)) {
//if it isn't, add the letter
currentWord.push(goalWord[i]);
//add the step to the solution
var currentStep = step(stepNumber, currentWord);
if (currentStep != previousStep) {
stepNumber++;
solution += step(stepNumber, currentWord) + ", ";
previousStep = step(stepNumber, currentWord);
}
}
}
}
//rearrange the letters in the current word to match the goal word
if (currentWord != goalWord) {
var correctLetters = -1;
//see how many of the letters at the beginning of the word are correct
for (var i=0; i < goalWord.length; i++) {
//check if a letter in the current position is in the same spot as the one in the goal word
if (currentWord[i] == goalWord[i]) {
//record how many letters in the beginning of the word are correct
correctLetters = i;
}
else {
//break the loop when the first incorrect letter is reached
break;
}
}
//starting at the first incorrect letter, rearage the letters at the end of the word to be in the right order
for (var i=correctLetters+1; i < goalWord.length; i++) {
//move each letter to the end of the word in the correct order to arrange the letters
currentWord.push(currentWord.remove(currentWord.indexOf(goalWord[i])));
//add the step to the solution
var currentStep = step(stepNumber, currentWord);
if (currentStep != previousStep) {
stepNumber++;
solution += step(stepNumber, currentWord) + ", ";
previousStep = step(stepNumber, currentWord);
}
}
}
//sometimes incorrect letters are left at the beginning of the word and need to be removed
while ((currentWord[0] != goalWord[0]) || (currentWord[1] != goalWord[1])) {
//remove the incorrect letter
currentWord.remove(0);
//add the step to the solution
var currentStep = step(stepNumber, currentWord);
if (currentStep != previousStep) {
stepNumber++;
solution += step(stepNumber, currentWord) + ", ";
previousStep = step(stepNumber, currentWord);
}
}
//return the solution string
return solution;
}
//this function creates an array from a string
function createArray(string) {
var array = [];
//loop through the string and push each letter into an array
for (var i = 0; i < string.length; i++) {
array.push(string.charAt(i));
}
//return the array
return array;
}
//this function creates a 'step' from the current word
function step(number, array) {
//create a string for the step
var step = "";
//start the step with the step number followed by a period
step = number + "."
//add the word to the step by looping through the array of letters and adding them
for (var i=0; i<array.length; i++) {
step += array[i];
}
//return the step
return step;
}
//counts the amount of times a letter appears in an array
function count(letter, array) {
//initialize the count at 0
var count = 0;
//loop through the array and count how many times the letter occurs
for (var i = 0; i<array.length; i++) {
if (array[i] == letter) {
count++;
}
}
//return the total count
return count;
}Other solutions: Vamshi Balanga (Columbus North HS - Columbus, IN).