Next Level Code @wylliamjudd - Tumblr Blog

w2d4

When learning how to code, we get to spend a lot of time coming up with our own solutions to different puzzles. But there’s more to coding well than merely finding solutions. Learning new syntax is a great way to get more tools for solving different problems, but it’s always exciting to learn certain broader lessons about how to be a better programmer. Today we learned about algorithms and Big O notation, which was like opening a whole new toolbox. Here are some of the things we’ve learned so far about bringing our code to the next level:

Clean Code

When you write code that’s easy to read, it’s not just easier for other programmers to work with, it’s also less confusing, leading to fewer bugs, and easier to modify. Associated chunks of code with unabbreviated descriptive words (referred to as idiomatic code) makes it clear what your code does, and lets you avoid repeating yourself (referred to as DRY or Don’t Repeat Yourself). Breaking code up into small Classes and smaller methods helps your code be readable, clear, and modular.

Class Structure

Writing classes well is sort of an extension of clean code. Using a few principles about how to organize your classes, you can write code that’s easier to read, easier to understand, and easier to read. One of these principles is called “tell don’t ask,” though I think this should be called “ask don’t take”. What the principle is about is instead of grabbing information from another class of object, you should always use one of that class’s methods (and write a method for it, if you need the information).

A related principle is polymorphism, which is the idea that if your program is likely to attempt to ask two different objects the same question (call the same method on them) that method should be defined for both objects to avoid getting an error that crashes your program. For example, if you ask a blank space in Chess “what is your color?” it should respond with “I have no color,” instead of “ERRORKILLPROGRAMDIE.’

Another principle is encapsulation. This is the idea that you should limit each object to containing a minimum amount of information, and have your objects work in tandem to accomplish tasks. This is closely related to avoiding the use of god objects.

Algorithms and Big O Notation

This brings me to what I learned about today! Algorithms and Big O notation. There are usually many ways of solving the same problem, but some algorithms take longer than others. When your code uses your input, different algorithms scale in time at different rates compared to your input. For example, if you have a loop inside a loop and each of them looks at each item you fed the code, your code runs in O(n^2) time. Considering that computers have to handle more and more data going forward, that’s really bad.

If you could find a way to accomplish the same thing without the second loop you could get your program down to O(n) time. If you can split your code up in half each time you iterate through it, you can get yourself down to O(log n) time, which is very nearly as fast as you can get. The ultimate though is O(1) time, which means that your program takes the same amount of time, no matter how much or how big your input is. For example, adding a word to the end of a dictionary would only take O(1) time, no matter how long your dictionary is. But, if you wanted to put it in the right place in the alphabet, that would take O(log n) time if you use an algorithm that searches for where it goes by checking the center item of the dictionary recursively.

Several of the problems we’ve had so far, we learned how to do using much faster algorithms today. I’ll give you an example:

Two Sum

Given a list of numbers, find if any two of them add to a given target.

def bad_two_sum?(array, target) array.each_index do |i| array.each_index do |j| if j > i return true if array[i] + array[j] == target_sum end end end false end

This one takes O(n^2) time. In other words, the time it takes is a function of a square of the size of the array you give it.

def good_two_sum?(array, target_sum) complements = {} array.each do |x| return true if complements[target_sum - x] complements[x] = true end false end

This version takes O(n) time, so the time it takes is a function of the size of the array you give it.

Here’s another one:

Largest Contiguous Sum

Find the largest contiguous sum in a given array.

def largest_contiguous_subsum1(array) subs = [] array.each_index do |idx1| (idx1..array.length - 1).each do |idx2| subs << array[idx1..idx2] end end subs.map { |sub| sub.inject(:+) }.max end

This takes O(n^3) time because not only do I have two loops, but I also loop through again to create a new array to add to subs.

def largest_contiguous_subsum2(array) largest = 0 current = 0 array.each do |el| current += el largest = current if current > largest current = 0 if current < 0 end largest end

This takes O(n) time. I love this solution because not only is it faster, it’s easier to read, and it doesn’t use any tricky objects like hashes, which can be harder for beginners to understand than arrays.

wylliamjudd

One of my favorite blog posts from AppAcadmey. I love the humble solution to largest contiguous subsum and it’s superior time complexity.

A New Approach

