CS Ed Week Programming Challenge 2018

Purdue University's Computer Science K-12 Outreach program held its sixth high school programming challenge during the week of December 3rd-9th, 2018. 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 15 students at 6 different schools from across Indiana. The students wrote solutions using C#, C++, GO, Java, Javascript, Kotlin, PHP, Python, Ruby and Rust.

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 Jacqui Kane, Peter Morey, Amanda Muller, Seth Pizzo, Karen Podell, and John Todor.

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: Alumni Phone Numbers

Purdue Alumnus Mike Donations (class of ’81) works for the alumni association and is creating a calling list to contact recent graduates about contributing to a scholarship fund. Unfortunately, the various contact information formats that the alumni provided upon graduation don’t fit the format needed by the auto-dialing program Mike uses. The correct format should have the form “(XXX) XXX-XXXX”. The file contains phone numbers stored as some combination of 10 digits, mixed with other characters including parentheses, dashes, periods, whitespace, etc. Write a program that takes a string of characters and returns a phone number in the format shown above.

Best solution by Andrew Davis from R. Nelson Snider High School in Fort Wayne, IN. Sponsored by Mr. John Todor. Solution written in Python.

def formatPhone(number): 
    '''The following variable filters out all the numbers in the string parameter using a lambda function, checking whether or not each
    character in the parameter is a digit.'''
    phoneNumber = filter(lambda phoneNumber: phoneNumber.isdigit(), number)
    '''The following if-else statement determines if whether or not the newly filtered numbers
    in the string can be made into a 10-digit phone number.'''
    if len(phoneNumber) != 10: #If a phone number can't be made, the function prints that the phone number is invalid.
        print('Number is invalid.')
    else: #If the phone number can be made, it is formatted into (XXX) XXX-XXXX
        return str('(') + phoneNumber[:3] + str(') ') + phoneNumber[3:6] + str('-') + phoneNumber[6:]

Other solutions: Katrina Brown (Bloomington South HS - Bloomington, IN); Noah Brown (NorthWood HS - Nappanee, IN); Trevor Cunningham (Snider HS - Fort Wayne, IN); Joseph Didion (LaPorte HS - LaPorte, IN); Jack Foster and Alex Rocha (Bloomington South HS - Bloomington, IN); Akio Fujito (Carmel HS - Carmel, IN); Adam Ratzman (Carmel HS - Carmel, IN); Wyatt Roberson and Alex Puckett (Bloomington South HS - Bloomington, IN); Jacob Schmitt (NorthWood HS - Nappanee, IN); Zoe Skiver (Snider HS - Fort Wayne, IN)

Problem 2: Interstellar Positioning System

2) The gallivanting superhero known as Galaxy Girl (real name, Lakshmi Lane) is searching a series of planets to find precious stones needed to restore her powers and save Earth from an impending invasion. She turns to you, her trusty sidekick “Code Kid”, to show her where to go. Your IPS (interstellar positioning system) can provide your current position, the location of your target planet, and any planets that are positioned close to your flight path. You know, of course, that if you fly close enough to any planet, the gravitational pull will change your trajectory. Data for each planet comes with three pieces of data, the x-y coordinate pair that locates the planet (three points can always be considered in a 2D plane, of course), and the distance within which the planet’s gravity can impact your ship. Write a program that takes a string of coordinates / gravity effects and return a coordinate pair, using whole numbers, as a string representing the initial position that the ship should fly towards, minimizing the total travel and avoiding any gravitational effects. If the intermediate planets have no effect, you should return the target planet coordinates. You may assume that the input lists locations starting from your position and ending with your target.

Best solution by Joseph Didion from LaPorte High School in LaPorte, IN. Sponsored by Mrs Amanda Muller. Solution written in JavaScript.

const is_gravity_inclusive = true; ///IMPORTANT!!!

const dist = (x1, x2, y1, y2) => ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** .5;
//basic function for computation of distance of points on a 2D plane

var flyTo = args => {

	var [here, ...obstacles] = args.split `; `.map(v => v.slice(1, -1).split `,`.map(Number)),
		there = obstacles.pop();
	//this formats, sanatizes, and sets the input into a more JS friendly format.


	//START of section to determine the area which everything is in
	let XArray = [],
		YArray = []
	for (let a of [here, there, ...obstacles]) {
		let [x, y] = [a[0], a[1]]
		if (a[2]) {
			XArray.push(x + a[2])
			XArray.push(x - a[2])
			YArray.push(y - a[2])
			YArray.push(y + a[2])
		} else {
			XArray.push(x)
			YArray.push(y)
		}
	}
	var minX = Math.min(...XArray) - 1,
		maxX = Math.max(...XArray) + 1,
		minY = Math.min(...YArray) - 1,
		maxY = Math.max(...YArray) + 1;

	//start heavy computational section
	var ops = [
			[here[0], here[1], 0]
		], //list of options available to move from
		//options are formatted like so: [X_COORD, Y_COORD, DIST, [FIRST_X,FIRST_Y]]
		successful = [],
		iter = (maxX - minX) * (maxY - minY) * 800000,
		len = 1;

	for (var i = 0; i < len && i < iter && successful.length < 400; ++i) {

		if (!intCircles(obstacles, ops[i][0], ops[i][1], ...there)) {
			if (i === 0)
				return `(${there})`; //If it starting 'here' simply return target coords

			//create an array of successful entries attemps, their distance, and starting coords
			successful.push([ops[i][3], ops[i][2] + dist(ops[i][0], ops[i][1], ...there)])
			continue;
		}

		for (var y = minY; y <= maxY; ++y)
			for (var x = minX; x <= maxX; ++x)
				if (!intCircles(obstacles, ops[i][0], ops[i][1], x, y)) { //check every point in grid for validity of mvmnt
					ops.push([ //if a valid move than append that to operating list of points
						x,
						y,
						ops[i][2] + dist(ops[i][0], ops[i][1], x, y), //distance is totaled
						ops[i][3] || [x, y] //if orig. coords not set, set it to current coords
					]);
					++len //increment options array length
				}
	}
	if (successful.length)
		return '(' + successful.sort((A, B) => A[1] - B[1])[0][0].join `,` + ')' //Sort the successful arrays by distance

	return "No possible valid route within " + iter + " iterations!"
}


function intCircles(circles, ...points) {
	intersect = false
	if (points[0] == points[2] && points[1] == points[3]) return true;
	for (let circle of circles) {
		intersect |= intersectCircle(...points, ...circle)
		if (intersect) return true
	}
	return false;
}

function intersectCircle(x1, y1, x2, y2, cx, cy, r) {
	// Formula For Finding Intersecting Segment to a circle
	/* 
	I got the equation from here
			https://math.stackexchange.com/a/275537
	*/
	//
	if (is_gravity_inclusive && (dist(x1, cx, y1, cy) <= r || dist(x2, cx, y2, cy) <= r)) return true;
	//test if points themselves are in(/on if inclusive) circle
	x1 -= cx;
	x2 -= cx;
	y1 -= cy;
	y2 -= cy;
	c = x1 ** 2 + y1 ** 2 - r ** 2;
	b = 2 * (x1 * (x2 - x1) + y1 * (y2 - y1));
	a = (x2 - x1) ** 2 + (y2 - y1) ** 2;
	d = b ** 2 - 4 * a * c;
	//^ this formats it as a basic quadratic ^
	//d is going to be divided to test for real answers 
	if (is_gravity_inclusive ? d < 0 : d <= 0) return false;
	s = d ** .5;
	//s: squared
	t1 = (-b + s) / (2 * a);
	t2 = (-b - s) / (2 * a);
	//check for both 't' values to see if either answer is real, if so return true
	return ((0 < t1 && t1 < 1) || (0 < t2 && t2 < 1));

}

Other solutions: Adam Ratzman (Carmel HS - Carmel, IN)

Problem 3: Top Customers

Café Arré’s customers with rewards accounts are assigned a unique ID when they sign up. The ID is stored each time a customer makes a purchase in the café’s database. As a CS Ed Week promotion, the top 3 customers at each store during this week are given rewards. Write a program that takes a list of purchases by customer ID and returns a list of the top 3 customer IDs in order of purchases from left-to-right (list position 0 should be the top customer). In case of a tie, the customer that made the earliest purchase should appear in the output first. In case of a tie for the third position, include as many tied customers as necessary.

Best solution by Adam Ratzman from Carmel High School in Carmel, IN. Sponsored by Ms. Jacqui Kane. Solution written in Kotlin.

fun topCustomers(purchases: List) = purchases.asSequence().groupBy { it }.map { it.key to it.value.size }
        .sortedByDescending { it.second }
        .let { groups ->
            listOf(groups[0].first, groups[1].first) +
                    (2..groups.lastIndex).filter { groups[it].second == groups[2].second }.map { groups[it].first }
        }