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
')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.
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.
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" ;