Ward Number In Many Programming Languages

See also: WardNumber, ArraySumInManyProgrammingLanguages, CounterInManyProgrammingLanguages, DotProductInManyProgrammingLanguages, HelloWorldInManyProgrammingLanguages, EightQueensInManyProgrammingLanguages


Remember: ConvertSpacesToTabsNotForCode

The code formatting on this page has already been messed up once by ConvertSpacesToTabs. Don't do it again!

Some of the more popular languages have been factored off of this huge page:


PythonLanguage -- SteveHowell

	class wardnumber:
	def __init__(self, pairs):
		self.wardnumber = {}
		self.partners = {}
		for (p1, p2) in pairs:
		self.pair(p1,p2)
		self.pair(p2,p1)
		self.visit(['ward'], 1)

def pair (self, me, you): if self.wardnumber.has_key(me): self.partners[me].append(you) else: self.partners[me] = [you] self.wardnumber[me] = None

def visit(self, closer_folks, cnt): newer_folks = [] for p1 in closer_folks: for p2 in self.partners[p1]: if not self.wardnumber[p2]: self.wardnumber[p2] = cnt newer_folks.append(p2) if len(newer_folks): self.visit(newer_folks,cnt+1)

def output(self): folks = self.wardnumber.keys() folks.sort() for me in folks: print me, self.wardnumber[me]

f = concat("pairs.py","r") exec f wardnumber(pairs).output()

This program accurately gives Ward a WardNumber of 2. The pairs.py file just initializes the self variable with an array of tuples of person names.


Another one in Python, slightly shorter. This correctly gives Ward a WardNumber of 0. It expects an input file each of whose lines is a space-separated pair of names. Uses some Python 2.2 features.

	def dijkstra(G,v0):
	d = {}
	for v in G.keys(): d[v] = len(G)+1
	queue = [v0]
	d[v0] = 0
	while queue:
	v = queue.pop(0)
	for w in G[v]:
	  if d[v]+1 < d[w]:
		d[w] = d[v]+1
		queue.append(w)
	return d

def read_pairs(filename): G = {} for a,b in [line.split() for line in concat(filename)]: for (person, partner) in [(a,b),(b,a)]: if person not in G: G[person]=[] G[person].append(partner) return G

results = dijkstra(read_pairs("pairs.txt"), "Ward").items() results.sort() for person,number in results: print person, number

Some caveats about this version: it uses a list to represent a queue, which may be inefficient when the queue becomes large. In various places I've not bothered to avoid evaluating the same expression several times.


Another Python version. Short and sweet, but 'partners' looks a bit inefficient! -- MichaelDavies?

	# Finds the minumum distance between two authors (the Erdo"s number)
	pairs = ( ('a', 'b'),('b', 'c'),('b', 'd'),('c', 'd'),('d', 'e'),('d', 'f'),
	 ('e', 'i'), ('f', 'g'), ('g', 'h'),  ('h', 'i'),  ('j', 'k') )

def partners(me): return [ p[0] for p in pairs if p[1] == me ] + [ p[1] for p in pairs if p[0] == me ]

def erdosNumbersFrom(root): queue = [root] erdos = {root: 0} while queue <> []: this = queue.pop(0) e = erdos[this] + 1 for p in partners(this): if erdos.setdefault(p, 9999) > e: queue.append(p) erdos[p] = e return erdos

print "from 'f'", erdosNumbersFrom('f') print "from 'a'", erdosNumbersFrom('a')


ErlangLanguage

Here's my most incomprehensionable, in Erlang. -- LukeGorrie

 -module(ward).

-export([run/0, ward_number/1]). -import(lists, [member/2, reverse/1, foldl/3]).

run() -> print_ward_numbers(ward_number(read_file("data.txt")), 0).

print_ward_numbers([], _) -> ok; print_ward_numbers([H|T], N) -> io:format("~p: ~p~n", [N, H]), print_ward_numbers(T, N+1).

