TweetFollow Us on Twitter

Mar 02 Challenge

Volume Number: 18 (2002)
Issue Number: 03
Column Tag: Programmer's Challenge

by Bob Boonstra, Westford, MA

Megaminx

Some months the Challenge ideas come easily. Other months an interesting idea eludes me. This is one of those "other" months. The column deadline looms near, becomes imminent, encroaches into the present, overtakes me, and rushes onward, leaving me in its past. The wrath of my editor awaits. What to do?

Just in time, my collection of mechanical puzzles beckons, and an idea pops into my head. Time for another Meffert puzzle, perhaps. Something more difficult than the Tetraminx Challenge from June of 1999. Something even more difficult than the R*biks Cube Challenge. Yes, this month we'll Challenge readers to solve the Megaminx, pictured below.

The Megaminx is a regular solid with twelve faces, where each face is divided into one center face element (which I'll call a facelet), five corner facelets, and five edge facelets. The faces are colored with six colors, pairs of opposing faces being colored the same. The solid is divided into slices corresponding to the faces of the Megaminx. Each face can be rotated clockwise or counterclockwise, with five rotation steps in the same direction bringing the corresponding slice back to its original position. Your Challenge is to restore a scrambled Megaminx to its original position. Entries this month will be complete applications, so there is no prototype for the code you should write.

To describe the coloring of the solid, we're going to have to agree on some notation to identify the facelets. We'll number the faces from 1..12, thinking of face 1 as the "top" face. Face 2 will be one of the five faces adjacent to the top face, and faces 3..6 the other faces adjacent to the top face, proceeding clockwise from face 2 when viewed from above the top face. Faces 7..12 will be numbered such that face N+6 is opposite face N. We'll number the colors of the solved Megaminx using 1..6 as well, assigning color N to the center facelet of faces N and N+6. Sounds complicated perhaps, but if you read carefully, it should become clear. If it isn't, perhaps the following list of face adjacencies will help:

Face 1 is adjacent to faces: 2 3 4 5 6
Face 2 is adjacent to faces: 6 10 11 3 1
Face 3 is adjacent to faces: 2 11 12 4 1
Face 4 is adjacent to faces: 3 12 8 5 1
Face 5 is adjacent to faces: 4 8 9 6 1
Face 6 is adjacent to faces: 5 9 10 2 1
Face 7 is adjacent to faces: 8 9 10 11 12
Face 8 is adjacent to faces: 12 4 5 9 7
Face 9 is adjacent to faces: 8 5 6 10 7
Face 10 is adjacent to faces: 9 6 2 11 7
Face 11 is adjacent to faces: 10 2 3 12 7
Face 12 is adjacent to faces: 11 3 4 8 7

Your program must process multiple test cases, the number of which is provided in the file input.txt. The initial conditions for each test case are provided in file megaminxNN.in, where NN ranges from 1 to the number of test cases. Each input file contains 120 lines, 60 describing the coloring of the corner facelets, followed by 60 describing the coloring of the edge facelets. The lines describing the corner facelets will contain four comma-delimited numbers: the number of the face on which the facelet lies, the number of one of the other faces on this corner piece, the number of the third face on this corner piece, and the color of the facelet. The lines describing the edge facelets will contain three comma-delimited numbers: the number of the face on which the facelet lies, the number of the other face defining this corner piece, and the color of the facelet. So, for a Megaminx in the "solved" orientation, the megaminxNN.in file would contain the following lines for the top face:

            1,2,3,1
            1,3,4,1
            1,4,5,1
            1,5,6,1
            1,6,2,1
            ...
            1,2,1
            1,3,1
            1,4,1
            1,5,1
            1,6,1
            ...

The puzzle is solved with a sequence of slice rotations, resulting in each facelet being moved to the face that matches its color. Each rotation moves the corner and edge pieces of the rotated slice to new positions. A clockwise rotation of the slice corresponding to face 1, for example, moves corner piece (1,2,3) to (1,3,4), which moves to (1,4,5), which moves to (1,5,6), which moves to (1,6,2). A clockwise rotation of slice 2 moves the corners from (2,3,1) -> (2,1,6) -> (2,6,10) -> (2,10,11) -> (2,11,3) -> (2,3,1).

After reading the input for each test case, you should determine the sequence of rotations needed to solve the puzzle and output them to a file rotationsNN.txt. Each rotation should produce one line of output of the form:

            face,direction

...where face is the number of the slice being rotated, and "direction" is the character ‘+' for a clockwise rotation and ‘-‘ for a counterclockwise rotation.

Finally, your program should produce a megaminx.log file, with one line per test case containing the integer number of microseconds used by your application to solve that test case, including the time to read the input, find the solution, and produce the rotationsNN.txt output.

Scoring will be based on minimizing execution time. You can earn a reduction of up to 25% of your execution time if your application has an option to display the Megaminx as it is being solved. (Scoring will be done with the display option disabled, so the display time will not count against your solution.) The bonus will be awarded based on a subjective evaluation of the quality and attractiveness of your application.

This will be a native PowerPC Challenge, using the development environment of your choice, provided I have or can obtain a copy - email progchallenge@mactech.com to check before you start. You can develop for Mac OS 9 or Mac OS X. Your solution should be a complete Macintosh application, and your submission should provide everything needed to build your application.

Winner of the December, 2001 Challenge

Congratulations to Ernst Munter (Kanata, ON, Canada) for winning the December Parent-Teacher Conferences Challenge. This problem required contestants to schedule appointments between parents of children with their teachers. Penalty points were assessed for each requested conference that was not scheduled, for any scheduling gaps that caused parents or teachers to be idle between scheduled conferences, as well as for elapsed execution time. Parents indicate the strength of their desire for a conference with a teacher of a given child, and the penalty for not scheduling a conference is proportional to the parents' desire to hold one.

Ernst starts with an initial assignment of conferences that gives priority first to those parents whose availability is low, and then to those conferences that are most strongly desired by parents. He then tries to reduce scheduling gaps by moving conferences to different slots where both parent and teacher are available, assigning the conference to the other parent of the child, or swapping time slots with another parent who has a conference with the same teacher. The solution iterates on these techniques until no further advantage is obtained, after which it attempts to reduce penalties for scheduling gaps by canceling conferences entirely. Ernst not only achieved the lowest number of penalty points, but did so using the least execution time.

Alan Stenger again shares the prize with Ernst as the best-placing entrant without a recent victory. Alan's entry incurred about 9% more penalty points, in part because of two factors. First, he did not recognize cases when one parent had requested a conference for multiple children with the same teacher, correctly observing that this was unlikely to happen often in the real world. Second, he did nothing special to reduce penalties due to scheduling gaps, beyond scheduling conferences starting from the middle of the available periods and working outward from there.

Tom Saxton took second place (but as a recent winner does not share in the prize). Tom also processes conference requests in order of the strength of the parents' desire to hold it, moving other conferences held by a teacher if necessary and possible, or rescheduling the parent's conferences. Tom's approach incurred about 6% more penalty points than Ernst's.

Acknowledgements also to Ken Slezak and Tetuya Takeo for submitting solutions in non-Metrowerks development environments, Ken for using REALBasic, and Tetuya for using Objective C.

The table below lists, for each of the solutions submitted, the number of penalty points assessed due to missed conferences and scheduling gaps, the total execution time in milliseconds, and the penalty points after adding 10% for each second of execution time per test case. It also lists the programming language of each entry. As usual, the number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges prior to this one.

Name Penalty Time Points Language
(msec)
Ernst Munter(800) 48513 571.4 48825.0 C++
Tom Saxton(193) 51476 760.0 51997.1 C++ (OS X)
Alan Stenger(75) 52744 1482.8 53636.5 C++
Tetuya Takeo 54224 8539.3 60256.7 Objective C
Jan Schotsman(14) 59745 2192.0 61364.1 C
Ken Slezak(26) 60046 8199.0 66946.7 REALBasic

Top Contestants ...

Listed here are the Top Contestants for the Programmer's Challenge, including everyone who has accumulated 20 or more points during the past two years. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

Rank Name Points Wins Total
(24 mo) (24 mo) Points
1. Munter, Ernst 265 10 822
2. Rieken, Willeke 73 3 134
3. Wihlborg, Claes 49 2 49
4. Saxton, Tom 45 1 203
5. Taylor, Jonathan 39 1 63
7. Maurer, Sebastian 31 1 108
9. Mallett, Jeff 20 1 114
10. Cooper, Tony 20 1 20
11. Truskier, Peter 20 1 20

... and the Top Contestants Looking for a Recent Win

In order to give some recognition to other participants in the Challenge, we also list the high scores for contestants who have accumulated points without taking first place in a Challenge during the past two years. Listed here are all of those contestants who have accumulated 6 or more points during the past two years.

Rank Name Points Total
(24 mo) Points
6. Boring, Randy 32 144
8. Sadetsky, Gregory 22 24
12. Shearer, Rob 19 62
13. Stenger, Allen 17 82
14. Schotsman, Jan 16 16
15. Nepsund, Ronald 10 57
16. Hart, Alan 10 35
17. Day, Mark 10 30
18. Downs, Andrew 10 12
19. Desch, Noah 10 10
20. Fazekas, Miklos 10 10
21. Flowers, Sue 10 10
22. Leshner, Will 7 7
23. Miller, Mike 7 7
There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) being the first person to find a bug in a published winning solution or, (3) being the first person to suggest a Challenge that I use. The points you can win are:
1st place 20 points
2nd place 10 points
3rd place 7 points
4th place 4 points
5th place 2 points
finding bug 2 points
suggesting Challenge 2 points

