Keskustelu: Ohjelmointikysymykset: Pascal: Mikähän on pasianssin läpimenotodennäköisyys?

program PetriAnssi;

uses SysUtils;

function KortinNimi(Kortti: Integer): String;
var
  Maa, Arvo: Integer;
  MaaS, ArvoS: String;
begin
  Maa := Kortti mod 4;
  Arvo := Kortti div 4;
  case Maa of
    0: MaaS := 'risti';
    1: MaaS := 'ruutu';
    2: MaaS := 'hertta';
    3: MaaS := 'pata';
  end;
  case Arvo of
    0: ArvoS := 'K';
    11: ArvoS := 'J';
    12: ArvoS := 'D';
    1..10: ArvoS := IntToStr(Arvo);
  end;
  KortinNimi := MaaS + '-' + ArvoS;
end;

function AjaPeli(Tulosta: Boolean): Boolean;
var
  Kortit: Array [0..51] of Integer;
  Nostettu, NostettuAlussa: 4..52;
  Maa: 0..3;
  I, J: Integer;
  MaaLkm: Array[0..3] of Integer;
begin
  AjaPeli := True;
  for I := 0 To 51 do begin
    J := Random(I + 1);
    Kortit[I] := Kortit[J];
    Kortit[J] := I;
  end;
  Nostettu := 4;
  repeat begin
    if Tulosta then WriteLn(KortinNimi(Kortit[0]):10, KortinNimi(Kortit[1]):10, KortinNimi(Kortit[2]):10, KortinNimi(Kortit[3]):10);
    NostettuAlussa := Nostettu;
    for Maa := 0 to 3 do MaaLkm[Maa] := 0;
    for I := 0 to 3 do Inc(MaaLkm[Kortit[I] mod 4]);
    for I := 0 to 3 do if MaaLkm[Kortit[I] mod 4] > 1 then begin
      Kortit[I] := Kortit[Nostettu];
      Inc(Nostettu);
      if Nostettu = 52 then Exit;
    end;
  end until Nostettu = NostettuAlussa;
  AjaPeli := False;
end;

var
  Tulokset: Array [Boolean] of LongInt;
  I, N: LongInt;
begin
  Randomize;
  if AjaPeli(True) then WriteLn('Pakka tyhjenee.') else WriteLn('Tappio.');
  WriteLn('Montako ajetaan?');
  ReadLn(N);
  Tulokset[True] := 0;
  Tulokset[False] := 0;
  for I := 1 to N do begin
    Inc(Tulokset[AjaPeli(False)]);
    if (I = N) or (I mod 100000 = 0) then
      WriteLn('Voittoja ', Tulokset[True], ', tappioita ', Tulokset[False], ', voittoja ', (100 * Tulokset[True] / I):4:2, ' %');
  end;
end.

(() => {
let kertoma = Array(53).fill().map((x, i, t) => t[i] = i ? t[i-1] * BigInt(i) : 1n);

let muisti = {};
function tulos(tila) {
	// Pakka tyhjä?
	if (tila[0] + tila[1] + tila[2] + tila[3] == 0) {
		return {voitot: 1n, tappiot: 0n};
	}
	// Pöytä täysi?
	if (tila[4] + tila[5] + tila[6] + tila[7] == 4) {
		// Pöydällä pelkkiä ykkösiä? => Tappioiden määrä on pakan mahdollisten järjestysten määrä.
		if ((tila[4] | tila[5] | tila[6] | tila[7]) == 1) {
			return {voitot: 0n, tappiot: kertoma[tila[0] + tila[1] + tila[2] + tila[3]]};
		}
		// Muuten poistetaan samat maat.
		if (tila[4] > 1) tila[4] = 0;
		if (tila[5] > 1) tila[5] = 0;
		if (tila[6] > 1) tila[6] = 0;
		if (tila[7] > 1) tila[7] = 0;
	}

	// Dynaaminen ohjelmointi, alkeisversio:
	// Jos tämä tila on jo laskettu, palautetaan tulos muistista.
	let avain = tila.join(",");
	if (muisti[avain]) return muisti[avain];

	// Käydään kaikki vaihtoehdot, mitä maata pakasta voi tulla.
	let summa = {voitot: 0n, tappiot: 0n};
	for (let maa of [0, 1, 2, 3]) if (tila[maa]) {
		// Koska seuraava kortti voi olla mikä tahansa, seuraava välitulos pitää kertoa vaihtoehdoilla.
		let vaihtoehtoja = BigInt(tila[maa]);
		// Siirretään tätä maata yksi pakasta pöydälle.
		let uusi = tila.concat();
		uusi[maa] -= 1;
		uusi[maa + 4] += 1;
		// Rekursiolla jatketaan.
		let t = tulos(uusi);
		summa.voitot += t.voitot * vaihtoehtoja;
		summa.tappiot += t.tappiot * vaihtoehtoja;
	}
	muisti[avain] = summa;
	return summa;
}

// Ratkaisun alussa pakassa on 13 jokaista maata ja esillä 0 jokaista maata.
let t = tulos([13, 13, 13, 13, 0, 0, 0, 0]);
return 100 * Number(t.voitot) / Number(t.voitot + t.tappiot);
})();

