PureBasic

Forums PureBasic - Français
https://www.purebasic.fr/french/

Entretiens d'embauche chez Google

https://www.purebasic.fr/french/viewtopic.php?t=17202

Page 7 sur 7

Re: Entretiens d'embauche chez Google

Publié : dim. 08/avr./2018 17:07
par zaphod_b
ma soluce (pas de garde aujourd'hui) :

Code : Tout sélectionner

Global Dim t(10)
Global Dim c(10)

;t(0)=4:t(1)=2:t(2)=0:t(3)=0:t(4)=2:t(5)=0
;t(0)=3:t(1)=2:t(2)=0:t(3)=2:t(4)=1:t(5)=1
;t(0)=4:t(1)=1:t(2)=1:t(3)=4:t(4)=0:t(5)=1:t(6)=0:t(7)=4:t(8)=1
;t(0)=4:t(1)=5:t(2)=0:t(3)=0:t(4)=2:t(5)=0
t(0)=3:t(1)=3:t(2)=2:t(3)=0:t(4)=2:t(5)=2 
;
Global r=6

Procedure verif2()
   Protected i,m
   For i=0 To ArraySize(t())-1
     If t(i)>m
       m=t(i)
     EndIf
   Next
   ;
   If m>t(0)
     ProcedureReturn 1
   EndIf   
EndProcedure

Procedure verif(j)
  Protected i,p
  For i=0 To j-1
    p+t(c(i))
  Next
  If p>=r
    ProcedureReturn 1
  EndIf
EndProcedure

If verif2()
  Debug "impossible de sauter"
  End
EndIf

Repeat
  If t(i)<>0
   
    c(j)=i
    i+t(i)
    j+1
    If verif(j)   
      For l=0 To j-1
        c$+Str(c(l))+" : "
      Next
      Debug c$
      Break
    EndIf
   
  Else
    i=c(j-1)
    c(j)=0
    j-1   
    If j<0
      Debug "impossible 1"
      Break     
    EndIf
   
    t(i)-1
  EndIf

ForEver
Correction du code suite remarque de Zorro....
Peut être ca colle maintenant....
...encore corrigé.... :D :D

Re: Entretiens d'embauche chez Google

Publié : dim. 08/avr./2018 19:38
par Zorro
non ça ne marche pas :)

si tu mets
t(0)=4:t(1)=5:t(2)=0:t(3)=0:t(4)=2:t(5)=0

il donne toujours le meme resultat , hors c'est pas possible :)

parce que la deuxième tour fait 5 la première fait 4 , donc ton bonhomme ne peut pas passer par dessus ;)

ps: mon code est une usine a gaz a comparer du tiens :lol:
bon il faut dire aussi , que j'affiche les phases successive du déplacement du personnage ..

Re: Entretiens d'embauche chez Google

Publié : dim. 08/avr./2018 19:54
par Fig
Zorro a écrit : parce que la deuxième tour fait 5 la première fait 4 , donc ton bonhomme ne peut pas passer par dessus ;)
Je ne l'avais pas précisé mais effectivement on ne peut pas sauter une tour plus haute que celle sur laquelle on est.

Re: Entretiens d'embauche chez Google

Publié : dim. 08/avr./2018 20:44
par Zorro
voici mon code :)

le resultat s'affiche de la sorte :

"3[x],2,2,0,2,2"

les chiffres symbolise la hauteur de chaque tour (il y en a 6 )
le [x] indique l'endroit ou se trouve le joueur

il y aura suivant les cas, plusieur lignes d'affilé , qui montreront les etapes du deplacement du joueur

dans le cas fourni par defaut , la progression sera la suivante

on commence sur la tour 0 qui fait 3 de haut
donc le joueur va sauter sur la tour 3 qui fait 0 de haut puisqu'elle se trouve a 3 de distance
seulement c'est un piege ! si le joueur saute là , c'est terminé
l'algo va donc rechercher a sauter a la position precedente , la tour numero 2 qui fait 2 de haut
puis continu son bonhomme de chemin de la tour 2 a la tour 4 , puis en dehors, c'est fini

cela va donc afficher les etapes suivantes :
3[x],2,2,0,2,2
3,2,2[x],0,2,2
3,2,2,0,2[x],2
3,2,2,0,2,2[x]
Arrivée FINI !!!
***********************************************
Le code indiquera si il y a un cas d'imposibilité
par exemple une tour trop haute dans le parcours ....
ou bien si le joueur tombe dans un trou , ou sur une tour plus petite que la suivante , et qui le bloque :)

Recusif Power :)

le code :

Code : Tout sélectionner


;***********************************************
;Titre  :*probleme_google_4
;Auteur  : Zorro
;Date  :08/04/2018
;Heure  :15:26:18
;Version Purebasic :  PureBasic 5.62 (Windows - x86)
;Version de l'editeur :EPB V2.68
; Libairies necessaire : Aucune 
;***********************************************


Declare affichage (Position_joueur)
Declare recherche(position_joueur)

Global  Dim D(13),Carte.s,Carte_ori.s




; pour tests .... 
D(0)=2   ; <<<<<<<<<<<<<<<<<<<<<<<<<<< va sauter en D(3)
Carte.s=Carte.s+str(D(0))+","
D(1)=2
Carte.s=Carte.s+str(D(1))+","
D(2)=0
Carte.s=Carte.s+str(D(2))+","
D(3)=0  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<< ici j'ai mis volontairement un piege, qui  force l'algo a reculer d'un pas pour repartir sur la colonne 2 precedente :o)
Carte.s=Carte.s+str(D(3))+","
D(4)=2
Carte.s=Carte.s+str(D(4))+","
D(5)=1
Carte.s=Carte.s+str(D(5))+","
#Max=5