Here is Ernst's winning Parent-Teacher Conferences solution:

PT-Main.cpp
Copyright © 2001
Ernst Munter, Kanata ON, Canada

/*
The task
————
Schedule parent-teacher conferences, while maximizing parent and teacher satisfaction. Each conference 
relating to a child involves a teacher, a parent, and a priority. Satisfaction is maximized by 
accommodating those conferences having higher priority while minimizing the time any teacher or 
parent have to wait between conferences. The input is provided in the form of three text files for 
each test case.  The output is a text file listing the conferences, and a log file reporting the run 
times.

Solution
————
Each input file is scanned to generate an array of corresponding records of children,
parents, and teachers.  Names are replaced by pointers linking parents to children,
and parents and teachers to conference requests.  Spouses are linked to each other.

Conference requests for children with the same parents and teacher reference, are combined,  their 
priorities added together and transferred to a single request.  All redundant requests are then removed.

Conference requests are first sorted to place the highest priority requests at the front.
The first N requests are then sorted to favour requests for conferences with parents who have less time
available.  N is the number of teachers multiplied by the number of  available conference periods.

A processing sequence of the conference periods is prepared, based on the total availability of parents 
for each period.  Periods with less availability will be used  first in trying to accommodate a request.

Then all requests are sequentially served, and if possible accommodated by booking a
conference period with the requested teacher.

When no more matches can be found, a loop of simple strategies is used to reduce the waiting penalties, 
essentially by shifting conferences around among time slots, parents and their spouses, and between 
parents having conferences with the same teacher.

When no more improvement can be made, the set of conferences is sent to the disk file.

Version 2 addition: a 4th wait-reduction technique is added by which conferences may be cancelled if 
the waiting times eliminated exceed the priority points lost.  

Version 3 addition: Exploits the rule that a spouse may use a parent in the same 
conference, to reduce a spouse's waiting time.  In the test cases, this change resulted in only a tiny 
improvement.  The data structure does not allow the recognition of more than one spouse, so there may 
still be some missed opportunities for points savings.
   
Limitations
—————-
Where there are two parents to a child, they are usually "married" and cross linked in  the database.  
However, no parent can have more than one spouse, and only one crosslinkage  can exist.  This implies 
that we can use spousal cross links to find alternates for  conferences, but we cannot infer from the 
absence of a crosslink that (another) spouse does  not exist.  

No multiple conferences can occur with the same teacher at the same time, i.e. only one parent can be 
present at a conference. This restriction was removed in version 3.
   
Assumptions
—————-
The number of periods does not exceed 255.  This limit can be increased in the
PT-compile-constants header file.

(It might have been nice to use 32-bit bit maps in some cases, but I thought 32 might 
be a bit too low as a realistic limit for the general case) 

Associated Program Files
————————————
The main program (this file) is "PT-Main.cp".

The header file "PT-Files.h" contains classes for the various input and output files.

The header file "PT-Persons.h" contains classes for the person records.

The header file "PT-compile-constants.h" contains a few compile policies, such as
the maximum number of periods (defaulting to 255), and the debug and assert controls. It also contains 
a directory string which can be used to locate the input and output files in a directory other than the 
executable.

The header file "PT-Utilities.h" and the file "PT-Utilities.cpp" contain some minor
utility functions, not all of which may actually be still in use in this version.

The header file "MyTimer.h" contains a microsecond timer class.

*/
#include "PT-Persons.h"
#include "PT-Files.h"
#include "PT-compile-constants.h"
#include "PT-Utilities.h"
#include "MyTimer.h"

class AvailabilityByPeriod
// Used in computing the optimal period assignment order.
{
   long   availabilitySum; // of all parents
   long   period;
public:
   void    Init(long x) {availabilitySum=0;period=x;}
   void   Increment() {availabilitySum++;}
   long   Period() const {return period;}
   int operator - (AvailabilityByPeriod& r) const 
      {return availabilitySum-r.availabilitySum;}
};

class TestCase
// Contains the resources of a test case, files, parents, teachers, etc.
{
   SchedulesFile   schedulesFile;
   ChildrenFile   childrenFile;
   TeachersFile   teachersFile;
   OutputFile      outputFile;

   long      numPeriods;
   
   Parent*    parents;
   long      numParents;

   Child*      children;
   long      numChildren;
   
   Request*   requests;
   long      numRequests;
   
   Teacher*   teachers;
   long      numTeachers;
   
   Conference*   conferences;
   long      numConferences;
   
   Period_t*   assignmentOrder;
public:
   TestCase(long testNumber) :
// Constructor reads all input files and sets up the resources.
      schedulesFile(testNumber,numPeriods,parents,numParents),
      childrenFile(testNumber,children,numChildren),
      teachersFile(testNumber,requests,numRequests),
      outputFile(testNumber),
      teachers(0),
      numTeachers(0),
      conferences(0),
      numConferences(0),
      assignmentOrder(0)
   {}
   ~TestCase()
   {
      delete [] conferences;
      delete [] teachers;
      delete [] assignmentOrder;
   }
   void Run()
   {
      MakeAssignmentOrder();
      LinkParentsWithChildren(); 
      SetupTeachers();
      CombineRequests();
      numRequests -= 
      NumAbsorbedRequests();
      
      AllocateConferences();
      PopulateConferences();
      
      ReduceWaits();   
      SendConferences();
   }
   
private:
   void MakeAssignmentOrder()
// Generates a period order, from the least available to the most available,
// based on parent availablity.  Less available periods will be assigned first.
   {
#if MAXNUMPERIODS > 255
      AvailabilityByPeriod*   ABP;
      try {
         ABP=new AvailabilityByPeriod[1+numPeriods];
      } catch(...) {
         Error("Could not allocate storage for","ABP");
      }
#else
      AvailabilityByPeriod ABP[256];
#endif
      for (int period=0;period<=numPeriods;period++)
         ABP[period].Init(period);
         
      for (Parent* P=parents;P<parents+numParents;P++)
      {   
         long firstPeriod=P->FirstPeriod();   assert(firstPeriod>0);
         long lastPeriod=P->LastPeriod(); 
                                                         assert(lastPeriod<=numPeriods);
         for (long period=firstPeriod;period<=lastPeriod;period++)
         {
            ABP[period].Increment();
         }
      } 
      
      qsort(ABP+1,numPeriods,sizeof(AvailabilityByPeriod),
                                 Cmp<AvailabilityByPeriod>);
      
      try {
         assignmentOrder=new Period_t[1+numPeriods];
      } catch(...) {
         Error("Could not allocate storage for","assignmentOrder");
      }
      
      for (int period=0;period<=numPeriods;period++)
         assignmentOrder[period]=ABP[period].Period();
      
#if MAXNUMPERIODS > 255
      delete [] ABP;
#endif
   }
   
   void LinkParentsWithChildren()
// Replaces parentName and childName with parent and child pointers.
   {
      Child* C=children;
      for (long i=0;i<numChildren;i++,C++)
      {
         Parent* parent1=FindParent(C->Parent1Name());
         Parent* parent2=FindParent(C->Parent2Name());
         
         C->RegisterParents(parent1,parent2);
      }
      for (long i=0;i<numChildren;i++)
      {
         children[i].MarryParents();
      }
   }
   
   void SetupTeachers()
// Scans the already sorted requests (by teacher’s name, from teachers file) to:
//       discover unique teacher names, and setup in the teachers array,
//       replaces childName with child (assumes childrenFile exists).
//      installs availablity in parents (assumes parents are linked to children)
// Then scans the requests again to make the teachers array
   {
      char* lastTeacherName=””;
      char* teacherName=0;
      Request* R=requests;
      long teacherId=-1;
      for (long i=0;i<numRequests;i++,R++)
      {
         teacherName=R->Name();
         if (strcmp(lastTeacherName,teacherName))
         { 
            lastTeacherName=teacherName;
            teacherId++;
         }
         R->SetTempTeacherId(teacherId);
         
         char* childName=R->ChildName();
         Child* child=FindChild(childName);
         assert(child);
         R->ReplaceChildName(child);
         child->SetParentAvailability();
      }
      
      numTeachers=teacherId+1;
      try {
         teachers=new Teacher[numTeachers];
      } catch(...) {
         Error("Could not allocate storage for","teachers");
      }
      
      long lastTid=-1;
      R=requests;
      for (long i=0;i<numRequests;i++,R++)
      {
         long tid=R->TempTeacherId();
         assert(tid<numTeachers);
         if (tid != lastTid)
         {
            teachers[tid].Init(R->Name(),tid);
            lastTid=tid;
         }
         R->SetTeacher(teachers+tid); 
      }
   }
   
   void CombineRequests()
// Entered with requests already sorted by teacher.
// For each teacher’s block of request, sorts by parent,
// Combines equivalent requests (same teacher, same parents, sums priorities)
// All absorbed requests are marked with negative priority
   {
      Request* src=requests;// read from
      Request* end=numRequests+requests;
      for (int i=0;i<numTeachers;i++)
      {
         long numSameTeacher=CountByTeacher(src,end,&teachers[i]);
         qsort(src,numSameTeacher,sizeof(Request),Request::CmpParents);
         
         Request* uniqueRequest=src;
         for (Request* R=src+1;R<src+numSameTeacher;R++)
         {
            if (Request::CmpParents(R,uniqueRequest)) // if they differ
            {
               uniqueRequest=R;
            } else 
            {
               R->TransferPriorityTo(uniqueRequest);
            }
         }
         src+=numSameTeacher;
      }
   }
   
   long NumAbsorbedRequests()
// Sorts requests by priority and counts the tail of -1 priority (nonUnique) requests
// returns the number of requests that can be dropped
   {
      qsort(requests,numRequests,sizeof(Request),
                        Request::CmpPriorities);
      Request* R=requests+numRequests;
      long numDropped=0;
      while ((R>requests) && (—R)->Priority() < 0)
         numDropped++;
      return numDropped;
   }
   
   void AllocateConferences()
// There can not be more than numTeachers*numPeriods conferences
// unless one were to allow multiple parents to attend the same conference.
// This version does not support multiple conferences at the same time.
   {
      numConferences=1+numTeachers*numPeriods;// 1 extra for [0] location
      try {
         conferences=new Conference[numConferences];
         memset(conferences,0,sizeof(Conference)*numConferences);
      } catch(...) {
         Error("Could not allocate storage for","conferences");
      }
      // address as conferences[teacherNr*numPeriods + periodNumber]
      // block pitch is numPeriods;  conferences[0] is not used.
   }
   
   long PopulateConferences()
// Simple first come, first served, lower availability and higher priorities first.
// After assigning requests to conferences, the request array must not change. 
// Returns the simple score (sum of priorities of requests accommodated).
   {   
      long numToSort=(numConferences-1 < numRequests)?
         (numConferences-1):numRequests;
      qsort(requests,numToSort,sizeof(Request),
                              Request::CmpAvailability);
      
      Request* R=requests;
      long score=0;
      long numAssigned=0;
      for (int i=0;i<numRequests;i++,R++)
      {      
         
         Teacher* teacher=R->TheTeacher();
         long teacherId=teacher->Pid();
         long priority=R->Priority();
         
         Conference* block=conferences+teacherId*numPeriods;
         
         // find first free conference
         for (int periodIndex=1;periodIndex<=numPeriods;
                              periodIndex++)
         {
            long period=assignmentOrder[periodIndex];
            if (block[period].IsAssigned())
               continue;
            
            Parent* parent=R->GetAvailableParent(period);
            
            if (parent)
            {
               block[period].Init(teacher,parent,period,priority);
               parent->Book(block+period,period);
               score+=priority;
               numAssigned++;
               R->SetPeriod(period);
               break;
            } 
         }
         if (numAssigned >= numConferences-1)
            break;
      }
      return score;

   }
   
   void ReduceWaits()
// Tries easy ways of reducing waiting times:
//      moving to a different time (agreeable to both parent and teacher);
//      transferring a conference to a spouse;
//      swapping time slots with another parent (same teacher).
//      These operations affect each other and are repeated until no more 
//      improvement can be obtained.
//   ADDED in version 2:
//      cancelling a scheduled conference if that generates a points advantage.
   {
      long accumulatedReduction;
      do {
         accumulatedReduction = ReduceWaitsByTimeChange();
      
         long reduction;
         while (0 < (reduction = ReduceParentWaitsByTransfers()))
            accumulatedReduction+=reduction;
      
         accumulatedReduction += ReduceParentWaitsBySwapping();
      } while (accumulatedReduction>0);
      
      ReducePenaltyByCancellation();
   }
   
   Child* FindChild(char* childName)
// Finds a child record by name.
   {
      Child searchKey(childName,0,0,0);
      return (Child*)
      bsearch(&searchKey,children,numChildren,sizeof(Child),
                                    Cmp<Child>);
   }
   
   Parent* FindParent(char* parentName)
// Finds a parent record by name.
   {
      if (parentName)
      {
         Parent searchKey(parentName,0,0,0);
         return (Parent*)
         bsearch(&searchKey,parents,numParents,sizeof(Parent),
                                    Cmp<Parent>);
      } else return 0;
   }
   
   long CountByTeacher(Request* R,Request* end,Teacher* teacher)
// Returns the number of requests for one teacher.
   {
      long count=0;
      while ((R<end) && ((R++)->TheTeacher()==teacher))
         count++;
      return count;
   }
   
   long ReduceParentWaitsBySwapping()
// Attempts to swap conferences with the same teacher, but between different parents,
//       if that results in a reduction of waitinf penalties.
// Returns the reduction achieved.
   {
      long reduction=0;
      for (Conference* block=conferences;
            block<conferences+numConferences-1;block+=numPeriods)
      {
         for (long period1=1;period1<numPeriods;period1++)
         {
            Conference* C1=block+period1;
            for (long period2=period1+1;period2<=numPeriods;period2++)
            {
               Parent* P1=C1->TheParent();
               if (!P1)
                  continue;
               if (P1->IsBooked(period2) || !P1->IsAvailable(period2))
                  continue;
               Conference* C2=block+period2;
               Parent* P2=C2->TheParent();
               if (!P2)
                  continue;
               if (P2->IsBooked(period1) || !P2->IsAvailable(period1))
                  continue;
               long before=P1->NumIdlePeriods()+P2->NumIdlePeriods();
               if (before<=0)
                  continue;
               P1->SwapConference(period1,P2,period2);
               long after=P1->NumIdlePeriods()+P2->NumIdlePeriods();
               if (after <= before)
               {
                  C1->UpdateParent(P2);
                  C2->UpdateParent(P1);
                  reduction += before-after;
               } else   // swap back
               P1->SwapConference(period2,P2,period1);
            }
         }
      }
      return reduction;
   }
   
   long ReduceParentWaitsByTransfers()
// Attempts to reduce waiting penalties by assigning conferences to spouses.
// Returns the reduction achieved.
   {
      long reduction=0;
      for (Conference* C=conferences;
                        C<conferences+numConferences;C++)
      {
         Parent* P=C->TheParent();  
         if (!P)
            continue;
         Parent* spouse=P->Spouse();
         if (!spouse) 
            continue;
         long period=C->Period();
         if (!spouse->IsAvailable(period) || 
                        spouse->IsBooked(period))
            continue;
         long before=P->NumIdlePeriods() + spouse->NumIdlePeriods();
         if ((before<=0))
            continue;
         P->TransferConferenceToSpouse(period);
         long after=P->NumIdlePeriods() + spouse->NumIdlePeriods();
         
         if (after <= before)// update conference with transfer
         {
            C->UpdateParent(spouse);
            reduction+=before-after;
         } else
            spouse->TransferConferenceToSpouse(period);// undo transfer
      }
      return reduction;
   }
   
   long ReduceWaitsByTimeChange()
// Attempts to reduce waiting penalties by shifting conferences to different periods.
// Returns the reduction achieved.
   {
      long reduction=0;
      for (Conference* C=conferences;
                              C<conferences+numConferences;C++)
      {
         Parent* P=C->TheParent();  
         if (!P)
            continue;
         long bestPeriod=C->Period();
         Teacher* T=C->TheTeacher();
         assert(T);
         Conference* teachersBlock=conferences+T->Pid()*numPeriods;
         long lowestWait=P->NumIdlePeriods()+TeacherWaits(T);
         
         if (lowestWait<=0)
            continue;
         long before=lowestWait;
         for (int alternatePeriod=1;alternatePeriod<=numPeriods;
                              alternatePeriod++)
         {
            if (alternatePeriod==bestPeriod)
               continue;
            if (P->IsAvailable(alternatePeriod) && 
               !P->IsBooked(alternatePeriod) &&
               !teachersBlock[alternatePeriod].IsAssigned())
            {
               P->RescheduleConference(bestPeriod,alternatePeriod);
               teachersBlock[alternatePeriod].
                  Copy(teachersBlock[bestPeriod],alternatePeriod);
               teachersBlock[bestPeriod].Clear();
               long wait=P->NumIdlePeriods()+TeacherWaits(T);
               if (wait<=lowestWait)
               {
                  lowestWait=wait;
                  bestPeriod=alternatePeriod;
               } else // undo the rescheduling
               {
                  P->RescheduleConference(alternatePeriod,bestPeriod);
                  teachersBlock[bestPeriod].
                     Copy(teachersBlock[alternatePeriod],bestPeriod);
                  teachersBlock[alternatePeriod].Clear();
               }
            }
         }
         reduction += before-lowestWait;
      }
      return reduction;
   }
   
   long ReducePenaltyByCancellation()
// Attempts to reduce waiting penalties by cancelling conferences entirely.
// Returns the reduction achieved.
   {
      long reduction=0;
      for (Conference* C=conferences+1;
                                 C<conferences+numConferences;C++)
      {
         if (!C->IsAssigned()) continue;
         Parent* P=C->TheParent(); 
         Teacher* T=C->TheTeacher();   
         long priority=C->Priority();
         long waitBefore=P->NumIdlePeriods()+TeacherWaits(T);
         long period=C->Period();
         P->Unbook(period);   // cancel conference
         C->Clear();
         long waitAfter=P->NumIdlePeriods()+TeacherWaits(T);
         if (waitAfter < waitBefore-priority)
         {
            reduction += waitBefore-priority - waitAfter;
         } else // reestablish conference
         {
            P->Book(C,period);
            C->Init(T,P,period,priority);
         }
      }
      return reduction;
   }
   void SendConferences()
// Sends the conference schedule to the output file.
   {
      outputFile.Open();
      for (int i=0;i<numConferences;i++)
      {
         if (conferences[i].IsAssigned())
         {
            outputFile.SendConference(conferences[i]);
// Version 3:
// Let spouse join a conference if that reduces waiting time for the spouse.
            Parent* spouse=conferences[i].TheParent()->Spouse();
            if (spouse)
            {
               long period=conferences[i].Period();
               if (spouse->IsAvailable(period) &&
                  !spouse->IsBooked(period) && 
                  // make sure extra conference improves spouse's schedule
                  (period < spouse->LastPeriodUsed()) &&
                  (period > spouse->FirstPeriodUsed()) 
                  )
               {
// We just replace parent with spouse since parent's conference is already recorded.
                  conferences[i].UpdateParent(spouse);
                  outputFile.SendConference(conferences[i]);
               }
            }
         }
      }
      outputFile.Close();
   }
   
   long TeacherWaits(Teacher* T)
// Assumes the conference array is laid out as rows of numPeriod conferences per 
// teacher. Returns the number of idle periods of one teacher.
   {
      long teacherId=T->Pid();
      long teacherfirst=numPeriods+1;
      long teacherLast=0;
      long teacherNum=0;
      Conference* block=conferences+teacherId*numPeriods;
      for (int period=1;period<=numPeriods;period++)
      {
         if (block[period].IsAssigned())
         {
            if (period<teacherfirst) teacherfirst=period;
            teacherLast=period;
            teacherNum++;
         }
      }
// FIXED in version 2: Correct output (0) if teacher is not assigned any conference
      long teacherWaits=(teacherNum) ? 
            (teacherLast+1-teacherfirst-teacherNum):0;
      return teacherWaits;
   }
};


