Robodoku

Turing School of Software Design: Module 1, Week 1

This week I started a new professional adventure at the Turing School of Software Design, a seven month long web application development program located in the heart of Denver, Colorado. As I began to research coding bootcamps, I struggled with the dearth of non-marketing material available about these types of institutions to the public. For that reason I intend this series of blog posts to first help others decide whether intensive coding educational experiences are worth the plunge, second to give others a look at what goes on at the Turing School specifically, and third to help cement my own learning by writing about significant learnings from each week (or weeks) at Turing.

The first course, or module, in the Web Application Development series at Turing is called "Object-Oriented Programming in Ruby". From the Turing website:

In module 1, students learn how to solve problems using Object-Oriented programming. To do so, they build data structures and build command-line applications using the Ruby programming language. By the end of this module, students should be able to take a complex problem, create an algorithm to solve it, and feel comfortable test-driving their implementation.

Roboduko, the aptly named first project for my cohort at Turing, is about writing a sudoku solving program that takes in a simple sudoku puzzle as a .txt file and outputs the resulting solved puzzle as text. To Turing's credit, they maintain a comprehensive public github page with curriculum resources and projects. The key concepts that I believe this project is intended to teach are:

  1. Basic code organization, content and refactoring.
  2. Ruby's Enumerable methods.
  3. Ruby Hashes, Arrays, and Strings.

The first tremendously helpful resource that I tapped when attacking this project was an article provided in the project's specifications written by Google's Director of Research, and all around super genius, Peter Norvig. The article, Solving Every Sudoku, is an essay on Norvig's website and really should be called 'Norvig Solves all the Sudokus.' The fact that Norvig uses one letter variable names and Python for his code examples made this an arduous read, throughout which I was wracked with self-doubt and awe. My biggest takeaways from 'Norvig Solves all the Sudokus' were:

  1. A vocabulary for talking about sudokus e.g. digits, rows, columns, squares, units, peers, etc.
  2. To use a hash to represent the puzzle where keys are the names of individual spaces (e.g. A1, A2, A3... I9)
  3. The values attached to the space named-keys are the list of possible digits that could occupy the cell. So a space that we know nothing about has a value of '123456789'.
  4. The fundamental action when solving a sudoku is elimination. We are getting rid of possible values as we examine the values held by each space's peers. 

A second resource that I was blessed with during this project was a paired coding experience with an upperclassman at Turing - Matthew Campbell, who graciously stayed late with me and helped me think through and execute methods to find a given space's peer spaces on the board. Matt's willingness to delay progress on his own projects and spend time with his new son and wife speaks to the community culture at Turing, where there is a real sense of mutual support. While I have not been a part of any other coding bootcamp or formal computer science programs, I believe strongly that this altruistic culture sets Turing apart from the competition.

Walking through the Code

def initialize(puzzle_text)

      @digits = (1..9).to_a
      @rows = ("A".."I").to_a
      @cols = @digits
      @spaces = @rows.product(@cols).collect { |x,y| x + y.to_s }
      @squares = create_squares
      @grid = parse_grid(puzzle_text)
      @puzzle_solved = false

  end

In my initialize method I setup some constants, which I later learned from my instructor, Michael Dao, should have been stylistically declared outside of the initialize method. The most interesting part of the above method, which Matt helped me with significantly, is the create_squares method, which returns an array of arrays where each sub-array is a list of squares, (e.g. ["A1", "A2", "A3", "B1", "B2", "B3", "C1", "C2", "C3"]).

def create_squares
    squares = []
    letters = [["A","B","C"],["D","E","F"],["G","H","I"]]
    numbers = [["1","2","3"],["4","5","6"],["7","8","9"]]
    letters.each do |letter_group|
      numbers.each do |number_group|
        squares << letter_group.product(number_group).collect { |x,y| x + y }
      end
    end
    return squares
  end

create_squares will output the following two dimensional array:

[["A1", "A2", "A3", "B1", "B2", "B3", "C1", "C2", "C3"],
 ["A4", "A5", "A6", "B4", "B5", "B6", "C4", "C5", "C6"],
 ["A7", "A8", "A9", "B7", "B8", "B9", "C7", "C8", "C9"],
 ["D1", "D2", "D3", "E1", "E2", "E3", "F1", "F2", "F3"],
 ["D4", "D5", "D6", "E4", "E5", "E6", "F4", "F5", "F6"],
 ["D7", "D8", "D9", "E7", "E8", "E9", "F7", "F8", "F9"],
 ["G1", "G2", "G3", "H1", "H2", "H3", "I1", "I2", "I3"],
 ["G4", "G5", "G6", "H4", "H5", "H6", "I4", "I5", "I6"],
 ["G7", "G8", "G9", "H7", "H8", "H9", "I7", "I8", "I9"]]

