BEGIN:VCALENDAR
METHOD:PUBLISH
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION:**Solving Problems**\n\nThe theme for November's Code Share is 
 Solving Problems. The programmers job is to solve problems with code.\n\n> 
 \n[Robert L Glass][1]  in [Software Conflict 2.0][2]  (1990)\n\nWhy do we w
 rite code? To solve problems. The best code is the code that solves the mos
 t important problems.\n\n> \n[Leo Brodie][3]  in the preface to [Thinking F
 orth][4]  (2004)\n\nWe need to be careful\, because sometimes we inadverten
 tly create new ones. Those that follow us can spend more time solving the p
 roblems we created rather than moving forward the solutions we provided.\n\
 n> \n[Michael Jackson][5]  in [Problem Frames][6]  (2001)\n\nWhen we read c
 ode we need to ask ourselves some important questions:\n\n\n - What problem
  is being solved? How important is the problem being solved?\n - How effect
 ively is the problem reflected in the code? Does the code show the concerns
  that need to be addressed to deliver results in the real world?\n - How cl
 ear does the code make the technical solution? Does it bury the important a
 spects of the design below layers of abstraction?\n\n\n**November challange
 : Solving Soduku**\n\nThe complexity of the Soduku puzzle is not incalculab
 le\, but the creation of soduku solvers has much to [teach us][7] .\n\nOne 
 again we are going to use a [python solution by Peter Norvig][8] as a start
 ing point:\n\n\n## Solve Every Sudoku Puzzle\n\n## See [\nhttp://norvig.com
 /sudoku.html][9] \n\n## Throughout this program we have:\n##   r is a row\,
     e.g. 'A'\n##   c is a column\, e.g. '3'\n##   s is a square\, e.g. 'A3'
 \n##   d is a digit\,  e.g. '9'\n##   u is a unit\,   e.g. ['A1'\,'B1'\,'C1
 '\,'D1'\,'E1'\,'F1'\,'G1'\,'H1'\,'I1']\n##   grid is a grid\,e.g. 81 non-bl
 ank chars\, e.g. starting with '.18...7...\n##   values is a dict of possib
 le values\, e.g. {'A1':'12349'\, 'A2':'8'\, ...}\n\ndef cross(A\, B):\n    
 "Cross product of elements in A and elements in B."\n    return [a+b for a 
 in A for b in B]\n\ndigits   = '123456789'\nrows     = 'ABCDEFGHI'\ncols   
   = digits\nsquares  = cross(rows\, cols)\nunitlist = ([cross(rows\, c) for
  c in cols] +\n            [cross(r\, cols) for r in rows] +\n            [
 cross(rs\, cs) for rs in ('ABC'\,'DEF'\,'GHI') for cs in ('123'\,'456'\,'78
 9')])\nunits = dict((s\, [u for u in unitlist if s in u])\n             for
  s in squares)\npeers = dict((s\, set(sum(units[s]\,[]))-set([s]))\n       
       for s in squares)\n\n################ Unit Tests ################\n\n
 def test():\n    "A set of tests that must pass."\n    assert len(squares) 
 == 81\n    assert len(unitlist) == 27\n    assert all(len(units[s]) == 3 fo
 r s in squares)\n    assert all(len(peers[s]) == 20 for s in squares)\n    
 assert units['C2'] == [['A2'\, 'B2'\, 'C2'\, 'D2'\, 'E2'\, 'F2'\, 'G2'\, 'H
 2'\, 'I2']\,\n                           ['C1'\, 'C2'\, 'C3'\, 'C4'\, 'C5'\
 , 'C6'\, 'C7'\, 'C8'\, 'C9']\,\n                           ['A1'\, 'A2'\, '
 A3'\, 'B1'\, 'B2'\, 'B3'\, 'C1'\, 'C2'\, 'C3']]\n    assert peers['C2'] == 
 set(['A2'\, 'B2'\, 'D2'\, 'E2'\, 'F2'\, 'G2'\, 'H2'\, 'I2'\,\n             
                   'C1'\, 'C3'\, 'C4'\, 'C5'\, 'C6'\, 'C7'\, 'C8'\, 'C9'\,\n
                                'A1'\, 'A3'\, 'B1'\, 'B3'])\n    print 'All 
 tests pass.'\n\n################ Parse a Grid ################\n\ndef parse
 _grid(grid):\n    """Convert grid to a dict of possible values\, {square: d
 igits}\, or\n    return False if a contradiction is detected."""\n    ## To
  start\, every square can be any digit\; then assign values from the grid.\
 n    values = dict((s\, digits) for s in squares)\n    for s\,d in grid_val
 ues(grid).items():\n        if d in digits and not assign(values\, s\, d):\
 n            return False ## (Fail if we can't assign d to square s.)\n    
 return values\n\ndef grid_values(grid):\n    "Convert grid into a dict of {
 square: char} with '0' or '.' for empties."\n    chars = [c for c in grid i
 f c in digits or c in '0.']\n    assert len(chars) == 81\n    return dict(z
 ip(squares\, chars))\n\n################ Constraint Propagation ###########
 #####\n\ndef assign(values\, s\, d):\n    """Eliminate all the other values
  (except d) from values[s] and propagate.\n    Return values\, except retur
 n False if a contradiction is detected."""\n    other_values = values[s].re
 place(d\, '')\n    if all(eliminate(values\, s\, d2) for d2 in other_values
 ):\n        return values\n    else:\n        return False\n\ndef eliminate
 (values\, s\, d):\n    """Eliminate d from values[s]\; propagate when value
 s or places &lt\;= 2.\n    Return values\, except return False if a contrad
 iction is detected."""\n    if d not in values[s]:\n        return values #
 # Already eliminated\n    values[s] = values[s].replace(d\,'')\n    ## (1) 
 If a square s is reduced to one value d2\, then eliminate d2 from the peers
 .\n    if len(values[s]) == 0:\n        return False ## Contradiction: remo
 ved last value\n    elif len(values[s]) == 1:\n        d2 = values[s]\n    
     if not all(eliminate(values\, s2\, d2) for s2 in peers[s]):\n          
   return False\n    ## (2) If a unit u is reduced to only one place for a v
 alue d\, then put it there.\n    for u in units[s]:\n        dplaces = [s f
 or s in u if d in values[s]]\n        if len(dplaces) == 0:\n            re
 turn False ## Contradiction: no place for this value\n        elif len(dpla
 ces) == 1:\n            # d can only be in one place in unit\; assign it th
 ere\n            if not assign(values\, dplaces[0]\, d):\n                r
 eturn False\n    return values\n\n################ Display as 2-D grid ####
 ############\n\ndef display(values):\n    "Display these values as a 2-D gr
 id."\n    width = 1+max(len(values[s]) for s in squares)\n    line = '+'.jo
 in(['-'*(width*3)]*3)\n    for r in rows:\n        print ''.join(values[r+c
 ].center(width)+('|' if c in '36' else '')\n                      for c in 
 cols)\n        if r in 'CF': print line\n    print\n\n################ Sear
 ch ################\n\ndef solve(grid): return search(parse_grid(grid))\n\n
 def search(values):\n    "Using depth-first search and propagation\, try al
 l possible values."\n    if values is False:\n        return False ## Faile
 d earlier\n    if all(len(values[s]) == 1 for s in squares):\n        retur
 n values ## Solved!\n    ## Chose the unfilled square s with the fewest pos
 sibilities\n    n\,s = min((len(values[s])\, s) for s in squares if len(val
 ues[s]) &gt\; 1)\n    return some(search(assign(values.copy()\, s\, d))\n  
               for d in values[s])\n\n################ Utilities ###########
 #####\n\ndef some(seq):\n    "Return some element of seq that is true."\n  
   for e in seq:\n        if e: return e\n    return False\n\ndef from_file(
 filename\, sep='\n'):\n    "Parse a file into a list of strings\, separated
  by sep."\n    return file(filename).read().strip().split(sep)\n\ndef shuff
 led(seq):\n    "Return a randomly shuffled copy of the input sequence."\n  
   seq = list(seq)\n    random.shuffle(seq)\n    return seq\n\n#############
 ### System test ################\n\nimport time\, random\n\ndef solve_all(g
 rids\, name=''\, showif=0.0):\n    """Attempt to solve a sequence of grids.
  Report results.\n    When showif is a number of seconds\, display puzzles 
 that take longer.\n    When showif is None\, don't display any puzzles."""\
 n    def time_solve(grid):\n        start = time.clock()\n        values = 
 solve(grid)\n        t = time.clock()-start\n        ## Display puzzles tha
 t take long enough\n        if showif is not None and t &gt\; showif:\n    
         display(grid_values(grid))\n            if values: display(values)\
 n            print '(%.2f seconds)\n' % t\n        return (t\, solved(value
 s))\n    times\, results = zip(*[time_solve(grid) for grid in grids])\n    
 N = len(grids)\n    if N &gt\; 1:\n        print "Solved %d of %d %s puzzle
 s (avg %.2f secs (%d Hz)\, max %.2f secs)." % (\n            sum(results)\,
  N\, name\, sum(times)/N\, N/sum(times)\, max(times))\n\ndef solved(values)
 :\n    "A puzzle is solved if each unit is a permutation of the digits 1 to
  9."\n    def unitsolved(unit): return set(values[s] for s in unit) == set(
 digits)\n    return values is not False and all(unitsolved(unit) for unit i
 n unitlist)\n\ndef random_puzzle(N=17):\n    """Make a random puzzle with N
  or more assignments. Restart on contradictions.\n    Note the resulting pu
 zzle is not guaranteed to be solvable\, but empirically\n    about 99.8% of
  them are solvable. Some have multiple solutions."""\n    values = dict((s\
 , digits) for s in squares)\n    for s in shuffled(squares):\n        if no
 t assign(values\, s\, random.choice(values[s])):\n            break\n      
   ds = [values[s] for s in squares if len(values[s]) == 1]\n        if len(
 ds) &gt\;= N and len(set(ds)) &gt\;= 8:\n            return ''.join(values[
 s] if len(values[s])==1 else '.' for s in squares)\n    return random_puzzl
 e(N) ## Give up and make a new puzzle\n\ngrid1  = '003020600900305001001806
 400008102900700000008006708200002609500800203009005010300'\ngrid2  = '4....
 .8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4.....
 .'\nhard1  = '.....6....59.....82....8....45........3........6..3.54...325.
 .6..................'\n    \nif __name__ == '__main__':\n    test()\n    so
 lve_all(from_file("easy50.txt"\, '========')\, "easy"\, None)\n    solve_al
 l(from_file("top95.txt")\, "hard"\, None)\n    solve_all(from_file("hardest
 .txt")\, "hardest"\, None)\n    solve_all([random_puzzle() for _ in range(9
 9)]\, "random"\, 100.0)\n\n## References used:\n## [\nhttp://www.scanraid.c
 om/BasicStrategies.htm][10] \n## [\nhttp://www.sudokudragon.com/sudokustrat
 egy....][11] \n## [\nhttp://www.krazydad.com/blog/2005/09/29/an-...][12] \n
 ## [\nhttp://www2.warwick.ac.uk/fac/sci/moac/curr...][13] \n\n\nPlease have
  a go at creating your own soduku solver. Whatever you do\, though\, don't 
 just translate the above code into another language. Take the time to under
 stand the problem and possible solutions\, then express your own solution i
 n code as elegantly as you can.\n\n&nbsp\;\n\n**What's Going To Happen?**\n
 \n&nbsp\;\n\nOn Monday 31st October\, a couple of days before the share\, w
 e'll send out an email to everybody who has signed up. If you have any code
  to contribute please send it in a reply to that email.\n\nOn Wednesday 2nd
  November\, the Code Share itself\, we will all have a couple of short pres
 entations. This will be followed by breaking out into groups to cast a crit
 ical eye over the code for some solutions. We will print these out\, so you
  won't have to bring a laptop. Afterwards we will come back together as a g
 roup to discuss what we have learned.\n\nAfter the event we will be heading
  to the Half Moon\,&nbsp\;213-223 Mile End Road\, Mile End\, Greater London
 \, E1 4AA -&nbsp\;[http://www.jdwetherspoon.co.uk/home/pubs/th...][14]  - f
 or drinks/networking.\n\nThoughtWorks are delighted to be sponsors of the N
 ovember Code Share!**&nbsp\;**\n\nThis event is hosted in collaboration wit
 h the [London Java Community][15] . We expect many programmers across the r
 ange from junior to experienced to be participating\, so it's a great chanc
 e to see how code is viewed by an experienced programmer.\n\n\n\n\n\n  [1]:
  http://www.robertlglass.com/\n  [2]: http://www.developerdotstar.com/books
 /software_conflict_glass.html\n  [3]: http://c2.com/cgi/wiki?LeoBrodie\n  [
 4]: http://netcologne.dl.sourceforge.net/project/thinking-forth/reprint/rel
 -1.0/thinking-forth.pdf\n  [5]: http://en.wikipedia.org/wiki/Michael_A._Jac
 kson\n  [6]: http://books.google.co.uk/books?id=8fqIP83Q2IAC\n  [7]: http:/
 /ravimohan.blogspot.com/2007/04/learning-from-sudoku-solvers.html\n  [8]: h
 ttp://norvig.com/sudoku.html\n  [9]: http://norvig.com/sudoku.html\n  [10]:
  http://www.scanraid.com/BasicStrategies.htm\n  [11]: http://www.sudokudrag
 on.com/sudokustrategy.htm\n  [12]: http://www.krazydad.com/blog/2005/09/29/
 an-index-of-sudoku-strategies/\n  [13]: http://www2.warwick.ac.uk/fac/sci/m
 oac/currentstudents/peter_cock/python/sudoku/\n  [14]: http://www.jdwethers
 poon.co.uk/home/pubs/the-half-moon\n  [15]: http://www.meetup.com/Londonjav
 acommunity/events/38197352/\n\nFor full details and to track/follow this ev
 ent check the event page http://www.superdevs.com/events/2379 on Superdevs!
DTEND:20111102T203000Z
DTSTAMP:20130522T052125
DTSTART:20111102T183000Z
CLASS:PUBLIC
LOCATION:London
SEQUENCE:0
SUMMARY:SuperDevs event: November's Code Share: Solving Problems
UID:2013-05-22T05:21:25-07:00_151732397@fce3b558-1094-4ac5-adf4-399b7e7e3d3
 b
END:VEVENT
END:VCALENDAR