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

BusyCal 3.7.2 - Powerful calendar app wi...
BusyCal is the powerful, flexible, reliable calendar app for macOS. It's packed with time-saving features and compatible with all leading cloud services including iCloud, Google, Exchange and more.... Read more
BusyContacts 1.4.2 - Fast, efficient con...
BusyContacts is a contact manager for OS X that makes creating, finding, and managing contacts faster and more efficient. It brings to contact management the same power, flexibility, and sharing... Read more
iShowU Instant 1.3.0 - 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
Capo 3.8 - Slow down and learn to play y...
Capo lets you slow down your favorite songs so you can hear the notes and learn how they are played. With Capo, you can quickly tab out your songs atop a highly-detailed OpenCL-powered spectrogram... Read more
Viber 11.7.0 - Send messages and make fr...
Viber lets you send free messages and make free calls to other Viber users, on any device and network, in any country! Viber syncs your contacts, messages and call history with your mobile device, so... Read more
Drive Genius 5.3.1 - $79.00
Drive Genius features a comprehensive Malware Scan. Automate your malware protection. Protect your investment from any threat. The Malware Scan is part of the automated DrivePulse utility. DrivePulse... Read more
CorelDRAW 21.2.0.708 - Graphic design so...
CorelDRAW - professional graphic design software for vector illustration, layout, and so much more. Get started quickly and easily with a wealth of intuitive tools, built-in learning materials,... Read more
Navicat Premium Essentials 12.1.27 - Pro...
Navicat Premium Essentials is a compact version of Navicat which provides basic and necessary features you will need to perform simple administration on a database. It supports the latest features... Read more
OmniFocus 3.4.3 - GTD task manager with...
OmniFocus is an organizer app. It uses projects to organize tasks naturally, and then add tags to organize across projects. Easily enter tasks when you’re on the go, and process them when you have... Read more
Microsoft OneNote 16.30 - Free digital n...
OneNote is your very own digital notebook. With OneNote, you can capture that flash of genius, that moment of inspiration, or that list of errands that's too important to forget. Whether you're at... Read more

Latest Forum Discussions

See All

Breakout: Dark Prison is a fast-paced ac...
Breakout: Dark Prison is an action RPG from LaterSoft. Set in the aftermath of a deadly virus outbreak your daughter has been taken from you because she has an immunity to the illness in her DNA. Not being a fan of experimentation on children –... | Read more »
Apple Arcade in review
This weekend, Apple Arcade will officially be one month old. That means anyone who signed up for the free trial on day one has a decision to make: Stick with the service and shell out $5 a month, or cancel and go about your merry way. | Read more »
Alluris is a choose-your-own adventure g...
Alluris is an RPG that the developer's are calling a swipe-your-own adventure game. This is because the game incorporates a Reigns-style - swiping left or right - selection mechanic to make all the decisions you'd usually expect to make across... | Read more »
Hello Hero All Stars receives update wit...
The first Hello Hero game hit global platforms in 2013 and proved a huge success, with developer Fincon adding two more entries to this popular series of casual RPG games since. Released in June this year, Hello Hero All Stars brings many of the... | Read more »
Zombieland: Double Tapper, a cartoon idl...
Zombieland: Double Tapper is the idle RPG tie-in to the upcoming Zombieland: Double Tap. Oddly, it's one of two different Zombieland games launching today, with the other being the Switch title Zombieland: Double Tap - Road Trip. [Read more] | Read more »
Rusty Lake's The White Door launche...
Rusty Lake and Second Maze's intriguing point-and-click adventure game, The White Door, is now up for pre-order on the App Store. This one sees you playing as Robert Hill, a mental health patient who is suffering from severe memory loss. The game... | Read more »
Hellrule is an auto-runner inspired by G...
Hellrule is an upcoming auto-runner game from independent developer Pedrocorp where players will take control of a dapperly dressed gentlemen who comes equipped with a razor-sharp umbrella for slicing up his foes. The game will be available for... | Read more »
Grobo is a gravity bending puzzle platfo...
Grobo is a 2D puzzle platformer that marks the first release from developers Hot Chocolate Games. You'll find yourself manipulating gravity as you make your through this title that's available now for iOS and Android. [Read more] | Read more »
Adrenaline, Compulsive Entertainment’s h...
Compulsive Entertainment’s high-octane arcade racer, Adrenaline, has now made its way to the App Store following a successful launch on Google Play. It’s a ton of challenging, fast-paced fun, boasting easy-to-learn controls and a varied selection... | Read more »
Mario Kart Tour is adding Super Mario Ga...
Earlier today on Twitter, Nintendo announced that Mario Kart Tour is getting a new racer and track. Fans of Super Mario Galaxy will be pleased to hear that Rosalina is the first post-launch character being added, while the iconic Rainbow Road is... | Read more »

