BattleDev du 3 Juin 2021 – PHP

Voici les solutions en PHP aux exercices 3 et 4.

J’ai résolu les 2 premiers exercices en quelques minutes. Puis j’ai mis une petite heure sur le 3, ce fameux Tetris. J’ai résolu le 4 de façon « naïve » assez rapidement. J’avais donc une solution mais elle ne permettait pas de passer les cas comportant beaucoup (beaucoup) de données. C’est souvent à partir de l’exercice 4 que les choses se corsent vraiment ! J’ai trouvé des pistes vers 21h50 mais pas eu le temps du coup de les implémenter. Et c’est en suivant le débrief sur le Twitch de h25io, que j’ai pu finaliser ma solution. Merci à eux pour ce débrief et le contenu qu’ils produisent régulièrement 😉

Pour Tetris, j’ai réécrit ma solution à partir de leur logique, je vous mettrais ma solution aussi pour le fun, mais elle est vraiment + tordue :p

Les énoncés complets et les autres exercices sont disponibles ici.

Remarque : dans mon code ci-dessous, j’utilise la fonction exit si tôt que j’ai trouvé la réponse à afficher. C’est une astuce utile dans ce genre de concours. On évite les else ou autre imbrications à gérer pour savoir quoi afficher à la fin.

Exercice 3 : Tetris

En réfléchissant, on se rend compte assez vite qu’il ne peut y avoir qu’un seul Tetris possible. C’est-à-dire une seule colonne où vous pouvez déposer une barre verticale pour « effacer » 4 lignes d’un coup. Donc si vous en trouvez une, c’est forcément la seule.

Il y avait des cas particuliers comme celui-ci qui m’ont compliqué la vie :

Ici, on peut mettre la barre verticale dans la dernière colonne, mais ça ne fait pas un Tetris car la ligne 8 n’est pas complète. Et même si vous détectiez que les lignes 4, 5, 6 et 7 sont OK, ça ne marchait pas. Il fallait donc un NOPE sur un cas comme ça.

Une première astuce consistait à rajouter une ligne pleine « ##### » tout en bas.

On cherchait ensuite, pour chaque colonne, le premier bloc # pour savoir où je peux poser ma barre verticale. Il fallait alors regarder si les 4 lignes du dessus étaient « pleines », prêtes à faire un Tetris.

Voici le code :

$lines = $input;

// On rajoute une ligne pleine
$lines[] = str_repeat('#', 10); // On a 21 lignes désormais

// Vérifie si une ligne est "pleine", c'est à dire prête à accueillir un Tetris
function pleine($line)
{
	return substr_count($line, '#') == 9;
}

// On va parcourir chaque colonne
for ($c = 0; $c <= 9; $c++) {

	// Dans chaque colonne, je cherche le point le + bas, c'est à dire le premier #
	// Comme on a rajouté la 21è ligne, on aura forcément un dernier bloc
	for ($l = 0; $l <= 20; $l++) {
		if ($lines[$l][$c] == '#') {
			$dernierBloc = $l;
			break;
		}
	}

	// Pas la place de mettre une barre
	if ($dernierBloc < 4) {
		continue;
	}

	// Je dois donc vérifier que les 4 lignes au dessus sont "pleines"
	if (
		pleine($lines[$dernierBloc - 1]) &&
		pleine($lines[$dernierBloc - 2]) &&
		pleine($lines[$dernierBloc - 3]) &&
		pleine($lines[$dernierBloc - 4])
	) {
		echo 'BOOM ' . ($c + 1);
		exit;
	}
}

echo 'NOPE';

Exercice 4 : les orbites

On avait donc ici une suite de caractères représentant des déchets, il fallait trouver le nombre de séparations permettant de retrouver le même nombre de déchets d’un côté comme de l’autre.

Solution « naïve »

Je vous mets ma solution naïve, non optimisée, qui peut permettre de bien comprendre ce qu’on cherche à faire.

J’ai une première fonction « slices » qui permet par exemple de découper « ABCDEFGH » en « ABCD » et « EFGH », ou « BCDE » et « FGHA » etc. pour avoir les séparations de mes déchets (à base de substr).

Ensuite, je compte les occurrences de chaque caractère, j’ordonne, et je compare.