Now, I could have typed that array directly into the code, but that would clearly have been weak sauce. Instead, I made use of the array.product method, which will return an array of all combinations of elements from all arrays. The collect method invokes a code block for each element of the array it is called on.

def get_col(space)
    peer_column = @spaces.find_all do |this_space|
      this_space[1] == space[1]
    end
  end

  def get_row(space)
    peer_row = @spaces.find_all do |this_space|
      this_space[0] == space[0]
    end
  end

My implementation of the get_col and get_row methods are pretty straight forward examples of how to use the array.find method in Ruby. Here I use the instance variable @spaces, which is an array of all the spaces on the board, ["A1", "A2", ... "I9"] and return all of the spaces on the board with the same column in get_col and same row in get_row. 

def get_units(space)
    return units = [get_col(space), get_row(space), get_square(space)]
  end

  def get_peers(space)
    peers = get_units(space).flatten.uniq
    peers.delete(space)
    return peers
  end

Next, my code gets a space's units (get_units), which are made up of the peer column, peer row, and peer square. Finally, in get_peers, the code removes duplicate peers, removes the space in question, and creates a one dimensional array listing all of a given space's peer spaces. So if we input space A1, we get back all of A1's peers, see below, and can then loop through this new peers array to start eliminating values.

["B1", "C1", "D1", "E1", "F1", "G1", "H1", "I1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9", "B2", "B3", "C2", "C3"]
def solve
    until @puzzle_solved
      @puzzle_solved = puzzle_solved?
      assign_values
    end
    return format_grid
  end

My solve function uses an until loop to run two sets of instructions until the puzzle is solved (@puzzle_solved is initialized at the start of the class to false). The first instruction is to check if the puzzle is solved, which is true if every space's value on the board hash has a length of 1. In other words, the puzzle is solved when we have eliminated all possible values down to the one remaining true value for each space on the board (@grid). 

def puzzle_solved?
    unsolved_squares = @grid.select { |space, values| values.length > 1 }
    return unsolved_squares.empty?
end

Until the puzzle is solved, the code will repeatedly use the assign_values method to loop through the board and apply the eliminate method on any unsolved spaces. Now this is where my approach differs from Peter Norvig's and why he is the Research Director of Google and why I am a first week, module 1 student at the Turing School. My code will work on easy puzzles where process of elimination can solve the problem. My code will not work on puzzles where multiple spaces contain values that can not be eliminated down to one without employing a more advanced strategy than process of elimination.

def assign_values
    @grid.each do |space, value|
      if (value.length > 1)
        eliminate(space, value)
      end
    end
  end

def eliminate(space, values)
    peers = get_peers(space)
    peers.each do |peer|
      if @grid[peer].length == 1
        values.sub!(@grid[peer], "")
      end
    end
    @grid[space] = values 
end

Conclusions from Week 1 of Module 1

My entire project can be found on my github page, and the solver class is defined in the solver.rb file in the lib directory. 

The hardest part of completing this project was first, in general, representing the board in code and in particular figuring out a smarter way to find a given space's peer square (create_squares and get_square methods). The squares were challenging because of my limited understanding of how arrays can be combined and manipulated to form new arrays, but I think that is one of the goals of the project. 

The next most challenging issue, which honestly took about three hours of line by line debugging, was an error that I somehow overlooked in my initial implementation of the get_square method which caused the code to inconsistently locate the correct peer square for a given space. It was tough to pinpoint the issue because for certain spaces, the correct peer square was returned, but for others an incorrect set of peers were returned. The takeaway here is clearly the importance of test driven development, which we were not expected to employ on this first project, but will use on our next project in week 2. So, had I written a test that correctly checked the expected outputs of my get_square method, I would have found and corrected the error much sooner. Test driven development 1, Jesse 0.

Overall, it was a great first week at the Turing School of Software Design. I'm not regretting my decision to enroll in the least and look forward to continuing to deepen my understanding of object oriented programing, the Ruby language, and getting closer to becoming a professional Full Stack Developer.