v 0. Pasted by _W as python at 2008-03-30 04:29:55 MSK and set expiration to never.

Paste will expire never.

  1. #-*- encoding: UTF-8 -*-
  2.  
  3. all = ['papa', 'mama', 's1', 's2', 'd1', 'd2', 'prest', 'polic']
  4. for x in all:
  5.     vars()[x] = x
  6. #papa, mama, s1, s2, d1, d2, prest, polic = range(8)
  7.    
  8. S = set((s1, s2))
  9. D = set((d1, d2))
  10.  
  11. def good_shore(l):
  12.     #Полицейский не может оставлять преступника с людьми одного.
  13.     if prest in l and set(l) != set([prest]) and polic not in l:
  14.         return False
  15.     #Папа не может оставлять сыновей одних с мамой, а мать - дочерей с папой.
  16.     if papa not in l and mama in l and (S & l):
  17.         return False
  18.     if mama not in l and papa in l and (D & l):
  19.         return False
  20.     return True
  21.    
  22. def plot_candidate(l):
  23.     l2 =  [frozenset((x, y)) for x in l for y in l if x > y and (not (set((x,y)) <= (S | D)))]
  24.     l1 = [frozenset((x,)) for x in l if x != prest and x not in (S|D) ]
  25.     return l1 + l2
  26.    
  27. #state: ((frozenset, frozenset), plot)
  28. def nexts(state):
  29.     s1, s2, plot = state
  30.     if plot == 0:
  31.         pcs = plot_candidate(s1)
  32.         result = [((s1 - pc, s2 | pc, 1), sorted(list(pc))) for pc in pcs]
  33.     if plot == 1:
  34.         pcs = plot_candidate(s2)
  35.         result = [((s1 | pc, s2 - pc, 0), sorted(list(pc))) for pc in pcs]
  36.  
  37.     result = [((rs1, rs2, p), path) for ((rs1, rs2, p), path) in result if good_shore(rs1) and good_shore(rs2)]
  38.     return result
  39.  
  40. def breadth_search(nexts, first, is_end):
  41.     wavefront = [first]
  42.     found_links = { first : (None, None) }
  43.     while wavefront:
  44.         x = wavefront.pop(0)
  45.         for neigbour, link in nexts(x):
  46.             if neigbour not in found_links and neigbour not in wavefront:
  47.                 wavefront.append(neigbour)
  48.                 found_links[neigbour] = (x, link)
  49.                 if (is_end(neigbour)):
  50.                     return found_links, neigbour
  51.     return None
  52.  
  53. paths, end = breadth_search(nexts, (frozenset(all), frozenset(), 0), lambda (s1, s2, plot): not s1)
  54.  
  55. x = end
  56. while x:
  57.     x, link = paths[x]
  58.     print `link`.ljust(30), x