int main()
{
   long    numTests=InputFile::GetNumTests();      // get the number of tests
   LogFile logFile(numTests);

   for (long testNumber=1;testNumber<=numTests;testNumber++)
         // loop over the number of tests
   {
      MyTimer timer;                              // starts a timer
      TestCase testCase(testNumber);   // constructs a test case
      testCase.Run();                           // runs the test case
      logFile.Set(                                 // saves the timing in logFile
         testNumber,timer.ElapsedMilliSecs());
   }
   logFile.Send();                              // sends the logFile to disk
   return 0;
}

PT-Persons.h

#ifndef PT_PERSONS_H
#define PT_PERSONS_H
/* Person based classes for the Parent-Teacher conferences */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "PT-compile-constants.h"
#include "PT-Utilities.h"

enum {
   kLineLength=255,
   kLineEnd=0x0D // Mac line end
};

class Request;
typedef Request* RequestPtr;

class Conference;
typedef Conference* ConferencePtr;

class Person
// Base class, knows how to scan the text to extract the persons name.
{
   char*   name;
   ulong   pid;
public:
   Person():name(0){}
   Person(char* xname,ulong xid):name(xname),pid(xid){}
   char*    Name() const {return name;}
   ulong   Pid() const {return pid;}
   
   int operator - (Person& r) const {return strcmp(name,r.name);}
   
   char* Init(char* cp,long xid)
   {
      char* line=LeftTrim(cp);
      name=line;
      line=ForwardTo(line,',');
      *line=0;
      RightTrim(name,line);
      pid=xid;
      return line;
   }
   
   static char* LeftTrim(char* cp)
   {
      while (*cp && !isalnum(*cp))
         cp++;
      return cp;
   }

   static void RightTrim(char* start,char* cp)
// Scans backwards, beginning at the null char beyond string
   {
      while ((cp>start) && !isalnum(*(—cp)))
         *cp=0;
   }

   static char* ForwardTo(char* cp,char c)
   {
      while (*cp && (*cp != c))
         cp++;
      return cp;
   }

   static char* ForwardTo(char* cp,char c1,char c2)
   {
      while (*cp && (*cp != c1) && (*cp != c2))
         cp++;
      return cp;
   }
};

