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

Artlantis Studio 5.1.2.7 - 3D rendering...
Artlantis Studio is a unique and ideal tool for performing very high resolution rendering easily and in real time. The new FastRadiosity engine now lets you compute images in radiosity-even in... Read more
MacUpdate Desktop 6.0.5 - Search and ins...
MacUpdate Desktop 6 brings seamless 1-click installs and version updates to your Mac. With a free MacUpdate account and MacUpdate Desktop 6, Mac users can now install almost any Mac app on macupdate.... Read more
BitTorrent Sync 2.0.82 - Sync files secu...
BitTorrent Sync allows you to sync unlimited files between your own devices, or share a folder with friends and family to automatically sync anything. File transfers are encrypted. Your information... Read more
Google Drive 1.20 - File backup and shar...
Google Drive is a place where you can create, share, collaborate, and keep all of your stuff. Whether you're working with a friend on a joint research project, planning a wedding with your fiancé, or... Read more
Simon 4.0.3 - Monitor changes and crashe...
Simon monitors websites and alerts you of crashes and changes. Select pages to monitor, choose your alert options, and customize your settings. Simon does the rest. Keep a watchful eye on your... Read more
Vitamin-R 2.23 - Personal productivity t...
Vitamin-R creates the optimal conditions for your brain to work at its best by structuring your work into short bursts of distraction-free, highly focused activity alternating with opportunities for... Read more
iDefrag 5.0.0 - Disk defragmentation and...
iDefrag helps defragment and optimize your disk for improved performance. Features include: Supports HFS and HFS+ (Mac OS Extended). Supports case sensitive and journaled filesystems. Supports... Read more
PCalc 4.2 - Full-featured scientific cal...
PCalc is a full-featured, scriptable scientific calculator with support for hexadecimal, octal, and binary calculations, as well as an RPN mode, programmable functions, and an extensive set of unit... Read more
FileZilla 3.10.2 - Fast and reliable FTP...
FileZilla (ported from Windows) is a fast and reliable FTP client and server with lots of useful features and an intuitive interface. Version 3.10.2: Note: Now requires a 64-bit Intel processor.... Read more
The Hit List 1.1.11 - Advanced reminder...
The Hit List manages the daily chaos of your modern life. It's easy to learn - it's as easy as making lists. And it's powerful enough to let you plan, then forget, then act when the time is right.... Read more

