DEV Community: Grzegorz Kućmierz

Random normal distribution

Grzegorz Kućmierz — Thu, 27 Jul 2023 05:19:23 +0000

JavaScript by default don't have randomness with normal distribution.

We can use for that pretty simple Box-Muller implementation that I showed below.

// Box-Muller implementation:
const randNormal = (mean, sigma) => {
  const y1 = Math.random();
  const y2 = Math.random();
  return (mean + sigma *
    Math.cos(2 * Math.PI * y2) *
    Math.sqrt(-2 * Math.log(y1))
  );
};

It can be useful to solve this codewars kata.

You can see example use of this code here.

Achilles numbers generation

Grzegorz Kućmierz — Wed, 26 Jul 2023 07:34:34 +0000

Today I solved "Slay Achilles!" codewars task.

Achilles numbers can be found on on-line encyclopedia of integer sequences A052486

https://www.codewars.com/kata/5708c90cd531cdfecf00147c/javascript

Here is my code that is checking if number is Achilles one, and prints 10k first integers with Achilles check.

function factors(n) {
  let max = Math.floor(Math.sqrt(n));
  let res = [];
  for (let i = 2; i <= max; ++i) {
    if (n % i === 0) {
      res.push(i);
      n /= i;
      max = Math.floor(Math.sqrt(n));
      i = (Math.min(...res) || 2) - 1;
    }
  }
  res.push(n);
  return res;
}

const groupToMap = (array, cb = el => el) => {
  const map = new Map();
  array.map((el, i) => {
    const key = cb(el, i);
    if (map.has(key)) {
      map.get(key).push(el);
    } else {
      map.set(key, [el]);
    }
  });
  return map;
};

function gcd(a, b) {
  if (a < 0) a = -a;
  if (b < 0) b = -b;
  if (b > a) {
    [a, b] = [b, a];
  }
  while (1) {
    if (b == 0) return a;
    a %= b;
    if (a == 0) return b;
    b %= a;
  }
}

const isAchilles = n => {
  const f = factors(n);
  const grouped = groupToMap(f);
  const values = [...grouped.values()];
  const gcdLen = values.map(arr => arr.length).reduce(gcd);
  if (gcdLen !== 1) return false;
  return values.length > 1 && values.every(arr => arr.length > 1);
};

for (let i = 0; i < 1e4; ++i) {
  console.log(i, isAchilles(i));
}

In this code I used few already created functions:

factors - breaks integer number into factors
groupToMap - group array elements (MDN experimental feature yet)
gcd - calculates Greatest Common Divisor

Here you can play with that code:

Instacode playground

Binary search

Grzegorz Kućmierz — Wed, 26 Apr 2023 16:04:37 +0000

Binary search is commonly used technique in computer science.

Using this technique you can find element in sorted array in O(log n) time complexity.

Below is my implementation of this algorithm.

const binarySearchArr = (arr, target) => {
  let [a, b] = [0, arr.length];
  let lm;
  while (b - a > 0) {
    const mid = (a + b) / 2 | 0;
    const val = arr[mid];
    if (target < val) {
      b = mid;
    } else if (val < target) {
      a = mid;
    } else {
      return mid;
    }
    if (lm === mid) break;
    lm = mid;
  }
  return -1;
};

With this function we can very easily solve Search a 2D Matrix task on LeetCode.

Only thing we need yet is converting matrix to array or representing it as array which I implemented using Proxy.

const matrixAsArray = matrix => {
  const [h, w] = [matrix.length, matrix[0].length];
  return new Proxy([], {
    get(target, prop, receiver) {
      if (prop === 'length') return h * w;
      const idx = +prop;
      const col = idx % w;
      const row = (idx - col) / w;
      return matrix[row][col];
    }
  });
};

With these two functions solving this task is now trivial as you can see below.

const searchMatrix = (matrix, target) => {
  const arr = matrixAsArray(matrix);
  return binarySearchArr(arr, target) !== -1;
};

You can play with this code on Instacode.app

I also added both of these functions binarySearchArr and matrixAsArray in my JavaScript Utils collection.

Heap implementation

Grzegorz Kućmierz — Mon, 24 Apr 2023 13:53:03 +0000

Heap is a very useful data structure for solving many programming problems.

One of the problem I found is merge k sorted lists on leetcode.

In this problem we have possible many lists which are sorted and we need to return 1 sorted list, so the most obvious attempt will be keeping always first element of every list in some data structure that allows to very efficient find max or min value (min in this case).

For heap taking min or max is O(1) complexity
And adding new element is O(log n)

This is efficient enough to build O(n log m) algorithm, where n is a collection size of all elements from all lists together and m is number of lists.

Here is my very simple implementation of heap.

const Heap = (valFn = n => n) => {
  const arr = [-1];

  const up = idx => {
    while (idx > 1) {
      const ni = idx / 2 | 0;
      if (valFn(arr[idx]) < valFn(arr[ni])) {
        [arr[idx], arr[ni]] = [arr[ni], arr[idx]];
      }
      idx = ni;
    }
    return idx;
  };

  return {
    add: el => up(arr.push(el) - 1),
    take: () => {
      const len = arr.length;
      if (len <= 1) return [][0];
      let idx = 1;
      const res = arr[idx];
      while (idx < len) {
        const ia = idx * 2;
        const ib = idx * 2 + 1;
        if (ia >= len) break;
        if (ib >= len || valFn(arr[ia]) < valFn(arr[ib])) {
          arr[idx] = arr[ia];
          idx = ia;
        } else {
          arr[idx] = arr[ib];
          idx = ib;
        }
      }
      if (idx === arr.length - 1) {
        arr.pop();
      } else {
        arr[idx] = arr.pop();
        up(idx);
      }
      return res;
    },
    size: () => arr.length - 1,
    data: () => arr.slice(1),
  };
};

Be noticed that constructor of this heap is expecting getter function for element value.
Thanks to that we can keep in our data structure more information.
For this problem we will need to keep index number of list so we can take next element from same list if we removing it from heap.

Here is my very simple implementation of this problem using arrays instead lists and using my heap implementation.

const mergeKLists = lists => {
  const heap = Heap(a => a[0]);
  lists.map((list, i) => {
    const el = list.shift();
    heap.add([el, i]);
  });
  const res = [];
  while (1) {
    const next = heap.take();
    if (next[0] === [][0]) break;
    const [val, i] = next;
    heap.add([lists[i].shift(), i]);
    res.push(val);
  }
  return res;
};

const lists = [[1,4,5],[1,3,4],[2,6]];

mergeKLists(lists);

You can play with this code on Instacode.app

Changing array to list is very trivial thing.

I also added this heap to my utils collection for future tasks.

Be noticed that I implemented min heap here actually.
In most cases it is good enough because even if you need max heap instead and you don't care about handling same elements like 1 === 1 you can just pass invert value getter function like this below to accomplish that.

const heap = Heap(n => Number.MAX_SAFE_INTEGER - n);

What can be max const name in JavaScript?

Grzegorz Kućmierz — Wed, 14 Oct 2020 01:06:54 +0000

This post is about maximum length of variable name in JavaScript.

The answer is:

2 ** 29 - 63

Pretty long variable name, huh?

It is more than 500 megabytes!

I don't know why is that exactly, but I precisely checked this using bisection algorithm.

Natural Search Algorithm

Grzegorz Kućmierz ・ Sep 29 '20

#javascript #algorithms #bisection #search

1
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
402653184
469762048
503316480
520093696
528482304
532676608
534773760
535822336
536346624
536608768
536739840
536805376
536838144
536854528
536862720
536866816
536868864
536869888
536870400
536870656
536870784
536870848
536870880
536870864
536870856
536870852
536870850
536870849
'maxConstName', 536870849

Here is code, that I wrote.

const naturalSearch = (cond, retFirstTrue = true) => {
  let min = 1;
  let max = 1;
  while(1) {
    const stop = cond(max);
    if (stop) break;
    min = max;
    max *= 2;
  }
  let mid;
  while (1) {
    mid = Math.floor((min + max) / 2);
    const stop = cond(mid);
    if (stop) {
      max = mid;
    } else {
      min = mid;
    }
    const diff = max - min;
    if (max - min <= 1) {
      return retFirstTrue ? max : min;
    }
  }
};

const checkConstName = n => {
  console.log(n);
  try {
    const name = 'a'.repeat(n);
    new Function(`const ${name} = 5;`)();
    return false;
  } catch (e) {
    return true;
  }
  return false;
};

const maxConstName = naturalSearch(checkConstName, false);

console.log('maxConstName', maxConstName);

Play sound in JavaScript

Grzegorz Kućmierz — Mon, 12 Oct 2020 13:27:10 +0000

Very simple function that plays sine wave in browser environment.

const play = (frequency = 300, duration = 1e3) => {
  const context = new AudioContext();
  const gainNode = context.createGain();
  const oscillator = context.createOscillator();
  oscillator.frequency.value = frequency;
  oscillator.connect(gainNode);
  gainNode.connect(context.destination);
  oscillator.start(0);
  setTimeout(() => oscillator.stop(), duration);
};

Just run play() or provide sine wave frequency or duration

play(8000, 1e3);

Maximum Product of Three Numbers

Grzegorz Kućmierz — Mon, 05 Oct 2020 05:20:59 +0000

Platforms to practice

Leetcode problem

Implementation

const maxProduct = arr => {
  if (arr.length < 3) return false;
  const max3 = [-Infinity, -Infinity, -Infinity];
  const min2 = [Infinity, Infinity];

  for (let i = 0; i < arr.length; ++i) {
    const n = arr[i];
    if (n > max3[0]) {
      max3[0] = n;
      max3.sort((a, b) => a - b);
    }
    if (n < min2[0]) {
      min2[0] = n;
      min2.sort((a, b) => b - a);
    }
  }
  return max3[2] * Math.max(min2[0] * min2[1], max3[0] * max3[1]);
};

Complexity

Time complexity: O(n)
Space complexity: O(1)

Explanation

Loop through array, while keeping 3 max elements and 2 min elements.
We want 2 min elements because min element can have bigger absolute value. When we calculating product always 2 negative numbers give 1 positive, so we need only 2 min to check if their product is not bigger that 2 smaller numbers of our 3 max.

My github reference

https://github.com/gkucmierz/algorithms/blob/master/problems/maximum_product_of_three_numbers.js

Instacode playground

instacode.app

Natural Search Algorithm

Grzegorz Kućmierz — Tue, 29 Sep 2020 16:10:00 +0000

This post is about function I wrote while solving LeetCode task.

Complexity of naive solution for this task is O(w²) where w is weights size.
But it can be done better with little improvement.
Instead checking every possible day from 1 to weights.length we can implement natural search algorithm and finish this task with O(w * log(w)) complexity.

Here is code I wrote:
https://github.com/gkucmierz/algorithms/blob/master/js/natural_search.js

Using this function is very simple.
Whenever we have Signum function with unknown bias.

Like this:

const fn = n => Math.sign(n - 345) >= 0;

345 here is random unknown number.
We can easily find it using simple code:

const fn = n => Math.sign(n - 345) >= 0;

console.log(naturalSearch(fn));

Second parameter for naturalSearch function which is retFirstTrue indicates if function should return first natural number when condition is returning true value, or last natural number when it is still false.

Lets check if algorithm really is calling function optimal number of times:

const fn = n => {
  const res = n >= 345;
  console.log('checking number:', n, 'result:', res);
  return res;
};

console.log(naturalSearch(fn));

Than we have this result:

'checking number:', 1, 'result:', false
'checking number:', 2, 'result:', false
'checking number:', 4, 'result:', false
'checking number:', 8, 'result:', false
'checking number:', 16, 'result:', false
'checking number:', 32, 'result:', false
'checking number:', 64, 'result:', false
'checking number:', 128, 'result:', false
'checking number:', 256, 'result:', false
'checking number:', 512, 'result:', true
'checking number:', 384, 'result:', true
'checking number:', 320, 'result:', false
'checking number:', 352, 'result:', true
'checking number:', 336, 'result:', false
'checking number:', 344, 'result:', false
'checking number:', 348, 'result:', true
'checking number:', 346, 'result:', true
'checking number:', 345, 'result:', true
345

As we can see in first phase algorithm is trying to find true value by multiplying number by 2, then when it find, it can find exact point using bisection technique.

Simplifying Linked-List interview tasks

Grzegorz Kućmierz — Mon, 28 Sep 2020 16:00:33 +0000

While I was solving one of leetcode task I came upon idea that there is many similar tasks in many places. All of them are very similar, but they require much code writing and precise testing.

So to simplify solving further tasks I created JavaScript code, that implements popular methods on linked lists and accepts any type of node implementation.

I have put it on my github

Now with this abstraction solving remove-linked-list-elements task is very easy, even monkey can do that!

Complete solution

// [put LinkedList code here]

const removeElements = (head, val) => {
  const ll = LinkedList();
  return ll.removeItems(head, v => v === val);
};

First

Create linkedList instance by passing function that is creating node list

/*
 * function ListNode(val = 0, next = null) {
 *   return { val, next };
 * }
 */

const linkedList = LinkedList((value, next) => {
  return new ListNode(value, next);
});

In my case I don't need to pass this function because it is by default exactly matching to LeetCode Linked Node constructor.

Second

Just call removeItems method and return head of this list.

return linkedList.removeItems(head, v => v === val);

