Connect 4

A couple of weeks ago I was lucky enough to have my employer send me to PyCon. If you weren't at PyCon you missed out on a lot of things...like the invading squirrel hordes. Thankfully, all of the talks are viewable here. But PyCon is not the focus of this post, just a starting point. At PyCon, in the vendor area, there was the Thumbtack booth. The guys at this book weren't doing the “normal” conference thing (passing out schwag to every being, living or dead, that passed them); they actually made people work for their swag. Thumbtack had a programming challenge that you had to submit a solution to before they would give you either a large shot glass or a glass beer stein.
The challenge was to accept a list of lists from standard input, and parse it looking for a winner in a game of Connect 4. I believe this could be a great interview question, and will be using it for the upcoming interviews where I work. One of the reasons for this is that it's deceptively difficult. While we as humans have been conditioned to recognize patterns since birth, computers need to be taught every step from the beginning. How do I go about teaching something that I don't remember learning? But enough of my babbling - let's look at my solution:

  1. #!/usr/bin/env python
  2.  
  3. from __future__ import print_function
  4. import sys
  5.  
  6. def char_check(row, col, char, prev_row=0, prev_col=0, count=0, direction=0):
  7. direction_dict = {1: None,
  8. 2: None,
  9. 3: None,
  10. 4: lambda: char_check(row, col - 1, char, row, col, count + 1, 4),
  11. 5: None,
  12. 6: lambda: char_check(row, col + 1, char, row, col, count + 1, 6),
  13. 7: lambda: char_check(row + 1, col - 1, char, row, col, count + 1, 7),
  14. 8: lambda: char_check(row + 1, col, char, row, col, count + 1, 8),
  15. 9: lambda: char_check(row + 1, col + 1, char, row, col, count + 1, 9)}
  16.  
  17. if count == 3:
  18. print("Winner: %s" % char)
  19. sys.exit(0)
  20.  
  21. direction_list = []
  22. direction_list_append = direction_list.append
  23.  
  24. try:
  25. if (four_list[row][col - 1] == char and
  26. (row != prev_row or (col - 1) != prev_col) and
  27. direction in (0,4)):
  28. direction_list_append(4)
  29. elif (four_list[row][col + 1] == char and
  30. (row != prev_row or (col + 1) != prev_col) and
  31. direction in (0,6)):
  32. direction_list_append(6)
  33. elif (four_list[row + 1][col - 1] == char and
  34. ((row + 1) != prev_row or (col - 1) != prev_col) and
  35. direction in (0,7)):
  36. direction_list_append(7)
  37. elif (four_list[row + 1][col] == char and
  38. ((row + 1) != prev_row or col != prev_col) and
  39. direction in (0,8)):
  40. direction_list_append(8)
  41. elif (four_list[row + 1][col + 1] == char and
  42. ((row + 1) != prev_row or (col + 1) != prev_col) and
  43. direction in (0,9)):
  44. direction_list_append(9)
  45.  
  46. for d in direction_list:
  47. direction_dict[d]()
  48.  
  49. except IndexError:
  50. pass
  51.  
  52. if __name__ == "__main__":
  53. try:
  54. four_list = eval(sys.stdin.read())
  55. except SyntaxError:
  56. print("Error getting list from the web, using preprogrammed backup.")
  57. four_list = [
  58. [".", ".", ".", ".", ".", ".", "."],
  59. [".", ".", ".", ".", ".", ".", "."],
  60. [".", ".", "O", ".", ".", ".", "."],
  61. [".", ".", "X", "O", "X", "X", "."],
  62. [".", ".", "X", "X", "O", "O", "X"],
  63. [".", ".", "O", "X", "X", "O", "X"]
  64. ]
  65. finally:
  66. for r,_ in enumerate(four_list):
  67. [char_check(r, col, four_list[r][col]) for col,_ in enumerate(four_list[r]) if four_list[r][col] != "."]
  68.  
  69. print("No Winner")

Maybe it's my preference for functional programming coming out, but when I looked at this problem I thought “recursion,” remembering from college how much easier it is to solve the Tower of Hanoi problem with recursion than without. The problem became a little more complicated when I went from solving the original example to generating and testing a different board.

At the moment I'm trying to figure out a Haskell version of this solution. Hopefully I'll have one soon and I'll update this page when I do.

Before I posted this, I wrote a quick email to the person I spoke to at the Thumbtack booth and sent him my solution. He thanked me for the solution and requested my address to mail a mug to me, which showed up in the mail couple of days ago. (Below is a pic of the mug filled with a beautiful amber beer.) He also sent me a link to the company's blog post about their experiences using a coding challenge to earn schwag. Here is the link. There are also some pretty impressive solutions to the challenge there, including one done in regular expressions, which deserves a tip of the hat in my book.

If you made it this far down into the article, hopefully you liked it enough to share it with your friends. Thanks if you do, I appreciate it.

Bookmark and Share