BattleDev du 25 novembre 2020 – PHP

Voici mes réponses, en PHP, aux 4 premiers exercices de la Battle Dev du 25 novembre 2020.

J’ai trouvé ça très sympa d’avoir un fil rouge pour chacune des questions, ça apporte vraiment quelque chose de plus dans la résolution des challenges.

Je me suis classé 387ème, 5ème sur le langage PHP. J’ai bouclé les 3 premiers exercices en 17 minutes, puis j’ai séché sur la version optimisée du 4… Dommage parce que j’avais la version non optimisée ! J’ai fini le 4 vers 23h, après avoir glané quelques indices sur Twitter.

Pour les 4 exercices, je vais vous donner d’abord la réponse que j’ai trouvée rapidement, puis une variante ou un complément, avec ce que j’ai pu trouver en ligne à la suite du concours.

Je ne remets pas tout le descriptif des exercices, vous pouvez tout retrouver ici.

Exercice 1

// Ma solution
$c = 0;
for ($i = 1; $i < count($input); $i++) {
	$fin = substr($input[$i], -5);

	if (is_numeric($fin)) {
		$c++;
	}
}

echo $c;

L’astuce ici c’est d’utiliser substr avec une valeur négative pour démarrer par la fin. Et avec is_numeric on vérifie si c’est un nombre ou pas. On incrémente un compteur et le tour est joué.

// Variante avec une expression régulière
$c = 0;
for ($i = 1; $i < count($input); $i++) {
	if (preg_match('#\d{5}$#', $input[$i])) {
		$c++;
	}
}

echo $c;

// Variante condensée, avec un opérateur ternaire
$c = 0;
for ($i = 1; $i < count($input); $i++) {
    $count += is_numeric(substr($input[$i], -5)) ? 1 : 0;
}
echo $c;

Exercice 2

// Ma solution
$c = 0;
$total = 0;
for ($i = 1; $i < count($input); $i++) {
	$heure = $input[$i];

	if (date('H', strtotime($heure)) >= 20 or  date('H', strtotime($heure)) < 8) {
		$c++;
	}

	$total++;
}

if ($c > floor( $total /2 )) {
	echo 'SUSPICIOUS';
} else {
	echo 'OK';
}

Mon astuce ici c’est d’utiliser date + strtotime en même temps, ce qui me permet d’isoler très facilement un élément d’une date. Je compare donc l’heure, supérieure ou égale à 20 (20h00 inclus), et strictement inférieure à 8 (jusque 07h59). Et à la fin je compare mon compteur avec le total.

Exercice 3

// Ma solution
$retour = '1 ';
$groupeEnCours = [0];

for ($rang = 1; $rang < 10; $rang++) {
	$groupeSuivant = [];
	$countSuivant = 0;

	for ($i = 1; $i < count($input); $i++) {
		$lien = $input[$i];
		$lien = explode(' ', $lien);

		$agent = $lien[0];
		$superieur = $lien[1];
		
		if (in_array($superieur, $groupeEnCours)) {
			$groupeSuivant[] = $agent;
			$countSuivant++;
		}
	}

	$groupeEnCours = $groupeSuivant;
	$retour .= $countSuivant . ' ';
}
echo $retour;

Sur Twitter, ça parlait beaucoup de récursivité pour cet exercice. Étant donné qu’on sait qu’on va faire maximum 10 tours, je ne vois pas vraiment l’intérêt, même si la solution peut être + élégante.

Du coup ici j’initialise au départ mon retour avec un 1 car il n’y a toujours qu’une personne dans le premier groupe. Et le premier groupe est donc le tableau [0].

À chacune de mes 10 itérations, j’initialise un tableau vide qui me servira pour l’itération suivante. Le compteur sert par contre pour compter les agents du niveau en cours. Je parcours donc tous mes couplets agent/supérieur à la recherche de ceux qui font partie du niveau en cours, c’est-à-dire qui dépendent des gens du groupeEnCours. Et j’en profite pour remplir groupeSuivant avec ces mêmes agents. Et à la fin je bascule groupeSuivant dans GroupeEnCours. Et je recommence 10 fois.

Exercice 4

Au début j’ai lu l’énoncé, je l’ai relu, 2 fois, 3 fois… Et j’ai failli abandonner direct… Extrait :

