Find common directory path: Difference between revisions
Line 57: | Line 57: | ||
let item = List.hd heads in |
let item = List.hd heads in |
||
let all_the_same = |
let all_the_same = |
||
List. |
List.for_all ((=) item) (List.tl heads) |
||
(fun b this -> b && (item = this)) |
|||
true (List.tl heads) |
|||
in |
in |
||
if all_the_same |
if all_the_same |
Revision as of 23:52, 25 March 2010
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
Create a routine that, given a set of strings representing directory paths and a single character directory separator, will return a string representing that part of the directory tree that is common to all the directories.
Test your routine using the forward slash '/' character as the directory separator and the following three strings as input paths:
'/home/user1/tmp/coverage/test' '/home/user1/tmp/covert/operator' '/home/user1/tmp/coven/members'
Note: The resultant path should be the valid directory '/home/user1/tmp'
and not the longest common string '/home/user1/tmp/cove'
.
If your language has a routine that performs this function (even if it does not have a changeable separator character, then mention it as part of the task)
Clojure
<lang clojure>(defn common-prefix [sep paths]
(let [parts-per-path (map #(.split (re-pattern sep) %) paths) common-parts (for [part-list (apply map vector parts-per-path) :when (apply = part-list)] (first part-list))] (apply str (interpose sep common-parts))))
(println
(common-prefix "/" ["/home/user1/tmp/coverage/test" "/home/user1/tmp/covert/operator" "/home/user1/tmp/coven/members"]))</lang>
Factor
<lang factor>: common-head ( seq1 seq2 -- head )
dupd mismatch head ;
- common-prefix ( file1 file2 -- prefix )
common-head parent-directory ;</lang>
( scratchpad ) "/home/user1/tmp/coverage/test" "/home/user1/tmp/covert/operator" common-prefix . "/home/user1/tmp/"
J
Solution: <lang j>parseDirs =: = <;.2 ] getCommonPrefix =: ([: *./\ *./@({. ="1 }.)) ;@# {.
getCommonDirPath=: [: getCommonPrefix parseDirs&></lang>
Example: <lang j> paths=: '/home/user1/tmp/coverage/test';'/home/user1/tmp/covert/operator';'/home/user1/tmp/coven/members'
getCommonPrefix >paths
/home/user1/tmp/cove
'/' getCommonDirPath paths
/home/user1/tmp/</lang>
Note: This alternative formulation of parseDirs provides cross-platform support, without the need to specify the path separator. <lang j>parseDirs =: (PATHSEP_j_&= <;.2 ])@jhostpath</lang>
OCaml
<lang ocaml>let rec aux acc paths =
let heads = List.map List.hd paths in let item = List.hd heads in let all_the_same = List.for_all ((=) item) (List.tl heads) in if all_the_same then aux (item::acc) (List.map List.tl paths) else (List.rev acc)
let common_prefix sep = function
| [] -> invalid_arg "common_prefix" | dirs -> let paths = List.map (Str.split (Str.regexp_string sep)) dirs in let res = aux [] paths in (sep ^ (String.concat sep res))
let () =
let dirs = [ "/home/user1/tmp/coverage/test"; "/home/user1/tmp/covert/operator"; "/home/user1/tmp/coven/members"; ] in print_endline (common_prefix "/" dirs);
- </lang>
(uses the module Str, str.cma)
Oz
With a few helper functions, we can express the solution like this in Oz: <lang oz>declare
fun {CommonPrefix Sep Paths} fun {GetParts P} {String.tokens P Sep} end Parts = {ZipN {Map Paths GetParts}} EqualParts = {List.takeWhile Parts fun {$ X|Xr} {All Xr {Equals X}} end} in {Join Sep {Map EqualParts Head}} end
fun {ZipN Xs} if {Some Xs {Equals nil}} then nil else {Map Xs Head} | {ZipN {Map Xs Tail}} end end
fun {Join Sep Xs} {FoldR Xs fun {$ X Z} {Append X Sep|Z} end nil} end
fun {Equals C} fun {$ X} X == C end end
fun {Head X|_} X end
fun {Tail _|Xr} Xr end
in
{System.showInfo {CommonPrefix &/ ["/home/user1/tmp/coverage/test" "/home/user1/tmp/covert/operator" "/home/user1/tmp/coven/members"]}}</lang>
PureBasic
PureBasic don't have a path comparator directly but instead have powerful string tools.
Simply by checking the catalog names until they mismatch and add up the correct parts, the task is accomplished. <lang PureBasic>Procedure.s CommonPath(Array InPaths.s(1),separator.s="/")
Protected SOut$="" Protected i, j, toggle If ArraySize(InPaths())=0 ProcedureReturn InPaths(0) ; Special case, only one path EndIf Repeat i+1 toggle=#False For j=1 To ArraySize(InPaths()) If (StringField(InPaths(j-1),i,separator)=StringField(InPaths(j),i,separator)) If Not toggle SOut$+StringField(InPaths(j-1),i,separator)+separator toggle=#True EndIf Else ProcedureReturn SOut$ EndIf Next ForEver
EndProcedure</lang>
Example of implementation <lang PureBasic>Dim t.s(2) t(0)="/home/user1/tmp/coverage/test" t(1)="/home/user1/tmp/covert/operator" t(2)="/home/user1/tmp/coven/members"
Debug CommonPath(t(),"/"))</lang>
Python
The Python os.path.commonprefix function is broken as it returns common characters that may not form a valid directory path: <lang python>>>> import os >>> os.path.commonprefix(['/home/user1/tmp/coverage/test', '/home/user1/tmp/covert/operator', '/home/user1/tmp/coven/members']) '/home/user1/tmp/cove'</lang>
This result can be fixed: <lang python>>>> def commonprefix(*args, sep='/'): return os.path.commonprefix(*args).rpartition(sep)[0]
>>> commonprefix(['/home/user1/tmp/coverage/test', '/home/user1/tmp/covert/operator', '/home/user1/tmp/coven/members']) '/home/user1/tmp'</lang>
But it may be better to not rely on the faulty implementation at all: <lang python>>>> from itertools import takewhile >>> def allnamesequal(name): return all(n==name[0] for n in name[1:])
>>> def commonprefix(paths, sep='/'): bydirectorylevels = zip(*[p.split(sep) for p in paths]) return sep.join(x[0] for x in takewhile(allnamesequal, bydirectorylevels))
>>> commonprefix(['/home/user1/tmp/coverage/test', '/home/user1/tmp/covert/operator', '/home/user1/tmp/coven/members']) '/home/user1/tmp'</lang>
Tcl
<lang tcl>package require Tcl 8.5 proc pop {varname} {
upvar 1 $varname var set var [lassign $var head] return $head
}
proc common_prefix {dirs {separator "/"}} {
set parts [split [pop dirs] $separator] while {[llength $dirs]} { set r {} foreach cmp $parts elt [split [pop dirs] $separator] { if {$cmp ne $elt} break lappend r $cmp } set parts $r } return [join $parts $separator]
}</lang>
% common_prefix {/home/user1/tmp/coverage/test /home/user1/tmp/covert/operator /home/user1/tmp/coven/members} /home/user1/tmp