I’ve been struggling a bit with writing cover letters and had a friend take a look. First thing he told me was that I needed to talk more about why I want to work for the company I’m applying for. Butter them up, make them feel special. And of course I knew that, and I’d tried to do that, but when I re-read my cover letter, I didn’t so much talk about why I was excited to work at that company, but about what I would do there, and how I would help the company succeed.

That’s when I realized that I was having trouble finding things to say about the company because I wasn’t all that excited about the company in the first place. That led me to another insight: I need to change my approach to job applications.

My approach so far has been to find job postings on job boards, look up the company, write a cover letter tailored to that company, and then apply for the job. My new approach is to look up companies I’m excited about, write a cover letter about why I want to work for that company, and then find their job postings on job boards and apply to them. This should fix the problem I’m having with writing my cover letters, but more importantly, it will ensure that when I do land a job, it’s at a company I’m excited to work for.

I’m also pairing this with another approach, which is to take coding challenges that put me in front of employers. These have been scaring me off, because I feel out of practice doing them, but I’m going to have to bite the bullet on these eventually. This approach is actually the most exciting to me, because it will mean just doing the fun part (coding) the whole way to a job, and let me skip the parts I don’t like (looking at job postings and crafting cover letters).

To supplement these approaches to finding a job, I plan to continue to develop my projects, practice coding challenges, practice algorithms, practice white-boarding, and start contributing to open source code.

#job search #tech #web development

For the Love of Learning

I’m a self-taught web developer. I started out learning Ruby code for the application process to App Academy. I was one of the 3% of applicants admitted to their course, but my self-taught journey really began when my relationship with App Academy ended.

Learning how to code has changed my perspective on what’s possible and when I’ve exhausted my ability to solve a problem (basically, never). When coding, the answer is always out there, and the most exciting challenges are the ones where you’ve learned something new by the time you’ve completed them. I’m always excited to learn new programming languages, like Ruby, SQL, or JavaScript. And it’s just as exciting to learn a new programming concept, like Object Oriented Programming principles, what makes someone a good pair-programmer, and Test Driven Development.

Just a few months ago, my Collectize project would have looked impossible for me. It’s a Ruby on Rails web app that renders the front end in React with a Flux design pattern. What made it possible for me to progress so quickly from where I was then, is that excitement I feel when I learn something new. And the new things you learn are never very large. I was excited to learn about the difference between .each and .map. I was excited to master recursive methods. All the way through understanding Flux Stores, and React components, every new thing I learn, no matter how small, is what keep me going. It’s what makes it worth all the time I spend, just me and my computer, is the excitement for learning something new.

Love of learning is what’s motivated me to learn to code. It’s not even really about finding work. On some rational level, of course I need to find work. But that’s not what keeps me going, and what keeps me motivated to continue to develop as a coder.

Freelance work may be the perfect way for me to go. Not only will I get to make my own hours and work from home, but every job represents an opportunity to learn something new. That’s why I’m joining the Toptal React.js freelancers network. They screen computer engineers and pair them with freelance opportunities. Working on new projects all the time will ensure that I’m always learning new things, and will also give me extra time to spend with my family.

#toptal #freelance #coding

wylliamjudd

JS Closure

Javascript closure has been one of the more difficult concepts for me to pick up. Here’s some code I wrote to demonstrate closure to myself:

function1 = function(){ variable = "foo" function2 = function(argument){ console.log(variable + argument); } return function2 } function3 = function1(); function3("bar");

function1 constructs another function, function2 and returns it. function3 gets assigned to that newly constructed function. The mysterious thing about closures is that function3 still has access to the variable defined in function1.

What happens when you call function3 with the argument “bar” is that it adds “bar” to the variable defined in function1, “foo” and prints “foobar” to the console. So, now I know that closure works, but I’m still not sure how it works under the hood. Where does variable live? Is it stored in memory? Does it become a property of the function3 object? Is there a closure chain similar to the prototype chain? Where does a closure variable live?

wylliamjudd

I asked this question on Stack Overflow and got some awesome answers.

JS Closure

Javascript closure has been one of the more difficult concepts for me to pick up. Here’s some code I wrote to demonstrate closure to myself:

function1 = function(){ variable = "foo" function2 = function(argument){ console.log(variable + argument); } return function2 } function3 = function1(); function3("bar");

#javascript #closure

Next Level Code 4

1. Debug 2. Clean Code

Extract Temp to Query: Convert local variables to methods.

You Do You: Allow your classes to handle their own internal states (previously known as Tell don’t Ask.)

Depend Upon Abstractions: Write short methods and classes.

3. Object Oriented Programming

Don’t Repeat Yourself: Abstract away code instead of repeating it.

Polymorphism: Create the same API across multiple objects.

Encapsulation: Keep your private methods private.

4. Big O Notation

Part of the fun of programming is that there are many different ways to solve the same puzzles. But some solutions are better than others; some algorithms are faster than others. Big O Notation is a way of expressing that speed. Specifically it represents how quickly the runtime grows relative to the input, as the input gets arbitrarily large.

You can determine the time complexity of a chunk of code just by looking at it once you get the hang of Big O Notation. Part of the reason for this is that Big O Notation expresses speed in broad strokes.

Constant Time O(1): Runtime doesn’t grow as input grows.

Logarithmic Time O(log(n)): Runtime grows more slowly than input grows.

Linear Time O(n): Runtime grows at the same pace as our input.

Polynomial O(n^a), Exponential O(a^n), Factorial O(n!): Runtime grows more quickly than input grows.

Iterating through an Array

Big O Notation is pretty easy to think about when working with Arrays. Let’s say we have an array [3, 1, 5, 4, 2]. What’s the time complexity of searching for an item in the array? Well, we have to check each item in the array. We might only have to do one operation if we happen to be looking for 3, but suppose we’re looking for 6? Six isn’t in the array, so we’ll check each item, and then return false. Now what if this array had 1000 elements in it? Checking for inclusion will take 1000 operations. That’s O(n) time complexity. The number of operations we have to do grows linearly with the number of elements in our array.

What about indexing into an array? In other words, if I want to find the third item in the array or the item at index 2, how long will that take? It’s just one operation! That’s the magical thing about Arrays. array[2] will go directly to the third item in the array, without even looking at the first two items. How does this grow if our array has 1000 elements in it? It doesn’t. Indexing into an array takes the same amount of time, regardless of how big the array is. That’s O(1) time complexity.

Resizing

To insert something to the end of an array takes O(1) time. We just push an item onto the end of the array, without iterating through the array at all. But what about inserting something at the beginning of an array? That takes O(n) time. Why is it different from adding an item to the end? Well, think about what Arrays do so well - indexing. When you add something to the beginning of an array, now it’s the first item. What used to be the first item, is now the second item, and so on. The array is getting resized, and each item reindexed, iterating over each item to assign it its new index.

Binary Search

Let’s say you’re looking up a phone number in the phone book. You’re looking for my number, Judd. You could start at page 1 and flip page by page until you find my name. That would be time complexity of O(n). But you can do better than that. You could flip to the middle of the phonebook, and check whether you’re before or after J. You know which half of the phonebook I’m in now, and you can go to the middle of that half. Repeat, until you’ve found my number. This is faster than flipping through the phone book one page at a time, and in computer science it’s called Binary Search. Binary search has O(log(n)) time complexity. Looking for my name in a phone book with 10,000 pages will only take a little longer than finding it in a phone book with only 1000 pages (only about a third longer, nowhere near ten times as long).

Why Does This Matter?

Understanding the time complexity of your code, and of various algorithms and data structures allows you to apply the best solution to a given problem, rather than one that merely works. Abstract Data Types can even be combined to get the strengths of each and can seemingly impossibly give you better than O(n) time on all of your operations. Better time complexity doesn’t always run faster with small inputs, but it always runs faster with arbitrarily large inputs, so being mindful of your Big O Notation is what allows your code to scale.

This is why we care about Algorithms and Abstract Data Types, because they allow us to solve problems in the most efficient way available.

#Big O Notation #Computer Science #Algorithms #Coding

Canvas

I’m learning about Canvas, a drawing API for websites. You can follow along at: http://joshondesign.com/p/books/canvasdeepdive/chapter01.html

Chess

I wrote a command line chess game. This exercise was mainly about Object Oriented Programming, so I’m going to go through how I applied different concepts.

Inheritance - Polymorphism

Each piece is its own class, but all the pieces share some common functionality, so they all inherit from a Piece class. Pieces share their instance variables in common: color, the board their on, and their position on the board. Pieces also share a common API. They all have a #valid_move? method and a to_s method (which tells the console how to display the piece).

def valid_move?(destination) self.moves.include?(destination) end

