Bonjour, j'essaie de résoudre un exo sur coding game, mais honnêtement je comprend même pas l'énoncé ..
Les règles:
Dans cet exercice, on vous donne une grille représentant un parcours de golf.
Sur chaque parcours se trouve une certaine quantité de balles et une quantité égale de trous. L'objectif est de tracer le trajet de chaque balle vers un trou différent sans que les trajets ne se croisent.
Votre programme doit afficher la solution unique du parcours.
Pour chaque parcours est donné le nombre de colonnes et de lignes. Chaque case est représentée par un caractère.
Une case peut être :
Un point . pour une cellule vide, représentant du gazon.
Un entier allant de 1 à 9, représentant une balle. La valeur indique son nombre de coups.
La lettre X, représentant un obstacle d'eau.
La lettre H, représentant un trou.
Une balle peut être tapée plusieurs fois, autant que son nombre de coups.
Votre programme doit afficher sur la sortie standard une grille de taille égale à celle donnée en entrée, contenant des flèches indiquant comment les balles doivent être tapées.
Une flèche est représenté par une série de cases contenant une direction.
Les quatre directions sont représentées par les caractères v, <, > et ^ (respectivement bas, gauche, droite et haut).
Pour représenter le mouvement d'une balle, une flèche doit commencer là où se trouvait la balle et s'arrêter juste avant la case où la balle atterrit.
Vous devez afficher uniquement les flèches, utilisez des caractères point . pour toute autre case.
Les flèches ne doivent pas croiser l'emplacement de balles, de trous ou d'autres flèches.
Le nombre de coups d'une balle indique aussi le nombre de cases qu'elle traverse la première fois qu'elle bouge.
Le prochain coup ira une case moins loin, chaque coup décrémente le nombre de cases que la balle traverse de 1.
À chaque nouveau coup la balle pourra être tapée dans une nouvelle direction.
Quand le prochain coup devient 0 ou que la balle s'arrête sur une case trou, la balle ne peut plus bouger.
Chaque balle doit atteindre un trou. Un trou peut recevoir au plus 1 balle.
Une balle ne peut pas quitter la grille, ni atterrir dans un obstacle d'eau. Elle peut cependant passer par dessus les obstacles d'eau.
Conditions de victoire
Affichez une grille solution :
Une balle ne peut pas quitter la grille, ni atterrir dans un obstacle d'eau. Elle peut cependant passer par dessus les obstacles d'eau.
Toute balle doit finir dans un trou en au moins un coup.
Les flèches ne peuvent se croiser.
Les flèches ne peuvent croiser les positions ni des balles ni des trous.
Les flèches ne peuvent amener à un obstacle d'eau.
Les flèches ne peuvent amener à l'extérieur de la grille.
Le problème est que je comprend pas l'énoncé + le résultat, par exemple pour une grille comme celle-là:
2.X
..H
.H1
Le résultat attendu est: "v.."
Alors déjà plusieurs questions, on nous dit que les digits allant de 1-9 sont des balles, jusque là OK!
Donc, je regarde le résultat par rapport à la grille et ça à l'air de bien match avec la balle 2, mais quant est-t-il pour la balle 1 ??
Je vois pas comment le résultat peut être celui-ci pour la balle 1, et même en disant "qu'elle traverse la map" le nombre de coups dépassent.
Encore une autre:
4..XX
.H.H.
...H.
.2..2
.....
Résultat attendu: "v...."
Là encore, je suis largué. En faisant le chemin pour la balle 4, ça mène nulle part.
...XX
.H.H.
...H.
.2..2
4....
// le 4 serait alors ici ???
et pour les balles 2 il y a plus de coups que leur digits imposent.
SVP pouvez vous m'expliquer, et en faisant le chemin pas à pas avec une balle pour que je suis comprendre svp
Tu pourrais quand même poster l'énoncé ailleurs que dans un container de code. Là ça ne facilite pas la lecture et ça ne donne pas envie de le lire !
EDIT :
loictuchus a écrit:
Le problème est que je comprend pas l'énoncé + le résultat, par exemple pour une grille comme celle-là:
2.X
..H
.H1
Le résultat attendu est: "v.."
Le résultat attendu est étonnant ? Car il est dit dans l’énoncé que la grille résultat doit avoir la même taille que la grille d'entrée :
loictuchus a écrit:
Votre programme doit afficher sur la sortie standard une grille de taille égale à celle donnée en entrée, contenant des flèches indiquant comment les balles doivent être tapées.
Il faut que tu trouves l'endroit du code où a lieu l'erreur de segmentation. Par exemple tu ajoutes des 'printf' numérotés partout et tu regardes ce qu'il se passe entre le dernier 'printf' affiché et le premier non affiché. C'est là qu'il se passe un truc louche. Cette méthode peut sembler laborieuse, mais c'est beaucoup plus rapide que de tenter de trouver le souci juste en regardant le listing (en tout cas pour moi).
Un détail de programmation, comme je suis fainéant, au lieu d'avoir 4 fois le même genre de code pour les 4 directions, je préfère écrire une boucle
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (is_inside(ny, nx) && !constraints(map[ny][nx]))
{
map[ny][nx] = symbol[d];
if (algo(counter + 1, value, ny,nx))
return true;
map[ny][nx] = save_char;
counter = save_counter;
}
}
Merci pour ce conseil ce fainéant ! Toutefois, je doute que ce code fournit fasse le même boulot je pense qu'il y a un problème par exemple si la carte c'est: 1H
Mais merci je vais appliquer ça dans mon code ce sera plus lisible
J'ai utilisé ce truc dans des programmes des dizaines de fois, et ça a toujours marché (après avoir corrigé les typos, qui arrivent de temps en temps)
C'est peut être le cas, mais comme le code de départ est réputé ne pas marcher, je n'ai pas testé.
Mais effet, ce que j'ai écrit n'est pas - par inadvertance - équivalent. Un truc qui beugue dans le code d'origine, à mon avis, c'est précisément l'enchaînement de if then else if etc, qui empêche, si c'était possible d'emprunter une direction, d'essayer les suivantes en cas d'échec.
Mais ça c'est un problème d'algorithme correct ou pas, plutôt que de simplification de code équivalent.
PS pour un code équivalent à celui qui ne marche pas, faudrait un break dans le if pour échapper du for
for (int d = 0; d < 4; d++)
{
int nx = x + dx[d];
int ny = y + dy[d];
if (is_inside(ny, nx) && !constraints(map[ny][nx]))
{
// ...
counter = save_counter;
break; // <---- ICI
}
}
- Edité par michelbillaud 21 décembre 2023 à 17:30:38
mais je comprend pas .. j'ai eu beau tout essayé, ça ne marche pas. Je sais pas pourquoi rien ne se rempli dans map. C'est là que je rend compte que je suis vraiment débutant, le backtracking >< Et même en voulant avoir la même sortie que mon code qui ne marche pas(break), bah là non plus, on peut dire qu'au moins il est efficace dans tout ce qui ne marche pas
bool algo2(int value, int y, int x, int h, int w, char map[][w])
{
if (map[y][x] == 'H') {
map[y][x] = 'F';
return true;
}
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (is_inside(ny, nx, w, h) && !constraints(map[ny][nx]))
{
char save_char = map[ny][nx];
char save_value = map[y][x];
map[ny][nx] = symbol[d];
if (algo2(value - 1, ny, nx, h, w, map))
return true;
map[ny][nx] = save_char;
map[y][x] = save_value;
}
}
return false;
}
Mais outre ce raccourci, j'ai compris mon erreur enfin je pense. Je sais pas comment lui dire mets x char puis passe au suivant. Tout ce que je fais là cette mettre un char et passer au suivant. J'ai essayé une boucle sur value mais non plus :/
Pourquoi la ligne 21 ? On n'a pas changé les valeurs en x y.
> j'ai tout essayé
N'exagérons rien.
Disons que j'étais très fatigué hier. Fraichement levé après avoir mangé mes 3oeufs, je tente une nouvelle fois de comprendre pourquoi à la sortie de la fonction, rien est stocké dans map.
Donc toujours avec la raccourci et avec une map comme: '1H' donc h:1 | w: 2
start_from_digit va matcher avec la position: 0,0 car le '1' y est présent, algo sera donc appelé avec les params suivants:
algo(1, 0, 0, 1, 2, char map[][w]);
ny et nx auront pour valeur au:
1er tour: ny: 1 | nx: 0 y < h: faux
2e tour: ny: -1 | nx: 0 y >= 0: faux
3e tour: ny: 0 | nx: 1 vrai
4e tour: ny: 0 | nx: -1 faux
Le programme matchera donc que le 3e tour, quand ny vaut 0 et nx vaut 1
Et le soucis vient de là, il va écraser mon H pour mettre le symbol
Il le fait parce que le programmeur lui dit de le faire (ou ne l'en empéche pas, si on suggére qu'il aurait une volonté propre, une intention malfaisante carrément). Dire au susdit programmeur de mettre un test "si la case contient H, ...," ?
Dans ce qui est écrit plus haut (y compris mes oeuvres), j'ai l'impression qu'il y a des inversions entre w et h. Je renouvelle : r pour rows et v pour cols, ça évite de se prendre la tête. On a besoin de nos 3 neurones pour des choses plus sérieuses que de se rappeler que le premier c'est y qui correspond à h. Avec r et nbr...
Un bon début, ça serait de rédiger, en une phrase ou deux de bon français, ce que fait l'appel à la mal nommée fonction algo.
Ça serait du genre
La fonction xx xx (trouver_solution ?) reçoit en paramètre une carte de taille nbr x nbc et des coordonnées r et c, et un entier value qui indique je sais pas quoi
Elle cherche une solution
Si il y en a une, elle retourne vrai et la carte contient xx xx
Sinon, la carte revient dans son état d'origine
- Edité par michelbillaud 22 décembre 2023 à 9:01:04
Desole j'ai l'impression de me faire gronder par mon prof mais vraiment je crois que je suis à côté de la plaque..
michelbillaud a écrit:
> Il va écraser mon H
Il le fait parce que le programmeur lui dit de le faire (ou ne l'en empéche pas, si on suggére qu'il aurait une volonté propre, une intention malfaisante carrément). Dire au susdit programmeur de mettre un test "si la case contient H, ...," ?
Oui car je n'ai pas à le faire, si je rajoute H dans constraints, je ne pourrais jamais avoir ma condition de sortie(vrai)
Dans le cas de la map: 1H, il débute à partir de 1(y: 0|x: 0), donc si je vérifie que x + 1 != 'H' il va jamais rentrer et donc renvoyer faux.
Si c'est pas le cas merci de me le dire car j'ai l'impression de passer pour âne.
Je ne connaissais pas v et r comme mnémotechnique ; Chose que j'utilise maintenant.
La phrase serait:
La fonction algo certes mal nommée (j'ai pas d'inspiration), prend en paramètre une map de taille v x r , qui débute au coordonnées [y;x]qui a pour but de se déplacer à partir y et x jusqu'au 'trou' soit 'H' en vérifiant que counter != 0 et:
Toute balle doit finir dans un trou en au moins un coup.
Les flèches ne peuvent se croiser.
Les flèches ne peuvent croiser les positions ni des balles ni des trous.
Les flèches ne peuvent amener à un obstacle d'eau.
Les flèches ne peuvent amener à l'extérieur de la grille.
Aussi une chose que je n'ai pas mentionnée, la première fois que la bouge, elle doit bouger de counter cases, et ainsi de suite en décrémentant jusqu'à 0.
Cela donnerait un truc du genre:
for (int i = counter; i >= 0; i--)
{
for (int j = 0; j < i; i++)
{
// blabla ..
}
}
Mais ça complique énormément les choses, j'arrive pas à voir de la même manière que si je posais une case à la fois
Je dois reconnaitre que non seulement je ne comprends rien à l'énoncé du probléme, mais qu'en plus je n'ai pas envie de faire des efforts :-)
C'est pas v et r, mais r (pour row, rangée, ligne) et c pour col (onne)
> prof
Déformation professionnelle sans doute, mais je ne gronde personne. J'insiste beaucoup (lourdement) sur les problèmes de nommage, mais ils ne sont pas futiles. Techniquement ça ajoute une charge mentale, et comme on est souvent à la limite de nos capacités quand on programme, ça peut etre la paille qui casse le dos du chameau, comme disent les britanniques.
> ça complique les choses
Le remède à la complication est souvent d'introduire des abstractions qui s'occupent des détails. Genre écrire une fonction qui dit si tel coup est possible dans une situation donnée.
Donc ici, voir si' Il est possible d'avancer de n coups dans une direction (= les n cases sont vides)
- Edité par michelbillaud 22 décembre 2023 à 22:05:49
Déformation professionnelle sans doute, mais je ne gronde personne. J'insiste beaucoup (lourdement) sur les problèmes de nommage, mais ils ne sont pas futiles. Techniquement ça ajoute une charge mentale, et comme on est souvent à la limite de nos capacités quand on programme, ça peut etre la paille qui casse le dos du chameau, comme disent les britanniques.
Je doute pas que vous deviez être un excellent prof! Et je me plains par au contraire c'était une blague rien de sérieux. J'aime cet esprit plutôt.
michelbillaud a écrit:
> ça complique les choses
Le remède à la complication est souvent d'introduire des abstractions qui s'occupent des détails. Genre écrire une fonction qui dit si tel coup est possible dans une situation donnée.
Donc ici, voir si' Il est possible d'avancer de n coups dans une direction (= les n cases sont vides)
C'est exactement ce que j'ai fais avant de voir votre message, et ça a plutôt l'air de bien marcher mais maintenant je pense que c'est la condition de done()qui n'est pas bon
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h>
void print(int h, int w, const char map[][w])
{
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
if (map[i][j] == '>' || map[i][j] == '<'
|| map[i][j] == '^' || map[i][j] == 'v')
printf("%c", map[i][j]);
else
printf(".");
}
printf("\n");
}
}
bool constraints(int c)
{
return isdigit(c) || c == 'F' ||
c == '>' || c == '<' || c == '^' || c == 'v';
}
bool is_inside(int y, int x, int c, int r)
{
return y >= 0 &&
x >= 0 &&
y < c &&
x < r;
}
bool done(bool last_loop, int counter, char * const current_char)
{
if (*current_char == 'H')
{
*current_char = 'F';
return true;
}
if (counter == 0) {
if (last_loop && *current_char == 'X')
return false;
return !last_loop;
}
return false;
}
typedef struct s_infos
{
bool last_loop;
int remaining_hits;
int direction;
} t_infos;
bool up_down(t_infos info, int y, int x, int c, int r, char map[][r])
{
if (!is_inside(y, x, c, r))
return false;
if (done(info.last_loop, info.remaining_hits, & map[y][x]))
return true;
if (!constraints(map[y + info.direction][x]))
{
const char save_char = map[y][x];
map[y][x] = info.direction == 1 ? 'v' : '^';
info.remaining_hits--;
if (up_down(info, y + info.direction, x, c, r, map))
return true;
map[y][x] = save_char;
}
return false;
}
bool left_right(t_infos info, int y, int x, int c, int r, char map[][r])
{
if (!is_inside(y, x, c, r))
return false;
if (done(info.last_loop, info.remaining_hits, & map[y][x]))
return true;
if (!constraints(map[y][x + info.direction]))
{
const char save_char = map[y][x];
map[y][x] = info.direction == 1 ? '>' : '<';
info.remaining_hits--;
if (left_right(info, y, x + info.direction, c, r, map)) return true;
map[y][x] = save_char;
}
return false;
}
bool foo(int counter, int y, int x, int c, int r, char map[][r])
{
for (int count = counter; count > 0; count--)
{
t_infos info = { count == 1, count, +1 };
const char save_char = map[y][x];
if (y + count < c) {
info.direction = +1;
if (up_down(info, y, x, c, r, map)) {
y += count;
continue ;
}
map[y][x] = save_char;
}
if (y - count >= 0) {
info.direction = -1;
if (up_down(info, y, x, c, r, map)) {
y -= count;
continue ;
}
map[y][x] = save_char;
}
if (x + count < r) {
info.direction = +1;
if (left_right(info, y, x, c, r, map)) {
x += count;
continue ;
}
map[y][x] = save_char;
}
if (x - count >= 0) {
info.direction = -1;
if (left_right(info, y, x, c, r, map)) {
x -= count;
continue ;
}
map[y][x] = save_char;
}
}
return false;
}
void start_from_digit(int c, int r, char map[][r])
{
for (int y = 0; y < c; y++)
{
for (int x = 0; x < r; x++)
{
char current_char = map[y][x];
if (isdigit(current_char))
{
int value = current_char - '0';
foo(value, y, x, c, r, map);
}
}
}
}
il m'en résout quelque-uns comme:
1H
2.X
..H
.H1
4..XX
.H.H.
...H.
.2..2
.....
Mais avec lui par exemple, il prend les mauvaises décisions je sais pas où je faute :/
3..H.2
.2..H.
..H..H
.X.2.X
......
3..H..
- Edité par loictuchus 24 décembre 2023 à 12:17:59
Avec plusieurs balles, il se peut que le trajet trouvé pour une balle bloque les possibilités pour les suivantes. Dans ce cas il faut revenir sur les choix faits pour les balles précédentes
La fonction récursive ne porte donc pas seulement sur une balle, mais sur un ensemble de balles.
Si il n'y a plus de balles à loger : c'est gagné,
Sinon, pour chaque mouvement possible de la première balle
- si ça la mène dans un trou, hourra, résoudre récursivement pour le reste des balles
- sinon, résoudre récursivement avec la première balle déplacée
- Edité par michelbillaud 24 décembre 2023 à 9:08:32
Avec plusieurs balles, il se peut que le trajet trouvé pour une balle bloque les possibilités pour les suivantes.
C'est exactement ce qu'il se passe.
michelbillaud a écrit:
Dans ce cas il faut revenir sur les choix faits pour les balles précédentes
Yes mais je sais pas comment le faire, j'ai pas appris à le faire(parce-que ça enlève l'esprit créatif de tout avoir sur un plateau). Là c'est différent d'un sudoku ou d'un skycrapper, car à la différence d'eux, je devais simplement remplacer un digit s'il ne correspondait pas aux contraintes et c'était plutôt facile et cool à faire.
Là, si down() réussi et right() échoue, je dois effacer ce qu'à fait right() et revenir sur down() puis effacer petit à petit pour re essayer mais c'est justement là où je bloque, si une direction échoue après qu'une direction ait réussi. Le fait les fonctions up down right et left soient des fonctions à part entière c'est là où est la difficulté
michelbillaud a écrit:
- si ça la mène dans un trou, hourra, résoudre récursivement pour le reste des balles
" hourra " oui c'est exactement ce que je vais crier quand j'aurais enfin fini cette exo de malade!
- Edité par loictuchus 24 décembre 2023 à 12:12:10
Résoudre une grille
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
En recherche d'emploi.