Voici le code :

$max = (int) $input[0];
$nb = 0;

for ($i = 0; $i < $max; $i++) {

	$tabs = slices($input[1], $i);

	$tab1 = array_count_values(str_split($tabs[0]));
	$tab2 = array_count_values(str_split($tabs[1]));

	ksort($tab1);
	ksort($tab2);

	if ($tab1 == $tab2) {
		$nb++;
	}
}

echo $nb;

Et ça fonctionne très bien sur les premiers jeux de données, mais assez vite, on manque de performance pour résoudre les gros jeux de données.

Solution optimisée

Plusieurs choses à prendre en compte. Tout d’abord, il n’y a qu’une seule répartition possible. Si j’ai dans mes déchets : 4 A, 2 B et 2 C. La seule répartition possible pour avoir le même nombre de chaque côté est : 2A, 1B et 1C. Je peux donc commencer par chercher cette répartition, qui sera mon modèle de comparaison.

Ensuite, je n’ai besoin de parcourir que la moitié de mes déchets, puisque passer la moitié, je vais simplement inverser les côtés de ma répartition, mais ce sera la même. Donc je ne parcours que la moitié et je multiplierais le résultat par 2.

Enfin, et le plus important, quand je me déplace de 1 dans ma liste de déchets, il n’y a en fait que 2 valeurs qui changent :

• Un caractère s’en va
• Un nouveau caractère arrive

Donc d’une répartition à l’autre, pas besoin de tout recalculer, il suffit de mettre à jour ces 2 valeurs.

Voici le code :

$max = (int) $input[0];
$half = $max / 2;

// On va compter toutes les valeurs
$repartition = array_count_values(str_split($input[1]));

// On range dans le bon ordre
ksort($repartition);

// On calcule la moitié de la répartition
// et on initialise l'autre tableau ($mouvant) en même temps, pour avoir le même ordre
$mouvant = [];
foreach ($repartition as $char => $count) {
	$repartition[$char] = $count / 2;
	$mouvant[$char] = 0;
}

// On initialise $mouvant avec la première moitié des déchets
for ($i = 0; $i < $half; $i++) {
	$mouvant[$input[1][$i]]++;
}

// Initialisation du résultat
$nb = (int) ($mouvant === $repartition);

// Parcours pas à pas
for ($i = 0; $i < ($half - 1); $i++) {
	
	// Le caractère qui s'en va    
	$char1 = $input[1][$i];
	$mouvant[$char1]--;
    
    // Le caractère qui arrive
	$char2 = $input[1][($i + $half)];
	$mouvant[$char2]++;

	$nb += (int) ($mouvant === $repartition);
}

echo $nb * 2;

Et voilà 🙂

Bonus : ma solution à Tetris

function plein($line)
{
	return substr_count($line, '#') == 9;
}

// Je parcous chaque colonne
for ($c = 0; $c <= 9; $c++) {
    
    // Pour réussir, il me faut minimum 4 à succes
    // Et $socle à true
	$success = 0;
	$socle = true;
	for ($i = 19; $i >= 0; $i--) {

		$line = $input[$i];
		
        // Si je tombe sur "#" je remets mon compteur à 0
        // Et socle à true du coup car je pourrais poser une barre
		if ($line[$c] == '#') {
		    $success = 0;
		    $socle = true;
		    continue;
		}
		
        // Si j'ai pas de socle, je passe
		if (!$socle) {
		    continue;
		}
	    
        // J'incrémente success s'il y a de la place
		if ($line[$c] == '.') {
			$success++;
		}
        
        // Mais au premier, je vérifie que la ligne est bonne
        // sinon ce n'est pas bon et je ne pourrais pas poser ma barre ici
		if ($success == 1 && !plein($line)) {
			$socle = false;
			continue;
		}
		
        // Si je suis là c'est que je vais pouvoir poser ma barre
		$socle = true;
        
        // Pour les 4 premières lignes, je dois être sûr qu'elles sont "pleines
        // Sinon je retombe à 0
		if ($success <= 4 && !plein($line)) {
			$success = 0;
		}
	}

	if ($success >= 4 && $socle) {
		echo 'BOOM ' . ($c + 1);
		die();
	}
}

echo 'NOPE';