Solutions au problème de labyrinthe de mamund

+

Python

Le code est là.

Il vous faut le module httplib2.

Pour le lancer python maze.py http://amundsen.com/examples/mazes/2d/five-by-five/.

')

Je suis plus dhumeur «fonctionnelle» en ce moment

')
Maze en Python (maze.py)
    1 #!/bin/env python
    2 # Python solution to mamund's maze problem (functional style)
    3 # see http://amundsen.com/examples/misc/maze-client.html
    4 
    5 from xml.etree.ElementTree import XML
    6 from httplib2 import Http
    7 
    8 MAZE = "http://amundsen.com/examples/mazes/2d/five-by-five/"
    9 RULES = {
   10     'east'  : ['south','east','north','west'],
   11     'south' : ['west','south','east','north'],
   12     'west'  : ['north','west','south','east'],
   13     'north' : ['east','north','west','south']
   14 }
   15 
   16 def get(uri):
   17     """ return the XML from the given uri """
   18     resp, content = Http().request(
   19                       uri,
   20                       headers={
   21                         'Accept':
   22                           "application/vnd.amundsen.maze+xml"})
   23     return XML(content)
   24 
   25 def get_links(uri):
   26     """ 
   27     return a dict {rel: href} of the <link>s found at the given uri
   28     """
   29     return dict(
   30          (link.get('rel'), link.get('href')) 
   31          for link in get(uri).findall('*/link')
   32         )
   33 
   34 def selector(rules):
   35     """
   36     a little closure to create the next-link selector based on the 
   37     given rules
   38     """
   39     def select(facing, links):
   40         """
   41         app logic:
   42         given the current facing direction and the available links,
   43         chooses the next direction (according to the rules),
   44         follows the link and return the new facing direction and the 
   45         available links for the current state
   46         """
   47         if facing is None and 'start' in links:
   48             return ('north', get_links(links['start']))
   49         if 'exit' in links:
   50             return ('exit', get_links(links['exit']))
   51         for choice in rules[facing]:
   52             if choice in links:
   53                 return (choice, get_links(links[choice]))
   54     return select
   55 
   56 def find_path(maze, rules):
   57     """ 
   58     just follow the links until exit, yielding the current state 
   59     """
   60     select_next = selector(rules)
   61     facing, links = None, get_links(maze)
   62     while facing is not 'exit':
   63         facing, links = select_next(facing, links)
   64         yield (facing, links)
   65 
   66 if __name__ == '__main__':
   67     import sys
   68     if len(sys.argv) == 2:
   69         maze = sys.argv[1]
   70     else:
   71         maze = MAZE
   72     for step, (facing, links) in enumerate(find_path(maze, RULES)):
   73         print "%s: go to %s"  % (step, facing)
   74         print "    <%s>" % (links.get('current', ''),)
   75     print "I'm free !"
   76
+

Bash

(et grep, sed, curl...)

Le code est là.

Pour le lancer: ./maze.sh http://amundsen.com/examples/mazes/2d/five-by-five/. Les détails sont affichés sur stderr, les uri seules sur stdout.

