Grille de nombres-croises

candide <candide@free.invalid> writes:

Sylvain Togni a écrit :

> 0 0 0 0
> 0 0 0 0
> 0 0 0 0
> 0 0 0 0
>

OK, la solution triviale

> 0 3 8 8
> 6 4 0 2
> 7 9 5 4
> 9 2 1 5
>
> 0 6 7 9
> 6 4 0 2
> 7 0 8 1
> 9 2 1 5
>

La dernière solution est amusante, on obtient une matrice symétrique.

> Mais quel rapport avec le C ?
>


Il s'agit de proposer du code C résolvant la question et de discuter de
ce code : respect de la norme, portabilité, variations possibles sur le
code, optimisations diverses, avantage à écrire ce code en C plutôt que
dans un autre langage, etc.

Bon, je vais donner l'exemple :



/* 97.c */

#include <stdio.h>

#define NB_CHIFFRES 4
#define BASE 10

void afficher(int t[NB_CHIFFRES][NB_CHIFFRES])
{
int lig, col;

for (lig = 0; lig < NB_CHIFFRES; lig++)
{
for (col = 0; col < NB_CHIFFRES; col++)
printf("%d", t[lig][col]);
printf("n");
}
printf("nn");
}

void chiffres(int *t, int x)
{
int i;
int q;

for (i = 0; i < NB_CHIFFRES; i++)
{
q = x / BASE;
t[NB_CHIFFRES - i - 1] = x - BASE * q;
x = q;
}
}

int solve(void)
{
#define N 97
#define BORNE 10*10*10

BORNE devrait etre 10000

int a, b, c, d;
int t[NB_CHIFFRES][NB_CHIFFRES];

for (a = 0; a < BORNE; a += N)
for (b = 0; b < BORNE; b += N)
for (c = 0; c < BORNE; c += N)
for (d = 0; d < BORNE; d += N)
{
int col = 0;

chiffres(&t[0][0], a);
if (t[0][0])
goto fin;

Tu peux sortir cela des boucles sur b, c et d

chiffres(&t[1][0], b);
if (t[1][2])
continue;

tu peux sortir cela des boucles sur c et d

chiffres(&t[2][0], c);

tu peux sortir cela de la boucle sur d

chiffres(&t[3][0], d);

while (!(t[3][col] + t[2][col] * 10 + t[1][col] * 100 +
t[0][col] * 1000 % N))

au moins deux problemes ici:
* %N doit se faire sur tout le calcul
* il faut aussi verifier que col n'a pas de depassement.

col++;
if (col == NB_CHIFFRES)
afficher(t);
}
fin:
return 0;
}

tu pourrais aller encore un peu plus vite en remarquant qu'il y a tres peu
de solutions pour c et d, donc travailler sur les colonnes apres les deux
premieres lignes (il y a au au minimum 1 et au maximum 2 solutions par
colonne) et verifier apres que les 2 dernieres lignes sont valides.

Le code qui suit fait cela, est plus generique mais plus long et moins
efficace qu'un code plus specialise. Il doit y avoir dedans une ou deux
techniques qui pourraient t'interesser (comme l'utilisation de la
recursivite pour avoir un nombre de boucles imbriquees variables).

#include <stdio.h>
#include <assert.h>

/* ---------------------------------------------------------------------------- */

#define NB_CHIFFRES 4

int validateline(int const* t, int line)
{
int result;

switch (line) {
case 0:
return t[0] == 0;
case 1:
return t[2] == 0;
default:
return 1;
}
}

/* ---------------------------------------------------------------------------- */

void show(int *t)
{
int i, j;

for (i = 0; i < NB_CHIFFRES; ++i) {
for (j = 0; j < NB_CHIFFRES; ++j) {
printf("%2d", t[i*NB_CHIFFRES+j]);
}
putchar('n');
}
putchar('n');
}

int generate(int* t, int stride, int fixed)
{
int sum, i;

for (i = 0; i < NB_CHIFFRES-1; ++i) {
assert(0 <= t[i*stride] && t[i*stride] < 10);
}
assert(-1 <= t[(NB_CHIFFRES-1) * stride] && t[(NB_CHIFFRES-1) * stride] < 10);

sum = 0;
for (i = 0; i < NB_CHIFFRES; ++i) {
sum = 10*sum + t[i*stride];
}
if (sum < 0) {
t[(NB_CHIFFRES-1)*stride] = 0;
return 1;
} else {
int newsum = ((sum / 97) + 1) * 97;

for (i = NB_CHIFFRES; i-- > fixed; ) {
t[i*stride] = newsum % 10;
newsum /= 10;
}
for (i++; i-- > 0;) {
if (t[i*stride] != newsum % 10) {
return 0;
}
newsum /= 10;
}
if (newsum == 0) {
return 1;
} else {
return 0;
}
}
}

