PROBLEMA: jogo 2048
Você conhece o jogo 2048? Se não, irei apresentá-lo a vocês. Abaixo segue uma imagem.
-Nesse jogo, as teclas direcionais são usadas para realizar jogadas (cima, baixo, esquerda e direita). A
-cada vez que uma tecla é pressionada, os blocos numerados tentam deslizar pela matriz caso haja
espaço. No exemplo da imagem abaixo, se a tecla para esquerda for pressionada, 5 blocos irão se
mover (8, 2, 16, 2, 32).
-Além de tentar deslizar, blocos adjacentes com o mesmo número se juntam em um único bloco com um
número dobrado caso tentem deslizar na direção certa. No exemplo da imagem abaixo, se a tecla para
baixo for pressionada, dois blocos 2 irão se transformar em um bloco 4 e dois blocos 32 irão se
transformar em um bloco 64.
Durante o jogo, além de fazer as jogadas, surgem aleatoriamente blocos na matriz com números iguais
a potências de 2. O objetivo é fazer os blocos se juntarem para que um bloco com número 2048 seja
formado. Quando isso acontece, o jogador vence o jogo e não é possível fazer mais jogadas.

Porém, também pode acontecer do jogador não ter mais jogadas possíveis antes de formar o número
2048. No exemplo da imagem abaixo, apertar a tecla para a direita não é uma jogada válida, pois
nenhum bloco pode se mover ou se juntar a outro bloco.
Sua tarefa nesse problema é dizer quais são as jogadas válidas para uma determinada situação
do jogo.
Entrada
Você deve fornecer 6 casos de teste de estado de jogo. Ou seja, 6 matrizes 4x4 aleatórias com valores
zero (para espaço vazio) ou múltiplos de 2. Isto é, os números da matriz são iguais a 0 para indicar que
não há bloco na posição, ou são iguais a potências de 2 entre 2 e 2048 inclusive.
Saída
Para cada teste, a saída consiste de uma linha contendo todas as jogadas possíveis para a entrada. As
jogadas são indicadas por BAIXO, ESQUERDA, DIREITA E CIMA. Caso não haja nenhuma jogada
possível, imprima NONE.
Imprima também a quantidade de vezes que não foi possível fazer uma jogada possível (NONE).
Exemplo
6 MATRIZES SORTEADAS RESULTADO
2 128 8 16
16 8 4 32
8 16 32 64
16 2 64 128
0 0 0 8
0 0 2 16
0 0 2 32
2 8 16 32
NONE
BAIXO ESQUERDA CIMA
DIREITA CIMA
NONE
BAIXO ESQUERDA
NONE
Não foi possível fazer jogadas 3 vezes

0 0 0 0
0 0 0 0
0 0 0 0
2 0 0 0
2 4 8 16
4 8 16 32
8 16 32 64
16 32 64 128
0 0 0 2
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Atividade de avaliativa 1
O objetivo desse exercício é que vocês comparem algoritmos em relação ao tempo de execução.
Lembrem-se que, se é desejado aferir o tempo de execução do processo, é necessário levar em
consideração que outros processos estão concorrendo por esse tempo de processamento na
máquina.
Escolha a mesma linguagem de programação para os exercícios 1 e 2 abaixo.
1) Faça um algoritmo A (sequencial) que resolva o problema acima.
2) Faça uma nova versão do algoritmo que utilize threads (algoritmo B) para o mesmo problema .
3) Faça um programa testador de tempo de execução. Ele terá por intuito inicializar os processos A e B,
aferir seus respectivos tempos médios de execução e calcular os speedups:
a) aferir o tempo médio do algoritmo A para 50 execuções;
b) aferir o tempo médio do algoritmo B para 50 execuções em cada um dos cenários abaixo:
i) 3 thread;
ii) 6 threads;
b) calcular os speedups do algoritmo A em relação a cada uma das versões do algoritmo B.
4) REFLITA e ANOTE:
a) Por que obteve esses resultados?
b) A relação do tempo do speedup coletado com os itens abaixo:
i) Qual o hardware usado? Isso influencia?
Instituto Federal de Educação, Ciência e Tecnologia do Sudeste de Minas Gerais
Campus Rio Pomba
- Sistemas Paralelos e Distribuídos -
professora: Bianca Portes
ii) Qual o sistema operacional usado? Isso influencia?
iii) Qual a linguagem e recursos da linguagem usados? Haveria diferença se as linguagens
fossem diferentes?
iv) Por que determinada abordagem obteve melhor desempenho em relação a outra
(paralelo x sequencial)?
v) Onde foi possível aumentar a vazão na sua proposta?
.