Petit jeujeu mathématique deviendra gros casse-tête
+6
Petitagore
Pieyre
loulou38
Professeur Megamiaou
Stauk
Ardel
10 participants
Page 5 sur 6
Page 5 sur 6 • 1, 2, 3, 4, 5, 6
Re: Petit jeujeu mathématique deviendra gros casse-tête
Oui, je suis certain que j'ai trouvé le minimum. Ce n'est pas par une méthode statistique, c'est déterministe. Au mieux on pourra les trouver plus rapidement (c'est meme sur, d'ailleurs je cherche encore à optimiser mon algo), mais c'est tout, il est impossible de les compléter en moins de coups. Par contre je pense qu'avec un peu de gymnastique je pourrai en faire une IA imbattable (ou match nul).
Quant à les numéroter, c'est nécessaire pour que mon algo puisse bouffer les paramètres d'entrée... peu importe la numération, mon algo sortira quand meme un minimum.
Quant à les numéroter, c'est nécessaire pour que mon algo puisse bouffer les paramètres d'entrée... peu importe la numération, mon algo sortira quand meme un minimum.
Invité- Invité
Re: Petit jeujeu mathématique deviendra gros casse-tête
hobb a écrit:Oui, je suis certain que j'ai trouvé le minimum. Ce n'est pas par une méthode statistique, c'est déterministe.
Ah, tu as donc planché sur un algorithme, OK.
Pourrais-tu envisager d'en faire un logiciel libre? (oui, cette question est bassement intéressée) Et si la réponse est positive (autrement, je m'en fous ), tu as écrit ça en quel langage?
Quant à les numéroter, c'est nécessaire pour que mon algo puisse bouffer les paramètres d'entrée... peu importe la numération, mon algo sortira quand meme un minimum.
Bien sûr. Mais tant qu'à faire, tu aurais pu prendre en paramètres d'entrée les fichiers XML exploités par mes listings Javascript, dans ce genre-là. C'est peut-être ce que tu as fait, d'ailleurs, mais alors je m'étonne que tu n'en aies pas profité pour récupérer la numérotation (balise "alias").
Re: Petit jeujeu mathématique deviendra gros casse-tête
J'ai fais ça en fortran. Pour en faire un logiciel libre, why not, au pire je peux te passer les bibliothèques précompilées gratis sinon (parce que si ça a prit autant d'ampleur ça a peut etre moyen de finir en publi, auquel as il ne faut pas que je le mette en public avant qu'il ne parte en referee).
Non pour la numérotation je n'avais pas envie de m'emm****** à décrypter du xml avec du fortran (qui n'est quand meme pas super adapté pour bidouiller du texte tu en conviendras), donc en entrée je n'entre que les les 3 liens de chaque triangle avec les autres, il s'occupe du reste.
Non pour la numérotation je n'avais pas envie de m'emm****** à décrypter du xml avec du fortran (qui n'est quand meme pas super adapté pour bidouiller du texte tu en conviendras), donc en entrée je n'entre que les les 3 liens de chaque triangle avec les autres, il s'occupe du reste.
Invité- Invité
Re: Petit jeujeu mathématique deviendra gros casse-tête
Et puis très honnetement, le code est vraiment compliqué (serieusement)... Je veux bien t'expliquer l'algorithme mais sur le net ça serait vraiment trop long...
Invité- Invité
Re: Petit jeujeu mathématique deviendra gros casse-tête
Je viens de regarder, tu es sur de mettre le code à dispo de tout le monde ça ne risque pas de pourrir les jeux du meme type dispos sur le net ? C'est toi qui l'a inventé ?
Invité- Invité
Re: Petit jeujeu mathématique deviendra gros casse-tête
Merci, je vais essayer de comprendre au moins la démarche générale.
Re: Petit jeujeu mathématique deviendra gros casse-tête
En fait le but est de faire de la remontée d'échelle de la taille des polygones. On sait que pour poser un triangle, il faut un coup.
Après, tu détermines TOUS les polygones possibles (triangles ajoutés), et tu les tries par taille.
Pour chaque couple de polygones, tu cherches quel autre polygone ça donne. Le nombre de coup pour obtenir ce polygone est donc la somme des coups nécessaires pour avoir ceux d'en dessous. A chaque fois que tu fais le lien, tu regarde si le cumul est pas plus petit. Ca pour chercher le minimum.
Ensuite tu fais une recherche inverse : tu pars tu polygone le plus grand (tout rempli quoi), et tu remontes aux 2 polygones qui ont nécessités le moins de coup pour donner celui-là par récursion, et tu trouves la dispositions des triangles nécessaires pour l'obtenir.
Ca c'est dans les grandes lignes, ça va de soi que les préallocations / quicksort / recherches dichtomiques etc sont nécessaires pour optimiser la vitesse, tu manipule quand meme des millions de polygones potentiels...
Tiens, voilà le code, si tu veux en faire une IA j'ai une idée de comment il faut faire (en jouant sur la parité du nombre d'action nécessaire pour chaque polygone) :
D'ailleurs ce qui est marrant, vu que je pars de l'espace dual, c'est que je peux faire n'importe quelle topologie (Klein, tore, sphere, etc...)
Après, tu détermines TOUS les polygones possibles (triangles ajoutés), et tu les tries par taille.
Pour chaque couple de polygones, tu cherches quel autre polygone ça donne. Le nombre de coup pour obtenir ce polygone est donc la somme des coups nécessaires pour avoir ceux d'en dessous. A chaque fois que tu fais le lien, tu regarde si le cumul est pas plus petit. Ca pour chercher le minimum.
Ensuite tu fais une recherche inverse : tu pars tu polygone le plus grand (tout rempli quoi), et tu remontes aux 2 polygones qui ont nécessités le moins de coup pour donner celui-là par récursion, et tu trouves la dispositions des triangles nécessaires pour l'obtenir.
Ca c'est dans les grandes lignes, ça va de soi que les préallocations / quicksort / recherches dichtomiques etc sont nécessaires pour optimiser la vitesse, tu manipule quand meme des millions de polygones potentiels...
Tiens, voilà le code, si tu veux en faire une IA j'ai une idée de comment il faut faire (en jouant sur la parité du nombre d'action nécessaire pour chaque polygone) :
- Code:
program temp2
!!! By HObb / ZC forum
implicit none
type polygon
integer(2) :: nb_tri
integer(2), allocatable, dimension(:) :: tri
end type
type polygon_finaux
integer(2) :: nb_tri
integer(2), allocatable, dimension(:) :: tri
integer, dimension(2) :: min_from, max_from
integer(2) :: cumul_min, cumul_max
end type
integer, allocatable, dimension(:) :: borne_inf, borne_sup
type(polygon), dimension(:), allocatable :: polygones
type(polygon_finaux), dimension(:), allocatable :: polygones_finaux
integer(2), dimension(:,:), allocatable :: reduced_polygons, reduced_polygons_sorted
integer, allocatable, dimension(:,:) :: liens
logical, dimension(:), allocatable :: powered
integer :: taille_loc, nbpoly=0,iloc,jloc,kloc,lloc,nblink, nbpoly_tmp = 0, nbpoly_fin = 0
integer :: debut, fin, med !! pour la dichotomie
integer :: min_act, max_act
logical :: finished
character(30) :: filename
call getarg(1,filename)
allocate(polygones(10000000))
allocate(polygones_finaux(10000000))
open (file=filename, unit=10)
read(10,*) nblink
allocate(liens(nblink,3),powered(nblink))
allocate(borne_inf(nblink), borne_sup(nblink))
do iloc = 1, nblink
read(10,*) kloc, liens(iloc,:)
write(*,*) 'link n°',iloc, ' : ' , liens(iloc,:)
liens(iloc,:) = liens(iloc,:) + 1
enddo
close(10)
!!! CHECK LINKS
do iloc = 1, nblink
do jloc = 1, 3
kloc = liens(iloc,jloc)
finished = .false.
do lloc = 1, 3
if (liens(kloc,lloc)==iloc) finished = .true.
enddo
if (.not.finished) then
write(*,*) 'ERROR LINK ', ILOC, ': linking to un-reverse ', KLOC
stop
endif
enddo
enddo
do taille_loc = 1,nblink ! compute all polygons ! -> 44
do iloc = 1, nblink
powered = .true.
powered(iloc) = .false.
call expand_poly(powered,iloc,taille_loc)
enddo
write(*,*) 'computing polygons of size : ', taille_loc, '->', nbpoly - nbpoly_tmp, 'total : ', nbpoly
write(13,*) taille_loc, nbpoly - nbpoly_tmp, nbpoly
nbpoly_tmp = nbpoly
enddo
write(*,*) 'now, detecting twins polygons...'
!!! now reduce the twins polygones !!!
write(*,*) '-> sort each triangle number in each polygon'
do taille_loc = 1,nblink ! compute all polygons size
allocate(reduced_polygons(10000000,taille_loc),reduced_polygons_sorted(10000000,taille_loc))
kloc = 0
do iloc = 1, nbpoly
if (polygones(iloc)%nb_tri == taille_loc) then
kloc = kloc + 1
reduced_polygons(kloc,:) = polygones(iloc)%tri(:)
call QsortC1D(taille_loc,reduced_polygons(kloc,:))
endif
enddo
write(*,*) '-> sort ', kloc,'polygons'
! reduced_polygon now contains all polygons of size 'taille_loc', sorted by increased tri number
! now, sorting by tri numbers, to detect duplicates polygons
call QsortC2D(kloc,taille_loc,reduced_polygons(1:kloc,:))
! copying, ignoring twins
write(*,*) '-> delete duplicated polygons'
if (kloc > 0) then
kloc = 0
borne_inf(taille_loc) = nbpoly_fin + 1
nbpoly_fin = nbpoly_fin + 1
kloc = kloc + 1
allocate(polygones_finaux(nbpoly_fin)%tri(taille_loc))
polygones_finaux(nbpoly_fin)%nb_tri = taille_loc
polygones_finaux(nbpoly_fin)%tri(:) = reduced_polygons(1,:)
polygones_finaux(nbpoly_fin)%cumul_min = nblink
polygones_finaux(nbpoly_fin)%cumul_max = 0
reduced_polygons_sorted(kloc,:) = reduced_polygons(1,:)
do iloc = 1, nbpoly
if (any(reduced_polygons(iloc,:) /= reduced_polygons_sorted(kloc,:)).and.any(reduced_polygons(iloc,:)/=0)) then
nbpoly_fin = nbpoly_fin + 1
kloc = kloc + 1
allocate(polygones_finaux(nbpoly_fin)%tri(taille_loc))
reduced_polygons_sorted(kloc,:) = reduced_polygons(iloc,:)
polygones_finaux(nbpoly_fin)%nb_tri = taille_loc
polygones_finaux(nbpoly_fin)%tri(:) = reduced_polygons(iloc,:)
polygones_finaux(nbpoly_fin)%cumul_min = nblink ! for the min research after
polygones_finaux(nbpoly_fin)%cumul_max = 0 ! for the max research after
endif
enddo
borne_sup(taille_loc) = nbpoly_fin
endif
! reduced_polygons_sorted now contains kloc un-duplicated polygons of size taille_loc
write(*,*) ' -> reduced : ', kloc
write(*,'(A,I8,A,I6,A,I6,A)') 'total polygons : ', nbpoly_fin, '(',borne_inf(taille_loc),',', borne_sup(taille_loc),')'
deallocate(reduced_polygons,reduced_polygons_sorted)
enddo
! !!!!!!!!!! OK, now we have all the unique polygone in polygones_finaux -> writing it in a file
! open(file = 'polygons.dat', unit=20)
! do iloc = 1, nblink
! write(20,*) iloc
! write(20,*) borne_inf(iloc),borne_sup(iloc)
! do jloc = borne_inf(iloc),borne_sup(iloc)
! write(20,*) polygones_finaux(jloc)%nb_tri
! write(20,*) polygones_finaux(jloc)%tri(:)
! write(20,*) polygones_finaux(jloc)%cumul_min
! write(20,*) polygones_finaux(jloc)%cumul_max
! write(20,*) polygones_finaux(jloc)%min_from(:)
! write(20,*) polygones_finaux(jloc)%max_from(:)
! enddo
! enddo
! close(20)
!!!!!!!!!! on action by polygone = triangle, after all the combinaisons are upgraded
do iloc = borne_inf(1), borne_sup(1)
polygones_finaux(iloc)%min_from = 0
polygones_finaux(iloc)%max_from = 0
polygones_finaux(iloc)%cumul_min = 1
polygones_finaux(iloc)%cumul_max = 1
enddo
! now, ALL the combinaisons
allocate(reduced_polygons(1,nblink))
do iloc = 1, nbpoly_fin - 1
write(*,*) 100.*real(iloc)/real(nbpoly_fin), '%'
do jloc = iloc + 1, nbpoly_fin
! if any common triangle : ignore
if (.not.common_tri(polygones_finaux(iloc)%nb_tri,polygones_finaux(jloc)%nb_tri, &
polygones_finaux(iloc)%tri(:),polygones_finaux(jloc)%tri(:))) then
powered = .true.
do kloc = 1, polygones_finaux(iloc)%nb_tri
powered(polygones_finaux(iloc)%tri(kloc)) = .false.
enddo
do kloc = 1, polygones_finaux(jloc)%nb_tri
powered(polygones_finaux(jloc)%tri(kloc)) = .false.
enddo
! reducing the developpment of the two polygons
finished = .false.
do while (.not.finished)
finished = .true.
do kloc = 1, nblink
if ((count(.not.powered(liens(kloc,:)))>=2).and.powered(kloc)) then
powered(kloc) = .false.
finished = .false.
endif
enddo
enddo
taille_loc = 0
do kloc = 1, nblink
if (.not.powered(kloc)) then
taille_loc = taille_loc + 1
reduced_polygons(1,taille_loc) = kloc
endif
enddo
call QsortC1D(taille_loc,reduced_polygons(1,:taille_loc))
! research the present polygon obtained (with dichotomy)
debut = borne_inf(taille_loc)
fin = borne_sup(taille_loc)
lloc = 1
do while (lloc /= 0)
if (med /= (debut + fin) / 2) then
med = (debut + fin) / 2
lloc = compare(taille_loc,reduced_polygons(1,:taille_loc),polygones_finaux(med)%tri(:taille_loc))
if (lloc > 0) then ! ce qu'on cherche est au dessus de la médiane
debut = med
elseif(lloc < 0) then ! sinon en dessous
fin = med
endif
else
lloc = 0!!!! SI on ne trouve pas, c'est que le cumul des 2 polygones donne 2 polygones distincts, osef pour le cumul donc
endif
enddo
! update min an max if necessary
!!!! WARNING : for the max, better algorithm to find : it's false.
if (all(reduced_polygons(1,:taille_loc)==polygones_finaux(med)%tri(:taille_loc))) then
min_act = polygones_finaux(iloc)%cumul_min + polygones_finaux(jloc)%cumul_min
max_act = polygones_finaux(iloc)%cumul_max + polygones_finaux(jloc)%cumul_max
if (polygones_finaux(med)%cumul_min >= min_act) then
polygones_finaux(med)%min_from(:) = (/iloc,jloc/)
polygones_finaux(med)%cumul_min = min_act
endif
if (polygones_finaux(med)%cumul_max <= max_act) then
polygones_finaux(med)%max_from(:) = (/iloc,jloc/)
polygones_finaux(med)%cumul_max = max_act
endif
endif
endif
enddo
enddo
deallocate(reduced_polygons)
! do kloc = 1, nbpoly_fin
!
! write(*,*) polygones_finaux(kloc)%tri
! enddo
! stop
!
! write(*,*) '============= MIN ============'
! write(*,*) nbpoly_fin
! ! write(*,*) polygones_finaux(nbpoly_fin)%nb_tri
! ! write(*,*) polygones_finaux(nbpoly_fin)%tri
! ! write(*,*) polygones_finaux(nbpoly_fin)%cumul_min
! write(*,*) polygones_finaux(nbpoly_fin)%cumul_max
! write(*,*) polygones_finaux(nbpoly_fin)%max_from
! iloc = polygones_finaux(nbpoly_fin)%min_from(1)
! jloc = polygones_finaux(nbpoly_fin)%min_from(2)
!
! write(*,*) polygones_finaux(iloc)%tri
! write(*,*) polygones_finaux(jloc)%tri
!
!
! stop
write(*,*) (polygones_finaux(nbpoly_fin)%cumul_min), 'actions'
call affichage_min(nbpoly_fin) ! recursive search of minimal action and display
! write(*,*) '============= MAX ============'
! write(*,*) (polygones_finaux(nbpoly_fin)%cumul_max), 'actions'
! call affichage_max(nbpoly_fin) ! recursive search of minimal action and display
contains
recursive subroutine expand_poly(power,begin,taille)
logical, dimension(nblink), intent(inout) :: power
integer, intent(in) :: begin
logical, dimension(nblink) :: power2
logical :: finished
integer :: i, j, k, taille, taille2
if (taille==1) then ! taille=1 : récursivement c'est la fin (pas 0, va savoir)
nbpoly = nbpoly + 1
allocate(polygones(nbpoly)%tri(count(.not.power)))
polygones(nbpoly)%nb_tri = count(.not.power)
k = 0
do j = 1, nblink
if (.not.power(j)) then
k = k + 1
polygones(nbpoly)%tri(k)=j
endif
enddo
else
do j = 1, 3 ! for all link centered on the begin'th triangle
if (power(liens(begin,j))) then
power2 = power
power2(liens(begin,j)) = .false.
taille2 = taille - 1
! reducing
finished = .false.
do while (.not.finished)
finished = .true.
do i = 1, nblink
if ((count(.not.power2(liens(i,:)))>=2).and.power2(i)) then
power2(i) = .false.
taille2 = taille2 - 1
finished = .false.
endif
enddo
enddo
call expand_poly(power2,liens(begin,j),taille2)
endif
enddo
endif
end subroutine
!!!!!!!!!!!!!!!!!! QUICKSORT ALGO !!!!!!!!!!!!!!!!! -> 2D & 1D
recursive subroutine slow_sort(taille,nbpol,debut,fin,indexa,A)
integer, intent(in) :: nbpol,taille,debut,fin,indexa
integer(2), intent(inout), dimension(taille,nbpol) :: A
integer(2) :: temp
integer :: i,j,k, minlocation,nb
if ((debut < fin).and.(indexa<=nbpol)) then
do i = debut,fin-1
minlocation = i
do j = i+1, fin
if (A(j,indexa)<A(minlocation,indexa)) minlocation = j
enddo
! exchange A(i) and A(minlocation)
do k = 1, nbpol
temp = A(i,k)
A(i,k) = A(minlocation,k)
A(minlocation,k) = temp
enddo
enddo
j = 1
nb = 0
do while(j+nb<=taille)
do while((all(A(j,1:indexa)==A(j+nb,1:indexa)).and.(j+nb<=taille)))
nb = nb + 1
enddo
nb = nb - 1
call slow_sort(taille,nbpol,j,j+nb,indexa+1,A)
j = j + nb + 1
nb = 0
enddo
endif
end subroutine
recursive subroutine QsortC2D(taille,nbpol,A)
integer :: nbpol,taille
integer(2), intent(in out), dimension(taille,nbpol) :: A
integer :: iq
if(taille > 1) then
call Partition2D(taille, nbpol, iq, A)
call QsortC2D(iq-1,nbpol,A(:iq-1,:))
call QsortC2D(taille-iq+1,nbpol,A(iq:,:))
endif
end subroutine QsortC2D
recursive subroutine QsortC1D(nbpol,A)
integer :: nbpol
integer(2), intent(in out), dimension(nbpol) :: A
integer :: iq
if(nbpol > 1) then
call Partition1D(nbpol, iq, A)
call QsortC1D(iq-1,A(:iq-1))
call QsortC1D(nbpol-iq+1,A(iq:))
endif
end subroutine QsortC1D
subroutine Partition2D(taille,nbpol,marker,A)
integer :: i, j, k
integer, intent(in) :: nbpol, taille
integer(2), intent(inout), dimension(taille,nbpol) :: A
integer, intent(out) :: marker
! integer(2), dimension(nbpol) :: x, temp ! pivot point
integer(2) :: temp
! x = A(1,:)
i= 0
j= taille + 1
do
j = j-1
do
if (compare(nbpol,A(j,:),A(1,:)) <= 0) exit
j = j-1
end do
i = i+1
do
if (compare(nbpol,A(i,:),A(1,:)) >= 0) exit
i = i+1
end do
if (i < j) then
! exchange A(i) and A(j)
do k = 1, nbpol
temp = A(i,k)
A(i,k) = A(j,k)
A(j,k) = temp
enddo
elseif (i == j) then
marker = i+1
return
else
marker = i
return
endif
end do
end subroutine Partition2D
subroutine Partition1D(nbpol,marker,A)
integer :: i, j, nbpol
integer(2), intent(in out), dimension(nbpol) :: A
integer, intent(out) :: marker
integer(2) :: x, temp ! pivot point
x = A(1)
i= 0
j= nbpol + 1
do
j = j-1
do
if (A(j)<=x) exit
j = j-1
end do
i = i+1
do
if (A(i)>=x) exit
i = i+1
end do
if (i < j) then
! exchange A(i) and A(j)
temp = A(i)
A(i) = A(j)
A(j) = temp
elseif (i == j) then
marker = i+1
return
else
marker = i
return
endif
end do
end subroutine Partition1D
integer function compare(n,A,B) ! return -1 if A<B, 0 if = and 1 if >
integer :: i
integer, intent(in) :: n
integer(2), dimension(n), intent(in) :: A,B
i = 1
do while((A(i)==B(i)).and.i<n)
i = i + 1
enddo
if (A(i)<B(i)) then
compare = -1
elseif (A(i)>B(i)) then
compare = 1
else
compare = 0
endif
end function
logical function common_tri(N1, N2, T1, T2)
integer(2), intent(in) :: N1,N2
integer(2), dimension(N1) :: T1
integer(2), dimension(N2) :: T2
integer :: i, j
common_tri = .false.
do i = 1, N1
do j = 1, N2
if (T1(i) == T2(j)) then
common_tri = .true.
return
endif
enddo
enddo
end function
recursive subroutine affichage_min(number)
integer, intent(in) :: number
if (polygones_finaux(number)%cumul_min /= 1) then
call affichage_min(polygones_finaux(number)%min_from(1))
call affichage_min(polygones_finaux(number)%min_from(2))
else
write(*,*) polygones_finaux(number)%tri(1) - 1
endif
end subroutine
recursive subroutine affichage_max(number)
integer, intent(in) :: number
if (polygones_finaux(number)%cumul_max /= 1) then
call affichage_max(polygones_finaux(number)%max_from(1))
call affichage_max(polygones_finaux(number)%max_from(2))
else
write(*,*) polygones_finaux(number)%tri(1) - 1
endif
end subroutine
end program
D'ailleurs ce qui est marrant, vu que je pars de l'espace dual, c'est que je peux faire n'importe quelle topologie (Klein, tore, sphere, etc...)
Invité- Invité
Re: Petit jeujeu mathématique deviendra gros casse-tête
hobb a écrit:C'est toi qui l'a inventé ?
Je veux, mon neveu!
Re: Petit jeujeu mathématique deviendra gros casse-tête
hobb a écrit:Ca c'est dans les grandes lignes, ça va de soi que les préallocations / quicksort / recherches dichtomiques etc sont nécessaires pour optimiser la vitesse, tu manipule quand meme des millions de polygones potentiels...
J'ai très peu fait de Fortran dans ma longue carrière, donc il me serait sans doute plus simple d'essayer d'imiter ta démarche dans un langage que je domine plutôt que d'essayer de comprendre ton listing...
Je suis assez tenté d'employer pour résoudre ton problème (prise de toute la grille avec un minimum de coups) la même méthode quick and dirty que j'ai utilisée pour résoudre le mien (prise d'un maximum de cases de la grille trois par trois): définir une démarche générale dans un langage facile à écrire (Python), noter les résultats intermédiaires dans des fichiers de texte de taille titanesque (pour mon problème, ça se compte parfois en méga-octets), les trier avec l'utilitaire Unix sort (ééénorme avantage: je n'ai aucun besoin de le déboguer), puis les écrémer à mort, de nouveau en Python (je garde 0,5 % des meilleurs résultats, je jette les méga-octets restants): c'est ignominieusement inélégant, mais ça marche et ça ne prend pas des plombes à écrire, ni même à exécuter (il faut quelques dizaines de secondes pour atteindre le résultat qu'un algorithme optimisé pourrait sans doute atteindre en une fraction de seconde... mais je m'en fous du moment que ça va déjà des millions de fois plus vite que ce que pourrait faire mon vrai cerveau en barbaque!).
Dans l'immédiat, ne t'en déplaise, je vais peut-être commencer par traduire les douze résultats que tu as communiqués avec ma numérotation à moi, pour me faire une idée plus claire de leur élégance. Va savoir, ce sera peut-être déjà suffisant pour permettre d'imaginer une démarche exploitable par le cerveau d'un humain (c'est comme ça que j'ai fait pour mon problème "partrois"; il est vrai que j'ai étudié bien plus que douze solutions avant d'élaborer ma méthode des cavexes).
En tout cas, merci beaucoup, vraiment, d'avoir 1) résolu ton problème; 2) communiqué tes résultats. L'air de rien, c'est comme ça qu'on fait avancer la civilisation...
Re: Petit jeujeu mathématique deviendra gros casse-tête
Aaargh, hobb, sur la grille "juillet", tu as oublié de numéroter une case (et du coup, ton nombre total de cases est impair, ce qui est impossible comme démontré beaucoup plus haut)... Bizarre que ça n'ait pas fait planter ton algo, d'ailleurs.
Re: Petit jeujeu mathématique deviendra gros casse-tête
Petitagore a écrit:Aaargh, hobb, sur la grille "juillet", tu as oublié de numéroter une case (et du coup, ton nombre total de cases est impair, ce qui est impossible comme démontré beaucoup plus haut)... Bizarre que ça n'ait pas fait planter ton algo, d'ailleurs.
Ca ne peut pas le faire planter...
Ce que tu veux faire (3 par 3) ne sera pas déterministe.
Invité- Invité
Re: Petit jeujeu mathématique deviendra gros casse-tête
Apparemment, pour que la solution que tu as donnée pour la grille "juillet" marche, il suffit (colossale finesse) de numéroter la case non numérotée avec le numéro manquant (41)... J'aimerais quand même que tu revérifies, siouplaît (c'est pour les générations futures, sait-on jamais).
Je ne comprends pas ta remarque sur le 3 par 3 non déterministe, mais de toute façon il s'agit d'un autre sujet.
Je ne comprends pas ta remarque sur le 3 par 3 non déterministe, mais de toute façon il s'agit d'un autre sujet.
Re: Petit jeujeu mathématique deviendra gros casse-tête
J'ai regardé, en fait j'ai oublié de le numéroter sur l'image mais j'avais bien rentré cette case comme étant la 41° dans le data d'entrée. Le résultat est donc bon ^^
Invité- Invité
Re: Petit jeujeu mathématique deviendra gros casse-tête
Et en python ça ira pas assez vite. Pour la plupart de tes grilles, mon code mets à l'aise de 2 minutes à plus d'une demi-heure. en python t'en as pour des mois...
J'ai fais ça en fortran, pour que ça aille le plus vite possible. A la rigueur tu peux le faire en C, mais en python t'en as pour des plombes, vraiment.
Quant aux fichiers en Mo........ t'as pas vu ceux que je manipule ^^
J'ai fais ça en fortran, pour que ça aille le plus vite possible. A la rigueur tu peux le faire en C, mais en python t'en as pour des plombes, vraiment.
Quant aux fichiers en Mo........ t'as pas vu ceux que je manipule ^^
Invité- Invité
Re: Petit jeujeu mathématique deviendra gros casse-tête
Petitagore a écrit:L'air de rien, c'est comme ça qu'on fait avancer la civilisation...
Si tu savais à quel point elle s'en cogne la civilisation de ceux qui la font avancer... Du pur égoïsme individuel : tant que le confort de chacun s'améliore, elle ne fait que gueuler pour que ça soit encore mieux... enfin c'est un autre débat.
Invité- Invité
Re: Petit jeujeu mathématique deviendra gros casse-tête
hobb a écrit:Si tu savais à quel point elle s'en cogne la civilisation de ceux qui la font avancer...
A vrai dire, je le sais. Mais je fais semblant de ne pas le savoir.
Re: Petit jeujeu mathématique deviendra gros casse-tête
Je viens de mettre en ligne ici une page HTML permettant d'étudier les douze solutions de notre ami Hobb dans une interface clicable (légèrement modifiée pour l'occasion: il n'y a plus de coloration spécifique pour la prise de trois cases à la fois, toutes les prises de cases se font en jaune). Je rappelle que Hobb poursuit un objectif différent de celui auquel j'ai consacré les douze pages qui précèdent: il s'agit pour lui de prendre toutes les cases d'une grille en un minimum de coups. C'est un challenge différent de celui dont j'ai abondamment parlé dans les pages qui précèdent, mais qui peut lui aussi se révéler fort intéressant.
Il serait peut-être envisageable de faire de cette idée toute neuve un nouveau jeu mathématique. Le défi serait alors, ou carrément d'égaler from scratch le record identifié par Hobb, ou seulement de retrouver les n derniers coups à partir des premiers (ce qui nous donnerait un casse-tête un peu similaire aux problèmes de type "mat en trois coups", "mat en cinq coups", bien connus et appréciés des joueurs d'échecs). Ce serait peut-être plus rigolo... et en tout cas, sans doute plus compréhensible que ma pourtant brillantissime idée de recherche de cavexes inversibles -- à laquelle la plupart des lecteurs de ce fil n'ont visiblement pas compris grand-chose, je le dis avec une tristesse infinie et nonobstant compatible avec le peu de lucidité dont je suis capable...
(Je m'en fous, le vrai génie est par nature incompris.)
Pauvres nases.
En tout cas, j'espère que l'honorable Hobb acceptera de réfléchir avec moi à cette idée.
Il serait peut-être envisageable de faire de cette idée toute neuve un nouveau jeu mathématique. Le défi serait alors, ou carrément d'égaler from scratch le record identifié par Hobb, ou seulement de retrouver les n derniers coups à partir des premiers (ce qui nous donnerait un casse-tête un peu similaire aux problèmes de type "mat en trois coups", "mat en cinq coups", bien connus et appréciés des joueurs d'échecs). Ce serait peut-être plus rigolo... et en tout cas, sans doute plus compréhensible que ma pourtant brillantissime idée de recherche de cavexes inversibles -- à laquelle la plupart des lecteurs de ce fil n'ont visiblement pas compris grand-chose, je le dis avec une tristesse infinie et nonobstant compatible avec le peu de lucidité dont je suis capable...
(Je m'en fous, le vrai génie est par nature incompris.)
Pauvres nases.
En tout cas, j'espère que l'honorable Hobb acceptera de réfléchir avec moi à cette idée.
Re: Petit jeujeu mathématique deviendra gros casse-tête
Je peux adapter l'algo pour qu'il te dise en combien de coups minimum tu peux finir la grille à partir de n'importe quelle configuration, à creuser...
Invité- Invité
Re: Petit jeujeu mathématique deviendra gros casse-tête
Bon, j'ai fait deux tests à partir des douze grilles résolues par hobb. Primo, j'ai essayé d'atteindre le même optimum que son algorithme à partir d'une grille vide. Deuxio, j'ai amputé ses solutions de leurs cinq derniers coups, et essayé d'imaginer une nouvelle fin permettant de prendre la grille avec cinq coups issus de ma tête.
Résultat: ben c'est de la gnognotte, à mon avis. Non seulement je n'ai pas trouvé ça difficile, mais dans l'immense majorité des cas j'y suis arrivé du premier coup ou presque. Certes, je suis surentraîné, et il est possible que pour quelqu'un qui découvre la logique du jeu ça représente quand même un défi pas complètement inintéressant. Appel au peuple: si quelqu'un de mes sympathiques lecteurs veut faire le test et publier son avis, ça m'intéresserait.
Ça ne veut pas forcément dire qu'on ne peut pas faire un casse-tête avec de telles idées de jeu, mais en l'état ça me paraît seulement voué à élaborer des exercices pédagogiques assez faciles voués par exemple à enseigner le concept de réaction en chaîne aux petits nenfants; c'est très bien, j'aime beaucoup les petits nenfants et je trouve qu'il est important de leur apprendre la logique... en revanche de tels exercices ne me paraissent pas suffisants pour permettre aux surdoués (mes semblables mes frères) de trouver là le merveilleux plaisir masochiste qu'on éprouve à se triturer les méninges.
Oui, je sais, à part moi peu de personnes peuvent approcher l'orgasme en contemplant une grille Triancey. Tant pis pour vous, vous ne savez pas ce que vous perdez.
La recherche d'une prise totale de la grille en un minimum de coups présenterait peut-être plus d'intérêt avec très peu de cases (une vingtaine, voire une douzaine): là, l'algorithme de Hobb trouverait peut-être des solutions extraterrestres d'une élégance difficile à égaler. Symétriquement, on pourrait essayer de travailler avec beaucoup plus de cases... mais je suppose qu'alors ça conduirait à démultiplier exponentiellement les temps de réponse de l'algorithme de Hobb, sans que les optima ainsi identifiés soient forcément difficiles à égaler.
Hobb, je suis à ta disposition pour faire des essais. Ce serait dommage que tes efforts algorithmiques ne servent à rien, mais il faut peut-être leur chercher d'autres applications (avec peut-être des contraintes supplémentaires, du genre obligation de jouer les n premiers coups sur des cases totalement isolées).
Dans l'immédiat, je persiste à trouver que la règle "partrois" dont j'ai si abondamment parlé ci-dessus (quitte à empistrouiller mes lecteurs...) mène à des exercices nettement plus stimulants intellectuellement. Je suis mauvais juge parce que c'est moi que je l'ai inventé et qu'évidemment j'ai pour mon bébé une tendresse compréhensible (voire excusable!). Et puis tout le monde il a pas mes penchants masochistes, même que c'est très heureux... mais quand même, quand même: tel que je vous l'ai montré, il est pas si mal pensé que ça, mon petit jeujeu.
Si, si, je vous assure.
Résultat: ben c'est de la gnognotte, à mon avis. Non seulement je n'ai pas trouvé ça difficile, mais dans l'immense majorité des cas j'y suis arrivé du premier coup ou presque. Certes, je suis surentraîné, et il est possible que pour quelqu'un qui découvre la logique du jeu ça représente quand même un défi pas complètement inintéressant. Appel au peuple: si quelqu'un de mes sympathiques lecteurs veut faire le test et publier son avis, ça m'intéresserait.
Ça ne veut pas forcément dire qu'on ne peut pas faire un casse-tête avec de telles idées de jeu, mais en l'état ça me paraît seulement voué à élaborer des exercices pédagogiques assez faciles voués par exemple à enseigner le concept de réaction en chaîne aux petits nenfants; c'est très bien, j'aime beaucoup les petits nenfants et je trouve qu'il est important de leur apprendre la logique... en revanche de tels exercices ne me paraissent pas suffisants pour permettre aux surdoués (mes semblables mes frères) de trouver là le merveilleux plaisir masochiste qu'on éprouve à se triturer les méninges.
Oui, je sais, à part moi peu de personnes peuvent approcher l'orgasme en contemplant une grille Triancey. Tant pis pour vous, vous ne savez pas ce que vous perdez.
La recherche d'une prise totale de la grille en un minimum de coups présenterait peut-être plus d'intérêt avec très peu de cases (une vingtaine, voire une douzaine): là, l'algorithme de Hobb trouverait peut-être des solutions extraterrestres d'une élégance difficile à égaler. Symétriquement, on pourrait essayer de travailler avec beaucoup plus de cases... mais je suppose qu'alors ça conduirait à démultiplier exponentiellement les temps de réponse de l'algorithme de Hobb, sans que les optima ainsi identifiés soient forcément difficiles à égaler.
Hobb, je suis à ta disposition pour faire des essais. Ce serait dommage que tes efforts algorithmiques ne servent à rien, mais il faut peut-être leur chercher d'autres applications (avec peut-être des contraintes supplémentaires, du genre obligation de jouer les n premiers coups sur des cases totalement isolées).
Dans l'immédiat, je persiste à trouver que la règle "partrois" dont j'ai si abondamment parlé ci-dessus (quitte à empistrouiller mes lecteurs...) mène à des exercices nettement plus stimulants intellectuellement. Je suis mauvais juge parce que c'est moi que je l'ai inventé et qu'évidemment j'ai pour mon bébé une tendresse compréhensible (voire excusable!). Et puis tout le monde il a pas mes penchants masochistes, même que c'est très heureux... mais quand même, quand même: tel que je vous l'ai montré, il est pas si mal pensé que ça, mon petit jeujeu.
Si, si, je vous assure.
Dernière édition par Petitagore le Lun 01 Juin 2015, 23:15, édité 1 fois (Raison : faute d'accord)
Re: Petit jeujeu mathématique deviendra gros casse-tête
Il sagit d'un algo en O(n²) maximum, donc limité en terme de taille (logique), mais il peut encore monter (sinon avec encore un peu d'optim, genre parallélisation MPI (pas openmp parce que vu la structure de l'algo c'est un coup à attraper des dead-lock), ça pourrait aller plus vite).
Invité- Invité
Re: Petit jeujeu mathématique deviendra gros casse-tête
Petitagore, je trouve les jeux futiles et que c'est perdre son temps d'intelligence et de concentration pour rien d'autre, le cas échéant d'addiction, qu'une espèce de culturisme du cerveau. Comment peux t'on s'appeler Kasparov et avoir employé tant d'intelligence uniquement pour montrer qu'il a la plus grosse dans un exercice de vie qui vaut bien les poids et haltères plus le régime hyper-protéiné ?
Attention, je ne suis pas en train de juger. En fait je ne fais que donner une opinion qui ne concerne que ma gestion personnelle des ressources intellectuelles dont je dispose : je suis intégralement fada de programmation, même si c'est mon métier depuis 30 ans. Ce qui se passe, c'est que j'estime que cette activité met en jeu les mêmes circuits neuronaux que ce genre de jeux mathématiques ou logiques. Passer du temps à des casse têtes, c'est comme de me reposer d'avoir programmé dix heures dans la journée en faisant un peu de programmation !
Ceci était dit a la fois pour le simple plaisir de la digression pré-oratoire et pour justifier le fait que je n'irai sur ce sujet pas au delà de l'éloge, j'admire résolument ta découverte, j'admire l'originalité, la profondeur et la variété de ce jeu pour lequel, pourtant tu l'as compris, je ne donnerai pas plus de cinq minutes de ma vie à cliquer sur un canevas java bien foutu en plus, ou à réfléchir aux nombreuses et ouvertes variantes des équations que tu proposes à la sagacité des lecteurs joueurs.
Une telle découverte/réalisation mérite largement que des tas et des tas de gens perdent des heures et des heures de leur temps de cerveau disponible à tenter de résoudre ces subtiles et pures équations totalement inutiles et communiquent fébrilement entre eux leur certitude d'avoir la plus grosse à l'aune de cette nouvelle et magnifique échelle !
Magnifique !
Attention, je ne suis pas en train de juger. En fait je ne fais que donner une opinion qui ne concerne que ma gestion personnelle des ressources intellectuelles dont je dispose : je suis intégralement fada de programmation, même si c'est mon métier depuis 30 ans. Ce qui se passe, c'est que j'estime que cette activité met en jeu les mêmes circuits neuronaux que ce genre de jeux mathématiques ou logiques. Passer du temps à des casse têtes, c'est comme de me reposer d'avoir programmé dix heures dans la journée en faisant un peu de programmation !
Ceci était dit a la fois pour le simple plaisir de la digression pré-oratoire et pour justifier le fait que je n'irai sur ce sujet pas au delà de l'éloge, j'admire résolument ta découverte, j'admire l'originalité, la profondeur et la variété de ce jeu pour lequel, pourtant tu l'as compris, je ne donnerai pas plus de cinq minutes de ma vie à cliquer sur un canevas java bien foutu en plus, ou à réfléchir aux nombreuses et ouvertes variantes des équations que tu proposes à la sagacité des lecteurs joueurs.
Une telle découverte/réalisation mérite largement que des tas et des tas de gens perdent des heures et des heures de leur temps de cerveau disponible à tenter de résoudre ces subtiles et pures équations totalement inutiles et communiquent fébrilement entre eux leur certitude d'avoir la plus grosse à l'aune de cette nouvelle et magnifique échelle !
Magnifique !
Re: Petit jeujeu mathématique deviendra gros casse-tête
mumen a écrit:Une telle découverte/réalisation mérite largement que des tas et des tas de gens perdent des heures et des heures de leur temps de cerveau disponible à tenter de résoudre ces subtiles et pures équations totalement inutiles et communiquent fébrilement entre eux leur certitude d'avoir la plus grosse à l'aune de cette nouvelle et magnifique échelle !
Magnifique !
Hum... J'aurais mauvaise grâce à ne pas prendre tout ça pour un compliment.
Je suis généralement assez de ton avis sur la perte de temps et d'énergie intellectuelle que représentent les jeux. J'ai pas mal étudié les échecs, je pense que ça m'a appris beaucoup de choses, mais ce qu'ils m'ont appris de plus important et de très loin, c'est que... jouer aux échecs est une perte de temps. Tu vois, je pense un peu comme toi.
Pour mon casse-tête, c'est un peu différent. C'est moi qui avais eu l'idée, si ce n'était pas moi qui la creusais personne ne l'aurait fait à ma place... Je me suis senti responsable de mon idée comme le Petit Prince était responsable de sa rose, et puis je suis vraiment titillé par ce paradoxe: il existe de toute éternité, sur ce jeu que j'ai inventé il y a quelques années, sur une grille que mes algorithmes ont fabriquée ce matin, un ensemble parfaitement défini de solutions; ça existe depuis toujours, ça existe à jamais, c'est éternel, incréé, incontestable... comme Dieu, quoi -- sauf que je peux douter de l'existence de Dieu alors que je ne peux pas douter de la validité des solutions de mes grilles!
Par ailleurs, à côté de la version casse-tête qui a fait l'objet de ce fil, il y a la version toute simple à laquelle on peut faire jouer les mômes -- et là je pense que si tu vois les échecs comme du culturisme, alors ce petit jeujeu peut faire en comparaison l'effet d'une saine gymnastique.
Merci de ton commentaire en tout état de cause.
Re: Petit jeujeu mathématique deviendra gros casse-tête
@mumen : Parce que pour toi les gens "intelligents" doivent uniquement appliquer ça au service de l'humanité ? Pas le droit d'avoir un loisir ?
Tu peux aussi les enfermer dans une cave et les interdire de rire et passer leur vie à bosser sur des trucs qu'eux seuls peuvent résoudre. T'en as d'autres des idées à la **** comme ça ?
Tu peux aussi les enfermer dans une cave et les interdire de rire et passer leur vie à bosser sur des trucs qu'eux seuls peuvent résoudre. T'en as d'autres des idées à la **** comme ça ?
Invité- Invité
Re: Petit jeujeu mathématique deviendra gros casse-tête
Bon, je doute qu'il reste qui que ce soit pour suivre encore ce fil, mais tant pis: il me sert toujours à prendre des notes pour une monographie future. Donc, out of the blue, permettez-moi de noter ici une précision dont j'ai pris conscience ce matin en jouant sur cette grille-ci (oui, je joue à mon casse-tête à peu près tous les jours que le Bon Dieu fait; vous ne m'auriez pas cru monomaniaque à ce point, hein? si? ah bon):
... laquelle grille est aussi disponible dans une version interactive (en Javascript) à cette adresse.
Or donc, cette grille, munie d'un trilatère (les cases 17, 18 et 26) montre que le théorème de l'avant-dernier coup (qui affirme que le dernier coup d'une partie à score optimal doit être joué sur un pentagone) peut tolérer des exceptions. La solution ci-dessous (trouvée par mon solveur, bien entendu) en constitue une:
29 4 36 7 27 2 0 37 15 22 12 17 (19)
Eh bien oui, sur cette grille le score optimal peut être obtenu en jouant l'avant-dernier coup sur un trilatère plutôt que sur un pentagone. Vous, je sais pas, mais moi ça m'en a bouché un coin d'en prendre conscience.
C'est tout pour aujourd'hui. Navré de vous avoir dérangés.
... laquelle grille est aussi disponible dans une version interactive (en Javascript) à cette adresse.
Or donc, cette grille, munie d'un trilatère (les cases 17, 18 et 26) montre que le théorème de l'avant-dernier coup (qui affirme que le dernier coup d'une partie à score optimal doit être joué sur un pentagone) peut tolérer des exceptions. La solution ci-dessous (trouvée par mon solveur, bien entendu) en constitue une:
29 4 36 7 27 2 0 37 15 22 12 17 (19)
Eh bien oui, sur cette grille le score optimal peut être obtenu en jouant l'avant-dernier coup sur un trilatère plutôt que sur un pentagone. Vous, je sais pas, mais moi ça m'en a bouché un coin d'en prendre conscience.
C'est tout pour aujourd'hui. Navré de vous avoir dérangés.
Re: Petit jeujeu mathématique deviendra gros casse-tête
Sauf que l'optimum est en 2 coups de moins : 24, 29, 22, 18, 20, 6, 11, 31, 2, 9 ;-)
Invité- Invité
Re: Petit jeujeu mathématique deviendra gros casse-tête
hobb a écrit:Sauf que l'optimum est en 2 coups de moins : 24, 29, 22, 18, 20, 6, 11, 31, 2, 9 ;-)
On joue sur la même grille, mais pas au même jeu... Je parlais bien sûr de la règle "partrois" (l'essentiel des pages précédentes y est consacré), où l'optimum est constitué de la séquence où chaque coup gagnant prend exactement trois cases, pas une de plus, pas une de moins.
Donc, je t'incite vivement à relire toutes les pages précédentes.
Re: Petit jeujeu mathématique deviendra gros casse-tête
Hmmm intéressant. A voir si je ne peux pas adapter le code pour cette règle là...
Invité- Invité
Page 5 sur 6 • 1, 2, 3, 4, 5, 6
Sujets similaires
» Petit casse-tête à l'attention de ceux qui lancent des sorties ici :)
» Petit Zebron? Deviendra grand ?
» L'Amour.. Mon casse-tête zébré...
» L'art de m'en faire voir de 6 couleurs... Rubik's Cube [Casse-tête]
» Ca yest... mon petit a mal à la tête et au ventre à l'école
» Petit Zebron? Deviendra grand ?
» L'Amour.. Mon casse-tête zébré...
» L'art de m'en faire voir de 6 couleurs... Rubik's Cube [Casse-tête]
» Ca yest... mon petit a mal à la tête et au ventre à l'école
Page 5 sur 6
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum