meven's blog

Aller au contenu | Aller au menu | Aller à la recherche

dimanche 8 janvier 2017

Yet another sudoku solver, in rust

I have been quite interested recently with the new languages Go and rust. Go and rust have some very nice new features and their design and tooling reflects the standards of this days. So I have been hacking with go and rust.

I share this piece of rust code that solves sudoku, in the hope it will be useful to someone. It is not very much optimized as the algorithm is naive, but the purpose of this code was to get more comfortable with rust.


fn print_grid(g: [Option<i32>; 81]) {

    let mut cnt = 0;
    let mut line = 0;

    for &x in g.iter() {

        cnt = cnt + 1;

        match x {
            Some(i) => print!("{}", i),
            None => print!("_"),
        }

        if cnt == 9 {
            line = line + 1;
            println!("");
            cnt = 0;
            if line == 3 {
                line = 0;
                println!("");
            }
        } else if cnt % 3 == 0 {
            print!("   ");

        } else {
            print!(" ");
        }
    }
}

fn check_grid(g: [Option<i32>; 81]) -> bool {

    // check lines
    for x in 0..9 {
        let i = 9 * x;
        let val = [i, i + 1, i + 2, i + 3, i + 4, i + 5, i + 6, i + 7, i + 8];

        for v in 0..(val.len() - 1) {
            let valv = g[val[v]];
            if valv != None {
                for c in 1..val.len() {
                    let valc = g[val[c]];
                    if valc != None && val[v] != val[c] && valv == valc {
                        // println!("Block false at {}", x);
                        return false;
                    }
                }
            }
        }
    }

    // check columns
    for x in 0..9 {
        let val = [x, x + 9, x + 18, x + 27, x + 36, x + 45, x + 54, x + 63, x + 72];

        for v in 0..(val.len() - 1) {
            let valv = g[val[v]];
            if valv != None {
                for c in 1..val.len() {
                    let valc = g[val[c]];
                    if valc != None && val[v] != val[c] && valv == valc {
                        // println!("Block false at {}", x);
                        return false;
                    }
                }
            }
        }
    }

    // check blocks
    for x in 0..9 {
        let mut i = 3 * (x % 3);
        if x > 2 {
            i = i + 27;
        } else if x > 5 {
            i = i + 54;
        }

        let val = [i, i + 1, i + 2, i + 9, i + 10, i + 11, i + 18, i + 19, i + 20];

        for v in 0..(val.len() - 1) {
            let valv = g[val[v]];
            if valv != None {
                for c in 1..val.len() {
                    let valc = g[val[c]];
                    if valc != None && val[v] != val[c] && valv == valc {
                        // println!("Block false at {}", x);
                        return false;
                    }
                }
            }
        }
    }

    return true;
}

fn is_grid_complete(g: [Option<i32>; 81]) -> bool {
    let mut ret = true;
    for &x in g.iter() {
        match x {
            Some(_) => {}
            None => {
                ret = false;
                break;
            }
        }
    }
    return ret;
}

fn clone_grid(g: [Option<i32>; 81]) -> [Option<i32>; 81] {
    let mut new_g: [Option<i32>; 81] = [None; 81];
    for x in 0..g.len() {
        new_g[x] = g[x];
    }
    return new_g;
}


fn solve_grid(g: [Option<i32>; 81]) -> Option<[Option<i32>; 81]> {

    if is_grid_complete(g) {
        return Some(g);
    }

    for x in 0..g.len() {
        match g[x] {
            Some(_) => {}
            None => {

                let mut checked: [bool; 9] = [false; 9];

                for v in 1..10 {

                    let mut new_g = clone_grid(g);
                    new_g[x] = Some(v);

                    checked[(v - 1) as usize] = true;

                    if check_grid(new_g) {
                        match solve_grid(new_g) {
                            None => {
                                if checked == [true; 9] {
                                    // the path is a dead end
                                    return None;
                                } else {
                                    continue;
                                }
                            }

                            Some(gx) => return Some(gx),
                        }
                    }
                }

                if checked == [true; 9] {
                    // Detected a dead end
                    return None;
                }
            }
        }
    }

    return None;
}

fn parse_grid(grid_string: &str) -> [Option<i32>; 81] {
    let mut grid = [None; 81];

    let mut i = 0;
    for s in grid_string.split_whitespace() {
        match s {
            "_" => {}
            val => {
                grid[i] = Some(val.parse::<i32>().unwrap());
            }
        }
        i = i + 1;
    }

    return grid;
}