%% ward_number([Pair]) => [Group] %% Pair = {Name, Name} %% Returns a list of lists of names, sorted by ward number. ward_number(Pairs) -> ward_number(Pairs, 1, [[ward]]).

ward_number(Pairs, N, Groups) -> case [Who || {true, Who} <- [in_next(Groups, A, B) || {A,B} <- Pairs]] of [] -> reverse(Groups); Next -> ward_number(Pairs, N+1, [Next|Groups]) end.

in_next(Groups, A, B) -> case {group_member(A, Groups), group_member(B, Groups)} of {true, false} -> {true, B}; {false, true} -> {true, A}; _ -> false end.

group_member(X, G) -> [L || L <- G, member(X, L)] /= [].

read_file(Fname) -> {ok, Bin} = file:read_file(Fname), [{A,B} || [A,B] <- [[list_to_atom(T) || T <- string:tokens(Line, " ")] || Line <- string:tokens(binary_to_list(Bin), "\n")]].

RubyLanguage -- JimWeirich

  class Programmer
	attr_reader :mates, :name, :ward_number
	def initialize(name)
	@name = name
	@mates = []
	@ward_number = 10**20
	end
	def examine_level(level)
	return [] if level >= ward_number
	@ward_number = level
	mates
	end
	def <=>(other)
	name <=> other.name
	end
  end

class WardNumberCalculator? def intern(name) @by_name[name] || (@by_name[name] = Programmer.new(name)) end def adjust_level(ground_zero) level = 0 current, pending = [intern(ground_zero)], [] while not current.empty? current.each { |p| pending += p.examine_level(level) } level += 1 current, pending = pending, [] end end def read_pairs(filename) @by_name = Hash.new pairs = concat(filename) { |file| file.each { |line| a, b = line.split.collect {|name| intern(name) } a.mates << b b.mates << a } } end def print for programmer in @by_name.values.sort puts "#{programmer.name}: #{programmer.ward_number}" end end end

ward = WardNumberCalculator?.new ward.read_pairs("ward.dat") ward.adjust_level("Ward") ward.print


Here's another one -- JasonArhart

 class Programmer
   def initialize(name)
     @name = name
     @partners = {}
     @ward_number = 0 if name == 'ward'
   end
   attr_reader :name, :ward_number
   def max_ward_number=(n)
     if @ward_number.nil? or @ward_number > n
       @ward_number = n
       @partners.each_value { |e| e.max_ward_number = @ward_number + 1 }
     end
   end
   def pair_with(other)
     unless @partners.include?(other.name)
       @partners[other.name] = other
       self.max_ward_number = other.ward_number + 1 unless other.ward_number.nil?
       other.pair_with(self)
     end
   end
 end

programmers = {} open('ward.dat') do |file| for line in file a, b = line.strip.split.collect { |e| programmers[e] ||= Programmer.new(e) } a.pair_with(b) end end

for programmer in programmers.keys.sort.collect {|k| programmers[k] } puts "#{programmer.name}: #{programmer.ward_number}" end


BackWardLanguage -- SteveHowell

	{ al bob /pair
	bob cal /pair
	cal dave /pair
	dave ed /pair
	cal fred /pair
	al ward /pair
	dave ward /pair
	} /data Def

{ 1 Copy /names Set Add
  1. Copy Set Add
	} /match Def

{ 2 Copy /match Swap /match } /pair Def

/data

{ /wn Dict Obj 0 Assign } /names Set Forall

{ /level Obj Swap Assign /kids Set Clear { { { 1 Copy /wn Dict Obj Val } { Pop } { 1 Copy /kids Set Add /wn Dict Obj /level Obj Val Assign } If } Swap Set Forall } /folks Set Forall /folks Set Clear { /folks Set Add } /kids Set Forall } /sweep Def ward /folks Set Add /i Obj 1 Assign { /folks Set Val } { /i Obj Val /sweep /i Obj Incr } While { 1 Copy Output /wn Dict Obj Val Output } /names Set Forall


JoyLanguage

trying hard to beat LukeGorrie's ErlangLanguage version, here's a first hack at a JoyLanguage version. --ShaeErisson
 DEFINE pairs == [["ward" "al"] ["al" "shae"] ["ward" "mike"] ["al" "joe"]] .
 DEFINE whackname ==  [!=] cons [filter] cons .
 DEFINE whackward == pairs "ward" whackname map .
 DEFINE rankone == whackward [size 1 =] filter flatten .
 DEFINE nowardpairs == pairs "ward" whackname map [size 2 =] filter .
 DEFINE makefilter == rankone [whackname] map .
 DEFINE flatten == [null] [] [uncons] [concat] linrec .
 DEFINE ranktwo == nowardpairs makefilter flatten map flatten .
 "rank zero is ward." putln.
 "rank one is " put rankone putln .
 "rank two is " put ranktwo putln .


SchemeLanguage

  (define pairings
	'((al . bob)
	  (bob . cal)
	  (cal . dave)
	  (dave . ed)
	  (cal . fred)
	  (al . ward)
	  (dave . ward)))

(define (partners name) (foldl (lambda (pair base) (cond [(eq? name (car pair)) (cons (cdr pair) base)] [(eq? name (cdr pair)) (cons (car pair) base)] [else base])) '() pairings))

(define (distance name group) (cond [(memq name group) 0] [else (+ 1 (distance name (apply append (map partners group))))]))

Use it as follows:

  (distance 'bob '(ward))	----> 2	

(distance 'al '(fred)) ----> 3


HaskellLanguage

A short (but correct) implementation in HaskellLanguage (this seems to be one of the shortest ones). I had a previous version here for a couple of hours, but that wasn't as elegant and it was harder to read.

The idea here is, we pick people out of an ever-shrinking set of unarranged people. We do this by reading the list of already-arranged people (think of a snake eating its tail) and adding their neighbours to the end of the list. The solution is elegant and shows some of the power of lazy evaluation, but unfortunately it has the side effect that if the set of people is disjoint (there are people with no paths in between), the routine will catch up itself when trying to find new paths to the rest of people, effectively making the snake eat itself. (This is a nonending loop in practice, or more precisely, a(n) _|_ -terminated list.)

 import List((\\),delete,intersect,nub)

examplepeers = [("panu", "jinx"), ("janne", "panu"), ("panu", "osma"), ("osma", "tero"), ("lard", "tero"), ("ward", "woe"), ("jinx", "woe"), ("ward", "lard"), ("woe", "binx"), ("binx", "zoo"), ("foo", "zoo")]

symmetric_rel rel = nub $ map (\(x,y) -> (y,x)) rel ++ rel

wardsnumbers start peer_pairs = wardsnumbers' where peer_rel = symmetric_rel peer_pairs wardsnumbers' = (0, start) : arrange_by wardsnumbers' people people = delete start $ nub $ map fst peer_rel arrange_by numbers [] = [] arrange_by ((rank, person) : rest) peers_left = let nbrs = [ dst | (src, dst) <- peer_rel, src == person ] in [ (rank + 1, peer) | peer <- peers_left `intersect` nbrs ] ++ arrange_by rest (peers_left \\ nbrs)

Try it out with

 wardsnumbers "ward" examplepeers


Here is my implementation in HaskellLanguage.

  module Ward (
	XNumber,
	xNumber,
	xNumberFromText
  ) where

import List import Maybe

type XNumber a = (a, Maybe Int)

xNumber :: Eq a => a -> [(a, a)] -> [XNumber a] xNumber src pairs | src `elem` ids = bfs 1 pairs dist f | otherwise = error "xNumber: source not present in pairings" where ids = nub $ concatMap (\(a, b) -> [a, b]) pairs dist = map (\x -> (x, Nothing)) ids f = nub [ x | x <- ids, (x, src) `elem` pairs || (src, x) `elem` pairs ]

bfs :: Eq a => Int -> [(a, a)] -> [XNumber a] -> [a] -> [XNumber a] bfs _ _ dist [] = dist bfs cd pairs dist v = bfs (cd + 1) pairs dist' v' where dist' = foldl (visit cd) dist v v' = nub $ concatMap (neighbors pairs dist') $ reverse v

visit :: Eq a => Int -> [XNumber a] -> a -> [XNumber a] visit cd dist v = (v, Just cd) : v' where v' = filter (\(x, _) -> x /= v) dist

neighbors :: Eq a => [(a, a)] -> [XNumber a] -> a -> [a] neighbors pairs dist v = intersect unv reachable where unv = [x | (x, y) <- dist, y == Nothing] reachable = concat [[a, b] | (a, b) <- pairs, a == v || b == v]

xNumberFromText :: String -> String -> [XNumber String] xNumberFromText src txt = xNumber src $ map (\x -> let [a, b] = words x in (a, b)) $ lines txt

showPairs :: String -> [XNumber String] -> IO () showPairs src xs = do mapM_ (\(name, num) -> case num of Nothing -> putStrLn $ name ++ " has an undefined " ++ src ++ "Number" Just n -> putStrLn $ name ++ " has a " ++ src ++ "Number of " ++ show n ) xs putStrLn "End of list."

main :: IO () main = do src <- getLine txt <- getContents showPairs src $ xNumberFromText src txt

If run as a program, it expects the name of the "source" person (e.g., Ward) on the first line of input. Each subsequent line should contain a whitespace-delimited list of exactly two people, representing a pair that has programmed together. After reading the list, the program will output the "XNumber" (where X represents the name in the first line of input, e.g. Ward) for every person listed (or "undefined" if they have none). There are also a couple of functions provided for processing such a list of pairs from within another program (and it's even polymorphic in the type of programmer identifier).

Note that it accurately returns an X number for X of 2 (that is, if X actually appears in any pairs, otherwise it is undefined). It would be a trivial change (and in fact would make the program look a little neater) to return the correct answer rather than the accurate one. I leave this as an exercise for the reader.

 -- LoganHanks?


PrologLanguage

I thought it should be easy to do in the PrologLanguage. Unfortunately, I don't know Prolog. While reading a simple tutorial, I cobbled up the following, which works, but a real Prologger might be able to produce somethign more elegant.

 pairing(al, bob).
 pairing(bob, cal).
 pairing(cal, dave).
 pairing(dave, ed).
 pairing(cal, fred).
 pairing(al, ward).
 pairing(dave, ward).

pair(X, Y) :- pairing(X, Y). pair(X, Y) :- pairing(Y, X).

ward_number_visited(ward, _, 0). ward_number_visited(X, Visited, _) :- member(X, Visited), !, fail. ward_number_visited(X, Visited, N) :- pair(X, Y), ward_number_visited(Y, [X|Visited], M), N is M+1.

ward_number(X, N) :- findall(M, ward_number_visited(X, [], M), Lst), sort(Lst, [N|_]).

Use it like this:
  ward_number(bob, N).

-- StephanHouben

The above is basically an exhaustive search of all possible paths for each individual. Below is a sample that efficiently calculates all the values. Output is a ranking table as a list of lists of names according to increasing WardNumber.

  unvisited_neighbours(Relation, Visited, X, []) :-
    \+ ((call(Relation, X, Y), \+member(Y, Visited))), !.
  unvisited_neighbours(Relation, Visited, X, Nbrs) :-
    setof(Y, (call(Relation, X, Y), \+member(Y, Visited)), Nbrs).

ranking_(_, [], _, []) :- !. ranking_(Relation, Front, Visited, [Front|Xs]) :- union(Front, Visited, Visited2), maplist(unvisited_neighbours(Relation, Visited2), Front, NbrSets?), foldl(union, NbrSets?, [], Nbrs), ranking_(Relation, Nbrs, Visited2, Xs).

ranking(A, Relation, Xs) :- ranking_(Relation, [A], [], Xs).

Note that the predicate that defines the actual graph is given as a parameter. Using the pair/2 predicate above, we get:

  ?- ranking(ward, pair, WardRanking?).
  WardRanking? = [[ward],[al,dave],[cal,ed,bob],[fred]]

It does not end there, though. We can do much more with it:

  ?- L = [_, X | _], ranking(_, pair, L), member(bob, X).
  L = [[al], [bob, ward], [dave, cal], [fred, ed]],
  X = [bob, ward] ;
  L = [[cal], [bob, dave, fred], [ed, ward, al]],
  X = [bob, dave, fred] ;
  false.


IconLanguage

My IconLanguage version breaks the 20-line barrier. This is my third attempt (the second was here for a few hours). The clever idea for the second attempt was to store the pairs as a set of sets, which turns parsing stdin into internal storage into a one-line operation ("every insert..."). The clever idea for the third attempt was to keep a set of people in the pair list who hadn't been printed, instead of lugging around an ever-growing list of people who had been. This should get rid of the n-squared behavior of each printing step, along with allowing the program to generate less garbage.

I also fixed a bug where a pair with a WardNumber of omega would cause the program to spin (does everyone else's program do this right?). Another possible bug I checked for is the case where JuliusCaesar? is used as the root of the number graph (which should prevent anything from being printed).

Put the depth-zero people (i.e., "ward") on the command line.
  procedure main(args)
	pairs := set()
	every insert(pairs, set(|read() ? [tab(upto(' ')), tab(many(' ')) & tab(0)]))
	toBeWritten := set()
	every toBeWritten ++:= !pairs
	WriteFromDepth(0, toBeWritten, set(args), pairs)
  end

procedure WriteFromDepth(depth, toBeWritten, people, pairs) if not member(toBeWritten, !people) then fail writes(depth, " ") every writes(member(toBeWritten, !people), " ") write()

nextPeople := set() every member(people, !(pair := !pairs)) do nextPeople ++:= pair WriteFromDepth(depth + 1, toBeWritten --:= people, nextPeople --:= people, pairs) end
-- BillTrost
After spending two hours scratching my head over my HtagLanguage implementation, I remembered that I haven't built-in support for local variables yet. And I was so happy about hte fact that it could do recursion.. sigh. -- SvenNeumann

Will this ever be fixed?
JavaLanguage

In JavaLanguage, completely off the top of my head (not even looking up the APIs) and not bothering to try to compile it:

 class NamePair? implements Comparable {
	private String names[2];
	// The second is allowed to be null; the first isn't
	private int nullSemanticHack;
	public int compareTo(Object o) throws ClassCastException {
	NamePair? np = (NamePair?)o;
	int result = names[0].compareTo(np.names[0]);
	if (result != 0) return result;
	// Otherwise, check the second name
	if (names[1] == null || np.names[1] == null) return nullSemanticHack;
	return (names[1].compareTo(np.names[1]);
	}
	public NamePair?(String[] names, int nsh) {
	nullSemanticHack = nsh;
	this.names[0] = names[0]; this.names[1] = names[1];
	}
	public String getName(boolean first) {
	if (first) return names[0]; // else
	return names[1];
	}
 }

public class WardNumberFinder? { TreeSet? pairs; Hashtable numbers; private static void promote(NamePair? promotion) { String x = promotion.getName(true); String y = promotion.getName(false); // Here comes the ugly part. NullIsaHack. if (!(numbers.get(x) || numbers.get(y))) return; Integer xnum = ((Integer)numbers.get(x)); Integer ynum = ((Integer)numbers.get(y)); if (!xnum || (xnum.getValue() - ynum.getValue() > 1)) { numbers.put(x, new Integer(ynum + 1)); } if (!ynum || (ynum.getValue() - xnum.getValue() > 1)) { numbers.put(y, new Integer(xnum + 1)); } } private static void solve(String source) { // Find all pairs starting with source. // Maybe these should be the other way around NamePair? begin = new NamePair?(source, null, -1); NamePair? end = new NamePair?(source, null, 1); Iterator i = pairs.subSet(begin, end).iterator(); while (i.hasNext()) { NamePair? np = (NamePair?)i.next(); String nextNode = np.getName(false); i.remove(); // Ah hell, there will be problems with concurrent // modification for sure. Oh well. Someone else can debug this hopefully? // Call for this node promote(np); // Call recursively solve(nextNode); } } public static void main(String[] args) { // First arg is Ward's name. // Following that, each pair of args is a pairing for the list. String wardsName = args[0]; pairs = new TreeSet?(); numbers = new Hashtable(); int i = 1; while (i + 1 < args.length) { pairs.add(new NamePair?({args[i], args[i+1]}, 0)); pairs.add(new NamePair?({args[i+1], args[i]}, 0)); i += 2; } // Now do our searching. numbers.put(wardsName, new Integer(0)); solve(wardsName); // Output from the 'numbers'. Anyone not present has Ward number oo. Iterator i = numbers.keys().iterator(); while(i.hasNext()) { String name = (String)i.next(); System.out.println(name + " has Ward number " + numbers.get(name) + "."); } } }

Hmm. I suspect Java isn't the right tool for this job ;) I'd have picked Perl, but there was already an implementation for Perl, so I thought I'd fill a gap.

Anyone want to try this in any of the EsotericProgrammingLanguages? >;) -- KarlKnechtel
BourneAgainShell (BourneShell)

Here's a real horror -- a bash version. Works in the FreeBSD /bin/sh, and probably Korn shell, too. -- BillTrost
  #!/bin/sh
  while read dee dum junk; do
	eval peers_$dee=\"\$peers_$dee $dum\"
	eval peers_$dum=\"\$peers_$dum $dee\"
  done

until toEcho= found= for hacker; do eval \$visited_$hacker false && continue toEcho="$toEcho $hacker" eval 'found="$found $peers_'$hacker'"' eval visited_$hacker=true done set -- $found [ $# -eq 0 ] do echo "$toEcho" done | ( set -- while read l; do echo $# $l set x $* done )

AssemblyLanguage

Linux/GAS/x86 in AT&T syntax.

  .MACRO PERSON name
  .data 0
  \name:
	  .int 0x7FFFFFF0, str_\name

.data 1 str_\name: .asciz "\name" .data 0

.ENDM

.MACRO PAIR name1, name2 .int \name1, \name2 .ENDM

.data

persons_begin: PERSON al PERSON bob PERSON cal PERSON dave PERSON ed PERSON fred PERSON ward persons_end:

pairs_begin: PAIR al, bob PAIR bob, cal PAIR cal, dave PAIR dave, ed PAIR cal, fred PAIR al, ward PAIR dave, ward pairs_end:

format_str: .asciz "Person %s has ward number %d.\n"

.text

.global main main: pushal movl $0, ward /* initialize the thing */

outer_loop: xor %bl, %bl mov $pairs_begin, %eax inner_loop: cmp $pairs_end, %eax je end_inner_loop

mov (%eax), %ecx /* %ecx is person 1 */ mov 4(%eax), %edx /* %edx is person 2 */

mov (%ecx), %esi /* %esi is ward number of 1 (so far) */ mov (%edx), %edi /* %edi is ward number of 2 (so far) */

/* first, check if ward # 1 + 1 < ward # 2 */ inc %esi cmp %esi, %edi jle next_person /* it is so, update ward number */ mov $1, %bl mov %esi, (%edx) jmp continue_inner_loop

/* next, check if ward # 1 > ward # 2 + 1 */ next_person: dec %esi inc %edi cmp %esi, %edi jge continue_inner_loop /* it is so, update ward number */ mov $1, %bl mov %edi, (%ecx)

continue_inner_loop: add $8, %eax jmp inner_loop

end_inner_loop: test %bl, %bl jnz outer_loop

/* OK, time to print some results */ mov $persons_begin, %ebx print_loop: cmp $persons_end, %ebx je end_print_loop

push (%ebx) push 4(%ebx) push $format_str call printf add $12, %esp

add $8, %ebx jmp print_loop

end_print_loop: popal xor %eax, %eax ret

ForthLanguage -- IanOsgood

 \ Ward number: adjust numbers as relations are declared

: person create ( Ward# ) , 0 , does> @ ; 0 person Ward : person 9999 person ; \ override : !ward# ( n person -- ) >body ! ; : >ward# ( person -- n ) >body @ ; \ or just execute : >pairs ( person -- ^pairs ) >body cell+ ;

\ linked list (cell 0: link, cell 1: person) : >next ( node -- next-node ) @ ; : >data ( node -- data ) cell+ @ ; : add-head ( data list -- ) dup >next here rot ! , , ;

: link-pair ( person1 person2 -- ) 2dup >pairs add-head swap >pairs add-head ;

: ?lower-ward ( person maybe-lower-ward# -- ) 1+ over >ward# over > if swap 2dup !ward# >pairs \ set lower Ward number begin >next dup while ( ward# node ) 2dup >data swap recurse \ lower partners too? repeat then 2drop ;

: adjust-ward#s ( person1 person2 -- ) 2dup >ward# ?lower-ward swap >ward# ?lower-ward ;

: find-person ( "name" -- person ) bl word find if exit then count type -1 abort" who?" ;

: pair ( "name1 name2" -- ) find-person find-person ( person1 person2 ) 2dup link-pair adjust-ward#s ;

\ test data

person al person bob person cal person dave person ed person fred

pair al bob pair bob cal pair cal dave pair dave ed pair cal fred cr al . ed . \ 9999 9999 pair al ward cr al . bob . cal . dave . ed . fred . \ 1 2 3 4 5 4 pair dave ward cr al . bob . cal . dave . ed . fred . \ 1 2 2 1 2 3

C++ Templates (don't you just Love how templates can be used for functional programming?)

I'm sorry about the readability of the code, but please do ask questions if you want an explanation (that might help me understand it myself). It's also quite large in comparison to the code here (501 lines), so I've put it on an external web server: http://www.persepolis.se/~salparot/ward_number/

Main code in ward.cc - utilities for some LISP constructs (conses, values and printing functions) in templ_lists2.h

The general idea is a BFS search of the graph of pairs that just terminates as soon as the 'ward' symbol has been found. Well, the rest is in the code, which really is self-explanatory (if you're not picky on the definition of 'explanation'). -- SimonBrenner


OcamlLanguage

Copied from the Scheme examples

 let pairings =
   ["al"  , "bob" ;
    "bob" , "cal" ;
    "cal" , "dave";
    "dave", "ed"  ;
    "cal" , "fred";
    "al"  , "ward";
    "dave", "ward"]

(* assuming that each edge is only listed once *) let get_partners name = List.fold_left (fun base (x, y) -> if name = x then y :: base else if name = y then x :: base else base) [] pairings

let rec distance name group = if List.mem name group then 0 else succ (distance name (List.concat (List.map get_partners group))) (* Use as follows: distance "bob" ["ward"] (* returns 2 *) distance "al" ["fred"] (* returns 3 *) *)

let ward_numbers = Hashtbl.create 10

let rec assign_ward_number name number = try let old_number = Hashtbl.find ward_numbers name in if number < old_number then begin Hashtbl.replace ward_numbers name number; List.iter (fun partner -> assign_ward_number partner (succ number)) (get_partners name) end with Not_found -> Hashtbl.add ward_numbers name number; List.iter (fun partner -> assign_ward_number partner (succ number)) (get_partners name)

let () = assign_ward_number "ward" 0; Hashtbl.iter (Printf.printf "%s %d\n") ward_numbers (* outputs: cal 2 dave 1 al 1 fred 3 ward 0 bob 2 ed 2 *)
--Anon


Add your implementation here.

Hands up who can't understand the programs they posted here anymore :-). -- LukeGorrie

Heck, I'm not sure I understand what I just posted! -- BillTrost


CategoryInManyProgrammingLanguages

EditText of this page (last edited April 23, 2014) or FindPage with title or text search