By inheriting this method, I don’t have to write it on each piece class. Not only that, but it’s polymorphic because the rest of the code only has to interact with a piece by asking if a move is valid. Each piece will have its own #moves method, which will list all of the valid moves from the piece’s current position, but other parts of the code don’t need to be aware of the details.

include Module

I also used modules. The Queen, Bishop and Rook all move in similar ways. The Bishop can move diagonally, the Rook orthogonally, and the Queen both. Since these pieces all move similarly, I can use the same code to describe their behavior. Here’s what I had for the Queen when all was said and done:

class Queen < Piece include Slidable def deltas ORTHOGONAL + DIAGONAL end end

Yes, it’s really that simple! The only thing the Queen has to do is provide deltas to slidable, which does the rest of the work. Slidable uses the deltas for a #moves method, which is then used by the #valid_move? method inherited from Piece.

Encapsulation - Pawn

Just like every other piece, the Pawn only has one public method: #moves. Here’s the #moves method I wrote for it:

def moves march + flank end

Pawn has seven private methods: #march_delta, #flank_deltas, #march, #step_forward, #start_row, #flank, #in_bound. But no other part of the program needs to be concerned with these methods other than the Pawn itself. You’ll just ask the Pawn if it can make a certain move, and it’ll say yes or no. That’s encapsulation.

Refactoring

I was able to reduce the number of arguments for several methods by moving them from the Board class to a Game class. The Game class has a @current_color instance variable, so I don’t have to constantly pass the current color around as an argument.

In order to write #checkmate? you have to duplicate the board so that you can try all of the current player’s moves to see if they can get out of check. This required me to move #in_check? back to the Board class, taking current_color as an argument, so that I could call it on duplicated boards. Here’s Game#checkamte?

def checkmate? return false unless in_check? current_pieces = board.pieces.select {|piece| piece.color == current_color} current_pieces.each do |piece| piece.moves.each do |move| test_board = board.dup test_board.move!(piece.pos, move) return false unless test_board.in_check?(current_color) end end true end

And here’s Board#in_check?

def in_check?(current_color) pieces.any? { |piece| piece.moves.include?(king(current_color).pos) } end

I wrote another class, Session, that’s responsible for actually displaying a game to a user and taking turns. I also adapted code written by Ryan Glassett to handle displaying and coloring the board and giving the player a cursor they can move with the arrow keys. Far from cheating, this felt like a useful skill to develop.

#coding #chess #object oriented programming #polymorphism #encapsulation

thingsprogrammersshout

Things Programmers Shout #475

“Oh great, now it says NaN instead.”

wylliamjudd

Hahaha!!!

Next Level Code 3

1. Debugging

Write short classes and methods that are easy to debug

Use your debugger.

2. Clean Code

Extract Temp to Query: Convert your local variables into methods.

Tell Don’t Ask: Call methods on other classes rather than accessing their instance variables.

Depend Upon Abstractions: The more you abstract, the easier your code will be to change.

3. Object Oriented Programming

You might be noticing a pattern. In debugging I told you to write more shorter methods, because they’re easier to debug. In clean code I told you to write more shorter classes, because they’re easier to change. Today I’m going to go over some more Object Oriented Programming concepts.

Don’t Repeat Yourself (DRY)

DRY is one of the most basic principles of code. Instead of copying and pasting, you should figure out how to abstract that chunk of code so you can reuse it later. Finding and abstracting repetition, or “drying out your code”, is one of the most straightforward ways to refactor.

Inheritance

If you write the same block of code in two of your methods, you can write a third method and have both of your methods call that third method. But what about when you have the same method defined for two different classes? That’s where inheritance comes in. Here’s an example of two classes that share some functionality:

class Dolphin def move puts “I swim with my powerful tail.” end def breathe puts “I breathe with my lungs.” end end class Dog def move puts “I walk on four legs.” end def breathe puts “I breathe with my lungs.” end end

OK, so a dog and a dolphin move differently. But, they breathe the same way. They both have lungs, and can’t breathe under water because they don’t have gills. We should create a class that Dolphin and Dog both inherit from. Here’s what that would look like:

class Mammal def breathe puts “I breathe with my lungs.” end end class Dolphin < Mammal def move puts “I swim with my powerful tail.” end end class Dog < Mammal def move puts “I walk on four legs.” end end

