Cpp Freecell Solver: FCSMove.cpp Source File

00001 
00002 
00003 
00004 
00005 
00006 
00007 
00008 
00009 
00010 #include <stdlib.h>
00011 #include <string.h>
00012 #include <stdio.h>
00013 #include <assert.h>
00014 #include "FCSMove.h"
00015 #include "FCSDebugMove.h"
00016 #include "FCSCompactMove.h"
00017 #include "FCState.h"
00018 #include "FCTalonState.h"
00019 #include "FCHelpingAlgorithms.h"
00020 
00021 FCSMove* FCSMove::Create()
00022 {
00023     switch (GlobalStateType)
00024     {
00025     case FC_DEBUG_STATE:
00026     case FC_TALON_DEBUG_STATE:
00027         return new FCSDebugMove();
00028     case FC_COMPACT_STATE:
00029     case FC_INDIRECT_STATE:
00030     case FC_TALON_COMPACT_STATE:
00031     case FC_TALON_INDIRECT_STATE:
00032         return new FCSCompactMove();
00033     default:
00034         return NULL;
00035     }
00036 }
00037 
00038 FCSMove* FCSMove::CreateArray(int Size)
00039 {
00040     switch (GlobalStateType)
00041     {
00042     case FC_DEBUG_STATE:
00043     case FC_TALON_DEBUG_STATE:
00044         return new FCSDebugMove[Size];
00045     case FC_COMPACT_STATE:
00046     case FC_INDIRECT_STATE:
00047     case FC_TALON_COMPACT_STATE:
00048     case FC_TALON_INDIRECT_STATE:
00049         return new FCSCompactMove[Size];
00050     default:
00051         return NULL;
00052     }
00053 }
00054 
00055 void FCSMove::MoveAsString(char* String)
00056 {
00057     switch(GetType())
00058     {
00059         case FCS_MOVE_TYPE_STACK_TO_STACK:
00060             sprintf(String, "Move %i cards from stack %i to stack %i",
00061                     GetNumberOfCardsInSequence(),
00062                     GetSourceStack(),
00063                     GetDestStack() );
00064             return;
00065         case FCS_MOVE_TYPE_FREECELL_TO_STACK:
00066             sprintf(String, "Move a card from freecell %i to stack %i",
00067                     GetSourceFreecell(),
00068                     GetDestStack());
00069             return;
00070         case FCS_MOVE_TYPE_FREECELL_TO_FREECELL:
00071             sprintf(String, "Move a card from freecell %i to freecell %i",
00072                     GetSourceFreecell(),
00073                     GetDestFreecell());
00074             return;
00075         case FCS_MOVE_TYPE_STACK_TO_FREECELL:
00076             sprintf(String, "Move a card from stack %i to freecell %i",
00077                     GetSourceStack(),
00078                     GetDestFreecell());
00079             return;
00080         case FCS_MOVE_TYPE_STACK_TO_FOUNDATION:
00081             sprintf(String, "Move a card from stack %i to the foundations", GetSourceStack());
00082             return;
00083         case FCS_MOVE_TYPE_FREECELL_TO_FOUNDATION:
00084             sprintf(String, "Move a card from freecell %i to the foundations", GetSourceFreecell());
00085             return;
00086         case FCS_MOVE_TYPE_SEQ_TO_FOUNDATION:
00087             sprintf(String, "Move the sequence on top of Stack %i to the foundations", GetSourceStack());
00088             return;
00089         case FCS_MOVE_TYPE_KLONDIKE_TALON_TO_STACK:
00090             sprintf(String, "Move top talon card to Stack %i", GetDestStack());
00091             return;
00092         case FCS_MOVE_TYPE_KLONDIKE_TALON_TO_FOUNDATION:
00093             sprintf(String, "Move top talon card to the foundations");
00094             return;
00095         case FCS_MOVE_TYPE_KLONDIKE_FLIP_TALON:
00096 //          if (GetNumberOfCardsFlipped() > 0)
00097                 sprintf(String, "Flip %i cards from the talon deck", GetNumberOfCardsFlipped());
00098             return;
00099         case FCS_MOVE_TYPE_KLONDIKE_REDEAL_TALON:
00100             sprintf(String, "Restart the talon deck");
00101             return;
00102         case FCS_MOVE_TYPE_FLIP_CARD:
00103             sprintf(String, "Flip top card from Stack %i", GetSourceStack());
00104             return;
00105         default:
00106             String = NULL;
00107             return;
00108     }
00109 
00110     //this shouldn't happen
00111     assert(false);
00112 }
00113 
00114 void FCSMove::MoveAsStringStandardNotation(char* String)
00115 {
00116     switch(GetType())
00117     {
00118         case FCS_MOVE_TYPE_STACK_TO_STACK:
00119             sprintf(String, "%i%i", 1+GetSourceStack(), 1+GetDestStack());
00120             return;
00121         case FCS_MOVE_TYPE_FREECELL_TO_STACK:
00122             sprintf(String, "%c%i", 'a'+GetSourceFreecell(), 1+GetDestStack());
00123             return;
00124         case FCS_MOVE_TYPE_FREECELL_TO_FREECELL:
00125             sprintf(String, "%c%c", 'a'+GetSourceFreecell(), 'a'+GetDestFreecell());
00126             return;
00127         case FCS_MOVE_TYPE_STACK_TO_FREECELL:
00128             sprintf(String, "%i%c", 1+GetSourceStack(), 'a'+GetDestFreecell());
00129             return;
00130         case FCS_MOVE_TYPE_STACK_TO_FOUNDATION:
00131             sprintf(String, "%ih", 1+GetSourceStack());
00132             return;
00133         case FCS_MOVE_TYPE_FREECELL_TO_FOUNDATION:
00134             sprintf(String, "%ch", 'a'+GetSourceFreecell());
00135             return;
00136         case FCS_MOVE_TYPE_SEQ_TO_FOUNDATION:
00137             sprintf(String, "%ih", GetSourceStack());
00138             return;
00139         default:
00140             String = NULL;
00141             return;
00142     }
00143 
00144     //this shouldn't happen
00145     assert(false);
00146 }
00147 
00148 FCSMoveStack::FCSMoveStack()
00149 {
00150     m_MaxNumberOfMoves = FCS_MOVE_STACK_GROW_BY;
00151     m_NumberOfMoves = 0;
00152 }
00153 
00154 FCSMoveStack::~FCSMoveStack()
00155 {
00156 }
00157 
00158 void FCSMoveStack::Normalize(FCSStateWithLocations* InitialState, 
00159                              int NumberOfFreecells, int NumberOfStacks, int NumberOfDecks)
00160 {
00161     FCSMoveStack* TempMoves = CreateMoveStack();
00162     FCSMove *InMove = FCSMove::Create(),
00163             *OutMove = FCSMove::Create();
00164 
00165     FCSStateWithLocations* DynamicState = CreateStateWithLocations();
00166     DynamicState->Copy(InitialState);
00167 
00168     while (Pop(&InMove) == 0)
00169     {
00170         ApplyMove(DynamicState, InMove, NumberOfFreecells, NumberOfStacks, NumberOfDecks);
00171 
00172         if (InMove->GetType() != FCS_MOVE_TYPE_CANONIZE)
00173         {
00174             OutMove->SetType(InMove->GetType());
00175 
00176             switch(InMove->GetType())
00177             {
00178             case FCS_MOVE_TYPE_STACK_TO_STACK:
00179                 OutMove->SetSourceStack(DynamicState->m_StackLocations[InMove->GetSourceStack()]);
00180                 OutMove->SetDestStack(DynamicState->m_StackLocations[InMove->GetDestStack()]);
00181                 OutMove->SetNumberOfCardsInSequence(InMove->GetNumberOfCardsInSequence());
00182                 break;
00183             case FCS_MOVE_TYPE_STACK_TO_FREECELL:
00184                 OutMove->SetSourceStack(DynamicState->m_StackLocations[InMove->GetSourceStack()]);
00185                 OutMove->SetDestFreecell(DynamicState->m_FreecellLocations[InMove->GetDestFreecell()]);
00186                 break;
00187             case FCS_MOVE_TYPE_STACK_TO_FOUNDATION:
00188                 OutMove->SetSourceStack(DynamicState->m_StackLocations[InMove->GetSourceStack()]);
00189                 OutMove->SetFoundation(InMove->GetFoundation());
00190                 break;
00191             case FCS_MOVE_TYPE_SEQ_TO_FOUNDATION:
00192                 OutMove->SetSourceStack(DynamicState->m_StackLocations[InMove->GetSourceStack()]);
00193                 OutMove->SetFoundation(InMove->GetFoundation());
00194                 break;
00195             case FCS_MOVE_TYPE_FREECELL_TO_STACK:
00196                 OutMove->SetSourceFreecell(DynamicState->m_FreecellLocations[InMove->GetSourceFreecell()]);
00197                 OutMove->SetDestStack(DynamicState->m_StackLocations[InMove->GetDestStack()]);
00198                 break;
00199             case FCS_MOVE_TYPE_FREECELL_TO_FREECELL:
00200                 OutMove->SetSourceFreecell(DynamicState->m_FreecellLocations[InMove->GetSourceFreecell()]);
00201                 OutMove->SetDestFreecell(DynamicState->m_FreecellLocations[InMove->GetDestFreecell()]);
00202                 break;
00203             case FCS_MOVE_TYPE_FREECELL_TO_FOUNDATION:
00204                 OutMove->SetSourceFreecell(DynamicState->m_FreecellLocations[InMove->GetSourceFreecell()]);
00205                 OutMove->SetFoundation(InMove->GetFoundation());
00206                 break;
00207             case FCS_MOVE_TYPE_KLONDIKE_TALON_TO_STACK:
00208                 OutMove->SetDestStack(DynamicState->m_StackLocations[InMove->GetDestStack()]);
00209                 break;
00210             case FCS_MOVE_TYPE_KLONDIKE_TALON_TO_FOUNDATION:
00211                 OutMove->SetFoundation(InMove->GetFoundation());
00212                 break;
00213             case FCS_MOVE_TYPE_KLONDIKE_FLIP_TALON:
00214                 OutMove->SetNumberOfCardsFlipped(InMove->GetNumberOfCardsFlipped());
00215                 break;
00216             case FCS_MOVE_TYPE_KLONDIKE_REDEAL_TALON:
00217                 break;
00218             case FCS_MOVE_TYPE_FLIP_CARD:
00219                 OutMove->SetSourceStack(DynamicState->m_StackLocations[InMove->GetSourceStack()]);
00220                 break;
00221             default:
00222                 assert(false);
00223             }
00224 
00225             TempMoves->Push(OutMove);
00226         }
00227     }
00228 
00229     // TempMoves contain the needed moves in reverse order. So let's use
00230     // SwallowStack to put them in the original in the correct order.
00231 
00232     Reset();
00233 
00234     SwallowStack(TempMoves);
00235 
00236     DynamicState->CleanState();
00237 
00238     delete DynamicState;
00239     delete InMove;
00240     delete OutMove;
00241 }
00242 
00243 void FCSMoveStack::Reset()
00244 {
00245     m_NumberOfMoves = 0;
00246 }
00247 
00248 void FCSMoveStack::SwallowStack(FCSMoveStack* SrcStack)
00249 {
00250     FCSMove *Move = FCSMove::Create();
00251     while (!SrcStack->Pop(&Move))
00252         Push(Move);
00253 
00254     delete Move;
00255     delete SrcStack;
00256 }
00257 
00258 int FCSMoveStack::GetNumberOfMoves()
00259 {
00260     return m_NumberOfMoves;
00261 }
00262 
00263 FCSMoveStack* CreateMoveStack()
00264 {
00265     switch(GlobalStateType)
00266     {
00267     case FC_DEBUG_STATE:
00268     case FC_TALON_DEBUG_STATE:
00269         return new FCSDebugMoveStack();
00270     case FC_COMPACT_STATE:
00271     case FC_INDIRECT_STATE:
00272     case FC_TALON_COMPACT_STATE:
00273     case FC_TALON_INDIRECT_STATE:
00274         return new FCSCompactMoveStack();
00275     default:
00276         return NULL;
00277     }
00278 }
00279 
00280 void ReallocMoveStackArray(FCSMoveStack*** Array, int OldSize, int NewSize)
00281 {
00282     switch (GlobalStateType)
00283     {
00284     case FC_DEBUG_STATE:
00285     case FC_TALON_DEBUG_STATE:
00286         Realloc<FCSDebugMoveStack*>((FCSDebugMoveStack***)Array, OldSize, NewSize);
00287         break;
00288     case FC_COMPACT_STATE:
00289     case FC_INDIRECT_STATE:
00290     case FC_TALON_COMPACT_STATE:
00291     case FC_TALON_INDIRECT_STATE:
00292         Realloc<FCSCompactMoveStack*>((FCSCompactMoveStack***)Array, OldSize, NewSize);
00293         break;
00294     default:
00295         //this shouldn't happen
00296         assert(false);
00297     }
00298 }
00299 
00300 void ApplyMove(FCSStateWithLocations* StateWithLocations, FCSMove* Move, 
00301                     int NumberOfFreecells, int NumberOfStacks, int NumberOfDecks)
00302 {
00303     FCSCard* TempCard;
00304     int SourceStack = Move->GetSourceStack(),
00305         DestStack = Move->GetDestStack(),
00306         SourceFreecell = Move->GetSourceFreecell(), 
00307         DestFreecell = Move->GetDestFreecell(),
00308         SourceStackLength,
00309         a;
00310 
00311     switch(Move->GetType())
00312     {
00313         case FCS_MOVE_TYPE_STACK_TO_STACK:
00314             SourceStackLength = StateWithLocations->GetStackLength(SourceStack);
00315 
00316             TempCard = FCSCard::Create();
00317             for(a=0; a<Move->GetNumberOfCardsInSequence(); a++)
00318             {
00319                 StateWithLocations->PushStackCardIntoStack(DestStack, SourceStack,
00320                     SourceStackLength - Move->GetNumberOfCardsInSequence() + a);
00321             }
00322             
00323             for(a=0; a<Move->GetNumberOfCardsInSequence(); a++)
00324             {
00325                 StateWithLocations->PopStackCard(SourceStack, TempCard);
00326             }
00327 
00328             delete TempCard;
00329             break;
00330         case FCS_MOVE_TYPE_FREECELL_TO_STACK:
00331             StateWithLocations->PushCardIntoStack(DestStack, StateWithLocations->GetFreecellCard(SourceFreecell));
00332             StateWithLocations->EmptyFreecell(SourceFreecell);
00333             break;
00334         case FCS_MOVE_TYPE_FREECELL_TO_FREECELL:
00335             TempCard = StateWithLocations->GetFreecellCard(SourceFreecell);
00336             StateWithLocations->PutCardInFreecell(DestFreecell, TempCard);
00337             StateWithLocations->EmptyFreecell(SourceFreecell);
00338             break;
00339         case FCS_MOVE_TYPE_STACK_TO_FREECELL:
00340             TempCard = FCSCard::Create();
00341             StateWithLocations->PopStackCard(SourceStack, TempCard);
00342             StateWithLocations->PutCardInFreecell(DestFreecell, TempCard);
00343             delete TempCard;
00344             break;
00345         case FCS_MOVE_TYPE_STACK_TO_FOUNDATION:
00346             TempCard = FCSCard::Create();
00347             StateWithLocations->PopStackCard(SourceStack, TempCard);
00348             StateWithLocations->IncrementFoundation(Move->GetFoundation());
00349             delete TempCard;
00350             break;
00351         case FCS_MOVE_TYPE_FREECELL_TO_FOUNDATION:
00352             StateWithLocations->EmptyFreecell(SourceFreecell);
00353             StateWithLocations->IncrementFoundation(Move->GetFoundation());
00354             break;
00355         case FCS_MOVE_TYPE_SEQ_TO_FOUNDATION:
00356             TempCard = FCSCard::Create();
00357             for(a=0;a<13;a++)
00358             {
00359                 StateWithLocations->PopStackCard(SourceStack, TempCard);
00360                 StateWithLocations->IncrementFoundation(Move->GetFoundation());
00361             }
00362             delete TempCard;
00363             break;
00364         case FCS_MOVE_TYPE_FLIP_CARD:
00365             StateWithLocations->FlipStackCard(SourceStack, 
00366                         StateWithLocations->GetStackLength(SourceStack) - 1);
00367             break;
00368         case FCS_MOVE_TYPE_CANONIZE:
00369             StateWithLocations->CanonizeState(NumberOfFreecells, NumberOfStacks);
00370             break;
00371         case FCS_MOVE_TYPE_KLONDIKE_TALON_TO_STACK:
00372             StateWithLocations->PushCardIntoStack(DestStack, ((FCSTalonStateWithLocations*)StateWithLocations)->GetTalonData()->GetKlondikeTalonTopCard());
00373             ((FCSTalonStateWithLocations*)StateWithLocations)->DecrementKlondikeTalonStack();
00374             break;
00375         case FCS_MOVE_TYPE_KLONDIKE_TALON_TO_FOUNDATION:
00376             StateWithLocations->IncrementFoundation(Move->GetFoundation());
00377             ((FCSTalonStateWithLocations*)StateWithLocations)->DecrementKlondikeTalonStack();
00378             break;
00379         case FCS_MOVE_TYPE_KLONDIKE_FLIP_TALON:
00380             for (a=0;a<Move->GetNumberOfCardsFlipped();a++)
00381                 ((FCSTalonStateWithLocations*)StateWithLocations)->GetTalonData()->KlondikeTalonQueueToStack();
00382             break;
00383         case FCS_MOVE_TYPE_KLONDIKE_REDEAL_TALON:
00384             ((FCSTalonStateWithLocations*)StateWithLocations)->GetTalonData()->KlondikeTalonRedealBare();
00385             break;
00386         default:
00387         {
00388             assert(false);
00389         }
00390     }
00391 }