; *****Laisser ceci c'est le bornage ******
; au dela du tableau je remplis de "88" 
; comme ça je sais si je suis sorti du tableau ... ;o)
For i=6 to 13
		D(i)=88
Next i
; ************************************
Carte.s=Left(Carte.s,Len(Carte.s)-1)
Carte_ori.s=Carte.s
Position_joueur=0
; resultat
;affichage (Position_joueur)
; *****************************************
Position_joueur=recherche(Position_joueur)
Debug " ***********************************************"
Debug ""

Carte_ori.s=""
Carte.s=""






;- *********************  Zone Procedures *****************************************************
; *******************************************************************************************
Procedure affichage (Position_joueur)
		; ***  juste pour gestion affichage du joueur *** par un '[x]'
		Carte.s=Carte_ori.s ; efface
		pre_Carte.s=mid(Carte.s,0,((Position_joueur+1)*2)-1)+"[x]"
		Post_carte.s=mid(Carte.s,((Position_joueur+1)*2))
		Carte.s=pre_Carte.s+Post_carte.s
		Debug Carte.s
		; *****************************************
EndProcedure

Procedure recherche(Position_joueur)
		; By Zorro (pas du tout optimisé !! )
		; Recursif Power
		Static Flag
		Flag=Flag+1
		If Flag>#Max
		Debug "Pas de solutions FINI !!!  "
						ProcedureReturn -1
		Endif
		If Position_joueur>=ArraySize(D())
				ProcedureReturn -1
		Endif
		affichage (Position_joueur)
		For z=Position_joueur to #Max
				If D(z)>D(Position_joueur)
						Debug "Pas de solutions FINI !!!  "
						ProcedureReturn -1
				Endif
		Next z
;		calldebugger
		
		nombre_tour=D(Position_joueur)
		If nombre_tour=88
				affichage (#Max)
				Debug "Arrivée FINI !!!  "
				Position_joueur=ArraySize(D())
				ProcedureReturn -1
		Endif
		Arrive_possible=D(nombre_tour+Position_joueur)


		
		If Arrive_possible=88  or D(0)=#Max  or (Position_joueur+nombre_tour>=#Max)
				affichage (#Max)
				Debug "Arrivée FINI !!!  "
				Position_joueur=ArraySize(D())

				ProcedureReturn -1
		Endif
		
		
		If Arrive_possible=0 ; ce cas si l'arrivée prevu est un trou
				nombre_tour=nombre_tour-1
				Arrive_possible=D(nombre_tour+Position_joueur)
				If nombre_tour<1
						Position_joueur=Position_joueur-1
						If Position_joueur<1
								Debug "Pas de solutions FINI !!!  "
								ProcedureReturn -1
						Endif
				Endif
				Position_joueur=nombre_tour
				recherche(Position_joueur)
				goto suite
		Endif
		Position_joueur=nombre_tour+Position_joueur	
		If Position_joueur>=ArraySize(D())
				ProcedureReturn -1
		Else
				recherche(Position_joueur)
		Endif
		suite:
EndProcedure

; Epb

Re: Entretiens d'embauche chez Google

Publié : dim. 08/avr./2018 21:59
par zaphod_b
Bon j'ai corrigé mon précédent code... je croise les doigts.

Code : Tout sélectionner

t(0)=4:t(1)=5:t(2)=0:t(3)=0:t(4)=2:t(5)=0
rend un résultat impossible.

Re: Entretiens d'embauche chez Google

Publié : lun. 09/avr./2018 5:10
par Zorro
pour mon algo , j'ai effectué une petite correction dans le code
pour detecter une impossiblité non flagrante

par exemple pour une carte style qui est impossible a finir

D(0)=2
D(1)=2
D(2)=0
D(3)=0
D(4)=2
D(5)=1
il passe de D(0) a D(1)
puis de D(1) a .... D(0)
puis recommence indefiniment .... :lol:

j'ai donc ajouté un test :)




@zaphod_b :

Ta correction fonctionne
mais ton prg considere

t(0)=3:t(1)=2:t(2)=2:t(3)=0:t(4)=2:t(5)=2 ; comme impossible

hors si le bonhomme peut sauter sur 3 il peut aussi sauter sur 2 ou sur 1....
ton algo ne semble pas explorer ces possibilités.... mais je me trompe peut etre

a|
a|b|c| |e|f|
a|b|c| |e|f | <-- on peut sauter de 'A' vers || et c'est fini ..... ou de 'A' vers 'b' .. ou de 'A' vers 'c' ensuite de 'c' vers 'e'
puis de 'e' vers l'exterieur FINI ..... :)

donc la solution serai 0,2,4, fini

ton prg renvoi presque ça ....
il renvoi 0,2,4,5,5 "Impossible" :)

Re: Entretiens d'embauche chez Google

Publié : lun. 09/avr./2018 14:33
par zaphod_b
J'ai encore corrigé pour tenir compte de l'exemple :

Code : Tout sélectionner

t(0)=3:t(1)=3:t(2)=2:t(3)=0:t(4)=2:t(5)=2
Et j'ai aussi simplifié.

Re: Entretiens d'embauche chez Google

Publié : lun. 09/avr./2018 20:29
par Zorro
il n'y a pas a dire ton code est plus concis que le miens :)
Fuseau horaire sur UTC+01:00
Page 7 sur 7

Développé par phpBB® Forum Software © phpBB Limited

Traduction française officielle © Qiaeru