program pasianssi;
TYPE kortit = 	1..52;
	maat  	=	1..4;
	poytaind	=	1..4;
VAR	lapimenot, peli	:	LongInt;
	poytakortit	:	ARRAY[1..4] OF kortit;
	pakka	:	ARRAY [1..52] OF kortit;
	ind		:	kortit;
	lapimeni	:	BOOLEAN;
	maxpeli	:	Longint;
function kortinmaa(kortti:kortit):maat; {palauttaa kortin 1..52 maan 1..4}
BEGIN
	kortinmaa:=(kortti-1) div 13+1;
END;
PROCEDURE alusta; {laitetaan taulukkoon 52 korttia, jotta taulukko voidaan sekoittaa}
VAR i	:	kortit;
BEGIN
	FOR i:=1 TO 52 DO
		pakka[i]:=i;
	lapimenot:=0;
	maxpeli:=1000000;
END;
PROCEDURE sekoitapakka;
VAR i,j, apu	: 	kortit;
BEGIN
	Randomize;
	FOR i:=1 TO 52 DO {vaihdetaan 52 kertaa korttipareja}
		BEGIN
			apu:= pakka[i];
			j:=Random(52)+1;
			pakka[i]:=pakka[j];
			pakka[j]:=apu;
		END;
END;
FUNCTION kaikkierimaata:BOOLEAN; {Onko taulukossa poytakortit kaikki erimaata?}
BEGIN
	IF ind<=49 THEN
	BEGIN
		IF ((kortinmaa(poytakortit[1])<>kortinmaa(poytakortit[2]))
			AND (kortinmaa(poytakortit[1])<>kortinmaa(poytakortit[3]))
			AND (kortinmaa(poytakortit[1])<>kortinmaa(poytakortit[4]))
			AND (kortinmaa(poytakortit[2])<>kortinmaa(poytakortit[3]))
			AND (kortinmaa(poytakortit[2])<>kortinmaa(poytakortit[4]))
			AND (kortinmaa(poytakortit[3])<>kortinmaa(poytakortit[4])))
			THEN
				BEGIN
					kaikkierimaata:=TRUE;
				END
			ELSE kaikkierimaata:=FALSE;
	END;
	IF ind=50 THEN
	BEGIN
		IF (kortinmaa(poytakortit[1])<>kortinmaa(poytakortit[2]))
			AND (kortinmaa(poytakortit[1])<>kortinmaa(poytakortit[3]))
			AND (kortinmaa(poytakortit[2])<>kortinmaa(poytakortit[3]))
			THEN
				BEGIN
					kaikkierimaata:=TRUE;
				END
			ELSE kaikkierimaata:=FALSE;
	END;
	IF ind=51 THEN
	BEGIN
		IF kortinmaa(poytakortit[1])<>kortinmaa(poytakortit[2])
			THEN
				BEGIN
					kaikkierimaata:=TRUE;
				END
			ELSE kaikkierimaata:=FALSE;
	END;
END;
PROCEDURE poistakortit(iind,jind:maat);
BEGIN
	poytakortit[iind]:=pakka[ind];
	ind:=ind+1;
	poytakortit[jind]:=pakka[ind];
	IF (ind>=51) THEN
	BEGIN
		lapimeni:=TRUE; {läpimeni}
		lapimenot:=lapimenot+1;
		WRITELN('Läpimeni');
	END;
END;
PROCEDURE poistasamatmaat;
VAR i,j,vika	:	poytaind;
BEGIN
	IF ind<=49 THEN vika:=4;
	IF ind=50 THEN vika:=3;
	IF ind=51 THEN vika:=2;

	FOR i:=1 TO vika DO {poistetaan kortit, mitkä ovat ekan kanssa samaa maata.}
		FOR j:=i+1 TO vika DO
			IF kortinmaa(poytakortit[i])=kortinmaa(poytakortit[j]) THEN
				poistakortit(i,j);
	FOR i:=2 TO vika DO {poistetaan kortit, mitkä ovat tokan kanssa samaa maata. "Tokan oikealla puolella"}
		FOR j:=i+1 TO 4 DO
			IF kortinmaa(poytakortit[i])=kortinmaa(poytakortit[j]) THEN
				poistakortit(i,j);
	IF kortinmaa(poytakortit[vika-1])=kortinmaa(poytakortit[vika]) THEN
				poistakortit(vika,vika+1);

END;
PROCEDURE pelaapasianssi;
VAR i	:	poytaind;
BEGIN
	{laitetaan neljä ensimmäistä korttia pöydälle}
	ind:=5; {osoittaa pakan päälimmäiseen korttiin}
	FOR i:=1 TO 4 DO poytakortit[i]:=pakka[i];
	REPEAT
		poistasamatmaat;
	UNTIL kaikkierimaata OR lapimeni;
END;
begin
	alusta;
	sekoitapakka;
	FOR peli:=1 TO maxpeli DO
		BEGIN
			pelaapasianssi;
			sekoitapakka;
		END;
	WRITELN('Lapimenoprosentti=', (100 * lapimenot / maxpeli):5);
end.

program pikkupasianssi;
CONST	peleja	=	100000000; {10 miljoonaa simulointia}
TYPE kortit = 	1..52;
VAR	pakka	:	ARRAY [1..52] OF kortit;
	eimennytlapi	:	BOOLEAN;
	tappioita, peli	:	LongInt;
	indeksi	:	kortit;
function arvo(kortti:kortit):kortit; {palauttaa kortin arvon}
BEGIN
	arvo:=((kortti-1) mod 13)+1;
END;
PROCEDURE alusta; {Laitetaan kortit pakkaan sekoitusta varten}
BEGIN
	Randomize;
	FOR indeksi:=1 TO 52 DO
		pakka[indeksi]:=indeksi;
	tappioita:=0;

END;
PROCEDURE sekoitapakka; {Vaihdetaan 52 korttia}
VAR i,j, apu	: 	kortit;
BEGIN
	FOR i:=1 TO 52 DO
		BEGIN
			apu:= pakka[i];
			j:=Random(52)+1;
			pakka[i]:=pakka[j];
			pakka[j]:=apu;
		END;
END;
PROCEDURE pelaa;
VAR pelaajanlaskuri: kortit;
BEGIN
	indeksi:=1;
	pelaajanlaskuri:=1;
	eimennytlapi:=FALSE;
	REPEAT
		IF arvo(pakka[indeksi])=pelaajanlaskuri THEN eimennytlapi:=TRUE;
		pelaajanlaskuri:=pelaajanlaskuri+1;
		IF pelaajanlaskuri=14 THEN pelaajanlaskuri:=1;
		indeksi:=indeksi+1;
	UNTIL (indeksi=52) OR eimennytlapi;
END;
begin
	alusta;
	FOR peli:=1 TO peleja DO
	BEGIN
		sekoitapakka;
		pelaa;
		IF eimennytlapi THEN tappioita:=tappioita+1;
	END;
	WRITELN('Läpimenoja=', peleja-tappioita,' kpl eli läpimenoprosentti=', 100*(peleja-tappioita)/peleja);
end.