Chaque octet du message est calculé avec une opération décrite par deux entiers L et R (avec L <= R). Le résultat de l’opération est égal à (clé[L] XOR clé[L+1] XOR clé[L+2] …. XOR clé[R-1] XOR clé[R]), où XOR dénote l’opération Ou Exclusif sur des nombres entiers.

BattleDev – Exercice 4 – Beaucoup de devs sont tombés au combat ici même…

Et puis finalement j’ai fini par comprendre 🙂

// Ma solution, non optimisée
$retour = '';
$cle = $input[1];
$cle = explode(' ', $cle);
$octets = [];

for ($i = 2; $i < count($input); $i++) {

	$entiers = $input[$i];
	$entiers = explode(' ', $entiers);

	$l = $entiers[0];
	$r = $entiers[1];

        // Calcul de la position de l'octet, XOR = ^
	$calc = 0;
	for ($k = $l; $k <= $r; $k++) {
		$calc = $calc ^ $cle[$k];
	}
	
        // Enregistrement des positions des octets 
	if (isset($octets[$calc])) {
		$octets[$calc]++;
	} else {
		$octets[$calc] = 1;
	}
}

// Affichage
for ($o = 0; $o <= 255; $o++) {
	if (isset($octets[$o])) {
		$retour .= $octets[$o];
	} else {
		$retour .= 0;
	}

	$retour .= ' ';
}

echo $retour;

Pour chaque couple, je crée un calcul qui consiste à faire des « ^ » entre les différents éléments consécutifs de ma clé. Je prends les éléments 3 à 5 par exemple, puis 7 à 12, etc.

Le résultat me donne toujours une valeur entre 0 et 255 et donc j’incrémente mon tableau $octets avec un ensemble de compteurs indexés avec des clés allant de 0 à 255.

Pour l’affichage je reboucle de 0 à 255 dans le cas où je n’aurais pas forcément au moins un octet à chaque fois.

Pour être franc, je ne maîtrisais pas bien les XOR avant cet exercice, j’ai découvert notamment que 0 ^ a = a. C’est pourquoi j’initialise $calc à 0.

Cette solution me permettait de valider 6 à 7 jeux de tests avant d’atteindre le fameux « Maximum execution time has been reached » (de l’enfer…).

// Solution optimisée
$retour = '';
$cle = $input[1];
$cle = explode(' ', $cle);
$octets = [];

// Je stocke les calculs intermédiaires
$stock = [0];
$calc = 0;
foreach ($cle as $c) {
	$calc = $calc ^ $c;
	$stock[] = $calc;
}

for ($i = 2; $i < count($input); $i++) {

	$entiers = $input[$i];
	$entiers = explode(' ', $entiers);

	$l = $entiers[0];
	$r = $entiers[1];
        // Calcul de mon chemin complet depuis l'origine XOR la portion entre l'origine et le début de mon chemin
	$calc = $stock[$r + 1] ^ $stock[$l];

	if (isset($octets[$calc])) {
		$octets[$calc]++;
	} else {
		$octets[$calc] = 1;
	}
}

for ($o = 0; $o <= 255; $ov++) {
	if (isset($octets[$o])) {
		$retour .= $octets[$o];
	} else {
		$retour .= 0;
	}

	$retour .= ' ';
}

echo $retour;

Encore une fois, je suis arrivé à cette solution en récupérant des indices sur Twitter et en tâtonnant pas mal…

Ce qu’il faut retenir avec les XOR, c’est que :

b ^ c = (a ^ b ^ c) ^ a

C’est-à-dire que je peux calculer une portion d’un chemin, en connaissant la valeur du chemin depuis l’origine, XOR la portion entre l’origine et le début de la portion.

Dans $stocks, je calcule donc tous les chemins possibles depuis l’origine, si j’ai 4 éléments a, b, c et d, je calcule :

a

a ^ b

a ^ b ^ c

a ^ b ^ c ^ d

Et avec ça je peux retrouver toutes les portions de mon chemin. Car les portions sont toujours « consécutives ». Je ne peux pas chercher a ^ d par exemple.

---

Si vous avez une question ou une remarque, n’hésitez pas à me contacter sur Twitter. Je rappelle que c’est du code produit dans le cadre d’un concours de rapidité, il y a donc forcément des choses à optimiser d’un point de vue qualité de code.

Je vous donne rendez-vous pour la prochaine Battle Dev 😉