Computer Science 15-112, Spring 2013
Class Notes:  Two-Dimensional Lists


  1. Creating 2d Lists
  2. Getting 2d List Dimensions
  3. Nested Looping over 2d Lists
  4. Copying 2d Lists
  5. Printing 2d Lists
  6. Accessing 2d Lists by Row or Column
  7. Non-Rectangular ("Ragged") 2d Lists
  8. 3d Lists
  9. Examples Using 2d Lists
    1. WordSearch
    2. Othello
    3. Optional: Connect4
    4. Optional:  Matrices

Two-Dimensional Lists
  1. Creating 2d Lists
    1. Static Allocation

      # create a 2d list with fixed values (static allocation)
      a = [ [ 2, 3, 4 ] , [ 5, 6, 7 ] ]
      print a

    2. Dynamic (Variable-Length) Allocation
      1. Wrong:  Cannot use * (Shallow Copy)

        # Try, and FAIL, to create a variable-sized 2d list
        rows = 3
        cols = 2

        a = [ [0] * cols ] * rows # Error: creates shallow copy
                                 
        # Creates one unique row, the rest are aliases!
         
        print "This SEEMS ok.  At first:"
        print "   a =", a

        a[0][0] = 42
        print "But see what happens after a[0][0]=42"
        print "   a =", a


      2. Right:  Append Each Row

        # Create a variable-sized 2d list
        rows = 3
        cols = 2

        a=[]
        for row in xrange(rows): a += [[0]*cols]

        print "This IS ok.  At first:"
        print "   a =", a

        a[0][0] = 42
        print "And now see what happens after a[0]
        [0]=42"
        print "   a =", a


      3. Even Better:  make2dList() 

        def make2dList(rows, cols):
            a=[]
            for row in xrange(rows): a += [[0]*cols]
            return a

        rows = 3
        cols = 2
        a = make2dList(rows, cols)
        print "This IS ok.  At first:"
        print "   a =", a

        a[0][0] = 42
        print "And now see what happens after a[0]
        [0]=42"
        print "   a =", a
      4. Another option: use a list comprehension

        rows = 3
        cols = 2
        a = [ ([0] * cols) for row in xrange(rows) ]
        print "This IS ok.  At first:"
        print "   a =", a

        a[0][0] = 42
        print "And now see what happens after a[0]
        [0]=42"
        print "   a =", a

  2. Getting 2d List Dimensions

    # Create an "arbitrary" 2d List
    a = [ [ 2, 3, 5] , [ 1, 4, 7 ] ]
    print "a = ", a

    # Now find its dimensions
    rows = len(a)
    cols = len(a[0])
    print "rows =", rows
    print "cols =", cols


  3. Nested Looping over 2d Lists

    # Create an "arbitrary" 2d List
    a = [ [ 2, 3, 5] , [ 1, 4, 7 ] ]
    print "Before: a =", a

    # Now find its dimensions
    rows = len(a)
    cols = len(a[0])

    # And now loop over every element
    # Here, we'll add one to each element,
    # just to make a change we can easily see
    for row in xrange(rows):
        for col in xrange(cols):
            # This code will be run rows*cols times, once for each
            # element in the 2d list
            a[row][col] += 1

    # Finally, print the results
    print "After:  a =", a


  4. Copying 2d Lists
    1. copy.deepcopy example

      import copy

      # Create a 2d list
      a = [ [ 1, 2, 3 ] , [ 4, 5, 6 ] ]

      # Try to copy it
      b = copy.copy(a)      # Error:  creates shallow copy

      c = copy.deepcopy(a)  # Ok

      # At first, things seem ok
      print "At first..."
      print "   a =", a
      print "   b =", b
      print "   c =", c

      # Now modify a[0][0]
      a[0][0] = 9
      print "But after a[0][0] = 9"
      print "   a =", a
      print "   b =", b
      print "   c =", c
    2. limitations of copy.deepcopy of aliases

      a = [[0]*2]*3 # makes 3 shallow copies of (aliases of) the same row
      a[0][0] = 42  # appears to modify all 3 rows
      print a       # prints [[42, 0], [42, 0], [42, 0]]

      # now do it again with a deepcopy

      import copy
      a = [[0]*2]*3        # makes 3 shallow copies of the same row
      a = copy.deepcopy(a) # meant to make each row distinct
      a[0][0] = 42         # so we hope this only modifies first row
      print a              # STILL prints [[42, 0], [42, 0], [42, 0]]

      # now one more time with a simple deepcopy alternative that does
      # what we thought deepcopy did...

      def myDeepCopy(a):
          if (isinstance(a, list) or isinstance(a, tuple)):
              return [myDeepCopy(element) for element in a]
          else:
              return copy.copy(a)

      a = [[0]*2]*3     # makes 3 shallow copies of the same row
      a = myDeepCopy(a) # once again, meant to make each row distinct
      a[0][0] = 42      # so we hope this only modifies first row
      print a           # finally, prints [[42, 0], [0, 0], [0, 0]]

      # what's going on with deepcopy? Answer: if the original list has aliases,
      # the deepcopied list will have aliases (of a single copy, not the original).
      # So copy.deepcopy preserves alias structure!
  5. Printing 2d Lists

    # Helper function for print2dList.
    # This finds the maximum length of the string
    # representation of any item in the 2d list
    def maxItemLength(a):
        maxLen = 0
        rows = len(a)
        cols = len(a[0])
        for row in xrange(rows):
            for col in xrange(cols):
                maxLen = max(maxLen, len(str(a[row][col])))
        return maxLen

    # Because Python prints 2d lists on one row,
    # we might want to write our own function
    # that prints 2d lists a bit nicer.
    def print2dList(a):
        if (a == []):
            # So we don't crash accessing a[0]
            print []
            return
        rows = len(a)
        cols = len(a[0])
        fieldWidth = maxItemLength(a)
        print "[ ",
        for row in xrange(rows):
            if (row > 0): print "\n  ",
            print "[ ",
            for col in xrange(cols):
                if (col > 0): print ",",
                # The next 2 lines print a[row][col] with the given fieldWidth
                format = "%" + str(fieldWidth) + "s"
                print format % str(a[row][col]),
            print "]",
        print "]"

    # Let's give the new function a try!
    a = [ [ 1, 2, 3 ] , [ 4, 5, 6 ] ]
    print2dList(a)

  6. Accessing 2d Lists by Row or Column
     
    1. Accessing a whole row

      # alias (not a copy!); cheap (no new list created)
      a = [ [ 1, 2, 3 ] , [ 4, 5, 6 ] ]
      row = 1
      rowList = a[row]
      print rowList
       
    2. Accessing a whole column

      # copy (not an alias!); expensive (new list created)
      a = [ [ 1, 2, 3 ] , [ 4, 5, 6 ] ]
      col = 1
      colList = [ ]
      for i in xrange(len(a)):
          colList += [ a[i][col] ]
      print colList

       
    3. Accessing a whole column with a list comprehension

      # still a copy, still expensive, but cheaper and cleaner with a list comprehension!
      a = [ [ 1, 2, 3 ] , [ 4, 5, 6 ] ]
      col = 1
      colList = [ a[i][col] for i in xrange(len(a)) ]
      print colList

       
  7. Non-Rectangular ("Ragged") 2d Lists
    # 2d lists do not have to be rectangular
    a = [ [ 1, 2, 3 ] ,
          [ 4, 5 ],
          [ 6 ],
          [ 7, 8, 9, 10 ] ]
    
    rows = len(a)
    for row in xrange(rows):
        cols = len(a[row]) # now cols depends on each row
        print "Row", row, "has", cols, "columns: ",
        for col in xrange(cols):
            print a[row][col],
        print
  8. 3d Lists
    # 2d lists do not really exist in Python.
    # They are just lists that happen to contain other lists as elements.
    # And so this can be done for "3d lists", or even "4d" or higher-dimensional lists.
    # And these can also be non-rectangular, of course!
    
    a = [ [ [ 1, 2 ],
            [ 3, 4 ] ],
          [ [ 5, 6, 7 ],
            [ 8, 9 ] ],
          [ [ 10 ] ] ]
    
    for i in xrange(len(a)):
        for j in xrange(len(a[i])):
            for k in xrange(len(a[i][j])):
                print "a[%d][%d][%d] = %d" % (i, j, k, a[i][j][k])
  9. Examples Using 2d Lists
    1. WordSearch
    2. Othello
    3. Optional: Connect4
    4. Optional:  Matrices

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem