quinta-feira, 4 de julho de 2013

Problema de Josephus

CÓDIGO-FONTE:
https://github.com/r-bauer/josephus/archive/master.zip


Na matemática um exemplo famoso de recorrência é atribuído a Flavius Josephus, um famoso historiador do primeiro século, que durante a guerra Judaica, se encontrava entre um bando de 41 judeus rebeldes encurralados pelos romanos em uma caverna.

Sem chance de fuga o grupo decide pela morte ao invés do aprisionamento, os rebeldes formam um circulo e começariam a partir de certo ponto pular duas pessoas e a matar a terceira pessoa numa direção fixa, a eliminação procede em torno do circulo que irá se tornando menor conforme as pessoas mortas são removidas, até não restar alguém vivo.

Conta à lenda que graça ao talento matemático de Josephus o mesmo conseguiu escapar desta tolice quanto ao suicídio ao encontrar o local no circulo inicial em que será o ultimo.

Determinada a tarefa, para buscar uma solução simples, podemos analisar a simulação grafica, com o seguinte circulo inicial:

Através da imagem percebe-se que a representação ideal para este tipo dado seria criar uma fila circular como primeiro passo.


Após o primeiro ciclo encontramos a fila circular com os elementos removidos, com as setas apontando para o elemento seguinte que continua na fila, associando assim ao tratamento de remoção feito por uma lista encadeada.



Uma lista pode armazenar o valor de forma mais intuitiva do que um vetor, que adicionaria um tratamento para mover os valores de índice no circulo inicial a cada exclusão, através da lista encadeada cada elemento mantém como informação o valor da posição original, descartando qualquer operação que não seja a de remover.


A solução reside no valor armazenado no ultimo nó a permanecer na lista encadeada

Ultimo ponto deve ser considerado antes programar a solução, Flavius Josephus atribui em sua biografia que devido à sorte ou a mão de Deus, ele e outro homem resolveram se entregar aos romanos, fato que inclui uma variação no problema, uma vez que historiadores consideram o tal homem como um cúmplice de Josephus, como a morte era administrada pela próxima escolha na fila, a forma de Josephus evitar o ato de assassinar um colega implica que ele colocou alguém de comum acordo para se render na penúltima posição.

Fugindo do tópico, gostaria de deixar indicado o filme cômico A vida de Brian feito pelo Monty Python narrando às engraçadas desventuras de um pobre judeu ante aos romanos, motivo pelo qual a fuga de Josephus sempre me faz associar com está película.

Para o código exemplo a ser apresentado, será utilizadas as rotinas mostradas em lista encadeada genérica parte 1 e parte 2, com a devida adaptação, a primeira é o formato do nó a ser utilizado que irá manter o numero da posição inicial no circulo, sua declaração no arquivo llapp.h resulta em:

// A lista de noh consiste em:
typedef struct tagSNODEDATA
{
    unsigned int uPos;     // posicaoh da pessoa na fila
}SNODEDATA;

                Para resolver o problema, ao criar a lista para simulação os dados que serão inseridos com a função a rotina AddNodeAtHead com valores já ordenados.

      L = CreateLList(  CreateData,
                        DeleteData,
                        DuplicatedNode,
                        NodeDataCmp);

      for (iCount = 1; iCount <= iPerson; ++iCount)
            AddNodeAtHead(L, &iCount);

                Tendo a criação da lista sido concluída, o resultado que se tem na memória é:

Head
41
40
39
38
37
36
35
......
7
6
5
4
3
2
1
Tail

O que descarta as operações de comparação, duplicados e ordenação da lista que devem ser incluídas no arquivo llapp.c, DuplicateNode e NodeDataCmp, não serão chamadas, enquanto que DeleteData não precisa de processamento adicional pelo tipo simples de dados armazenado.

BOOL  DeleteData(void *data)
{
    free( data );
    return TRUE;
}

int   DuplicatedNode(SLINK slkNewNode, SLINK slkListNode)
{
    return 2; // nunca serah chamada
}

int   NodeDataCmp(void *first, void *second)
{
    return ( 0 );       // nunca serah chamada
}
               
Somente a implementação de CreateData será necessária.

void *CreateData(void *data)
{
      SNODEDATA *pNewData;

      // aloca sua estrutura de dados
      pNewData = (SNODEDATA *) malloc(sizeof(SNODEDATA));
      // move os valores para a estrutura de dados
      pNewData->uPos = *((int *) data);
      // retorna o endereco da estrutura
      return (pNewData);
}

                Agora resta percorrer a lista como se está fosse um circulo, para tanto o seguinte trecho do código demonstra como a tarefa será efetivada.

slQueue = L->slkTail;
while (1)
{
      // avancah para o proximo noh
      slQueue = slQueue->prior;
      // terminou de percorrer a lista
      if (slQueue == NULL)
            // transforma a lista em uma fila circular
            slQueue = L->slkTail;
}

                Dentro deste laço será incluído o contador de eliminação iCount que ao atingir o valor iSeq exclui o nó, reiniciando a contagem, processo que irá se repetir até o momento que eliminar todos os nós da lista, controlado pela variável L->uiCount que armazena o total de nós presentes.

Ao tornar a lista em uma fila circular, os ponteiros que indicam inicio (L->slkHead) e fim (L->slkTail) deveriam apontar-se entre si, como tal mudança implicaria em alterar as rotinas genéricas para este tipo de suporte, foi descartada, outra opção também ignorada seria fazer verificações quanto ao elemento ser de inicio ou fim. A solução mais simples foi incluir a variável slDel para indicar o elemento a ser excluído, funcionando como ponteiro para a posição previa.

slQueue = L->slkTail;
iCount = 1;
while (L->uiCount)
{
      slDel = slQueue;
      slQueue = slQueue->prior;
      if (slQueue == NULL)
            slQueue = L->slkTail;

      // conta ateh achar o valor da sequencia
      if (iCount++ == iSeq) {
            // reinicia a contagem
            iCount = 1;
            // elimina o numero da lista
            DeleteNode(L, slDel);
      }
}

                Para armazenar a solução da ultima e penúltima posição nos ponteiros pLast e pSecLast, dentro da condicional que elimina os nós incluímos a outra verificação na variável que controla o total de nós na lista.

if (L->uiCount == 1)
      *pLast = ((pND) slDel->pdata)->uPos;
else if (L->uiCount == 2)
      *pSecLast = ((pND) slDel->pdata)->uPos;

                A rotina completa recebe como entrada a quantidade de pessoas e a sequencia de eliminação através da linha de comando para o programa, e irá utilizar os ponteiros pLast e pSecLast para retornar as duas ultimas posições e imprimir o resultado na tela.

BOOL Josephus(int iPerson, int iSeq, int *pLast, int *pSecLast)
{
      SLIST *L;
      int iCount;
      SLINK slQueue, slDel;

      L = CreateLList(CreateData,
                        DeleteData,
                        DuplicatedNode,
                        NodeDataCmp);

      for (iCount = 1; iCount <= iPerson; ++iCount)
            AddNodeAtHead(L, &iCount);

      slQueue = L->slkTail;
      iCount = 1;
      while (L->uiCount) {
            slDel = slQueue;
            slQueue = slQueue->prior;
            if (slQueue == NULL)
                  slQueue = L->slkTail;

            if (iCount++ == iSeq) {
                  iCount = 1;

                  if (L->uiCount == 1)
                        *pLast = ((pND) slDel->pdata)->uPos;
                  else if (L->uiCount == 2)
                        *pSecLast = ((pND) slDel->pdata)->uPos;

                  DeleteNode(L, slDel);
            }
      }
      return (TRUE);
}

int LLDriver(int argc, char *argv[])
{
      int iPerson, iSeq, iLast, iSecLast;

      iPerson = atoi(argv[1]);
      iSeq = atoi(argv[2]);

      Josephus(iPerson, iSeq, &iLast, &iSecLast);
      printf("penultimo: %d\n", iSecLast);
      printf("ultimo:    %d\n", iLast);

      return (EXIT_SUCCESS);
}

                Ao criar e rodar o projeto, o resultado na tela se apresentara da seguinte forma:

C:\Projects\Josephus\Debug>Josephus 41 3

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

1 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41

2 4 7 8 11 13 16 17 20 22 25 26 29 31 34 35 38 40
2 4 8 11 16 17 22 25 29 31 35 38
2 4 11 16 22 25 31 35
2 4 16 22 31 35
4 16 31 35
16 31
16 31
31
31
penultimo: 16
ultimo:    31

C:\Projects\Josephus\Debug>Josephus 10 2
1 2 3 4 5 6 7 8 9 10
1 3 5 7 9
1 5 9
5
5
penultimo: 9
ultimo:    5


Todos os arquivos deste projeto se encontram armazenados no github,  o problema de Josephus permite outro caminho através da permutação fornecendo uma reposta  mais elegante comparada a simples simulação da contagem envolvendo lista encadeada, assunto que voltara a pauta com a postagem de recursividade.

quarta-feira, 26 de junho de 2013

Fila de Prioridade

CÓDIGO-FONTE: https://github.com/r-bauer/prioQueue/archive/master.zip

Como explicado na postagem anterior(Fila Circular), um problema singular ocorre quando se cria um tipo de dado abstrato como a fila usando vetores, aonde inserir e remover elementos continuamente desloca os dados por  toda a memória, como solução utiliza-se um buffer circular, em um segundo caso quando criamos uma fila com lista encadeada, a mesma sofre de uma deficiência ligeiramente diferente em seu formato, continuar criando e apagando nós da lista, acabara por fragmentar a memória com as sucessivas operações de alocar e liberar.

No caso da fila com lista encadeada temos duas soluções para o problema:
1.       Usar funções próprias para alocar e devolver a memória, esta função iria alocar uma sequencia de nós que seriam usados e devolvidos.
2.       Criar uma lista encadeada de nós livres, conforme os itens foram inseridos, os nós são movidos da lista livre para a fileira, ao remover, os nós retornam para a lista livre.

Será utilizada a abordagem numero 2, as rotinas de lista encadeada a serem utilizadas, foram introduzidas anteriormente na postagem lista encadeada genérica parte 1 e parte 2. Para os arquivos de aplicação qapp.c e qapp.h, teremos a adaptação da lista ligada para uma fila, semelhante à forma com que se trabalhou com os arquivos llapp.c e llapp.h.

Uma lista ordenada será usada para representar a fila de prioridade, utilizando uma lista ordenada ascendente, implica numa alteração do processo de inserção, aonde abandonamos o FIFO (First In, First Out) para colocar o elemento na posição indicada para sua prioridade, a rotina insere fica responsável em manter a ordem enquanto a rotina remove mantém sua simplicidade ao remover o primeiro da fila, em termos de desempenho o processo de inserção requer uma media de aproximadamente n/2 nós para inserção e apenas um nó para eliminação.

typedef struct tagSNODEDATA
{
      char *pText;                 // ponteiro para um texto
      unsigned int uiPriority;     // o nivel de prioridade
}SNODEDATA;

A vantagem de uma lista sobre vetor para programar a fila de prioridade reside no fato de que não é necessário nenhum deslocamento de dados, um item pode ser inserido numa lista sem deslocar os demais, enquanto que a mesma operação num vetor fica impossível se não houver espaços vazios.

A estratégia para o programa se inicia com a criação de duas estruturas de lista encadeada slQueue e slFreeList no arquivo qdriver.c.

    SLIST *slQueue, *slFreeList;

    // configura a estrutura de lista ligada para filas
    slQueue = CreateLList(  CreateData1,
                            DeleteData1,
                            DuplicatedNode,
                            NodeDataCmp1 );

    slFreeList = CreateLList(   CreateData2,
                                DeleteData2,
                                DuplicatedNode,
                                NodeDataCmp2 );

Antes de detalhar as rotinas especificas de cada lista, é importante ressaltar que toda a memória usada será criada pela lista livre e compartilhada pelas duas listas, o que resulta na criação de todos os nós pela lista livre no seguinte trecho.

    for (iCount = 0; iCount < QMAX; ++iCount)
    {
        AddNodeAtHead(slFreeList, cRecord);
    }

A consequência desta lógica acaba com as rotinas CreateData1 e DeleteData1 jamais sendo executadas no código, com suas declarações sendo vazias no arquivo qapp.c.

void *CreateData1(void *data)
{
    return (NULL);
}

BOOL  DeleteData1(void *data)
{
    return TRUE;
}

O mesmo acontece para tratamento de elementos duplicados , apesar de incluir a rotina DuplicateNode, a mesma não é chamada por nenhuma das duas listas, mantendo sua declaração apenas com fim de compatibilidade, ambas as listas compartilham a mesma rotina.

int   DuplicatedNode(SLINK slkNewNode, SLINK slkListNode)
{
    return 2;
}

A única operação especifica para a lista slQueue será a comparação dos nós através do valor de prioridade para posicionar na fila.

int   NodeDataCmp1(void *first, void *second)
{
    return (((pND)first)->uiPriority - ((pND)second)->uiPriority);
}

Como a lista slFreeList fica responsável por gerar e apagar o nós, CreateData2 e DeleteData2 serão as únicas rotinas com a tarefa de alocar e liberar.

void *CreateData2(void *data)
{
    SNODEDATA *pNewData;

    // aloca sua estrutura de dados
    pNewData = (SNODEDATA *) malloc(sizeof(SNODEDATA));

    // move os valores para a estrutura de dados
    pNewData->uiPriority = 0;
    pNewData->pText = (char *) malloc(TEXT_SIZE + 1);
    *pNewData->pText = '\0';

    return (pNewData);     // retorna o endereco da estrutura
}

BOOL  DeleteData2(void *data)
{
    // SNODEDATA consiste em: um ponteiro e um inteiro.
    // Sendo nescessario liberar a string manualmente
    free( ((pND) data)->pText);
    // e somente agora libera SNODEDATA
    free(  data );
    return TRUE;
}


Com a adaptação das rotinas especificas de lista encadeada para uso com a fila de prioridade, monta-se o controlador de fila, com as rotinas para inserir e remover elementos da fila.

Função
InsertQueue
Propósito
Armazenar um dado baseado em sua prioridade
Parâmetros
SLIST *slQueue - lista ligada usada para fila de prioridade
SLIST *slFree - lista com as vagas livres a serem inseridas
void *pNewEntry - a nova entrada a ser guardada na fila
Retorno
TRUE - dado armazenado
FALSE - não foi possível armazenar o dado
Descrição
Enfileira os dados passados no inicio da lista livre, e depois adiciona o nó na lista baseada na prioridade.

BOOL InsertQueue(SLIST *slQueue, SLIST *slFree, void *pNewEntry)
{
    SLINK slkCurr, slkNewNode;

    // existe algum noh livre na lista
    if (slFree->uiCount == 0)
        return (FALSE);

    // usa como novo noh, o inicio da lista livre
    slkNewNode = slFree->slkHead;

    DataCopy(slkNewNode->pdata, pNewEntry);

    // adiciona os dados numa lista vazia
    if (slQueue->uiCount == 0)
    {
        // encontrou uma vaga, corrige a lista livre
        // atualiza a o inicio da lista para o seguinte
        slFree->slkHead = slFree->slkHead->next;

        // ponteiros do noh = NULO por ser o primeira insercaoh
        slkNewNode->prior = NULL;
        slkNewNode->next = NULL;

        // indica que o novo noh faz parte da lista de prioridade
        slQueue->slkTail = slkNewNode;
        slQueue->slkHead = slkNewNode;

        slQueue->uiCount = 1;// inicia o contador da lista
        --slFree->uiCount;   // retira uma vaga da lista livre

        return (TRUE);
    }
    // jah existem dados na lista
    else
    {
        //´percorre a lista para encontrar a posicaoh de insercaoh
        for (slkCurr = slQueue->slkHead; ; slkCurr = slkCurr->next)
        {
            if ((slkCurr == NULL) || // se for fim da fila
           // ou dentro dele
           (slQueue->fNodeDataCmp(pNewEntry, slkCurr->pdata) < 0))
            {
                // encontrou uma vaga, corrige a lista livre
                // atualiza a o inicio da lista para o seguinte
                slFree->slkHead = slFree->slkHead->next;

                // eh o fim da lista ?
                if (slkCurr == NULL) {
                    // novo noh aponta para o fim da fila
                    slkNewNode->prior = slQueue->slkTail;  
                    // naoh tem para quem apontar
                    slkNewNode->next = NULL;
                    // o seguinte do fim aponta para o novo noh
                    slQueue->slkTail->next = slkNewNode;   
                    // indica o novo fim da lista
                    slQueue->slkTail = slkNewNode;
                }
                else {
                    // estah adicionando no inicio da lista ?
                    if (slkCurr->prior == NULL)
                        // atualiza o inicio da lista
                        slQueue->slkHead = slkNewNode;     

                    // atualiza os ponteiro do novo noh
                    slkNewNode->prior = slkCurr->prior;      
                    // colocando ele entre o atual e anterior
                    slkNewNode->next = slkCurr;            

                    // naoh estah adicionando no inicio
                    if (slkCurr->prior != NULL)
                        // anterior p/ referenciar o novo noh
                        slkCurr->prior->next = slkNewNode;  

                    // ajusta o atual p/ referenciar o novo noh
                    slkCurr->prior = slkNewNode;
                }

                // atualiza a contagem das lista
                // adiciona um noh na lista de prioridade
                ++slQueue->uiCount;
                // subtrai um noh da lista de livres
                --slFree->uiCount;

                return (TRUE);
            }
        }
    }
}


Função
RemoveQueue
Propósito
Retira o dado de uma fila
Parâmetros
SLIST *slQueue - lista ligada usada para fila de prioridade
SLIST *slFree - lista com as vagas livres a serem inseridas
 void *pOurData - o dado retirado da fila
Retorno
TRUE - recuperou a informação da fila
FALSE - Fila vazia ou erro ao copiar dado para buffer
Descrição
Para remover, usa um ponteiro para o nó no inicio da fila. Move esse nó inicial retirado da fila e o insere na lista de nó livres. Obs.: Se não os dados não forem usados antes que se execute uma nova operação p/ enfileirar (insertQueue), os dados serão perdidos, portanto copie se for necessário.

