Petit jeujeu mathématique deviendra gros casse-tête

+6
Petitagore
Pieyre
loulou38
Professeur Megamiaou
Stauk
Ardel
10 participants

Page 5 sur 6 Précédent  1, 2, 3, 4, 5, 6  Suivant

Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Invité Jeu 28 Mai 2015, 18:25

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.

Invité
Invité


Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore Jeu 28 Mai 2015, 18:58

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  Razz ), 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").
Petitagore
Petitagore

Messages : 6311
Date d'inscription : 29/11/2011
Age : 63
Localisation : Ile-de-France

http://lesmoulinettes.amarelia.ch

Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Invité Jeu 28 Mai 2015, 19:31

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.

Invité
Invité


Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Invité Jeu 28 Mai 2015, 19:42

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é


Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Invité Jeu 28 Mai 2015, 19:58

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é


Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore Jeu 28 Mai 2015, 20:07

Merci, je vais essayer de comprendre au moins la démarche générale. Very Happy
Petitagore
Petitagore

Messages : 6311
Date d'inscription : 29/11/2011
Age : 63
Localisation : Ile-de-France

http://lesmoulinettes.amarelia.ch

Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Invité Jeu 28 Mai 2015, 20:14

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) :

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é


Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore Jeu 28 Mai 2015, 20:31

hobb a écrit:C'est toi qui l'a inventé ?

Je veux, mon neveu! Very Happy
Petitagore
Petitagore

Messages : 6311
Date d'inscription : 29/11/2011
Age : 63
Localisation : Ile-de-France

http://lesmoulinettes.amarelia.ch

Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore Sam 30 Mai 2015, 10:16

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... Very Happy
Petitagore
Petitagore

Messages : 6311
Date d'inscription : 29/11/2011
Age : 63
Localisation : Ile-de-France

http://lesmoulinettes.amarelia.ch

Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore Sam 30 Mai 2015, 10:32

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.
Petitagore
Petitagore

Messages : 6311
Date d'inscription : 29/11/2011
Age : 63
Localisation : Ile-de-France

http://lesmoulinettes.amarelia.ch

Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Invité Sam 30 Mai 2015, 12:20

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é


Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore Sam 30 Mai 2015, 12:40

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.
Petitagore
Petitagore

Messages : 6311
Date d'inscription : 29/11/2011
Age : 63
Localisation : Ile-de-France

http://lesmoulinettes.amarelia.ch

Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Invité Sam 30 Mai 2015, 14:34

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é


Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Invité Sam 30 Mai 2015, 15:58

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........ Very Happy t'as pas vu ceux que je manipule ^^

Invité
Invité


Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Invité Sam 30 Mai 2015, 16:06

Petitagore a écrit:L'air de rien, c'est comme ça qu'on fait avancer la civilisation... Very Happy

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é


Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore Sam 30 Mai 2015, 23:03

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. Very Happy
Petitagore
Petitagore

Messages : 6311
Date d'inscription : 29/11/2011
Age : 63
Localisation : Ile-de-France

http://lesmoulinettes.amarelia.ch

Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore Dim 31 Mai 2015, 15:48

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.  Razz

En tout cas, j'espère que l'honorable Hobb acceptera de réfléchir avec moi à cette idée. Very Happy
Petitagore
Petitagore

Messages : 6311
Date d'inscription : 29/11/2011
Age : 63
Localisation : Ile-de-France

http://lesmoulinettes.amarelia.ch

Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Invité Dim 31 Mai 2015, 18:04

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é


Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore Lun 01 Juin 2015, 20:18

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. Very Happy 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)
Petitagore
Petitagore

Messages : 6311
Date d'inscription : 29/11/2011
Age : 63
Localisation : Ile-de-France

http://lesmoulinettes.amarelia.ch

Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Invité Lun 01 Juin 2015, 20:40

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é


Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par mumen Sam 29 Aoû 2015, 13:06

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 !
mumen
mumen

Messages : 318
Date d'inscription : 02/05/2013
Age : 63
Localisation : Arras

https://www.zebrascrossing.net/t14327-indexmumen#595427

Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore Sam 29 Aoû 2015, 16:08

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. Very Happy

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.
Petitagore
Petitagore

Messages : 6311
Date d'inscription : 29/11/2011
Age : 63
Localisation : Ile-de-France

http://lesmoulinettes.amarelia.ch

Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Invité Lun 31 Aoû 2015, 22:19

@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 ?

Invité
Invité


Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore Lun 20 Nov 2017, 16:01

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):

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 20171120b

... 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. Very Happy
Petitagore
Petitagore

Messages : 6311
Date d'inscription : 29/11/2011
Age : 63
Localisation : Ile-de-France

http://lesmoulinettes.amarelia.ch

Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Invité Jeu 04 Jan 2018, 15:21

Sauf que l'optimum est en 2 coups de moins : 24, 29, 22, 18, 20, 6, 11, 31, 2, 9 ;-)

Invité
Invité


Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Petitagore Jeu 04 Jan 2018, 15:30

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. Wink
Petitagore
Petitagore

Messages : 6311
Date d'inscription : 29/11/2011
Age : 63
Localisation : Ile-de-France

http://lesmoulinettes.amarelia.ch

Revenir en haut Aller en bas

Petit jeujeu mathématique deviendra gros casse-tête - Page 6 Empty Re: Petit jeujeu mathématique deviendra gros casse-tête

Message par Invité Jeu 04 Jan 2018, 15:34

Hmmm intéressant. A voir si je ne peux pas adapter le code pour cette règle là...

Invité
Invité


Revenir en haut Aller en bas

Page 5 sur 6 Précédent  1, 2, 3, 4, 5, 6  Suivant

Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum