Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Test.cpp : Defines the entry point for the console application.
- //
- #include "stdafx.h"
- #include <cmath>
- #include <vector>
- #include <list>
- #include <cassert>
- #include <cstdarg>
- #include <algorithm>
- #define VERBOSE 0
- typedef int INT;
- typedef unsigned int UINT;
- typedef unsigned long ULONG;
- // todo quitar push invertido (no es necesario)
- struct _Log
- {
- void Print( const char* format, ... )
- {
- #if VERBOSE
- for( INT i=0; i<NUMTABS; ++i ) { printf(" "); }
- #endif
- va_list args;
- va_start( args, format );
- vprintf( format, args );
- va_end( args );
- }
- void Push()
- {
- ++NUMTABS;
- }
- void Pop() {
- --NUMTABS;
- assert( NUMTABS >= 0 );
- }
- private:
- INT NUMTABS;
- } Log;
- struct ScoreTrack
- {
- ScoreTrack() { Reset(); }
- enum
- {
- TOKEN_START = 0
- , ESCALERA
- , MATCH3 = 3
- , MATCH4
- , MATCH5
- , MATCH6
- , MATCH7
- , FREE
- , TOKEN_END
- };
- void PushEscalera()
- {
- Combinacion.push_back( ESCALERA );
- }
- void PushMatch( UINT Reps )
- {
- assert( Reps >= MATCH3 && Reps <= MATCH7 );
- Combinacion.push_back( Reps );
- }
- void PushFree()
- {
- Combinacion.push_back( FREE );
- }
- void PushVal( UINT v )
- {
- while ( v > 500 ) { v -= 400; }
- Combinacion.push_back( v );
- }
- bool IsBackToken() const
- {
- UINT Val = Combinacion.back();
- return ( Val > TOKEN_START && Val < TOKEN_END );
- }
- void Pop()
- {
- assert( Combinacion.size() > 0 && !IsBackToken() );
- do
- {
- Combinacion.pop_back();
- } while( !IsBackToken() );
- Combinacion.pop_back();
- }
- ULONG GetScore() const
- {
- return Score;
- }
- bool IsEmpty()
- {
- return Combinacion.empty();
- }
- void Reset()
- {
- Score = 666;
- Combinacion.clear();
- }
- void Print()
- {
- Log.Print( " Mejor Jugada:\n" );
- for( UINT i=0; i<Combinacion.size(); ++i )
- {
- if ( Combinacion[i] == ESCALERA )
- {
- printf( " | - Escalera = {" );
- }
- else if ( Combinacion[i] >= MATCH3 && Combinacion[i] <= MATCH7 )
- {
- printf( " | - Match x%d = {", Combinacion[i] );
- // Porque hago push invertido
- for ( UINT j = i + Combinacion[i]; j > i ; --j )
- {
- if ( j == i+1 )
- {
- printf( "%d}\n", Combinacion[j] );
- }
- else
- {
- printf( "%d, ", Combinacion[j] );
- }
- }
- i = i + Combinacion[i];
- }
- else if ( Combinacion[i] == FREE )
- {
- printf( " | - Libres = {" );
- }
- else
- {
- UINT Next = i+1;
- if ( Next >= Combinacion.size() || ( Combinacion[Next] < TOKEN_END ) )
- {
- printf( "%d}\n", Combinacion[i] );
- }
- else
- {
- printf( "%d, ", Combinacion[i] );
- }
- }
- }
- printf( " | + Score = %lu\n", Score );
- //Log.Print( "- - - - - - - - - \n\n" );
- }
- ULONG Score;
- private:
- std::vector<UINT> Combinacion;
- };
- ScoreTrack CurrentScore;
- ScoreTrack BestScore;
- class Mano
- {
- private:
- typedef std::vector<UINT> Container;
- Container Cards;
- Container UsedCards;
- public:
- void AddCard( UINT c )
- {
- Cards.push_back( c );
- assert( Cards.size() <= 7 );
- }
- void Use( UINT first, UINT count )
- {
- assert( count <= ( Cards.size() - first ) );
- for( UINT i = first ; i < (first+count); ++i )
- {
- UsedCards.push_back( Cards[i] );
- CurrentScore.PushVal( Cards[i] );
- }
- Cards.erase( Cards.begin() + first, Cards.begin() + first + count );
- }
- void Restore( UINT count )
- {
- assert( count <= UsedCards.size() );
- for( UINT i = 0; i < count; ++i )
- {
- AddCard( UsedCards[UsedCards.size() - i - 1] );
- }
- CurrentScore.Pop();
- UsedCards.erase( UsedCards.end() - count, UsedCards.end() );
- std::sort( Cards.begin(), Cards.end() ); // podria optimizarse
- }
- void RemoveCardByVal( UINT c )
- {
- Container::iterator match = std::find( Cards.begin(), Cards.end(), c );
- assert( match != Cards.end() );
- Cards.erase( match );
- }
- void RemoveCardByIndex( UINT i )
- {
- assert( i < Cards.size() );
- Cards.erase( Cards.begin() + i );
- }
- bool HayEscalera( UINT index, UINT n ) const
- {
- assert( n > 2 && n <= Cards.size() );
- return ( Cards[index+n-1] - Cards[index] == (n-1) );
- }
- UINT CardsLeft( UINT curIdx ) const
- {
- assert( curIdx <= Cards.size() );
- return Cards.size() - curIdx;
- }
- bool HayNext( UINT curIdx ) const
- {
- return (curIdx+1) < Cards.size();
- }
- UINT Valor( UINT curIdx ) const
- {
- assert( curIdx < Cards.size() );
- return UINT( Cards[curIdx] % 100 );
- }
- void Print() const
- {
- PrintFrom( 0, Cards.size() );
- }
- void PrintFrom( UINT first, UINT count ) const
- {
- assert( first >= 0 && count <= ( Cards.size() - first ) );
- printf("{");
- for( UINT i = first ; i < (first+count); ++i )
- {
- if ( i != first )
- {
- printf(", ");
- }
- printf( "%u", Cards[i] );
- }
- printf("}\n");
- }
- void CleanDups()
- {
- for ( UINT i=0; i < Cards.size(); ++i )
- {
- for ( UINT j=i+1; j < Cards.size(); ++j )
- {
- if ( Cards[i] == Cards[j] )
- {
- Cards[j] += 400;
- }
- }
- }
- }
- void RestoreDups()
- {
- for ( UINT i=0; i < Cards.size(); ++i )
- {
- while ( Cards[i] > 500 )
- {
- Cards[i] -= 400;
- }
- }
- }
- void FindBestScore();
- private:
- void Buscar( UINT curIdx );
- void Match( UINT curIdx );
- ULONG CloseVal() const;
- };
- ULONG Mano::CloseVal() const
- {
- ULONG Val = 0;
- for ( UINT i = 0; i < Cards.size(); ++i )
- {
- Val += Valor( i );
- }
- return Val;
- }
- void Mano::Match( UINT curIdx )
- {
- #if VERBOSE
- Log.Print("Match: ");
- PrintFrom( curIdx, CardsLeft( curIdx ) );
- #endif
- if ( CardsLeft( curIdx ) >= 3 )
- {
- UINT CardsLeftTotal = CardsLeft( curIdx );
- UINT Val = Valor( curIdx );
- UINT Reps = 1;
- for ( UINT i = curIdx + 1; i < curIdx + CardsLeftTotal; ++i )
- {
- if ( Valor( i ) == Val )
- {
- ++Reps;
- }
- }
- if ( Reps >= 3 )
- {
- #if VERBOSE
- Log.Print( "Match x%d = {", Reps );
- UINT NumRep = 1;
- for ( UINT i = curIdx; i < curIdx + CardsLeftTotal; ++i )
- {
- if ( Valor( i ) == Val )
- {
- if ( NumRep == Reps )
- {
- printf( "%d}\n", Cards[i] );
- break;
- }
- else
- {
- printf( "%d, ", Cards[i] );
- }
- ++NumRep;
- }
- }
- #endif
- CurrentScore.PushMatch( Reps );
- Log.Push();
- for ( INT i = curIdx+CardsLeftTotal-1; i >= (INT)curIdx; --i )
- {
- if ( Valor( (UINT)i ) == Val )
- {
- Use( i, 1 );
- }
- }
- Match( curIdx );
- Log.Pop();
- Restore( Reps );
- }
- else if ( HayNext( curIdx ) )
- {
- Match ( curIdx + 1 );
- }
- }
- else
- {
- CurrentScore.Score = CloseVal();
- if ( CurrentScore.Score < BestScore.Score )
- {
- BestScore = CurrentScore;
- // Add libres
- if ( UINT FreeCount = CardsLeft(0) )
- {
- BestScore.PushFree();
- for( UINT i=0; i<FreeCount; ++i )
- {
- BestScore.PushVal( Cards[i] );
- }
- }
- }
- #if VERBOSE
- Log.Print( "Libres = " );
- Print();
- Log.Print( " + New Score = %lu\n", CloseVal() );
- Log.Print( "- - - - - - - - - \n\n" );
- #endif
- }
- }
- void Mano::Buscar( UINT curIdx )
- {
- assert( curIdx < Cards.size() );
- #if VERBOSE
- Log.Print("Buscar: ");
- PrintFrom( curIdx, CardsLeft( curIdx ) );
- #endif
- // Buscar escaleras de todos los tamanyos
- for ( UINT n = CardsLeft( curIdx ); n >= 3; --n )
- {
- if ( HayEscalera( curIdx, n ) )
- {
- #if VERBOSE
- Log.Print( "Escalera = " );
- PrintFrom( curIdx, n );
- #endif
- CurrentScore.PushEscalera();
- // Considerar dicha escalera
- Log.Push();
- Use( curIdx, n );
- if ( CardsLeft( curIdx ) > 0 )
- {
- Buscar( curIdx );
- }
- else
- {
- Match( 0 );
- }
- Restore( n );
- Log.Pop();
- }
- }
- // Si quedan cartas que no se han probado
- if ( HayNext( curIdx ) )
- {
- Buscar( curIdx+1 );
- }
- else
- {
- // Si no, es hora de matchear repes
- Match( 0 );
- }
- }
- void Mano::FindBestScore()
- {
- std::sort( Cards.begin(), Cards.end() );
- printf( " Ordenada " );
- Print();
- CleanDups();
- std::sort( Cards.begin(), Cards.end() );
- //printf( " Hacked " );
- //Print();
- CurrentScore.Reset();
- BestScore.Reset();
- Buscar( 0 );
- BestScore.Print();
- RestoreDups();
- std::sort( Cards.begin(), Cards.end() );
- //printf( " Ordenada " );
- //Print();
- }
- int main(int argc, char* argv[])
- {
- {
- Mano m;
- m.AddCard( 102 );
- m.AddCard( 103 );
- m.AddCard( 104 );
- m.AddCard( 105 );
- m.AddCard( 205 );
- m.AddCard( 305 );
- m.AddCard( 402 );
- printf( "*******************************************************\n" );
- printf( " MANO " );
- m.Print();
- //printf( "*******************************************************\n" );
- m.FindBestScore();
- printf("\n");
- }
- if ( 1 )
- {
- Mano m;
- m.AddCard( 102 );
- m.AddCard( 202 );
- m.AddCard( 302 );
- m.AddCard( 105 );
- m.AddCard( 205 );
- m.AddCard( 305 );
- m.AddCard( 405 );
- printf( "*******************************************************\n" );
- printf( " MANO " );
- m.Print();
- //printf( "*******************************************************\n" );
- m.FindBestScore();
- printf("\n");
- }
- if ( 1 )
- {
- Mano m;
- m.AddCard( 102 );
- m.AddCard( 103 );
- m.AddCard( 104 );
- m.AddCard( 105 );
- m.AddCard( 103 );
- m.AddCard( 102 );
- m.AddCard( 202 );
- printf( "*******************************************************\n" );
- printf( " MANO " );
- m.Print();
- //printf( "*******************************************************\n" );
- m.FindBestScore();
- printf("\n");
- }
- if ( 1 )
- {
- Mano m;
- m.AddCard( 306 );
- m.AddCard( 402 );
- m.AddCard( 305 );
- m.AddCard( 403 );
- m.AddCard( 307 );
- m.AddCard( 404 );
- m.AddCard( 401 );
- printf( "*******************************************************\n" );
- printf( " MANO " );
- m.Print();
- //printf( "*******************************************************\n" );
- m.FindBestScore();
- printf("\n");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment