Why Would You Need a Linked List in Ruby?

I am learning more about linked lists, and one question that kept coming up for me is, what would you use a linked list for in Ruby or Rails programming?

This resource says that you use linked lists to avoid problems and complexity with memory allocation in C.

Basically, to create an array in C, you have to allocate memory, and you have to have some idea of how big the array will be if you want to do that. If the array gets much bigger than the original size, you will have to reallocate memory for the new elements.

Using a linked list is much simpler, because each element or node only needs memory for its content, and a pointer to the next node. Each time you add to the list, you are only adding memory for a new node. And you can add any datatype, of any size, at any node (although I’m not sure this is an issue for Ruby arrays).

But Ruby does all this for us, right?

This excellent article on sitepoint explains that yes, Ruby does this for us, and it does a pretty good job. But you still might want to use a linked list in special cases.  Allocating new memory to add more elements to an array still takes time. So if you have an array with thousands of elements, you might want to look at using a linked list for optimization if you will be adding to it.

But in most cases, it’s fine to add elements to an array, and Ruby will only resize the array if needed.  (It is faster, for larger arrays, to use push or pop instead of shift or unshift.)

Linked lists are also useful immutable data structures for functional programming, if you’re into that sort of thing.

And finally, searching an array and searching a linked list are both O(n) (aka linear) complexity.  You have to search through every element to find a specific element.  If you need a faster lookup time, you’ll need a hash table.

Ruby Array.zip

Learned a neat little trick today:

>>arr1 = [1, 2, 3, 4]
>>arr2 = [5, 6, 7, 8]
>>arr1.zip(arr2)
=> [[1,5],[2,6],[3,7],[4,8]]

Made me smile. It turns out you can use this to iterate over two arrays at the same time and execute a block of code. In JavaScript I’ve gotten used to using a for loop and then indexing using the iterator:

