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

The best video player on mobile
We all know the stock video player on iOS is not particularly convenient, primarily because it asks us to hook a device up to iTunes to sync video in a world that has things like Netflix. [Read more] | Read more »
Four apps to help improve your Super Bow...
Super Bowl Sunday is upon us, and whether you’re a Panthers or a Broncos fan you’re no doubt gearing up for it. [Read more] | Read more »
LooperSonic (Music)
LooperSonic 1.0 Device: iOS Universal Category: Music Price: $4.99, Version: 1.0 (iTunes) Description: LooperSonic is a multi-track audio looper and recorder that will take your loops to the next level. Use it like a loop pedal to... | Read more »
Space Grunts guide - How to survive
Space Grunts is a fast-paced roguelike from popular iOS developer, Orange Pixel. While it taps into many of the typical roguelike sensibilities, you might still find yourself caught out by a few things. We delved further to find you some helpful... | Read more »
Dreii guide - How to play well with othe...
Dreii is a rather stylish and wonderful puzzle game that’s reminiscent of cooperative games like Journey. If that sounds immensely appealing, then you should immediately get cracking and give it a whirl. We can offer you some tips and tricks on... | Read more »
Kill the Plumber World guide - How to ou...
You already know how to hop around like Mario, but do you know how to defeat him? Those are your marching orders in Kill the Plumber, and it's not always as easy as it looks. Here are some tips to get you started. This is not a seasoned platform... | Read more »
Planar Conquest (Games)
Planar Conquest 1.0 Device: iOS Universal Category: Games Price: $12.99, Version: 1.0 (iTunes) Description: IMPORTANT: Planar Conquest is compatible only with iPad 3 & newer devices, iPhone 5 & newer. It’s NOT compatible with... | Read more »
We talk to Cheetah Mobile about its plan...
Piano Tiles 2 is a fast-paced rhythm action high score chaser out now on iOS and Android. You have to tap a series of black tiles that appear on the screen in time to the music, being careful not to accidentally hit anywhere else. Do that and it's... | Read more »
Ultimate Briefcase guide - How to dodge...
Ultimate Briefcase is a simple but tricky game that’s highly dependent on how fast you can react. We can still offer you a few tips and tricks on how to survive though. Guess what? That’s exactly what we’re going to do now. Take it easy [Read more... | Read more »
SoundPrism Link Edition (Music)
SoundPrism Link Edition 1.0 Device: iOS Universal Category: Music Price: $4.99, Version: 1.0 (iTunes) Description: ***Introductory price for a the first few days after launch - if you're reading this, get it while it's fresh out of... | Read more »

Price Scanner via MacPrices.net

12-inch 1.2GHz Silver Retina MacBook on sale...
B&H Photo has the 12″ 1.2GHz Silver Retina MacBook on sale for $1399 including free shipping plus NY sales tax only. Their price is $200 off MSRP, and it’s the lowest price for this model from... Read more
iPads on sale at Target: $100 off iPad Air 2,...
Target has WiFi iPad Air 2s and iPad mini 4s on sale for up to $100 off MSRP on their online store for a limited time. Choose free shipping or free local store pickup (if available). Sale prices for... Read more
Target offers Apple Watch for $100 off MSRP
Target has Apple Watches on sale for $100 for a limited time. Choose free shipping or free local store pickup (if available). Sale prices for online orders only, in-store prices may vary: - Apple... Read more
Apple refurbished 2014 13-inch Retina MacBook...
Apple has Certified Refurbished 2014 13″ Retina MacBook Pros available for up to $400 off original MSRP, starting at $979. An Apple one-year warranty is included with each model, and shipping is free... Read more
Macs available for up to $300 off MSRP, $20 o...
Purchase a new Mac or iPad using Apple’s Education Store and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free, and... Read more
Watch Super Bowl 50 Live On Your iPad For Fre...
Watch Super Bowl 50 LIVE on the CBS Sports app for iPad and Apple TV. Get the app and then tune in Sunday, February 7, 2016 at 6:30 PM ET to catch every moment of the big game. The CBS Sports app is... Read more
Two-thirds Of All Smart Watches Shipped In 20...
Apple dominated the smart watch market in 2015, accounting for over 12 million units and two-thirds of all shipments according to Canalys market research analysts’ estimates. Samsung returned to... Read more
12-inch 1.2GHz Retina MacBooks on sale for up...
B&H Photo has 12″ 1.2GHz Retina MacBooks on sale for $180 off MSRP. Shipping is free, and B&H charges NY tax only: - 12″ 1.2GHz Gray Retina MacBook: $1499 $100 off MSRP - 12″ 1.2GHz Silver... Read more
12-inch 1.1GHz Gray Retina MacBook on sale fo...
B&H Photo has the 12″ 1.1GHz Gray Retina MacBook on sale for $1199 including free shipping plus NY sales tax only. Their price is $100 off MSRP, and it’s the lowest price available for this model... Read more
Apple now offering full line of Certified Ref...
Apple now has a full line of Certified Refurbished 2015 21″ & 27″ iMacs available for up to $350 off MSRP. Apple’s one-year warranty is standard, and shipping is free. The following models are... Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Subject Matter Expert - Experis (Uni...
This position is for an Apple Subject Matter Expert to assist in developing the architecture, support and services for integration of Apple devices into the domain. Read more
*Apple* Macintosh OSX - Net2Source Inc. (Uni...
…: * Work Authorization : * Contact Number(Best time to reach you) : Skills : Apple Macintosh OSX Location : New York, New York. Duartion : 6+ Months The associate would Read more
Computer Operations Technician ll - *Apple*...
# Web Announcement** Apple Technical Liaison**The George Mason University, Information Technology Services (ITS), Technology Support Services, Desktop Support Read more
Restaurant Manager - Apple Gilroy Inc./Apple...
…in every aspect of daily operation. WHY YOU'LL LIKE IT: You'll be the Big Apple . You'll solve problems. You'll get to show your ability to handle the stress and Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.