#if MAXNUMPERIODS <= 255   
typedef uchar Period_t;
#define Period_FORMAT "%hhd"
#else
typedef long Period_t;
#define Period_FORMAT "%ld"
#endif
class Parent:public Person
// Collection of parental functions.
{
   Parent*      spouse;
   ConferencePtr*   booked;
   // array[numPeriods] allocated if/when parent books a conference
   Period_t   firstPeriod;
   Period_t   lastPeriod;
   Period_t   firstPeriodUsed;
   Period_t   lastPeriodUsed;
   Period_t   numPeriodsUsed;
public:
   Parent() :
      spouse(0),
      booked(0)
   {}
   Parent(char* parentName,long xid,long p1,long p2) :
// This constructor is only used in making a searchkey for bsearch
      Person(parentName,xid),
      spouse(0),
      booked(0),
      firstPeriod(p1),
      lastPeriod(p2),
      firstPeriodUsed(lastPeriod+1),
      lastPeriodUsed(0),
         // we'll rely on lastPeriodUsed initialized to 0 to indicate no-conference
      numPeriodsUsed(0)
   {}
   ~Parent(){if (booked) delete [] booked;}
   char* Init(char* cp,long xid) 
// initializes each parent as part of reading the schedules file
   {
      char* line=Person::Init(cp,xid);
      sscanf(++line,Period_FORMAT","Period_FORMAT,&firstPeriod,
                                    &lastPeriod);
      firstPeriodUsed=lastPeriod+1;
      lastPeriodUsed=0;// we'll rely later on this having been initialized to 0
      numPeriodsUsed=0;
      line=ForwardTo(line,kLineEnd);
      return line+1;
   }
   Parent* Spouse() const {return spouse;}
   void Marries(Parent* s) {spouse=s;}
   const Parent* FirstParent() const // returns parent of higher address
   {
      if (this > spouse)
         return this;
      else
         return spouse;
   }
   
   long FirstPeriod() const {return firstPeriod;}
   long LastPeriod() const {return lastPeriod;}
   long FirstPeriodUsed() const {return firstPeriodUsed;}
   long LastPeriodUsed() const {return lastPeriodUsed;}
   bool IsAvailable(long period) const 
   {
      return ((period>=firstPeriod) && (period<=lastPeriod));
   }
   
   void Book(Conference* C,long period)
   {
      numPeriodsUsed++;
      if (period>lastPeriodUsed)lastPeriodUsed=period;
      if (period<firstPeriodUsed)firstPeriodUsed=period;
      if (!booked)
      {
         booked=new ConferencePtr[1+lastPeriod];
         memset(booked,0,sizeof(ConferencePtr)*(1+lastPeriod));
      }
      booked[period]=C;
   }
   ConferencePtr IsBooked(Period_t period) const 
   {
      if (period>lastPeriodUsed) return 0;
      return  booked[period];
   }
   void TransferConferenceToSpouse(long period)
   {
      assert(IsBooked(period));
      assert(spouse);
      assert(!spouse->IsBooked(period));
      Conference* C=booked[period];
      Unbook(period);
      spouse->Book(C,period);
   }
   void SwapConference(Period_t period1,Parent* P2,
                        Period_t period2)
   {
      Conference* C1=booked[period1];
      assert(C1);
      Unbook(period1);
      Conference* C2=P2->booked[period2];
      assert(C2);
      P2->Unbook(period2);
      Book(C2,period2);
      P2->Book(C1,period1);
   }
   
   void Unbook(long period)
   {
      booked[period]=0;
      if (period==firstPeriodUsed)
      {
         if (period==lastPeriodUsed)
         {
            firstPeriodUsed=lastPeriod+1;
            lastPeriodUsed=0;// reinit
         } else
         {
            while (!booked[++firstPeriodUsed])
               assert(firstPeriodUsed<lastPeriod);
         }
      } else if (period==lastPeriodUsed)
      {
         while (!booked[—lastPeriodUsed])
            assert(lastPeriodUsed>firstPeriod);
      }
      numPeriodsUsed—;
   }
   void RescheduleConference(long oldPeriod,long newPeriod)
   {
      Conference* C=booked[oldPeriod];
      assert(C);
      Unbook(oldPeriod);
      assert(!IsBooked(newPeriod));
      Book(C,newPeriod);
   }
   
   long NumIdlePeriods() const
   {
      long numIdle=0;
      if (lastPeriodUsed)
         numIdle=1+lastPeriodUsed-firstPeriodUsed-numPeriodsUsed;
         
      return numIdle;
   }
   void Show()
   {
      printf("%s, %d, %d\n",Name(),firstPeriod,lastPeriod);
   }
};

class Teacher:public Person
// Collection of teachers functions.
// In this program, teachers have no functions, and are just persons.
{
};

