fév.
2013
Coding challenge !
Je suis tombé hier sur un vieux challenge proposé par Cédric Beust sur son blog :
http://beust.com/weblog/2008/06/27/
Comme je suis en train d'apprendre Haskell, et que ce genre de challenge algorithmique semble particulièrement bien adapté à ce langage, je vous livre ici ma solution.
Quelle serait la vôtre ? Tous les langages sont acceptés.
(Si le code est trop long pour tenir dans un commentaire, ou si ce n'est pas pratique pour des raisons de formatage, postez-le sous la forme d'un Gist par exemple)
import Data.List -- Check for repeating digits by transforming to a string, -- then comparing to the same string without duplicate chars nonRepeating x = (show x) == (nub $ show x) -- Get non-repeating nums in the [1..n] range nrNums n = filter nonRepeating [1..n] -- Count the non-repeating nums nbNRNums = length . nrNums -- Calculate gaps between consecutive non-repeating nums -- Returns a list of triplets (number, next number, difference) gaps n = zipWith (\a b -> (a, b, b-a)) (nrNums n) (tail $ nrNums n) -- Loops over the triplets to extract the one with the greatest difference maxGap = foldl1 (\g1@(_,_,d1) g2@(_,_,d2) -> if d1>d2 then g1 else g2) -- Converts a triplet to a nice string displayGap (a,b,c) = (show a) ++ " to " ++ (show b) ++ " : " ++ (show c) main = do putStrLn $ "Number of non-repeating numbers : " ++ (show (nbNRNums 10000)) putStrLn $ "Maximum gap : " ++ displayGap (maxGap $ gaps 10000)
PS :
Grâce à la magie de Twitter et aux gens sympas et balèzes qui s'y promènent, voici des pistes alternatives pour la fonction "maxGap".
1. En utilisant maximumBy plutôt qu'un foldl brut de fonderie (merci Clément Delafargue) :
maxGap = maximumBy (\g1@(_, _, d1) g2@(_, _, d2) -> compare d1 d2)
2. En utilisant la fonction "on" fournie par Data.Function (merci Julien Tanguy) :
maxGap = maximumBy (compare `on` trd) where trd (_,_,x) = x
Commentaires
J'aurais globalement le même code sauf pour maxGap où j'aurais utilisé maximumBy à la place d'un fold explicite.
function counter($max,$start=0){
$values = range($start,$max); $values = array_filter($values,function($value){ $ar_string = str_split($value); $valid = array_unique($ar_string) == $ar_string; return $valid; }); return $values;}
counter(10000);
J'ai pas fait le compteur pour le plus grand gap mais l'algo globale est là ^^
Sympa ce petit challenge, le voici en Objective Caml (avec Batteries).
<code>
(* Test whether a number have repeating digits *)
let no_repeat n = let d = String.to_list n in List.length(List.unique d) == List.length d;;
(* Get the max gap *)
let max_gap l = let x = ref 0 in List.max (List.map (fun e -> let r = e - !x in (x := e; r)) l);;
(* solve *)
let () = let range = 1..10000 in
let filtered = List.filter no_repeat range in List.iter (Printf.printf "%d, ") filtered; (* print numbers *) Printf.printf "Number: %d" (List.length filtered); (* print max number *) Printf.printf "Max Gap: %d" (max_gap filtered) (* print max gap *);;
Voir le Gist ici: https://gist.github.com/agrison/496...
My clojure implementation on https://gist.github.com/error3/4991...
Bien joué pour toutes ces implémentations !
J'arrive à décrypter la version Clojure, mais pfiou, je trouve que la syntaxe est très pénible à lire. Il y a une grosse soupe de parenthèses, accolades et crochets, et il n'est pas simple (pour un oeil non-averti) de distinguer la fonction de chacun.
Je trouve celle d'OCaml plus compréhensible par exemple, et pourtant je n'en ai jamais fait. C'est dommage, je pense que ça ne donne pas aux Javaistes l'envie de se mettre aux langages fonctionnels...
Salut Olivier
Si tu lances la génération avec un maxmum de 10 chiffres, combien de temps est-ce que cela prend ? Combien de nombres est-ce que tu trouves ?
Voilà une implémentation en Java, un poil plus verbeuse que les vôtres, mais aussi plus rapide : https://github.com/pingtimeout/chal...
Effectivement ma version n'est pas terrible au niveau des perfs, et prend déjà 400ms pour 10^6 nombres. Mais ce n'était pas mon but premier : je suis encore débutant en Haskell.
Si tu es intéressé par les perfs, sur son challenge originel, Cédric a reçu des solutions très ingénieuses et très rapides... Voir : http://beust.com/weblog/2008/08/28/...
Edit :
Bon, presque 10 minutes pour 1 milliard de nombres vérifiés, ça raaaame ^^;
@Olivier pour clojure, j'aurais fait la même remarque pour Haskell.
Je trouve ça complexe à lire... La syntaxe semble inutilement complexe.
Comme tu le dis, je pense que c'est une question d’œil avertis ou pas.
Après, je débute juste en Clojure, j'ai commencé il y a moins d'un mois.
Donc peut-être que je ne fais pas encore de code très lisible.
J'ai essayé d'améliorer un peu la chose
https://gist.github.com/error3/4991...
puis
https://gist.github.com/error3/4991...
C'est mieux? :-)