for (i = 0; i < arr.length; i++) {
if arr1[i] == arr2[i]
//do something...
//close brackets etc

But Ruby doesn’t really have a for loop that works that way. Array.zip() to the rescue!

>>arr1.zip(arr2).each do |x, y|
>>if y == x+4
>>puts "awesome!"
>>end
>>end
"awesome"
"awesome"
"awesome"
"awesome"

Benchmarking my Code

I joined Codewars.com last week and I’m a little addicted.  The coding challenges are a good motivation to learn new methods and techniques.

I’ve been working on this kata today.  The challenge states “props if you do it without a nested loop,”  so I tried a few different ways.  After a little noodling around, I decided on the strategy of creating an array of arrays, passing a block to Array.new which would insert the proper values as the array was created.  Then Array.reduce would sum it up for me neat and clean.

I had trouble coming up with the code to initialize the arrays though.  I tried Array.new(weeks) { Array.new(days) } but couldn’t figure out how to increment properly as I went along.  So I just started hacking away, keeping the original idea of creating an array of arrays, inserting the values, and then using reduce at the end.  Here is my first function that passed the tests:

with a loopAs you can see I ended up with a nested loop.  But the tests passed, so I hit submit!

Apparently there’s a cutoff time.  It took more than 6 seconds to complete the tests to pass submission.  So I tried benchmarking the code:

benchmarking benchmarks with a loopHoly crap!  Look at the jump in time.  I know enough about Big O to know this is not good.

So I simplified a little bit:

Screenshot from 2015-11-01 18:44:17No need to create all those arrays, so I just pulled them out.  The results, with the same parameters passed to Benchmark, were:

Benchmarking the sumMuch better.  But although it’s passing the first round of tests, it’s still not passing the 6 second cutoff time for the submit tests, so I’ll keep trying.

I Am Determined to Build a Twitter Bot!

I haven’t figured out the problem with the MicroBlogger tutorial that I’ve been posting about. But I’ve become intrigued by the idea of building a twitter bot.

I went through the Codecademy Twitter API course. It was a nice, very basic introduction. A little googling led me to several more tutorials on building a twitterbot, which I’m posting here for reference.

How to Make an eBooks Bot

Five Steps To Build Your Own Random Non-Sequitur Twitter Bot

Create a Twitter Bot Using Ruby

Do You Know How to Create a Bot in Ruby?

Updating OpenSSL on Windows

My last post was about some problems I ran into with authenticating a twitter spam-bot project, using git bash and the twitter API. I finally figured out how to update Open SSL for my git – I just installed the newest version of Git! I had been using Git for Windows. Installing Git, instead of Git for Windows, updated my SSH version.

After hours of searching for a solution, I was happy to find one. I fired up git and ran ruby micro_blogger.rb, and…

certificate verify failed

Again, certificate verify failed.

I guess it could be that I’m running an older version of ruby? Or maybe something has changed about Twitter’s API. I really have no idea.

This is the frustrating part about learning to code. I am getting confident in my ability to bang out some lines of code that will do what I want. But I spend a lot of time trying to figure out how to make the code work, and many of the tutorials online don’t really address these strange little things that pop up, like the LOAD_PATH not working. I suppose it will get easier eventually.

Meanwhile I think I am going to do Codecademy’s Twitter API course and see if that offers any clues.

Updating OpenSSL on Windows… not so simple

So I figured out the problem in my last post. Then, after getting some things working, I ran into another problem and decided to move on to the next project, creating a Twitter spambot.

Here I ran into a problem with OpenSSL. I googled the problem and discovered a solution. The problem is, the solution doesn’t work for Windows.

I have tried to install a linux virtual machine in the past. I spent hours on it and could never get it to work quite right. I could also partition my drive and install linux on my desktop, I suppose. Again, it seems like a lot of work.

xkcd - talk to your kids about linux

I will keep looking. If anyone reading has any solutions, let me know!

LOAD_PATH problem solved, another problem pops up

I’ve been working on the hangman project at the Odin Project.

I had a basic working program. I decided to break it up into some different files to get a better understanding of how classes and files interact with each other.

I had a lot of trouble with getting the dictionary to work once I did this. The game loads a word from a text file containing a long list of random words. Once I put the game into a couple different files, I couldn’t get the text file to load anymore. I was finally able to figure out a solution, although I still don’t completely understand what happened, once I read this blog post.

It seems that once a program has been executed, the file path for that program is set. So when I changed the file structure, the program was still looking for the dictionary (the “5desk.txt” file) in the same old place and couldn’t find it. This is strange, because I didn’t move the dictionary file, just split the ruby code into two different files. I added the following to my code:

File.join(File.expand_path(File.dirname(__FILE__)), "..", "5desk.txt")

and now things work.

I am still not 100% clear on how this works (more like 60%), so if any readers have reading materials or comments that can help me understand, please share!

Once I got the dictionary to work, I had to change the ruby code a little to reference the right instance variables. As it currently stands, the program runs, but the turns are borked. Instead of the turns variable counting up from 0, I can only run one game round, the turns variable gets set to the length of the word, and the program exits. I have pushed the code to github here, and I’ll copy some of it below since the github code will change in the future.

play.rb:

File.join(File.expand_path(File.dirname(__FILE__)), "..", "5desk.txt")
require_relative "lib/hangman.rb"
require_relative "lib/game_engine.rb"

play = GameEngine.new
play.play_game

lib/game_engine.rb:

require_relative "hangman.rb"

class GameEngine

def initialize
@game = Game.new
@turns = 0
@score = 0
end

attr_accessor :turns
attr_accessor :score
attr_accessor :game

def take_guess
puts "Guess a letter!"
print ">"
input = gets.chomp.downcase
@game.guesses.push(input)
i = 0
while i <= @game.word.length
if input == @game.word[i]
puts "The word contains #{input}!"
@game.word_board[i] = input
i += 1
else
i += 1
@turns += 1
end
end
print "#{@game.word_board.join} Guesses: #{@game.guesses.join} "
end

def play_game
print @game.word.join+"n"
print @game.word_board.join
while @turns < @game.word.length
take_guess
puts " Turn #{@turns}"
end
end
#end class
end

lib/hangman.rb:
require_relative "game_engine.rb"

puts "Hangman initialized"

class Game

def initialize
puts "New game initialized"
@word = pick_random.downcase.split(//).slice(0..-2)
@word_board = []
@guesses = []
create_word_board
end

attr_accessor :word_board
attr_accessor :word
attr_accessor :guesses

def pick_random
chosen_line = nil
File.foreach("5desk.txt").each_with_index do |line, number|
chosen_line = line if rand < 1.0/(number+1)
end
return chosen_line
end

def create_word_board
@word.length.times do
@word_board.push("_ ")
end
end
end