int check(int const* t, int stride)
{
int sum, i;

for (i = 0; i < NB_CHIFFRES; ++i) {
assert(0 <= t[i*stride] && t[i*stride] < 10);
}

sum = 0;
for (i = 0; i < NB_CHIFFRES; ++i) {
sum = 10*sum + t[i*stride];
}

return sum % 97 == 0;
}

int clear(int* t, int stride, int fixed)
{
int sum, i;

for (i = fixed; i < NB_CHIFFRES-1; ++i) {
t[i*stride] = 0;
}
t[(NB_CHIFFRES-1) * stride] = -1;
}

void handlecol(int* t, int col)
{
if (col < NB_CHIFFRES) {
clear(t+col, NB_CHIFFRES, NB_CHIFFRES-2);
while (generate(t+col, NB_CHIFFRES, NB_CHIFFRES-2)) {
handlecol(t, col+1);
}
} else {
if (check(t + (NB_CHIFFRES-2) * NB_CHIFFRES, 1)
&& validateline(t + (NB_CHIFFRES-1) * NB_CHIFFRES, (NB_CHIFFRES-1))
&& check(t + (NB_CHIFFRES-1) * NB_CHIFFRES, 1)
&& validateline(t + (NB_CHIFFRES-2) * NB_CHIFFRES, (NB_CHIFFRES-2)))
{
show(t);
}
}
}

void handleline(int* t, int line)
{
if (line < NB_CHIFFRES-2) {
clear(t + line * NB_CHIFFRES, 1, 0);
while (generate(t + line * NB_CHIFFRES, 1, 0)) {
if (validateline(t + line * NB_CHIFFRES, line)) {
handleline(t, line+1);
}
}
} else {
handlecol(t, 0);
}
}

int main()
{
int t[NB_CHIFFRES*NB_CHIFFRES];

handleline(t, 0);

return 0;
}

--
Jean-Marc
FAQ de fclc: http://www.levenez.com/lang/c/faq
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Sylvain Togni <"sylvain.togni at visionobjects.com"> writes:

candide a écrit :

> Il marche pas : c'est-à-dire ? il compile pas ou t'as une erreur à
> l'exécution ?

Il ne trouve aucune solution.

Mais en remplaçant
#define BORNE 10*10*10
par
#define BORNE 10*10*10*10
et
while (!(t[3][col] + t[2][col] * 10 + t[1][col] * 100 +
t[0][col] * 1000 % N))
par
while (col < 4 && !((t[3][col] + t[2][col] * 10 + t[1][col] * 100 +
t[0][col] * 1000) % N))
il fonctionne et ne met que 0.5s.

Pourquoi diable n'ai-je pas vu tes reponses quand j'ai fait les miennes?

--
Jean-Marc
FAQ de fclc: http://www.levenez.com/lang/c/faq
Site de usenet-fr: http://www.usenet-fr.news.eu.org

"candide" <candide@free.invalid> a écrit dans le message de news:
491d68b5$0$1965$426a34cc@news.free.fr...

Sylvain Togni a écrit :

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

OK, la solution triviale

0 3 8 8
6 4 0 2
7 9 5 4
9 2 1 5

0 6 7 9
6 4 0 2
7 0 8 1
9 2 1 5

La dernière solution est amusante, on obtient une matrice symétrique.

Mais quel rapport avec le C ?

Il s'agit de proposer du code C résolvant la question et de discuter de
ce code : respect de la norme, portabilité, variations possibles sur le
code, optimisations diverses, avantage à écrire ce code en C plutôt que
dans un autre langage, etc.

Bon, je vais donner l'exemple :



/* 97.c */

#include <stdio.h>

#define NB_CHIFFRES 4
#define BASE 10

void afficher(int t[NB_CHIFFRES][NB_CHIFFRES])
{
int lig, col;

for (lig = 0; lig < NB_CHIFFRES; lig++)
{
for (col = 0; col < NB_CHIFFRES; col++)
printf("%d", t[lig][col]);
printf("n");
}
printf("nn");
}

void chiffres(int *t, int x)
{
int i;
int q;

for (i = 0; i < NB_CHIFFRES; i++)
{
q = x / BASE;
t[NB_CHIFFRES - i - 1] = x - BASE * q;
x = q;
}
}

int solve(void)
{
#define N 97
#define BORNE 10*10*10

non: #define BORNE (10*10*10*10)

int a, b, c, d;
int t[NB_CHIFFRES][NB_CHIFFRES];

for (a = 0; a < BORNE; a += N)
for (b = 0; b < BORNE; b += N)
for (c = 0; c < BORNE; c += N)
for (d = 0; d < BORNE; d += N)
{
int col = 0;

chiffres(&t[0][0], a);
if (t[0][0])
goto fin;
chiffres(&t[1][0], b);
if (t[1][2])
continue;
chiffres(&t[2][0], c);
chiffres(&t[3][0], d);

while (!(t[3][col] + t[2][col] * 10 + t[1][col] * 100 +
t[0][col] * 1000 % N))
col++;

Cette boucle est completement boguée : elle fait référence en dehors du
tableau et ne teste pas correctement le nombre. Il faudrait ecrire :

while (col < NB_CHIFFRES &&
!((t[3][col] + t[2][col] * 10 + t[1][col] * 100 +
t[0][col] * 1000) % N))
col++;

if (col == NB_CHIFFRES)
afficher(t);
}
fin:
return 0;
}

int main(void)
{
solve();

return 0;
}
/* Fin de 97.c */

$time ./x
0000
0000
0000
0000


0388
6402
7954
9215


0679
6402
7081
9215

real 0m6.411s
user 0m5.452s
sys 0m0.048s

Avec mes corrections, j'ai bien le bon resultat et un temps d'execution de
1.162s
Mais il ne sert a rien d'utiliser des tableaux et de laisser croire que
l'algorithme est generique si on change la valeur de NB_CHIFFRES... il
faudrait alors changer aussi le nombre de boucles for(;;) et le test des
colonnes.
Voici une implementation plus brutale:

#include <stdio.h>
#define N 97
int main(void) {
int a, b, c, d;
for (a = 0; a < 10000; a += N) {
if (a / 1000 % 10 != 0) continue; /* 0XXX */
for (b = 0; b < 10000; b += N) {
if (b / 10 % 10 != 0) continue; /* XX0X */
for (c = 0; c < 10000; c += N) {
for (d = 0; d < 10000; d += N) {
#define T(p) (a/p % 10 * 1000 + b/p % 10 * 100 + c/p % 10 * 10 + d/p % 10)
if (T(1) % N == 0 && T(10) % N == 0
&& T(100) % N == 0 && T(1000) % N == 0)
printf("%04dn%04dn%04dn%04dnn", a, b, c, d);
}
}
}
}
return 0;
}

$ time ./fsq97
0000
0000
0000
0000

0388
6402
7954
9215

0679
6402
7081
9215


real 0m0.241s
user 0m0.061s
sys 0m0.015s

même algorithme, mais implementation plus simple => 5 fois plus rapide.
on peut obtenir les 181 solutions generales en commentant les deux tests.

--
Chqrlie.

When in doubt, use brute force (Ken Thomson)

"Charlie Gordon" <news@chqrlie.org> a écrit dans le message de news:
gfl0al$qad$1@news.motzarella.org...

Avec mes corrections, j'ai bien le bon resultat et un temps d'execution de
$ time ./97

real 0m1.162s
user 0m1.000s
sys 0m0.000s

Version brutale:

$ time ./fsq97

real 0m0.241s
user 0m0.061s
sys 0m0.015s

même algorithme, mais implementation plus simple => 5 fois plus rapide.
on peut obtenir les 181 solutions generales en commentant les deux tests.

En fait, le calcul est 16 fois plus rapide, c'est l'affichage des résultats
sur la console qui prend les 3/4 du temps écoulé.

--
Chqrlie.

Jean-Marc Bourguet a écrit :

#define BORNE 10*10*10

BORNE devrait etre 10000

Oui, mon intention était de remplacer 10000 par 10*10*10*10 pour voir si
ça ralentissait l'exécution.

Tu peux sortir cela des boucles sur b, c et d
(...)
tu peux sortir cela des boucles sur c et d

chiffres(&t[2][0], c);

tu peux sortir cela de la boucle sur d

Très bien vu, car comme placé dans mon code, ces instructions
entraînaient des recalculs ENORMES, et en plus je peux remplacer le goto
par un break, le code devient clc-valide ;)
Le résultat à l'exécution est _impressionnant_ :
ça tombe de 5.6 s à 0.45 s !!

au moins deux problemes ici:
* %N doit se faire sur tout le calcul

Pas compris, de quel calcul tu parles ?

* il faut aussi verifier que col n'a pas de depassement.

Ah oui, tu as raison, mon code est incorrect ici, j'ai juste eu de la
chance !!




Ci-dessous le code modifié :

/*-----------------------------------------------------------------*/
#include <stdio.h>

#define NB_CHIFFRES 4

void afficher(int t[NB_CHIFFRES][NB_CHIFFRES])
{
int lig, col;

for (lig = 0; lig < NB_CHIFFRES; lig++)
{
for (col = 0; col < NB_CHIFFRES; col++)
printf("%d", t[lig][col]);
printf("n");
}
printf("nn");
}


void chiffres(int *t, int x)
{
int i;
int q, d = 10;

for (i = 0; i < NB_CHIFFRES; i++)
{
q = x / d;
t[NB_CHIFFRES - i - 1] = x - d * q;
x = q;
}
}

int solve(void)
{
#define N 97
#define BORNE 10000
int a, b, c, d;
int t[4][4];

for (a = 0; a < BORNE; a += N)
{
chiffres(&t[0][0], a);
if (t[0][0])
break;
for (b = 0; b < BORNE; b += N)
{
chiffres(&t[1][0], b);
if (t[1][2])
continue;
for (c = 0; c < BORNE; c += N)
{
chiffres(&t[2][0], c);
for (d = 0; d < BORNE; d += N)
{
int col = 0;

chiffres(&t[3][0], d);

while (col < 4
&& (t[3][col] + t[2][col] * 10 + t[1][col] * 100 +
t[0][col] * 1000) % N == 0)
col++;
if (col == 4)
afficher(t);
}
}
}
}
return 0;
}

int test(void)
{
int tt[4];
int i;

chiffres(tt, 2009);

for (i = 0; i < 4; i++)
printf("%d", tt[i]);


return 0;
}

int main(void)
{
solve();

return 0;
}
/*-----------------------------------------------------------------*/

tu pourrais aller encore un peu plus vite en remarquant qu'il y a tres peu
de solutions pour c et d, donc travailler sur les colonnes apres les deux
premieres lignes (il y a au au minimum 1 et au maximum 2 solutions par
colonne) et verifier apres que les 2 dernieres lignes sont valides.

Oui, d'accord, c'est ce que j'aurais fait si l'exécution avait été
longue mais je trouve ça ch**** à écrire. C'est ce genre de technique
qu'on utilise (parmi d'autres possibles je suppose) pour engendrer tous
les carrés magiques d'ordre 4.

(...) Il doit y avoir dedans une ou deux
techniques qui pourraient t'interesser (comme l'utilisation de la
recursivite pour avoir un nombre de boucles imbriquees variables).

Oui, j'avais déjà pratiqué ce genre de choses mais je n'ai jamais réussi
à donner de réponses générales à ce problème des boucles imbriquées de
profondeur variable, c'est toujours au cas par cas et assez prise de
tête à écrire (pour moi en tout cas).


Surtout ce que je note dans ton code, ce sont les points suivants
(signalés dans le désordre) :

*) emploi de puts au lieu de printf (vitesse d'exécution ? moins de
lettres à écrire dans le code !!?)
*) emploi d'un tableau unidimesionnel et un stride plutôt que qu'un
tableau 2D (jamais vu utiliser ce terme de stride)
*) for (i = a; i-- > b; ) : j'avais jamais vu une expression de contrôle
d'un boucle for qui avait cette tête
*) je trouve que la multiplicité des assert nuisent à la lisibilité
(normal je n'ai pas l'habitude de les utiliser)

Charlie Gordon a écrit :

Cette boucle est completement boguée :

Tout à fait, j'en ai pris conscience en lisant le message de jmb, je ne
sais pas comment j'ai laissé passé une chose pareille.

Avec mes corrections, j'ai bien le bon resultat et un temps d'execution de
1.162s
Mais il ne sert a rien d'utiliser des tableaux et de laisser croire que
l'algorithme est generique si on change la valeur de NB_CHIFFRES... il
faudrait alors changer aussi le nombre de boucles for(;;) et le test des
colonnes.

Tout à fait mais c'était un premier jet.

Voici une implementation plus brutale:

#include <stdio.h>
#define N 97
int main(void) {
int a, b, c, d;
for (a = 0; a < 10000; a += N) {
if (a / 1000 % 10 != 0) continue; /* 0XXX */
for (b = 0; b < 10000; b += N) {
if (b / 10 % 10 != 0) continue; /* XX0X */
for (c = 0; c < 10000; c += N) {
for (d = 0; d < 10000; d += N) {
#define T(p) (a/p % 10 * 1000 + b/p % 10 * 100 + c/p % 10 * 10 + d/p % 10)
if (T(1) % N == 0 && T(10) % N == 0
&& T(100) % N == 0 && T(1000) % N == 0)
printf("%04dn%04dn%04dn%04dnn", a, b, c, d);
}
}
}
}
return 0;
}

$ time ./fsq97
0000
0000
0000
0000

0388
6402
7954
9215

0679
6402
7081
9215


real 0m0.241s
user 0m0.061s
sys 0m0.015s

Oui, joli car court et efficace.

candide <candide@free.invalid> writes:

au moins deux problemes ici:
* %N doit se faire sur tout le calcul

Pas compris, de quel calcul tu parles ?

Dans

while (!(t[3][col] + t[2][col] * 10 + t[1][col] * 100 + t[0][col] * 1000 % N))

Le % N ne s'applique pas à la même chose que dans ta version corrigée:

while (col < 4
&& (t[3][col] + t[2][col] * 10 + t[1][col] * 100 +
t[0][col] * 1000) % N == 0)

En passant, tu utilises parfois 4, parfois NB_CHIFFRES. C'est à mon avis
pire que d'utiliser tout le temps 4 car quand on voudra changer, ça ne
fonctionnera pas correctement et on ne pensera pas de suite à ce genre de
problème.

Surtout ce que je note dans ton code, ce sont les points suivants
(signalés dans le désordre) :

*) emploi de puts au lieu de printf (vitesse d'exécution ? moins de
lettres à écrire dans le code !!?)

J'ai pas utilisé puts() mais putchar, et plus parce que ça correspond à ce
que je fais -- écrire un caractère et pas tenter de formater qqch -- que
pour une autre raison.

*) emploi d'un tableau unidimesionnel et un stride plutôt que qu'un
tableau 2D (jamais vu utiliser ce terme de stride)
*) for (i = a; i-- > b; ) : j'avais jamais vu une expression de contrôle
d'un boucle for qui avait cette tête

C'est pourtant le parfait symétrique de

for (i = b; i < a; ++i)

*) je trouve que la multiplicité des assert nuisent à la lisibilité
(normal je n'ai pas l'habitude de les utiliser)

C'est un moyen de commenter certains aspects de la conception (ici, en
particulier le jeu avec le -1 qui est parfois valide parfois pas).

A+

--
Jean-Marc
FAQ de fclc: http://www.levenez.com/lang/c/faq
Site de usenet-fr: http://www.usenet-fr.news.eu.org

In article <491e1326$0$32083$426a74cc@news.free.fr>,
candide <candide@free.invalid> wrote:

*) emploi d'un tableau unidimesionnel et un stride plutôt que qu'un
tableau 2D (jamais vu utiliser ce terme de stride)

C'est employe de facon systematique pour les algo un peu intelligents
sur matrices creuses, en particulier dans la description de valarray dans
la bibliotheque standard C++.

Si tu connais un peu Tolkien, Aragorn est appele Grand Pas, ce qui est la
traduction a peu pres fidele de Strider dans la VO.

On 14 nov, 00:09, candide <cand...@free.invalid> wrote:

Tous les prétextes sont bons pour faire du C : compléter la grille 4x 4
ci-dessous par des chiffres décimaux (deux zéros sont déjà plac és) en
sorte que tous les nombres de 4 chiffres (lus de la gauche vers la
droite ou de haut en bas) qui apparaissent soient des multiples de 97 :

0XXX
XX0X
XXXX
XXXX

Il n'y a pas que la solution triviale. Bon amusement.

Hors-sujet. C'est un problème d'algo. La réponse ne dépend pas du
langage.

On 15 nov, 01:09, candide <cand...@free.invalid> wrote:

Jean-Marc Bourguet a écrit :

>> #define BORNE 10*10*10
> BORNE devrait etre 10000

Oui, mon intention était de remplacer 10000 par 10*10*10*10 pour voir s i
ça ralentissait l'exécution.

Alors c'est

#define BORNE (10*10*10)

sinon le comportement dépend de l'utilisation.

Mais c'est strictement équivallent à 1000, car une expression
constante est évaluée par le compilateur.

de même

#define BORNE (10*10*10*10)

vaut 10000

Aucune différence de codage.