Tags » Iteration

Iteration Is Not "First to be Second," It's First To Be Next

Advertising creativity values originality above all. Firsts have long been considered its highest expression.

In less than two months, we’ve already been through lots of iteration. 221 more words

Python :: Unit testing, mock opens and iteration

Python 3, unit testing, mock_opens, and when you get caught out by a peculiar omission.

Recently I’ve been working a lot with Python, and have come across a strange omission that’s rather easily solved. 467 more words

Programming

Getting Unstuck - Using the Lean StartUp Method to Move Forward

Ever been stuck?  Just can’t move? Don’t know what to do? Most of us have been stuck at one point or another. The question is how to get unstuck. 456 more words

Decision-Making

Shortest Path - BFS

def ShortestPath(graph, start, target):
  """Finds the shortest path to from start to target if available."""
  visited = set()
  queue = []
  while queue:
    path = queue.pop(0)
    node = path[-1]
    if node not in visited:
      if node == target:
        return path
      visited.add(node)
      for child in graph:
        if child not in visited:
          queue.append(path + )
  return None


# Unit Tests

import unittest


class ShortestPathTest(unittest.TestCase):

  def setUp(self):
    self.graph = {
        'A': set(['B', 'C']),
        'B': set(['A', 'D', 'E']),
        'C': set(['A', 'F']),
        'D': set(['B']),
        'E': set(['B', 'F']),
        'F': set(['C', 'E'])
    }

  def testSearch(self):
    self.assertEquals(['A', 'B', 'E'], ShortestPath(self.graph, 'A', 'E'))

  def testMiss(self):
    self.assertIsNone(ShortestPath(self.graph, 'A', 'X'))


if __name__ == '__main__':
  unittest.main()
Search

Depth First Search (DFS) - Iteratively

def DepthFirstSearch(graph, start):
  """Traverse graph from start node iteratively."""
  visited = set()
  path = []
  stack = 
  while stack:
    node = stack.pop()
    if node not in visited:
      visited.add(node)
      path.append(node)
      stack.extend(graph - visited)
  return path


# Unit Tests

import unittest


class DepthFirstSearchTest(unittest.TestCase):

  def setUp(self):
    self.graph = {
        'A': set(['B', 'C']),
        'B': set(['A', 'D', 'E']),
        'C': set(['A', 'F']),
        'D': set(['B']),
        'E': set(['B', 'F']),
        'F': set(['C', 'E'])
    }

  def testSearch(self):
    """Tests that the resulting path is one of the valid answers."""
    self.assertIn(
      DepthFirstSearch(self.graph, 'A'),
      (['A', 'B', 'D', 'E', 'F', 'C'], ['A', 'C', 'F', 'E', 'B', 'D']))


if __name__ == '__main__':
  unittest.main()
Search

Binary Search (BS) - Iteratively

def BinarySearch(array, target):
  """Searches for an element in a sorted array iteratively."""
  left = 0
  right = len(array) - 1
  while right >= left:
    mid = (right + left) / 2
    val = array
    if val == target:
      return mid
    elif val < target:
      left = mid + 1
    else:
      right = mid - 1
  return None


# Unit Tests

import unittest


class BinarySearchTest(unittest.TestCase):
  def testEvenArrayLength(self):
    self.assertEquals(BinarySearch(, 0), 0)
    self.assertEquals(BinarySearch(, 4), 4)
    self.assertEquals(BinarySearch(, 7), 7)
    self.assertEquals(BinarySearch(, 1), 1)
    self.assertIsNone(BinarySearch(, 9))
    self.assertIsNone(BinarySearch(, -1))

  def testOddArrayLength(self):
    self.assertEquals(BinarySearch(, 0), 0)
    self.assertEquals(BinarySearch(, 4), 4)
    self.assertEquals(BinarySearch(, 8), 8)
    self.assertEquals(BinarySearch(, 1), 1)
    self.assertIsNone(BinarySearch(, 9))
    self.assertIsNone(BinarySearch(, -1))

  def testSingleElementArray(self):
    self.assertIsNone(BinarySearch([0], -1))
    self.assertEquals(BinarySearch([0], 0), 0)
    self.assertIsNone(BinarySearch([0], 1))

  def testEmptyArray(self):
    self.assertIsNone(BinarySearch([], 1))


if __name__ == '__main__':
  unittest.main()
Search

Seasons of the school year

Shelby Aaberg of Scottsbluff High School (Nebraska) mixes action with reflection to create a classes that are personalized to the students he teaches.  See below for more on how he does it. 6 more words

Calendar