Forem: Marisa You

Should you join a coding bootcamp?

Marisa You — Sat, 30 Jan 2021 00:45:25 +0000

If you've never been totally in love with your job and have thought about changing your career and becoming a programmer, you've probably come across coding bootcamps while doing your research. A bootcamp seem like a great option for someone in your position -- you get handed a curriculum of things that you need to learn, it's much less expensive than grad school, and the top bootcamps all boast extremely high employment rates after graduation. There's no better time than now, amidst a pandemic (especially if you've lost your job due to it), to change your career and turn your life around. So should you enroll in a bootcamp?

The short answer is that it depends. It depends on how much time and effort you can put into it and what you want out of it.

I graduated from my bootcamp recently, and these are my thought about it. For some background on me, I don't have a degree in computer science, but I do have a degree in another engineering field. I also studied programming on my own for a while before I decided to join a bootcamp and get some more formal training on it. As a disclaimer, some other bootcamp grads might have had very different experiences from me.

Can you really do it with no experience?

You can. In fact, I'd say 75% of my cohort had absolutely no experience with coding before coming into the bootcamp, and most of them graduated with me. However, I'd highly encourage you to dabble with it for a good while before handing your money over to a bootcamp for several reasons:

A career change is a big deal

And you want to make sure that it's right for you. Bootcamps are less expensive and less of a time commitment than, say, a master's degree, but they're still a lot of money. If you didn't like your last job, or even if you did, what guarantee is there that you'll like coding? I'd recommend learning on your own for at least a few months before you join a bootcamp, because you probably want to make sure you like coding before you commit yourself to it.

For the bootcamp I attended, there was about 80-100 hours of pre-work before classes started, but in my opinion, this is not nearly enough for you to gauge whether you'll like coding every day for 5 days a week for the next few decades.

You won't feel (as) behind during the program

In the first month of my program, quite a few of my cohort-mates stated that they had cried several times each week because they felt so lost. A few even said by the end of the first week that they felt like quitting. Almost all of these people made it to the end, which is very commendable, and you can too. But it would be better to save yourself some of the stress of falling behind, because there will be plenty of other things for you to stress about.

You'll be able to go beyond the curriculum

If you're not struggling with keeping up with the curriculum, then you'll have the capacity to learn things outside of that. The reality is that there is so much to learn in this field that you can never really stop learning, so you don't have to limit yourself to just learning things taught in the bootcamp's curriculum.

What is the day-to-day life of a bootcamp student like?

I've only ever attended one bootcamp, so I can't speak for all bootcamps. For my bootcamp, there were 5 "phases" in my program, each one about 3 weeks long. For the first four phases, in the middle of each phase, there was a code challenge (aka coding test), which you had to pass to move onto the next phase. At the end of the phase, there was a phase project. The entire last phase, however, was dedicated to a single capstone project.

Schedule

I was on Zoom at 9 am sharp every day Monday through Friday. Most days followed a similar schedule. We'd start with stand-up, where we gathered together and talked about what we were going to do for that day. We'd work on labs (basically small assignments) individually for part of most of the day, but most days, there was also a pair programming lab. Once or twice a day, there would also be a 1-2 hour lecture with the instructor. At 5:30 pm, we'd begin stand-down, where we each reviewed how our day went and got to know each other better. A lot of the day was very flexible, and we'd all work individually or in small groups in separate breakout rooms for the majority of the time. This meant that most of what you did in a day was entirely up to you.

Exceptions to this schedule were during project weeks. The whole day would be dedicated to working on your project.

It's school, but it's not really like school

In addition to not having a rigid schedule, you don't get graded on anything you do (other than the code challenge, which you only have to pass). You don't have to do all of the labs if you don't feel like they'll benefit you. In fact, no one's even going to force you to do any of them, if you don't want to. This means that how much you get out of a bootcamp is entirely up to you.

You'll have an instructor to teach you the topics in the curriculum, but you shouldn't depend on your instructor to teach you everything. It's very possible that you'll get an instructor whose teaching style isn't suitable for you, but learning on your own is something that you'll have to do eventually anyway.

Outside of the classroom (aka Zoom)

If it's not really like school, is there homework? How many extra hours do you need to put in outside of class? The answer is that there is homework if you choose to give yourself homework, and you'll put in as many extra hours as you would like to. I personally spent a few hours every night either working on more labs from class or learning other things on my own, and I hardly ever slept before 1 am. There were also very few weekends where I took breaks. In addition to the projects I did for the program, I also wrote little mini projects on my own (some of which are in my other blog posts). However, you absolutely can get by without doing any of that. Again, it's entirely up to you.

Making friends

Making friends during my bootcamp was a very unexpected part of it for me. Especially because classes are all entirely online now, I didn't really give this much though before I started my bootcamp. However, because you see the same people five days a week for four months straight, and you're all more or less struggling through the same things, it's kind of a bonding experience. I was very lucky to have had very kind and genuine cohort-mates, and I'll definitely be keeping in touch with some of them for a very long time.

Will a bootcamp really help me get a job?

So the running theme is that it depends on you. A bootcamp can help you in the process of getting a job if you're eager to learn and put in the work, but it won't get the job for you. Most bootcamps have career services. At my bootcamp, each student gets a career coach to help with the job searching process, but career service always emphasizes that the career coach is just there to guide you and you're the one in the driving seat.

Bootcamps usually have high graduate employment rates, but employment can mean a lot of different things. To be realistic, you won't get a 6-figure paying job right out of a bootcamp. You've just spent 4 months, give or take, working really hard and learning new things every day, but truthfully, you still know next to nothing about coding. A lot of people do get employed within a few months after graduating from a bootcamp, but a lot of the time they get hired as interns or apprentices. And what they'll be doing in their job is most likely not what they've learned at bootcamp.

A bootcamp is a good place to learn how to learn. It is not a place that will teach you everything you need to know to become a programmer.

Advice and takeaways

Be comfortable with being uncomfortable

That's the only way to grow and learn. At the beginning of this experience, the thought of not know a lot of things really scared me. Now, the thought is still daunting, but instead of thinking, "I'll never be able to learn all of this," I think of it from a perspective of, "There's still so much interesting stuff out there for me to learn."

Be eager to learn

This one might be kind of obvious. But if you really find yourself enjoying coding, you won't groan so much at the thought of having to stay up later to work on a project or to learn more about something. Learning is hard, but it should also be exciting. Like I mentioned earlier, this is a field where you have to constantly learn for the rest of your career if you want to be good at it, so if you don't find yourself eager to learn more about computer science, this really might not be the right career for you.

Don't compare yourself to other people in your cohort

Everyone enters the bootcamp with different background. Some people will have a head start because they've already coded a bit beforehand (again, I think you should do this if at all possible), and some people will find everything entirely new. What you should compare yourself to is your past self. If you feel like you've done your personal best and have learned new things every day, then you're on the right track.

This sums up most of what I have to say. These are my honest thoughts about my bootcamp experience, both the good and the bad. If you have any questions, feel free to leave a comment and I'll try to get back to you!

Make a facial recognition program using Azure's Face client library

Marisa You — Fri, 22 Jan 2021 20:49:47 +0000

In the past few years, we've seen applications of facial recognition technology being integrated into our daily lives. The first practical application of facial recognition that I can think of is identity verification. For example, for iPhone owners (of iPhone X and more recent versions), gone are the days of entering passcodes, mis-typing them, and re-typing them. Now, iPhone users can simply pick up their phones and look at them to unlock their screens.

Other devices are starting to use facial recognition for identification as well. Microsoft Surface users can also simply sit in front of their cameras to access their contents. Aside from ID verification, facial recognition is also used for a few other cool (but arguably less useful) applications, such as Facebook identifying people in photos and suggesting who to tag.

Since facial recognition technology is being used more and more for useful applications and research is continuously being done to improve the technology, I thought it would be fun to play around with it a bit and determine which celebrity I look the most similar to using the Face client library from Azure Cognitive Services to build a simple facial recognition app.

Make an account with Azure

You will need to sign up for an Azure subscription to access the Face client library. Note that the first 12 months are free, but after that, you will have to pay for any services that you use. Of course, you can cancel your subscription at any time. Also note that, if you use the free version, Azure will limit the frequency of requests you send to it, so you'll need to add a lot of sleep time into your scripts.

Once you have an account, log in and create a Face resource. After you've created your resource, click on "Go to resource," where you will see a key and an endpoint, both of which you will need to use later.

The Face documentation does a much better job at detailing this process than I do, so feel free to use that as well.

Installation

For this project, I'm using Python. To install the Face client library:

pip install --upgrade azure-cognitiveservices-vision-face

Alternatively, you can use Go or C# as well.

Data Collection

The first step to building anything involving AI is data collection, and for this project, the data is in the form of images. Since I'm an Asian female, I thought that it would make the most sense to use images of Asian female celebrities. I used Playwright to scrape for photos of 41 female Kpop idols. For each image, I grabbed the source and wrote it to a text file along with a label to identify which celebrity the image belonged to in the format of:

[idol_name],[image_src]

For example, here's a line from the text file containing the data:

blackpink lisa,https://th.bing.com/th/id/OIP.ijTvepbl0DsSHIHwRTszqgHaLH?w=200&h=300&c=7&o=5&pid=1.7

To get started with using Playwright, you can reference my most recent blog post! Of course, you can use any other method that you prefer to collect your images as well.

Data Processing (generating faceId)

The Face client library generates a unique faceId for every face with a shell command in this format:

curl -H "Ocp-Apim-Subscription-Key: FACE_SUBSCRIPTION_KEY" "FACE_ENDPOINT/face/v1.0/detect?detectionModel=detection_02&returnFaceId=true&returnFaceLandmarks=false" -H "Content-Type: application/json" --data-ascii "{\"url\":\"IMG_SOURCE\"}"

Replace the FACE_SUBSCRIPTION_KEY and FACE_ENDPOINT placeholders with the key and endpoint from your resource in the shell command above. Also, replace IMG_SOURCE with an image source.

This, however, will only generate the faceId(s) for one image. You can write a script to generate the shell commands for every image and save the outputs to a shell script. This is the script that I used:

same = "curl -H \"FACE_SUBSCRIPTION_KEY\" \"FACE_ENDPOINT/face/v1.0/detect?detectionModel=detection_02&returnFaceId=true&returnFaceLandmarks=false\" -H \"Content-Type: application/json\" --data-ascii "

output = open('curl_script.sh', 'w+')
everyone = {}
for line in open('result.txt').readlines():
    person = line.split(',')[0]
    url = line.split(',')[1].replace('\n', '')

    output.write('printf "' + person + ',"\n')
    output.write(same)
    output.write('"{\\"url\\":\\"' + url + '\\"}" \n')
    output.write('printf "\\n"\n')
    output.write('sleep 5\n')

And the resulting shell script looks something like this (repeated for every image):

printf "blackpink lisa,"
curl -H \"FACE_SUBSCRIPTION_KEY\" \"FACE_ENDPOINT/face/v1.0/detect?detectionModel=detection_02&returnFaceId=true&returnFaceLandmarks=false\" -H \"Content-Type: application/json\" --data-ascii  "{\"url\":\"https://th.bing.com/th/id/OIP.ijTvepbl0DsSHIHwRTszqgHaLH?w=200&h=300&c=7&o=5&pid=1.7\"}"
printf "\n"

Then run the shell script and save the output to a text file. Each line in the text file will look something like:

blackpink lisa,[{"faceId":"FACE_ID","faceRectangle":{"top":49,"left":87,"width":48,"height":62}}]

and the faceId will be in the place of FACE_ID

Data Processing (saving images locally)

Aside from generating faceIds, you'll also need to save the images locally. To do this, I wrote another python script and saved the results in a shell file.

output = open('wget.sh', 'w+')
tally = {}
idx = -1
for line in open('result.txt').readlines():
    person = line.split(',')[0]
    if person in tally:
        tally[person] += 1
    else:
        tally[person] = 1

    idx = tally[person]

    url = line.split(',')[1]
    output.write('wget -O ./images/' + person.replace(' ', '_') + str(idx) + '.jpg ' + url.replace('\n', '') + '\n')

The resulting shell file looks like (again, repeated for every image):

wget -O ./images/blackpink_lisa1.jpg https://th.bing.com/th/id/OIP.ijTvepbl0DsSHIHwRTszqgHaLH?w=200&h=300&c=7&o=5&pid=1.7
wget -O ./images/blackpink_lisa1.jpg https://th.bing.com/th/id/OIP.ijTvepbl0DsSHIHwRTszqgHaLH?w=200&h=300&c=7&o=5&pid=1.7

And then, of course, run the shell script.

Now, all the data is in the correct formats, and we can proceed to training the facial recognition algorithm.

Training

Training the data is fairly straightforward if you follow the steps in the Face client library documentation. However, you might have to wait a while for it to complete due to all the sleep time. I had about 1,000 images in my training data set and plenty of sleep time, so I ran my training script overnight.

To get started with training the data, make a new python script and import some libraries. These are all the libraries that the Face documentation recommends importing:

import asyncio
import io
import glob
import os
import sys
import time
import uuid
import requests
from urllib.parse import urlparse
from io import BytesIO
# To install this module, run:
# python -m pip install Pillow
from PIL import Image, ImageDraw
from azure.cognitiveservices.vision.face import FaceClient
from msrest.authentication import CognitiveServicesCredentials
from azure.cognitiveservices.vision.face.models import TrainingStatusType, Person

I didn't actually need all of them, but you might if you're trying to build a different type of program. After importing, the rest of the script is as follows. Remember that a lot of wait time must be interspersed in it for the free service to work.

# grab your key and endpoint and create a FaceClient
KEY = FACE_SUBSCRIPTION_KEY
ENDPOINT = FACE_ENDPOINT

face_client = FaceClient(ENDPOINT, CognitiveServicesCredentials(KEY))

# create a PersonGroup
# the person group id must be unique, so add in some error handling
PERSON_GROUP_ID = str(uuid.uuid4())
try:
    face_client.person_group.create(person_group_id=PERSON_GROUP_ID, name=PERSON_GROUP_ID)
except:
    face_client.person_group.delete(person_group_id=PERSON_GROUP_ID)
    face_client.person_group.create(person_group_id=PERSON_GROUP_ID, name=PERSON_GROUP_ID)


# get list of all people from the text file containing the processed data
people = []
last = ""
for line in open('./faces-all.txt').readlines(): 
    person_str = line.split(",")[0].replace(" ", "_")
    if person_str != last:
        people.append(person_str)
    last = person_str

# write output to a text file 
output_face_id = open('face-ids.txt', 'w+')

# make face group for each person
everyone = {}
images = {}
for person in people:
    print('Make face group for ' + person)
    everyone[person] = face_client.person_group_person.create(PERSON_GROUP_ID, person)
    output_face_id.write(person + ',' + str(everyone[person].person_id)+'\n')
    time.sleep(5)
    images[person] = [filename for filename in glob.glob('./images/*.jpg') if person in filename]

# add images for each person to corresponding face group
# add in error handling for photos where a face cannot be detected
for person in images:
    for person_image in images[person]:
        image = open(person_image, 'r+b')
        print('Add an image to face group for ' + person)
        try :
            face_client.person_group_person.add_face_from_stream(PERSON_GROUP_ID, everyone[person].person_id, image)
        except Exception as e: 
            print(e)
            continue
        time.sleep(10)

# train the person group
print()
print('Training the person group...')
face_client.person_group.train(PERSON_GROUP_ID)

while (True):
    training_status = face_client.person_group.get_training_status(PERSON_GROUP_ID)
    print("Training status: {}.".format(training_status.status))
    print()
    if (training_status.status is TrainingStatusType.succeeded):
        break
    elif (training_status.status is TrainingStatusType.failed):
        sys.exit('Training the person group has failed.')
    time.sleep(5)

print('PERSON_GROUP_ID: ' + PERSON_GROUP_ID)
print('DONE TRAINING!!')

This script will output the person_id for each person in a text file, which will be used later in the test script. Additionally, the PERSON_GROUP_ID will be printed. Copy this and save it somewhere.

Testing

Add a few images of some of the people in your training set to another another directory in your working directory. These images should be images that are not already in your training set. Ensure that each image you select only has one face in it. Your completed program will try to determine if the faces in these images match anyone in the training set.

Start the testing script by importing the same libraries used for the training script or just the ones you will need. Then proceed with the rest of it.

# again, start by getting your key and endpoint and creating a FaceClient
KEY = FACE_SUBSCRIPTION_KEY
ENDPOINT = FACE_ENDPOINT

face_client = FaceClient(ENDPOINT, CognitiveServicesCredentials(KEY))

# get the person group id from your training script and put it here
PERSON_GROUP_ID = PERSON_GROUP_ID

# get the test images 
test_image_array = glob.glob('./test_images/*.jpg')

This next part shows how I tested 1 image, but if you'd like to test more than 1, simply stick this whole section into a for loop.

image = open(test_image_array[0], 'r+b')

# detect face in test image
face_ids = []
faces = face_client.face.detect_with_stream(image, detection_model='detection_03')
for face in faces:
    face_ids.append(face.face_id)

# get results
print('Identifying faces in {}'.format(os.path.basename(image.name)))

highest_confidence = 0.0
best_match = ""

for line in open('./face-ids.txt').readlines():
    person = str(line.split(',')[0].replace('_', ' '))
    person_id = str(line.split(',')[1]).replace('\n','')

    try:
        result = face_client.face.verify_face_to_person(face_ids[0], person_id, PERSON_GROUP_ID)
        print(person + ': ' + str(result.confidence))
        if result.confidence > highest_confidence:
            highest_confidence = result.confidence
            best_match = person
        time.sleep(2)
    except:
        print('Cannot find person_id for ' + person)
        time.sleep(2)

print('The person in the photo looks the most similar to ' + best_match + ' with a confidence of ' + str(highest_confidence))

To break down the code above, it's first detecting a face in the test image(s) and generating a face_id for it. Then, that face is being comparing to the person_ids, generated from the training file, for every person in the training group. The line

result = face_client.face.verify_face_to_person(face_ids[0], person_id, PERSON_GROUP_ID)

outputs something that looks like

{'additional_properties': {}, 'is_identical': False, 'confidence': 0.37697}

for each person, which you can print if you want to see it. This gives you a prediction of whether the person in your test image is identical to each person from your training set as well as a confidence score.

After running the test script, if the results were as you expected, then you're good to go.

Final Results

Now, it's finally time to determine who you look the most similar to from your training set!. For this, simply replace the test image with an image of yourself and run the test script again. When I did this myself, this is what I got:

You look the most similar to red velvet irene with a confidence of 0.41322

Pretty cool, right?

Just to make it clear, in no way am I saying that I actually look like her! The confidence score is not that high, which makes that clear. The Face client library has simply determined that, out of the people in my training group, I look the most similar to her.

Final Note

I ran into a lot of errors while I was writing the scripts. Most of the time, it was because I didn't have enough sleep time. If you get any errors and you can't figure out what's wrong, try putting in more sleep time and see if it helps!

This was just a project that I did to play around a bit with facial recognition. It's obviously not that useful but I had fun making it, and I think that it can be easily tweaked for other purposes. If you have some time on your hands and you're interested in facial recognition, give it a try!

How To Get a PlayStation 5 When It's Always Out of Stock

Marisa You — Tue, 01 Dec 2020 20:59:23 +0000

In these times of Covid-19, gaming consoles are more sought-after than ever before. Since people are staying home most of the time, many have turned to video games as a way to pass the time, resulting in almost instantaneous sell-outs of the newest and hottest gaming consoles released. If you weren't among the lucky few who managed to get their hands on one of these when they were first released, your options are to 1) stalk the retailers' websites daily in the hopes that that item with just happen to be in stock when you're there or 2) buy it from a reseller on eBay for a 200% markup, neither of which sound remotely appealing.

However, if you're a clever software engineer, you'll realize that you can use your software engineering skills to your advantage in this situation. Why not use your knowledge to build a simple program that alerts you whenever the item you want is back in stock?

There exists a Node.js library called Playwright, which enables automation across most browsers. Setup is easy, and a simple web-scraping script can be built in under an hour.

As an example, let's write a program using Playwright that sends an alert when a PlayStation 5 console comes back in stock at Best Buy. A slight downside to this whole thing is that you'll have to write a custom scraper for each retailer that sells the particular item you're looking for, but really, how many of those retailers are there? Probably fewer than 10. And the process for writing these scripts is identical anyway.

Step 1: Installation and Getting Started

First, ensure that you have Node.js installed. To check whether you have Node.js installed, run node -v in the terminal. If you get back a version of Node.js (for example, something that looks like v14.13.1), then you're good to go. Otherwise, you can install it here. Once that's installed, run npm i -D playwright in your terminal.

Next, in your script, require Playwright and launch a browser (in this case, firefox) in an asynchronous function.

const { firefox } = require('playwright');
(async () => {
  const browser = await firefox.launch();
  // do something here...
})();

This function will be invoked as soon as the script is run.

The code written in this script will heavily rely on the async/await pattern. If you would like more information about that, this documentation on the topic explains it well.

Step 2: Go to Retailer's Site

Let's write a function tailored to searching for a PlayStation 5 Console at Best Buy and pass it the browser. We can then call it in the async function.

(async () => {
  const browser = await firefox.launch();
  searchBestBuyForPS5(browser);
})();

Inside the searchBestBuyForPS5 function, the first thing that needs to be done is to go to the site of the retailer

var searchBestBuyForPS5 = async (browser) => {
  const context = await browser.newContext();
  const page = await context.newPage();
  await page.goto('https://www.bestbuy.com');
  // more code to come...
}

Step 3: Search For Product

From here onwards, your function is going to look a bit different depending on the DOM of the site that you are working with. To search for a PlayStation 5 console on Best Buy's Site, let's first inspect the page and grab the element that contains the search input.

For Best Buy, the search input's id is 'gh-search-input'. We can use that id to specify where to type the search term.

  await page.type('#gh-search-input', 'playstation 5 console', {delay: 100});
  await sleep(3000);
  await page.press('.header-search-button', 'Enter');
  await sleep(1000);

(This still goes in the searchBestBuyForPS5 function, right after the code in Step 2.)

Let's break down the code in this code block. In the first line of this code block, the type function of Playwright takes in 2 or more parameters. The first parameter is the selector, which selects the element that we want. In this case, we specify that we want the element with the id of 'gh-search-input'. The second parameter is the text, or the search term. In this case, that's 'playstation 5 console'. (Before moving on, it would be a good idea to actually type in your search term on the retailer's site and ensure that the search results give you the product that you're looking for.) For the third parameter, I have here an optional delay parameter. All this does is delay the typing of each letter in the search bar by 100 ms to better imitate a human. If you don't do this, the site could get suspicious that you're using a bot, which.. you technically are.

The second line in the code block above allows time for the program to type in the full search term before moving on. The sleep helper function called in that line looks like this:

const sleep = (milliseconds) => {
  return new Promise(resolve => setTimeout(resolve, milliseconds))
}

The third line selects the search bar's submit button with a class name of 'header-search-button' and presses enter. After that, it sleeps for another second for the same anti-bot-detection reasons described above.

Once these lines of code execute, we should have access to a page that displays the search results:

Step 4: Identify the Target Item(s)

Or, more specifically, grab the innerHTML of the target item.

From this search results page, it seems that the items that we want are li elements with a class name of 'sku-item', so we can identify it using that information. Before we can find it, however, we have to be sure that those DOM elements have fully rendered.

  await page.innerHTML('li.sku-item'); // wait for elements to render
  const results = await page.$$('li.sku-item');
  for (let i = 0; i < results.length; i++) {
    // get name of item
    const skuHeader = await results[i].$('h4.sku-header'); 
    const html = await skuHeader.innerHTML();

    // check whether item's name contains "playstation 5" and "console"
    if (html.toLowerCase().includes('playstation 5') && html.toLowerCase().includes('console')) {
      // check in-stock status...
    }
  }

(Note: .$ and .$$ are both query selectors. The difference is that .$ returns null if it doesn't find anything that matches while .$$ returns and empty array.)

Step 5: Check Whether Item is In Stock

Inside the conditional in the code block above, we can check whether an item is in stock. First, we must select the element that gives us information about the item's in-stock status. For this particular page, the "Sold Out" button is the same as the "Add to Cart" button, just disabled. Therefore, it still has a class name of 'add-to-cart-button', so we can use that to query for the button.

      const button = await results[i].$('button.add-to-cart-button')
      const buttonText = await button.innerText()
      if (buttonText !== "Sold Out") {
        // alert user!
      }

Step 6: Alert User That Item is Back In Stock!

At this point, if our program has determined that an item is back in stock, it must alert us so that we can grab it before it sells out again. One way to do this is to send a text alert using Twilio. To do this, you do need to make an account with them and purchase a number that you'll use to send these alerts from.

Complete Code

If you would like to see all the code in one place, here it is:

// require playwright and launch browser
const { firefox } = require('playwright');
(async () => {
  const browser = await firefox.launch({ headless: false });
  searchBestBuyForPS5(browser);
})();

// helper function for sleeping
const sleep = (milliseconds) => {
  return new Promise(resolve => setTimeout(resolve, milliseconds))
}

// search whether PS5 is in stock at Best Buy
var searchBestBuyForPS5 = async (browser) => {
  // go to Best Buy's site
  const context = await browser.newContext();
  const page = await context.newPage();
  await page.goto('https://www.bestbuy.com');

  // enter search term "playstation 5 console"
  await page.type('#gh-search-input', 'playstation 5 console', {delay: 100});
  await sleep(3000);
  await page.press('.header-search-button', 'Enter');
  await sleep(1000);

  // wait for result products to render and put them in a results array
  await page.innerHTML('li.sku-item');
  const results = await page.$$('li.sku-item');

  // iterate through results array
  for (let i = 0; i < results.length; i++) {
    // get product's name
    const skuHeader = await results[i].$('h4.sku-header');
    const html = await skuHeader.innerHTML();

    // check whether product's name contains "playstation 5" and "console"
    if (html.toLowerCase().includes('playstation 5') && html.toLowerCase().includes('console')) {
      // get Sold Out/Add to Cart button
      const button = await results[i].$('button.add-to-cart-button');
      const buttonText = await button.innerText();

      // if the product is not sold out, alert the user
      if (buttonText !== "Sold Out") {
        console.log("Available!");
        // alert the user!!!
      }
    }
  }
};

And there you have it! A simple step-by-step process for writing a program that will allow you to know when an item you want is back in stock. Although the program shown here is specifically for searching for PlayStation 5 consoles at Best Buy, it can easily be altered for other purposes. To search for a different item, simply replace the search term. Searching for an item at a different retailer is slightly more complicated because the program accesses specific elements in the DOM of that page, but the process for writing the program is the same.

These steps can also be used for other purposes. For example, a similar process can be used to alert you when an item goes on sale. Simply alter the code so that you get an alert when the price changes instead of when the "Sold Out" button changes to "Add to Cart."

Lastly, it's worth noting that this script needs to be called consistently and frequently to be effective. For example, if this script were only run once a week, that would be no better than you checking the retailers' sites manually. To do this, you can use a job scheduler, such as cron, to invoke this script every few minutes. Here is an article on how to use cron. Good luck and happy shopping!

Adding is hard (I mean it)

Marisa You — Mon, 09 Nov 2020 07:06:22 +0000

In my last post, I analyzed the difference in runtime between an O(N) algorithm and an O(log N) algorithm for finding the nth number in the Fibonacci Sequence. When I plotted the runtime of both algorithms against a range of values of n, I ended up with the following graph:

The red points on this graph resulted from the O(N) algorithm, and the blue points resulted from the O(log N) algorithm. As expected, the O(N) algorithm was significantly slower than the O(log N) algorithm, especially as the value of n got larger.

However, the shape of the O(N) graph was unexpected. As can be seen on the graph, the O(N) curve is not exactly linear and actually appears to be closer to exponential, so I decided to investigate this to try to come up with an explanation for it.

One of the first things I noticed was that the value of the Fibonacci numbers got really big really quickly.

puts simple_fib(10)
# => 55

puts simple_fib(100)
# => 354224848179261915075

puts simple_fib(1000)
# => 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

Since my graph goes up to n = 220,000 on the x-axis, most of the outputs from simple_fib had to have been pretty large.

This leads me into a discussion of how numbers are represented in Ruby. Many personal machines these days are 64-bit. This means that a general-purpose register in the CPU has a maximum of 64 bits, and the largest number that could theoretically be stored in one of these registers is 2⁶⁴ - 1, or 18,446,744,073,709,551,615, since every single bit being a 1 would add up to 2⁰ + 2¹ + 2² + ... + 2⁶³.

In actuality, the largest number that can be stored in a CPU register is often smaller in many language runtimes because they need to use some bits to store metadata, which is the case when representing numbers in Ruby.

Ruby actually has two types of integers. Prior to the release of Ruby 2.4 in 2016, numbers were classified as either FixNum or BigNum, but later versions of Ruby represent both FixNum and BigNum numbers with the Integer class. FixNum numbers are those that can be represented with 64 bits while BigNum numbers require more than 64 bits.

In Ruby, the largest positive integer that can be represented using a single register, and therefore the largest FixNum, is 2⁶² - 1, or 4,611,686,018,427,387,903 (which is much smaller than the 1000th Fibonacci number, as shown above). The 63rd bit is reserved for the sign flag, with 0 indicating a positive number and 1 indicating a negative number. The 0th bit is reserved for the FixNum flag. A FixNum flag of 1 indicates a FixNum while a FixNum flag of 0 indicates a BigNum.

While the way that a FixNum is stored in a register is fairly straightforward (since the integer backing it fits in a single register), the way that a BigNum is stored is slightly more complicated. Ruby stores a BigNum in 32-bit chunks in an array, with the first 32 bits storing the 32 least-significant bits, the second 32 bits storing the 32 second-least-significant bits, and so on. (This article explains this in much greater detail.)

So what does this mean in terms of performance? If you haven't read my last post (or if you need a refresher), this was my simple_fib algorithm:

def simple_fib(n)
    if n == 0
        return 0
    end
    x = 0
    y = 1
    i = 1 
    while i < n
        temp = x + y
        x = y
        y = temp
        i += 1
    end
    return y
end

Essentially, each number is found by adding the previous 2 numbers in the Fibonacci sequence. When n is small and the sum of 2 numbers is a FixNum, which fits within 1 register, Ruby simply has to add the value in the second register to the value in the first register. However, when n is larger and the sum of 2 numbers is larger than the largest FixNum, Ruby has more operations to do.

It might be helpful to think of the addition of FixNums vs. the addition of BigNums analogously to single-digit additions vs. multi-digit additions. When adding single-digit numbers that result in a single-digit sum, the addition is straightforward, but when the sum is multi-digit, the addition process could require a carry and become more complicated:

For the single-digit addition, only one addition operation (4 + 5) had to be done. For the multi-digit addition, the sum of the least significant digits required 1 addition operation (8 + 2), but because that sum resulted in a carry-over, the next summation required 2 addition operations (4 + 5 + 1). In total, the single-digit summation required only 1 addition operation, but the two-digit addition required 3! Similarly, when Ruby sums FixNum integers (and the sum also fits in one 64-bit register), only one add assembly instruction is needed. But when adding BigNum integers, Ruby must keep track of any digits that carry over from one 32-bit chunk to the next, and if there are any carries, extra addition operations must be performed.

Therefore, it's easy to imagine that, as the numbers being added become larger, the number of operations that must be performed to add them and store the sum would also increase. The amount of time that Ruby takes to do these operations would increase for each addition as well. In fact, the function that ends up performing the "addition" operation with BigNums in the Ruby VM is about 45 lines long, as seen here. These extra operations cause the amount of time that it takes to add BigNums to increase exponentially because the number of digits of the BigNums being added increases exponentially with respect to n, which is consistent with the time vs. n graph for simple_fib.

The takeaway from this study is that coming up with efficient algorithms is an important part of writing performant applications, but it is certainly not the only factor. After all, algorithms are mathematical abstractions of problems that need to eventually run on the physical hardware. As an engineer, knowing how the actual algorithm executes on the hardware is just as important as being able to come up with efficient algorithms to solve problems! And while high-level programming languages such as Ruby abstracts these implementation details away from us so that we don't have to think about them all the time, we should not be afraid to dive into the details when we need to.

NOTE This study was done on my new MacBook Pro 2020, which uses an i7 processor (64-bit Intel CPU). On a platform that uses different processors (especially ones with different register sizes, like the ARMv7 processors in Raspberry Pi 2 or 3), things may look different :-) Who knew things could get this complicated for adding numbers?!

The Importance of Algorithm Efficiency: Case Study of the Fibonacci Sequence

Marisa You — Thu, 22 Oct 2020 07:46:52 +0000

Why is algorithm efficiency important, and as a software engineer, should you care about it? The short (and probably obvious) answer is yes. But let's take a deeper look at how much of a difference an efficient algorithm can make by doing a case study with the Fibonacci Sequence.

If you've never heard of the Fibonacci Sequence, this is it:

0, 1, 1, 2, 3, 5, 8, 13, 21...

Essentially, it's a sequence of numbers where the nth number can be found by summing the (n-1)th number and the (n-2)th number. In simpler words, each number can be found by adding the two numbers that come before it.

Let's take a look at a simple iterative method for finding the nth number in the Fibonacci Sequence. Since we're software engineers, let's define the leading element as the 0^th element.

def simple_fib(n)
    if n == 0
        return 0
    end
    x = 0
    y = 1
    idx = 1 
    while idx < n
        temp = x + y
        x = y
        y = temp
        idx += 1
    end
    return y
end

This simple and intuitive method for finding the nth element in the fibonacci sequence has a time complexity of O(N). If you're not familiar with big-O notation, this article is a great, beginner-friendly guide to it.

Now let's also take a look at a much less intuitive but much more efficient algorithm. We're going to be multiplying matrices, so if you need a quick refresher on how that works, this source might help. Consider the following matrix:

M = [[1, 1],
     [1, 0]]

If we compute M², we're going to get

[[2, 1],
 [1, 0]]

And M³ =

[[3, 2],
 [2, 1]]

Let's increase the exponent once more, just for good measure. Computing M⁴ will give us

[[5, 3]
 [3, 2]]

Do you see the pattern? Take a look at the first element in the first row of each result matrix. These are the elements of the Fibonacci Sequence, starting at index 2!

That's cool, but how does that help with making the Fibonacci algorithm more efficient? Since taking matrix M to the power of n seems to help with finding the (n+1)^th element of the Fibonacci Sequence, we should be able to use an efficient algorithm for exponentiation to make a more efficient Fibonacci.

So let's take a brief detour and talk a bit about an efficient algorithm for exponentiation. Consider a method that computes mⁿ.

def exp(m, n)
    prod = 1
    for i in 0...n
        prod *= m
    end
    return prod    
end

The method above computes mⁿ in O(N) time, because it iterates through all numbers from 0 to N-1 to multiply. This seems OK, but we can do better.

Consider this method instead:

def exp(m, n)
    if n == 0
        return 1
    end
    if n%2 == 0
        return exp(m*m, n/2)
    else
        return exp(m*m, n/2) * m
    end
end

This method has a time complexity of O(log N), which is much better than O(N). So let's apply this method to matrix M. This method applied to a matrix will look slightly more complicated due to the matrix multiplication, but the runtime will be on the same order.

# This method will take in a 2x2 matrix and an integer exponent
def mat_exp(m, n)
    if n == 1
        return m
    end
    m1 = m[0][0]
    m2 = m[0][1]
    m3 = m[1][0]
    m4 = m[1][1]

    m_sq = [
        [m1*m1 + m2*m3, m1*m2 + m2*m4], 
        [m3*m1 + m4*m3, m3*m2 + m4*m4]
    ] 
    if n%2 == 0
        return mat_exp(m_sq, n/2)
    else
        r = mat_exp(m_sq, n/2)
        r1 = r[0][0]
        r2 = r[0][1]
        r3 = r[1][0]
        r4 = r[1][1]
        # Multiply matrix m to matrix r
        return [
            [r1*m1 + r2*m3, r1*m2 + r2*m4],
            [r3*m1 + r4+m3, r3*m2 + r4*m4]
        ]
    end
end

Since this method doesn't actually return a Fibonacci number but returns a matrix instead, we can call it as a helper method inside another method that will return the actual number that we're looking for.

def efficient_fib(n)
    if n == 0
        return 0
    end
    m = [[1, 1],[1, 0]]
    r = mat_exp(m, n - 1)
    return r[0][0]
end

Now we have an algorithm whose time complexity is O(log N), but will this actually help much with the performance of the method?

The answer is both yes and no. Let's say we're looking for the 5th number in the Fibonacci Sequence.

puts "Using simple_fib:"
t1 = Time.now
puts "The 5th element in the Fibonacci Sequence is #{simple_fib(5)}"
t2 = Time.now
puts "Time taken: #{t2 - t1}\n\n"

puts "Using efficient_fib:"
t3 = Time.now
puts "The 5th element in the Fibonacci Sequence is #{efficient_fib(5)}"
t4 = Time.now
puts "Time taken: #{t4 - t3}\n\n"

# => Using simple_fib:
# => The 5th element in the Fibonacci Sequence is 5
# => Time taken: 7.0e-06
# => 
# => Using efficient_fib:
# => The 5th element in the Fibonacci Sequence is 5
# => Time taken: 6.0e-06
# =>

So the efficient algorithm was about 1 μs faster than the simple one. It doesn't really seem like it was worth it to write an entirely new algorithm just to improve performance by 1 μs.

But what if we're looking for the 500th element instead of the 5th element?

t1 = Time.now
simple_fib(500)
t2 = Time.now
puts "Time taken using simple_fib: #{t2 - t1}\n\n"

t3 = Time.now
efficient_fib(500)
t4 = Time.now
puts "Time taken using efficient_fib: #{t4 - t3}\n\n"

# => Time taken using simple_fib: 7.7e-05
# =>  
# => Time taken using efficient_fib: 3.0e-05
# =>

This time there's a difference of 47 μs. So that's slightly better... Let's take a look now at what happens if we call both methods on n = 50000.

t1 = Time.now
simple_fib(50000)
t2 = Time.now
puts "Time taken using simple_fib: #{t2 - t1}\n\n"

t3 = Time.now
efficient_fib(50000)
t4 = Time.now
puts "Time taken using efficient_fib: #{t4 - t3}\n\n"

# => Time taken using simple_fib: 0.075218
# =>
# => Time taken using efficient_fib: 0.000832
# =>

This time there's a difference of 2 orders of magnitude! It seems that, when n is small, there's not much of a difference in the runtime of the methods, but when n gets larger, the difference in runtime also becomes larger. We can graph some more values of n to look at the trends.

The red points on the graph mark the runtime for different values of n for simple_fib, and the blue points mark the runtime for different values of n for efficient_fib. From the graph, it is apparent that the runtime increases rapidly for simple_fib as the value of n increases while the runtime for efficient_fib stays relatively low.

Although most programs with real applications probably won't be needing an efficient algorithm specifically for the Fibonacci Sequence, the purpose of this case study is to demonstrate how big of a difference an efficient algorithm can make. It is especially important when input values or the number of inputs is large, which is very likely if you're working on an app that has a substantial number of users. In the world of tech, a few seconds can be a big deal. You've experienced that yourself if you've ever felt frustration from a webpage or app taking more than 3 seconds to load.

If you are new to programming, it can be easy to find yourself thinking, "I'll be happy as long as I can get this code to work." However, I hope that this post has convinced you to take it a step further and also keep algorithm efficiency and performance optimization in mind as you continue your journey as a software engineer.