class Child:public Person
// Converts parent names into pointers to parent records.
// Collection of child functions, mostly about their parents though.
{
   union 
   {
      char*   parent1Name;
      Parent*   parent1;
   };
   union 
   {
      char*   parent2Name;
      Parent*   parent2;
   };
   Period_t   parentAvailability;
public:
   Child():parent1(0),parent2(0){}
   Child(char* childName,long xid,char* p1,char* p2) :
      Person(childName,xid),
      parent1Name(p1),
      parent2Name(p2),
      parentAvailability(0)
   {}
   char* Init(char* cp,long xid)
   {
      char* line=Person::Init(cp,xid);
      
      line=LeftTrim(line+1);
      parent1Name=line;
      line=ForwardTo(line,',',kLineEnd);
      bool secondParent=(*line==',');
      *line=0;
      RightTrim(parent1Name,line);
      
      if (secondParent)
      {
         line=LeftTrim(line+1);
         parent2Name=line;
         line=ForwardTo(line,kLineEnd);
         *line=0;
         RightTrim(parent2Name,line);
      } else parent2Name=0;
      parentAvailability=0;// not known until parents are linked
      return line+1;
   }
   char* Parent1Name() const {return parent1Name;}
   char* Parent2Name() const {return parent2Name;}
   
   Parent* Parent1() const {return parent1;}
   Parent* Parent2() const {return parent2;}
   
   void RegisterParents(Parent* p1,Parent* p2)
   {
      assert(!strcmp(p1->Name(),parent1Name));
      parent1=p1;
      if (p2)
      {
         assert(!strcmp(p2->Name(),parent2Name));
         parent2=p2;
      }
   }
   void MarryParents()
   {
      assert(parent1);
      Parent* spouse1=parent1->Spouse();
      if (parent2)
      {
         Parent* spouse2=parent2->Spouse();
         if (!spouse1 && !spouse2)
         {
            parent1->Marries(parent2);
            parent2->Marries(parent1);
         } 
      }
   }
   long ParentAvailability() const {return parentAvailability;}
   void SetParentAvailability()
// because of possibly mixed parent sets, this needs to be computed for each child
   {
      parentAvailability=ComputeParentAvailability();
   }
   long ComputeParentAvailability()   
// returns total number of periods either parent is available
   {
      long p1first=parent1->FirstPeriod();
      long p1last=parent1->LastPeriod();
      long p1length=1+p1last-p1first;
      if (parent2)
      {
         long p2first=parent2->FirstPeriod();
         long p2last=parent2->LastPeriod();
         long p2length=1+p2last-p2first;
         if (p1first<=p2first)
         {
            if (p2first > p1last) return p1length+p2length;
               // disjoint or contiguous
            if (p2first <= p1last) 
               if (p2last>p1last) return 1+p2last-p1first;
               else return p1length;
         } else // p2first < p1first
         {
            if (p1first > p2last) return p1length+p2length;
            // disjoint or contiguous
            if (p1first <= p2last) 
               if (p1last>p2last) return 1+p1last-p2first;
               else return p2length;
         }
      }
      return p1length;
   }
};

class Request:public Person
// Teachers name from file is stored in Person.
// Expansion of the data gathered from the teachers file.
{
   ulong      tempTeacherId;
   Teacher*   teacher;
   union
   {
      char*   childName;
      Child*  child;
   };
   Period_t   assignedPeriod;
   long      priority;
public:
// We rely on memset() to clear all to 0 when an array of Requests is allocated.
   char* Init(char* cp,long xid)
   {
      char* line=LeftTrim(cp);
      childName=line;
      line=ForwardTo(line,',');
      *line=0;
      RightTrim(childName,line);
      
      line=Person::Init(line+1,xid);
      sscanf(++line,"%ld",&priority);
      line=ForwardTo(line,kLineEnd);
      return line+1;
   }
   long Priority() const {return priority;}
   void ReplaceChildName(Child* c)
   {
      assert(!strcmp(c->Name(),childName));
      child=c;
   }
   ulong TempTeacherId() const {return tempTeacherId;}
   void SetTempTeacherId(ulong tid) {tempTeacherId=tid;}
   
   Teacher* TheTeacher() const {return teacher;}
   char* TeacherName() const {return teacher->Name();}
   void SetTeacher(Teacher* theTeacher){teacher=theTeacher;}
   
   char* ChildName() const {return childName;}
   Child* TheChild() const {return child;}
   
   Parent* Parent1() const {return child->Parent1();}
   Parent* Parent2() const {return child->Parent2();}
   Parent* GetAvailableParent(long period) const 
   {
      Parent* parent=Parent1();
      if (parent->IsAvailable(period) && !parent->IsBooked(period))
         return parent;
      parent=Parent2();
      if (parent && parent->IsAvailable(period) && 
                                 !parent->IsBooked(period))
         return parent;
      return 0;
   }
   
   long ParentAvailability()   // precomputed for all parent pairs ahead of time
// returns number of periods either parent is available
   {
      return child->ParentAvailability();
   }
   
   void TransferPriorityTo(Request* uniqueRequest)
   {
      uniqueRequest->priority += priority;
      priority=-1;
   }
   
   long IsAssigned() const {return assignedPeriod;}
   void SetPeriod(Period_t period) {assignedPeriod=period;}
   
   static int CmpParents(const void* a,const void* b)
   // compares parents simply by their address in memory
   {
      Request* ra=(Request*)a;
      Request* rb=(Request*)b;
      int d=ra->Parent1()-rb->Parent1();
      if (d==0)
         return ra->Parent2()-rb->Parent2();
      return d;
   }
   static int CmpPriorities(const void* a,const void* b)
   // highest priority first
   {
      Request* ra=(Request*)a;
      Request* rb=(Request*)b;
      int d=rb->priority-ra->priority;
      return d;
   }
   static int CmpAvailability(const void* a,const void* b)
   // lowest availability first, then highest priority
   {
      Request* ra=(Request*)a;
      Request* rb=(Request*)b;
      int d=ra->ParentAvailability()-rb->ParentAvailability();
      if (d==0)
      {
         d=rb->priority-ra->priority;
      }
      return d;
   }
};


class Conference
// Holds data defining a conference.
// Collection of conference related functions.
{
   Teacher*   teacher;
   Parent*      parent;
   Period_t   period;
   long      priority;
public:
   Teacher* IsAssigned() const {return teacher;}
   void Init(Teacher* t,Parent* p,Period_t x,long y)
   {
      teacher=t;
      parent=p;
      period=x;
      priority=y;
   }
   void Clear() {Init(0,0,0,0);}
   void Copy(Conference& C,Period_t x) 
   {
      teacher=C.teacher;
      parent=C.parent;
      period=x;
      priority=C.priority;
   }
   Teacher* TheTeacher() const {return teacher;}
   Parent* TheParent() const {return parent;}
   const Parent* FirstParent() const 
   {
      assert(parent);
      return parent->FirstParent();
   }
   long Period() const {return period;}
   long Priority() const {return priority;}
   void UpdateParent(Parent* p) {parent=p;}
   int operator - (Conference& r) const 
   {
      int d=r.parent->FirstParent()-parent->FirstParent();
      if (d==0)
         return period-r.period;
      return d;
   }
};

#endif

PT-Utilities.cpp

/* Some basic utilities.
   Mostly self-explanatory.
*/
#include <string.h>
#include "PT-Utilities.h"

void Error(char* s1,char* s2)
{
   printf("%s %s\n",s1,s2);
   exit(0);
}

void Error(char* s1,long x,char* s2)
{
   printf("%s%d%s\n",s1,x,s2);
   exit(0);
}

long FileSize(FILE* f)
{
   long curPos=ftell(f);
   fseek(f,0,SEEK_END);
   long size=ftell(f);
   fseek(f,curPos,SEEK_SET);
   return size;
}

PT-Utilities.h

#ifndef PT_UTILITIES_H
#define PT_UTILITIES_H

/*
   Prototypes of utilities, and a generic comparator.
   Mostly self-explanatory.
*/

#include <stdio.h>
#include <stdlib.h>

typedef unsigned char uchar;
typedef unsigned long ulong;
typedef unsigned short ushort;

void Error(char* s1,char* s2);
void Error(char* s1,long x,char* s2);

long FileSize(FILE* f);


template <class T>
inline int Cmp(const void* a,const void* b)
// Generic comparator for qsort and bsearch
// Uses operator - of <T> for the actual comparison
{
   return *((T*)a) - *((T*)b);
}


#endif

PT-Files.h

#ifndef PT_FILES_H
#define PT_FILES_H

