TweetFollow Us on Twitter

Dec 01 Programmers Challenge

Volume Number: 17 (2001)
Issue Number: 12
Column Tag: Programmer's Challenge

by Bob Boonstra, Westford, MA

Parent-Teacher Conferences

If you have children in school, you are familiar with parent-teacher conferences. Little Johnny isn’t doing so well in French, or Algebra, or perhaps Advanced Calculus if your school has a gifted and talented program. Or Sally is doing very well in Subatomic Physics, and you’d like to hear her teachers tell you so.

I was reminded recently of a Challenge suggested by Ernst Munter to write code that would help schools schedule these conferences. Your Challenge this month is to arrange a set of parent-teacher conferences that maximize the parents’ satisfaction and minimize the amount of time wasted by both parents and teachers in between conferences.

You will be given three data sets to work with for each test case. The first, in a file childrenNN.txt (where NN is a number from 01 to the number of test cases), will have one line for each child in the school, containing the child’s name followed by the names of one or two parents. No child will appear on more than one line, and there will be no duplicate names of children. A sample would be the following:

Johnny Smith, Donald Smith, Marilyn Waters-Smith
Sally Jones,Samantha Jones

The second data set, in a file named teachersNN.txt, maps children to their teachers. Each line contains the name of a child, followed by the name of one of his/her teachers, followed by a number from 0 to 9 indicating the strength of the parents’ desire to talk with that teacher. A value of 0 indicates no conference is desired, up to a value of 9 indicating the strongest desire for a conference. Example lines from this file might be:

Johnny Smith, Richard Darwin, 3
Johnny Smith, Rene Descartes, 9
Johnny Smith, Edgar Allen Poe, 0
Sally Jones, Rene Descartes, 5
Sally Jones, Albert Einstein, 9

The final data set, in a file named schedulesNN.txt, identifies which parents are available at which times. The first line in this file contains the number N of conference periods available for scheduling. All teachers can be available for any or all of the periods from 1..N. Subsequent lines contain the names of parents, along with the first and the last conference period for which they will be available. Parents will be available for any period between their first and last available periods, inclusive. Each parent whose name appears in the children.txt file will appear on one line in the schedules.txt file. Example lines from this file might be:

9
Donald Smith, 1,9
Samantha Jones, 4,9
Marilyn Waters-Smith,4,6

Finally, the number of test cases is provided in a file input.txt, with a single line containing the number of test cases:

15

Your code needs to produce output that provides the matching of parents to teachers. The output (conferencesNN.txt) should contain one line for each conference, with the name of the teacher first, the name of the parent second, and the conference period third. No parent or teacher can be in more than one conference during a given period. Both parents of a given child can participate in a conference with a teacher if they are both available during that period (two lines would be output in such a case). One line in such a file might be:

Richard Darwin,Marilyn Waters-Smith,5

Finally, your solution needs to produce a log file (log.txt) that contains, for each test case, the execution time in milliseconds that your solution required to process the test case.

Once again, the objective is to maximize parents’ satisfaction with the conference schedule, and to minimize wasted time. The Challenge will be scored based on the number of penalty points accumulated by each entry. If a desired conference is not accommodated, you will accumulate 1-9 penalty points, depending on the strength of the parents’ desire for that conference as expressed in teachers.txt. If a parent has a gap in the conference schedule, where a conference is scheduled during periods N and N+2, but not in N+1, you will accumulate one penalty point for each unscheduled period in the gap. Similar penalty points will accumulate for gaps in the conference schedule for teachers. Finally, the penalty will be increased by 10% for each second of execution time used by your solution.

We’re going to make another attempt to broaden the development environments accepted for the Challenge, despite mixed success in the past. This will be a native PowerPC Challenge, using any of the following environments: CodeWarrior Pro, REALbasic, MetaCard, Revolution, or ProjectBuilder. You may use another development environment if I can arrange to obtain a copy – email progchallenge@mactech.com to check before you use something else. You can develop for Mac OS 9 or Mac OS X. Your submission should provide everyting needed to build your application.

Three Months Ago Winner

I mentioned above that we have had mixed success in experimenting with alternative development environments for the Challenge. That was certainly true in the September Challenge, where we asked readers to produce Nassi-Schneiderman diagrams using the environment of their choice. Perhaps because the Challenge focused on diagramming C/C++ code, no one submitted an entry using these alternative environments. Sadly, no one submitted a C/C++ entry either, so we have no winner for the Challenge this month. Remember, you can’t win if you don’t play!

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

iShowU Instant 1.3.3 - Full-featured scr...
iShowU Instant gives you real-time screen recording like you've never seen before! It is the fastest, most feature-filled real-time screen capture tool from shinywhitebox yet. All of the features you... Read more
Affinity Photo 1.8.3 - Digital editing f...
Affinity Photo - redefines the boundaries for professional photo editing software for the Mac. With a meticulous focus on workflow it offers sophisticated tools for enhancing, editing and retouching... Read more
Affinity Designer 1.8.3 - Vector graphic...
Affinity Designer is an incredibly accurate vector illustrator that feels fast and at home in the hands of creative professionals. It intuitively combines rock solid and crisp vector art with... Read more
Pinegrow 5.95 - Mockup and design web pa...
Pinegrow (was Pinegrow Web Designer) is desktop app that lets you mockup and design webpages faster with multi-page editing, CSS and LESS styling, and smart components for Bootstrap, Foundation,... Read more
WhatRoute 2.3.1 - Geographically trace o...
WhatRoute is designed to find the names of all the routers an IP packet passes through on its way from your Mac to a destination host. It also measures the round-trip time from your Mac to the router... Read more
Dropbox 94.4.384 - Cloud backup and sync...
Dropbox for Mac is a file hosting service that provides cloud storage, file synchronization, personal cloud, and client software. It is a modern workspace that allows you to get to all of your files... Read more
Boom 3D 1.3.6 - $19.99
Boom 3D is a revolutionary app with 3D Surround Sound and phenomenally rich and intense audio that is realistic and works on any headphones. Features 3D surround sound Built-in audio player... Read more
Remotix 6.1.4 - Access all your computer...
Remotix is a fast and powerful application to easily access multiple Macs (and PCs) from your own Mac. Features: Complete Apple Screen Sharing support - including Mac OS X login, clipboard... Read more
iMazing 2.11.4 - Complete iOS device man...
iMazing (was DiskAid) is the ultimate iOS device manager with capabilities far beyond what iTunes offers. With iMazing and your iOS device (iPhone, iPad, or iPod), you can: Copy music to and from... Read more
EtreCheck Pro 6.2.4 - For troubleshootin...
EtreCheck is an app that displays the important details of your system configuration and allow you to copy that information to the Clipboard. It is meant to be used with Apple Support Communities to... Read more

Latest Forum Discussions

See All

