DEV Community: Samriddha Chattopadhyay

Neovim for beginners

Samriddha Chattopadhyay — Mon, 30 Sep 2024 09:01:40 +0000

So Here's the thing. I had planned to write one blog a week, but due to some reasons, I couldn't do much research on the thing I wanted to write about. So instead of writing a half-assed blog about a topic I don't know much about, I am writing a blog on something that I do know some things about. And yes, that's Neovim. It's a text editor I have been using in the past, and have always come back to even after I thought I would never return to it at some point.

My Neovim Journey

Before going into the actual content, I would like to share my neovim journey first.
I first started using neovim three years back. I was in the second year of my college at the time and was learning linux. Due to some issues (both hardware and software), VS Code wasn't running properly and I was having to use Sublime text (which is a fantastic tool imo). However, I was just not content with using Sublime. Something felt wrong and so, I started searching for other editors. I also tried Brackets, Atom and Eclipse in the process and none of them suited my taste. That was when I discovered vim (yes vim, not neovim).

The baby steps

I started using vim and started learning the shortcuts and keybinds. Eventually, I also wrote a config file (init.vim.....Ah.....this brings back memories) and was pretty content with it. But something still felt lacking. I had started watching Primeagen and in one of his videos, I heard about neovim. I was curious, so I checked it out. I had heard that it's a fork of vim and has a lot of extra stuff (like native lsp support and all), but I wasn't too happy with it as it felt mostly same to me. However, all that changed when I discovered something new.

The world of linux ricing

As I mentioned earlier, I was learning linux and to no surprise, I came across linux ricing soon. At the time, I was using a ubuntu installation on my HP pavilion laptop, and I was pretty bored with the stock gnome look. I had tried to customize with some plugins and stuff, but I still didn't like it at the time. That was when I came across Distrotube channel and learnt about linux ricing. I started installing different window managers and bars and run launchers and started tinkering with config files. One of the first window managers I used was the awesome window manager. It's configured in lua, the same language used to configure neovim. That was when I learnt lua properly. However, I wasn't content with just my desktop looking good. I wanted my editor to match the theme and that was when I started using Lunar vim.

The first ever neovim distro

For people who don't know, Lunarvim is a distro for neovim. That is, it's a specific set of config made by @chrisatmachine. At the time, it was in it's very early stage and I got to see the exact configs without much abstractions. Being a nerd, I dug into it and within a month, figured out how things worked. Once that happened, I made my very first config file (custom one) and started daily driving it.

Making my own demon

We create our own demons

- Tony Stark

After I made my own config, I started daily driving it. However, I started to notice that my productivity had gone down instead of going up.
The reason was that, I was always updating my config. Everytime I stareted working, I would come across some issue and I would start tinkering with my config and I would spend a lot of time in the process. And this was not restricted to neovim. I would also make changes to my window manager config, my polybar config and rofi configs from time to time, but these were still rare. Neovim was something I used frequently, and I noticed a lot of issues with it (yeah I was a noob at the time, and still am xD) and started fixing them. This made me lose a lot of time in a day and it was starting to affect my productivity and work as well. So, I shifted to Nvchad.

The Chad config

Nvchad was the setup of my dreams. It looked so similar to VS Code, but was in vim and I loved it. I started daily driving it, and I used it for the longest ( I think 5-6 months). Again, being a nerd, I used to go through it's code and figure out how things worked and I would change some things here and there to see how it affected the setup. These 6 months, I learned the most about Neovim. I learnt about buffers, windows, tabs and the differences between those. I learnt how the keybindings actually worked (yeah earlier I mostly copy pasted, so I wasn't sure how things were actually working), I learned about neovim auto commands, and the list goes on.
There was another thing I leant from this, and that is actually what this blog is about. I learnt what I actually needed to have an usable setup.

Wrting a config from scratch

Yes, I made another config (I somehow managed to lose all the code for the config, though 😅) and this time, it helped increase my productivity by a lot. "But Samy, I thought you liked Nvchad. Then why did you bother writing your own config ?" is what you'd like to ask, and here's my answer:

Nvchad was too much similar to vs code and was bloated with stuff that I didn't use. In fact, it reminded me of VS Code and for some reason, I wasn't able to focus on my work at one point (yeah that's kind of a lame reason)
I think neovim is a personalized editor, and I would like something that actually catered to my needs (minimal, fast and reliable). So I went on and made my own custom config and I used it for the rest of the time I was using linux. Yes. I am on windows now, and I have another config at the moment.

Getting my very own laptop

"Wait I think you said you had your laptop!" is what careful readers would say. Yes, I had one, but I had stored up enough money to buy a gaming laptop (the former one being more of an office laptop, couldn't run games smoothly) and yes I like gaming. So I got myself a gaming laptop, and yeah I had to use windows in it because linux gaming sucked (it still does imo, but that's a conversation for later). I loved my new laptop but I hated windows and I cursed it for around 2-3 months as there were not many tools that I used to use which were available on windows. However, at some point, I realized that I could just make some if I wanted to use them. If you're interested, please let me know in the comments and I would love to share some stuff I did to get back my linux setup (or at least something close to it) on windows. I installed neovim and made my new setup.

Basic parts of a neovim config

Okay, that's enough of backstory. Let's get to the point now.
To have a basic setup, you need the following:

A terminal and a neovim installation (duh)
Some sensible settings (details below)
Some sensible keybinds (details below)
Treesitter
A fuzzy finder (Telescope, for example)
Your required plugins (this depends on the user, but I will share the ones I use below and some essential ones)

As you can see, I didn't mention a colorscheme and a file tree. This is because, I believe a file tree is not much important when you have a fuzzy finder, however, you can have one if you want (even I use one and I have included that under 6). So let's see how to configure each of these. I will discuss how I configured them and I will link documentations for each of them. I highly suggest reading the documentation for details. This blog will simply cover the surface so that it's simple to understand, however, to really understand how things work, reading the docs is a must.

A terminal and a neovim installation

This should be a no brainer. Neovim is a terminal text editor, and so, having a terminal is a must. There are some GUI apps to load neovim as well, and you are free to use them too. It's just that my experience with them have been a little lacking as sometimes, they tend to slow down a lot (In my case, it happened when I opened a lot of files and had a lot of plugins) or sometimes, they have certain configs diabled (for example, transparent background would sometimes be disabled for some reason, etc).
My choice of terminal for my current windows workflow is the OG Windows Terminal. I am daily driving my neovim in it for about 6 months now and I have yet to face any issue. Of course, I had to change some keybinds in it to make things work (For example, I disabled the Ctrl+V as it was conflicting with neovim's visual block mode).
To set up neovim in windows, first, install neovim. I used winget to do that:

$ winget install Neovim.Neovim

You can also use chocolatey or scoop or any other package manager you use. Once neovim is installed, you need to write your config in C:\Users\_username_\AppData\Local\nvim folder. If the folder doesn't exist, you can create one. All your config will reside inside the init.lua file within the folder. This is the folder structure I use:

├───lua
│   ├───config
│   │   ├───comments.lua
│   │   ├───context.lua
│   │   ├───git.lua
│   │   ├───harpoon.lua
│   │   ├───illuminate.lua
│   │   ├───init.lua
│   │   ├───lazy.lua
│   │   ├───lsp.lua
│   │   ├───lualine.lua
│   │   ├───telescope.lua
│   │   ├───treesitter.lua
│   │   ├───trouble.lua
│   │   └───undotree.lua
│   └───samy
│   │   ├───autocommands.lua
│   │   ├───git.lua
│   │   ├───init.lua
│   │   ├───keybinds.lua
│   │   └───settings.lua
└───undodir

Please ignore all the different files for now. As a general rule, this is what I follow:
Any plugin config goes into config/.
Any of my own config goes into samy/.
This helps me keep the code clean (it's not that clean, though 😅)

Some sensible settings

I shall divide this into some sub-sections to make things easier to understand.

Line numbers

There are three types for line numbers in neovim:

No line numbers (default)
Regular line numbers
Relative line numbers I personally use a mixture of regular and relative line numbers. This is how I achieve it:

local opts = vim.opt

-- Line Numbers
opts.nu = true
opts.relativenumber = true

And this is how it looks:

Notice how the actual line number on the actual line is visible and the rest are numbered on the basis of the active line. This helps in navigating code within the file.
Let's say, I need to go to General settings portion. Instead of hitting j multiple times, I can hit 13j and go there directly. I know it's 13j and not 25j or 6j because I can see the relative line number for the line is 13!

Indentation

This should be straightforward. Indenting code is a part of our daily lives and let's be honest, indented code looks kinda sexy (Just kidding I don;t get turned on my code indentation). Personally, I like 4 space indenting as it tells me when I should made a modular function for the logic or when I am writing bad code (trust me, it's easier to spot bad code with a 4 space indenting). So these are the setting I use for specifying my indentation:

-- Indenting
opts.tabstop = 4
opts.softtabstop = 4
opts.shiftwidth = 4
opts.expandtab = true
opts.smartindent = true

Search and other general settings

Please note that everything I say under this section is a personal opinion. You might not agree with me, and that's fine, so feel free to change things here according to your taste.
I like my code wrapped, hence, this line:

-- General Settings
opts.wrap = false

I like to keep swapfile off. What this does is, it makes neovim to not store the buffers in case they are not closed properly. So, I add these lines:

opts.swapfile = false
opts.backup = false

The next two lines are related to a plugin called undotree, and I would recommend using this one (details further down):

opts.undodir = "C:\\Users\\samy3\\AppData\\Local\\nvim\\undodir"
opts.undofile = true

I like the current line to be highlighted and hence, I add this:

opts.cursorline = true

The following two lines configure highlights after search and incremental search:

-- Searching
opts.hlsearch = false
opts.incsearch = true

hlsearch = false makes sure that the searches are not highlighted after the search is complete (this just looks weird, so I keep it off. Please try keeping it on and see for yourself if it looks good).
incsearch = true ensures that the searches are highlighted while the search is happening. For example, when I hit / and write sea, all instances of sea will be highlighted. This is not a default behavior and needs to be enabled (yeah this was a shock to me too).

Some sensible keybinds

I won't say much here. Keybinds and shortcuts are personal stuff, so I would simply share what I use and some tips to customize them.
These are what I use:

vim.g.mapleader = " "

local keymap = vim.keymap

-- keymap.set("n", "<leader>pv", vim.cmd.Ex)

-- VS Code style shifting
keymap.set("v", "J", ":m '>=1<CR>gv=gv")
keymap.set("v", "K", ":m '<-2<CR>gv=gv")

-- Keybindings to make life easy
keymap.set("i", "jj", "<Esc>")
keymap.set("n", "Y", "yg$")
keymap.set("n", "J", "mzJ`z")
keymap.set("n", "<C-d>", "<C-d>zz")
keymap.set("n", "<C-u>", "<C-u>zz")
keymap.set("n", "n", "nzzzv")
keymap.set("n", "N", "Nzzzv")

-- Copy paste Keybindings for various utilities
keymap.set("x", "<leader>p", "\"_dP")
keymap.set("n", "<leader>y", "\"+y")
keymap.set("v", "<leader>y", "\"+y")
keymap.set("n", "<leader>Y", "\"+Y")
keymap.set("n", "<leader>d", "\"_d")
keymap.set("v", "<leader>d", "\"_d")

-- More life enhancement Keybindings
keymap.set("n", "Q", "<nop>")
keymap.set("n", "<leader>f", function ()
    vim.lsp.buf.format({ async = true })
end)
keymap.set("n", "<leader>x", "<cmd>!chmod +x %<CR>", { silent = true })

-- Error navigation
keymap.set("n", "<C-k>", "<cmd>cprev<CR>", { silent = true })
keymap.set("n", "<C-j>", "<cmd>cnext<CR>", { silent = true })

-- Buffer navigation
keymap.set("n", "<leader>bx", "<cmd>bdelete<CR>", { silent = true })
keymap.set("n", "<leader>bb", "<cmd>bnext<CR>", { silent = true })
keymap.set("n", "<leader>bB", "<cmd>bprev<CR>", { silent = true })

Disclaimer: Some of these are copied from Primeagen's config, so if you're a viewer and were wondering why they looked familiar, you know now.

Here's an explanation of what's going on:

vim.g.mapleader sets the leader key. This is similar to a mod key, but for neovim. SUPER, META, ALT, CTRL and SHIFT are also available, but it's generally not a good idea to set these as leader keys. A lot of people use SPACE as leader key, and so do I.
keymap.set sets a keybind. To do so, all you need to do is specify the mode, the key (or skystorkes) you want to bind and the key or function or command you want to bind it to. We use n for Normal Mode, i for Insert mode, v or x for different visual modes and t for terminal mode.

If you want to copy my keybinds, here's a summary of what you're going to have:

Mode	Key	Effect
Normal	Y	Yank till end of line
Normal	J	Join the current and the next line and keep the cursor on the last line
Normal	Ctrl + d	Scroll down half a page and keep the cursor at the center of the page
Normal	Ctrl + u	Scroll up half a page and keep the cursor at the center of the page
Normal	n	Go to next search result
Normal	N	Go to previous search result
Normal	Leader + y	Copy to clipboard
Normal	Leader + y	Copy entire line to clipboard
Normal	Leader + d	Delete and remove from yank buffer
Normal	Leader + f	Format document using the active LSP
Normal	Leader + x	Make current script executable (works only in linux)
Normal	Ctrl + j	Go to next error
Normal	Ctrl + k	Go to previous error
Normal	Ctrl + bx	Close buffer
Normal	Ctrl + bb	Go to next buffer
Normal	Ctrl + bB	Go to previous buffer
Insert1	jj	Exit insert mode
Visual	J	Move lines down
Visual	K	Move lines up
Visual	Leader + y	Copy selection to clipboard
Visual	Leader + d	Delete selection and remove from yank buffer
Visual	Leader + x	Paste without copying the selection

Treesitter

Treesitter is what makes your neovim colorful. It uses the LSP and colorscheme and colors your variables, keywords and other stuff. To understand how treesitter works and configure treesitter please read the docs. Here is my configuration for treesitter:

require('nvim-treesitter.install').prefer_git = true
require 'nvim-treesitter.configs'.setup {
    ensure_installed = { 'bash', 'c', 'diff', 'html', 'lua', 'luadoc', 'markdown', 'vim', 'vimdoc', 'javascript', 'rust', 'typescript', "comment" },
    -- Autoinstall languages that are not installed
    auto_install = true,
    highlight = {
        enable = true,
        -- Some languages depend on vim's regex highlighting system (such as Ruby) for indent rules.
        --  If you are experiencing weird indenting issues, add the language to
        --  the list of additional_vim_regex_highlighting and disabled languages for indent.
        additional_vim_regex_highlighting = { 'ruby' },
    },
    indent = { enable = true, disable = { 'ruby' } },
}

A fuzzy finder

I personally use Telescope as my fuzzy finder. Again, here's the docs for telescope and here's my config:

local builtin = require("telescope.builtin")

local keymap = vim.keymap

keymap.set("n", "<leader>pf", builtin.find_files, {})
keymap.set("n", "<leader>bl", builtin.buffers, {})
keymap.set("n", "<leader>pp", builtin.git_files, {})
keymap.set("n", "<leader>ps", function ()
    builtin.grep_string({ search = vim.fn.input("Search: ") });
end)

Here's an explanation about what is going on:
Firstly, as soon as we install the telescope plugin and start it when our neovim session starts, we can call the find_files, buffers, git_files, etc. anytime we want. There are some commands as well to trigger them and the docs will mention everything in detail. Here, we are triggering them using lua functions.
So builtin contains all the functions and stuff within the telescope package and we simply call the individual functions (this is a higher level explanation for any library in neovim btw).
Now, here, we bind it to some keystokes:

Mode	Key	Effect
Normal	Leader + pf	Search within all the files (this includes files ignored by git, like node_modules)
Normal	Leader + pp	Search within all the git files (this excludes files ignored by git, like node_modules)
Normal	Leader + bl	List all the active buffers (this lets you navigate between opened buffers or files)
Normal	Leader + ps	Project wide search for a specific term (Similar to what we have on VS Code)

Now, you might be confused about two things:

How do we even install this telescope or the treesitter mentioned above ?
How are buffers and files related ?

The answer to the first is provided in the next section, where we discuss the required plugins, so please hold your horses.
The answer to the second one ? Let's understand that.

Bonus: Opening files (and folders) in neovim

For people who have experience with IDEs or even notepad, opening files is something simple. You click on a file (or double click in some cases) and it opens up in an editor for you to edit. However, as with everything else, neovim takes this a step ahead.
In neovim, there are these three concepts relating to opening files:

Buffers
Window and Panes
Tabs

Let's get down to each of these at once, starting with windows. We will take an example of VS Code to make things easier to understand.
In VS Code, when you open a file, it opens in a tab. Think of the current VS Code session as the window (I'm 99.99% sure that is what people call it as well). The concept of window is the same in neovim. You start a session and a window appears. Now, if you've used split views in VS Code, you'd know that windows can be split between panes. What this does is, it opens the file again (side by side) in another tab.

In neovim, panes and windows work in a similar way. A window is a neovim window and a pane is a split of the window (vertical or horizontal). What is different, though is the content being shown (or at least how it's being shown).
You see, neovim opens the file only once and then just shows it to you side by side.
This is done with the help of Buffers. Neovim always opens a file or folder in a buffer and shows the buffer in separate panes. This way, less memory is used for doing the same task (This is why VS Code doesn't suit me anymore).

So let's make things clear. You hit enter on a file (or open it in some way) and neovim creates a buffer for the file and shows it in a window. You can split the window and create panes, but the same buffer will be shown instead of opening the file again. Tabs takes this one step further. A tab is like a superset for the window. When you open multiple tabs, you get multiple windows in the same neovim session. So you can have your different microservices open in different tabs on the same session and keep working without worrying about anything else.

Now that this is clear, let's see some essential plugins you'd need for your basic setup.

Your required plugins

The first thing you need is a plugin manager. This works in the same way any package manager works in an OS.
There are couple of popular ones, like Packer, Plug, Lazy, etc.
I use Lazy (because I am Lazy lol). It really lives up to it's name, and let's you install packages in the most lazy way. Simply mention the git repo of the package and it will take care of the rest. Of course, you need to write the configs, but there is no other hastle in the installation part at least. This also enabled lazy loading by default, which makes neovim load faster than is the packages were all loaded at once. Here is what you need to do to install Lazy:

-- Bootstrap lazy.nvim
local lazypath = vim.fn.stdpath("data") .. "/lazy/lazy.nvim"
if not (vim.uv or vim.loop).fs_stat(lazypath) then
    local lazyrepo = "https://github.com/folke/lazy.nvim.git"
    local out = vim.fn.system({ "git", "clone", "--filter=blob:none", "--branch=stable", lazyrepo, lazypath })
    if vim.v.shell_error ~= 0 then
        vim.api.nvim_echo({
            { "Failed to clone lazy.nvim:\n", "ErrorMsg" },
            { out,                            "WarningMsg" },
            { "\nPress any key to exit..." },
        }, true, {})
        vim.fn.getchar()
        os.exit(1)
    end
end
vim.opt.rtp:prepend(lazypath)

-- Make sure to setup `mapleader` and `maplocalleader` before
-- loading lazy.nvim so that mappings are correct.
-- This is also a good place to setup other settings (vim.opt)
vim.g.mapleader = " "
vim.g.maplocalleader = "\\"

-- Setup lazy.nvim
require("lazy").setup({
    spec = {
        -- All the plugins go here
    },
    -- Configure any other settings here. See the documentation for more details.
    -- colorscheme that will be used when installing plugins.
    install = { missing = true, colorscheme = { "catppuccin-mocha" } },
    -- automatically check for plugin updates
    checker = { enabled = true, notify = false },
}, {
    ui = {
        -- If you are using a Nerd Font: set icons to an empty table which will use the
        -- default lazy.nvim defined Nerd Font icons, otherwise define a unicode icons table
        icons = vim.g.have_nerd_font and {} or {
            cmd = '⌘',
            config = '🛠',
            event = '📅',
            ft = '📂',
            init = '⚙',
            keys = '🗝',
            plugin = '🔌',
            runtime = '💻',
            require = '🌙',
            source = '📄',
            start = '🚀',
            task = '📌',
            lazy = '💤 ',
        },
    },
})

This is a boilerplate and you can get the same along with the docs from here.
To install a package, you need to provide the name in the spec object and Lazy will take care of the rest. here are some examples for that:

Using just a package name:

"nvim-lua/plenary.nvim",

Using a name and options:

{
    'nvim-telescope/telescope.nvim',
    tag = '0.1.8',
    dependencies = { 'nvim-lua/plenary.nvim' }
},
{
    "nvim-treesitter/nvim-treesitter",
    build = ":TSUpdate",
    opts = {
        ensure_installed = { 'bash', 'c', 'diff', 'html', 'lua', 'luadoc', 'markdown', 'vim', 'vimdoc', 'javascript', 'rust', 'typescript' },
        -- Autoinstall languages that are not installed
        auto_install = true,
        highlight = {
            enable = true,
            -- Some languages depend on vim's regex highlighting system (such as Ruby) for indent rules.
            --  If you are experiencing weird indenting issues, add the language to
            --  the list of additional_vim_regex_highlighting and disabled languages for indent.
            additional_vim_regex_highlighting = { 'ruby' },
        },
        indent = { enable = true, disable = { 'ruby' } },
    },
},

As you can see, it's pretty simple to install packages and the same can be found on the docs for each package (well, at least mostly).

Alongside this, there are some other packages that any developer would like to have:

Undotree
Gitsigns
LSP
Comment
File tree (optional)
Colorscheme (optional)

I'll drop the docs and my configs for each of these here without much explanation as one good look at the docs will explain everything here. If something is difficult to understand, please feel free to put that up in the comments and I shall answer each of them:

Undotree

Docs: https://github.com/mbbill/undotree
Config:

vim.keymap.set("n", "<leader>u", vim.cmd.UndotreeToggle)

Gitsigns

Docs: https://github.com/lewis6991/gitsigns.nvim
Config:

[vim.keymap.set("n", "<leader>u", vim.cmd.UndotreeToggle)](<local neogit = require('neogit')
neogit.setup {}

require('gitsigns').setup {
    signs = {
        add          = { text = '┃' },
        change       = { text = '┃' },
        delete       = { text = '_' },
        topdelete    = { text = '‾' },
        changedelete = { text = '~' },
        untracked    = { text = '┆' },
    },
    signs_staged = {
        add          = { text = '┃' },
        change       = { text = '┃' },
        delete       = { text = '_' },
        topdelete    = { text = '‾' },
        changedelete = { text = '~' },
        untracked    = { text = '┆' },
    },
    signs_staged_enable = true,
    signcolumn = true,  -- Toggle with `:Gitsigns toggle_signs`
    numhl      = false, -- Toggle with `:Gitsigns toggle_numhl`
    linehl     = false, -- Toggle with `:Gitsigns toggle_linehl`
    word_diff  = false, -- Toggle with `:Gitsigns toggle_word_diff`
    watch_gitdir = {
        follow_files = true
    },
    auto_attach = true,
    attach_to_untracked = false,
    current_line_blame = false, -- Toggle with `:Gitsigns toggle_current_line_blame`
    current_line_blame_opts = {
        virt_text = true,
        virt_text_pos = 'eol', -- 'eol' | 'overlay' | 'right_align'
        delay = 1000,
        ignore_whitespace = false,
        virt_text_priority = 100,
    },
    current_line_blame_formatter = '%3Cauthor%3E, <author_time:%R> - <summary>',
    sign_priority = 6,
    update_debounce = 100,
    status_formatter = nil, -- Use default
    max_file_length = 40000, -- Disable if file is longer than this (in lines)
    preview_config = {
        -- Options passed to nvim_open_win
        border = 'single',
        style = 'minimal',
        relative = 'cursor',
        row = 0,
        col = 1
    },
    on_attach = function(bufnr)
        local gitsigns = require('gitsigns')

        local function map(mode, l, r, opts)
            opts = opts or {}
            opts.buffer = bufnr
            vim.keymap.set(mode, l, r, opts)
        end

        -- Navigation
        map('n', ']c', function()
            if vim.wo.diff then
                vim.cmd.normal({']c', bang = true})
            else
                gitsigns.nav_hunk('next')
            end
        end)

        map('n', '[c', function()
            if vim.wo.diff then
                vim.cmd.normal({'[c', bang = true})
            else
                gitsigns.nav_hunk('prev')
            end
        end)

        -- Actions
        map('n', '<leader>hs', gitsigns.stage_hunk)
        map('n', '<leader>hr', gitsigns.reset_hunk)
        map('v', '<leader>hs', function() gitsigns.stage_hunk {vim.fn.line('.'), vim.fn.line('v')} end)
        map('v', '<leader>hr', function() gitsigns.reset_hunk {vim.fn.line('.'), vim.fn.line('v')} end)
        map('n', '<leader>hS', gitsigns.stage_buffer)
        map('n', '<leader>hu', gitsigns.undo_stage_hunk)
        map('n', '<leader>hR', gitsigns.reset_buffer)
        map('n', '<leader>hp', gitsigns.preview_hunk)
        map('n', '<leader>hb', function() gitsigns.blame_line{full=true} end)
        map('n', '<leader>tb', gitsigns.toggle_current_line_blame)
        map('n', '<leader>hd', gitsigns.diffthis)
        map('n', '<leader>hD', function() gitsigns.diffthis('~') end)
        map('n', '<leader>td', gitsigns.toggle_deleted)

        -- Text object
        map({'o', 'x'}, 'ih', ':<C-U>Gitsigns select_hunk<CR>')
    end
}>

LSP

Docs: https://github.com/VonHeikemen/lsp-zero.nvim
Config:

local lsp_zero = require('lsp-zero')
local cmp_lsp = require("cmp_nvim_lsp")

lsp_zero.on_attach(function(client, bufnr)
    -- see :help lsp-zero-keybindings
    -- to learn the available actions
    if client.name == "tsserver" then
        client.server_capabilities.document_formatting = false
    end
    lsp_zero.default_keymaps({ buffer = bufnr })
end)

local capabilities = vim.tbl_deep_extend(
    "force",
    {},
    vim.lsp.protocol.make_client_capabilities(),
    cmp_lsp.default_capabilities()
)

-- to learn how to use mason.nvim
-- read this: https://github.com/VonHeikemen/lsp-zero.nvim/blob/v3.x/doc/md/guide/integrate-with-mason-nvim.md
require('mason').setup({})
require('mason-lspconfig').setup({
    ensure_installed = {
        "lua_ls",
        "tsserver",
        "eslint",
        "rust_analyzer"
    },
    handlers = {
        function(server_name)
            local opts = {}
            if server_name == "tsserver" then
                opts.settings = {
                    implicitProjectConfiguration = {
                        checkJs = true
                    },
                }
            end

            opts.capabilities = capabilities

            require('lspconfig')[server_name].setup(opts)
        end,
    },
})

local cmp = require("cmp")
local luasnip = require('luasnip')
luasnip.config.setup {}
local cmp_mappings = cmp.mapping.preset.insert({
    ["<C-Space>"] = cmp.mapping.complete(),
    ["<C-k>"] = cmp.mapping.select_prev_item(),
    ["<C-j>"] = cmp.mapping.select_next_item(),
    ["<C-b>"] = cmp.mapping(cmp.mapping.scroll_docs(-1), { "i", "c" }),
    ["<C-f>"] = cmp.mapping(cmp.mapping.scroll_docs(1), { "i", "c" }),
    ["<C-y>"] = cmp.config.disable, -- Specify `cmp.config.disable` if you want to remove the default `<C-y>` mapping.
    ["<C-e>"] = cmp.mapping({
        i = cmp.mapping.abort(),
        c = cmp.mapping.close(),
    }),
    -- Accept currently selected item. If none selected, `select` first item.
    -- Set `select` to `false` to only confirm explicitly selected items.
    ["<CR>"] = cmp.mapping.confirm({ select = true }),
    ["<Tab>"] = cmp.mapping(function(fallback)
        if cmp.visible() then
            cmp.select_next_item()
        else
            fallback()
        end
    end, { "i", "s" }),
    ["<S-Tab>"] = cmp.mapping(function(fallback)
        if cmp.visible() then
            cmp.select_prev_item()
        else
            fallback()
        end
    end, { "i", "s" }),
})

cmp.setup({
    snippet = {
        expand = function(args)
            luasnip.lsp_expand(args.body)
        end,
    },
    completion = { completeopt = 'menu,menuone,noinsert' },
    mapping = cmp_mappings,
    sources = {
        { name = 'nvim_lsp' },
        { name = 'luasnip' },
        { name = 'path' },
    },
})

local status, prettier = pcall(require, "prettier")
if not status then
    return
end

prettier.setup({
    bin = "prettierd",
    filetypes = {
        "css",
        "javascript",
        "javascriptreact",
        "typescript",
        "typescriptreact",
        "json",
        "scss",
        "less",
    },
})

Comment

This has two parts to it:

Comments (To add comments) Docs: https://github.com/numToStr/Comment.nvim Config:

local status_ok, comment = pcall(require, "Comment")
if not status_ok then
    return
end

comment.setup({
    pre_hook = function(ctx)
        local U = require("Comment.utils")

        local location = nil
        if ctx.ctype == U.ctype.block then
            location = require("ts_context_commentstring.utils").get_cursor_location()
        elseif ctx.cmotion == U.cmotion.v or ctx.cmotion == U.cmotion.V then
            location = require("ts_context_commentstring.utils").get_visual_start_location()
        end

        return require("ts_context_commentstring.internal").calculate_commentstring({
            key = ctx.ctype == U.ctype.line and "__default" or "__multiline",
            location = location,
        })
    end,
})

Treesitter Context (To give treesitter context of which language it is) Docs: https://github.com/nvim-treesitter/nvim-treesitter-context Config:

require 'treesitter-context'.setup {
    enable = true,            -- Enable this plugin (Can be enabled/disabled later via commands)
    max_lines = 0,            -- How many lines the window should span. Values <= 0 mean no limit.
    min_window_height = 0,    -- Minimum editor window height to enable context. Values <= 0 mean no limit.
    line_numbers = true,
    multiline_threshold = 20, -- Maximum number of lines to show for a single context
    trim_scope = 'outer',     -- Which context lines to discard if `max_lines` is exceeded. Choices: 'inner', 'outer'
    mode = 'cursor',          -- Line used to calculate context. Choices: 'cursor', 'topline'
    -- Separator between context and content. Should be a single character string, like '-'.
    -- When separator is set, the context will only show up when there are at least 2 lines above cursorline.
    separator = nil,
    zindex = 20,     -- The Z-index of the context window
    on_attach = nil, -- (fun(buf: integer): boolean) return false to disable attaching
}

File tree (optional)

This is a little subjective and varies for user to user. There are many good file tree plugins, some of the popular ones being nvim-tree, neotree, nerdtree, etc.
personally, I hate file explorers (takes up a lot of space and shifts focus, and more importantly, reminds me of VS Code), so I use yazi.nvim

Docs: https://github.com/mikavilpas/yazi.nvim
Config:
This doesn't require any separate config. If you use yazi, the same config will be used here. Only the keybinds need to be configured while installing:

{
    "mikavilpas/yazi.nvim",
    event = "VeryLazy",
    keys = {
        -- 👇 in this section, choose your own keymappings!
        {
            "<leader>pv",
            function()
                require("yazi").yazi()
            end,
            desc = "Open the file manager",
        },
        {
            -- Open in the current working directory
            "<leader>cw",
            function()
                require("yazi").yazi(nil, vim.fn.getcwd())
            end,
            desc = "Open the file manager in nvim's working directory",
        },
    },
    opts = {
        -- if you want to open yazi instead of netrw, see below for more info
        open_for_directories = false,
    },
},

Colorscheme (optional)

This is again subjective, and depends on the user. I personally use catppuccin.
Docs: https://github.com/catppuccin/nvim
Config:

{
    "catppuccin/nvim",
    name = "catppuccin",
    priority = 1000
},

Bonus: Some quality of life plugins

Here are some more plugins that I use personally:

Harpoon
Neogit
TODO Domments
Mini.nvim
Noice.nvim
Lualine
Autopairs
Indent Blankline
nvim-ts-context-commentstring
vim-css-color
vim-closetag
vim-illuminate
goto-preview
Trouble
Codeium If you think these are a lot, then yes they are but this gives me the most basic neovim setup that I need. You can add more plugins and make it even more feature rich, and it's completely fine but I like my setup to be fast and reliable, so the fewer plugins I have, the less I need to worry about them going out of date xD

Conclusion

With that, we come to the end of this long blog. I hope this was informative (except foy my backstory) and you learnt somethigng from it. If you reached this far, then I'd like to thank you for your time and patience and I'd like it if you could drop a comment on anything related to the blog or my writing style or some detail that I covered or something I missed out on. I am looking to actively give back to this community that gave me so many resources to learn and upskill and I'd like to get some suggestions on that as well.
See you in the next blog this weekend.

Introducing Wincast: A new way of searching apps in windows (spoiler alert, it's rusty 🤪)

Samriddha Chattopadhyay — Sun, 22 Sep 2024 15:48:41 +0000

Hey, fellow developers!
Today, I give you wincast, a CLI tool I have been building for some days to search up apps, files and folders on windows.

The Problem

You see, I have been a linux user in the past and I still love linux for how customizable it is (yeah I'm talking about that sexy tiling wind0w manager setup with bspwm and polybar and using rofi as the run launcher. Those were fun days). However, there's a bigger problem, which is, gaming. Linux gaming is not as great as windows (it has gotten a lot better, but it's still not there). So, I switched to windows some time back and I have been regretting this choice since.

"But Samy, you can easily dual boot your PC and get both running on the same system" is that people would say, but that's not the point. I like to sometimes game while my code is compiling or some heavy process is running (or when I am bored while working lol), and if I dual boot, I need to turn that off which defeats the point. Anyway, that's enough for a rant.

So after switching to windows, I was left with only the windows search feature which is a piece of shit (just stating facts), unless I got to know about Powertoys Run. I gave it a try, but I always felt something was missing in it (unlike my past experiences with dmenu and rofi). Recently, I came across Flow Launcher, and I have been using it for some time now and yet, I am not satistied enough (also, I just wanted to build a similar tool). Also, I have recently started learning rust and have been loving it (much more than javascript at least). So, I decided to build a tool for doing the same thing, but in rust.

What is Wincast ?

Wincast is a search tool built primarily for windows. This is intended to work similar to apple's spotlight, with similar features. Here's a small demo:

Yeah. As of now, it works in the command line, and yes it's also open source, and I intend to maintain it properly. So if someone is interested, it will be my pleasure if you can contribute (mainly with issues and features). PRs are also accepted xD.

Why should you use it ?

Well, here's the hard truth. As of now, it can only accomplish basic stuff. You can search up apps, open your search query on google, youtube or youtube music (more media app recommendations are appreciated). I am also working on searching media, files and folders and show them in separate tabs. Native youtube search is also something I want to build into this. So, overall, I want this to be the go to place for any developer (personally, I am going to keep this open in a secondary monitor all day lol).

If you're a developer and you resonate with this idea and have some suggestions, please feel free to drop them in the comments.

That's it ?

Well, yes. That's it. I don't want to project this as some state of art work or the best search tool out there, but I want to build this into something similar. Any kind of contribution, advice and support is deeply appreciated.

Here's the github repo if anyone is interested to take a look: wincast

Thank you and I hope you cast your doubts away and use wincast (lol).

Where art thou data ?

Samriddha Chattopadhyay — Sat, 08 Oct 2022 08:42:13 +0000

Today, data is the second most important thing (next to our life, that is) in our lives.

And this is true even in programming.

The way you store your data makes all the difference in how your program executes and how it simplifies everything for you.

Data structures are some abstract things that let you store data and that too, in different formats.

Sometimes, you want to make a shopping list where things come in order whereas, sometimes, you just want to put things into a bag and get them at once without going through all of them. Sometimes, you want your things to be sorted in a specific way without you having to do it yourself. All these can be achieved with the right data structure and with the right application of them.

However, there is one thing that every newbie programmer wonders. What is that one data structure that works everywhere. Or to put it in simpler terms, which is the best data structure ?

You might’ve seen or heard about things called Hash-Map and how it can be used to solve any problem. So is it the best data structure that we can use everywhere ?

Let’s see if it is that way or if there is something that is even better.

Arrays

Arrays are the very first data structure that anyone learns while they learn how to code. Put simply, arrays are continuous chunks of indexed data in the memory. Think of it simply as a shopping list where you have numbered everything and you go through these one at a time.

Arrays are something similar conceptually, however, the only difference is that, their indexing start from 0 (well, that is how the programming community works lol).

So consider the following example:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]

Here, the numbers are indexed as follows:

0 -> 1
1 -> 2
2 -> 3
3 -> 4
4 -> 5
5 -> 6
6 -> 7
7 -> 8
8 -> 9
9 -> 0

Here the indexing starts from 0 and goes up to 9 as there are 10 elements in this array.

Also, it is stored in the memory in a similar fashion.

If the memory address of the first element is 2000, and the size of an integer is 4 bytes (in C++), then, the memory address of the 3rd, 5th and the last elements are 2008, 2016 and 2036 respectively.

So arrays can make up for that shopping list of yours pretty easily. However, there is an inherent problem. Let’s say I ask you if 10 is present in this array. You need to go through each element before telling me that it is not. Hence, we say that searching time for an array is O(n) where n is the length of the array. Following are some time complexities for related to arrays:

Adding element: O(1)
Deleting element: O(1)
Searching element: O(n) (Can be extended to O(logn) using algorithms like binary search)
Finding maximum: O(n)
Finding minimum: O(n)

Stacks

Have you ever seen plates being washed ? That is exactly what a stack is.

In a stack, elements are pushed at the top and popped out from the top as well.

That means, you can only see the top most element of the stack and nothing else. Think of this like a pile of coins placed symmetrically. You can see the top coin and only if you remove it, can you get to see the coin below it. A stack is exactly similar to that.

Following are some time complexities for related to stacks:

Adding element: O(1) (only at the top)
Deleting element: O(1) (only from the top)
Searching element: Not possible
Finding maximum: Not possible generally
Finding minimum: Not possible generally
Peek top most element: O(1)

Maximum and minimum elements can be found out in some cases, if the stack is properly arranged, i.e, if elements are always sorted in one way. This can be done by creating monotonic stacks, however, the add operation in these can go up to O(n) time.

Queues

Queues are basically similar to the ones we see in day to day life (pun intended).

Really, a queue works exactly same as a ticket counter line (also called a queue). Elements are pushed from the back and popped from the front. Hence, you cannot really search in a queue, however, adding and deleting can be done pretty fast.

A stack is exactly similar to that.

Following are some time complexities for related to queues:

Adding element: O(1) (only at the front)
Deleting element: O(1) (only from the back)
Searching element: Not possible
Finding maximum: Not possible
Finding minimum: Not possible
Peek front element: O(1)
Peek back element: O(1)

There are queues called dequeue (double ended queues) which can add and remove from any side.

Priority Queues or Heaps

A priority queue is similar to queue, as elements can be removed only to the front. However, They work based on a certain priority. Think of it this way:

You are standing in a ticket counter line at the back. Now, an old man comes up and stands after you. You feel bad, so you let him go before you (so does all other people in the line). So, he goes towards the front unless another old guy is already there in front of him. So, you are prioritising him over your time. This is exactly how a priority queue works.

While pushing to a priority queue, the elements are rearranged so as to maintain the priority order. So, essentially, elements are pushed at the back, but then things are rearranged, so, pushing elements take O(logn) time, where n is the number of elements in the queue.

There are generally two types of priority queues:

Min Heaps - Minimum element at the top
Max Heaps - Minimum element at the top

Following are some time complexities for related to priority queues:

Adding element: O(logn)
Deleting element: O(1)
Searching element: Not possible
Finding maximum: O(1) (for max heap)
Finding minimum: O(1) (for min heap)
Peek front element: O(1)
Peek back element: O(1)

Hashmaps and Hashsets

Here comes the most popular data structure of all: Hashmap.

You might’ve heard this phrase from your seniors: “Whenever you are stuck, throw a hashmap at the problem.”

Well, that is not totally wrong. Hashmaps can greatly optimise time complexity of a problem by using some space. Essentially, you are storing the data in an indexed format, where the index is not an integer, but any other data type (unlike arrays). These are named differently in different languages (maps in C++, hashmaps in java, dictionary in python, etc.), but they essentially, they do the same thing. Hash data to something so that it can be assessed easily afterwards.

There are a lot of ways to hash data, and we won’t be discussing those as the topic is huge in itself. If you are interested to know more about how data is hashed in a hashmap, do put it in the comments, and I’d be more than happy to write up about the same.

Hashsets work in the same way, except that, they have keys only instead of a key-value pair.

Following are some time complexities for related to priority hashmaps and hashsets:

Adding element: O(1)
Deleting element: O(1)
Searching element: O(1)
Finding maximum: Not possible generally
Finding minimum: Not possible generally

Finding maximum and minimum are not possible generally, as hashmaps and hashsets cannot be iterated.

However, some languages (like C++) make this possible by implementing them using arrays.

These are some of the basic data structures that are used in day to day life by any programmer. Thanks for reading it till the end and stay tuned for more amazing content like this one!

How to build your own google search

Samriddha Chattopadhyay — Mon, 18 Jul 2022 20:22:34 +0000

Got interested ? Yeah we will build an algorithm to make our own search engine.

There are a couple of steps in doing so. First, we do some web scraping and index the data we obtain to store it in the database in a meaningful format. We won’t be doing these here, though. What we will do is to search what you want from these indexed data. So let’s get started.

Problem at hand

You suddenly get an urge to build your own google search. Your friend is helping you out in the initial stuff, but he is really dumb when it comes to algorithms. So you need to build an algorithm that can search for a word efficiently from a given list of strings.

We shall make some assumptions here. Firstly, we will assume that the strings will be unique and will be comprising of single word each. Also, the characters of the strings will be from a-z.

NOTE: These assumptions are just to deduce the algorithm. The algorithm that will be building can handle all characters and also multi-word strings. These assumptions will just let us deduce the algorithm easily and then we can generalise our algorithm by some minute modifications.

Intuition

Let’s first try to think what we can do in this case.

One simple option is to hash each string to a value and use the string as and when it is called. However, there are two problems in this method. We need to store the same part of the string twice. For example, consider these two cases:

[ "app", "apple" ]

Here, it is evident that storing app and apple separately will cause us to use more memory as compared to storing one of them. So the question is can we do better ?

Well, the answer is yes we can, however, there are some trade-offs for this method.

We can use something called a trie.

Tries are efficient information retrieval data structures. We can use these to retrieve data more efficiently than arrays (they don’t have that O(1) time complexity, though).

And guess what ?

Tries take lesser memory than hashmaps.

Solution

Now, let’s implement our trie. Before we start, though, I’d like to give you a basic structure of a TrieNode (basically a node or vertex in the trie).

struct Node{
    char val;
    Node* next;
};

class TrieNode{
    unordered_map<char, Node*> children;
    bool endOfWord;
public:
    TrieNode() {
        for(char c='a'; c<='z'; c++)
            children[c] = NULL;
        endOfWord = false;
    }
};

This is what a basic trie node looks like. Here, I took the information in each node as a character. It can be anything ranging from a character to complex objects. The children map will have all the characters in range (here, a-z) as keys and the node for that character’s data as the value.

So once we have that in place, now is the time we construct our trie.

First step is to understand how it will work. Basically, we will have a starting node (let’s call this a wildcard character). This node will be an empty TrieNode with null pointers as all it’s children and endOfWord as false.

Now, we keep on adding the strings in our trie. For each string, we add one character to the trie’s children with the corresponding node’s value. We repeat unless the string has ended. Once it has, we mark the endOfWord of that TrieNode as true.

void insert(string word) {
    Node* curr = root;
    for(char c : word) {
        if(curr->children.find(c) == curr->children.end()) {
            curr->children[c] = new Node();
            curr = curr->children[c];
        }
    }
    curr->endOfWord = true;
}

We do this for each string we get and at the end, we will have our trie completed.

Good, now we have our data in place. But how do we query it ?

If you understood it till now, you should’ve already guessed it. However, if you are dumb (like me), then hang on. Let’s discuss this through.

So querying it is quite simple. For the query word, we perform a similar logic and search character by character. If at any moment we see that a character that you need to complete the current word is not present, we can conclude that the word is not present in the trie and need to go further. (Case I)

In case you find the whole word, however, the last character you visited to doesn’t have endOfWord as true, then again, the word you are searching for doesn’t exist. In all other cases, you can find the word you are searching for. (Case II)

Consider the following example for case I:

  *
 / \
a   b
|   |
p   e
|   |
p   a
|   |
l   r
| 
e

So we have “apple” and “bear” in our trie. Now, say, you search for “boat”.

You see we have a ‘b’ but, hold on we do not have an o after b. Hence, “boat” doesn’t exist in our trie. Now, say you add “boat” to it. It’d look something like this:

  *
 / \
a   b
|  / \
p o   e
| |   |  
p a   a
| |   |  
l t   r
| 
e

Now, if you search for “boat”, you can see you will get all the characters, and ‘t’ will also have endOfWord as true.

Consider the following example for case I:

  *
 / \
a   b
|  / \
p o   e
| |   |  
p a   a
| |   |  
l t   r
| 
e

Now, say you search for “app”. You notice, ‘a’ is present, then ‘p’ is also present and the next ‘p’ is also present. However, this ‘p’ doesn’t have endOfWord set to true. Hence, “app” isn’t present in our trie. Now, if you add “app” to our trie, it’d look something like this.

  *
 / \
a   b
|  / \
p o   e
| |   |  
p a   a
| |   |  
l t   r
| 
e

As you can see, we marked p with endOfWord true as well in the above case.

Here is how you implement this in code:

bool search(string word) {
    Node* curr = root;
    for(char c : word) {
    if(curr->children.find(c) == curr->children.end()) {
      return false;
    }
    curr = curr->children[c];
    }

    return curr->endOfWord;
}

Also, let’s discuss a bonus thing you can do with tries. You can even predict the words (or characters in this case) that the user is going to type next. It works on the same logic as above with a slight modification.

Here, we just say if the word starts with the prefix string. All you need to do to make this into an autosuggestion feature is to put the words into an array and returning it in place of true (also, change the function return type lol).

bool startsWith(string prefix) {
    Node* curr = root;

    for(char c : prefix) {
        if(curr->children.find(c) == curr->children.end()) {
            return false;
        }
        curr = curr->children[c];
    }

    return true;
}

With that, my lecture is over. But you’d ask now, “Wait! You mentioned this is better than hashmaps and started giving a lecture without even asking if I was interested. So is it really more efficient than a hasmap ?”

So let’s try to answer that.

Here, we are traversing through the entire trie and we visit each node in a branch exactly once. So, the time complexity will be O(h) in the worst case, where h is the height of the trie. If you know that the trie has N nodes, then, you can even say it takes O(logN) time (Yay less than linear!!!).

The space needed is almost constant as each node has a fixed number(26 in this case) of children. If the height of tree is h, then, space taken is O(26*h) ~ O(h) which can also be interpreted as O(logN) if the number of nodes are N.

As you can imagine, it’s pretty efficient as compared the the naive way of using a hashmap to store stuff. Sure, we’d get O(1) search time, but we’d have taken a lot of memory and we also would’ve to give up on the autosuggest featue xP.

Well, with that, you’ve successfully planned the algorithm to build the next google search. What are you waiting for ? Go and build it! Don’t keep your friend waiting after he did all that hardwork of doing the initial indexing for you.

Thanks for reading it till the end and stay tuned for more amazing content like this one!

How to build Google Maps

Samriddha Chattopadhyay — Sun, 03 Jul 2022 08:03:49 +0000

Well, for you to visit this page means you are really interested to know how to build your own google maps. However, we aren’t gonna do something that crazy here. We will be building an algorithm, though which will let us find the shortest path between any two locations. So let’s get started.

Problem at hand

You live in an era before google maps was made, so you need to rely on a printed map to get to your destination. However, you know how to code, so you try to build a google map on your own.

What you basically want to do is, you want to create something that tells you the shortest distance you need to travel from your current location to your destination, given all the different locations in the map.

Intuition

Let’s first try to analyse our options here. First, we can try out each of the paths and figure out which would give you the minimum distance. However, this is very inefficient. Consider you have N locations on the map. You will have n(n-1) paths connecting each of the two locations and to find the minimum by considering each combination of these n(n-1) paths is far too inefficient.

Now, let’s try to see this from a different perspective. You consider each location as a vertex and the path joining any two locations, an edge between the vertices. You end up constructing a graph in this way. Now, all you need to do is find the shortest distance of the path that will let you reach the destination. Does this sound familiar to some algorithm you already know ? If not, then let’s see how we achieve this. Just FYI, this is called Dijkstra’s Algorithm (yeah I didn’t make it so no credits to me for the algorithm as much as I wanted to take it all for myself)

Solution

Here, we perform an algorithm similar to bfs (if you don’t know what that is, I’d highly recommend you to check it out from here). We take a priority queue (min heap) instead of a queue.

We maintain a distances array which stores the minimum distances of all nodes from the source. Initially, we make the distance of source as 0 and insert a pair of 0 and source node in the queue. Now, we iterate until the priority queue is empty and in each iteration, we store the min between the distance of the child node and the sum of distanced of the parent and edge weight of the child in the distance of the child. Once this is done, we add the pair of distance and child node to the priority queue if the sum is more than the previous distance.

Once the loop is over, we will get all the minimum distances in the distance array.

Now that you’ve thought of this algorithm, the next question that would come to you mind is, how efficient is this ? So let’s try to answer that.

Here, we are traversing through the entire graph and we visit each node exactly once. So, the time complexity will be O(N+E)

Also, we are using a priority queue, so the space complexity is O(N)

As you can imagine, it’s pretty efficient as compared the the naive way that came you us at the beginning (i.e., to check for each combination of the path and compute the minimum distance).

Well, with that, you’ve successfully planned the algorithm to build the google maps. What are you waiting for ? Go and build it so that u can give it to your friends and amaze them with your genuis.

Thanks for reading it till the end and stay tuned for more amazing content like this one!

How to walk a graph

Samriddha Chattopadhyay — Thu, 30 Jun 2022 15:47:47 +0000

Walking a graph is as simple as visiting each node and doing some operations for it. There are mainly two ways of walking (or traversing) a graph:

BFS (Breadth First Search)
DFS (Depth First Search)

Alright! Let’s do it. Let us take an example.

Your mom has given you a grocery list and the exact shops you need to buy them from.

You are a nerd (like me) and do not have good knowledge of the neighbourhood (or maybe you moved in recently lol). So you take a look at your google maps and figure out the exact locations of the stores you need to visit.

However, you are a nerd, remember ? You wanna know how many blocks of stores you have to visit. For example, if in the following list, 1s represent the location of the stores you need to visit, then there are 2 blocks that you want to visit.

1 1 1 1 0 0 0
1 1 1 0 0 0 0
1 1 0 0 0 1 1
1 1 0 0 0 1 1

Now, how do you calculate this ?

In real life, it’s easy to calculate as we will just draw a boundary across the ones and say there are two blocks. But how do you do this in code ? Let’s see that down below.

BFS (Breadth First Search)

So this is one approach that you can take. Here, you visit each element (node) and then, plan where you want to visit next. So, we start from (0, 0) and then we want to visit (0, 1) and (1, 0). Notice that both of these are having ones, hence, we can visit them. Next, we visit (0, 1) and we plan on visiting the adjacent elements, which are 1, i.e., (0, 2) and (1, 1). Notice how we are not going for (0, 0) again even though it’s adjacent as we’ve already visited it (also, nerds are lazy so).

So we continue to visit the elements this way, in layers and we visit each element exactly once.

Now, let’s convert this to code.

We maintain a queue for each block (component) we visit. We also maintain a visited array where we can mark the elements we’ve already visited as true.

Initially, when we are visiting a block (component), we add the first node (or the root node for the component) into the queue. Also, we need to keep a note that we have already visited this element (node), so, we mark the index of this node in the visited array as true.

Then we start traversing the block(component) and for each iteration, we first pop the first element in the queue and push the adjacent elements (nodes) of this element into the queue.

Once we are done, we can end the function call and go for the next block(component).

Now, time for some nerdy content. Let’s talk about the time and space complexity of this algorithm.

Time Complexity: O(N+E)
Space Complexity: O(N)
N = Number of nodes in the graph
E = Number of edges in the graph

With that, you’ve successfully calculated the number of blocks you need to go to. Make sure you go back home safely along with the groceries or your mom will be mad and send you back for shopping.

DFS (Depth First Search)

This is approach that you can take. Here, you visit each element (node) and then, go to the immediate next element (node) that you see. So if you visit (0, 0), you go to (0, 1) next, then (0, 2) and so on until you see an element with no store (node with 0 value).

So we continue to visit the elements this way, in order and we visit each element exactly once.

Now, let’s convert this to code.

We can make a recursive function that takes in the current element (node) and marks it as visited (same way as in BFS, but without a queue). Then, it makes a recursive call to the same function with the immediate neighbours of this element (node) only if it has not been visited already.

Another way to do this is using a stack that can effectively simulate the recursion call stack. However, this is more efficient sometimes (when the number of nodes are more).

Now, it’s again time for some nerdy content. Let’s talk about the time and space complexity of this algorithm as well.

Time Complexity: O(N+E)
Space Complexity: O(N)
N = Number of nodes in the graph a
E = Number of edges in the graph

With that, you’ve successfully calculated the number of blocks you need to go to again. Make sure that this time, you go back home safely along with the groceries or your mom will be really mad and maybe cut you computer power ot wifi line.

With that said, Thanks for reading it till the end! If you want some more of these graph blogs, stay tuned as I’m gonna write a lot of em from now on.