DEV Community: Luciano Muñoz

CS50: Week 5, Data Structures

Luciano Muñoz — Sat, 10 Sep 2022 12:26:26 +0000

Three months have passed since I wrote my last post. I’ve finished the CS50 course on time, but work and life made me choose others than writing, but I wanted to recover the feeling of doing something for the dev community, so here we go again… Finishing the CS50 series with this post! I hope you enjoy it.

In past lessons, we’ve learned about memory, and we’ve been working with arrays. The problem with arrays to store a large amount of data is that they have fixed size and their values are stored in contiguous memory addresses, so if you want to add a new item you have to allocate a new block of memory with enough space for the new array, copy value by value including the new element, and lastly, delete the old array. Arrays offer constant time O(1) for lookup thanks to random access, but they’re bad for inserting/deleting an element, especially when we are working with large arrays because copy value by value takes linear time O(n).

Linked Lists

A linked list is a data structure that, unlike arrays, it allows us to store a list of values in different parts of memory, giving us a better time complexity for inserting new values.

With linked lists doesn’t matter where the data is stored, we can use small chunks of free memory for each node, stitching them together with pointers:

We have the tradeoff of needing to allocate more memory for each item (for its value and the pointer to the next element), in order to spend less time adding values, because you don’t need all the copy process arrays to do to add an element.

Linked lists are composed of nodes that store its value and the pointer to the next element of the list. We could define a node in C like this:

typedef struct node
{
    int number;
    struct node *next;
}
node;

Linked lists usually have a property called head, which is a pointer to the first node of the list. Each time we want to add a new node to the list, we just make the new node point to the current head element, and then make head point to the new node. In this way we are inserting new nodes at the beginning of the list, which takes constant time O(1) since the required steps don’t change doesn’t matter how many items the list has. On the other hand, inserting nodes into a sorted list will have a running time of O(n), since we might need to insert our nodes at the end.

Unlike arrays, searching is not a powerful feature of linked lists, we have a running time of O(n) for searching since we need to follow each node, one at a time, to search for a value. We won’t be able to use binary search either, since we can’t use indexes to access elements.

Binary Trees

A tree is another data structure where each node points to other nodes. It allows us to store a list of values in different parts of memory, just like linked lists. But, preserves the searching power of arrays, allowing us to use Binary search (divide and conquer approach), since each node points to one to the left (with a smaller value) and one to the right (with a larger value).

Every left child is smaller than the root, and every right child is larger than the root, as we can see in the picture below:

Each node has at most two children, or nodes it is pointing to. And like a linked list, we’ll want to keep a header pointer to the beginning of the list, the root of the tree. To search for a number, we’ll start at the root node, and be able to recursively search the left or right subtree.

We can define a node in C like this:

typedef struct node
{
    int number;
    struct node *left;
    struct node *right;
}
node;

If we add nodes in inefficient ways, though, our binary search tree might start to look like a linked list:

We can make the tree balanced, or more optimal, by making the node with value 2 the new root node.

With a balanced binary search tree, the running time for search and insert will be O(log⁡ n). But if our tree isn’t balanced, it can devolve into a linked list, with running time for search and insert of O(n).

Binary trees are used for efficient searching and sorting.

Hash Table

A hash table is a data structure that allows us to associate keys with values. It looks like an array, where we can jump to each location by its index (key). Keys are hashed and converted into an index where we can find the value stored.

If we need to implement a phone book, we could think of each location as a letter from A through Z, and insert names into each location. If we have multiple names with the same first letter, we can add them with a linked list, like this. Using a linked list to store values is a method to solve hash collisions, and is called chaining:

To create the hash table in C, we might write:

node *hash_table[NUMBER_OF_BUCKETS];

Since a hash table is just an array of pointers to nodes, with NUMBER_OF_BUCKETS as its size.

To decide which location in the array a value should be placed in, we use a hash function, which takes some input and produces an index.

It turns out that the worst case running time for searching a hash table is O(n) since all of our values might be in the same location, devolving into a linked list as well. But, on average the running time is constant O(1).

Hash tables are used for database indexes, implementing caches, implementing set data structures, etc. And offer constant time for adding, removeing, and lookup elements. But they’re not an ideal data structure if sorting is the goal.

Trie

A trie is a tree with arrays as nodes. It gives us constant time lookup, even for massive datasets. Supposing we are looking to store names:

Each array will have locations that represent each letter, A-Z.

For each word, the first letter will point to an array, where the next valid letter will point to another array, and so on, until we reach a boolean value indicating the end of a valid word, marked in green:

With multiple names, we start seeing some of the space being reused for the first letters that are shared:

We might define a trie in code with a structure like this:

typedef struct node
{
    bool is_word;
    struct node *children[SIZE_OF_ALPHABET];
}
node;

At each node, we’ll have a boolean value that indicates if it’s a valid word. Then, we’ll have an array of SIZE_OF_ALPHABET pointers to other nodes, called children.

The good thing is that the height of our trie is the length of the longest word we want to store.

And even if our data structure has lots of words, the maximum lookup time will be just the length of the word we’re looking for. Doesn’t matter how many names contain the trie, will always take 5 steps to find the name “Harry”.

Tries have a constant time O(1), for searching and insertion. The cost for this, though, is that we need lots of memory to store mostly arrays with null pointers.

Summary

Here you have some sort of summary of each data structure seen on this post:

Linked Lists

Insertion is easy - just stack onto the front
Deletion is easy - once you find the element
Lookup is bad - have to rely on linear search
Relatively difficult to sort - unless you’re willing to compromise on super-fast insertion and instead sort as you construct
Relatively small size-wise (not as small as arrays)

Hash Tables

Insertion is a two-step process - hash, then add
Deletion is easy - once you find the element
Lookup is on average better than linked lists because you have the benefit of a real-world constant factor. You have smaller linked lists on each location instead of one entire linked list.
Not an ideal data structure if sorting is the goal, just use an array
Can run the gamut of size. It depends on the height of the hash table and the length of the linked lists on each location.

Tries

Insertion is complex - A lot of dynamic memory allocation, but gets easier as you go
Deletion is easy - Just free a node
Lookup is fast - not quite as fast as an array, but almost
Already sorted - sorts as you build in almost all situations
Rapidly becomes huge, even with very little data present, not great if space is at a premium

If you wanna know more about time complexity of different data structures and sorting algorithms here you have a great cheatsheet: bigocheatsheet.com

There are more data structures like queues, stacks, doubly linked lists, b-trees, etc; but maybe we can see some of them in other posts. This is a really important topic to learn and understand, not just because they’re present in every tech interview, but because they’re really helpful and improve us as developers to take better decisions when storing data.

On each data structure, we always pay a price, we must choose to minimize space, or minimize time. It’s not really possible to get the best of both worlds. That’s why is so important to learn about data structures: to make smart decisions.

See you soon! 😉

Thanks for reading. If you are interested in knowing more about me, you can give me a follow or contact me on Instagram, Twitter, or LinkedIn 💗.

Web Scraping with Python

Luciano Muñoz — Tue, 14 Jun 2022 17:31:58 +0000

Scraping is a technique for extracting data from a website when there’s no other source to obtain that data, like a Rest API or RSS feed.

Google and other search engines have bots scraping all the information that later you see in your search results. Not just search engines use scraping, but also other kinds of websites, for example, for pricing, flights, and hotels comparison.

I want to show you in this post how we can develop our own bot. You could use the same approach that I use to track the price of that product you want, or get the latest news from the news website you like, the limit is your imagination.

I recommend you the book Web Scraping with Python if you want to go a bit deeper into web scraping with Python 🐍.

Let's go!

¿How does scraping work?

There are different ways, but the most used technique is by obtaining the HTML code of the target website, and telling our bot what tags or attributes it has to search for, and where the information we want is stored.

Imagine a website with this HTML structure:

<section class="layout-articles">
    <!-- News 1 -->
    <article>
        <h1 class="title">
            <a href="/news-1" title="News 1">
                News 1
            </a>
        </h1>
        <img src="news-1.jpg">
    </article>
    <!-- News 2 -->
    <article>
        <h1 class="title">
            <a href="/news-2" title="News 2">
                News 2
            </a>
        </h1>
        <img src="news-2.jpg">
    </article>
</section>

If we want to get all the news titles of this page, we could search for the section element which contains the attribute class="layout-articles", and from them get all the a tags that contain the title and URL of each news item.

This is just a simple example for you to have a better understanding of scraping.

¿What are we going to build?

There’s a great site called Simple Desktops, with a cool collection of fancy wallpapers, and our bot will take care of browsing the pages of this site and downloading each wallpaper 👏👏👏.
https://giphy.com/embed/l41lUJ1YoZB1lHVPG
First, let’s analyze the HTML structure of the website, which allows us to understand the steps our bot must follow for its task:

Website pagination works as follows, /browse/, /browse/1/, /browse/2/
On each page, each wallpaper is a div class="desktop" containing an img tag whose src attribute has the URL to download the wallpaper.
The site uses a thumbnail generator implicit in the URL of each wallpaper image, but if we delete the text • that referred to the resize we can have access to the original image: Apple_Park.png~~.295x184_q100.png~~ 😎.
The URL to the next page is stored in the <a class="more" tag.

With the information collected before we can say that our algorithm must follow these steps:

Do a request to /browse/ URL
Get the wallpapers URL from the src attribute of img tag contained in each div class="desktop" tag
Remove the resize from the wallpaper URL
Download the wallpapers
Get the URL of the next page of the site and repeat step 2

Great, now that we know what to do… ¡let´s code!🎈

¿How to create a bot in Python?

These are the packages we will use:

os: for handling file paths and folders
re: for regular expressions
shutil: for file operations
requests: for HTTP requests
BeautifulSoup: for parsing the HTML code, the heart of our bot ❤️

BeautifulSoup and requests are two packages not built-in in Python, so we’re going to install them with pip:

$ pip install beautifulsoup4
$ pip install requests

We’re going to split our code into functions to make it easy to read and debug.

Create a directory and inside create a file called simpledesktop-bot.py. First, we start by importing the packages:

import os
import re
import shutil
import requests
from requests.exceptions import HTTPError
from bs4 import BeautifulSoup

At the entry point of our app we configure the initial data so that it can start running:

if __name__ == '__main__':
    # Run, run, run
    url = 'http://simpledesktops.com'
    first_path = '/browse/'
    download_directory = os.path.join(os.path.dirname(os.path.abspath(__file__)), 'wallpapers')

    # Create download directory if it does not exists
    if not os.path.exists(download_directory):
        os.makedirs(download_directory)

    # Start crawling
    processPage(url, first_path, download_directory)

At the beginning, we set the initial data, like the website URL, the path of the first page where our bot will start running, and a directory to store the downloaded wallpapers. If that directory doesn’t exist we create it with the os.makedirs method.

In the last place, we call the function processPage() to start the scraping process.

def processPage(url, path, download_directory):
    """
    Recursive function that deliver pages to request and wallpaper's data to the other functions
    """
    print('\nPATH:', path)
    print('=========================')

    wallpapers = getPageContent(url + path)
    if wallpapers['images']:
        downloadWallpaper(wallpapers['images'], download_directory)
    else:
        print('This page does not contain any wallpaper')

    if wallpapers['next_page']:
        processPage(url, wallpapers['next_page'], download_directory)
    else:
        print('THIS IS THE END, BUDDY')

processPage() is a recursive function that acts as a wrapper to manage the calls to the other functions.

The first called function is getPageContent(), which makes the HTTP request, analyzes the HTML structure, and returns a dictionary with the following data:

images: it’s a list containing each wallpaper’s URL
next_page: the URL path to the next page to process

If wallpapers['images'] is not empty, then we call downloadWallpaper(), which receives the list of image’s URL and the download directory, and it’s in charge of processing each download.