Be aware, that in this LeetCode task you can't just convert existing list to array, filter it, and convert back to list. This task also checks references, so if you try to submit that kind of code it should not pass.

const removeElements = (head, val) => {
    const ll = LinkedList();
    return ll.array2list(
        ll.list2array().filter(v => v === val)
    );
};

Now solving this type of tasks is super easy.

Delete duplicates task

Let's try to solve another task which is deleting duplicates in sorted list

This list is sorted, so any duplicates will be next to each other, so we can write simple code, that is comparing current value to last seen value and update it when it is changed.

const deleteDuplicates = head => {
    let lastVal;
    return LinkedList().removeItems(head, val => {
        if (val === lastVal) return true;
        lastVal = val;
        return false;
    });
};

Very simple code. Writing this complete solution took less than 60 seconds.

Playground

Here you can play with this code a little bit:
instacode.app

How to generate permutations in JavaScript?

Grzegorz Kućmierz — Tue, 22 Sep 2020 21:31:51 +0000

Generating permutations is pretty common problem in many algorithmic problems.

I have already implemented this problem, so you can find it in my github in algorithms repo.

Here you have function that is generating permutations from Set of specified size.
https://github.com/gkucmierz/algorithms/blob/master/js/generate_permutations.js

So if you pass 3 to it you will get this 2d array:

console.log(genPermutations(3));

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

Subarrays are indexed from 0 to 2, so you can very easily adapt it to your code using these indexes.

const map = ['a', 'b', 'c'];

console.log(
  genPermutations(3)
    .map(permutation => {
      return permutation.map(idx => map[idx]).join('')
    })
);

[
  'abc',
  'acb',
  'bac',
  'bca',
  'cab',
  'cba'
]

What is the JavaScript version of sleep()?

Grzegorz Kućmierz — Thu, 17 Sep 2020 20:39:58 +0000

There is no sleep function in JavaScript, but with async/await syntax it is very easy to implement.

If we need to mimic behavior like this written in c code.

#include<stdio.h>

main() {
   printf("Sleeping for 1 second.\n");
   sleep(1);
   return 0;
}

Using async/await syntax it is very simple.

const sleep = (timeout = 1) => new Promise((resolve) => {
  setTimeout(resolve, timeout * 1e3);
});

console.log('before sleep');
await sleep(1);
console.log('after 1 second!');

You can also use milliseconds version.

const sleepMs = (timeout = 1e3) => new Promise((resolve) => {
  setTimeout(resolve, timeout);
});

console.log('before sleep');
await sleep(1000);
console.log('after 1000 milliseconds!');

How to make my git contributions verified?

Grzegorz Kućmierz — Wed, 29 Jul 2020 14:54:42 +0000

Motivation

Github's verified commits may be useful especially, when you are making open source software.

It is warrant that person who is signing commit made it.
Github commits are very easy to change since they are not secured like for example bitcoin's blockchain is.

How To?

If you are on mac first install gpg using homebrew

brew install gpg

...after some ☕️ break

gpg --default-new-key-algo rsa4096 --gen-key

Type name and last name
Type email address 📧
Type password twice

Should generate keys:

pub   rsa4096 2020-07-29 [SC] [wygasa: 2022-07-29]
      688BA86A3C51E5A1350986EFD63EC3228BD83581
uid                      Grzegorz Kucmierz <gkucmierz@gmail.com>

ls  ~/.gnupg
.           S.gpg-agent.extra   pubring.kbx
..          S.gpg-agent.ssh     pubring.kbx~
S.gpg-agent     openpgp-revocs.d    trustdb.gpg
S.gpg-agent.browser private-keys-v1.d

List your keys

gpg --list-secret-keys

Add to Github

Export public key:

gpg --armor --export

My key:

Go to Github's settings:

Copy/Paste key to your Github form under SSH and GPG keys category

Your key should be added now:

Setup local git

Check your key 🔑 id:

gpg --list-secret-keys --keyid-format LONG

sec   rsa4096/D63EC3228BD83581 2020-07-29 [SC] [wygasa: 2022-07-29]
      688BA86A3C51E5A1350986EFD63EC3228BD83581
uid          [   absolutne   ] Grzegorz Kucmierz <gkucmierz@gmail.com>

Add it in git config:

git config --global user.signingkey D63EC3228BD83581

And export GPG_TTY variable in your .profile file

In my case .zshrc

echo 'export GPG_TTY=$(tty)' >> ~/.zshrc

Now you need to add -S flag to your commit

git commit -m "testing verified commit" -S

And your commit should be signed now:

Sign all commits by default

Just change global git config

git config --global commit.gpgSign true