There we go. Now I only have to define the breathe method once. My code is dry. There are some more tricks. There are modules which work like super classes except you can mix them into your class. This lets you have one super class, with some different modules to mix into some of your classes. For example, if I added a seal and a cat, I might add a Swimmable module and a Walkable module. Here’s what that would look like:

class Mammal def breathe puts “I breathe with my lungs.” end end module Swimmable def move puts “I swim with my powerful tail.” end end module Walkable def move puts “I walk on four legs.” end end class Dolphin < Mammal include Swimmable end class Seal < Mammal include Swimmable end class Dog < Mammal include Walkable end class Cat < Mammal include Walkable end

There’s one more thing I want to touch on, which is the “super” key word. Super lets you use a super class’s method, and then add additional functionality to that method. Here’s an example:

class Mammal def move puts “I flex my muscles.” end def breathe puts “I breathe with my lungs.” end end module Swimmable def move super puts “I swim with my powerful tail.” end end module Walkable def move super puts “I walk on four legs.” end end

Calling super will call the super class’s method with the same name, and then proceed to run the rest of the code in this instance’s method.

Polymorphism

Polymorphism is the ability of more than one class of object to respond differently to the same method called on it. Our move method above is an example of polymorphism. The great thing about polymorphism is that when a user or another piece of code uses our API, it doesn’t need to know in advance what kind of object it’s working with. The objects themselves will respond how they should to the API. That’s why our method is called “move” instead of “walk” and “swim”. Maybe we have a list of animals, and we want to make them all move. Rather than checking each one for its type and then calling the corresponding method, we can just tell each one to “move” and it will handle what that means for itself. This is also known as duck-typing.

Encapsulation

Encapsulation is related to “tell don’t ask,” or as I prefer to call it “you do you.” You want to make sure that other objects and users only interact with your object’s “public API”. For both safety and clarity, you should make methods that aren’t part of your public API private. To do that you just put a line “private” in your class, and then every method you define below that line is private. Those methods will only be available within the class itself, and won’t be available in another scope.

Curly’s Law

A class should be responsible for one thing, and one thing only. I’ll let Jeff Atwood take it from there: http://blog.codinghorror.com/curlys-law-do-one-thing/

#coding #object oriented programmiing #ruby #polymorphism #encapsulation #inheritance #computer science

Knight’s Trevails

I wrote a program to find the shortest path a Knight can take from one position on a chess board to another. I used my custom PolyTreeNode class to do it.

class KnightPathFinder attr_accessor :start_position, :move_tree, :end_pos, :root

def initialize(start_pos) @start_pos = start_pos @visited_positions = [start_pos] @root = PolyTreeNode.new(start_pos) build_move_tree end

def find_path(end_pos) target = self.root.dfs(end_pos) target ? trace_path_back(target).reverse : nil end

def self.valid_moves(pos) x, y = pos valid_moves = VALID_MOVES.map { |dx, dy| [dx += x, dy += y] } valid_moves.select { |x, y| x.between?(0, 7) && y.between?(0, 7) } end

We need to build the move tree before we can search it for the shortest path. So, this move path is going to contain every space on the board. new_move_positions rejects spaces that have already been visited or that aren’t on the board. Once we’ve built the tree, then we can traverse it in the fastest way by simply following the destination node back up its parents. Since each node only has one parent, it will never be ambiguous which way to go (though some of the moves will have arbitrary parents).

def build_move_tree queue = [root]

until queue.empty? current_node = queue.shift current_pos = current_node.value new_move_positions(current_pos).each do |next_pos| next_node = PolyTreeNode.new(next_pos) current_node.add_child(next_node) queue << next_node end end end

def new_move_positions(pos) KnightPathFinder.valid_moves(pos) .reject { |position| @visited_positions.include?(position) } .each { |new_pos| @visited_positions << new_pos } end

def trace_path_back(destination) return [] unless destination.parent [destination] + trace_path_back(destination.parent) end end

You might notice that building the move tree is sort of similar to a breadth first search. It also uses a queue, but instead of returning a value, it makes node objects as it goes. I experimented with building the move tree in a depth first fashion. This does crazy things! If you think about it, that means the knight will go as far as it can from its starting position before going back to its starting position to try a different move. That means that the paths it would find are extremely long (and not at all the shortest path). That made me laugh.

Obviously, we want to build our move tree in a breadth first fashion. We want all of the moves from one space to be that space’s children. We want all the moves that are two moves away from the root node (the starting position) to be exactly two nodes deep in the tree.

#coding

Poly Tree Node

I wrote my own Poly Tree Node Class.

class PolyTreeNode attr_reader :children, :parent, :value def initialize(value) @value = value @parent = nil @children = [] end

def parent=(parent) @parent.children.delete(self) if @parent @parent = parent unless parent == nil || parent.children.include?(self) parent.children << self end end

Since a tree node points to its parent and to its children, I need to take care of both pointers when a new parent is assigned. Since this node’s parent will point to it, I need to remove it from its parent’s children.

def add_child(child) child.parent = self end

def remove_child(child) raise "That is not my child!" unless @children.include?(child) child.parent = nil end

Likewise, when a child is added to a node, I need to add pointers to both objects. When adding a child, I need to set this node to be that child’s parent, and the #parent= method that’s already been defined will take care of adding the child to this nodes list of children.

A little bit of magic happens with remove child. When child.parent is assigned to nil that will remove the two objects pointers to each other. When an object has no pointers to it, it gets “garbage collected” and no longer exists. In programming, if nobody knows about you, there’s no reason for you to exist.

def dfs(target_value) return self if @value == target_value return nil if @children.empty? result_node = nil @children.each do |child| result_node = child.dfs(target_value) break if result_node end result_node end

This is depth first search. It recursively searches each child it sees. That means that it will get to a return statement before it actually returns a value from the call stack.

def bfs(target_value) queue = [self] until queue.empty? node = queue.shift return node if node.value == target_value node.children.each {|child| queue << child } end nil end

This is breadth first search. It checks each node of the tree by adding a node’s children to the queue as it checks them.

def inspect @value.inspect end end

Inspect is in there for debugging. It’s really useful to define an inspect method because this is what irb and pry call to display ruby return values. Rather than see all of the information for the object (which includes a bunch of long hashes), it’s much easier to display each node as just it’s value. You could define inspect to serve whatever debugging purpose you need at the time though.

#coding #abstract data type #tree node

Word Chains BFS

Here’s an example of code I wrote that implements a Tree Abstract Data Type in order to find word chains. This algorithm is similar to a Breadth First Search, except that it’s actually building the tree as it goes and then traces it back to the root once it’s either explored all related words, or found the target word.

def build_word_chain(start_word, end_word) children = Set.new([start_word.to_sym]) parents = { start_word.to_sym => nil } target = end_word.to_sym until children.empty? steps = Set.new children.each do |child| adjacent_words(child.to_s).each do |next_step| unless parents.has_key?(next_step) parents[next_step] = child return word_chain(parents, target) if next_step == target steps << next_step end end end children = steps end p "no chain" end

def word_chain(parents, target) chain = [target] chain << target while target = parents[target] p chain.reverse end

#coding #breadth first search #ruby

Abstract Data Types

Data Structures

Data structures are ways of organizing information in a programming language. They include things like Arrays, Hashmaps or Strings.

Abstract Data Types

Abstract Data Types (ADTs) are conceptual ways of organizing information. Data Structures implement ADTs. As their name suggests, ADTs are more abstract than Data Structures. Examples of ADTs includes a map, a stack or a queue. It doesn’t matter how you implement an ADT, as long as you follow the application program interface (or API) of the ADT, it will work. How you implement an ADT will affect performance, but not functionality. Map (Or Dictionary)

A map is an ADT that organizes data into key value pairs. It needs to be able to find the value associated with a key, assign a value to a key, or delete a key. When assigning a key a map must check if the key already exists and assign a new value to the existing key if it does before adding a new key. This API is essential for a map to work properly, but it’s not essential that a map be implemented using a Hashmap for it to work properly.

Later I’ll talk more about why a Hashmap implements a map so very well.

Set

A set is a group of distinct values. It’s an example of a different ADT that you could implement with a Hashmap. The essential thing about a Set is that it doesn’t have any duplicates. If you create a Hashmap where they keys all point to true, that will implement a set, because when you add a key that’s already in the Set, you won’t wind up adding a duplicate (you’ll just set it to true again).

Queue

A queue is most efficiently implemented by an Array. For a Queue to function properly, items must only be added to one end of the the Array, and removed/read from the other end of the Array, which can be used by restricting yourself to either #push and #shift or #deshift and #pop. This is also called First In First Out or FIFO.