function PoistaKortit: Boolean;
var MaanMaara: Array [Maa] of Integer;
begin
  for i := 1 to 4 do MaanMaara[KortinMaa(Kortit[i])] := 0;
  for i := 1 to 4 do Inc(MaanMaara[KortinMaa(Kortit[i])]);
  for i := 1 to 4 do if (MaanMaara[KortinMaa(Kortit[i])] > 1 then begin
    PoistaKortit := True;
    if not PakkaTyhja then Kortit[i] := Nosta;
  end;
end;

function PelinTulos: Boolean;
begin
  while not PakkaTyhja do if not PoistaKortit then Break;
  PelinTulos := PakkaTyhja;
end;

(() => {
'use strict';
let kertoma = Array(53).fill().map((x, i, t) => t[i] = i ? t[i-1] * BigInt(i) : 1n);

let muisti = {};
function tulos(tila) {
	// Pakka tyhjä?
	if (tila[0] + tila[1] + tila[2] + tila[3] == 0) {
		return {voitot: 1n, tappiot: 0n};
	}

	// Dynaaminen ohjelmointi, alkeisversio: jos tämä tila on laskettu, palautetaan tulos muistista.
	let avain = tila.join(",");
	if (muisti[avain]) return muisti[avain];

	// Käsi täysi?
	if (tila[4] + tila[5] + tila[6] + tila[7] == 4) {
		// Enintään yksi joka maata? => Tappioiden määrä on pakan mahdollisten järjestysten määrä.
		if ((tila[4] | tila[5] | tila[6] | tila[7]) == 1) {
			return muisti[avain] = {voitot: 0n, tappiot: kertoma[tila[0] + tila[1] + tila[2] + tila[3]]};
		}
		// Muu määrä kuin 0 tai 2 jotain maata? => Vain yksi on poistettavissa.
		if ((tila[4] | tila[5] | tila[6] | tila[7]) != 2) for (let maa of [4, 5, 6, 7]) if (tila[maa] > 1) {
			tila[maa] = 0;
			return muisti[avain] = tulos(tila);
		}
		// Kahta maata, etsitään ne ja valitaan a = enempi.
		let a = 0, b = 3;
		while (tila[a + 4] <= 1) ++a;
		while (tila[b + 4] <= 1) --b;
		if (tila[a] < tila[b]) [a, b] = [b, a];

		// Strategiat:
		const strategia = ["huonoin", "vähempi", "random", "enempi", "paras"][4];
		switch (strategia) {
			case "random":
				tila[(Math.random() < 0.5 ? a : b) + 4] = 0;
				return muisti[avain] = tulos(tila);
			case "enempi":
				tila[a + 4] = 0;
				return muisti[avain] = tulos(tila);
			case "vähempi":
				tila[b + 4] = 0;
				return muisti[avain] = tulos(tila);
			default:
				let uusi = tila.concat();
				tila[a + 4] = 0;
				uusi[b + 4] = 0;
				let t = [tulos(tila), tulos(uusi)];
				let paras = t[0].voitot * t[1].tappiot < t[1].voitot * t[0].tappiot ? 1 : 0;
				return muisti[avain] = (strategia == "paras") ? t[paras] : t[paras ^ 1];
		}
	}

	// Käydään kaikki vaihtoehdot, mitä maata pakasta voi tulla.
	let summa = {voitot: 0n, tappiot: 0n};
	for (let maa of [0, 1, 2, 3]) if (tila[maa]) {
		// Koska seuraava kortti voi olla mikä tahansa, seuraava välitulos pitää kertoa vaihtoehdoilla.
		let vaihtoehtoja = BigInt(tila[maa]);
		// Siirretään tätä maata yksi pakasta käteen.
		let uusi = tila.concat();
		uusi[maa] -= 1;
		uusi[maa + 4] += 1;
		// Rekursiolla jatketaan.
		let t = tulos(uusi);
		summa.voitot += t.voitot * vaihtoehtoja;
		summa.tappiot += t.tappiot * vaihtoehtoja;
	}
	return muisti[avain] = summa;
}

let t = tulos([13, 13, 13, 13, 0, 0, 0, 0]);
print(100 * Number(t.voitot) / Number(t.voitot + t.tappiot));
})();