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

calibre 3.1.1 - Complete e-book library...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital librarian... Read more
Sparkle Pro 2.2 - $79.99
Sparkle Pro will change your mind if you thought building websites wasn't for you. Sparkle is the intuitive site builder that lets you create sites for your online portfolio, team or band pages, or... Read more
Spotify 1.0.57.474. - Stream music, crea...
Spotify is a streaming music service that gives you on-demand access to millions of songs. Whether you like driving rock, silky R&B, or grandiose classical music, Spotify's massive catalogue puts... Read more
beaTunes 5.0.1 - Organize your music col...
beaTunes is a full-featured music player and organizational tool for music collections. How well organized is your music library? Are your artists always spelled the same way? Any R.E.M. vs REM?... Read more
LibreOffice 5.3.4.2 - Free, open-source...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
VOX 2.8.26 - Music player that supports...
VOX just sounds better! The beauty is in its simplicity, yet behind the minimal exterior lies a powerful music player with a ton of features and support for all audio formats you should ever need.... Read more
iFFmpeg 6.4.0 - Convert multimedia files...
iFFmpeg is a comprehensive media tool to convert movie, audio and media files between formats. The FFmpeg command line instructions can be very hard to master/understand, so iFFmpeg does all the hard... Read more
Beamer 3.3 - Stream any movie file from...
Beamer streams to your Apple TV.... Plays any movie file - Just like the popular desktop movie players, Beamer accepts all common formats, codecs and resolutions. AVI, MKV, MOV, MP4, WMV, FLV. To... Read more
jAlbum Pro 14.0 - Organize your digital...
jAlbum Pro has all the features you love in jAlbum, but comes with a commercial license. You can create gorgeous custom photo galleries for the Web without writing a line of code! Beginner-friendly... Read more
Apple Remote Desktop Client 3.9.3 - Clie...
Apple Remote Desktop Client is the best way to manage the Mac computers on your network. Distribute software, provide real-time online help to end users, create detailed software and hardware reports... Read more

Latest Forum Discussions

See All

This War of Mine gets a new ending and m...
This War of Mine just got a big new update, featuring free DLC that adds a new ending to the game, among other exciting changes. The update is celebrating the game's two-year release anniversary. Apart from the new ending, which will be quite... | Read more »
Summon eight new heroes in Fire Emblem H...
Nintendo keeps coming at us with Fire Emblem Heroes updates, and it doesn't look like that trend is stopping anytime soon. The folks behind the game have just announced the new War of the Clerics Voting Gauntlet, expected to start next Tuesday. [... | Read more »
The best deals on the App Store this wee...
iOS publishers are pulling out all the stops this week -- there's a huge number of seriously great games at discounted prices this week. Let's not waste any time and get right down to business. [Read more] | Read more »
The House of da Vinci (Games)
The House of da Vinci 1.0.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.0 (iTunes) Description: Enter The House of Da Vinci, a new must-try 3D puzzle adventure game. Solve mechanical puzzles, discover hidden... | Read more »
Solve the disappearance of history’s gre...
Blue Brain Games invites you to indulge in an immersive hands-on 3D puzzle adventure in similar vein to The Room series, with its debut release The House of Da Vinci. Set during the historic period of the Italian Renaissance (when Leonardo himself... | Read more »
Age of Rivals (Games)
Age of Rivals 3.3 Device: iOS Universal Category: Games Price: $.99, Version: 3.3 (iTunes) Description: Deep civilization-building strategy in a fast-paced card game! | Read more »
Panthera Frontier (Games)
Panthera Frontier 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: | Read more »
Angry Birds Evolution beginner's gu...
Angry Birds changes things up a fair bit in its latest iteration, Angry Birds Evolution. The familiar sling-shot physics mechanics are still there, but the game now features team-based gameplay, RPG elements, and a new top-down view. With all of... | Read more »
Sega Forever is for the retro game fans
Sega is launching a new retro games service titled Sega Forever, in a move that's sure to delight games enthusiasts with a bit of nostalgia. Sega's releasing five classic games for free. The titles include Sonic the Hedgehog, Phantasy Star II,... | Read more »
The Little Acre (Games)
The Little Acre 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: | Read more »

Price Scanner via MacPrices.net

ABBYY TextGrabber 6 for iOS Implements Instan...
ABBYY has announced the release of TextGrabber 6.0.0, an important feature update to the company’s productivity app developed for iOS and Android devices. TextGrabber 6.0 now offers Real-Time... Read more
vPhone, First Smartphone That Can’t Be Lost,...
Austin, Texas based Hypori has introduced the vPhone, a virtual smartphone that affords every business user the benefits of separate work and personal phones, conveniently delivered on a single... Read more
Save this weekend with 2016 refurbished MacBo...
Apple has dropped prices on Certified Refurbished 2016 15″ and 13″ MacBook Pros by as much as $590 off original MSRP. An Apple one-year warranty is included with each model, and shipping is free: -... Read more
New 27-inch 3.4GHz iMac on sale for $1699, sa...
MacMall has the new 2017 27″ 3.4GHz iMac (MNE92LL/A) in stock and on sale for $1699 including free shipping. Their price is $100 off MSRP. Read more
Clearance 2016 MacBook Pros available for up...
B&H Photo has clearance 2016 13″ and 15″ MacBook Pros in stock today and on sale for up to $400 off original MSRP. Shipping is free, and B&H charges NY & NJ sales tax only: - 15″ 2.7GHz... Read more
Apple Ranks 9th In comScore Top 50 U.S. Digit...
comScore, Inc. has released its monthly ranking of U.S. online activity at the top digital media properties for May 2017 based on data from comScore Media Metrix Multi-Platform. * Entity has... Read more
10.5-inch iPad Pros available for up to $20 o...
B&H Photo has the new 2017 10.5″ iPad Pros available for up to $20 off MSRP including free shipping plus NY & NJ sales tax only: - 64GB iPad Pro WiFi: $649 - 256GB iPad Pro WiFi: $749 - 512GB... Read more
Three Off-The-Beaten-Track iOS Apps That Dese...
One of the great things about using iPads and iPhones is the vast selection of apps available for most anything you want or need to do. The three outlined in this article have been in my core app... Read more
Apple No. 1 Spot In Gartner Top 100 Vendors i...
Gartner, Inc. has unveiled the top global 100 vendors in IT in 2016 based on their revenue across IT (excluding communication services) and component market segments. In the Gartner Global Top 100:... Read more
Clearance iMacs available for up to $300 off...
B&H Photo has clearance 21″ and 27″ Apple iMacs available starting at $949, each including free shipping plus NY & NJ sales tax only: - 27″ 3.3GHz iMac 5K: $1999 $300 off original MSRP - 27″... Read more

Jobs Board

*Apple* News Product Marketing Mgr., Publish...
…organizational consensus on strategy and vision for publisher tools, authoring, and Apple News Format.Carries this strategy and vision across the organization to Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Security Data Analyst - *Apple* Information...
…data sources need to be collected to allow Information Security to better protect Apple employees and customers from a wide range of threats.Act as the subject matter Read more
Lead *Apple* Solutions Consultant - Apple I...
…integrity, and trust.Success Metrics/Key Performance Indicators:Quantitative* Year over Year growth in Apple Product and Beyond the Box sales in the assigned Point of Read more
*Apple* Solutions Consultant till v%u00E5r...
…ethics, integrity, and trust.Success Metrics/Key Performance Indicators:QuantitativeYear over Year growth in Apple Product and Beyond the Box sales in the assigned Point Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.