Maze en Bash (maze.sh)
    1 #!/bin/bash
    2 # Bash solution to mamund's maze problem \o/
    3 # see http://amundsen.com/examples/misc/maze-client.html
    4 
    5 MAZE=http://amundsen.com/examples/mazes/2d/five-by-five/
    6 
    7 #---------------------------------------------------------------------
    8 function message {
    9     echo "# $1" >&2
   10 }
   11 function output {
   12     echo $1
   13 }
   14 
   15 # -- Orientation rules -----------------------------------------------
   16 function east {
   17     sed '
   18     s!^south!2 south!;
   19     s!^east!3 east!;
   20     s!^north!4 north!;
   21     s!^west!5 west!;'
   22 }
   23 function south {
   24     sed '
   25     s!^west!2 west!;
   26     s!^south!3 south!; 
   27     s!^east!4 east!; 
   28     s!^north!5 north!;'
   29 }
   30 function west {
   31     sed '
   32     s!^north!2 north!;
   33     s!^west!3 west!;
   34     s!^south!4 south!;
   35     s!^east!5 east!;'
   36 }
   37 function north {
   38     sed '
   39     s!^east!2 east!;
   40     s!^north!3 north!;
   41     s!^west!4 west!;
   42     s!^south!5 south!;'
   43 }
   44 function start_exit {
   45     sed '
   46     s!^exit!0 exit!;
   47     s!^start!1 north!;
   48     '
   49 }
   50 #---------------------------------------------------------------------
   51 
   52 #---------------------------------------------------------------------
   53 function get {
   54     # return the maze+xml from the given uri
   55     local uri="${1:?}"
   56     curl -sL --compressed \
   57         -H 'Accept: application/vnd.amundsen.maze+xml' \
   58         "$uri" |
   59         tr '\n' ' ' | tr -s ' '
   60 }
   61 
   62 
   63 #---------------------------------------------------------------------
   64 function get_links {
   65     # return rel href for the given uri
   66     local uri="${1:?}"
   67     get "$uri" | grep -o '<link [^>]*/>' | tr "'" '"' |
   68     grep -v 'rel="current"' |
   69     while read line ; do
   70         echo $(get_rel "$line") $(get_href "$line")
   71     done
   72 }
   73 function get_href {
   74      echo "$1" | sed 's!.*href="\([^"]*\)".*!\1!'
   75 }
   76 function get_rel {
   77      echo "$1" | sed 's!.*rel="\([^"]*\)".*!\1!'
   78 }
   79 
   80 #---------------------------------------------------------------------
   81 function select_next {
   82     # select the next direction
   83     local facing="${1:?}"
   84     local uri="${2:?}"
   85     get_links "$uri" | start_exit | $facing | sort -n | head -n 1
   86 }
   87 
   88 #---------------------------------------------------------------------
   89 function find_path {
   90     # bring me to exit !
   91     local uri="${1:?}"
   92     local facing="${2:?}"
   93     local next=""
   94     local count=0
   95     while [ "$facing" != "exit" ] ; do
   96         message "$count: I'm at <$uri>"
   97         next="$(select_next "$facing" "$uri")"
   98         facing=$(echo $next | cut -d ' ' -f 2)
   99         uri=$(echo $next | cut -d ' ' -f 3)
  100         message "$count: going to <$uri>, facing $facing"
  101         output $uri
  102         count=$((count+1))
  103     done
  104     message "I'm free!"
  105 
  106 }
  107 
  108 
  109 find_path "${1:-$MAZE}" "${2:-cat}"
  110
+

OCaml

Le code est là.

Le module OCamlNet est nécessaire.

Lancer avec ocaml maze.ml http://amundsen.com/examples/mazes/2d/five-by-five/.Vous pouvez aussi le compiler.

Comme je suis un débutant en Caml, j’ai essayé d’utiliser certaines fonctionnalités en guise d’exercice, et ce n’est donc pas focément la meilleure approche.