Protect Yourself from an Onslaught of Ca...
Surprise Attack Games has announced a Cat-astrophic new physics puzzler called Fort Meow! In the game, a young girl named Nia finds her grandfather’s journal which triggers an all mighty feline attack! Why do the cats want the journal? Who knows,... | Read more »
GDC 2015 – Jelly Reef will be Game Oven’...
GDC 2015 – Jelly Reef will be Game Oven’s Last Hurrah, and it Seems like a Good Note to Go Out on Posted by Rob Rich on March 4th, 2015 [ permalink ] It’s sad knowing that Game Oven ( | Read more »
daWindci Deluxe Review
daWindci Deluxe Review By Campbell Bird on March 4th, 2015 Our Rating: :: BLUSTERY PUZZLESUniversal App - Designed for iPhone and iPad This updated puzzle game offers some creative gameplay and new mechanics, but still suffers from... | Read more »
Dungeon Hunter 5 Coming on March 12
Gameloft has excitedly announced that Dungeon Hunter 5 is on its way! Once again, you will adventure across the land of Valenthia exploring dungeons and fighting monsters. The game will have a new asynchronous multiplayer mode called Strongholds... | Read more »
GDC 2015 – The Sandbox 2 is Coming, and...
GDC 2015 – The Sandbox 2 is Coming, and Now it has Textures! | Read more »
Warner Bros. Interactive Announces Mort...
Mortal Kombat X, by Warner Bros. and NetherRealm Studios, will be a a free-to-play fighting/card-battle Mortal Kombat game. The game promises card collecting, multiplayer team combat, classic characters such as Scorpion, Sub-Zero and Raiden, and the... | Read more »
GDC 2015 – Piloteer is Whitaker Trebella...
GDC 2015 – Piloteer is Whitaker Trebella’s Latest Project, and it’s Definitely Something DIfferent Posted by Rob Rich on March 3rd, 2015 [ permalink ] You know | Read more »
PangoLand Review
PangoLand Review By Amy Solomon on March 3rd, 2015 Our Rating: :: COME VISIT PANGO AND FRIENDSUniversal App - Designed for iPhone and iPad PangoLand is an open-ended world full of familiar characters, bright colors and interactive... | Read more »
Knights of Pen & Paper is Leveling U...
With the roll of a die and a critical success, Paradox Interactive has announced Knights of Pen & Paper 2! You’ll be taking your place at the table once again in this sequel to Knights of Pen & Paper +1 Edition. The game will introduce the... | Read more »
GDC 2015 – Project Highrise is an Intere...
GDC 2015 – Project Highrise is an Interesting Idea from SomaSim Posted by Rob Rich on March 3rd, 2015 [ permalink ] You might know SomaSim best from their gold rush sim, 1849< | Read more »

Price Scanner via MacPrices.net

iPad: A More Positive Outlook – The ‘Book Mys...
It’s good to hear someone saying positive things about the iPad. I’ve been trying to bend my mind around how Apple’s tablet could have gone from zero to bestselling personal computing device on the... Read more
Mac Pros on sale for up to $279 off MSRP
Amazon has Mac Pros in stock and on sale for up to $279 off MSRP. Shipping is free: - 4-Core Mac Pro: $2725.87, $273 off MSRP (9%) - 6-Core Mac Pro: $3719.99, $279 off MSRP (7%) Read more
Sale! 13-inch Retina MacBook Pros for up to $...
B&H Photo has 13″ Retina MacBook Pros on sale for up to $205 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.6GHz/128GB Retina MacBook Pro: $1219.99 save $80 - 13″ 2.... Read more
Another Tranche Of IBM MobileFirst For iOS Ap...
IBM has announced the next expansion phase for  its IBM MobileFirst for iOS portfolio, with a troika of new apps to address key priorities for the Banking and Financial Services, Airline and Retail... Read more
Sale! 15-inch Retina MacBook Pros for up to $...
B&H Photo has the new 2014 15″ Retina MacBook Pros on sale for up to $250 off MSRP for a limited time. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $... Read more
WaterField Designs Introduces the Minimalist...
With Apple Pay gaining popularity, Android Pay coming in May 2015, and loyalty cards and receipts that can be accessed from smartphones, San Francisco’s WaterField Designs observes that it may be... Read more
Sale! 15-inch 2.2GHz Retina MacBook Pro for $...
 Best Buy has the 15″ 2.2GHz Retina MacBook Pro on sale for $1774.99 $1799.99, or $225 off MSRP. Choose free home shipping or free local store pickup (if available). Price valid for online orders... Read more
13-inch 2.5GHz MacBook Pro (refurbished) avai...
The Apple Store has Apple Certified Refurbished 13″ 2.5GHz MacBook Pros available for $170 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 13″ 2.5GHz... Read more
13-inch 2.5GHz MacBook Pro on sale for $100 o...
B&H Photo has the 13″ 2.5GHz MacBook Pro on sale for $999.99 including free shipping plus NY sales tax only. Their price is $100 off MSRP. Read more
27-inch 3.5GHz 5K iMac in stock today and on...
 B&H Photo has the 27″ 3.5GHz 5K iMac in stock today and on sale for $2299 including free shipping plus NY sales tax only. Their price is $200 off MSRP, and it’s the lowest price available for... Read more

Jobs Board

*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
Position Opening at *Apple* - Apple (United...
…Summary** As a Specialist, you help create the energy and excitement around Apple products, providing the right solutions and getting products into customers' hands. You Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** The Apple Store is a retail environment like no other - uniquely focused on delivering amazing customer experiences. As an Expert, you introduce people Read more
*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
*Apple* Pay Automation Engineer - iOS System...
**Job Summary** At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring passion and dedication to your job Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.