Lastly, if wallpapers['next_page'] exist, then we call recursively processPage() with the path for the next page, otherwise, the program ends.

Now let’s see the code of each function that processPage() calls.

def getPageContent(url):
    """
    Get wallpaper and next page data from requested page
    """
    images = []
    next_page = None

    html = requestPage(url)
    if html is not None:
        # Search wallpapers URL
        wallpapers = html.find_all('div', {'class': 'desktop'})
        for wp in wallpapers:
            img = wp.find('img')
            images.append(img.attrs['src'])

        # Search for next page URL
        try:
            more_button = html.find('a', {'class':'more'})
            next_page = more_button.attrs['href']
        except:
            pass

    return {'images': images, 'next_page': next_page}

getPageContent() is the heart of our program, because its goal is to make a request to the page received by parameter and return a list of the wallpaper’s URL and the URL path of the next page.

First let’s initialize the image and next_page variables, which are going to store the return data.

Then we call requestPage(), which makes the HTTP request and returns the HTML content already parsed and ready to be manipulated. Here is where we see the black magic behind BeautifulSoup!. Using the find_all method we get a list of div class="desktop" tag. Then we loop over the list and using the find method we search the img tag and extract the wallpaper URL from the src attribute. Each URL is stored in the images list.

Next, we search for the a class="more" tag, extract the href attribute and store it in the next_page variable.

Lastly, we return a dictionary containing images and next_page.

def requestPage(url):
    """
    Request pages and parse HTML response
    """
    try:
        raw_html = requests.get(url)
        try:
            html = BeautifulSoup(raw_html.text, features='html.parser')
            return html
        except:
            print('Error parsing HTML code')
            return None
    except HTTPError as e:
        print(e.reason)
        return None

Now let’s see what requestPage() does. It requests the URL page received by parameter, and stores the payload into the raw_html variable. Then parse the plain HTML with BeautifulSoup and return the parsed content.

With try/except we intercept any error that may be raised.

def downloadWallpaper(wallpapers, directory):
    """
    Process wallpaper downloads
    """
    for url in wallpapers:
        match_url = re.match('^.+?(\.png|jpg)', url)
        if match_url:
            formated_url = match_url.group(0)
            filename = formated_url[formated_url.rfind('/')+1:]
            file_path = os.path.join(directory, filename)
            print(file_path)

            if not os.path.exists(file_path):
                with requests.get(formated_url, stream=True) as wp_file:
                    with open(file_path, 'wb') as output_file:
                        shutil.copyfileobj(wp_file.raw, output_file)
        else:
            print('Wallpaper URL is invalid')

downloadWallpaper() receives a list with the wallpaper’s URL to process each download. The first task this function does is delete from the URL the piece of text that works as a resize.

http://static.simpledesktops.com/uploads/desktops/2020/03/30/piano.jpg.300x189_q100.png

Deleting .300x189_q100.png from the end of the URL allows us to download the image with their original size. To accomplish this task we’re using the regular expression ^.+?(\.png|jpg), which returns the URL from the start until the first occurrence of .png or .jpg is found. If there is no match then the URL is not valid.

Then we extract the file name using the function rfind(’/’) to find the first slash character starting from the right of the string, where the filename starts. With this value and the directory, we save in the variable file_path the destination in our computer where the wallpaper will be downloaded.

In the next block of code, we check first if the wallpaper doesn't already exist to prevent downloading it again. If the file does not exist we execute the following steps:

We download the file using requests.get() and store a reference to the binary file in memory in the variable wp_file.
Then we open() the local file in binary and writing mode and reference that file as output_file.
The last step is to copy the content of wp_file (the downloaded image) into output_file (the file on disk) using shutil.copyfileobj().

We have already downloaded the wallpaper and saved it on our disk.

There’s no need to free the memory of opened files because we’re working inside a with statement, which manage it automatically.

And that’s all, we can now execute the program. To run it just open the console and type python3 simpledesktop-bot.py:

$ python3 simpledesktop-bot.py

PATH: /browse/
=========================
/Users/MyUser/simple-desktop-scraper/wallpapers/sphericalharmonics1.png
/Users/MyUser/simple-desktop-scraper/wallpapers/Dinosaur_eye_2.png
/Users/MyUser/simple-desktop-scraper/wallpapers/trippin.png
...

PATH: /browse/2/
=========================
/Users/MyUser/simple-desktop-scraper/wallpapers/Apple_Park.png
/Users/MyUser/simple-desktop-scraper/wallpapers/triangles.png
/Users/MyUser/simple-desktop-scraper/wallpapers/thanksgiving_twelvewalls.png
...

PATH: /browse/3/
=========================
/Users/MyUser/simple-desktop-scraper/wallpapers/minimalistic_rubik_cube_2880.png
/Users/MyUser/simple-desktop-scraper/wallpapers/Nesting_Dolls.png
/Users/MyUser/simple-desktop-scraper/wallpapers/flat_bamboo_wallpaper.png
...

You can find the code in the GitHub repository, and if you like it give it a star 😉.

SimpleDesktop-Bot

Thanks for reading, it is very valuable for me that you have read this post. I hope you have learned something new, as I did when I was writing and coding this, if so leave a comment or send me a tweet because I would love to know it.

See you soon! 😉

Thanks for reading. If you are interested in knowing more about me, you can give me a follow or contact me on Instagram, Twitter, or LinkedIn 💗.

CS50: Week 4, Memory

Luciano Muñoz — Tue, 07 Jun 2022 18:02:59 +0000

In week 2 we took a look at memory and how we could use arrays to store data. Now, in week 4, David Malan goes a bit deeper into memory management, introducing us to memory addresses, pointers, and memory allocation, among other low-level and interesting things.

If you remember, Memory RAM is like a huge grid where information is stored as 0's and 1's. Each square of the grid has an address used by the computer when reading and writing information into it. These addresses are described using the hexadecimal system.

Hexadecimal

The hexadecimal system is a much more concise way to express data. It is easier for a person to remember the number 72 to refer to the letter H, instead of the equivalent in binary 01001000. The same thing happens with memory addresses, it is easier to read 0x5FA3F than its equivalent in decimal system 391743 or in binary 1011111101000111111. The values in a computer’s memory are still stored as binary, but hexadecimal helps us, humans, represent larger numeric values with fewer digits needed.

Hexadecimal system, or base-16, is formed by 16 digits:

0 1 2 3 4 5 6 7 8 9 A B C D E F

The digits start with 0 through 9, and continue with A through F as equivalents to the decimal values of 10 through 15. After F, we need to carry the one, as we would go from 01 to 10 in binary:

16^1 16^0
  1    0   =  16

Here, the 1 has a value of 16^1×1 = 16, so 10 in hexadecimal is 16 in decimal.

With two digits, we can have a maximum value of FF, or (remember that F is 15 in the decimal system):

16^1×15 + 16^0×15 = 16×15 + 1×15 = 240 + 15 = 255

With 8 bits in binary, the highest value we can count to is also 255, with 11111111. So two digits in hexadecimal can conveniently represent the value of a byte in binary. (Each digit in hexadecimal, with 16 values, maps to four bits in binary.)

Pointers

When we create a variable in our program, it is stored at some memory location. That memory location has an address, which is described using hexadecimal.

int n = 50;

In our computer’s memory, there are now 4 bytes (remember that an int takes 4 bytes in memory) somewhere that has the value of 50, with some value for its address, like 0x123.

By writing 0x in front of a hexadecimal value, we can distinguish them from decimal values.

A reference to that address in memory can be stored in another variable, which is better known as a pointer. So, a pointer is a variable that stores a memory address, where some other variable might be stored, the specific byte in which that value is stored.

Also, pointers provide a way to pass data by reference between functions. By default, C passes data by value, which means it only passes a copy of that data. Using pointers we can pass a reference to work with the original data.

A pointer value is a memory address, and the type of the pointer describes the data stored at that memory address.

In C we can declare a pointer using the * star operator. Also, we can use the & address operator to get the memory address of some variable.

#include <stdio.h>

int main(void)
{
    int n = 50;
    int *p = &n;
    printf("%p\n", p);
}

$ make address
$ ./address
0x7ffcb4578e5c

We can run this program a few times and see that the address of n changes because different addresses in memory will be available at different times.

The * operator is also used as the dereference operator, which goes to an address to get the value stored there:

#include <stdio.h>

int main(void)
{
    int n = 50;
    int *p = &n;
    printf("%p\n", p);
    printf("%i\n", *p);
}

$ ./address
0x7ffda0a4767c
50

The value of a memory address in itself is not significant, since it’s just some location in memory where a variable is stored; but it is a significant idea to use with strings.

Strings

We already saw that C doesn’t have native support for strings, they’re just an array of type char. Because it is an array, we can declare a string with string s = "HI!";, and access each character with s[0], s[1], s[2], and s[3].

Each character has its own memory address, and s is actually just a pointer containing the address of the first character of the string:

Recall that we can read the entire string by starting at the address in s, and continue reading one character at a time from memory until we reach the NUL character \0.

As we can see in the following example, the address of the first character, &s[0], is the same as the value of s:

#include <stdio.h>

int main(void)
{
    char *s = "HI!";
    char *p = &s[0];
        printf("%s\n", s);
    printf("%p\n", p);
    printf("%p\n", s);
}

$ make address
$ ./address
HI!
0x123
0x123

Again, the address of the first character, &s[0], is the same as the value of s. And each following character has an address that is one byte higher:

#include <stdio.h>

int main(void)
{
    char *s = "HI!";
    printf("%p\n", s);
    printf("%p\n", &s[0]);
    printf("%p\n", &s[1]);
    printf("%p\n", &s[2]);
    printf("%p\n", &s[3]);
}

$ make address
$ ./address
0x123
0x123
0x124
0x125
0x126

Because each string is just a pointer to a different location in memory, if we compare two strings containing the same text, they will be different, because we are comparing the addresses where they are stored and not the text.

#include <stdio.h>

int main(void)
{
    char *s = "HI!";
    char *t = "HI!";

    if (s == t)
    {
        printf("Same\n");
    }
    else
    {
        printf("Different\n");
    }
}

$ make compare
$ ./compare
Different

This might look in our computer’s memory like this:

If we now copy the string into another variable we will see that any change made to the copy will affect also the original string:

#include <ctype.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    char *s = "hi!";
    char *t = s;

        // capitalize the first letter
    t[0] = toupper(t[0]);

    printf("s: %s\n", s);
    printf("t: %s\n", t);
}

$ make copy
$ ./copy
s: Hi!
t: Hi!

The concept is the same as with the compare situation, in this case both, variables point to the same address in memory where the string “hi!” is stored.

For both compare and copy operations with strings, the process is similar: loop over the string and compare or copy character by character. Also, you can use the methods strcmp() and strcpy() from the C library string.h created for this purpose. But we will see that in detail below.

Dynamic memory allocation

To make a copy of a string, we have to do a little more work, first, we need a free block of memory that acts like an “empty string”, where to copy the characters. To get a free block of memory there’s a function called malloc which allocates **dynamically some number of bytes in memory for our program to use. Once we´re done with the allocated memory, there’s another function called free to give back again the memory to the operating system, so it can do something else with it.

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    char *s = "hi!";

        // + 1 because we need an extra byte for the NUL '\0' character
    char *t = malloc(strlen(s) + 1);
        if (t == NULL)
    {
        return 1;
    }

    strcpy(t, s);

    t[0] = toupper(t[0]);

    printf("s: %s\n", s);
    printf("t: %s\n", t);

    free(t);
}

$ make copy
$ ./copy
s: hi!
t: Hi!

Our computers might slow down if a program we’re running never frees allocated memory. The operating system will take longer and longer to find enough available memory for our program.