BOOL RemoveQueue(SLIST *slQueue, SLIST *slFree, void *pOurData)
{
    SLINK slkRemove;

    // existe algum dado p/ desinfilerar ?
    if (slQueue->uiCount == 0)
        return (FALSE);

    // faz a copia dos dados desenfilerados
    DataCopy(pOurData, slQueue->slkHead->pdata);

    // salva a posicaoh do dado a ser retirado da fila
    slkRemove = slQueue->slkHead;
    // remove o noh da fila de prioridade
    // atualizando o inicio p/ o seguinte da lista
    slQueue->slkHead = slQueue->slkHead->next; 
   
    // se diferente de nulo, tem elemento armazenados na fila
    if (slQueue->slkHead != NULL)
        // eliminando a referencia de um previo
        slQueue->slkHead->prior = NULL;         
    // se o inicio for nulo, fila foi esvaziada, atualiza o fim
    else
        // naoh existe dados armazenados
        slQueue->slkTail = NULL;               

    --slQueue->uiCount; // ajusta a contagem de itens na fila
   

    // e adiciona no inicio da lista de livres
    slkRemove->prior = NULL;          // aponta o anterior p/ NULO
    // e o seguinte para o inicio da lista de livres
    slkRemove->next = slFree->slkHead;
    // e atualiza o inicio da lista de nohs livres
    slFree->slkHead = slkRemove;     
    ++slFree->uiCount;  // avisa que tem + 1 noh livre

    return (TRUE);
}


Para testarmos o resultado, a função QDriver servirá de exemplo de tratamento para fila de prioridade, irá abrir para leitura um arquivo de dados consistindo em linhas de texto no formato X9MESSAGE, aonde:

X
I – para inserir na fila
R – remover
L – listar a fila
9
Prioridade do item da fila
MESSAGE
Texto a ser inserido
Obs.: A ações D e P não tem prioridade ou texto.

O arquivo texto com dados deverá ter o seguinte padrão:

I8Lacuna Coil
I4Anthrax
R
L
R
I1Various
I9White Zombie
I2John Williams
I4Killswitch Engage
L
I4Ayreon

O código simplificado de teste para abrir o arquivo e executar as ações que encontrar em cada linha segue abaixo.

fin = fopen(argv[1], "rt");

pTemp = CreateData2(NULL);

while (fgets(cRecord, sizeof(cRecord) - 1, fin) != NULL)
{
      if (*cRecord == 'I')
      {
            ((pND) pTemp)->uiPriority = *(cRecord + 1) - '0';
            ((pND) pTemp)->pText = cRecord + 2;

            InsertQueue(slQueue, slFreeList, pTemp);
      }
      else if (*cRecord == 'R')
      {
            RemoveQueue(slQueue, slFreeList, pTemp);
      }
      else if (*cRecord == 'L')
      {
            SLINK slkCurr;
            printf("\n- Fila -\n");
            for ( slkCurr = slQueue->slkHead;
                  slkCurr != NULL;
                  slkCurr = slkCurr->next)
            {
                  printf("%d %s\n",
                        ((pND) slkCurr->pdata)->uiPriority,
                        ((pND) slkCurr->pdata)->pText);
            }
            printf("\n");
      }
}

fclose(fin);

Os arquivos deste projeto se encontram no github: https://github.com/r-bauer/prioQueue, o arquivo prio.txt deve ser criado para ser usado no teste como indicado acima, ao rodar o programa terá como resultado: 


C:\Algorit\Projects\pqueue\Debug>pqueue PRIO.TXT
        Enfilerou (1 Bryan Adams)
        Enfilerou (4 KC and the Sunshine Band)
        Desenfilerou (1 Bryan Adams)

----------- Fila ateh o momento -----------
4 KC and the Sunshine Band

        Enfilerou (2 Meat Loaf)
        Enfilerou (1 R.E.M)
        Enfilerou (9 Sugar Ray)
        Desenfilerou (1 R.E.M)
        Desenfilerou (2 Meat Loaf)

----------- Fila ateh o momento -----------
4 KC and the Sunshine Band
9 Sugar Ray

        Enfilerou (7 The Mission)
        Enfilerou (4 Temple of the Dog)
        Enfilerou (3 Pantera)
        Enfilerou (1 Ministry)
        Enfilerou (1 Kelly Clarkson)
        Desenfilerou (1 Ministry)
        Desenfilerou (1 Kelly Clarkson)

----------- Fila ateh o momento -----------
3 Pantera
4 KC and the Sunshine Band
4 Temple of the Dog
7 The Mission
9 Sugar Ray