Edizione XIII

Problema 1 – La morra cinese

Nel gioco della Morra cinese due giocatori scelgono ciascuno un simbolo fra Carta, Forbice, Pietra (di solito, indicandolo in contemporanea con un gesto della mano):

• Forbice vince su Carta
• Carta vince su Pietra
• Pietra vince su Forbice.

Si scriva un programma per macchina di Turing che, ricevuto in ingresso sul nastro una giocata composta da due simboli sull’alfabeto {C, F, P}, lasci in uscita

• 1 se vince il primo giocatore (ovvero, se il primo simbolo vince sul secondo),
• 2 se vince il secondo giocatore (ovvero, se il secondo simbolo vince sul primo),
• 0 altrimenti.

Problema 2 – Pari e Dispari

Nel gioco Pari e Dispari, due giocatori puntano uno su Pari, l’altro su Dispari, e quindi scelgono ciascuno un numero compreso fra 0 e5 (di solito, indicandolo in contemporanea con le dita aperte di una mano).
Si scriva un programma per macchina di Turing che, ricevuto in ingresso sul nastro i numeri scelti dai due concorrenti, lasci in uscitaP se la somma è pari, D se la somma è dispari.

Problema 3 – Testa o croce

Nel gioco Testa o Croce, due giocatori puntano uno su Testa, l’altro su Croce, e quindi lanciano una moneta un numero concordato di volte, scrivendo i risultati di ogni lancio sul nastro di una macchina di Turing.
Vince il concorrente che ha puntato sul simbolo uscito più volte.

Si scriva dunque un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull’alfabeto {T, C} rappresentante gli esiti dei lanci, lasci sul nastro T se sono uscite più teste, C se sono uscite più croci, P se la partita è patta (sono uscite cioè tante teste quante croci).

Problema 4 – Il baro

Un mazzo di carte napoletane contiene un totale di 40 carte, 10 per seme.
Esistono quindi esattamente 4 carte, di diverso seme, per ogni valore; i valori sono i numeri dall’1 al 7, il Fante, il Cavallo e il Re.

Si scriva un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull’alfabeto {1, 2, 3, 4, 5, 6, 7, F, C,R}, dica se la stringa rappresenta una mano valida, ovvero se ogni valore compare al più 4 volte.
In caso di mano valida, la macchina deve lasciare sul nastro OK, altrimenti BARO.

Problema 5 – Super Alan Bros

Nei videogiochi del genere platform, il personaggio controllato dal giocatore deve muoversi lungo un percorso, superando degli ostacoli di vario tipo, fino a raggiungere il premio finale del livello.

• In Super Alan Bros, il giocatore (A) si trova inizialmente a sinistra di una piattaforma, composta da tratti di terreno (.) e da tratti di staccionata (#).
• Il giocatore ha a disposizione solo due mosse: un passo verso destra (P), che lo porta nella successiva casella a destra, e un salto (S) che lo porta due caselle verso destra, saltando una casella.
• Poiché non è possibile camminare attraverso una staccionata, questi tratti possono solo essere saltati.
• Scopo del gioco è portare Alan nella posizione del tesoro (X), nel minor numero di mosse possibile.

Si scriva un programma per macchina di Turing che, ricevuto sul nastro una stringa descrivente il livello nella situazione iniziale, lasci sul nastro la sequenza di mosse di lunghezza minima che porta Alan sul tesoro di fine livello, senza mai camminare attraverso staccionate.

• Alan ha un comportamento eager: tutte le volte che è possibile sia fare un passo che fare un salto (atterrando su terreno piano e senza superare il tesoro), Alan preferisce fare un salto.
• È garantito che il livello di input sia risolubile (per esempio, non ci saranno lunghi tratti di staccionata come ### che non possono essere superati con un salto).

Problema 6 – Sette e mezzo

Nel gioco Sette e mezzo, ciascun giocatore riceve inizialmente una carta da un mazzo napoletano, e può poi chiedere ulteriori carte a sua discrezione.
Lo scopo è di avvicinarsi il più possibile al punteggio di 7 e mezzo (ogni carta vale il proprio punteggio nominale, mentre le figureFante, Cavallo, Re valgono ciascuna mezzo punto), senza superarlo.

Si scriva un programma per macchina di Turing che, ricevuto in ingresso sul nastro una stringa sull’alfabeto {1, 2, 3, 4, 5, 6, 7, F, C,R}, in cui ogni simbolo rappresenta una carta, dica se la giocata ha sballato superando il 7 e mezzo (lasciando sul nastro KO) o no (lasciando sul nastro OK).

Problema 7 – Dadi

Le scommesse sui dadi hanno portato alla rovina più di un giocatore.
In una variante di questo gioco, il giocatore punta una cifra a sua discrezione (strettamente maggiore di 0) su un numero fra 1 e 6; vengono quindi lanciati tre dadi a 6 facce, e il giocatore incassa tante volte la posta quanti sono i dadi che hanno fornito il risultato su cui ha puntato.
Se nessun dado ha dato quel risultato, il giocatore perde la posta.

Si scriva un programma per macchina di Turing che, ricevuta sul nastro una sequenza composta da un numero rappresentante la puntata, un simbolo e infine i tre valori forniti dai dadi, lasci sul nastro la vincita da incassare.

Problema 8 – Black jack

Il gioco Black jack, simile al Sette e mezzo, usa un mazzo di carte francesi, dall’asso al re (13 carte per seme), che indicheremo con {A,2, 3, 4, 5, 6, 7, 8, 9, D, J, Q, K} (D=10, J=Jack, Q=Queen, K=King).

• Nel Black jack, l’asso vale 1 o 11 punti a scelta del giocatore; J, Q e K valgono 10 punti, le carte dal 2 al 10 valgono ciascuna il proprio valore nominale.
• Scopo del gioco è avvicinarsi il più possibile al 21, senza superarlo.
• Il punteggio più ambito è ovviamente il black jack, dato da asso (con valore 11) e una figura (con valore 10), per un totale di 21.

Si scriva un programma per macchina di Turing che, data sul nastro di ingresso una serie di carte, lasci in uscita il valore numerico della giocata, scegliendo per l’asso il valore 1 o 11 a seconda di quale è più conveniente al giocatore.
Se il risultato supera il 21, il programma deve lasciare in uscita il solo simbolo S (superamento).

Problema 9 – Scopa

La Scopa si gioca con le carte napoletane.

• A turno, i giocatori scartano una carta, e se sono presenti a terra una o più carte per cui la somma del valore coincide con la carta scartata, il giocatore prende la propria carta e quelle che assommano lo stesso valore; in caso contrario, la carta viene lasciata a terra.
• Nella scopa, il Fante vale 8, il Cavallo vale 9, il Re vale 10, tutte le altre carte valgono il proprio valore nominale.

Problema 10 – Il Tris

Nel gioco del Tris, i concorrenti piazzano alternativamente un simbolo O (lettera O, non numero 0) o X in una casella di una scacchiera 3x3, spesso rappresentata come nelle figure sotto.

• Vince il concorrente che allinea tre simboli uguali in orizzontale, verticale o diagonale.
• Il gioco continua, con mosse alternate, finché ci sono caselle libere sulla scacchiera.

Si scriva un programma per macchina di Turing che, ricevuta sul nastro in ingresso una rappresentazione per righe di una scacchiera valida, in cui il simbolo . indica una casella vuota, lasci sul nastro il simbolo X o O se uno dei due giocatori ha vinto, P se è un pareggio, C se il gioco continua.