Hearthstone's new Demon Class is no...
A couple of weeks ago Blizzard announced that the game would be introducing its first new class since the game first launched in 2014. It's called the Demon Hunter and as of today, players will be able to get a glimpse and feel for how it will... | Read more »
The 5 Best Games Like Dark Souls
There's no escaping the fact that everyone loves Dark Souls. If you've not heard of it, it's a super tough action RPG that punished your every mistake with swift retribution. It's the sort of game where you die a lot, and it can be pretty... | Read more »
The Curse of Issyos is a retro-inspired...
The Curse of Issyos is the latest game to be ported to mobile and published by Abylight S.L who previously worked on Cursed Castilla. Much like that port, this game was also originally created by Spanish developers Locomalito. The Curse of Issyos... | Read more »
Same Room Games is a great collection of...
Staying at home under lockdown kinda sucks. Totally necessary, yes, but also more than a little anxiety-inducing and often boring. Thankfully, we've got lots of great multiplayer games to play with friends and keep us sane, the latest of which,... | Read more »
Bark Park is a joyfully silly multiplaye...
Bark Park is a charming, good-humoured game about competing against other players to claim as much territory as possible by peeing on nearby trees. Did I mention that everyone is playing as a dog? Makes things a little less weird. [Read more] | Read more »
The 5 Best Games Like Grindstone
Apple Arcade made a splash when it first launched, granting access to over 50 games as soon as it became available. Of those titles, the one that seemed to grab most people’s attention was Grindstone, a matching puzzle game from Capy Games. [Read... | Read more »
Awarding-winning puzzler Make One is now...
Make One is a game with a simple concept that it executes with flair and impressive levels of polish. It comes to us from developer Brazle and publisher PiG, and it's just landed this week for Android. At its core, Make One is a logic-based... | Read more »
Marvel Contest of Champions' latest...
Kabam's Marvel Contest of Champions has now teased some of the latest characters heading to the Battlerealm next month. Here's your chance to watch the new motion comic embedded below, Barons' War, before I spoil the surprise. [Read more] | Read more »
Why Calibria: Crystal Guardians is the p...
We could all use escapism right now, something to focus on and a project to feel part of during these times of social isolation. If you’re one of the many who’s turned to gaming to fill the lockdown void, Calibria: Crystal Guardians should be on... | Read more »
Mini Tank: Fire is a Worms-like, turn-ba...
Mini Tank: Fire is an online multiplayer game that takes a few cues from the likes of Worms and Shell Shock Live. It will feature 5v5 turn-based battles and is available now for both iOS and Android as a free-to-play game. [Read more] | Read more »

Price Scanner via MacPrices.net

Clearance 13″ 128GB MacBook Air in stock toda...
Guitar Center has clearance 2019 13″ 1.6GHz/128GB Space Gray MacBook Airs in stock today for $899 shipped. That’s $200 off Apple’s original MSRP for this model and the cheapest price available today... Read more
Weekend sale: 21″ & 27″ iMacs for up to $...
B&H Photo has new 21″ and 27″ 5K iMacs in stock today and on sale for up to $200 off Apple’s MSRP. These are the same iMacs sold by Apple in their retail and online stores, and B&H’s prices... Read more
Here’s how you can save $50 today on one of A...
– 11″ 128GB WiFi iPad Pro: $789 $10 off – 11″ 256GB WiFi iPad Pro: $849 $50 off – 11″ 512GB WiFi iPad Pro: $1049 $50 off – 11″ 1TB WiFi iPad Pro: $1249.99 $50 off – 11″ 128GB WiFi + Cell iPad Pro: $... Read more
Apple AirPods Pro back on sale at Amazon for...
Amazon has Apple’s AirPods Pro in stock and on sale today for $234.98 shipped. Their price is about $15 (6%) off Apple’s MSRP and the cheapest price available for these new models from any Apple... Read more
Apple restocks clearance, previous-generation...
Apple has clearance, Certified Refurbished, 2019 13″ MacBook Airs available for only $779. Each MacBook features a new outer case, comes with a standard Apple one-year warranty, and is shipped free.... Read more
Retro Reading: PowerBook Central Coverage of...
FEATURE: 04.03.20- Welcome to another edition of “Retro Reading,” a series here in my column, “Mac Potpourri,” where we dig deep into the archives for content written on today’s date several years... Read more
Price drop! 21″ 3.6GHz Quad-Core 4K iMac on s...
B&H Photo has the 21″ 3.6GHz Quad-Core 4K iMac in stock today and on sale for $1099.99 including free next day shipping to many locations in the US. That’s $200 off Apple’s MSRP: – 21″ 3.6GHz... Read more
Amazon is again offering $129 Apple AirPods,...
Amazon has Apple AirPods with Charging Case on sale again for $129.98 shipped. Their price is $30 off Apple’s MSRP for these AirPods. Their price is the cheapest available for AirPods from any Apple... Read more
Apple continues to offer iMac discounts rangi...
Apple has Certified Refurbished 2019 21″ & 27″ iMacs available starting at $929 and up to $350 off the cost of new models. Apple’s one-year warranty is standard, shipping is free, and each iMac... Read more
Apple offers Certified Refurbished iPhone XS...
Apple has Certified Refurbished iPhone XS models available for up to $350 off MSRP, with prices starting at $699. Each iPhone is unlocked and comes with Apple’s standard one-year warranty and a new... Read more

Jobs Board

Tier II Support Specialist- *Apple* - KeenL...
…will be responsible for Desktop Support of an environment composed of Apple workstations and several custom business applications. Job Responsibilities: + Providing Read more
Sephora Merchandise/Operations Supervisor -...
Sephora Merchandise/Operations Supervisor - Apple Blossom Mall Location:Winchester, VA, United States- Apple Blossom Mall 1850 Apple Blossom Dr Job Read more
Sales Supervisor - *Apple* Blossom Mall - J...
Sales Supervisor - Apple Blossom Mall Location:Winchester, VA, United States- Apple Blossom Mall 1850 Apple Blossom Dr Job ID:1083621Store Hourly Positions Read more
*Apple* Mac Product Engineer - Barclays (Uni...
Apple Mac Engineer Whippany, NJ Support the development and delivery of solutions, products, and capabilities into the Barclays environment working across technical Read more
Essbase Developer - *Apple* - Theorem, LLC...
Job Summary Apple is seeking an experienced, detail-minded Essbase developer to join our worldwide business development and strategy team. If you are someone who Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.