Maze en Caml (maze.ml)
    1 #!/bin/env ocaml
    2 
    3 (*
    4  * OCaml solution to mamund's maze problem (functional style)
    5  * see http://amundsen.com/examples/misc/maze-client.html
    6  *)
    7 
    8 #use "topfind";;
    9 
   10 (* OcamlNet for the HTTP client:
   11  * http://projects.camlcity.org/projects/ocamlnet.html *)
   12 #require "netclient" ;;
   13 #require "str";;
   14 open Str
   15 open Http_client.Convenience
   16 
   17 
   18 type direction =
   19     | Start of string
   20     | East of string
   21     | West of string
   22     | North of string
   23     | South of string
   24     | Exit of string
   25     | Current of string
   26     | Unknown of string * string
   27 
   28 
   29 let parse_direction = function
   30     | ("start", href) -> Start(href)
   31     | ("east", href) -> East(href)
   32     | ("west", href) -> West(href)
   33     | ("north", href) -> North(href)
   34     | ("south", href) -> South(href)
   35     | ("exit", href) -> Exit(href)
   36     | ("current", href) -> Current(href)
   37     | (rel, href) -> Unknown(rel,href)
   38 
   39 
   40 let format_direction = function
   41     | Start(href) -> "Start: <" ^ href ^ ">"
   42     | East(href) -> "East: <" ^ href ^ ">"
   43     | West(href) -> "West: <" ^ href ^ ">"
   44     | North(href) -> "North: <" ^ href ^ ">"
   45     | South(href) -> "South: <" ^ href ^ ">"
   46     | Exit(href) -> "Exit: <" ^ href ^ ">"
   47     | Current(href) -> ""
   48     | Unknown(rel,href) -> rel ^ ": <" ^ href ^ ">"
   49 
   50 
   51 
   52 (* Parse the "Link" header with some regexp *)
   53 let parse_link_header url =
   54     let extract_link l =
   55         let re = Str.regexp "<\\([^>]+\\)>; +rel=\"\\([^\"]+\\)\"" in
   56         let m = Str.string_match re l 0 in
   57         if m then parse_direction((Str.matched_group 2 l),
   58                                   (Str.matched_group 1 l))
   59         else Unknown("","")
   60     and call = http_head_message url in
   61     List.map extract_link (Str.split (Str.regexp ",") (call#response_header#field "Link")) 
   62 
   63 exception Lost
   64 exception Out
   65 let select_next_direction facing =
   66     let choose_direction f uri =
   67         let _choose (rank1, dir1) (rank2, dir2) = compare rank1 rank2
   68         and _mapper f dir = (f(dir),dir) in
   69         snd (List.hd (List.sort _choose 
   70                                 (List.map (_mapper f) 
   71                                           (parse_link_header uri))))
   72     in
   73     match facing with
   74     | East(uri) -> (choose_direction (function
   75                         | Exit(_)  -> 0
   76                         | South(_) -> 1
   77                         | East(_)  -> 2
   78                         | North(_) -> 3
   79                         | West(_)  -> 4
   80                         | _ -> 5) uri)
   81     | South(uri) -> (choose_direction (function
   82                         | Exit(_)  -> 0
   83                         | West(_)  -> 1
   84                         | South(_) -> 2
   85                         | East(_)  -> 3
   86                         | North(_) -> 4
   87                         | _ -> 5) uri)
   88     | West(uri) -> (choose_direction (function
   89                         | Exit(_)  -> 0
   90                         | North(_) -> 1
   91                         | West(_)  -> 2
   92                         | South(_) -> 3
   93                         | East(_)  -> 4
   94                         | _ -> 5) uri)
   95     | North(uri) -> (choose_direction (function
   96                         | Exit(_)  -> 0
   97                         | East(_)  -> 1
   98                         | North(_) -> 2
   99                         | West(_)  -> 3
  100                         | South(_) -> 4
  101                         | _ -> 5) uri)
  102     | Exit(uri) -> raise Out
  103     | Start(uri) -> North(uri)
  104     | _ -> raise Lost
  105 
  106 
  107 
  108 open Printf
  109 let () =
  110     let start_uri = if (Array.length Sys.argv) > 1 
  111                     then Sys.argv.(1) 
  112                     else "http://amundsen.com/examples/mazes/2d/five-by-five/"
  113     in
  114     let s = ref (North start_uri)
  115     and i = ref 0 in 
  116     try while true do
  117         printf "%d: %s\n" !i (format_direction !s) ;
  118         flush stdout ;
  119         s := select_next_direction !s ;
  120         i := !i +1 ;
  121         done
  122     with Out -> printf "I'm free!!\n" ;