/*
   File classes.
   Mostly self-explanatory.
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "PT-compile-constants.h"
#include "PT-Persons.h"

static char inputFileName[]      =INPUT_DIRECTORY"input.txt";
static char childrenFileName[]   =INPUT_DIRECTORY"childrenNN.txt";
static char teachersFileName[]   =INPUT_DIRECTORY"teachersNN.txt";
static char schedulesFileName[]   =INPUT_DIRECTORY"schedulesNN.txt";
static char outputFileName[]   =INPUT_DIRECTORY"conferencesNN.txt";
static char logFileName[]      =INPUT_DIRECTORY"log.txt";

enum {kOutputFileBufferSize=1024};

inline void SetFilename(char* name,unsigned long number)
// Repaces NN with a 2-digit number in a file name 
{
   assert(number<=99);
   int len=strlen(name);
   assert(len>=6);
   char NN[4];
   sprintf(NN,"%02d",number);
   name[len-6]=NN[0];
   name[len-5]=NN[1];
}

class InputFile
// Only used to read the number of tests.
{
public:
   static long GetNumTests()
   {
      FILE* f=fopen(inputFileName,"rb");
      if (!f) Error(inputFileName,"not found");
      char line[kLineLength+1];
      fgets(line,kLineLength,f);
      long numTests;
      sscanf(line,"%ld",&numTests);
      fclose(f);
      return numTests;
   }
};


class TextFile
// Generic ancestor for text files.
// Reads the entire file into memory.
// Derived classes are required to parse the text in memory.
{
   long   capacity;
   char*   fileStore;
public:
   TextFile() : fileStore(0) {}
   char* FileStore() const {return fileStore;}
   long  Capacity() const {return capacity;} 
   long Read(char* fileName)
// reads file into fileStore
// returns number of text lines read
   {
      FILE* f=fopen(fileName,"rb");
      assert(f);
      capacity=FileSize(f);
      try {
         fileStore=new char[1+capacity];// add 1 for NULL char at end
      } catch(...) {
         Error("Could not allocate storage for",fileName);
      }
      long numRead=fread(fileStore,1,capacity,f);
      assert (capacity == numRead); 
      fclose(f);
      fileStore[capacity]=0;// zero terminate
      return LineCount();
   }
   ~TextFile() 
   {
      if (fileStore)
         delete [] fileStore;
      fileStore=0;
   }
private:
   long LineCount()// assumes single line end character (Mac)
   {
      char* cp=fileStore-1;
      char c=*cp;
      long count=0;
      while (c)
      {
         if (c==kLineEnd) count++;
         c=*(++cp);
      }
      c=*(—cp);
      if (c != kLineEnd) count++;
      return count;
   }
};

class SchedulesFile:public TextFile,public Person
// Reads the PT-schedules file and sorts parents by name.
// Person class contains the "ForwardTo" function required here.
{
   Parent* parents;
public:
   SchedulesFile(long testNumber,long& numPeriods,
                        Parent* & xparents,long& numParents)
   {
      SetFilename(schedulesFileName,testNumber);
      numParents=Read(schedulesFileName)-1;
      try {
         parents=new Parent[numParents];
         xparents=parents;
      } catch(...) {
         Error("Could not allocate storage for","parents");
      }
      char* cp=FileStore();
      sscanf(cp,"%ld",&numPeriods);
      if (numPeriods>MAXNUMPERIODS)
      {
         Error(
            "The number of periods exceeds MAXNUMPERIODS = ",
            MAXNUMPERIODS,
         "\nPlease adjust MAXNUMPERIODS in PT-compile-constants.h, and recompile");
      }
      cp=1+ForwardTo(cp,kLineEnd);
      for (long i=0;i<numParents;i++)
      {
         assert(*cp);
         cp=parents[i].Init(cp,i);
      }
      qsort(parents,numParents,sizeof(Parent),Cmp<Parent>);
   }
   ~SchedulesFile(){delete [] parents;}
};

class ChildrenFile:public TextFile
// Reads the PT-children file and sorts children by name.
{
   Child* children;
public:
   ChildrenFile(long testNumber,Child* & xchildren,
                  long& numChildren)
   {
      SetFilename(childrenFileName,testNumber);
      numChildren=Read(childrenFileName);
      try {
         children=new Child[numChildren];
         xchildren=children;
      } catch(...) {
         Error(“Could not allocate storage for”,”children”);
      }
      char* cp=FileStore();
      for (long i=0;i<numChildren;i++)
      {
         assert(*cp);
         
         cp=children[i].Init(cp,i);
      }
      qsort(children,numChildren,sizeof(Child),Cmp<Child>);
   }
   ~ChildrenFile(){delete [] children;}
};

class TeachersFile:public TextFile
// Reads the PT-teachers file.
{
   Request* requests;
public:
   TeachersFile(long testNumber,Request* & xrequests,
               long& numRequests)
   {
      SetFilename(teachersFileName,testNumber);
      numRequests=Read(teachersFileName);
      try {
         requests=new Request[numRequests];
         memset(requests,0,sizeof(Request)*numRequests);
         xrequests=requests;
      } catch(...) {
         Error(“Could not allocate storage for”,”requests”);
      }
      char* cp=FileStore();
      for (long i=0;i<numRequests;i++)
      {
         assert(*cp);
         cp=requests[i].Init(cp,i);
      }
      qsort(requests,numRequests,sizeof(Request),Cmp<Request>);
   }
   ~TeachersFile(){delete [] requests;}
};

class OutputFile:public TextFile
// Handles the PT-conferences output file.
{
   FILE*   f; 
public:
   OutputFile(long testNumber):f(0)
   {
      SetFilename(outputFileName,testNumber);
   }
   void Open()
   {
      f=fopen(outputFileName,"w");
      assert(f);
   }
   void Close() {fclose(f);}
   void SendConference(Conference& C)
   {
      assert(C.IsAssigned());
      fprintf(f,"%s,%s,%d\n",
      C.TheTeacher()->Name(),C.TheParent()->Name(),C.Period());
   }
};

class LogFile
// Handles the PT-log file.
// Log events are stored here, and output together with a single routine.
{
   long   numTests;
   double* executionTime;
public:
   LogFile(long n) :
      numTests(n),
      executionTime(new double[1+n])// tests are numbered 1 to n
   {
      memset(executionTime,0,sizeof(double)*(1+n));
   }
   ~LogFile(){delete [] executionTime;}
   void Set(long testNumber,double time)
   {
      executionTime[testNumber]=time;
   }
   void Send()
   {
      FILE* f=fopen(logFileName,"w");
      assert(f);
      for (long testNumber=1;testNumber<=numTests;testNumber++)
      {
         fprintf(f,"%10.3f\n",executionTime[testNumber]);
      } 
      fclose(f);
   }
};

#endif

MyTimer.h

#ifndef MYTIMER_H
#define MYTIMER_H

/* Basic microsecond timer class. */
#include <Timer.h>

class MyTimer
{
   UnsignedWide startTime;
public:
   MyTimer(){Restart();}
   void Restart() {Microseconds(&startTime);} 
   double ElapsedMilliSecs() const 
   {
        UnsignedWide endTime;
        Microseconds(&endTime);
        return ((endTime.lo-startTime.lo)/1000.0);
   }   
};

#endif

PT-Compile-Constants.h

#ifndef PT_COMPILE_CONSTANTS_H
#define PT_COMPILE_CONSTANTS_H
/*
   Compile policies.
   Mostly self-explanatory.
*/

#define DBG 0

#if __profile__
#undef DBG
#define DBG 0
#endif


#if !DBG
#define NDEBUG
#endif

#include <assert.h>

#define xINLINE_RECURSIVES 1

#define INPUT_DIRECTORY //"::InputData:"

#define MAXNUMPERIODS 255

#endif


 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Spotify 1.2.0.1165 - Stream music, creat...
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
Thunderbird 102.5.1 - Email client from...
As of July 2012, Thunderbird has transitioned to a new governance model, with new features being developed by the broader free software and open source community, and security fixes and improvements... Read more
Pinegrow 7.03 - Mockup and design web pa...
Pinegrow (was Pinegrow Web Designer) is desktop app that lets you mockup and design webpages faster with multi-page editing, CSS and LESS styling, and smart components for Bootstrap, Foundation,... Read more
Adobe After Effects 2022 23.1 - Create p...
The new, more connected Adobe After Effects can make the impossible possible. Get powerful new features like a Live 3D Pipeline that brings CINEMA 4D scenes in as layers - without intermediate... Read more
SteerMouse 5.6.7 - Powerful third-party...
SteerMouse is an advanced driver for USB and Bluetooth mice. SteerMouse can assign various functions to buttons that Apple's software does not allow, including double-clicks, modifier clicks,... Read more
Wireshark 4.0.2 - Network protocol analy...
Wireshark is one of the world's foremost network protocol analyzers, and is the standard in many parts of the industry. It is the continuation of a project that started in 1998. Hundreds of... Read more
Adobe Premiere Pro 2022 23.1 - Digital v...
Adobe Premiere Pro is available as part of Adobe Creative Cloud for as little as $54.99/month. The price on display is a price for annual by-monthly plan for Adobe Premiere Pro only. Adobe Premiere... Read more
1Password 8.9.10 - Powerful password man...
1Password is a password manager that uniquely brings you both security and convenience. It is the only program that provides anti-phishing protection and goes beyond password management by adding Web... Read more
FotoMagico 6.3 - Powerful slideshow crea...
FotoMagico lets you create professional slideshows from your photos and music with just a few, simple mouse clicks. It sports a very clean and intuitive yet powerful user interface. High image... Read more
Affinity Photo 1.10.6 - Digital editing...
Affinity Photo - redefines the boundaries for professional photo editing software for the Mac. With a meticulous focus on workflow it offers sophisticated tools for enhancing, editing and retouching... Read more

Latest Forum Discussions

See All

‘Awaken Legends: Idle RPG’ Celebrates th...
Awaken Legends: Idle RPG is adding its first update since the game was soft-launched in November, letting players get their hands on a new hero “Hera Valen". Players can also look forward to the Covenant of the Dark Knight event and the Wishing Well... | Read more »
‘Horizon Chase 2’ Japan World Tour Expan...
Horizon Chase 2 () from Aquiris is getting a major expansion today on Apple Arcade. The Japan World Tour expansion brings in 11 new races across 9 cities and it should be rolling out now as of this writing. I expect it to be available worldwide... | Read more »
Dark Fantasy Visual Novel ‘The 13th Mont...
Originally announced for release in August, The 13th Month from Japanese developer Kobayashimaru and publisher Kodansha released on PC via Steam worldwide this month. The dark fantasy visual novel that reimagines the classic Sleeping Beauty tale, is... | Read more »
Tom Clancey’s The Divison Resurgence ann...
Ubisoft has announced the latest Live Test dates for Tom Clancy’s The Division Resurgence, the hotly anticipated mobile entry in the Divison series. Starting December 8th and ending on the 22nd, the test will offer a huge amount of content for the... | Read more »
‘Easy Come Easy Golf’ New Update Adds St...
Easy Come Easy Golf () from Clap Hanz is one of my favorite games on Apple Arcade. It has been updated quite a bit since launch bringing in new modes and improvements. It recently launched on Nintendo Switch as well. | Read more »
Out Now: ‘Magic vs Metal’, ‘Suzerain’, ‘...
Each and every day new mobile games are hitting the App Store, and so each week we put together a big old list of all the best new releases of the past seven days. Back in the day the App Store would showcase the same games for a week, and then... | Read more »
SwitchArcade Round-Up: Reviews Featuring...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for December 7th, 2022. Today can be accurately described as Mikhail Madness, with a whopping four reviews from our pal-est of pals. Football Manager 2023 Touch, Wobbledogs, Soccer Story... | Read more »
Alchemy Stars celebrates 1 and a half ye...
It has been one and a half years since Alchemy Stars launched, and Level Infinite is celebrating in style with a host of new content. There will be a new story mission and even a store to explore, and a whole new mode for those budding idol... | Read more »
Fighting Game ‘Art of Fighting 2’ ACA Ne...
Last week, side-scrolling shooter Pulstar hit mobile platforms as the newest ACA NeoGeo series release from Hamster and SNK. Read Shaun’s review of it here. Today, fighting game Art of Fighting 2 has launched on iOS and Android. Art of Fighting 2... | Read more »
‘Genshin Impact’ Version 3.3 Update Now...
HoYoverse recently revealed the next major update for Genshin Impact (Free) in the form of version 3.3 ‘All Senses Clear, All Existence Void’. | Read more »

Price Scanner via MacPrices.net

New! Details on Verizon’s Christmas/Holiday p...
Verizon is offering discounts on iPhones, Apple Watch models, and iPads with specific promo codes as part of their Christmas/Holiday 2022 offerings. Codes are valid when adding a new line of service... Read more
Apple MagSafe accessories are back on Holiday...
Amazon has Apple MagSafe Chargers and Apple’s MagSafe Battery on sale for up to 24% off MSRP again as part of their Christmas/Holiday sale. Shipping is free, and all models are in stock: – MagSafe... Read more
13″ M2 MacBook Airs on sale again for the low...
Amazon has 13″ MacBook Airs with M2 CPUs in stock today and on sale for $150 off MSRP as part of their Christmas/Holiday Sale, prices start at $1049. Shipping is free. They are the lowest prices... Read more
Get an Apple 16″ MacBook Pro for $400 off MSR...
16″ MacBook Pros with Apple’s M1 Pro CPUs are in stock and on sale today at B&H Photo for $300-$400 off Apple’s MSRP for a limited time. Prices start at $2099 for M1 Pro models with 512GB or 1TB... Read more
Holiday clearance sale! Previous-generation A...
Amazon has 2nd generation 32GB and 64GB 4K Apple TVs with Siri remotes and 32GB Apple TV HDs on clearance sale for $80-$90 off original MSRP. Shipping is free, and delivery is available in time for... Read more
Christmas sale at Verizon: Apple AirPods Pro...
Verizon has first-generation Apple AirPods Pro on sale for $159.99 on their online store as part of their continuing Christmas/Holiday sale. Their price is $90 off Apple’s original MSRP, and it’s the... Read more
New Christmas/New Years promo at Xfinity Mobi...
Switch to Xfinity Mobile and open a new line of service, and take $400 off the price of a new iPhone, no trade-in required, through January 10, 2023. The $400 is applied to your account as credits... Read more
Apple iPad Smart Keyboard Folio prices drop u...
Apple iPad Smart Keyboard Folio prices have dropped up to $60 off MSRP at Amazon and Walmart as part of their Christmas/Holiday sales. These are the cheapest prices currently available for these iPad... Read more
Today is the final day for Xfinity Mobile’s $...
If you switch to Xfinity Mobile and open a new line of service, they will take $500 off the price of a new iPhone, no trade-in required. This is the best no trade-in Cyber Monday Apple iPhone 14 deal... Read more
Amazon restocks 10.2″ 64GB 9th-generation iPa...
Amazon has Apple’s 9th generation 10.2″ 64GB WiFi iPads (Silver) in stock and on sale for $269.99 shipped as part of their Christmas/Holiday Sale. Their price is $60 off Apple’s MSRP. Free delivery... Read more

Jobs Board

*Apple* Systems Administrator - JAMF - Activ...
…Administration **Duties and Responsibilities** + Configure and maintain the client's Apple Device Management (ADM) solution. The current solution is JAMF supporting 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
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
Sephora Beauty Advisor - *Apple* Blossom Ma...
Sephora Beauty Advisor - 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
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.