Sudoku

Résolveur de Sudoku en C++

Je souhaite vous faire profiter d’un petit projet personnel que j’avais réalisé en 2006 : un résolveur de sudoku (9×9) en C++. Vous trouverez dans l’archive :

  • les sources,
  • quelques grilles,
  • le fichier de projet Dev-C++.

Les grilles à résoudre sont représentée dans les fichiers par une suite de chiffre qui peuvent être mis en forme (les caractère qui ne sont pas numériques sont ignorés, les zéros représentent les inconnues). Les deux exemples suivants sont deux représentations de la même grille :

  • 907500006006009007001002000
    000004130000000000038090000
    004700200500400800070003605
  • 9 0 7|5 0 0|0 0 6
    0 0 6|0 0 9|0 0 7
    0 0 1|0 0 2|0 0 0
    -----------------
    0 0 0|0 0 4|1 3 0
    0 0 0|0 0 0|0 0 0
    0 3 8|0 9 0|0 0 0
    -----------------
    0 0 4|7 0 0|2 0 0
    5 0 0|4 0 0|8 0 0
    0 7 0|0 0 3|6 0 5

Je sais qu’il existe déjà plein de résolveurs sur le Web mais celui là, il pense comme moi 🙂 : il applique mes méthodes de résolutions et il se trouve bloqué au mêmes endroits que moi sur les grilles complexes…

Télécharger le résolveur (version 0.0.1)

Creative Commons GNU GPL

Programme sous Creative Commons GNU GPL

Google Reader

Filtrez vos flux RSS avec ce qui vous intéresse

Pour quoi faire ?

J’utilise pas mal les flux RSS pour me simplifier certaines choses. Comme par exemple l’arrivée d’un nouvel épisode d’une des séries que je suis. Un de mes « problèmes » était que je recevais des actualités dont je n’avais rien à faire. Je me suis donc créé un petit outil PHP qui récupère les flux RSS de différents sites, les filtre et les regroupe en un seul.

Comment ça marche ?

Il y a deux moyens d’utiliser cet outil.

Première utilisation

Avec des paramètres GET :

  • feeds : la liste des flux séparés par une virgule.
  • filters : la liste des filtres d’inclusions aussi séparés par une virgule.
  • excludes (optionnel) : encore une liste séparée par des virgule pour forcer l’exclusion d’items qui sont passés.
  • debug  (optionnel) : pour recevoir dans le flux généré les erreurs qui se sont produites.

Exemple :

http://example.com/rss-filter/rssfilter.php?feeds=http://www.toto.com/rssfr.xml,http://www.tata.fr/rss.xml&filters=CSI,CSI Miami,House&exclude=Desperate&debug=1

Deuxième utilisation

Avec un fichier XML dans le sous dossier files qui contient la configuration. Les filtres sont des expréssions régulières. Exemle de fichier XML :

http://example.com/rss-filter/files/series.xml

<!--?xml version="1.0" encoding="UTF-8" ?-->
 
	[EZTV+VTV+subs] Filtrés
	Séries : Dexter, Dirty Sexy Money, Fringe, Grey's Anatomy, Heroes, House, How I Met Your Mother, Lost, My Name Is Earl, Naruto Shippuuden, The IT Crowd, The United State Of Tara, True Blood, Weeds.
 
		<!-- sous titres -->
		http://www.tvsubtitles.net/rssfr.xml
		http://www.sub-way.fr/rss.xml
		http://feeds.feedburner.com/seriessub
		<!-- séries -->
		http://www.mininova.org/rss.xml?user=VTV
		http://www.mininova.org/rss.xml?user=EZTV
		<!-- naruto -->
		http://www.dattebayo-fr.com/rss-news.php
 
		/\bDexter\b/i
		/\bDirty Sexy Money\b/i
		/\bFringe\b/i
		/\bGrey'?s? Anatomy\b/i
		/\bHeroes\b/i
		/\bHouse\b/i
		/\bHow I Met Your Mother\b/i
		/\bLost\b/i
		/\bMy Name Is Earl\b/i
		/\bNaruto Shippuuden\b/i
		/\bThe Mentalist\b/i
		/\bThe IT Crowd\b/i
		/\bSons of Anarchy\b/i
		/\bUnited States Of Tara\b/i
		/\bTrue Blood\b/i
		/\bWeeds\b/i
 
		/\bCrooked House\b/i
		/\bDesperate Housewives\b/i
		/\bx264\b/i

Le flux correspondant sera disponnible comme ceci :

http://example.com/rss-filter/rssfilter.php?file=series

http://example.com/rss-filter/rssfilter.php?file=series&debug=1 (pour avoir le debug en plus)

Installation

Votre navigateur risque d’essayer de parser le fichier rssfilter.txt en tant que flux RSS.

Posez le fichier rssfilter.php sur un serveur Web qui dispose de :

  • PHP 5,
  • la fonction file_get_contents,
  • L’extension SimpleXML.

Télécharger rssfilter.php

Questions ?

En cas de problème n’ésitez pas à me poser des questions dans les commentaire 😉

Creative Commons GNU GPL

Programme sous Creative Commons GNU GPL

Taquin

Résolveur de taquin

Je ne sais pas si quand vous vous lancez dans une énigme et que vous ne trouvez pas la solution, vous finissez par juste vouloir la réponse pour passer à autre chose. Ce fût mon cas récemment avec : l’énigme 135 du jeu Professeur Layton et l’étrange village sur Nintendo DS.

Quand je suis bloqué comme ça, j’aime pas non plus qu’on me donne la solution bêtement. Je préfère un compromis (un peu geek certe) : faire un programme qui va résoudre l’énigme à ma place.

Solution

Pour ceux qui viennent de Google et qui en ont rien à faire de mon code, la liste des étapes pour résoudre l’énigme est là :

Solution énigme 135

Pour comprendre la représentation du taquin :

Énigme 135

<->
<><>@
12^@
34v@
<><>@

Code

Pour ceux qui sont intéressés par comment j’ai fait, voici une brève explication :

  1. Il y a trois listes importantes : celle des taquins générés, celle des taquins à explorer et celle des taquin qui sont dans la position finale (juste avant la sortie).
  2. On insère la position de départ dans les listes.
  3. On explore : c’est à dire qu’on génère tous les taquins possibles à partir d’un autre.
  4. Les nouveaux taquins ne doivent pas correspondre à  un autre déjà existant. Si ce n’est pas le cas, on ajoute le nouveau à la liste des taquins trouvés et à celle à explorer.
  5. Si certains sont en position finale on les ajoute à la liste de taquins finaux.
  6. Si il y a un taquin (ou plus) dans la liste à explorer, on prend le premier et on retourne à l’étape 3.
  7. Quand il n’y a plus rien à explorer, c’est qu’on a fait le tour des possibilités de mouvements. On prend le premier des finaux et on affiches les étapes qui ont conduit à sa création.

Défauts du scripts :

  • La représentation du taquin est un tableau de caractère ce qui n’est pas très propre mais ça marche.
  • La méthode n’est pas très intelligente, c’est du brute force qui tâche mais pour une fois j’ai fait un brute en itératif et non en récursif.
  • Les solutions ne sont pas forcement les plus courtes.

Pour le dernier point, j’essairai d’y remédier si j’en ai la motivation car ça va prendre du temps (pour rien, ça on peut le dire).

Voici la source du programme, c’est du python.

enigme-135.py

Creative Commons GNU GPL

Programme sous Creative Commons GNU GPL

Taquin

Utilisation avancée de file_get_contents (PHP)

Préambule

Je fais cette note technique car je me suis plus d’une fois confronté à différentes configurations pour accéder à une page Web à partir de PHP. Normalement un serveur Web dispose d’une connection directe à internet et n’a pas besoin d’un proxy pour y acceder. Mais si on fait des script PHP en CLI (non liès à un serveur Web) on peut se trouver confronter à différents problèmes…

Cas 1 : la simplicité même

Voici le cas le plus simple pour récupérer un page à partir de son URL. Dnas le cas où PHP dispose d’un accès direct à internet.

HTTP

$content = file_get_contents("http://www.google.com/");

HTTPS

$content = file_get_contents("https://www.google.com/");

Si il vous manque l’extension open_ssl vous aurez une erreur dans ce genre :

Notice: file_get_contents(): Unable to find the wrapper "https" - did you forget to enable it when you configured PHP? in ...\test_001.php on line 3

Warning: file_get_contents(https://www.google.com/): failed to open stream: Invalid argument in ...\test_001.php on line 3

C’est aussi valable pour les cas suivants.

Cas 2 : Authentification HTML

Si la page est protégée par un mot de passe, PHP peut transformer une URL avec utilisateur et mot de passe pour envoyer la requête avec les bons headers.

HTTP

$content = file_get_contents("http://user:pass@www.example.com/");

HTTPS

$content = file_get_contents("https://user:pass@www.example.com/");

Méthode alternative

Vous pouvez aussi envoyer vous même les headers contenant mots de passe et utilisateur. C’est plus compliqué mais ça marche aussi.

// URL des données à récupérer
$url = 'http://protectedstuff.com';
// Encodage de l'autentification
$auth = base64_encode('user:password');
// Création des options de la requête
$opts = array(
	'http' => array (
		'method'=>'GET',
		'header'=>"Authorization: Basic $auth"
	),
	'https' => array (
		'method'=>'GET',
		'header'=>"Authorization: Basic $auth"
	)
);
// Création du contexte de transaction
$ctx = stream_context_create($opts);
// Récupération des données
file_get_contents($url,false,$ctx);

Source : http://fr.php.net/manual/fr/function.stream-context-create.php#74431

Cas 3 : En passant par un proxy

Il m’est arrivé d’écrire des script en PHP-CLI qui se retrouvaient bloqués par un proxy.

HTTP ou HTTPS

// URL des données à récupérer
$url = 'https://www.google.com/';
// Création des options de la requête
$opts = array(
	'http' => array (
		'proxy'=>'tcp://192.168.0.99:3128',
		'request_fulluri' => true
	),
	'https' => array (
		'proxy'=>'tcp://192.168.0.99:3128',
		'request_fulluri' => true
	)
);
// Création du contexte de transaction
$ctx = stream_context_create($opts);
// Récupération des données
$content = file_get_contents($url,false,$ctx);

Cas 4 : Proxy et page avec authentification HTML

Si en plus la page que vous souhaitez télécharger requière une authentification, cela reste simple.

HTTP ou HTTPS

// URL des données à récupérer
$url = 'https://user:pass@www.example.com/';
// Création des options de la requête
$opts = array(
	'http' => array (
		'proxy'=>'tcp://192.168.0.99:3128',
		'request_fulluri' => true
	),
	'https' => array (
		'proxy'=>'tcp://192.168.0.99:3128',
		'request_fulluri' => true
	)
);
// Création du contexte de transaction
$ctx = stream_context_create($opts);
// Récupération des données
$content = file_get_contents($url,false,$ctx);

Cas 5 : Proxy avec authentification

Dans certaines entreprises ou administration on peut se trouver derrière un proxy qui filtre les utilisateurs. Voici comment faire passer son script.

HTTP ou HTTPS

// URL des données à récupérer
$url = 'http://www.example.com/';
// Encodage de l'autentification
$authProxy = base64_encode('user:pass');
// Création des options de la requête
$opts = array(
	'http' => array (
		'method'=>'GET',
		'proxy'=>'tcp://192.168.0.99:3128',
		'request_fulluri' => true,
		'header'=>"Proxy-Authorization: Basic $authProxy"
	),
	'https' => array (
		'method'=>'GET',
		'proxy'=>'tcp://192.168.0.99:3128',
		'request_fulluri' => true,
		'header'=>"Proxy-Authorization: Basic $authProxy"
	)
);
// Création du contexte de transaction
$ctx = stream_context_create($opts);
// Récupération des données
$content = file_get_contents($url,false,$ctx);

Cas 6 : Proxy avec authentification et page avec authentification

Voici un des cas les plus complexes lorqu’il est question de récupérer des données. J’ai rencontré ce problème lorsque j’ai fait un script pour récupérer mes logs chez OVH.

HTTP ou HTTPS

// URL des données à récupérer
$url = 'https://user:pass@www.example.com/';
// Encodage de l'autentification
$authProxy = base64_encode('user:pass');
// Création des options de la requête
$opts = array(
	'http' => array (
		'method'=>'GET',
		'proxy'=>'tcp://192.168.0.99:3128',
		'request_fulluri' => true,
		'header'=>"Proxy-Authorization: Basic $authProxy"
	),
	'https' => array (
		'method'=>'GET',
		'proxy'=>'tcp://192.168.0.99:3128',
		'request_fulluri' => true,
		'header'=>"Proxy-Authorization: Basic $authProxy"
	)
);
// Création du contexte de transaction
$ctx = stream_context_create($opts);
// Récupération des données
$content = file_get_contents($url,false,$ctx);

Conclusion

Les exemples présentés ne se limitent aux cas typique de récupération de pages distantes. Ces cas seront satisfaisant dans la plupart des cas. Si vous rencontrez un cas non décrit dans cet article vous trouverez peut être de l’aide ici. Et si vous avez toujours des problèmes vous pouvez me demander de l’aide dans les commentaires. 😉

Internet

Fréquentation de mon site web

Je viens de jeter un coup d’oeil dans le logs bruts d’Apache et je suis tombé sur :

proxy.kunsan.af.mil pas-bien.net – [19/Dec/2007:17:53:49 +0100] « GET /rbproxy/ HTTP/1.1 » 200 33737 « http://www.google.com/search?q=Radioblog+Proxy » « Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET CLR 1.1.4322; InfoPath.1; .NET CLR 2.0.50727) »

Du coup qu’est ce que af.mil ? Une recherche sur Google : l’Air Force des États Unis.

Mais Kunsan, c’est une base ? Ben oui et après une petite recherche, une base en Corée du sud.
Agrandir le plan

Ca doit ceux qui viennent le plus loin sur mon site.