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.
NASTRO INIZIALE NASTRO FINALE
CF 2
FC 1
PP 0
FP 2
PC 2

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.

NASTRO INIZIALE NASTRO FINALE
40 P
00 P
53 P
14 D

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).

NASTRO INIZIALE NASTRO FINALE
TTCTC T
TCTCCTCCCTT C
TC P
CCTCTTCTTC P

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.

NASTRO INIZIALE NASTRO FINALE COMMENTO
4457FR OK
11112 OK
FCRFFR1F5F BARO Ci sono 5 fanti
54R4C OK
11111 BARO Ci sono 5 assi

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).
NASTRO INIZIALE NASTRO FINALE
A….X SSP
A#..#X SPS
A.#…#.#.X PSSSSP
AX P
A.X S
A#.X SP
A.#..#X PSPS

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).

NASTRO INIZIALE NASTRO FINALE COMMENTO
34 OK 7
145 KO 10
4RF OK 5
2R4C OK 7
411 OK 6
3R4 OK 7 e 1/2
1R16 KO 8 e 1/2

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.

NASTRO INIZIALE NASTRO FINALE
100/6/326 100
100/6/114 0
20/1/141 40
1300/6/666 3900
8320/2/422 16640
8320/2/153 0
1/1/111 3

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).

NASTRO INIZIALE NASTRO FINALE
478 19
5Q 15
KK 20
KKA 21
A8 19
AJ 21
4QD S
111AA 15

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.
Si scriva un programma per macchina di Turing che riceva sul nastro in ingresso l’elenco di carte a terra, seguito da una / e dalla carta giocata dal giocatore, e lasci sul nastro in uscita l’insieme delle carte a terra dopo la giocata (e l’eventuale presa).
In caso siano possibili più prese, esse sono considerate tutte ugualmente accettabili.
NASTRO INIZIALE NASTRO FINALE COMMENTO
436/4 36 Prende il 4
165F/5 16F Prende il 5
165F/7 5F Prende 6+1=7
165F/3 165F3 Non prende
113R2/7 R Prende 1+1+3+2=7
46/R Prende 4+6=10, scopa!
46/1 461 Non prende
/F F Non prende, cala un fante

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.

NASTRO INIZIALE NASTRO FINALE COMMENTO
XOX.XO..O C XOX
.XO
..O
Nessun tris, partita continua
XOO.XOXXO O XOO
.XO
XXO
Il giocatore O ha fatto tris
XOXXXOOXO P XOX
XXO
OXO
Nessun tris, partita patta
X.O.XO..X X X.O
.XO
..X
Il giocatore X ha fatto tris
C ...
...
...
Nessun tris, partita continua
….O…. C ...
.O.
...
Nessun tris, partita continua
XX..X.OOO O XX.
.X.
OOO
Il giocatore O ha fatto tris
Notice: This work is licensed under a BY-NC-SA. Permalink: Edizione XIII

Comments are closed.