Forem: Upamanyu Das

LeetCode Daily Problem - 967. Numbers With Same Consecutive Differences

Upamanyu Das — Sat, 03 Sep 2022 22:05:33 +0000

Problem

Return all non-negative integers of length n such that the absolute difference between every two consecutive digits is k.

Note that every number in the answer must not have leading zeros. For example, 01 has one leading zero and is invalid.

You may return the answer in any order.

Idea

The way to solve this is to construct the number digit by digit. We can pick any digit x from 1 through 9 as the first digit. Once we have picked the digit we have at most two valid choices x + k and x - k i.e. they both lie in [0, 9]. The problem then reduces to solving a smaller problem with similar structure, i.e. with one less digit at every step. When n digits have been picked we can add the number to our answer array.

Solution

class Solution {
    public void dfs (int NumOfDigits, int currNum, int k, List<Integer> ans) {
        if (NumOfDigits == 0) {
            ans.add(currNum);
            return;
        }

        List<Integer> nextDigits = new ArrayList<>();

        int tailDigit = currNum % 10;
        nextDigits.add(tailDigit + k);
        if(k != 0) {
            nextDigits.add(tailDigit - k);
        }

        for(int nextDigit : nextDigits) {
            if(0 <= nextDigit && nextDigit < 10) {
                int num = currNum * 10 + nextDigit;
                dfs(NumOfDigits - 1, num, k, ans);
            }
        }
    }

    public int[] numsSameConsecDiff(int n, int k) {
        if (n == 1) {
            return new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        }

        List<Integer> ans = new LinkedList<Integer>();

        for (int i = 1; i < 10; i++) {
            dfs(n - 1, i, k, ans);
        }

        return ans.stream().mapToInt(i -> i).toArray();

    }
}

Runtime: 9 ms, faster than 21.14% of Java online submissions for Numbers With Same Consecutive Differences.

Memory Usage: 44.2 MB, less than 6.62% of Java online submissions for Numbers With Same Consecutive Differences.

Note - The BFS solution of this problem will be much more memory efficient as the recursion stack will not have to be dealt with.

Real World Python 🐍: Environment Setup - pyenv

Upamanyu Das — Sun, 29 Aug 2021 19:22:26 +0000

You should never ever touch system python.

What is system python?

System python is the python that comes installed with your operating system.

Why shouldn't I touch it?

There are a host of reasons to not use system python.

Not the version of python you're looking for. Maybe you want the latest features from python 3.9 but your OS only came with 3.8.
Globally installing dependencies is never a good idea and problems with multiple versions of a dependency will have you troubleshooting on a Sunday morning.
Your OS might have a system dependency on python which might make your entire system unusable because you managed to break python.

pyenv

Simple Python version management.

This tool lets us install our preferred python version and use that for our projects so that we don't have to touch system python.

pyenv / pyenv

Simple Python version management

Installing pyenv

Build dependencies

pyenv builds python from source, so you will need some build dependencies to use pyenv. These dependencies vary by platform.

Mac

brew install openssl readline sqlite3 xz zlib

Note: Assumes you have brew installed on your machine.

Debian

sudo apt-get install -y make build-essential libssl-dev zlib1g-dev \
libbz2-dev libreadline-dev libsqlite3-dev wget curl llvm libncurses5-dev \
libncursesw5-dev xz-utils tk-dev libffi-dev liblzma-dev python-openssl

For other systems please refer to the official installation docs.

pyenv

curl https://pyenv.run | bash

This uses the pyenv-installer project to install pyenv on your system.

Installing a python version

Check what versions are available:

pyenv install --list

Install a python version

pyenv install -v 3.9.5

Setting python version

pyenv lets us set the python version globally, locally in our project and even for a particular shell.

We want to set the python version for our project so we will use local.

We will create our project directory and navigate into it.

mkdir quotes-scraper && cd quotes-scraper

And then set the python version we want to use for our project.

pyenv local 3.9.5

This will create a .python-version file in the root directory of the project. If pyenv is active in our environment, this file will automatically activate the specified python version in the project.

I hope you found this post useful. Please leave any feedback in the comments or DM me @tintin_das on Twitter 🐦.

// Detect dark theme var iframe = document.getElementById('tweet-1432055144640704512-158'); if (document.body.className.includes('dark-theme')) { iframe.src = "https://platform.twitter.com/embed/Tweet.html?id=1432055144640704512&theme=dark" }

Real World Python 🐍: Introduction

Upamanyu Das — Sun, 29 Aug 2021 16:28:44 +0000

Motivation

There is a gap in the python material available online. While a lot of tutorials are available for absolute beginners, there is a distinct lack of content for those who are looking to take the next step.

Nature abhors a vacuum. So, here I am to fill the void. In this series we will cover all the stuff that goes into making a real world python project.

Intended Audience

Python beginners who have knowledge of the fundamentals of programming and are looking to start with their first real project. I will assume that the reader already knows topics such as conditional statements, loops, functions etc. My focus will be more on the structure and the "flow" of a project rather than the logic.

What we will build

A web scraper which grabs quotes from goodreads.com and stores them locally or to a remote database.

tintindas / quotes-scraper

Scrape quotes based on author (or search term) from Goodreads.

Roadmap

These are the planned topics for the series.

Environment Setup - pyenv
Project Setup
Directory Structure

Some Notes

This is my way of doing things which is just one way out of many. There are no hard and fast rules. Most of the steps in this series are optional, but highly recommended.
The series is mostly geared towards Mac/Linux systems. Though it should all work on WSL too.

Uh Oh! I Cloned without Forking!

Upamanyu Das — Sat, 14 Aug 2021 07:36:57 +0000

Last week I cloned a repo without forking it first and only realised my mistake after I had already made some commits to my local copy.

Rookie mistake!

But there's an easy fix.

Step 1: Remove the existing remote from your local repo.

git remote remove origin

Note: You can get a list of configured remotes and their URLs by running:

git remote -v

Step 2: Fork the project and copy the fork's URL

Step 3: Add the URL to your local copy.

git remote add origin [copied URL]

And you're done 😀 ! You can now push your code and it will go to your fork.

Hope this was helpful!

Hi, I am Upamanyu!

If you liked this post maybe you'll like my tweets too. Follow me @tintin_das 🐦.

Adding Typescript to my existing Node + Express API - Part 2 - Directory Structure

Upamanyu Das — Tue, 26 Jan 2021 06:30:48 +0000

If you're reading this I am assuming you are familiar with the set up steps we took in my earlier post.

Before we get VSCode to chill let's make sure our project's directory structure is easily understandable.

My directory structure used to look like this

Now it looks like this

The names of the folders are pretty self-explanatory.

config exports all our configuration options for mongodb and our server. The most important variables being exported are the username and password with which we access our database.

Mine looks like this

import dotenv from 'dotenv'

dotenv.config()

const MONGO_OPTIONS = {
    useUnifiedTopology: true,
    useNewUrlParser: true,
    keepAlive: true,
    poolSize: 50
}

const MONGO_USER = process.env.MONGO_USER
const MONGO_PASS = process.env.MONGO_PASS
const MONGO_DB = process.env.MONGO_DB

const MONGO = {
    user: MONGO_USER,
    password: MONGO_PASS,
    db: MONGO_DB,
    options: MONGO_OPTIONS,
    url: `mongodb+srv://${MONGO_USER}:${MONGO_PASS}@cluster0-yo7rn.mongodb.net/${MONGO_DB}`
}

const PORT = process.env.PORT || 3000

const config = {
    port: PORT,
    mongo: MONGO
}

export default config

controllers is the folder where we write the main control functions for our API, i.e., the main logic. These files will export functions which will be executed when the user goes to one of our API's endpoints.
models is where we will create the models which tell our server how to interact with the data in our database.
interfaces are to make sure that mongoose's model definitions play nice with typescript.
In routes we define routers which will connect the controllers with the routes they are intended for.

In the next part we will download some dependencies and set up some npm scripts that will let us set up our development server.

If you liked this post consider,

checking out my projects at tintindas
following me on twitter @tintin_das

Upamanyu Das

@tintin_das

I'm so Bengali even my zsh shell is fishy themed.

#fishy #zsh #Ubuntu #webdev

17:00 PM - 30 Nov 2020

Adding Typescript to my existing Node + Express API - Part 1 - Set up

Upamanyu Das — Thu, 21 Jan 2021 17:40:39 +0000

This is some documentation I am writing mostly for myself and for anyone who might want to add typescript to their own projects.

The project we are adding typescript to can be found at https://github.com/tintindas/quotes-api

1. Making a new branch

Always make a new branch before screwing around with code that already works. Learnt this the hard way.

git checkout -b add-typescript

2. Adding typescript and required types as dev dependencies

The typescript compilers and the types of the libraries used in our project need to be added as developer dependencies so that we have access to all the type definitions we require.

npm install -D typescript @types/node @types/express @types/mongoose @types/cors

3. Make a tsconfig.json file

If you have typescript globally installed run
tsc --init
else run
npx tsc --init

4. Edit tsconfig.json

Edit the outDir and rootDir properties in the tsconfig file.
Set the rootDir to be the directory where all your logic is stored.
The outDir is the destination where the typescript transpiler puts all the files vanilla javascript files produced after transpilation.

"outDir": "./dist",                         
"rootDir": "./src",

I named my input directory src and the target directory dist

Set the include property to be src or whatever you have named your rootDir if there are typescript files you do not wish to be transpiled outside of the rootDir folder.

How my tsconfig.json file looks like

{
  "compilerOptions": {
    "target": "es5",
    "module": "commonjs",
    "outDir": "./dist",                         
    "rootDir": "./src", 
    "esModuleInterop": true,
    "skipLibCheck": true,
    "forceConsistentCasingInFileNames": true
  },
  "include": ["src"]
}

5. Create src directory and move all of your logic into it.

Anything outside of the src folder will not be put into the dist folder which will be our final production code.

6. Change extension .ts

Change the javascript files into typescript files by changing all the extensions to .ts.

This was the setup part of the project. VSCode should be screaming at you right now. Don't worry we will fix that in next part.

If you liked this post consider,

checking out my projects at https://github.com/tintindas
following me on twitter @tintin_das