Price Scanner via MacPrices.net

11″ WiFi iPad Pros on sale today for up to $2...
Amazon has new 2018 Apple 11″ WiFi iPad Pros in stock today and on sale for up to $250 off Apple’s MSRP. These are the same iPad Pros sold by Apple in its retail and online stores. Be sure to select... Read more
Apple offers clearance 2018 15″ 6-Core MacBoo...
Apple has clearance 2018 15″ 6-Core Touch Bar MacBook Pros, Certified Refurbished, available starting at only $1999. Each model features a new outer case, shipping is free, and an Apple 1-year... Read more
Apple continues to offer refurbished 2019 21″...
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
Verizon offers free iPhone 7 for customers wh...
Verizon is offering a free 32GB iPhone 7 for new or existing customers who open a new line of service, no trade-in required. Cost of the phone is credited to your account monthly for 24 months. The... Read more
13″ 2.4GHz 4-Core MacBook Pros remain availab...
Apple has a full line of Certified Refurbished 2019 13″ 2.4GHz 4-Core Touch Bar MacBook Pros available starting at $1529 and up to $300 off MSRP. Apple’s one-year warranty is included, shipping is... Read more
Lease one iPhone Xs, Xr, or X at Sprint and g...
Purchase an Apple iPhone X, Xr, Xs, or Xs Max at Sprint, and get a 64GB iPhone Xr for free. Requires 2 new lines or 1 upgrade-eligible line and 1 new line. The fine print: “iPhone Xs (64 GB) $37.50/... Read more
How to use your Apple Education discount to s...
Purchase a new MacBook Pro or MacBook Air using Apple’s Education discount, and take up to $200 off MSRP. All teachers, students, and staff of any educational institution with a .edu email address... Read more
Base 2019 13″ 1.4GHz 4-Core MacBook Pro on sa...
Amazon has the new 2019 13″ 1.4GHz/128GB 4-Core Space Gray Touch Bar MacBook Pro on sale for $100 off Apple’s MSRP. This is the same MacBook Pro sold by Apple in its retail and online stores: – 2019... Read more
Save up to $30 on Apple’s AirPods at these re...
Amazon is offering discounts on new 2019 Apple AirPods ranging up to $30 off MSRP. Shipping is free: – AirPods with Charging Case: $144 $15 off MSRP – AirPods with Wireless Charging Case: $169 $30... Read more
Save $15 on Apple Watch Series 5 models on Wa...
Walmart has new Apple Watch Series 5 models on sale for $15 off Apple’s MSRP on their online store. Choose free shipping or free local store pickup (if available). Sale prices for online orders only... Read more

Jobs Board

*Apple* Mobile App Developer - eiWorkflow So...
…eiWorkflow Solutions, LLC is currently looking for a consultant for the following role. Apple Mobile App Developer Tasks the role will be performing: ? Mobile App 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
Best Buy *Apple* Computing Master - Best Bu...
**738230BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Store Associates **Location Number:** 000233-Almeda-Store **Job Description:** The Core Read more
Best Buy *Apple* Computing Master - Best Bu...
**738182BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Sales **Location Number:** 000036-Independence MO-Store **Job Description:** **What Read more
*Apple* Mobility Pro - Best Buy (United Stat...
**741450BR** **Job Title:** Apple Mobility Pro **Job Category:** Store Associates **Location Number:** 000168-Mentor-Store **Job Description:** At Best Buy, our Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.