Scooby-Naire, le chien de Joseph Marchand, est très intelligent. Il arrive à communiquer avec son maître en tapant ses messages sur le clavier. Malheureusement, ses grosses pattes ne lui permettent pas d'être précis et il appuie sur les touches alentour.
En revanche, le vocabulaire de Scooby-Naire étant assez limité, Joseph Marchand peut facilement tester les messages les plus courants. Pour l'y aider, vous devez écrire un programme qui renvoie 1 si la chaîne passée en paramètre peut-être contenue dans le message, 0 sinon.
Trois exemples d'entrée + sortie :
1er exemple
68
Moi je le dis clairement: K est carrement trop fort, c'est mon idole
15
K est mon idole
1
2ème exemple
34
TATA YOYO IL MA TAPE ON VA LE TUER
10
TTY MA TUE
1
3ème exemple
15
JOSEPH MARCHAND
3
JEU
0
Comment lire les entrées ? Réponse :
Entrée
Sur la première ligne, un entier M représentant la taille du message de Scooby-Naire.
Sur la deuxième ligne, le message de Scooby-Naire.
Sur la troisième ligne, un entier N représentant la taille de la chaîne à tester.
Sur la dernière ligne, la chaîne à tester.
Sortie attendue
1 si la chaîne à tester est contenue dans le message de Scooby-Naire, 0 sinon.
Je vous invite à formuler vos réctions dans ce fil ainsi qu'à poster vos codes (ce n'est pas interdit par Prologin). Placer votre code dans des balises «secret».
Vous pouvez tester vos codes sur le serveur de Prologin (il faut juste s'être enregistré sur leur site). Il y a 7 tests à valider.
Voici un code Python 2.6 à compléter et qui permet tel quel de soumettre l'exercice en question :
def f(s,t):
# placer votre code-solution ICI
# LAISSER TEL QUEL
n = int(raw_input())
s = raw_input()
m = int(raw_input())
t = raw_input()
print f(s,t)
Bon je m'explique, j'avais pas bien compris l'histoire du chien au départ.
Lorsqu'il tape, il ne peut pas maîtriser exactement les touches sur lesquelles il va taper, il est donc logique de ne tester que des caractères et non des mots dans sa phrase.
Dans les exemples donnés, exemple 1 et 3, on aurait le même résultat (1 et 0) si on testait des mots.
Dans l'exemple 2, si on teste des mots, le résultat aurait dû être 0, c'est là où j'ai compris qu'il fallait tester caractère par caractère.
Enfin bref, maintenant j'ai compris la problématique du sujet.
- la première est super simple elle utilise une régex pour faire le boulot (probablement lent si l'hypothèse est longue)
- la seconde vérifie juste récursivement si l'hypothèse est correcte (au final ça fait la même chose que la solution de la régex mais sûrement plus rapide, et ne fonctionnera pas sur de longues chaînes → on va casser la pile.)
- la troisième c'est comme la seconde mais version itérative (plus de problèmes de pile)
#!/usr/bin/env python
#-*- coding: utf-8 -*-
import re
def possible_a(msg, hypo):
# match tout ce qui ressemble à hypo
return re.search('.*'.join(hypo), msg)
def possible_b(msg, hypo):
# si hypo vide ça matche
if not hypo:
return True
# si msg est vide ça ne marche pas
elif not msg:
return False
elif msg[0] == hypo[0]:
# si les deux premiers caractères sont égaux ça march
if possible_b(msg[1:], hypo[1:]):
return True
# sinon on avance msg et on retente de matcher
return possible_b(msg[1:], hypo)
def possible_c(msg, hypo):
# comme possible_b mais sans la récursion
while msg and hypo:
if msg[0] == hypo[0]:
hypo = hypo[1:]
msg = msg[1:]
return hypo == ''
if __name__ == '__main__':
input()
msg = input()
input()
hypo = input()
print(1 if possible_a(msg, hypo) else 0)
print(1 if possible_b(msg, hypo) else 0)
print(1 if possible_c(msg, hypo) else 0)
Merci pour les deux réponses fournies mais pourriez-vous utiliser le template suivant pour que je puisse tester votre code sur le serveur (au passage, il n'acceptera pas les regexp à mon avis mais je veux bien essayer) ?
def f(s,t):
# placer votre code-solution ICI
# doit renvoyer 0 ou 1
# LAISSER TEL QUEL
n = int(raw_input()) # le nombre de caracteres de s
s = raw_input() # la chaine s
m = int(raw_input()) # le nombre de caractère de t
t = raw_input() # la chaine t sous-chaine de s (ou pas)
print f(s,t)
Merci, bon le code complet prêt à tester aurait été mieux, oui je sais je suis ch****
Citation : la Hache
Je suis en Python3 chez moi, mais je crois que là c'est pareil.
Je trouve pas ton code super pythonnique, on dirait du C traduit en Python, mais c'est vrai que c'est pas le but
Citation : la Hache
EDIT : je me suis inscrit, j'ai soumis, j'ai vaincu.
Bravo, moi j'ai dû m'y prendre à deux fois (bien faire ses tests avant).
Citation : la Hache
En revanche, je sais pas comment on peut ensuite comparer différentes solutions ...
Le problème étant assez facile, je ne sais pas si ça a un grand intéreêt. il faudrait générer de grandes chaînes aléatoires, là je t'avoue que j'ai pas le temps de le faire.
J'en ai profité pour faire le décryptage II, plus Pythonique (Python est mon langage naturel, C je connais moins ; j'aime les deux)
import sys
def decryptage2(n, s1, m, s2):
dico = dict()
for c in s2:
if c in dico:
dico[c]+=1
else:
dico[c]=1
for c in s1:
if c in dico:
dico[c]-=1
if not dico[c]: del dico[c]
if not dico: return 1
return 0
if __name__ == '__main__':
n = int(raw_input())
s1 = raw_input()
m = int(raw_input())
s2 = raw_input()
print decryptage2(n, s1, m, s2)
EDIT : je viens de faire chocolat, avec chocolat.
C'est quoi ces brèles, pour eux 0/0 = 0 !!!!!!!!
Je suis furieux !!!!!!!!
Ça va pas se passer comme ça
@Candide: voila (j'ai pas testé hormis les trois exemples donc ça peut littéralement rater):
#-*- coding: utf-8 -*-
import re
def f(s,t):
return 1 if re.search('.*'.join(t), s) else 0
# LAISSER TEL QUEL
n = int(raw_input()) # le nombre de caracteres de s
s = raw_input() # la chaine s
m = int(raw_input()) # le nombre de caractère de t
t = raw_input() # la chaine t sous-chaine de s (ou pas)
print f(s,t)
#-*- coding: utf-8 -*-
def f(s,t):
if not t:
return 1
elif not s:
return 0
elif s[0] == t[0]:
if f(s[1:], t[1:]):
return 1
return f(s[1:], t)
# LAISSER TEL QUEL
n = int(raw_input()) # le nombre de caracteres de s
s = raw_input() # la chaine s
m = int(raw_input()) # le nombre de caractère de t
t = raw_input() # la chaine t sous-chaine de s (ou pas)
print f(s,t)
#-*- coding: utf-8 -*-
def f(s,t):
while s and t:
if s[0] == t[0]:
t = t[1:]
s = s[1:]
return 1 if t == '' else 0
# LAISSER TEL QUEL
n = int(raw_input()) # le nombre de caracteres de s
s = raw_input() # la chaine s
m = int(raw_input()) # le nombre de caractère de t
t = raw_input() # la chaine t sous-chaine de s (ou pas)
print f(s,t)
def prolog3(s, text):
if s and len(s) < 2001:
for c in s:
if c not in text:
break
else:
return True
return False
Je pense que c'est pas bon, le chien tape les lettres dans l'ordre (mais en rajoute au passage)
donc, ta fonction va sûrement échouer,
et puis aussi, s'il doit taper deux 'T', et qu'il n'y en a qu'un à l'arrivée ta fonction ne le détecte pas !!!
Je vois donc deux erreurs.
---
Je viens de me faire la brochette des huit premiers.
À part 0/0 = 0, je n'ai pas vu d'autres blagounettes.
Si j'ai le temps, j'essaye la suite, mais je voudrais que ce soit en Python3,
ça me saoule d'avance de devoir revérifier en mode Py2.
Il va falloir les booster pour qu'ils passent à Python3 : c'est l'avenir.
OK pour les utilisateurs actuels soient pas embêtés mais pour les étudiants ...
je pense qu'il faut promouvoir le Python3 sans faiblir !!!!
Si tu pouvais donner du code testable sur leur serveur, cf. le template plus haut. Bon tu passes 3 tests sur 7, voici ton code tel que je l'ai soumis :
def f(text,s):
if s and len(s) < 2001:
for c in s:
if c not in text:
break
else:
return 1
return 0
# LAISSER TEL QUEL
n = int(raw_input())
s = raw_input()
m = int(raw_input())
t = raw_input()
print f(s,t)
3 tests sur 7
Citation : cerium50
@Candide: voila (j'ai pas testé hormis les trois exemples donc ça peut littéralement rater)
Tes trois codes passent tous les tests. En particulier, il est bon de savoir qu'on utiliser des regexp.
Citation : la Hache
Je viens de me faire la brochette des huit premiers.
À part 0/0 = 0, je n'ai pas vu d'autres blagounettes.
J'en ai fait un certain nombre. J'ai trouvé l'énoncé de Décryptage 2 très ambigu, si tu ne l'avais pas essayé je l'aurais même pas tenté. Au final c'est assez simple mais bon qu'est-ce que c'est mal rédigé. Mon code est un peu différent du tien (j'ai utilisé deux dicos).
L'exo equilibre est infaisable si on n'a pas les connaissances de physique qu'il faut. N'importe quoi d'avoir posé un exo pareil, surtout qu'une fois qu'on connait la formule, c'est beaucoup plus simple que d'autres de niveau soi-disant moins élevé.
L'exo epiphanie a déjà été posé (par moi-même) sur ce forum.
Des seuls exos qui restent, seul rectangles me paraît à la fois suffisamment clair d'énoncé et intéressant. Les autres sont soit trop classiques, soit d'énoncé trop peu clair ou trop compliqué, soit pas intéressant (à mon goût).
Tes trois codes passent tous les tests. En particulier, il est bon de savoir qu'on utiliser des regexp.
Chouette
Bon après ça me semble quand même bizarre d'autoriser les regex dans un problème d'algorithmique comme celui-là, après je ne sais pas comment c'est noter. Mais s'ils notent juste le fait qu'on passe des tests et non la complexité (aussi bien celle en O(), que celle de la compréhension du code) de la solution je trouve ça dommage.
Pour équilibre, je suis content de mon code, je ne travaille qu'avec des entiers,
je pense que c'était l'objectif, en tout cas à mon goût.
X = Y = W = 0
for l in tab:
X += l[0]*l[2]
Y += l[1]*l[2]
W += l[2]
print X/W, Y/W
J'ai zieuté rectangles.
Je vais découper tout ça en 16*16=256 zones de largeur de quelques bits.
Puis me caler tranquillement sur chaque zone et faire du bitwiseOR.
Ça a l'air peinard, en tout cas ça me repose du Projet Euler qui devient très ardu.
EDIT : j'ai suivi le conseil donné plus bas. Merci.
---
@PsycoPy : tu n'as pas lu mes remarques ?
Tu dois vérifier que les lettres sont dans l'ordre et le bon nombre de fois !
Là c'est encore chocolat. Désolé.
J'ai revu le décryptageII (mais sans dico du tout ; en mode C)
def decryptage2(n, s1, m, s2):
tab = [0]*256
for c in s2: tab[ord(c)]+=1
s = sum(tab)
for c in s1:
i = ord(c)
if tab[i]:
tab[i]-=1
s-=1
if not s: return 1
return 0
----
@PsycoPy : essaye f("cho", "ohc"), ça doit normalement faire 0.
De plus f("cho", "chhoo") devrait aussi faire 0,
mais je parie que ton code renvoie 1. Désolé.
En revanche f("chhoo", "cho") fait bien 1.
@la Hache: je ne sais pas quel problème tu veux résoudre, mais c'est pas très beau :s Utilise plutôt forrowintab: plutôt que for_inxrange..., _ c'est utile quand tu sais que tu ne vas pas utiliser une variable, de plus on itére sur les éléments de la liste plutôt que sur l'indice en Python (et on peut utiliser enumerate au besoin).
Là je tente carré, pour entrer dans le top 10, mais mon premier algo était trop lent, il faut jouer fin avec Python.
J'ai trouvé labyrinthe très très sympa. vista est trop simple, il est surcoté.
Ensuite je taperai rectangle.
T'as de la chance moi je trouve l'énoncé pas clair du tout : c'est quoi la gauche, la droite dans le labyrinthe, déjà quand t'es en haut à gauche de la grille, (leur point de départ) c'est quoi leur mur de gauche (un mur est censé être 1) ? bref, devant ce genre d'énoncé je passe mon chemin alors que je suis sûr que c'est pas dur.
Citation : la Hache
vista est trop simple, il est surcoté.
Très classique, une fois les données capturées, ça tient en 2 lignes de Python.
Pour le labyrinthe, on doit rester dans la zone, en effet, pour y parvenir, une belle astuce est d'encadrer de '1' le labyrinthe dès la lecture ; pas de fuite possible !!!
Ensuite 10 petites lignes pour la fonction et c'est plié.
Imagine que tu avances et si ta main gauche se dérobe, alors tu tournes à gauche et tu avances, c'est tout.
Si ta main gauche ne se dérobe pas, tu tournes à droite jusqu'à ce que...
(x, y) -> (-y, x) est une astuce pour faire une rotation rapide à 90° de ton vecteur direction {(0, 1), ...}
---
Pour carré, c'est pas trivial, j'en ai posé déjà deux qui étaient trop lent, il a un intérêt. (en tout cas pour moi)
EDIT : j'ai tenté un troisième coup, il est assez rapide, mais je fais péter la mémoire à la fin !!! Presque bon !
EDIT : Ayé, j'ai bon, c'est vrai que c'était un peu classique en fait.
def f(s,t):
t = list(t)
return int(t[:]==[t.pop(0)for i in s if t and i==t[0]])
n = int(raw_input())
s = raw_input()
m = int(raw_input())
t = raw_input()
print f(s,t)
que j'ai tenté d'accélérer ...
def f(s,t):
t = list(t)
for i in s:
if i==t[0]:
t.pop(0)
if not t: return 1
return 0
n = int(raw_input())
s = raw_input()
m = int(raw_input())
t = raw_input()
print f(s,t)
finalement la plus efficace ...
def f(s,t):
i = 0
for c in t:
z = s[i:].find(c)+1
if not i: return 0
i += z
return 1
n = int(raw_input())
s = raw_input()
m = int(raw_input())
t = raw_input()
print f(s,t)
--------------------------------- edit ---------------------------------
arf, je viens de voir que PsycoPy à déjà posté quasiment la même ... en moins jolie quand même
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Python c'est bon, mangez-en.