Guest User

Chinchon

a guest
Apr 24th, 2013
187
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 12.36 KB | None | 0 0
  1. // Test.cpp : Defines the entry point for the console application.
  2. //
  3.  
  4. #include "stdafx.h"
  5.  
  6. #include <cmath>
  7. #include <vector>
  8. #include <list>
  9. #include <cassert>
  10. #include <cstdarg>
  11. #include <algorithm>
  12.  
  13. #define VERBOSE 0
  14.  
  15. typedef int INT;
  16. typedef unsigned int  UINT;
  17. typedef unsigned long ULONG;
  18.  
  19. //  todo quitar push invertido (no es necesario)
  20.  
  21. struct _Log
  22. {
  23.     void Print( const char* format, ... )
  24.     {
  25. #if VERBOSE
  26.         for( INT i=0; i<NUMTABS; ++i ) { printf("  "); }
  27. #endif
  28.         va_list args;
  29.         va_start( args, format );
  30.         vprintf( format, args );
  31.         va_end( args );
  32.     }
  33.     void Push()
  34.     {
  35.         ++NUMTABS;
  36.     }
  37.     void Pop() {
  38.         --NUMTABS;
  39.         assert( NUMTABS >= 0 );
  40.     }
  41. private:
  42.     INT NUMTABS;
  43. } Log;
  44.  
  45. struct ScoreTrack
  46. {
  47.     ScoreTrack() { Reset(); }
  48.  
  49.     enum
  50.     {
  51.         TOKEN_START = 0
  52.         , ESCALERA
  53.         , MATCH3 = 3
  54.         , MATCH4
  55.         , MATCH5
  56.         , MATCH6
  57.         , MATCH7
  58.         , FREE
  59.         , TOKEN_END
  60.     };
  61.  
  62.     void PushEscalera()
  63.     {
  64.         Combinacion.push_back( ESCALERA );
  65.     }
  66.     void PushMatch( UINT Reps )
  67.     {
  68.         assert( Reps >= MATCH3 && Reps <= MATCH7 );
  69.         Combinacion.push_back( Reps );
  70.     }
  71.     void PushFree()
  72.     {
  73.         Combinacion.push_back( FREE );
  74.     }
  75.     void PushVal( UINT v )
  76.     {
  77.         while ( v > 500 ) { v -= 400; }
  78.         Combinacion.push_back( v );    
  79.     }
  80.     bool IsBackToken() const
  81.     {
  82.         UINT Val = Combinacion.back();
  83.         return ( Val > TOKEN_START && Val < TOKEN_END );
  84.     }
  85.     void Pop()
  86.     {
  87.         assert( Combinacion.size() > 0 && !IsBackToken() );
  88.         do
  89.         {
  90.             Combinacion.pop_back();
  91.         } while( !IsBackToken() );
  92.         Combinacion.pop_back();
  93.     }
  94.     ULONG GetScore() const
  95.     {
  96.         return Score;
  97.     }
  98.     bool IsEmpty()
  99.     {
  100.         return Combinacion.empty();
  101.     }
  102.     void Reset()
  103.     {
  104.         Score = 666;
  105.         Combinacion.clear();
  106.     }
  107.     void Print()
  108.     {
  109.         Log.Print( " Mejor Jugada:\n" );
  110.         for( UINT i=0; i<Combinacion.size(); ++i )
  111.         {
  112.             if ( Combinacion[i] == ESCALERA )
  113.             {
  114.                 printf( "  | - Escalera = {" );
  115.             }
  116.             else if ( Combinacion[i] >= MATCH3 && Combinacion[i] <= MATCH7 )
  117.             {
  118.                 printf( "  | - Match x%d = {", Combinacion[i] );
  119.  
  120.                 // Porque hago push invertido
  121.                 for ( UINT j = i + Combinacion[i]; j > i ; --j )
  122.                 {                    
  123.                     if ( j == i+1 )
  124.                     {
  125.                         printf( "%d}\n", Combinacion[j] );
  126.                     }
  127.                     else
  128.                     {
  129.                         printf( "%d, ", Combinacion[j] );
  130.                     }                    
  131.                 }
  132.                 i = i + Combinacion[i];
  133.             }
  134.             else if ( Combinacion[i] == FREE )
  135.             {
  136.                 printf( "  | - Libres   = {" );
  137.             }
  138.             else
  139.             {
  140.                 UINT Next = i+1;
  141.                 if ( Next >= Combinacion.size() || ( Combinacion[Next] < TOKEN_END ) )
  142.                 {
  143.                     printf( "%d}\n", Combinacion[i] );
  144.                 }
  145.                 else
  146.                 {
  147.                     printf( "%d, ", Combinacion[i] );
  148.                 }
  149.             }
  150.         }
  151.         printf( "  | + Score = %lu\n", Score );        
  152.         //Log.Print( "- - - - - - - - - \n\n" );
  153.  
  154.     }
  155.  
  156.     ULONG Score;
  157. private:
  158.     std::vector<UINT> Combinacion;
  159. };
  160. ScoreTrack CurrentScore;
  161. ScoreTrack BestScore;
  162.  
  163. class Mano
  164. {
  165. private:
  166.     typedef std::vector<UINT> Container;    
  167.     Container Cards;
  168.     Container UsedCards;
  169.  
  170. public:
  171.     void AddCard( UINT c )
  172.     {
  173.         Cards.push_back( c );
  174.         assert( Cards.size() <= 7 );
  175.     }    
  176.     void Use( UINT first, UINT count )
  177.     {
  178.         assert( count <= ( Cards.size() - first ) );        
  179.         for( UINT i = first ; i < (first+count); ++i )
  180.         {
  181.             UsedCards.push_back( Cards[i] );
  182.             CurrentScore.PushVal( Cards[i] );
  183.         }
  184.         Cards.erase( Cards.begin() + first, Cards.begin() + first + count );
  185.     }
  186.     void Restore( UINT count )
  187.     {
  188.         assert( count <= UsedCards.size() );
  189.         for( UINT i = 0; i < count; ++i )
  190.         {
  191.             AddCard( UsedCards[UsedCards.size() - i - 1] );
  192.         }
  193.         CurrentScore.Pop();
  194.         UsedCards.erase( UsedCards.end() - count, UsedCards.end() );
  195.         std::sort( Cards.begin(), Cards.end() ); // podria optimizarse
  196.     }
  197.     void RemoveCardByVal( UINT c )
  198.     {
  199.         Container::iterator match = std::find( Cards.begin(), Cards.end(), c );
  200.         assert( match != Cards.end() );
  201.         Cards.erase( match );
  202.     }
  203.     void RemoveCardByIndex( UINT i )
  204.     {
  205.         assert( i < Cards.size() );
  206.         Cards.erase( Cards.begin() + i );
  207.     }
  208.  
  209.     bool HayEscalera( UINT index, UINT n ) const
  210.     {
  211.         assert( n > 2 && n <= Cards.size() );
  212.         return ( Cards[index+n-1] - Cards[index] == (n-1) );
  213.     }
  214.  
  215.     UINT CardsLeft( UINT curIdx ) const
  216.     {
  217.         assert( curIdx <= Cards.size() );
  218.         return Cards.size() - curIdx;
  219.     }
  220.     bool HayNext( UINT curIdx ) const
  221.     {
  222.         return (curIdx+1) < Cards.size();
  223.     }
  224.     UINT Valor( UINT curIdx ) const
  225.     {
  226.         assert( curIdx < Cards.size() );
  227.         return UINT( Cards[curIdx] % 100 );
  228.     }
  229.  
  230.     void Print() const
  231.     {
  232.         PrintFrom( 0, Cards.size() );
  233.     }
  234.     void PrintFrom( UINT first, UINT count ) const
  235.     {
  236.         assert( first >= 0 && count <= ( Cards.size() - first ) );
  237.         printf("{");
  238.         for( UINT i = first ; i < (first+count); ++i )
  239.         {
  240.             if ( i != first )
  241.             {
  242.                 printf(", ");
  243.             }
  244.             printf( "%u", Cards[i] );
  245.         }
  246.         printf("}\n");
  247.     }
  248.  
  249.     void CleanDups()
  250.     {
  251.         for ( UINT i=0; i < Cards.size(); ++i )
  252.         {
  253.             for ( UINT j=i+1; j < Cards.size(); ++j )
  254.             {
  255.                 if ( Cards[i] == Cards[j] )
  256.                 {
  257.                     Cards[j] += 400;
  258.                 }
  259.             }
  260.         }
  261.     }
  262.  
  263.     void RestoreDups()
  264.     {
  265.         for ( UINT i=0; i < Cards.size(); ++i )
  266.         {
  267.             while ( Cards[i] > 500 )
  268.             {
  269.                 Cards[i] -= 400;
  270.             }
  271.         }
  272.     }
  273.  
  274.     void FindBestScore();
  275.  
  276. private:
  277.     void Buscar( UINT curIdx );
  278.     void Match( UINT curIdx );
  279.     ULONG CloseVal() const;
  280.  
  281. };
  282.  
  283.  
  284. ULONG Mano::CloseVal() const
  285. {
  286.     ULONG Val = 0;
  287.     for ( UINT i = 0; i < Cards.size(); ++i )
  288.     {
  289.         Val += Valor( i );
  290.     }
  291.     return Val;
  292. }
  293.  
  294. void Mano::Match( UINT curIdx )
  295. {
  296. #if VERBOSE
  297.     Log.Print("Match: ");
  298.     PrintFrom( curIdx, CardsLeft( curIdx ) );
  299. #endif
  300.  
  301.     if ( CardsLeft( curIdx ) >= 3 )
  302.     {
  303.         UINT CardsLeftTotal = CardsLeft( curIdx );
  304.         UINT Val = Valor( curIdx );
  305.         UINT Reps = 1;
  306.         for ( UINT i = curIdx + 1; i < curIdx + CardsLeftTotal; ++i )
  307.         {
  308.             if ( Valor( i ) == Val )
  309.             {
  310.                 ++Reps;
  311.             }
  312.         }
  313.  
  314.         if ( Reps >= 3 )
  315.         {
  316.  
  317. #if VERBOSE
  318.             Log.Print( "Match x%d = {", Reps );
  319.             UINT NumRep = 1;
  320.             for ( UINT i = curIdx; i < curIdx + CardsLeftTotal; ++i )
  321.             {
  322.                 if ( Valor( i ) == Val )
  323.                 {
  324.                     if ( NumRep == Reps )
  325.                     {
  326.                         printf( "%d}\n", Cards[i] );
  327.                         break;
  328.                     }
  329.                     else
  330.                     {
  331.                         printf( "%d, ", Cards[i] );
  332.                     }
  333.                     ++NumRep;
  334.                 }
  335.             }
  336. #endif
  337.  
  338.             CurrentScore.PushMatch( Reps );
  339.  
  340.             Log.Push();
  341.             for ( INT i = curIdx+CardsLeftTotal-1; i >= (INT)curIdx; --i )
  342.             {
  343.                 if ( Valor( (UINT)i ) == Val )
  344.                 {
  345.                     Use( i, 1 );
  346.                 }
  347.             }
  348.  
  349.             Match( curIdx );
  350.  
  351.             Log.Pop();
  352.             Restore( Reps );
  353.         }
  354.         else if ( HayNext( curIdx ) )
  355.         {
  356.             Match ( curIdx + 1 );
  357.         }
  358.     }
  359.     else
  360.     {
  361.         CurrentScore.Score = CloseVal();
  362.         if ( CurrentScore.Score < BestScore.Score )
  363.         {
  364.             BestScore = CurrentScore;
  365.  
  366.             // Add libres
  367.             if ( UINT FreeCount = CardsLeft(0) )
  368.             {
  369.                 BestScore.PushFree();
  370.                 for( UINT i=0; i<FreeCount; ++i )
  371.                 {
  372.                     BestScore.PushVal( Cards[i] );
  373.                 }
  374.             }
  375.         }
  376.  
  377. #if VERBOSE
  378.         Log.Print( "Libres   = " );
  379.         Print();
  380.         Log.Print( " + New Score = %lu\n",  CloseVal() );
  381.         Log.Print( "- - - - - - - - - \n\n" );
  382. #endif
  383.  
  384.     }
  385.  
  386. }
  387.  
  388. void Mano::Buscar( UINT curIdx )
  389. {
  390.     assert( curIdx < Cards.size() );
  391.  
  392. #if VERBOSE
  393.     Log.Print("Buscar: ");
  394.     PrintFrom( curIdx, CardsLeft( curIdx ) );
  395. #endif
  396.  
  397.     // Buscar escaleras de todos los tamanyos
  398.     for ( UINT n = CardsLeft( curIdx ); n >= 3; --n )
  399.     {
  400.         if ( HayEscalera( curIdx, n ) )
  401.         {
  402. #if VERBOSE
  403.             Log.Print( "Escalera = " );
  404.             PrintFrom( curIdx, n );
  405. #endif
  406.             CurrentScore.PushEscalera();
  407.  
  408.             // Considerar dicha escalera
  409.             Log.Push();
  410.             Use( curIdx, n );
  411.    
  412.             if ( CardsLeft( curIdx ) > 0 )
  413.             {
  414.                 Buscar( curIdx );
  415.             }
  416.             else
  417.             {
  418.                 Match( 0 );
  419.             }
  420.                        
  421.             Restore( n );
  422.             Log.Pop();
  423.         }
  424.     }
  425.  
  426.     // Si quedan cartas que no se han probado
  427.     if ( HayNext( curIdx ) )
  428.     {
  429.         Buscar( curIdx+1 );
  430.     }
  431.     else
  432.     {
  433.         // Si no, es hora de matchear repes
  434.         Match( 0 );
  435.     }
  436. }
  437.  
  438. void Mano::FindBestScore()
  439. {
  440.     std::sort( Cards.begin(), Cards.end() );
  441.     printf( " Ordenada " );
  442.     Print();
  443.  
  444.     CleanDups();
  445.     std::sort( Cards.begin(), Cards.end() );
  446.     //printf( " Hacked   " );
  447.     //Print();
  448.  
  449.     CurrentScore.Reset();
  450.     BestScore.Reset();
  451.     Buscar( 0 );
  452.     BestScore.Print();    
  453.  
  454.     RestoreDups();
  455.     std::sort( Cards.begin(), Cards.end() );
  456.     //printf( " Ordenada " );
  457.     //Print();
  458. }
  459.  
  460.  
  461. int main(int argc, char* argv[])
  462. {
  463.     {
  464.         Mano m;
  465.         m.AddCard( 102 );
  466.         m.AddCard( 103 );
  467.         m.AddCard( 104 );
  468.         m.AddCard( 105 );
  469.         m.AddCard( 205 );
  470.         m.AddCard( 305 );
  471.         m.AddCard( 402 );
  472.         printf( "*******************************************************\n" );
  473.         printf( " MANO     " );
  474.         m.Print();
  475.         //printf( "*******************************************************\n" );
  476.         m.FindBestScore();
  477.         printf("\n");
  478.     }
  479.  
  480.     if ( 1 )
  481.     {
  482.         Mano m;
  483.         m.AddCard( 102 );
  484.         m.AddCard( 202 );
  485.         m.AddCard( 302 );
  486.         m.AddCard( 105 );
  487.         m.AddCard( 205 );
  488.         m.AddCard( 305 );
  489.         m.AddCard( 405 );
  490.         printf( "*******************************************************\n" );
  491.         printf( " MANO     " );        
  492.         m.Print();
  493.         //printf( "*******************************************************\n" );
  494.         m.FindBestScore();
  495.         printf("\n");
  496.     }
  497.  
  498.     if ( 1 )
  499.     {
  500.         Mano m;
  501.         m.AddCard( 102 );
  502.         m.AddCard( 103 );
  503.         m.AddCard( 104 );
  504.         m.AddCard( 105 );
  505.         m.AddCard( 103 );
  506.         m.AddCard( 102 );
  507.         m.AddCard( 202 );
  508.         printf( "*******************************************************\n" );
  509.         printf( " MANO     " );                
  510.         m.Print();
  511.         //printf( "*******************************************************\n" );
  512.         m.FindBestScore();
  513.         printf("\n");
  514.     }
  515.  
  516.     if ( 1 )
  517.     {
  518.         Mano m;
  519.         m.AddCard( 306 );
  520.         m.AddCard( 402 );
  521.         m.AddCard( 305 );
  522.         m.AddCard( 403 );
  523.         m.AddCard( 307 );
  524.         m.AddCard( 404 );
  525.         m.AddCard( 401 );
  526.         printf( "*******************************************************\n" );
  527.         printf( " MANO     " );                
  528.         m.Print();
  529.         //printf( "*******************************************************\n" );
  530.         m.FindBestScore();
  531.         printf("\n");
  532.     }
  533.  
  534.     return 0;
  535. }
Advertisement
Add Comment
Please, Sign In to add comment