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

Xcode 15.0.1 - Integrated development en...
Xcode includes everything developers need to create great applications for Mac, iPhone, iPad, and Apple Watch. Xcode provides developers a unified workflow for user interface design, coding, testing... Read more
Google Chrome 120.0.6099.62 - Modern and...
Google Chrome is a Web browser by Google, created to be a modern platform for Web pages and applications. It utilizes very fast loading of Web pages and has a V8 engine, which is a custom built... Read more
Dropbox 188.4.6302 - Cloud backup and sy...
Dropbox 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, manage... Read more
djay Pro 5.0 - Transform your Mac into a...
djay Pro provides a complete toolkit for performing DJs. Its unique modern interface is built around a sophisticated integration with iTunes and Spotify, giving you instant access to millions of... Read more
Things 3.19.4 - Elegant personal task ma...
Things is a task management solution that helps to organize your tasks in an elegant and intuitive way. Things combines powerful features with simplicity through the use of tags and its intelligent... Read more
Sublime Text 4169 - Sophisticated text e...
Sublime Text is a sophisticated text editor for code, markup, and prose. You'll love the slick user interface, extraordinary features, and amazing performance. Features Goto Anything. Use Goto... Read more
Typinator 9.1 - Speedy and reliable text...
Typinator turbo-charges your typing productivity. Type a little. Typinator does the rest. We've all faced projects that require repetitive typing tasks. With Typinator, you can store commonly used... Read more
ESET Cyber Security 6.11.414.0 - Basic i...
ESET Cyber Security provides powerful protection against phishing, viruses, worms, and spyware. Offering similar functionality to ESET NOD32 Antivirus for Windows, ESET Cyber Security for Mac allows... Read more
Opera 105.0.4970.29 - High-performance W...
Opera is a fast and secure browser trusted by millions of users. With the intuitive interface, Speed Dial and visual bookmarks for organizing favorite sites, news feature with fresh, relevant content... Read more
Quicken 7.4.1 - Complete personal financ...
Quicken makes managing your money easier than ever. Whether paying bills, upgrading from Windows, enjoying more reliable downloads, or getting expert product help, Quicken's new and improved features... Read more

Latest Forum Discussions

See All

Vampire Survivors Among Us Crossover Eme...
Day of the Devs The Game Awards 2023 Edition just aired, and there were a plethora of announcements of great indie games and updates. I’ll have a round-up of the ones I liked the most in the SwitchArcade, but poncle just announced the first... | Read more »
‘Refind Self: The Personality Test Game’...
The last two months have been so busy that I’ve not been able to make time to play many games until recently. There are still new games coming out even as we head closer to the holidays, but I finally managed to play Playism and Lizardry’s recent... | Read more »
Experience the glory of the Northern Lig...
Dinosaur Polo Club, one of the best developer names out there, have recently announced the final update of 2023 for Mini Motorways. Instead of embracing Christmas, this event is instead inspired by one of the most beautiful natural phenomena, the... | Read more »
‘Disney Dreamlight Valley Arcade Edition...
After a bit of a delay, Disney Dreamlight Valley Arcade Edition () is now available on Apple Arcade worldwide. When Disney Dreamlight Valley Arcade Edition hit early access on PC and consoles including Nintendo Switch, I always assumed it would... | Read more »
‘Devil May Cry: Peak of Combat’ Releases...
It feels like we’ve been covering Devil May Cry: Peak of Combat (), the mobile entry in the superb Devil May Cry series, for as long as we were waiting for Devil May Cry 5. After trailers revealing gameplay, characters, controller support, betas,... | Read more »
‘Marvel Snap’ Dons Its Finest in the New...
It’s been quite a year for the card battler Marvel Snap (Free), which is still one of my favorite mobile games. There have been a bunch of interestingly-themed seasons, sometimes connected to the MCU and sometimes just doing their own thing. Plenty... | Read more »
SwitchArcade Round-Up: ‘A Highland Song’...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for December 5th, 2023. It’s a bit of a short one today since I was busy with a variety of other things, but there are several new releases for us to summarize. There are some really... | Read more »
‘Metal Slug ACA NEOGEO’ Review – Another...
Well, here we go again. The latest addition to SNK and Hamster’s mobile Arcade Archives line is none other than Metal Slug ACA NEOGEO ($3.99), a second take on a game we got a mobile version of a decade back from Dotemu. That was a fine version for... | Read more »
‘Sonic Dream Team’ Apple Arcade Review –...
What an unusual day we have arrived upon today. Now, Sonic the Hedgehog games aren’t a new thing for iOS gaming. The original Sonic the Hedgehog appeared on the classic iPod, so the Blue Blur got in the doors as fast as you would expect him to. The... | Read more »
PvP Basketball Game ‘NBA Infinite’ Annou...
Level Infinite and Lightspeed Studios just announced a new real-time PvP basketball game for mobile in the form of NBA Infinite (). NBA Infinite includes solo modes as well, collecting and upgrading current NBA players, managing teams, and more. It... | Read more »

Price Scanner via MacPrices.net

Apple’s 14-inch M3 MacBook Pros are on Holida...
Best Buy is offering a $150-$200 discount on Space Gray or Silver 14″ M3 MacBook Pros on their online store with prices available starting at $1449 ($1399 for premium My Best Buy members). Prices... Read more
Holiday Sale: 128GB iPhone 15 Pro, 15 Plus, o...
Boost Infinite, part of MVNO Boost Mobile using AT&T and T-Mobile’s networks, is offering the 128GB iPhone 15 Pro, 128GB iPhone 15 Plus, or 128GB & 256GB iPhone 15 for $60 per month including... Read more
Clearance 12.9-inch iPad Pros with M1 CPUs av...
Apple has Certified Refurbished, previous-generation, 12″ M1 iPad Pros available in their online store in a variety of configurations. Models start at $889 and range up to $350 off Apple’s original... Read more
Mac Studios with M2 Max and M2 Ultra CPUs on...
B&H Photo has standard-configuration Mac Studios with Apple’s M2 Max & Ultra CPUs in stock today and on Holiday sale for $200 off MSRP. Their prices are the lowest available for these models... Read more
B&H is offering a $150 discount on 13-inc...
B&H Photo has 13″ MacBook Airs with M2 CPUs and 256GB of storage in stock today and on Holiday sale for $150 off Apple’s MSRP, only $949. Free 1-2 day delivery is available to most US addresses.... Read more
Apple is clearing out last year’s M1-powered...
Apple has Certified Refurbished 11″ M1 iPad Pros available starting at $639 and ranging up to $310 off Apple’s original MSRP. Each iPad Pro comes with Apple’s standard one-year warranty, features a... Read more
Save $50 on these HomePods available today at...
Apple has Certified Refurbished White and Midnight HomePods available for $249, Certified Refurbished. That’s $50 off MSRP and the lowest price currently available for a full-size Apple HomePod this... Read more
New 16-inch M3 Pro MacBook Pros are on sale f...
Holiday MacBook deals are live at B&H Photo. Apple 16″ MacBook Pros with M3 Pro CPUs are in stock and on sale for $200-$250 off MSRP. Their prices are among the lowest currently available for... Read more
Christmas Deal Alert! Apple AirPods Pro with...
Walmart has Apple’s 2023 AirPods Pro with USB-C in stock and on sale for $189.99 on their online store as part of their Holiday sale. Their price is $60 off MSRP, and it’s currently the lowest price... Read more
Apple has Certified Refurbished iPhone 12 Pro...
Apple has unlocked Certified Refurbished iPhone 12 Pro models in stock starting at $589 and ranging up to $350 off original MSRP. Apple includes a standard one-year warranty and new outer shell with... Read more

Jobs Board

Omnichannel Associate - *Apple* Blossom Mal...
Omnichannel Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Operations Associate - *Apple* Blossom Mall...
Operations Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Cashier - *Apple* Blossom Mall - JCPenney (...
Cashier - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Blossom Mall Read more
Mobile Platform Engineer ( *Apple* /AirWatch)...
…systems, installing and maintaining certificates, navigating multiple network segments and Apple /IOS devices, Mobile Device Management systems such as AirWatch, and Read more
Omnichannel Associate - *Apple* Blossom Mal...
Omnichannel Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.