MC346 - Projeto de Programação - Campeonato

  Revisada: 2015-11-02 (Lisp)
  Revisada: 2015-10-03 (input normal .txt)
  Revisada: 2015-09-14 (como fazer um módulo para entrega)
  Revisada: 2015-08-27 (lista de problemas)
  Revisada: 2015-08-26 (input "mastigado")
  Revisada: 2015-08-13
  Criada: 2015-07-23

Desafio

Lisp

Seu programa receberá um problema na forma de duas expressões Lisp, a primeira contendo domínios e a segunda contendo restrições, por exemplo:

((domain(cor) azul branca preta)
 (domain(nacionalidade) alemao brasileiro espanhol)
 (domain(animal) borboleta cachorro cavalo)
 (domain(esporte) futebol tenis sinuca))

((or (= brasileiro 1) (= brasileiro 3))
 (= cachorro futebol)
 (= (+ tenis 2) preta)
 (= cavalo (- borboleta 1))
 (= cachorro (+ branca 1))
 (= espanhol 3))

O problema deverá ser lido de uma arquivo com extensão .lisp. Seu programa deverá ser escrito dentro de um pacote Lisp e deverá implementar uma função solver que recebe um nome de arquivo contendo as expressões acima descritas e retorna a solução do problema na forma de uma lista como segue:

((alemao 1) (espanhol 3) (italiano 2) (azul 1) (vermelha 2) (preta 3))

O programa abaixo exemplifica o formato. Este programa apenas dá valores aleatórios às variáveis. Substitua neste código o símbolo your_package_name_here por um nome mais significativo, escolhido por você, e obviamente, o código da função solver pelo código que você desenvolver para resolver o problema. Pode acrescentar funções auxiliares ao arquivo, que pode ter qualquer nome.

(make-package 'your_package_name_here)
(in-package your_package_name_here)
(common-lisp:use-package 'common-lisp)
(export 'solver)

(defun solver (path)
  (with-open-file (f path)
		  (let* ((domains (read f))
			 (constraints (read f))
			 )
		    (setf *random-state* (make-random-state t))
		    (mapcar #'(lambda(x) (list x (1+ (random (- (length (car domains)) 2)))))
			    (apply #'append (mapcar #'cddr domains))
			    )
		    )
		  )
  )

Submeta seu programa (jogador) através do nosso sistema de submissão, dando ao jogador o mesmo nome que deu ao pacote.

Prolog

A partir de 2015-10-02, apenas serão aceitos programas que leiam os arquivos .txt dos problemas diretamente. Todos os pontos dos jogadores submnetidos anteriormente foram zerados, para que os pontos das novas versões não sejam contaminados pelas pontuações anteriores. Veja aqui a situação imediatamente antes da mudança.

Seu desafio será escrever um programa que resolve certos problemas de lógica como o descrito a seguir.

1. Há 5 casas de diferentes cores;
2. Em cada casa mora uma pessoa de uma nacionalidade diferente;
3. Os 5 moradores bebem diferentes bebidas, fumam diferentes tipos de cigarros e têm um diferente animal de estimação.

Tente descobrir quem mora em qual casa e as demais características a partir das seguintes dicas:

• O Norueguês vive na primeira casa.
• O Inglês vive na casa Vermelha.
• O Sueco tem Cachorros como animais de estimação.
• O Dinamarquês bebe Chá.
• A casa Verde fica do lado esquerdo da casa Branca.
• O homem que vive na casa Verde bebe Café.
• O homem que fuma Pall Mall cria Pássaros.
• O homem que vive na casa Amarela fuma Dunhill.
• O homem que vive na casa do meio bebe Leite.
• O homem que fuma Blends vive ao lado do que tem Gatos.
• O homem que cria Cavalos vive ao lado do que fuma Dunhill.
• O homem que fuma BlueMaster bebe Cerveja.
• O Alemão fuma Prince.
• O Norueguês vive ao lado da casa Azul.
• O homem que fuma Blends é vizinho do que bebe Água.

Descrição formal

Seu programa receberá um problema na forma de um arquivo de texto contendo todos os dados e dicas do problem. O arquivo texto terá duas seções. Na primeira seção, os domínios das características serão dados. No exemplo acima, os domínios seriam os seguintes:

  cor: vermelha, verde, branca, amarela, azul
  nacionalidade: noruegues, ingles, sueco, dinamarques, alemao
  bebida: cha, cafe, leite, cerveja, agua
  cigarro: pallmall, dunhill, blends, bluemaster, prince
  animal: cachorro, gato, passaro, cavalo, peixe

Uma linha em branco separa a primeira seção da segunda

A segunda seção conterá as dicas, codificadas da seguinte forma. Cada estado de cada característica representa um número inteiro de 1 a N (no exemplo, N=5) que corresponde à posição daquela característica na solução. Assim, por exemplo, a dica de que "O norueguês vive na primeira casa" será codificada como segue:

  noruegues = 1

Outros exemplos de tradução de dicas:

O inglês vive na casa vermelha

  ingles = vermelha

A casa verde fica do lado esquerdo da casa branca

  verde + 1 = branca

O homem que cria cavalos vive ao lado do que fuma Dunhill

  |cavalo - dunhill| = 1

E assim por diante. Cada linha da seção de dicas deverá ser lida e processada pelo seu programa, que deverá obter uma soluçao que satisfaça todas as dicas. Sua solução deverá ser impressa num arquivo texto com linhas da forma:

  estado = numero

e deverá ter tantas linhas quantos estados, juntando todas as caraterísticas. A ordem em que os estados aparecem não é importante. Lembre-se que estados da mesma característica não podem ter mesmo valor.

  :- module(nome, [solver/2]).

  solver(+Filename, -S)

  solver(+D, +C, -S)

  cor: azul, vermelha, preta
  nacionalidade: alemao, espanhol, italiano
  
  espanhol = vermelha + 1
  alemao = azul
  italiano = 2

  D = [[domain(cor), azul, vermelha, preta],
       [domain(nacionalidade), alemao, espanhol, italiano]]

  C = [[=, espanhol, [+, vermelha, 1]],
       [=, alemao, azul],
       [=, italiano, 2]]

  S = [c(alemao, 1),
       c(espanhol, 3),
       c(italiano, 2),
       c(azul, 1),
       c(vermelha, 2),
       c(preta, 3)] 

MC346 Home

© 2015 João Meidanis