Stack

A stack is sort of the inverse of a Queue. The rule with a stack is Last In First Out or LIFO. A stack could also be implemented using an Array by restricting yourself to only #push and #pop. A stack could also be implemented with recursion by taking advantage of the implicit call stack. Recursive methods are really just algorithms that use a stack, and could be implemented recursively or with a manual stack.

Trees

A tree is a group of data points, called nodes, that are organized into parent-child relationships. A node with no parents, is called the root. A node with no children is called a leaf. A node can have at most one parent, or the data structure isn’t a tree.

There are different types of trees with different limits on how many children a node can have.

Binary: A node can have at most two children.

Ternary: A node can have at most three children.

N-Ary or Poly: A node can have an unlimited number of children

Unary: A node can have at most one child. This is also (and more descriptively) referred to as a linked list.

Trees are very powerful ADTs, if somewhat complex. A Tree is a good way of implementing an AI for example. A tree is the ADT I had to use to write the word-chain program.

A Tree structure that you interact with all the time is your directory. All of the folders on your computer are organized in a PolyTree structure. A folder can contain any number of folders. But, a single folder can’t be contained within more than one other folder. That’s a tree.

Algorithms

An algorithm is a layer more abstract than an ADT. An Algorithm requires certain ADTs to work, and can’t be implemented without specific ADTs. It still doesn’t matter what Data Structure you use to implement the ADT that implements an Algorithm, but you can’t implement an Algorithm without the right ADT.

Breadth First Search (BFS)

BFS is a way of traversing a Tree in which you start at the root and move through the tree one layer at a time. A BFS is implemented using a queue.

Depth First Search (DFS)

DFS is a way of traversing a Tree in which you go straight to the leaves, and back your way up the tree. A DFS is implemented with a stack (and so it can be implemented recursively).

#coding #data structures #abstract data types #algorithms

wylliamjudd

stack overflow question

I submitted this question to stack overflow. Will let you know the solution.

I’m getting the error “uninitialized constant User::BCrypt”.

I checked this question: https://github.com/ryanb/nifty-generators/issues/68

Suggested solution to bundle install doesn’t work (of course, I bundle install frequently).

I checked this question: https://github.com/codahale/bcrypt-ruby/issues/89

Suggested solution to change the gem to ‘bcrypt-ruby’ instead of just 'bcrypt’ does update my gem to a newer version, but doesn’t solve the problem.

Here’s my User Model

class User < ActiveRecord::Base validates :username, :password_digest, :session_token, presence: true validates :session_token, uniqueness: true attr_reader :password def self.find_by_credentials(username, password) user = User.find_by_username(username) user.try(:valid_password?, password) ? user : nil end def valid_password?(password) BCrypt::Password.new(self.password_digest).is_password?(password) end def password=(password) @password = password self.password_digest = BCrypt::Password.create(password) end def reset_session_token self.session_token = SecureRandom.urlsafe_base64 self.save! self.session_token end end

wylliamjudd

Turns out I needed “require ‘bcrypt’” at the top of my user.rb file. I’m pretty sure this didn’t used to be required, but as of bcrypt version 3.1.5 it seems to be required.

stack overflow question

I submitted this question to stack overflow. Will let you know the solution.

I'm getting the error "uninitialized constant User::BCrypt".

I checked this question: https://github.com/ryanb/nifty-generators/issues/68

Suggested solution to bundle install doesn't work (of course, I bundle install frequently).

I checked this question: https://github.com/codahale/bcrypt-ruby/issues/89

Suggested solution to change the gem to 'bcrypt-ruby' instead of just 'bcrypt' does update my gem to a newer version, but doesn't solve the problem.

Here's my User Model

minesweeper

I made minesweeper. I don’t really know what to say about it. It took me a while to write. Just practice with Object Oriented Programming I guess. Here’s some nice code that expresses whether you’ve won or lost:

def won non_bombs = @grid.flatten.reject(&:bomb?) non_bombs.all?(&:revealed) end

def lost bombs = @grid.flatten.select(&:bomb?) bombs.any?(&:revealed) end

And here’s a recursive function. (I don’t know why, but it’s always exciting when this works.)

def explore unless revealed reveal adjacent_tiles.each do |tile| tile.explore if adjacent_bombs == 0 end end end

Trending Blogs

Recently Viewed Blogs

Next Level Code