prac-4-beginners/solutions/ch-08-problem-solving/readme.html

<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
  <head>
    <meta charset="utf-8" />
    <meta name="generator" content="pandoc" />
    <meta
      name="viewport"
      content="width=device-width, initial-scale=1.0, user-scalable=yes"
    />
    <title>readme</title>
    <style type="text/css">
      code {
        white-space: pre-wrap;
      }
      span.smallcaps {
        font-variant: small-caps;
      }
      span.underline {
        text-decoration: underline;
      }
      div.column {
        display: inline-block;
        vertical-align: top;
        width: 50%;
      }
    </style>
  </head>
  <body>
    <h2 id="solution-for-connect4">Solution for Connect4</h2>
    <p>
      This one is VERY similar to TIC-TAC-TOE. There are three fundamental
      changes, other than this, it’s the same code for both games.
    </p>
    <h3 id="change-1-board-data-structure.">Change 1: Board data structure.</h3>
    <p>
      We are using this data structure. Tic-Tac-Toe was 3x3. Connect4 is 7x6 (7
      columns, 6 rows):
    </p>
    <pre><code># Board is a list of rows
# Rows are a list of cells
board = [
    # 6 rows
    [None, None, None, None, None, None, None],  # 7 columns per row
    [None, None, None, None, None, None, None],  # 7 columns per row
    [None, None, None, None, None, None, None],  # 7 columns per row
    [None, None, None, None, None, None, None],  # 7 columns per row
    [None, None, None, None, None, None, None],  # 7 columns per row
    [None, None, None, None, None, None, None],  # 7 columns per row
]</code></pre>
    <h3 id="change-2-you-pick-a-column-drop-the-disk-it-falls-down">
      Change 2: You pick a column, drop the disk, it falls down
    </h3>
    <p>The second major change is how you pick where to play.</p>
    <p>
      In Tic-Tac-Toe, it’s choose the square. In Connect 4, it’s choose the
      column, drop the disk it fall as far as it can. We rewrote
      <code>choose_location()</code> accordingly.
    </p>
    <h3 id="change-3-finding-lists-of-4-in-the-rows-cols-and-diagonals">
      Change 3: Finding lists of 4 in the rows, cols, and diagonals
    </h3>
    <p>
      The final major change is finding wins. In Tic-Tac-Toe, we wrote a
      function called:
    </p>
    <pre><code>def get_winning_sequences(board):
    ...</code></pre>
    <p>
      This function would turn rows, columns, and diagonals into just straight
      lists. Then they are super simple to check. Are all of them one of the
      same kind and not empty? For example, is a diagonal all X’s? Then X’s win.
    </p>
    <p>
      It’s identical in connect 4. But finding these are a bit of a pain. You
      don’t have to have the whole row, or column, or diagonal the same to win.
      You just need 4 in a row of these.
    </p>
    <p>
      So we wrote a function called
      <code>find_sequences_of_four_cells_in_a_row(cells)</code>. It takes a
      series of items, say 7 items, then returns all consecutive possibilities
      of 4.
    </p>
    <p>For example:</p>
    <pre><code>cells = [1, 2, 3, 4, 5, 6]
fours = find_sequences_of_four_cells_in_a_row(cells)
# fours = [
#    [1, 2, 3, 4],
#    [2, 3, 4, 5],
#    [3, 4, 5, 6]
#]</code></pre>
    <p>
      Then we can just return these out of
      <code>get_winning_sequences()</code> and it’ll see if any are winners. At
      that point, it’s all the same as Tic-Tac-Toe. If they are all one type,
      that type is the winner.
    </p>
    <p>
      Finding the sequences is a bit more complex, but it’s the same idea. Find
      all possible diagonals, rows, and columns, use
      <code>find_sequences_of_four_cells_in_a_row()</code> to find the lists of
      4 and check them.
    </p>
    <p>That’s the game.</p>
    <p>See <a href="./connect4.py">connect4.py</a></p>
  </body>
</html>