fn main() {
    let grid_string = r#"
            1 _ _   _ _ _   _ _ 3
            _ 4 _   _ _ 9   2 6 _
            _ _ _   7 _ _   _ 5 4

            _ _ _   1 7 _   9 _ _
            _ _ 2   _ _ _   6 _ _
            _ _ 3   _ 9 5   _ _ _

            2 7 _   _ _ 1   _ _ _
            _ 8 9   3 _ _   _ 7 _
            6 _ _   _ _ _   _ _ 2"#;

    let grid: [Option<i32>; 81] = parse_grid(grid_string);

    print_grid(grid);

    match solve_grid(grid) {
        Some(g) => {
            println!("Grid complete !");
            print_grid(g)
        }
        None => println!("Couldn't solve the sudoku"),
    }

}

You can just, given you have installed rust.

cargo build

mercredi 19 novembre 2008

La main Visible par Dale Dougherty

Je suis tombé sur cette article http://radar.oreilly.com/2008/11/th... via http://standblog.org/blog/post/2008....

Je le trouve assez intéressant pour avoir envie de le traduire en partie. Morceau choisit traduit par mes soins. Je vous recommande la lecture de l'article original pour éviter les contre sens qui m'ont certainement échappés, mais en substance l'idée devrait être là.
Dale Dougherty de O'Reilly radar :

(Après un tiers de l'article)
C'est dur d'encaisser que notre gouvernement doive payer la note de Wall Street. Cela signifie que nous parions notre future sur les mêmes personnes qui ont ont créées cette situation. Pour paraphraser une blaque que j'ai entendu : C'est comme aller au casino à Vegas en jouant sa maison. Un lecteur du New York Times a exprimé la frustration que beaucoup ont ressentis: "Pourquoi ont ne peut pas prendre la moitié des 700 milliard et simplement construire quelque chose ?" Ces évènements secouent notre croyance que les marchés libres fonctionne pour le bien de tous. Le dogme fondamental du capitalisme est la "main invisible": Adam Smith a écrit que "En cherchant son propre intérêt chaque personne soutient fréquemment celui de la société". Cette année, le prix nobel d'économie Joseph Stiglitz a déclaré: "Dans un sens, la chute de Wall Street est pour le fondement de l'économie de marché ce que la chute du mur de Berlin fut pour le communisme - cela nous apprend que ce système économique n'est pas viable."
Un gros titre dans le Christian Science Monitor (www.csmonitor.com) affirmait: "Avec la crise financière, finit l'ère du laissez faire." Le gouvernement aura besoin d'être plus ferme dans la régulation de Wall Street. Mais je pense que cela va plus loin que ça. Je me demande si, en tant qu'individus, nous avons pas été dans une ère laisser faire. Est ce que nous américains, sommes devenus dépendant d'une force invisible pour subvenir à nos besoins ? Nous sommes nous habitués à laisser les questions importantes à des experts, jusqu'à ce qu'il s'avère qu'ils se trompent ?
N'est il pas tant que nous reprenions le contrôle ?
Nous, les gens, faisons face à d'énormes défis. En plus du bazar économique, des changements fondamentaux arrivent du fait du réchauffement climatique. Notre dépendance au fuel fossile n'est pas viable. Le changement arrive, que l'on le veille ou non.
Nous ferions bien de ne pas nous voiler la face et d'affronter ces défis. Un journaliste du New York Times l'a résumé ainsi: "Nous avons besoin de recommencer à fabriquer des choses, basé sur de l'ingénierie réel, pas seulement sur de l'ingénierie financière. Nous devons retourner à un monde où les gens sont capables de réaliser le rêve américain - une maison avec un jardin - grâce au travail de leur main et non pas grâce à un "prêt menteur" ... Le rêve américain est une aspiration, pas un droit."
Nous devons nous convaincre que ça commence par chacun d'entre nous - pas un gouvernement anonyme ou une bureaucratie d'entreprise. Il est temps pour nous, individuellement et en travaillant ensemble, de reconsidérer ce que "être productif" veut dire, pas seulement rentable. Il est temps pour nous de nous impliquer à nouveau dans les priorités de notre gouvernement en matière d'éducation, de santé, de logement et de transport.
Le paradigme du "Do it yourself" (Fais le toi-même) promu dans ce magazine dois à nouveau devenir un compétence essentiel basée sur la nécessité et la pratique. Notre sécurité futur dépend de la connaissance de notre capacité à créer et comment nous savons nous adapter au changement en faisant preuve de ressource.
Un défi aussi grand peut faire ressortir le meilleur de nous. On a besoin de tout le monde, parce que tout le monde a une sa contribution à apporter. Nous avons besoin de toutes les bonnes volontés.

dimanche 24 août 2008

Meizu M6 par Danelec : avec la radio FM s'il vous plaît

meizu m6

Si comme moi, vous possédez un "meizu by Danelec", voici un truc qui pourrait vous servir. Le meizu m6 (de son vrai nom) ne possède pas de tuner FM. Et bien Si en réalité ! Pour s'en convaincre il suffit d'installer le firmware original, de la version SP du baladeur (disponible là bas) du constructeur.

Après la mise à jour, vous aurez un nouveau onglet "FM Tuner" :p

mercredi 9 juillet 2008

L'ipod est mort, vive le miniPlayer

ipod_mort.jpg

Mort de mon ipod

A bout de 2 dans de bons et loyaux services mon ipod 4G 40Go est mort. Cela faisait en réalité presque 4 ans que j'avais un ipod 4G, grâce à une extension de garantie, J'avais pu l'échanger quand j'ai eu des pépins. Le baladeur à disque dur, c'est pas fait pour moi, trop fragile. Du coup il a fallu que je retrouve un baladeur et vite. meizu m6

Meizu miniPlayer m6

Je m'étais toujours dit que je me rachèterais un ipod, car certes c'est cher mais il y a pas mieux en particulier en matière d'ergonomie. Mais grâce aux commentaires de ce billet, j'ai trouvé baladeur à mes oreilles. Un meizu m6 fabriqué en Chine comme les ipods moins l'hypocrite "Designed in California" gravé au dos quand même.
Très sympa, moins ergonomique qu'un ipod certes mais avec plus de fonctionnalités (support du ogg flac et du xvid en particulier), un grand écran et un prix, tout petit, 100€ pour la version 8 Go.

Le m6 est bien plus pratique qu'un ipod dès lors qu'il s'agit d'ajouter de la musique, ou communiquer avec un PC, puisqu'avec lui, je n'ai plus besoin spécialement besoin d'un gestionnaire de musique pour ajouter de la musique. Fini les cables très cher, spéciaux pour ipod. Avec le meizu plus de tracas, un cable pour Appareil photo numérique suffit, en plus ça tombe bien, j'ai deux PC et deux cables, du coup fini les passages du cable d'un PC à l'autre...
Ce petit baladeur est parait-il populaire en Chine.

Rockbox

boite_a_musique.jpg

J'avais pu testé Rockbox sur feu ma "boîte à musique".
Rockbox est un firmware alternatif libre, qui supporte une trentaine de modèles de baladeurs et qui présente l'avantage d'avoir beaucoup de fonctions en plus comparés aux firmwares par défaut des baladeur.

C'est particulièrement vrai avec un ipod, qui ne supporte que quelques formats audio(3 il me semble), quand Rockbox supporte tous les principaux, dont le ogg, le flac.

Et la bonne nouvelle c'est que un port de Rockbox sur meizu m6 est en cours.

dimanche 23 mars 2008

Changement de thème pour Meven's blog, Enfin !

Je me suis décidé à franchir le pas et a adopté un thème déjà "prêt-à-thémer". Grâce à gandi et à son thème Blowup, en trois clics on obtient un thème simple à personnaliser. On peut changer la bannière, les tailles de police et les couleurs. Le tout très simplifient par le biais d'une interface web. Pour mémoire, mon blog ressemblait à cela avant : old theme Un thème créé par mes soins mais n'ayant pas rencontré son public mais plutôt ses critiques ! J'espère que ce nouveau thème rendra la lecture de mon blog plus agréable ;) .

lundi 27 août 2007

La difficulté de choisir un ultra-portable

Je vais bientôt m'acheter un ordinateur, un portable cette fois.
Je privilégie la mobilité et l'autonomie avant tout. Je me tourne donc vers la catégorie dite des ultra-portable. Ca tombe bien, ils sont devenus abordables, l'entrée de gamme est devenue moins chère, 1000€ environ pour mon plus grand bonheur. Etant étudiant je ne peut pas me permettre d'investir plus de toute façon.
J'ai fait des recherches sachant que j'ai des critères particuliers :

  • Intel Core 2 Duo architecture Santa Rosa, je veux du dernier cri
  • chipset graphique Intel X3100, le meilleur chipset pour linux (driver libre :D) et moins gourmand en énergie que les chipsets dédiés
  • un zolie objet tant qu'à faire, l'esthétique compte
  • bonne compatibilité avec linux
  • dépourvu de Vista et des logiciels maisons des constructeurs souvent médiocres pour économiser le coût des logiciels dont je ne veux pas.

Malheureusement pour ce dernier point je crains ne pouvoir le réaliser bien que la loi me protège de tels abus encore faudrait il qu'elle soit appliquée.
Il y a quelques modèles qui remplissent mes deux premiers critères en revanche pour les autres, c'est mitigé. J'ai notamment:

  • le dell XPS 1330M, très bel objet très soigné, à même un télécommande intégré ! Rempli les quatre premier critères, bien que pour installer linux quelques manipulations soient nécessaire. Et en plus c'est un dell (voire mon éloge de dell) même si celui ci n'est à priori pas disponible sans Vista.xps1330m

Malheureusement le tableau n'est pas si idyllique que ça : il est cher à niveau d'équipement équivalent à ses concurrents, et surtout il a des retards énormes, compté un mois et demi au moins pour se le faire livrer ! Dell s'en excuse, n'empêche que ça emmerde du monde. Dell a quand même le mérite de faire de la communication sur le sujet, encore un exemple à suivre pour les autres constructeurs.

  • l'ASUSTeK A8E-4P014C, qui offre toutes les conditions, un meilleur processeur que le dell, seul bémol un écran 14', 13.3' me suffisent amplement, résultat il est un peu lourd 2,4kg. En prime on a sacoche et souris inclus. Seul hic délai de au moins 30 jours, cela reste moins que pour dell ou bien sans délai mais sans la saccoche et la souris.
  • le TOSHIBA Satellite U300-11Q remplit les trois premiers critères au moins, idéal dans les spécifications : écran 13.3', un processeur T5250 mieux que celui du dell mais moins bien que le asus, un peu moins joli que les autres peu être.

Deux regrets sur ces offres :

  1. aucune n'incluent 2Go de mémoire vive dommage
  2. aucune n'est disponible sans Vista (autant que je sache) prépayé, pré-installé et pré-encrassés par les softs maisons des constructeurs. J'aurais bien voulu voir le choix et économiser les 50 à 100€ que ces logiciels représentent pour le prix achat.

Prochain épisode dans un mois environ quand l'heure sera venue de passer à la caisse. Les choses auront certainement évoluées en particulier pour les délais du dell et de l'asus. SI quelqu'un a vu une offre qui m'a échappé et remplissant mes critères qu'il n'hésite pas à laisser un commentaire.

jeudi 26 juillet 2007

Chronique d'un sauvetage d'ipod

sad_ipod.gifCe n'est pas la première fois que j'ai à faire a des problèmes hardware avec mon ipod, je pourrais même dire que je suis un habitué : remplacé deux fois, merci au service après vente d'apple et au programme applecare.
Mon bon vieux ipod 4G me faisait drolement peur depuis que l'icône de l'ipod triste apparaissait à l'écran. Surtout que je savais qu'il avait pris un joli coup après une chute très récemment. J'ai bien cru que c'était la fin (à nouveau).
Je me retrouvais au pied du mur, complètement addicte au meilleur des balladeurs mp3. Il allait falloir m'en acheter un nouveau.
J'aurais opté pour un nano 8Go plus petit et plus costaud que mon 4G avec son gros disque dur si fragile. Mais à 259€, je le trouve vraiment trop cher, franchement apple abuse. Mais avec une concurrence aussi impuissante à proposer un produit qui tienne la route, rien ne pousse apple à réduire ses marges.
J'ai donc décidé le tout pour le tout : réparer moi-même.
J'ai trouvé un bon howTo dans la langue de Shakespierre.
Je l'ai suivi, ouvrir l'ipod, en sortir le disque...
IMG_3547.JPG Je récupère le nom du modèle du disque dur : MK4006GAH. Je cherche le modèle ou un équivalent. Malheureusement en France ça semble ou dur à trouver ou bien plus cher que je ne l'espérais ( premier prix vers 135€).
Alors je me dis et pourquoi pas tester le disque, ça ne mange pas de pain, je rebranche le disque dur et comme par magie, le disque repart, avec toutes mes données, alors même que l'ipod était encore ouvert !
Je referme tout ça, depuis ça roule comme sur des roulettes.
Conclusion: encore un happy ending à l'américaine ;)

dimanche 3 juin 2007

L'ujap Quimper en final de pro B à Bercy

Veni, Vidi, perdi Le petit club de Quimper arrivé il y a trois saisons en PRO B, se rêve de PRO A. Seulement voilà, Vichy était trop fort, ils l'ont emporté et montent en PRO A.

Lire la suite...