Vous aimez ce que vous lisez sur ce blog ?
Envie d'aller plus loin avec véritable formation d'expertise en Java ?
Venez suivre ma formation Masterclasse Expertise Java !

"Même un développeur experimenté a besoin de continuer à apprendre. Et dans cette formation... j'ai appris beaucoup !" - A.G., Java Champion

Prochaines sessions inter-entreprises : 28-31 mars 2017 / 13-16 juin 2017
Sessions intra-entreprises sur demande.
Inscrivez-vous vite !

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

1. Le jeudi 14 février 2013, 13:57 par Clément

J'aurais globalement le même code sauf pour maxGap où j'aurais utilisé maximumBy à la place d'un fold explicite.

2. Le jeudi 14 février 2013, 15:20 par Airmanbzh

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à ^^

3. Le vendredi 15 février 2013, 18:22 par Alexandre

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

4. Le mercredi 20 février 2013, 00:45 par error3

My clojure implementation on https://gist.github.com/error3/4991...

5. Le mercredi 20 février 2013, 09:39 par Olivier Croisier

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

6. Le vendredi 22 février 2013, 14:20 par Pierre Laporte

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

7. Le vendredi 22 février 2013, 14:35 par Olivier Croisier

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 :
time ./challenge 1000000000
Nb NR Nums : 5611770
real	9m23.835s
user	9m21.660s
sys	0m1.107s

Bon, presque 10 minutes pour 1 milliard de nombres vérifiés, ça raaaame ^^;

8. Le dimanche 24 février 2013, 15:06 par error3

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

Ajouter un commentaire

Le code HTML est affiché comme du texte et les adresses web sont automatiquement transformées.