If the computer is out of memory, malloc will return NULL, a special value of all 0 bits that indicates there isn’t an address to point to. So we’re checking for that case in our example, and exit if t is NULL.

Now both s and t point to a different memory location where hi! and Hi! are stored.

We must be careful when allocating memory with malloc, if we don’t initialize our variables, we will end up getting what is known as garbage values, random data that were in the block of memory that the system gave us. And if we try to go to an address that’s a garbage value, our program is likely to crash from a segmentation fault error.

Next, we are going a bit deeper into how memory works.

Memory layout

So far we’ve been talking about memory imagining it is like a huge grid, where magically the computer stores and retrieves data. Going deeper about how memory works, different types of data that need to be stored for our program are organized into different sections:

The machine code section is our compiled program’s binary code. When we run our program, that code is loaded into memory.

Just below, or in the next part of memory, are global variables we declared in our program.

The heap section is an empty area from where malloc can get free memory for our program to use. As we call malloc, we start allocating memory from the top down.

The stack section is used by functions and local variables in our program as they are called and grow upwards.

If we call malloc for too much memory, we will have a heap overflow, since we end up going past our heap. The three golden rules of memory allocation are:

Every block of memory allocated with malloc must subsequently be freed.
Only memory you malloc should be freed, to prevent segmentation fault errors.
Do not free a block of memory more than once.

On the other hand, if we call too many functions without returning from them, we will have a stack overflow, where our stack has too much memory allocated as well.

But, why could we call too many functions without returning from them? Maybe for a bug in a recursive function.

Call Stack

The call stack is the flow that C uses to work. When you call a function, the system sets aside space in memory for that function to do its work. Those chunks in memory are known as stack frames or function frames.

More than one function’s stack frame may exist in memory at a given time, for example, we have a main() function which calls to move() function, which also calls to direction() function. All of them are in memory, but just one function is active doing its work.

Frames are arranged in a stack. A stack is a linear data structure that follows LIFO (Last In First Out) as the order in which the operations are performed. The frame for the most recently called function is always on top of the stack and is the active frame. When a function finishes its work, its frame is popped off the stack and the frame immediately below becomes the active frame, which continues doing its work where it left off.

This is how recursion works. But maybe it is better to explain it with the example of the factorial calculation:

#include <stdio.h>

int main(void) {
    printf("%i\n", fact(5));
    return 0;
}

int fact(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * fact(n - 1);
    }
}

      CALL STACK
-------------------------     ______
|        fact(0)        |    |      |
-------------------------    |      |
|        fact(1)        |    |      |
-------------------------    |      |
|        fact(2)        |    |      |
-------------------------    |      |
|        fact(3)        |    |      |
-------------------------    |      |
|        fact(4)        |    |      |
-------------------------    |      |
|        fact(5)        |    |      |
-------------------------    |      |
|         main()        |    |      |
-------------------------    ˄      ˅ ORDER OF EXECUTION

First, our program executes the main() function, and its frame is pushed to the stack.
Then main() calls the fact(5) function. For main() finishes its work, it needs the result of fact(5), so the frame for this function is pushed on top of the stack.
For fact(5) to finish its work, it needs the result of fact(n-1), which is the same as fact(4), so the frame for this function is pushed on top of the stack.
The process repeats until the program reaches fact(0).
fact(0) is the first function in returning a value, it returns the number 1. At this point, the frame for fact(0) is popped off from the stack.
fact(1) uses the value returned by fact(0) to calculate and return its own value, and then it’s also popped off from the stack.
Once fact(5) returns its value and is popped off from the stack, the main() function picks up its work where it left at the beginning, prints the factorial, and returns 0.
At this point, the program ends and the call stack gets empty.

I think it is great to know how memory works in general, and how programming languages manage it to do its work. I hope you found it interesting too. It is a topic that recruiters may ask when you’re in an interview, so better have a notion about it.

In the next post: data structures 😃, a must if you wanna be a good developer.

See you soon! 😉

Thanks for reading. If you are interested in knowing more about me, you can give me a follow or contact me on Instagram, Twitter, or LinkedIn 💗.

CS50: Week 3, Sorting and Searching Algorithms

Luciano Muñoz — Wed, 11 May 2022 20:28:05 +0000

Since previous lectures, we’ve been learning about memory, how to store data in it, the types and sizes of data, among others things.

If we need to manage a large amount of data, it is convenient to use an array to store it, we already know how to do it, so this week David Malan teaches how to sort and search values in arrays explaining Searching Algorithms and Sorting Algorithms.

Big O and Big Omega

To understand the difference between distinct algorithms, we must first have a notion about Big O notation. In computer science, we can measure the efficiency of an algorithm in terms of memory consumption and running time. Big O notation is a special notation that measures running time, it tells you how fast an algorithm is, or how long an algorithm takes to run given some size of input. It doesn’t measure running time in seconds or milliseconds, instead, it gives us an idea of how many operations an algorithm performs in relation to the input it receives.

Big O describes the upper bound of the number of operations, or how many steps an algorithm might take in the worst case until it finishes, while Big Omega notation (big Ω), in counterpart, describes the lower bound of the number of operations of an algorithm, or how few steps it might take in the best case.

The image above expresses the running time of three different ways of searching for a person in a phone book:

The red line represents searching on one page at a time starting from the beginning. It could take a lot of time find someone because the the searching becomes proportionally longer to complete as the phone book grows. If it takes 1 second to check 10 name, it will take 2 seconds to check 20 names, 3 seconds to check 30 names, 100 seconds to check 1000 names, and so on.
The yellow line represents searching on two pages at a time. It is double faster than the first option but still takes a lot of time to complete the search.
The green line represents the last and most efficient option, a divide and conquers approach. Open the phone book in the middle, if the target name is not there, then preserve the half where the name alphabetically must appear and discard the other half. Then repeat the process with the remaining half until the target is found. It’s much faster than the other two options because the time required to find a name goes up linearly while the size of the phone book grows exponentially. So if it takes 1 second to check 10 names, it will take 2 seconds to check 100 names, 3 seconds to check 1000 names, and so on.

In the chart above, if we zoomed out and changed the units on our axes, we would see the red and yellow lines end up very close together:

Since both the red and yellow lines end up being very similar as n becomes larger and larger, we can say they have the same time complexity. We would describe them both as having big O of n or on the order of n running time.

The green line, though, is fundamentally different in its shape, even as n becomes very large, so it takes big O of log⁡ n steps 🤯 (later we will see why).

The most common running times are:

O(n2) - Quadratic time
O(n * log n) - Linearithmic time
O(n) - Linear time
O(log n) - Logarithmic time
O(1) - Constant time

Linear Search

Is the simplest and intuitive method for finding an element within an array. The steps required to perform Linear Search would be:

Start from the leftmost element of the array.
Check if the target value matches the value stored in the array.
If matches, then the algorithm finishes successfully.
If it doesn’t match, repeat step 2 with the next element of the array.
If the array finishes with no matches, then the target is not present in the array.

We might write the algorithm pseudocode as:

For each element from left to right
    If number is at this position
        Return true
Return false

In the next example we search for the number 7:

list = [0, 2, 10, 4, 7, 9]

[0, 2, 10, 4, 7, 9] --> 0 is not equal to 7
 ^
[0, 2, 10, 4, 7, 9] --> 2 is not equal to 7
    ^
[0, 2, 10, 4, 7, 9] --> 10 is not equal to 7
       ^
[0, 2, 10, 4, 7, 9] --> 4 is not equal to 7
           ^
[0, 2, 10, 4, 7, 9] --> MATCH
              ^

The number 7 was found after 5 iterations

With n elements, we’ll need to look at all n of them in the worst case (e.g. if we were searching for the number 9 in the example above), so the big O running time of this algorithm is linear O(n).

The lower bound, would be Ω(1), since we might be lucky and find the number we are looking for at the first position of the array (e.g. if we were searching for the number 0 in the example above). Ω(1) is also known as constant time, because a constant number of steps is required, no matter how big the problem is.

Linear Search is correct because it solves the searching problem, but it is not very efficient.

Just in case, this is my implementation of Linear Search in Python:

# Linear Search

def linear_search(n, arr):
    # Use the in operator to check if the target value 
    # is on the list
    if n in arr:
        return True
    return False

if __name__ == '__main__':
    array = [53,9,6,23,8,5,4,1,88]
    # Ask the user for a target value
    number = int(input('Que número buscas?: '))
    result = linear_search(number, array)
    if result:
        print('El número existe.')
    else:
        print('El número no existe.')

Binary Search

This method uses an approach called divide and conquer, where we divide the problem in half on each step. This algorithm works only on sorted arrays. The steps required to perform Linear Search would be:

Get an element from the middle of the array.
If the element matches the target value, then the algorithm finishes successfully.
If the target value is smaller than the middle element, narrow the array to the left half.
If the target value is greater than the middle element, narrow the array to the right half.
Repeat from step 1 with the narrowed array.
If the array is empty, then the target is not present in the array.

We might write the algorithm pseudocode as:

If array is empty
    Return false
If number is at the middle position
    Return true
Else if number < number at the middle position
    Search left half
Else if number > number at the middle position
    Search right half

In the next example we search for the number 6:

list = [0, 1, 2, 3, 4, 5, 6]

[0, 1, 2, 3, 4, 5, 6] --> 3 is the middle element. 6 is higher so we search on the right half
          ^
[4, 5, 6] --> 5 is the middle element. 6 is higher so we search on the right half
    ^
[6] --> MATCH
 ^

The number 6 was found after 3 iterations

The upper bound for binary search is O(log⁡ n), known as logarithmic time. When an algorithm has O(log n) running time, it means that as the input size grows, the number of operations grows very slowly. Since in Binary Search we’re discarding the half of the elements on every step, we can say that n (the size of the problem) is reduced exponentially, while the time required to find the target goes up linearly.

The best case scenario for this algorithm is to find the target exactly in the middle, in the first iteration, which means that the Big Omega running time is in the order of Ω(1).

Even though binary search might be much faster than linear search, it requires our array to be sorted first. If we’re planning to search our data many times, it might be worth taking the time to sort it first, so we can use binary search.

To understand in-depth how Binary Search works we must know first what recursion is. If you look at the pseudocode again note that we're using the same “search” algorithm for the left and right half. That is recursion, the ability for a function to call itself.

This seems like a cyclical process that will never end, but we’re actually changing the input to the function and dividing the problem in half each time, stopping once there are no more elements left. When the function runs over elements, that is the condition, also known as base case, which tells the recursive function to stop, so it doesn’t call itself over and over forever.

Here is my implementation of Binary Search written in Python:

# Binary Search

def binary_search(n, arr, l):
    # Base Case
    # If there's only 1 element then check explcitly if matches the target value
    if l == 1:
        return True if arr[0] == n else False

    # Calculate the middle of the list
    mid = l // 2

    # Check if the middle element matches the target
    if arr[mid] == n:
        return True
    else:
        # If the target is smaller, repeat the search on the left half 
        # otherwise, look in the right half.
        if n < arr[mid]:
            return binary_search(n, arr[:mid], len(arr[:mid]))
        else:
            return binary_search(n, arr[mid:], len(arr[mid:]))

if __name__ == '__main__':
    array = [53,9,6,23,8,5,4,1,88]
    long = len(array)
    # Ask the user for a target value
    number = int(input('Que número buscas?: '))
    # Sort the array with sorted() function since Binary Search works with sorted lists
    result = binary_search(number, sorted(array), long)
    if result:
        print('El número existe.')
    else:
        print('El número no existe.')

Selection Sort

Selection Sort works by sorting arrays from left to right. The steps required to sort a list with this algorithm would be:

Start from the leftmost element of the array
Traverse the array to find the smallest element
After traversing the array, swap the smallest element with the value on the first position of the array
Repeat from step 2, now starting from the second element, and swap the smallest value with the value on the second position of the array. Continue repeating with the 3rd, 4td, and so on, until the array is sorted.

Because computers can only look at one number at a time, we must iterate over the entire array each time to find the smallest value, without taking into account already sorted elements.

We might write the algorithm pseudocode as:

For i from 0 to n–1
    Find smallest number between numbers[i] and numbers[n-1]
    Swap smallest number with numbers[i]

In the next example we sort the next list:

list = [3, 6, 5, 7, 8, 2]

[3, 6, 5, 7, 8, 2] --> 2 is the smallest element
                ^
[2, 6, 5, 7, 8, 3] --> Swap it with the element on the first position
 ^              ^

[2, 6, 5, 7, 8, 3] --> Now 3 is the smallest, since 2 is already sorted
                ^
[2, 3, 5, 7, 8, 6] --> Swap it with the element in the second position
    ^           ^

[2, 3, 5, 7, 8, 6] --> Now 5 is the smallest number. No swap needed because is already sorted
       ^

[2, 3, 5, 7, 8, 6] --> Repeat the process
                ^
[2, 3, 5, 6, 8, 7]
          ^     ^

[2, 3, 5, 6, 8, 7]
                ^
[2, 3, 5, 6, 7, 8]
             ^  ^

After 5 iterations the  array is sorted

We can say that the algorithm has an upper bound for running time of O(n2), because we will be iterating the array over and over, searching for the smallest number.

In the best case, where the list is already sorted, our selection sort algorithm will still look at all the numbers and repeat the loop, so it has a lower bound for running time of Ω(n2).

Here is my implementation of Selection Sort written in Python:

# Selection Sort

def selection_sort(arr, l):
    # If the list has just one item then it's already sorted
    if l == 1:
        return arr

    # Loop over the entire list
    for i in range(l):
        lowest_index = None
        # Loop over each element to find the smallest one
        for j in range(i, l):
            if lowest_index is None or arr[j] < arr[lowest_index]:
                # Save the index of the smallest element
                lowest_index = j
        # Swap elements
        # It's possible to swap elements like this in Python,
        # avoiding the use of a temporary variable
        (arr[i], arr[lowest_index]) = (arr[lowest_index], arr[i])

    return arr

if __name__ == '__main__':
    array = [53,9,6,23,8,5,4,1,88]
    long = len(array)
    print(selection_sort(array, long))

Bubble Sort

This algorithm sorts elements from right to left using comparison and swapping elements. We compare contiguous pairs of elements and swapping both if the smaller is on the right, and repeating the entire loop until no swaps were needed anymore.

We could describe its functionality as follows:

Look at the first element of the array, which will be the “current value”.
Compare the current value with the next element in the array.
If the next element is smaller, swap both values. Save in a variable that a swap was performed.
Move to the next element of the array and make it the current value.
Repeat from step 2 until the last number in the list has been reached.
If any values were swapped, repeat again from step 1, without taking into account the last element of the array, which will be already sorted.
If the end of the list is reached without any swaps being made, then the list is sorted.

The pseudocode for bubble sort might look like:

Repeat n-1 times
    For i from 0 to n–2
        If numbers[i] and numbers[i+1] out of order
            Swap them
    If no swaps
        Quit

We are going to sort the same list we sorted with Selection Sort to see the differences:

list = [3, 6, 2, 7, 5]

[3, 6, 2, 7, 5] --> compare 3 and 6, they're sorted
 ^  ^
[3, 6, 2, 7, 5] --> compare 6 and 2, swap them
    ^  ^
[3, 2, 6, 7, 5] --> compare 6 and 7, they're sorted
       ^  ^
[3, 2, 6, 7, 5] --> compare 7 and 5, swap them
          ^  ^
// Start from the beginning again

[3, 2, 6, 5, 7] --> compare 3 and 2, swap them
 ^  ^
[2, 3, 6, 5, 7] --> compare 3 and 6, they're sorted
    ^  ^
[2, 3, 6, 5, 7] --> compare 6 and 5, swap them
       ^  ^

// We don't compare 7 because is already sorted. At this point
// we know that the array is sorted, but still we need to loop 
// through the array one more time to check that no more swaps 
// are needed

[2, 3, 5, 6, 7] --> compare 2 and 3, they're sorted
 ^  ^
[2, 3, 5, 6, 7] --> compare 3 and 5, they're sorted
    ^  ^

// At this point the algorithm finishes because there were no
// swaps, and as in the previous iteration, we don't need to
// compare the number 6 because is already sorted.


After 3 iterations the array is sorted

We can say that bubble sort has an upper bound for running time of O(n2), because as with Selection Sort, we must iterate over the array once and once, but the difference is that the lower bound would be Ω(n), because if the array is sorted just a single iteration over the array is needed to check that there were no swaps.

Here is my implementation of Bubble Sort written in Python:

# Bubble Sort

def bubble_sort(arr, l):
    # If the list has just one item then it's already sorted 
    if l == 1:
        return arr

    # Loop over the entire list
    for i in range(1, l):
        # Swaps counter
        swaps = 0

        # Loop over the list to compare pairs of adjacent elements
        for j in range(l-i):
            if arr[j] > arr[j+1]:
                # Swap elements
                (arr[j], arr[j+1]) = (arr[j+1], arr[j])
                swaps += 1

        # If there were no swaps, then the array is sorted
        if swaps == 0:
            return arr

if __name__ == '__main__':
    array = [53,9,6,23,8,5,4,1,88]
    long = len(array)
    print(bubble_sort(array, long))

Merge Sort

This algorithm also makes use of the divide and conquer approach, and the recursion technique, just like Binary Search does. It divides the input array into two halves, calls itself for the two halves until it get an array containing one element (which is considered sorted), and then it repeatedly merges each sorted halves.

We could describe the algorithm with the following steps

Find the middle of the array.
Divide the array from the middle.
Call Merge Sort for the left half of the array.
Call Merge Sort for the right half of the array.
Merge the two sorted halves into a single sorted array

As we’re using recursion, each call to Merge Sort will perform all the steps (from 1 to 5) for the sublist it receives. The base case, when Merge Sort stops calling itself, is when it receives an array with just one element since an array of one element is already sorted.

The pseudocode for bubble sort might look like:

If only one number
  Quit
Else
    Sort left half of number
    Sort right half of number
    Merge sorted halves

It could be difficult to understand the algorithm just by words, so an example could help to show how Merge Sort works.

In the example below, the red arrows represent each call to Merge Sort, which divides the array it receives into two sublists; and the green arrows represent the merging operation.

The strategy is to sort each half, and then merge them. The merging operation works as follows:

Compare the leftmost element of both sublists and move the smallest value to a new array. Repeat the process until both sublists are merged into one array.

If we want to merge the last two sublists of the example above, the steps are the following:

// Compare the first element of each sublist and copy the smallest value 
// to a new array

[3, 27, 38, 43]  [9, 10, 82]  =>  [3]
 ^                ^
[27, 38, 43]     [9, 10, 82]  =>  [3, 9]
 ^                ^
[27, 38, 43]     [10, 82]     =>  [3, 9, 10]
 ^                ^
[27, 38, 43]     [82]         =>  [3, 9, 10, 27]
 ^                ^
[38, 43]         [82]         =>  [3, 9, 10, 27, 38]
 ^                ^
[43]             [82]         =>  [3, 9, 10, 27, 38, 43]
 ^                ^
[]               [82]         =>  [3, 9, 10, 27, 38, 43, 82]
                  ^

The base case for our recursive function will be a list containing just one element, as I said before, a list of one element is considered sorted.

The time complexity of Merge Sort is O(n Log n), as the algorithm always divides the array into two halves, which have a complexity of O(log n); and the merge operation takes linear time, or O(n), since we only need to look at each element once.

The lower bound of our merge sort is still Ω(n log⁡ n), since we have to do all the work even if the list is sorted.

Here is my implementation of Merge Sort written in Python:

# Merge Sort

def merge_sort(arr, l):
    # Base case
    if l == 1:
        return arr

    # Calculate the middle of the list
    mid = l // 2

    # Call merge sort for left and right halves
    left = merge_sort(arr[:mid], len(arr[:mid]))
    right = merge_sort(arr[mid:], len(arr[mid:]))

    # Calculate how many elements must be merged
    merge_q = len(left) + len(right)
    # Empty list were the sublists will be merged into
    sorted_array = []

    for i in range(merge_q):
        # If both sublists have elements to be sorted
        if len(left) > 0 and len(right) > 0:
            # Append smallest value to the sorted list
            if left[0] >= right[0]:
                sorted_array.append(right[0])
                del(right[0])
            else:
                sorted_array.append(left[0])
                del(left[0])
        # If right half is empty append left half to the sorted list
        elif len(left) > 0:
            sorted_array.append(left[0])
            del(left[0])
        # If left half is empty append right half to the sorted list
        else:
            sorted_array.append(right[0])
            del(right[0])

    return sorted_array

if __name__ == '__main__':
    array = [53,9,6,23,8,5,4,1,88]
    length = len(array)
    print(merge_sort(array, length))

I hope you found interesting searching and sorting algorithms, as I found it when taking the class. There are other algorithms, but this is a good first approach to this topic.

The next lecture is about memory: addresses, pointers, allocation, and other concepts to continue learning how computer software works.

I hope you find interesting what I’m sharing about my learning path. If you’re taking CS50 also, leave me your opinion about it.

See you soon! 😉

Thanks for reading. If you are interested in knowing more about me, you can give me a follow or contact me on Instagram, Twitter, or LinkedIn 💗.

CS50: Week 2, Arrays

Luciano Muñoz — Mon, 02 May 2022 15:32:56 +0000

Hi veryone! Continuing with the CS50 series, this is what I found interesting in Week 2. Topics included in this lecture were compilers, debugging techniques, memory, and mostly arrays.

We’re using the C programming language, a compiled language. It means that a compiler traduces the source code into machine code and generates the binary file that the computer runs to execute the software. On the other hand we have also interpreted languages, like Python or Javascript, which are traduced at run-time by an interpreter, line by line.

Compilers execute 4 tasks when compiling code: preprocessing, compiling, assembling, and linking.

Preprocessing involves replacing lines that start with a #, as #include. For example, #include <cs50.h> will tell the compiler to look for that header file, since it contains content, like prototypes of functions, that we want to include in our program. Then the compiler will essentially copy and paste the contents of those header files into our program.
Compiling takes our source code, in C, and converts it to another language called assembly language.
The next step is to take the code in assembly and translate it to binary by assembling it. The instructions in binary are machine code, which a computer’s CPU can run directly.
The last step is linking, where previously compiled versions of libraries that we included earlier, like cs50.c, are combined with the compiled binary of our program. In other words, linking is the process of combining all the machine code into one binary file.

That a language is compiled does not mean that you will never need to debug a program, it is an advantage that the compiler prevents some errors, but we going to debug our programs anyway.

There are different techniques to debug code, like printing variable values on the screen to understand what is doing the software. A better option is using a debugger, which you can run line by line to watch the flow the code follow and how each variable changes. Lastly, we have the rubber duck debugging technique, where we explain what we’re trying to do in our code to a rubber duck (or other inanimate object), and just by talking through our own code out loud step-by-step, we might realize the mistakes we made.

I mentioned in my last post about some of the data types that come with C, which we can use to declare variables and store specific data, like int, float, or char.

Each variable is stored in memory with a fixed number of bytes. These are common type size for most computer systems:

bool is 1 byte size
char is 1 byte size
int is 4 bytes size,
float is 4 bytes size
double is 8 bytes size
long is 8 bytes size
but talking about strings, the size will vary depending on the length of the string.

We can think of bytes stored in RAM as though they were in a grid, one after the other.

