CS Ed Week Programming Challenge 2016

Purdue University's Computer Science K-12 Outreach program held its fourth high school programming challenge during the week of December 5th-11th, 2016. 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 over 60 solutions from 63 students at 12 different schools from across Indiana. This is the largest number of students we have ever had for one of our challenges! The students wrote solutions using Java, Python, VB, Haskell 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 Brian Bettag, Chad Bobb, Vicki Davis, Summer Ehresman, Lisa Heid, Mindy Johns, Peter Morey, Karen Podell, Raegan Towne, and Donna Wilk.

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 some Purdue Computer Science swag and a certificate for their accomplishment.

Problem 1: Repeat Ranker

Purdue Alumnus Robbie Roberts (class of ’77) loves repetition almost as much as he loves numbers. In his free time, he likes to rank numbers based on his own simple system with the following rules. Each number is examined for repeated numbers. Those that contain at least one repeat are compared, and the highest value repeat is ranked first. If two numbers contain the same repeated value, the number with more repeats is ranked higher. If each number has the same repeats of the same value, the larger overall value is ranked higher. For numbers with multiple repeated digits, only the largest numerically ranked repeat is considered. Robbie has gotten awfully tired of doing this ranking by hand, so he wants you to develop a program that takes a string of unique integers and returns their ranking. 

Best solution by Tanner Wilhelm, Max Newport, and Saransh Garg from Center Grove High School in Greenwood, IN. Sponsored by Mrs. Summer Ehresman. Solution written in Java.

import java.util.*;
public class CSEW_1
{
    public static String repeatRanker(String input)
    {
        input=input+','; //  565,4545,453,34534 becomes 565,4545,453,34534, to allow for sorting each number from start to comma

        String occstring=input; //creates version of input that can be edited while preserving original string
        int occs;  //number of number strings entered 

        for(occs=0;occstring.indexOf(",")>0;occs++) //counts number of commas in the string, which is same as number of number strings
        {
            occstring=occstring.substring(occstring.indexOf(",")+1);
        }

        int[] num= new int[occs];  //array for the repeated number, with slot for each number string
        int[] repeat= new int[occs];  //array for number of times that the highest number is repeated, with slot for each number string
        int[] vals= new int[occs];  //array for the int value of the number string, with slot for each number string
        for(int c=0;c<occs&&input.indexOf(",")>0;c++)//collects values, highest repeated number, and number of repeats into above arrays
        {
            int reps=0;//number of times the highest number is repeated
            int high=-1; //highest number repeated (starts at 0 so that 0 can be distinguished from no repeated numbers
            String single= input.substring(0,input.indexOf(",")); //selects the first number string in the full string
            int value=Integer.parseInt(single); //int value of theb number string

            for(int x=0;x<single.length()-1;x++) //collects first number of the number string
            {
               int check=Character.getNumericValue(single.charAt(x)); //number at x in the number string
               if(check!=high) //if the number has not already been counted once
                {
                    for(int y=x+1;y<single.length();y++) //compares the number at x to the numbers after x, at y
                    {
                        int r=Character.getNumericValue(single.charAt(y)); //number at y, which is always after x
                        if(check==r && check==high) //if x number is the highest, and equals the y number, then add 1 to the number of repeats
                        {
                            reps++;
                        }
                        else if(check>high&&check==r) //if x number is higher than the highest, set a new high and reset the repeats to 2(one for x and one for y)
                        {
                            reps=2;
                            high=check;
                        }
                    }
                }
            }

            input=input.substring(input.indexOf(",")+1); // removes the first number string from the whole string 
            num[c]=high; //adds the highest number repeated to an array at the location of the number string (c)
            repeat[c]=reps;  //adds the number of times repeated to an array at the location of the number string (c)
            vals[c]=value;  //adds the value to an array at the location of the number string (c) 
        }
        

        //////////////////////////////////////////////////////////////////////////////////////////////////////////////
        int[] ranks=new int[occs];  //creates an array for the rank number of the number strings, with slots for each number string

        for(int d=0;d<occs;d++) //compares each number string by referencing the location of the number string in the various arrays
        {
            int rank=1; //int value of the rank, starts at 1 with 1 being the highest
            
            for(int e=0;e<occs;e++)//compares each number string to all the other number strings in the array, adding to rank if any are higher
            {
                if(num[e]>num[d]) //if the number repeated is higher, add to rank
                    rank++;
                if(num[e]==num[d]&&repeat[e]>repeat[d]) //if the number repeated is equal but the number of repeats is higher, add to rank
                    rank++;
                if(num[e]==num[d]&&repeat[e]==repeat[d]&&vals[e]>vals[d])  //if number repeated and repeats are equal but the value is higher, add to rank
                    rank++;
            }
            
            ranks[d]=rank; //adds rank to the array at corresponding location of the number string 

        }
        return Arrays.toString(ranks).replace('[',' ').replace(']',' ');  //returns the rank array as a string and removes the two brackets at either end
    }
}

Other solutions: Bryan McClain (Pike HS - Indianapolis, IN; Taylor Horne and Jacob Lovrinic (Center Grove HS - Greenwood, IN).

Problem 2: Base-2 Currency

In a surprise decision, the next U.S. president has decided to select a computer scientist as his treasury secretary (it’s true, I read it in a tweet!). Computer scientists love the number 2, so her first initiative is to explore whether we should shift our financial system to one using base-2 numbers. The deciding factor will be whether the new system using bills $1, $2, $4, $8, $16, $32, $64, and $128 (vs. the current $1, $5, $10, $20, $50, $100) will lead to citizens carrying fewer bills in their wallet. Help the treasury secretary by writing a function that compares the current system to the base-2 system. The function will receive a single input representing the total dollars held by a citizen. Assume that you will always minimize the bills within the given system. Ties should report false as they do not represent an improvement.

Best solution by Sean Fisher from NorthWood HS in Nappannee, IN. Sponsored by Mr Peter Morey. Solution written in Haskell.

--General case function to count number of bills needed for a given set of denominations
checkBills dollars totalBills index divisors | index < (length divisors) = checkBills (mod dollars (divisors !! index)) (totalBills + (div dollars (divisors !! index))) (index + 1) divisors | otherwise = totalBills
--Function to compare two currency types
compareCurrency dollars = (checkBills dollars 0 0 [128,64,32,16,8,4,2,1]) < (checkBills dollars 0 0 [100,50,20,10,5,1])

Other solutions: Akul Vijayvargiya and Eleanor Bentson (Center Grove HS - Greenwood, IN); Nick Fuller, Jimmy Phillips and Tanner Graves (Center Grove HS - Greenwood IN); Akhil Isanaka and Ben Barnard (Center Grove HS - Greenwood IN); Dex Keizers (Center Grove HS - Greenwood IN); Tanner Wilhelm, Max Newport, and Saransh Garg (Center Grove HS - Greenwood IN); Emily Simon, Cameron Todd, and Johnathan Hawley (Center Grove HS - Greenwood IN); Cory Snyder, Mary Hamilton and Andrew Stafford (Center Grove HS - Greenwood IN); Jacob Thrasher and Austin Freay (Center Grove HS - Greenwood IN); Jacob Bridgewater, Sam Brooks, and Noah Weier (Center Grove HS - Greenwood IN); Aaron Brookhouse (Chesterton HS - Chesterton, IN); Lucas Klein (Chesterton HS - Chesterton, IN); Alex Rich (New Albany HS - New Albany, IN); Ian Kimbell (New Albany HS - New Albany, IN); ZeCong Liang (New Albany HS - New Albany, IN); Jadon Steinmetz (NorthWood HS - Nappannee, IN); Ben Owen (Perry Meridian HS - Indianapolis, IN); Clare Brennan (Perry Meridian HS - Indianapolis, IN); Logan Kreider (Perry Meridian HS - Indianapolis, IN); Nick Osterburg and Erika Schellenberger (Perry Meridian HS - Indianapolis, IN); Bryan McClain (Pike HS - Indianapolis, IN); Tyler Ruth (Pike HS - Indianapolis, IN).

Problem 3: pSociety

Steganography is the art of hiding messages in plain sight. A Purdue student named Sneaky Pete was caught passing messages in class. Facing the threat of defragmenting all of the department’s hard drives, Pete has revealed his steganographic scheme, and has admitted to being part of the covert pSociety organization feared by students across campus. Help us decipher future pSociety messages by writing a function that applies Pete’s scheme to an input message to reveal the hidden communication. The rules are as follows. For words with odd numbers of letters, add the middle letter to the end of the solution text. For words with even numbers, reverse the current solution text entirely. 

Best solution #1 by Theresa Perez from Lebanon High School in Lebanon, IN. Sponsored by Mrs. Vicki Davis. Solution written in Python.

def pSociety(phrase):
    list=[]
    f=0
    phrase=phrase+" "
    solution = ""
    for x in range(f,len(phrase)):
        s=phrase[x]
        if(s==" "):
            l= x - f
            word=phrase[f:x]
            f=x+1
            if(l%2 == 1):
               ml=(len(word)//2)
               middle=word[ml]
               list.append(middle)
            if(l%2==0):
                list.reverse()
    for y in list:
        solution += y
    return solution

Best solution #2 by Bryan McClain from Pike High School in Indianapolis, IN. Sponsored by Mr. Chad Bobb. Solution written in Visual Basic.

'Decrypt the secret message
    Private Sub DecryptButton_Click(sender As System.Object, e As System.EventArgs) Handles DecryptButton.Click
        'Output the secret message
        DecryptedMessageTextBox.Text = Decrypt(EncryptedMessageTextBox.Text)
    End Sub

    'Decrypt the message
    Private Function Decrypt(ByVal message As String) As String

        'Split the message based on words
        Dim AllWords() As String = message.Split(" ")

        Dim SecretMessage As String = ""    'The output message

        'Read though each word and do the appropirate code
        For Each Word As String In AllWords

            'Make sure the word is not null
            If Word.Length > 0 Then

                'Test for odd words (Not normal words - lol jk :))
                If (Word.Length Mod 2 = 1) Then
                    'Add the middle letter
                    SecretMessage += Word.Substring(Math.Floor(Word.Length / 2), 1)
                Else
                    'Reverse the message
                    SecretMessage = StrReverse(SecretMessage)
                End If
            End If
        Next

        Return SecretMessage

    End Function

Other solutions: Marco Copat and Ethan Bomont (Center Grove HS - Indianapolis, IN); Dex Keizers (Center Grove HS - Indianapolis, IN); Jacob Lovrinic and Taylor Horne (Center Grove HS - Indianapolis, IN); Evan Ruder and Logan Underwood (Center Grove HS - Indianapolis, IN); Cory Snyder, Mary Hamilton and Andrew Stafford (Center Grove HS - Indianapolis, IN); Jacob Thrasher and Austin Freay (Center Grove HS - Indianapolis, IN); Aaron Brookhouse (Chesterton HS - Chesterton, IN); Alex Stark, Connor Dailey and Andrew Martin (Chesterton HS - Chesterton, IN); Camryn Davis (Lebanon HS - Lebanon, IN); Alex Rich (New Albany HS - New Albany, IN); Ian Kembell (New Albany HS - New Albany, IN); Will Boland (Noblesville HS - Noblesville, IN); Ben Kuzel and Oliver Krefta (Noblesville HS - Noblesville, IN); Jason Steinmetz (NorthWood HS - Nappannee, IN); Sean Fisher (NorthWood HS - Nappannee, IN); Ben Owen (Perry Meridian HS - Indianapolis, IN).