novembre
2013
Un article de Adjanakis
C’est avec un grand regret que je n’ai pas pu finir à temps ma composition pour aider le Docteur Who à sortir d’un bien mauvais pas. J’ai pu constater avec plaisir qu’il avait pu s’en sortir grâce aux quelques algorithmes qui ont pu être livrés à temps.
Mais pour ceux qui n’en peuvent plus d’attendre de lire un algo qui se rapprocherait de la solution, voici ce que j’aurais dû soumettre pendant le codingame si le manque de temps ne m’avait pas finalement poussé vers une voie de mauvais garçon (à voir sur le site codingame :evil:).
Les constantes ne sont pas les bonnes pour les noires et les blanches et ce code n’a été testé que sur un seul jeu de données(« Only 1 pixel wide – in10.txt »). Cependant, l’idée qui y est présentée me semble bonne et ne devrait souffrir que de petits ajustements pour pouvoir passer l’ensemble des tests.
En quelques mots, les étapes de la résolution sont indiquées dans la méthode main. Tout d’abord, une lecture des données en entrée permet de récupérer dans un tableau à deux dimensions les pixels de l’image. La difficulté est ici de devoir jouer avec les lignes du tableau indépendamment de la lecture du flux en entrée. Une lecture un peu plus complexe que dans la moyenne des codingame, une source de temps perdu, mais une difficulté surmontable.
Ensuite, on peut constater que dans toutes les partitions de musique, les premiers pixels correspondent aux 5 lignes noires. Dans l’algorithme choisi ici, la phase suivante consiste à repérer les coordonnées de ces lignes. Pour cela, la colonne sélectionnée sera la première de l’image contenant des pixels noirs. Cette colonne aura été préalablement déterminée lors de la lecture de la partition. Une sixième ligne pouvant intervenir, on en calcule la position en admettant que toutes les lignes sont séparées par des intervalles réguliers.
La phase suivante est déterminante pour arriver au résultat désiré. Les lignes de la partition déterminent des zones auxquelles on affectera un flag. Pour chaque colonne, on calculera une empreinte qui correspondra à l’ensemble des zones où apparaît un pixel noir, sans tenir compte des pixels des lignes de la portée. On comptabilise par contre le nombre de pixel noir de la colonne pour analyser plus tard la longueur des notes.
Une fois cette étape statistique réalisée, il ne reste plus qu’à en tirer des conclusions. Les colonnes considérées comme ne possédant aucun pixel sont à ignorer. Celles correspondant à une queue de note sont également ignorées car les zones traversées ne correspondant pas à une empreinte de note valide. Lorsqu’une empreinte est valide on conserve l’information et on compare la quantité de pixel noir entre la première et la deuxième colonne où la note apparaît. En effet, les notes blanches ont davantage de pixels noirs sur les côtés, alors que les notes noirs en ont davantage ! En calculant l’évolution de ce nombre, on connait la durée de la note.
Après ces quelques explications, j’espère que vous comprendrez le code source qui suit.
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
class Solution {
private static final int DOWN = 1;
private static final int UP = 0;
private static final String BLACK = "B";
private static final String WHITE = "W";
private static int width = 0;
private static int height = 0;
private static boolean[][] score = null;
private static int blackFirstX = -1;
private static int[][] lignes = new int[6][2];
private static int betweenLines;
private static int[] statZone;
private static int[] statPond;
public static void main(String args[]) throws FileNotFoundException {
readScoreInput();
guessScoreLines();
retrieveStatistics();
System.out.println(buildResult());
}
private static void guessScoreLines() {
int line_number = 0;
boolean onLine = false;
for (int y = 0; y < height; y++) {
if (score[y][blackFirstX]) {
lignes[line_number][DOWN] = y;
if (!onLine) {
onLine = true;
lignes[line_number][UP] = y;
}
} else if (onLine) {
line_number++;
onLine = false;
}
}
betweenLines = lignes[1][UP] - lignes[0][UP];
lignes[5][UP] = lignes[4][UP] + betweenLines;
lignes[5][DOWN] = lignes[4][DOWN] + betweenLines;
}
private static void retrieveStatistics() {
for (int w = 0; w < width; w++) {
int currentZone = 0;
int currentZoneFlag = 1 << currentZone;
int nextLine = 0;
int h = 0;
while (h < height) {
if (nextLine < lignes.length && h == lignes[nextLine][UP]) {
h = lignes[nextLine][DOWN] + 1;
currentZone++;
nextLine++;
currentZoneFlag = 1 << currentZone;
}
if (score[h][w]) {
statZone[w] |= currentZoneFlag;
statPond[w]++;
}
h++;
}
}
}
private static String buildResult() {
Map zoneMapping = new HashMap(13);
zoneMapping.put(1, "G");
zoneMapping.put(3, "F");
zoneMapping.put(2, "E");
zoneMapping.put(6, "D");
zoneMapping.put(4, "C");
zoneMapping.put(12, "B");
zoneMapping.put(8, "A");
zoneMapping.put(24, "G");
zoneMapping.put(16, "F");
zoneMapping.put(48, "E");
zoneMapping.put(32, "D");
zoneMapping.put(96, "C");
zoneMapping.put(64, "B");
StringBuilder result = new StringBuilder();
int currentZone = 0;
int currentPond = 0;
boolean typeIsKnow = false;
for (int w = 0; w = currentPond) ? BLACK : WHITE)
.append(" ");
typeIsKnow = true;
}
}
return result.toString();
}
private static void readScoreInput() throws FileNotFoundException {
Scanner in = new Scanner(new File("test.txt"));
width = in.nextInt();
height = in.nextInt();
score = new boolean[height][width];
statZone = new int[width];
statPond = new int[width];
Arrays.fill(statZone, 0);
Arrays.fill(statPond, 0);
boolean scoreCompleted = false;
int number, w = 0, h = 0;
String color;
blackFirstX = width;
while (!scoreCompleted) {
color = in.next("\\s*[WB]\\s*");
number = in.nextInt();
boolean colorBool = charToBoolean(color);
// tant que l'entrée n'est pas consommée
while (number > 0) {
if (blackFirstX > w && color.trim().equals("B")) {
blackFirstX = w;
}
if (number > (width - w)) {
Arrays.fill(score[h], w, width, colorBool);
number = number - (width - w);
w = 0;
h++;
} else {
Arrays.fill(score[h], w, w + number, charToBoolean(color));
w = w + number;
number = 0;
}
}
scoreCompleted = (h == height - 1);
}
in.close();
}
private static boolean charToBoolean(String color) {
return "B".equals(color.trim());
}
}
Salut Adjanakis,
La durée max était surement sous estimée, désolé :-/
Le problèmes du Doctor Who ne sont pas encore officiellement dispos dans la section training mais si vous souhaitez reprendre votre solution vous pouvez le faire ici : http://www.codingame.com/cg/candidatedemoservlet?id=58783600e82deca476df6a2c088ba307d1f0
a++;
Merci StickyByte,
J’ai lancer quelques tests supplémentaires et effectivement, quelques ajustements sont nécessaire pour déterminer la longueur des notes, mais ce n’est pas bien méchant. Je corrigerai le code de ce billet lorsque j’aurai un peu de temps devant moi !
Niveau timing, je n’aurai sûrement pas du me laisser perturber par des éléments extérieurs pendant la durée du concours, ça m’aurait sûrement permis de gagner quelques précieux pourcent. Ce n’est que partie remise !
@ la prochaine !