A char whose size is 1 byte will is stored in one of those, but an int will use four bytes, four of those squares.

When talking about arrays, we’re referring to one of the most widely used data structure in most programming languages.

In an array, we can store more than one value. In C all the values must be of the same type, but in other languages, an array can contain different types of values.

The particularly of arrays is that they’re stored in memory back-to-back, or contiguously, and we can access their values using bracket notation starting from the element 0: array[0], array[1], array[2], etc.

Arrays, unlike the other data types, don’t have a fixed size in memory, it’s up to you to assign the size when defining the array in the code. But, once you set the size of the array it is permanent, and can’t be changed.

C doesn’t have native support for strings, they’re just an array of type char. Each character in our string is stored in a byte of memory as well:

In C, strings end with a special character, '\0', or a byte with all eight bits set to 0, so our programs have a way of knowing where the string ends. This character is called the null character, or NUL. So, we actually need four bytes to store the string HI!.

The last words of this lecture were about command-line arguments. I’ve seen this before with Python, and now I realize that Python took it from C, and used even the same variable name. In C we have the variables argc and argv that the main function gets automatically when the program is run from the command line. argc (argument count) store the number of arguments, and argv[] (argument vector) is an array of the arguments themselves.

These variables receive at least one parameter when we run our software: the program itself.

$ ./name
argc = 1
argv[0] = './name'

$ ./name Luciano
argc = 2
argv[0] = './name'
argv[1] = 'Luciano'

The code below checks if it receives a name as an argument and prints hello, {name}:

#include <cs50.h>
#include <stdio.h>

int main(int argc, string argv[])
{
    if (argc != 2)
    {
        printf("missing command-line argument\n");
        return 1;
    }
    printf("hello, %s\n", argv[1]);
    return 0;
}

Note also that the main function returns an integer value called an exit status. There are some conventions but by default, we return 0 if nothing went wrong, and 1 or higher if something fails.

Check the code for the Problem set of Week 2.

Next week is about algorithms for sorting and searching, a challenging but necessary topic.

I hope you find interesting what I’m sharing about my learning path. If you’re taking CS50 also, left me your opinion about it.

See you soon! 😉

Thanks for reading. If you are interested in knowing more about me, you can give me a follow or contact me on Instagram, Twitter, or LinkedIn 💗.

CS50: About Week 0 and Week 1

Luciano Muñoz — Tue, 26 Apr 2022 13:43:40 +0000

Hi there!, in my previous post I told you that I’m looking for my first job as a software developer working abroad. After a few failed technical interviews, I realized that in my self-taught learning I missed some concepts and topics which now I need to learn to improve my programming skills.

Searching for study material was when I found CS50: Introduction to Computer Science, which seemed a good starting point to review concepts from scratch. The course is intended for people with or without prior programming knowledge and covers beginners to more advanced topics.

The intent is to teach students not how to use a programming language, but how to think algorithmically and solve problems efficiently, no matter the tool. The course is divided into weeks, each having a lecture, related materials, labs, and a set of problems to be solved.

Week 0

In this lecture the instructor explains the basics of programming, like variables, conditionals, and loops, using Scratch, a software developed to teach programming, but what I want to highlight is what David Malan says about our career: computer science is fundamentally problem solving. Sounds silly, but many times we programmers start coding without having fully understood the problem, and without having a clear idea of its solution, the most important thing of all.

The instructor gives a very clear explanation of how computers and the binary system work, which was what I liked the most about the lecture.

Computers use the binary system as their unique “language” to store and process data. This system uses just 0 and 1 to represent numbers. But, why do computers use it? Since computers run on electricity, which can be turned on or off, it is possible to represent a bit by turning some switch on or off. And what is a bit may you be thinking? It's just a binary digit, each 0 and 1.

But computers don't use bits separately, they work with groups of 8 bits at a time, known as bytes, like 00000011 which represents the number 3. With 8 bits we can count from 0 to 255, that is the reason why this range is widely used in different contexts, like in RGB colors or IP addresses.

So, computers use the binary system to represent information, and the binary system represents numbers, what happens with letters and other characters?. The computer uses an ASCII table to map numbers to characters. The ASCII standard includes uppercase and lowercase letters, numbers, punctuation, and other special characters. For example, bytes 01001000, 01001001, and 00100001 represent the decimal numbers 72, 73, and 33, which map to the word HI!.

But computers also represent others characters not included in the ASCII standard, like emojis, for example. For those characters, they use another standard called Unicode, which uses not just a byte for each character like ASCII does, but 4 bytes for a character, for example, these bytes 11110000 10011111 10011000 10110111 represent the emoji 😷.

To represent colors, one of the most used systems is RGB, which uses 3 bytes (from 0 to 255), each one for red, green, and blue respectively. The combination of these three values gives us a variety of shades of colors.

Each color is a pixel, we can represent an image on the screen using millions of pixels, and with thousands or millions of images, we get a video. Yes, videos are just a sequence of images. Music can be represented with bits, too. MIDI is one such format that represents music with numbers for each note.

The important thing here is that what a byte means is given by the context. In Microsoft Word, the number 72 could represent the letter H, but in Photoshop maybe is a value for one of the RGB channels of a pixel.

Here comes in handy what programmers do in typed programming languages, defining the data type of the value stored in a variable, like a number, or a string.

Week 1

Since this lecture, the instructor teaches and uses the C programming language. This is the first time I develop in it, and what I noted is that both Python and JavaScript, the languages that I use the most, have taken some syntax and functionalities from C, which makes me feel a bit familiar with it.

David starts with a few words about code quality, which I found pretty good to understand the goals that every programmer must follow each time to write code. The quality can be evaluated based on 3 aspects:

correctness, or whether our code solves our problem correctly
design, or how well-written our code is, based on how efficient and readable it is
style, or how well-formatted our code is visually

Already deep into the world of C, it is important to know which are its data types. This is useful, not just because the concept of a data type is common to every programming language, but to understand later the memory of the computer works.

In C, these are the data types and its size in memory:

char → 1 byte (8 bits) → Range (from -128 to 127)
unsigned char → 1 byte (8 bits) → Range (from 0 to 255)
int → 4 bytes (32 bits) → Range (from -2^31 to 2^31 which means about -2 billion to 2 billion)
unsigned int → 4 bytes (32 bits) → Range (from 0 to about 4 billion)
long → 8 bytes (64 bits) → Big integers
float → 4 bytes → 32 bits of precision
double → 8 bytes → 64 bits of precision

It is important to know the range of each data type, because going beyond the allowed range, it will end in an overflow issue. For example, if we try to store a bigger number than 2 billion in an int variable, an Integer Overflow error will be triggered.

Limits in the size of data types also come with other kinds of problems like the floating-point imprecision: the inability for computers to represent all possible real numbers with a finite number of bits, like 32 bits for a float. So, our computer has to store the closest value it can, leading to imprecision.

The Y2038 is an integer overflow problem that is going to happen in the year 2038, when 32-bit computers are going to run out of bits to track time. Many years ago, some humans decided to use 32 bits to measure time with Unix time (or Unix epoch), which is the number of seconds since January 1st, 1970. But since a 32-bit integer can only count up to about two billion, in 2038 we’ll reach that limit.

The 32 bits of an integer representing 2147483647 (the maximum value for an int) look like this:

01111111111111111111111111111111

When we increase that by 1, the bits will actually look like:

10000000000000000000000000000000

But the first bit in an integer represents whether or not it’s a negative value, so the decimal value will be -2147483648, the lowest possible negative value of an int. So computers might actually think it’s sometime in 1901.

Fortunately, these days we have powerful computers, so we can start allocating more and more bits to store higher and higher values.

This is the code for the Problem set of Week 1.

At the moment the course is great, with lots of information and very clear explanations. It is always good to review the bases because you find data that you did not remember or did not even know about.

I hope you find interesting what I’m sharing about my learning path. If you’re taking CS50 also, left me your opinion about it.

See you soon! 😉

Thanks for reading. If you are interested in knowing more about me, you can give me a follow or contact me on Instagram, Twitter, or LinkedIn ❤.

My Learning Journey

Luciano Muñoz — Wed, 20 Apr 2022 02:10:56 +0000

Hi there!, my name is Luciano Muñoz and I'm a developer. First of all I want to thank you for taking a few minutes to read me ❤️.

My intention with this blog is to document the learning process in my journey as a developer. I'm not starting from scratch, I have been programming for several years. I did it as a hobby for a long time, and the last few years as a freelancer, in parallel to my current full time job as IT support.

Since a few years for this part I have set myself the goal of getting a job as a developer for a foreign company. After seeing other programmers work for companies in USA, Canada or Germany, and earn salaries in dollars, I felt that was able to do it also. Not just for the possibility of working doing something that I love like programming, but also for the peace of living with a dollarized salary in an economically unstable country like Argentina, with inflation rates that seems to never stop growing.

Long story short, in early 2020 I began to study English, an essential requirement to work abroad; and parallel to my full time job as IT support I continued to carry out freelance projects for local clients in order to continue improving negotiation skills, deadlines managing, etc. In 2021, while I was still taking English classes, the goal changed, the idea of working abroad was still alive but no longer as a freelancer, but as a developer employed in a company or startup. Freelancing was definitely not for me, it requires skills that I didn’t have and that I didn’t like it. I learned a lot in those years as a freelancer and I gained experience that otherwise would have been impossible, but the reality is that all I wanted to do was programming and solve problems.

With the new goal in mind, I began applying to open Backend and Fullstack positions. It was hard to take the decision and overcome my fears, but I did it finally. The responses from the recruiters were not too long in coming, and at the end of 2021 I had my first interviews with foreign companies. To my surprise, I passed the english interviews 👌, but failed the technical interviews 🙈. All this time I had been so focused on improving my English that I had neglected programming.

These first interviews helped me to realize that in my self-taught learning I was skipping and taking many concepts for granted, about which I couldn’t give an answer when interviewers asked me. Beyond that in practice one knows how to write a Class or develop an API, it’s mandatory to be able to explain in word each of these concepts.

So it was that in this 2022 I set myself the goal of learning all those concepts that I am missing, and documenting the process in this blog.

The first step was building a learning roadmap, for which I recommend widely the site roadmap.sh for this purpose. In particular, it helped me a lot the roadmaps for Backend and Python, the language that I use because I think it’s very powerful with a nice and clear syntax.

With the roadmap in hand, the next step was to search for study material, and in that process I found CS50, Harvard’s Introductory Computer Science course, which I thought was a good starting point for the variety of topics it includes, such as algorithms, data structures, memory management, C, Python, Javascript, SQL, among others. David J. Malan is a great instructor, didactic and very clear when teaching.

So, this will be my starting point.

If someone feels an interest in the course, it’s totally free in the edX platform.

See you soon!

Thanks for reading. If you are interested in knowing more about me you can give me a follow or contact me at Instagram, Twitter or LinkedIn.

Documentando Mi Aprendizaje

Luciano Muñoz — Wed, 20 Apr 2022 02:10:27 +0000

Hola persona que lee, mi nombre es Luciano Muñoz y soy programador. Antes que nada te quiero agradecer por tomarte unos minutos para leerme ❤️.

En este blog voy a intentar documentar todo el proceso de aprendizaje en mi carrera como programador. No estoy empezando de cero, programo desde hace ya varios años. Por mucho tiempo lo hice como hobby, y los últimos años como freelance, en paralelo a mi actual trabajo de 48 horas semanales como soporte de IT.

Desde hace tiempo me puse como objetivo conseguir trabajo como programador para una empresa del exterior. Luego de ver a otros programadores trabajar para empresas de USA, Canadá o Alemania, y cobrar salarios en dólares, sentí que yo también podía lograrlo. No solo por la posibilidad de dedicarme a algo que me apasiona como la programación, sino también por la tranquilidad que genera un salario dolarizado en un país económicamente inestable como Argentina, con índices de inflación que nunca paran de crecer.

Long story short, a principios de 2020 comencé a estudiar inglés, requisito indispensable para trabajar para el exterior; y de forma paralela a mi trabajo fijo como soporte de IT seguí realizando proyectos freelance para clientes locales con el fin de continuar mejorando las skills de negociación, deadlines, etc. En 2021, mientras continuaba con las clases de inglés, el objetivo fue mutando, la idea de trabajar para el exterior seguía en pie, pero ya no como freelance, sino como programador empleado en una empresa o startup. El freelance definitivamente no era para mí, requería de habilidades comerciales que no poseía y no me gustaban. Aprendí mucho en esos años trabajando bajo esa modalidad y gané experiencia que de otra forma hubiese sido imposible, pero la realidad es que yo solo quería programar y resolver problemas.

Con este nuevo objetivo en mente, comencé a postularme a posiciones de Backend y Fullstack. Me costó mucho tomar la decisión y superar mis miedos, pero las respuestas de los recruiters no tardaron en llegar, y finalizando el 2021 tuve mis primeras entrevistas con empresas del exterior. Para mi sorpresa, lograba pasar las entrevistas en inglés 👌, pero fallaba en las entrevistas técnicas 🙈. Todo este tiempo me había enfocado tanto en mejorar mi inglés que había descuidado la programación.

Estas primeras entrevistas me sirvieron para darme cuenta que en mi aprendizaje autodidacta fui salteando y dando por sabido muchos conceptos, sobre los que no pude dar respuesta cuando me los preguntaron. Más allá de que en la práctica uno sepa cómo escribir una clase o desarrollar una API, es indispensable poder explicar en palabras cada uno de esos temas.

Así fue que en este 2022 me puse como objetivo aprender todos esos conceptos que me faltan, y documentar el proceso en este blog.

Comencé por armar un roadmap o plan de estudio, para lo cual recomiendo ampliamente el sitio roadmap.sh. Particularmente me fueron de gran utilidad los roadmaps para Backend y Python, lenguaje que utilizo por elección ya que me parece muy potente y con una sintaxis super clara.

Con roadmap en mano, el próximo paso fue buscar material de estudio para cada tema, y allí fue que di con CS50, el curso de introducción a las ciencias de la computación de Harvard, el cual me pareció un muy buen punto de arranque por la variedad de de conceptos y temas que se ven, como ser algoritmos, estructuras de datos, manejo de memoria, C, Python, SQL, Javascript, entre otros. David J. Malan es un gran instructor, didáctico y muy claro al enseñar.

Así que este será mi punto de partida.

Si alguien esta interesado en tomar el curso, puede inscribirse totalmente gratis en el sitio edX.

Nos vemos pronto!

Gracias por leer. Si te interesa conocer más sobre mí podes seguirme o contactarme en Instagram, Twitter o LinkedIn.

Backup en la Nube con Rclone

Luciano Muñoz — Wed, 10 Jun 2020 01:31:55 +0000

Hace unos días el cloud server de un cliente literalmente desapareció, llevándose consigo la aplicación entera, incluida la base de datos. El estrés se fue por las nubes, pero fue todavía peor cuando me di cuenta que el último backup tenia más de 90 días 😱.

Siempre recomiendo a mis clientes la contratación de algún servicio de hosting que incluya backups automáticos, pero eso no siempre sucede. Si desarrollas proyectos freelance para clientes medianos o pequeños sabrás que los recursos muchas veces son limitados, que el servidor de producción sirve aplicación y base de datos, y que el único ambiente de staging es la PC que usas para desarrollar.

Solía pensar que la responsabilidad no recaía sobre mi si algo llegara a ocurrir, pero al tener esta experiencia me dí cuenta que no podía simplemente desentenderme del problema y decirle al cliente que toda su información se había perdido, tenia que poder ofrecerle algún tipo de solución. Por ello decidí armarme un flow de backup simple, rápido, y replicable fácilmente en otros servidores Linux para implementar en este tipo de proyectos.

Al final la historia con mi cliente terminó bien, ya que con ayuda del soporte técnico fue posible recuperar la información y volver a dejar el server operativo, pero el estrés del momento me llevo a pensar en esta solución casera de backup que te mostraré a continuación.

Backup de Información en la Nube

Las herramientas que vamos a usar son:

El comando zip de Linux
mysqldump, pg_dump o el comando necesario para hacer un backup de la base de datos
crontab
Rclone

Conceptualmente la idea es muy sencilla:

Crear un script bash que se encargue de comprimir los archivos y carpetas que queramos resguardar
Hacer una copia del archivo en la nube
Crear una tarea programada que ejecute todo esto de manera automática

Rclone es la herramienta principal que vamos a usar en nuestro backup, ya que nos permitirá hacer una copia del archivo en algún servicio en la nube. Soporta servicios gratuitos de almacenamiento de archivos como Dropbox y Google Drive, y servicios de pago como Amazon S3 y Google Cloud Storage, entre otros.

1 - Instalando y Configurando Rclone

En primer lugar vamos a instalar Rclone para tenerlo disponible cuando armemos el script bash. Te recomiendo instalarlo primero en tu equipo local, ya que para configurar los servicios de almacenamiento es necesario un navegador, y si solo tienes acceso a tu servidor por SSH te será difícil de finalizar la configuración. Luego podrás copiar la configuración de tu PC al server remoto fácilmente.

Instalar Rclone es muy sencillo, tanto como ejecutar el siguiente comando en la consola:

$ curl [https://rclone.org/install.sh](https://rclone.org/install.sh) | sudo bash

Si por algún motivo el software no se instala, en la documentación tenes los pasos para instalar desde el binario 😉.

Y si estás en Windows podes bajar el instalador desde la página de descargas.

Una vez instalado Rclone vamos a configurar el servicio de almacenamiento:

$ rclone config

Acá tienes las guías para configurar Dropbox y Google Drive, y podes consultar el resto de los servicios en este enlace.

Ahora que ya tenemos Rclone instalado y configurado, vamos a buscar donde podemos encontrar el archivo de configuración, que luego deberemos copiar en nuestro servidor:

$ rclone config file
Configuration file is stored at:
/Users/MyUser/.config/rclone/rclone.conf

Ahora solo resta repetir el proceso de instalación de Rclone en el servidor remoto. Una vez instalado, ejecutamos el comando rclone config file para conocer en que directorio debemos pegar el archivo de configuración de nuestra PC local, y subimos el archivo .conf a esa carpeta con algún cliente FTP o de la manera que creas conveniente.

2 - Creando el Script de Backup

En primer lugar vamos a crear un directorio donde guardaremos nuestro script, y más adelante el archivo de backup:

$ mkdir ~/backup/
$ touch backup.script

El contenido del archivo de script es muy subjetivo, ya que dependerá de los archivos y carpetas que desees resguardar.

# Backup de la base de datos
mysqldump -u my_user -pmy_password my_db > /home/my_user/backup/my_db.sql
# Me ubico en la carpeta backup y borro último archivo de backup
cd /home/my_user/backup
rm /home/my_user/backup/*.zip
# Comienzo a crear el nuevo archivo de backup, zipeando archivos y carpetas con el comando zip
zip -ur "backup-$(date +"%Y-%m-%d").zip" /etc/apache2/apache2.conf
zip -ur "backup-$(date +"%Y-%m-%d").zip" /etc/apache2/sites-availables
zip -ur "backup-$(date +"%Y-%m-%d").zip" /home/my_user/my_site/mediafiles
# Copio el archivo de backup al servicio de almacenamiento en la nube
rclone copy backup-*.zip remote:my_site/

El script anterior está basado en un script real que utilizo en un servidor de producción. Hago un backup de la base de datos MySQL, luego genero el archivo comprimido backup-aaaa-mm-dd.zip (donde aaaa-mm-dd corresponde a la fecha de creación del archivo) al cual agrego el archivo de configuración de apache y los virtual hosts, comprimo la carpeta mediafiles que contiene los archivos subidos por los usuarios, y por último le digo a rclone que copie el archivo de backup dentro de la carpeta my_site del servicio que hemos declarado como remote.

Rclone tiene muchas más funcionalidades incorporadas que podes ver en la documentación.

Por último le damos permisos de ejecución al script, y lo ejecutamos para probar su funcionamiento:

$ chmod +x [backup-script.sh](http://backup-script.sh/)
$ source backup.script

Si todo va bien solo resta configurar crontab para que la tarea de backup se ejecute automáticamente.

3 - Backup Automático

Para que el backup se ejecute de manera automática vamos a crear una tarea con crontab.

Por si no lo sabes, crontab es el comando que nos ofrece el entorno Linux para administrar las tareas programadas. Básicamente es un archivo de texto donde agregaremos una nueva linea indicando la programación de nuestra tarea.

La sintaxis de crontab tiene los siguientes parámetros, con los que podemos jugar para asignar la programación que deseamos:

m = minuto (0-60)
h = hora (0-23)
dom = día del mes (1-31)
mon = mes (1-12)
dow = día de la semana (1-7)
command = comando a ejecutar

Para agregar nuestra tarea debemos ejecutar crontab con el parámetro -e (edición):

$ crontab -e

A continuación te dejo algunos ejemplos para te vayas dando una idea de como programar las tareas en crontab:

m h dom mon dow command
# Cada viernes a las 4:00
0 4 * * 5 /home/my_user/backup/backup.script
# El día 10 de cada mes a las 15:30
30 15 10 * * /home/my_user/backup/backup.script
# Todos los días a las 20:00
0 20 * * * /home/my_user/backup/backup.script

Para finalizar guardamos el archivo y eso es todo! La tarea programada debería ejecutar el script automáticamente. Solo tendremos que controlar que los backups se estén guardando en la nube.

Con estos pocos pasos ya tenemos configurado un backup automático que se guardará en la nube, y que es sencillo de implementar y replicar en otro server.

Nuevamente gracias por haber llegado hasta acá y leído este post. Espero que te sirva y lo puedas aplicar.

Me gustaría conocer tus historias de terror y como las resolviste. Si tenes algo para contarme no dudes en dejarme un comment, o mandarme un twit a @luciano_dev.

Si te gusta mi contenido me ayudarías mucho difundiéndolo con tus amigos o en tu feed de Twitter, y si te gustaría que escriba sobre algo en particular dejame un comment. Espero tu feedback para ir mejorando con cada nuevo post ❤️.

Virtualenv y Pip para crear Entornos Virtuales de Python

Luciano Muñoz — Mon, 01 Jun 2020 13:51:34 +0000

Virtualenv es una herramienta para crear entornos de Python aislados, es decir ambientes completamente separados de la instalación global de Python, con sus propias dependencias y versiones.

Cuando comencé a programar aplicaciones web, Django era uno de los frameworks MVC de moda. Aún no existía React, el ecosistema Javascript se reducía a jQuery, Node.js era una novedad y Rails era la joyita. Era tanto el hype con Django que venia creciendo muy rápido y con un ciclo de release muy corto, por lo que salían versiones muy seguido con bugfixes, nuevas features y algunos breaking changes.

En mi primera aplicación había usado Django 1.4 pero al comenzar a programar la segunda aplicacion el framework ya se encontraba en la version 1.8, y al actualizar esta dependencia desate el caos. Aquella primera aplicación web se empezó a romper por todos lados. Era obvio, los breaking changes entre Django 1.4 y 1.8 hacían que nada funcionase como debía.

Buscando una solución fue que encontré Virtualenv. Con esta herramienta pude crear dos entornos virtuales completamente aislados donde instalar las dependencias de cada proyecto sin que interfieran entre si. Esto me permitía correr las dos aplicaciones en paralelo sin inconvenientes, y me daba la seguridad de que podía instalar y actualizar cualquier dependencia sin miedo a romper otra cosa mas que la misma aplicación en la que me encontraba trabajando.

Virtualenv ya se ha vuelto un estándar para la comunidad, tal es así que desde Python 3.3 se agrego al core el modulo venv, que nos permite crear entornos virtuales de forma nativa. Aunque aún no posee todas las virtudes de Virtualenv se sabe que es un modulo en continuo desarrollo. Peeeeero... por el momento Virtualenv sigue siendo la mejor opción.

¿Cómo instalo Virtualenv?

Virtualenv se instala, al igual que la mayoría de las dependencias de Python, con pip. Solo necesitamos correr este comando:

$ pip install virtualenv

¿Cómo se usa Virtualenv?

Virtualenv es muy sencillo de usar y no requiere configuración. Generalmente solo necesitaremos de 3 comandos que nos permitirán crear, activar y desactivar los entornos virtuales.

Hay distintas maneras de organización, algunos programadores prefieren mantener todos sus entornos virtuales dentro de un mismo directorio, pero yo personalmente prefiero crearlos dentro del directorio de cada proyecto. De esta manera puedo asignarle siempre el mismo nombre, y me resulta mucho mas sencillo para trabajar.

Para crear un entorno virtual primero debemos ubicarnos en el directorio elegido y luego ingresar el siguiente comando:

$ virtualenv env

Este comando nos creará dentro de la carpeta env un entorno virtual con el interprete de Python por defecto de nuestro sistema operativo.

Y si necesitamos crear un entorno con otra versión de Python?

Sencillo... usamos el flag --python e indicamos la ruta del interprete de Python que querramos:

$ virtualenv --python=/usr/local/bin/python3.8 env

El entorno virtual instalara pip y wheel por defecto, de manera que con solo activarlo ya podremos comenzar a instalar las dependencias que necesitamos.

Para activar el entorno virtual nos ubicamos en el directorio donde lo hemos creado y ejecutamos el siguiente comando:

# Mac y Linux
$ source env/bin/activate

# Windows
> env\Scripts\activate

El prompt de nuestra consola ahora deberá mostrarnos el nombre del entorno virtual, lo cual nos da la seguridad de que se activo correctamente:

(env) $

Por último, una vez que hayamos terminado de trabajar, o si necesitamos cambiar de entorno, lo desactivamos con el siguiente comando:

(env) $ deactivate

Para borrar un entorno virtual basta simplemente con eliminar su carpeta.

Con estos comandos ya tenemos practicamente todo lo que necesitamos para usar Virtualenv, pero en la ayuda podemos consultar las demás opciones disponibles:

$ virtualenv --help

Por último, nunca te olvides de ir guardando las dependencias de tus proyectos con el comando freeze de pip, ya que este nos permitirá replicar nuestro entorno virtual en otro equipo de manera sencilla y rápida:

# Generar un archivo con las dependencias
$ pip freeze > requirements.txt

# Instalar las dependencias desde el archivo generado
$ pip install -r requirements.txt

Conclusiones

Espero que esto te sirva si estas empezando a programar con Python, y recordá que la mejor manera de aprender es haciendo, y al hacer vamos a equivocarnos.

Tenemos que darle mucho amor a lo que aprendemos desde la necesidad, porque nos permite comprender el valor real que nos aporta para resolver nuestro problema, y puedo asegurarte que es un aprendizaje que vamos a incorporar para siempre.

Gracias por haber llegado hasta el final. Si este post te gustó dejame un comment o mandame un tweet (@luciano_dev) porque me interesa conocer tu opinión.

¡Hasta el próximo post! ❤️

Web Scraping con Python

Luciano Muñoz — Thu, 21 May 2020 15:21:15 +0000

Scraping es una técnica para leer y extraer datos de un sitio web cuando no existe un medio que nos permita obtener está información "por el buen camino", como una API Rest o RSS. El scraping está relacionado a lo que hoy conocemos como crawler, o simplemente bot.

Sin ir más lejos Google y los demás buscadores tienen bots que indexan la web constantemente almacenando toda la información que luego ves en los resultados de búsqueda. Pero no solo los buscadores utilizan scraping, también sitios como los comparadores de precios de productos, hoteles, vuelos, y muchos otros más.

Lo que quiero mostrarte en este post es que nosotros podemos programar nuestro propio bot, ya que se trata de una técnica que podemos aprender sin mayores problemas. No vas a salir programando el próximo Google, pero por ejemplo vas a poder programar un bot para hacer un seguimiento del precio de ese producto que tanto queres, o para consultar los titulares de los sitios de noticias que lees a diario. Y lo cool es que con un poco de ingenio podemos lograr cosas mucho más increíbles.

Si te interesa conocer esta técnica más a fondo te recomiendo el libro "Web Scraping with Python". Con solo unos capítulos vas a entender lo potente que es el scraping, y como implementarlo con Python 🐍.

Let's go!

¿Cómo funciona el scraping?

Existen distintas técnicas, pero lo normal es scrapear un sitio web a través del código HTML, indicándole a nuestro bot que tags y atributos debe buscar para encontrar la información que queremos.

Imaginemos que deseamos obtener los titulares de un sitio de noticias que tiene la siguiente estructura HTML:

<section class="layout-articles">
    <!-- Noticia 1 -->
    <article>
        <h1 class="title">
            <a href="/noticia-1" title="Noticia 1">
                Noticia 1
            </a>
        </h1>
        <img src="noticia-1.jpg">
    </article>
    <!-- Noticia 2 -->
    <article>
        <h1 class="title">
            <a href="/noticia-2" title="Noticia 2">
                Noticia 2
            </a>
        </h1>
        <img src="noticia-2.jpg">
    </article>
</section>

Nuestro software debería buscar la etiqueta section class="layout-articles" que actúa como un wrapper de las noticias, obtener todos los tags h1 class="title", y de allí extraer la etiqueta a que contiene el título y la URL de las noticias.

Esto es solo un sencillo ejemplo para que vayas entendiendo la idea, y que te servirá para comprender mejor lo que vamos a programar.

¿Qué vamos a programar?

Existe un sitio genial llamado Simple Desktops que contiene una colección super cool de wallpapers totalmente fancy, y nuestro bot se encargará de recorrer las distintas páginas de esta web y descargar automáticamente todos los wallpapers 👏👏👏.

Como ves, lo divertido del scraping es que el limite lo pone tu imaginación.

Pero primero analicemos la estructura del sitio y el código HTML, ya que esto nos permitirá comprender que pasos debe seguir nuestro bot para cumplir su objetivo:

La web contiene una paginación tipo /browse/, /browse/1/, /browse/2/, etc., donde se muestran los wallpapers.
Cada wallpaper es un div class="desktop" que dentro contiene una etiqueta img. El atributo src de esta etiqueta es lo que nos interesa ya que contiene la URL para descargar el wallpaper.
El sitio usa un generador de thumbnails que viene implícito en la URL de las imágenes, pero si eliminamos el texto que hace referencia al resize accedemos a la imagen original: Apple_Park.png~~.295x184_q100.png~~ 😎.
La URL hacia la próxima página la podemos obtener del tag a class="more".

Con la información anterior podemos ver que el algoritmo debe hacer lo siguiente:

Comenzará haciendo un request a la URL /browse/
Del código HTML debe obtener las URL de los wallpapers
Luego debe formatear las URL para quitar el resize
Procesar las descargas de las imágenes
Obtener la URL de la página siguiente y volver a comenzar

Genial, ahora que ya sabemos lo que tenemos que hacer, empecemos con la parte divertida... ¡a codear! 🎈

¿Como programar un bot en Python?

Estas son las librerías que vamos a usar:

os: para manejo de rutas de archivos y carpetas
re: para expresiones regulares
shutil: para operaciones con archivos
requests: para realizar peticiones HTTP
BeautifulSoup: para parsear el código HTML, es el corazón de nuestro bot ❤️

BeautifulSoup y requests son dos librerías que no vienen incluidas con Python, por lo que tendrás que instalarlas con pip:

$ pip install beautifulsoup4
$ pip install requests

Para hacer el código más legible y fácil de debugear iremos separando la lógica en funciones, cada una de las cuales cumplirá una tarea particular.

Bien, primero te recomiendo que crees una carpeta para este proyecto y dentro el archivo simpledesktop-bot.py, al cual comenzaremos importando las librerías:

import os
import re
import shutil
import requests
from requests.exceptions import HTTPError
from bs4 import BeautifulSoup

El punto de entrada a nuestra app será la función init(), que funciona como un constructor. Allí setearemos los datos iniciales, como la URL del sitio web, el path desde donde comenzara a correr el bot, y el directorio donde guardaremos los wallpapers. Por defecto se creará la carpeta wallpapers dentro del directorio de nuestro proyecto y allí haremos las descargas. Para ello primero chequeamos con os.path.exists si este directorio ya existe, y de no existir lo creamos con os.makedirs.

Por último llamamos a la función processPage() que iniciará el scraping.

def init():
    url = 'http://simpledesktops.com'
    first_path = '/browse/'
    download_directory = os.path.join(os.path.dirname(os.path.abspath(__file__)), 'wallpapers')

    if not os.path.exists(download_directory):
        os.makedirs(download_directory)

    processPage(url, first_path, download_directory)

processPage() es un wrapper que se encargará de realizar las llamadas a las demás funciones. Por parámetro recibirá la URL inicial y con cada ejecución se vuelve a llamar recursivamente recibiendo la nueva página a procesar, lo cual nos permite hacer un loop que finalizará al alcanzar la última página.

La primera función llamada es getPageContent(), que recibe por parámetros las variables url y path, con las cuales hace el request HTTP y devuelve un diccionario con estos datos:

images: es una lista con las URL de los wallpapers a descargar
next_page: contiene la URL de la siguiente página a procesar

La segunda función que ejecuta es downloadWallpaper() a la cual le pasaremos las URL de los wallpapers y se encargará de procesar las descargas.

Por último tenemos la recursión, verificamos si next_page tiene un valor asignado y volvemos a llamar a processPage() con el nuevo path.

def processPage(url, path, download_directory):
    print('\nPATH:', path)
    print('=========================')

    wallpapers = getPageContent(url + path)
    if wallpapers['images']:
        downloadWallpaper(wallpapers['images'], download_directory)
    else:
        print('This page does not contain any wallpaper')
    if wallpapers['next_page']:
        processPage(url, wallpapers['next_page'], download_directory)
    else:
        print('THIS IS THE END, BUDDY')

Como dije anteriormente getPageContent() es la primer función llamada por processPage(), y su objetivo es retornar las URL de los wallpapers y la URL de la página siguiente.

Primero definimos las variables image y next_page que guardarán los datos a retornar, y las inicializamos con valores por defecto.

Luego llamamos a la función requestPage() (para que el código sea más fácil de leer he abstraído el request HTTP a su propia función, que veremos más adelante) que nos retornará el código HTML listo para ser manipulado. Y aquí es donde veremos la magia de BeautifulSoup! Primero vamos usar el método find_all para obtener todos los wallpapers que, tal como vimos en el análisis de la estructura HTML, están representados por el tag div class="desktop", y los guardamos en la variable wallpapers. Luego iteramos estos elementos y usando el método find buscaremos la etiqueta img, de la cual obtendremos el atributo src que contiene la URL del wallpaper. Con este dato iremos completando nuestra lista images.

Por último buscamos el tag a class="more", extraemos su URL del atributo href y lo asignamos a la variable next_page que creamos al principio de la función.

Retornamos images y next_page en un diccionario.

def getPageContent(url):
    images = []
    next_page = None

    html = requestPage(url)
    if html is not None:
        # Search wallpapers URL
        wallpapers = html.find_all('div', {'class': 'desktop'})
        for wp in wallpapers:
            img = wp.find('img')
            images.append(img.attrs['src'])

        # Search for next page URL
        try:
            more_button = html.find('a', {'class':'more'})
            next_page = more_button.attrs['href']
        except:
            pass

    return {'images': images, 'next_page': next_page}

Anteriormente usamos la función requestPage(), que tal como dijimos, se encarga del request HTTP y de retornar el HTML ya parseado. Para el request usamos requests.get y guardamos el payload en la variable raw_html. Por último parseamos el HTML plano con BeautifulSoup y lo retornamos.

Con try/except nos aseguramos de interceptar los errores y mostrar sus respectivos mensajes de error.

def requestPage(url):
    try:
        raw_html = requests.get(url)
        try:
            html = BeautifulSoup(raw_html.text, features='html.parser')
            return html
        except:
            print('Error parsing HTML code')
            return None
    except HTTPError as e:
        print(e.reason)
        return None

La segunda función llamada por processPage() es downloadWallpaper(), que recibe la lista de URL y descarga los wallpapers.

La primer tarea de esta función es hacer una pequeña modificación a las URL, porque recordemos que el sitio web usa un generador de thumbnails que viene implícito en el nombre de la imagen, y sin esta modificación estaríamos descargando un wallpaper de 300x189 px. Quitando este resize vamos a poder descargar las imágenes en su tamaño original.
Veamos un ejemplo:

http://static.simpledesktops.com/uploads/desktops/2020/03/30/piano.jpg.300x189_q100.png

Pongamos la atención en el nombre del wallpaper, vemos que en primer lugar se incluye el nombre del archivo con su extensión original (piano.jpg) y luego el "código" del resize (300x189_q100.png). Lo que necesitamos es obtener la misma URL pero sin esta última parte, para lo cual vamos a usar una expresión regular.

Con la regex '^.+?(\.png|jpg)' buscamos la primer ocurrencia de .png o .jpg comenzando desde el inicio de la URL. Si hay match obtenemos todo ese string, con lo cual nos quedará la URL sin el resize, y si no hay match quiere decir que no encuentra la extensión de la imagen y por lo tanto no es una URL válida.

Siguiendo con el código, en la variable file_path generamos la ruta completa a la imagen y chequeamos si ya existe en nuestro disco para no volver a descargarla. Si la imagen no existe haremos lo siguiente:

Usamos request.get para obtener la imagen por streaming y guardamos la referencia a este objeto en la variable wp_file.
Con la función open abrimos el archivo local (que será creado en este momento, aunque se encontrará vacío) en modo binario y escritura, y lo referenciamos con el nombre de variable output_file.
Por último usamos shutil.copyfileobj para copiar el contenido de wp_file dentro de output_file

Con esto ya tendremos descargado el wallpaper en nuestro disco.

Los bloques with nos permitirán liberar automáticamente la memoria usada por Python para el request HTTP y la creación del archivo local, por lo cual podemos proceder a descargar el siguiente wallpaper.

def downloadWallpaper(wallpapers, directory):
    for url in wallpapers:
        match_url = re.match('^.+?(\.png|jpg)', url)
        if match_url:
            formated_url = match_url.group(0)
            filename = formated_url[formated_url.rfind('/')+1:]
            file_path = os.path.join(directory, filename)
            print(file_path)

            if not os.path.exists(file_path):
                with requests.get(formated_url, stream=True) as wp_file:
                    with open(file_path, 'wb') as output_file:
                        shutil.copyfileobj(wp_file.raw, output_file)
        else:
            print('Wallpaper URL is invalid')

Eso es todo, solo resta incluir la llamada a la función init() que da inicio a la ejecución del código:

init()

Para poner a correr nuestro bot abrimos una consola en el directorio del proyecto y ejecutamos el comando python3 simpledesktop-bot.py, y veremos algo como lo siguiente:

$ python3 simpledesktop-bot.py

PATH: /browse/
=========================
/Users/MyUser/simple-desktop-scraper/wallpapers/sphericalharmonics1.png
/Users/MyUser/simple-desktop-scraper/wallpapers/Dinosaur_eye_2.png
/Users/MyUser/simple-desktop-scraper/wallpapers/trippin.png
...

PATH: /browse/2/
=========================
/Users/MyUser/simple-desktop-scraper/wallpapers/Apple_Park.png
/Users/MyUser/simple-desktop-scraper/wallpapers/triangles.png
/Users/MyUser/simple-desktop-scraper/wallpapers/thanksgiving_twelvewalls.png
...

PATH: /browse/3/
=========================
/Users/MyUser/simple-desktop-scraper/wallpapers/minimalistic_rubik_cube_2880.png
/Users/MyUser/simple-desktop-scraper/wallpapers/Nesting_Dolls.png
/Users/MyUser/simple-desktop-scraper/wallpapers/flat_bamboo_wallpaper.png

El código completo lo podes encontrar en el repositorio de GitHub y si te gustó dejale una estrellita al repo 😉
SimpleDesktop-Bot

Conclusiones

En primer lugar gracias por haber llegado hasta acá, significa mucho para mí que hayas leído este post.

Espero que hayas podido aprender algo nuevo ya que ese es mi objetivo, y si es así entonces dejame un comment o mandame un tweet porque me gustaría saberlo.

También me gustaría conocer sus propios bot, así que si te animas a desarrollar uno contame porque me interesa saber. Y si crees que podes aportar a nuestro Simple Desktop bot (porque también es tuyo) entonces animate a mandarme un pull request. No hay cosa que me gustaría más.

Comparti tu Localhost de forma segura con Ngrok y Localtunnel

Luciano Muñoz — Sun, 10 May 2020 02:45:50 +0000

ngrok y Localtunnel son dos aplicaciones que nos permiten exponer en internet una conexión HTTPS hacia nuestro localhost, de manera que podemos compartir, por ejemplo, nuestro servidor web local; incluso aunque nos encontremos detrás de un firewall. No solo podemos permitir el acceso a nuestro servidor web, sino también a cualquier puerto TCP local donde estemos corriendo algún servicio, como un servidor SSH, FTP, o una base de datos.

¿Qué logramos con esto?

Podemos hacer testing de nuestro sitio web desde el móvil, tablet o cualquier otro dispositivo de manera rápida y sencilla.
Otros co-workers pueden acceder a nuestro servidor local de manera segura para revisar un proyecto en conjunto.
Podemos hacer una demo con nuestros clientes en cuestión de segundos y sin necesidad de deployar a un servidor, configurar DNS, ni nada de eso. Es magia!

En este post veremos las ventajas y desventajas de cada app para que puedan decidir si optan por una u otra, o las dos 😉.

ngrok

Ngrok tiene la particularidad de que con la cuenta gratuita nos ofrece tunnels sin timeout, es decir que pueden estar corriendo indefinidamente, por ello les recomiendo que se creen una cuenta ya que es muy sencillo y lo pueden hacer logueandose con Google o GitHub si lo desean.

Lo primero que debemos hacer es descargar ngrok para nuestro sistema operativo.
Una vez descargado descomprimimos el ejecutable y lo copiamos en una carpeta de nuestra preferencia (yo lo tengo en la raíz del directorio donde guardo todos mis proyectos 🎈).
Luego iniciamos sesión en nuestra cuenta de ngrok y copiamos el Authtoken.
Abrimos una consola en la carpeta donde copiamos la app y la vinculamos a nuestra cuenta con el comando:
```
$ ngrok authtoken <YOUR_AUTH_TOKEN>
```
Ya podemos abrir una conexión a nuestro server:
```
$ ngrok http 80
```

Lo que hicimos con el último comando es abrir un túnel HTTP en el puerto 80. ngrok nos va a mostrar algo como lo siguiente:

ngrok by @inconshreveable

Session Status            online
Account                   Luciano Muñoz (Plan: Free)
Version                   2.3.35
Region                    United States (us)
Web Interface             http://127.0.0.1:4040
Forwarding                http://b9ccb437.ngrok.io -> localhost:80
Forwarding                https://b9ccb437.ngrok.io -> localhost:80

Como podemos ver ngrok nos asigna una URL random https://b9ccb437.ngrok.io y cualquiera que la tenga va a poder comunicarse con nuestro servidor local. Hace la prueba ingresando desde tu smartphone!

Otra de las cosas cool de ngrok es el inspector web donde podemos visualizar en tiempo real todo el trafico que esta pasando por nuestro tunnel, con detalle de los request, responses, headers, payload, etc. Para ingresar al inspector solo debemos acceder a la URL http://127.0.0.1:4040 desde el navegador.

El punto en contra es que las URL persistentes son una característica de la versión paga, de modo que con nuestra cuenta free al reiniciar el tunnel nos va a proporcionar una URL distinta. Pero, siempre tenes la opción de pagar por la app para contribuir con su desarrollo 😉 y obtener todas las funcionalidades.

Por ultimo, como dije al principio del post, es posible crear un tunnel hacia cualquier puerto TCP, por ejemplo ngrok tcp 22. Pero esto te lo dejo para que lo investigues por tu cuenta 👍!

Localtunnel

Localtunnel esta escrito en javascript y se instala mediante NPM, el gestor de paquetes de Node.js, lo que implica que debemos asegurarnos de tener Node.js instalado previamente.

La instalación es mucho mas sencilla que en el caso de ngrok si ya contamos con los requerimientos de los que les hablé anteriormente. Abrimos una consola y tecleamos el siguiente comando para instalar Localtunnel de forma global en nuestro sistema:

$ npm install -g localtunnel

Ya podemos crear nuestro tunnel al puerto que deseamos:

$ lt --port 80

Luego de ejecutar el comando anterior vamos a recibir una respuesta como la siguiente:

your url is: <https://bxtwmwsppb.localtunnel.me>

Podemos ver que ya tenemos nuestro tunnel creado hacia el puerto 80 de nuestro localhost.

Cuando ejecutamos Localtunnel sin parámetros extra nos proporciona una URL random, de la misma forma que lo hace ngrok, pero si usamos el parámetro --subdomain podemos solicitar un un subdominio personalizado, el cual podremos volver a utilizar cada vez que sea necesario, siempre y cuando dicho subdominio no este siendo utilizado ya por otra persona. Esto nos da la posibilidad de poder compartir siempre la misma URL dado que la misma será persistente:

$ lt --port 80 --subdomain mylocalhost
your url is: <https://mylocalhost.localtunnel.me>

Localtunnel sin embargo no es tan estable como ngrok por lo que debemos monitorear la consola cada cierto tiempo para verificar que el túnel sigue activo.

Pros y Cons

ngrok

🔥 Es muy estable, puede estar corriendo por días sin problemas
🔥 Tiene un inspector web para monitorear todo el trafico que pasa a través del tunnel
👎 Las URL no son persistentes en la versión free

Localtunnel

🔥 Tiene URL persistentes, lo que nos permite poder compartir siempre la misma URL
👎 Es necesario monitorear la consola cada tanto para chequear que sigue activo porque no es del todo estable

Conclusiones

Mis conclusiones en base a las ventajas y desventajas de cada app es que si necesitamos tunnels robustos que puedan permanecer corriendo por horas, incluso días, la mejor alternativa es ngrok. Pero Localtunnel gana cuando se trata de hacer una demo con un cliente, ya que gracias a los subdominios podemos compartirle una URL del tipo proyecto.localtunnel.me, y queda más profesional por decirlo de alguna manera.

Pero como siempre digo, proba las dos apps para que puedas sacar tus propias conclusiones, y usa lo que se adapte mejor a vos y a tu trabajo.

Si conoces o usas otra app de este estilo que te parezca una buena alternativa, dejala en los comentarios o escribime por mis redes sociales. Me interesa conocer que herramientas usan día a día ❤️.