Roman

Ray-casting with Pygame

2023-01-20T01:14:49.664Z

Hi there, in this article I'm going to discuss ray-casting theme and create raycasting algorithm from the scratch with pygame.

You could find following topics:

Theory about ray-casting and when was firstly used.
Implementation with pygame

Drawing map
Ray-casting algorithm implementation on 2D map
3D implementation
Collision detection
Displating FPS

Perfomance considerations
Resources

Theory about ray-casting

Raycasting is a rendering technique to create a 3D perspective in a 2D map. People came up to the idea of using raycasting in that time, when computers were way slow (early 90-s) to run a 3D engines in a realtime. The most famouse game, which uses raycasting is Wolfenstein 3D, released back in 1992. The basic idea behind raycasting is to trace rays from the 'eye' and find the closest object blocking the path of that ray. We need try to increase the length of a ray at each step of the loop and if ray does hit the wall, then ray ends at this point. This processing should be done with each ray, it could be 30 or 300, depends on needs.

Example with 30 rays and pi/3 FOV

More theory

As you could notice in ray-casting algorithm we need to use FOV(filed of view) for further simulating 3D. FOV determines where player's visible range begins and ends. Usually in games FOV is equal to 60% or pi/3. You could change FOV value and have a look at results.

Example with 30 rays and pi/6 FOV

The process of generating rays in FOV range is not hard at all. There are just a few formulas behind it.

The angle of the first ray will determined in the next way:

starting_angle = player_angle - FOV / 2

And formula for finding distance between two angles:

delta_angle = FOV / number_of_rays

Circle with angles labels

Let's substitute the values in our first quation. Player_angle is pi and FOV / 2 is ((pi/3)/2). Starting_angle equal to (5pi)/6 which is right in the upper left quadrant. If you have a look at the first screenshot, you could notice, that (5pi)/6 is exact dot where FOV starts.

I think for delta_angle no explanations needed, it's really simple.

Drawing map

Now I want to provide code that draws map, player, FOV and we'll be back again to a few formulas to compute points of intersection with walls.

import pygame
import sys
import math

#global constants
SCREEN_HEIGHT = 480
SCREEN_WIDTH = SCREEN_HEIGHT * 2
MAP_SIZE = 8
TILE_SIZE = int((SCREEN_WIDTH / 2) / MAP_SIZE)
FOV = math.pi / 3
HALF_FOV = FOV / 2
CASTED_RAYS = 30

#global variables
player_x = (SCREEN_WIDTH / 2) / 2
player_y = (SCREEN_WIDTH / 2) / 2
player_angle = math.pi

MAP = ('########'
       '# #    #'    
       '# #  ###'    
       '#      #'   
       '##     #'   
       '#  ### #'   
       '#   #  #'  
       '########')

#game window
pygamepygame.init()
win = pygame.display.set_mode((SCREEN_WIDTH, SCREEN_HEIGHT))
pygame.display.set_caption('Ray-casting')
clock = pygame.time.Clock()

#game loop
while True:    
    for event in pygame.event.get():        
        if event.type == pygame.QUIT:            
            pygame.quit()
            sys.exit(0)
    
    draw_map()
    
    #update display    
    pygame.display.flip()
    
    #set FPS    
    clock.tick(30)

I defined global constants, variables, map and wrote minimum framework for creating a window in pygame. Let's dive into draw_map function

The idea behind creating map is simple as hell. We need to iterate over two-dimensional array and compute square index, then create tiles with correspoding color (wall or not).

def draw_map():    
    #colors
    light_grey = (191, 191, 191)
    dark_grey = (65, 65, 65)
    
    #iterate over map    
    for i in range(MAP_SIZE):
        for j in range(MAP_SIZE):            
            #calculate square index            
            square = i * MAP_SIZE + j
            
            #draw map            
            pygame.draw.rect(win, 
                light_grey if MAP[square] == '#' else dark_grey,                
                (j * TILE_SIZE, i * TILE_SIZE, TILE_SIZE - 1, TILE_SIZE - 1))

The reason why I increase 1 from TILE_SIZE is because it just looks better, we got nice-looking grid on the map.

Map without stripes

Map with stripes

Map is ready, now need to add player. This code is continuation of draw_map function.

#draw player    
pygame.draw.circle(win, (162, 0, 255), (int(player_x), int(player_y)), 12)

Ray-casting implementation

Now the most interesting part: implementation of ray-casting algorithm

The idea is to firstly get target x and target y coorditanes and then to convert that coordinates to column and row. Then, with column and row, get square index and with square index it's really simple to check if it's a wall or nothing (do we need to cast the ray or not). Of course the set of this operations should be done with each ray.

for ray in range(CASTED_RAYS):        
    for depth in range(MAX_DEPTH):            
        #get ray target coordinates            
        target_x = player_x - math.sin(start_angle) * depth
        target_y = player_y +  math.cos(start_angle) * depth
        
        #convert target x, y coordinates to map col, row
        col = int(target_x / TILE_SIZE)           
        row = int(target_y / TILE_SIZE)  
        
        #calculate map square index            
        square = row * MAP_SIZE + col                        
        
        #print(square)
        if MAP[square] == '#':                
            pygame.draw.rect(win, (195, 137, 38), 
                            (col * TILE_SIZE, row * TILE_SIZE, 
                            TILE_SIZE - 1, TILE_SIZE - 1))                                
            
            #draw casted ray                
            pygame.draw.line(win, (233, 166, 49), (player_x, player_y), (target_x, target_y))                                
            break
        
        #increment angle by step        
        start_angle += STEP_ANGLE

Movement of the player and updating background. With using cos and sin functions we can move player in x and y directions. Feel free to experement with signs of numbers or math functions to observe how it all works.

#update background    
pygame.draw.rect(win, (0, 0, 0), (0, 0, SCREEN_HEIGHT, SCREEN_HEIGHT))

#get user input    
keys = pygame.key.get_pressed()

#handle user input    
if keys[pygame.K_LEFT]:        
    #working with radians, not degrees       
    player_angle -= 0.1
elif keys[pygame.K_RIGHT]:        
    player_angle += 0.1    
elif keys[pygame.K_UP]:        
    player_x += -1 * math.sin(player_angle) * 5        
    player_y += math.cos(player_angle) * 5    
elif keys[pygame.K_DOWN]:        
    player_x -= -1 * math.sin(player_angle) * 5        
    player_y -= math.cos(player_angle) * 5

Time for 3D

The idea is simple and beatiful. We need to estimate length untill wall and depending on results build wall with relevant size and color.

The are two things which affect to building a 3D wall, first is what size it should be and second what color wall should be(from white to black).

#wall shading                
color = 255 / (1 + depth * depth * 0.0001)

#calculate wall height
wall_height = 21000 / (depth + 0.0001)

Color formula is easy, further is player darker is color. Wall height formula also is a piece of cake. Instead of 21000 could be any other big number, you can experiment with this variable and get right result for your needs.

Example with value 21k

Example with value 17k instead of 21k

SCALE constant should be added to "global constants" part of the code with following code, below you will find out why it's important:

SCALE = (SCREEN_WIDTH / 2) / CASTED_RAYS

#draw 3D projection
pygame.draw.rect(win, (color, color, color),
                (SCREEN_HEIGHT + ray * SCALE,
                (SCREEN_HEIGHT / 2) - wall_height / 2, SCALE, wall_height))

This code draws wall with appropriate size, color and scale. But how it works in details? Actually we create a lot of vertical stripes with the same width(SCALE value) and shifting next stripe exactly on the SCALE value, that's why SCALE value is really important(sorry for the tautology).

Updating 3D background for upper and lower part of the screen.

#update 3D background    
pygame.draw.rect(win, (100, 100, 100), (480, SCREEN_HEIGHT / 2, SCREEN_HEIGHT, SCREEN_HEIGHT))    
pygame.draw.rect(win, (200, 200, 200), (480, -SCREEN_HEIGHT / 2, SCREEN_HEIGHT, SCREEN_HEIGHT))

Now we got a few things to finish in project: create collision detection with walls and display FPS.

Collision detection

The same tactic which we use in ray_casting function but in place of rays coordinate we use players coordinates for detection collisions with walls.nvert player x, y coordinates to map col, row
col = int(player_x / TILE_SIZE)
row = int(player_y / TILE_SIZE)

#calculate map square index
square = row * MAP_SIZE + col

# player hits the wall (collision detection)
if MAP[square] == '#':
if forward:
player_x -= -1 * math.sin(player_angle) * 5
player_y -= math.cos(player_angle) * 5
else:
player_x += -1 * math.sin(player_angle) * 5
player_y += math.cos(player_angle) * 5

Displaying FPS

Nothing interesting what we really should talk about. SCREEN_WIDTH / 2 is going to display FPS counter right in the left corner of 3D projection.

#set FPS    
fps = str(int(clock.get_fps()))    
font = pygame.font.SysFont('Arial', 30)    
fpssurface = font.render(fps, False, (255, 255, 255))    
win.blit(fpssurface, (int(SCREEN_WIDTH / 2), 0))

Perfomance considerations

Ray-casting, in fact, works slower than modern 3D engines getting rendered on our super quick computers with using 3D graphics cards. There are at least 2 big issues with this code.

The way how we find interaction with wall is not optimized at all. What we do is just sorting through dots to the wall, by comparing each dot with wall boundary. There are a way out! Using DDA(Digital Differential Analysis). DDA is a fast algorithm typically used on square grids to find which square line hits. Javidx9 got fascinating material about this.
Ray-casting works with vertical stripes, when our screen buffers were build to work with horizontal stripes. So, when we draw vertical stripe it is the worst scenario for memory locality. And this causes a lot of problems with speed. You may try to find interesting content about this.

Resources

I came to the conclusion that any work can be considered as "serious" if it does not have link to resources, so in the future I will always try to add them.

https://lodev.org/cgtutor/raycasting.html (eng)
https://killerrobotics.me/2021/08/13/raycasting-game-in-python-and-pygame-part-1/comment-page-1/ (eng)
https://permadi.com/1996/05/ray-casting-tutorial-table-of-contents/ (old but still can get understanding how things work) (eng)
https://replit.com/talk/ask/Move-a-sprite-at-an-angle-in-pygame/130940 (topic about movement player) (eng)

GitHub code: https://github.com/rastr-0/teletype_source_files/blob/main/ray-casting/ray-casting.py

See ya soon

@rastr

Hash tables

2022-12-19T11:14:19.049Z

Hi there, in this article I want to talk about hash tables and implement it with c++, let's get started.

Hash table is data structure that implements an associative array. Hash tables use hash function to compute an index, which makes them really fast in finding elements. Because of this they're widely used in comuter software.

Hash table

I'll define HashTable class to implement data structure. Here you can see definition of the main functions of class.

#include <iostream>
#include <list>
#include <string> 

class HashTable{
private: 
    static const int hash_groups = 1000;
    static const int lower_limit = 1;
    static const int upper_limit = 100000;
     
    std::list<std::pair<int, std::string>> table[hash_groups];
public:
    void insert_item(const int key, const std::string& value);
    void remove_item(const int key);
    bool is_empty() const;
    const int hash_function(const int key);
    void print();

Hash functions

Now let's talk about hash functions, it's the most interesting part of hash tables. There're some bases for creating "right" hash function:

It should be efficiently computable, let's say in constant time and usually with using arithmetic operations
it should produce few collisions. Collision is situation, when hash function generates the same output for different inputs. To put in simply: h(x) = h(y), even though x != y.

Exist a lot of different hash functions.

Example of hash function (division hashing):

const int HashTable::hash_function(const int key){        
    // distribute numbers by last value of number        
    // 101 => first group; 607 => seventh group        
    return key % hash_groups;    
}

It satisfies first criteria of efficiency, but consecutive keys are mapped to consecutive entries, and this is does not do a good job of breaking up clusters.

Here are 3 more commonly used hash functions:

1) Multiplicative hash function:

h(x) = (ax) mod m:

const int HashTable::hash_function(const int key){
    int a = lower_limit + rand() % upper_limit;
    
    return (a * key) % hash_groups;
}

2) Linear hash function:

h(x) = (ax + b) mod m:

const int HashTable::hash_function(const int key){
    int a = lower_limit + rand() % upper_limit;
    int b = lower_limit + rand() % upper_limit;
    
    return (a * x + b) % hash_groups;
}

3) Polynomial hash function:

Polynomial hash function is extend of the Linear hash function. it gives us opportunity to handle a sequences of objects, such as strings or multi-dimensional coordinates.

h(x₀, . . . , xₙ) = (∑(k-1, i=0) cᵢ(p^i)) mod m:

A useful algorithm for computing polynomials is called Horner’s rule.

const int HashTable::hash_function(const std::string key){
    int p = lower_limit + rand() % upper_limit;
    int hash_value = 0;
    for(int i = key.length() - 1; i >= 0; i--){
        hash_value = (p * hash_value + static_cast<int>(key[i])) % hash_groups;
    }
    
    return hash_value;
}

Universal hashing

The main problem of listed hash functions, that it's easy to find elements which hash function's will have the same result. But at the same time with random elements we are able to talk about some kind of math prediction. Actually for random data it'll be working just fine, the average time of finding element'll be O(1). But the world is cruel and random data is a really rare thing. That's why hash function should be designed for each data in it's own way. Here comes the idea about "universal hashing".

A family of hash functions H = {hᵢ}, hᵢ: X->{0,1...M-1} is called universal if
Ɐx₁,y₁ є X, x₁ != y₁
P(hᵢ(x₁) = hᵢ(y₁)) <= 1/M. In words: A family of hash-functions is called universal if for two random not equal elements the probability of choosing hash-function gives collision not bigger, than 1/M. With universal hashing there can't be any type of data, which could make hash table works slow. It's just impossible because we choose hash function in a random way.

Let's have a look at the code for other functions.

Firstly, insert_item. I think there is nothing complicated about it.We iterate over list until find the right position for value variable based on hash value.

void HashTable::insert_item(const int key, const std::string value){
    //choose hash function depends on your needs 
    int hash_value = hash_function(key); 
    
    auto& cell = table[hash_value]; 
    auto begin_itr = std::begin(cell); 
    bool key_exists = false;
     
    for (; begin_itr != std::end(cell); begin_itr++){ 
        if (begin_itr->first == key){ 
            begin_itr->second = value; 
            key_exists = true; 
            std::cout << "Key exists, values was replaced" << std::endl; 
            break; 
         } 
     }
      
     if (!key_exists) 
         std::cout << "Key was inserted" << std::endl; 
         cell.emplace_back(key, value); 
}

Almost the same for remove_item. Iterate over list, until find key value.

void HashTable::remove_item(const int key){ 
    int hash_value = hash_function(key); 
    
    auto& cell = table[hash_value]; 
    auto begin_itr = std::begin(cell); 
    bool key_exists = false; 
    
    for (; begin_itr != std::end(cell); begin_itr++){ 
        if (begin_itr->first == key){ 
            begin_itr = cell.erase(begin_itr); 
            key_exists = true; 
            std::cout << "Key exists, values was erased" << std::endl; 
            break; 
         } 
     } 
     if (!key_exists) 
         std::cout << "Key doesn't exist" << std::endl; 
}

Typical and evident is_empty function:

bool HashTable::is_empty() const{ 
    int sum = 0; 
    for (int i = 0; i < hash_groups; i++){ 
        sum += table[i].size(); 
        if (sum > 0) 
            return false; 
     }
     
     return true; 
}

Function print also is evident.

void HashTable::print(){ 
    for (int i = 0; i < hash_groups; i++){ 
        if (table[i].size() == 0) 
            continue;
             
        auto begin_itr = table[i].begin(); 
        std::cout << i << " cell" << std::endl;
         
        for (;begin_itr != table[i].end(); begin_itr++){ 
            std::cout << "Key: " << begin_itr->first << " Value: " << begin_itr->second << std::endl; 
        } 
        std::cout << "- - -" << std::endl; 
     } 
}

We did a good work for now, but hash table still doesn't have any mechanism to resolve collisions and it's going to be our next topic for the next article.

Full code: https://github.com/rastr-0/Simple_algorithms/blob/master/hash_table/HashTable.cpp

see ya soon

@rastr

References:

Text justification

2022-12-11T18:18:09.518Z

Hi everyone, in this article I'll try to explain how to implement text justification algorithm. We'll use python for this. Let's get started.

I saw this task at codewars a few month ago and solved it. The task formulates in the following way: "task is to emulate text justification in monospace font. You will be given a single-lined text and the expected justification width".

Here are the rules:

Use spaces to fill in the gaps between words.
Each line should contain as many words as possible.
Use '\n' to separate lines.
Gap between words can't differ by more than one space.
Lines should end with a word not a space.
'\n' is not included in the length of a line.
Large gaps go first, then smaller ones ('Lorem--ipsum--dolor--sit-amet,' (2, 2, 2, 1 spaces)).
Last line should not be justified, use only one space between words.
Last line should not contain '\n'
Strings with one word do not need gaps ('somelongword\n').

So, the result of justified text should look like this:

Example of justifed text

The idea of implementation of the algorithm is described in following text.

While we can add words to line we are doing it, if next word + current line length is bigger, than width, we don't add this word to the current line. If current line width still less, than width, we add spaces to line in the direction from left to right.

def justify(text, width):
    # starting variables
    line = ''
    linelength = 0
    finished_text = ''
    # iterate over text, item represents each word
    for item in text.split():
        # check if current line + new word is bigger than given width
        if linelength + len(item) > width:
            # delete space after last word
            line = line[:-1]
            linelength -= 1
            # if length of line is less than width, then add spaces to this line
            if width - linelength > 0:
                line = add_spaces(line, width - linelength)
            # add line with all needed spaces to the final text version
            finished_text += line + '\n'
            # setup variables to starting positions
            line = ''
            linelength = 0
        # if current line + new_word is less than width, then add new_word to current line
        else:
            linelength += len(item)
            line += item
            linelength += 1
            line += ' '
    # delete last space because of conditions on Codewars
    line = line[:-1]
    finished_text += line
    
    return finished_text

Let's see on the code in order. It's starting from initializing starting variables. Further, I start to iterate over string and face main condition.

if linelength + len(item) > width:

It's really important to have > sign and not >=, because anyway line width will be (width + 1) size.

Next nested condtion is about adding additional spaces to line.

if width - linelength > 0:
    line = add_spaces(line, width - linelength)

The realization of add_spaces function will be below.

If line width + word is less than width we don't do anything special, just adding word to line and one space after it.

Now let's dive into add_spaces function.

The idea of this function is next: Count needed amount of additional spaces, iterate over line (from the left to the right side) and put additional spaces between words, also decrease variable with needed amount of spaces. If after one circle there is still not enough spaces -> repeat it.

def add_spaces(line, count_spaces):
    i = 0
    splitted_line = line.split()
    total_words = sum(1 for _ in splitted_line)
    if total_words == 1:
        return line
    # start iterate over list if there are more than one word
    while True:
        # if it's last word and it's line still needed more spaces then iterate over list from the start (i = 0)
        if count_spaces != 0 and i == (total_words - 1):
            i = 0
        # check if it's still needed to add spaces to line
        if count_spaces > 0:
            splitted_line[i] += ' '
            count_spaces -= 1
            i += 1
        else:
            break
    return ' '.join(splitted_line)

Firstly, count amount of words in given line. Then, based on amount of words, add spaces to the line.

if count_spaces != 0 and i == (total_words - 1):

This condition detects, if already has been made one iteration over list but we still got spaces to add.

As always full code can be found at my GitHub: https://github.com/rastr-0/teletype_source_files/tree/main/text_justification

See ya soon

@rastr

RSA, part 2: encryption and decryption

2022-08-27T17:47:11.306Z

Hi there! It's second part about RSA alorithm. We'll talk about encryption of messages and their decryption. For encyption and decryption we use the same operation: modular exponention. So, basically what we need to do is to create pow_mod function. We can implement it with 2 different approaches: recursion and iterative realizations.

But firstly we need to define some conditions. Let's define f function. It should get x^y mod n values and result value.

if y = 0, then return result
if the smallest bit of y is 0 (y is even number) , then f(x^2 mod n, y >> 1, n, result)
if the smallest bit of y is 1 (y is odd number), then f(x^2 mod n, y >> 1, n, result * x mod n)

That's all, simple and smart.

Implementation

Let's try to implement it. First will be implementation with recursion.

long f(long x, long y, long n, long res){ 
    if (y == 0) 
        return res; 
    // if the smallest (last from right side) bit is 1, if so, then number is odd 
    else if (y & 0x01) 
        return f((x * x) % n, y >> 1, n, (res * x) % n); 
    // if the smallest (last from right side) bit is 0, then number is even 
    return f((x * x) % n, y >> 1, n, res);
} 
long pow_mod(long x, long y, long n){ 
    return f(x, y, n, 1);
}

Now some explanations, why I check if number is even or odd (y & 0x01 or y & 1 or y & 0x1) in this unclear way. It's just simply faster to use bit operations. Why it still works right? If we represent number in binary view, then we'll get interesting refularity: each even's number smallest bit is always 0 and each odd's number smallest bit is always 1. If you have time, you can convert any number to binary view and check. The same idea with using y >> 1 instead of y / 2. It works faster because it's a bit operation and bit operations always work fast.

Now iterative realization. It's better to use this implementation because you won't have any problems with call stack which of course has limits.

long pow_mod(long x, long y, long n){ 
    long res = 1; 
    // while y != 0 
    while (y){ 
        // if the smallest bit is 1 then number is odd 
        if (y & 0x01) 
            res = (res * x) % n; 
        x = (x * x) % n; 
        y >>= 1; 
    } 
    return res;
}

Time complexety, auxiliary space

Implementation with recursion: O(log n), O(log n)
Iterative iImplementation: O(log n), O(1) - constant time

Encryption and decryption

For encryption data we'll use this formula: m^e mod n. For decription data we'll use c^d mod n formula.

// encrypted text (c) = m^e mod n 
long long c = pow_mod(m, e, n); 
std::cout << "encrypted text: " << c << std::endl; 0
// decrypted text (m) = c^d mod n 
m = pow_mod(c, d, n); 
std::cout << "decrypted text: " << m;

Full code: https://github.com/rastr-0/Simple_algorithms/blob/master/RSA/rsa.cpp

see ya soon

@rastr

RSA, part 1: generating private and public keys

2022-08-12T23:37:00.912Z

Hi there. It's first part about RSA algorithm with using c++, I'll provide information and code about generating public and private keys. Let's get started. RSA is public key cryptosystem which widely used for transfering data. It was descovered in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman. RSA creates public key with using two large prime numbers and auxiliary value. The idea of all public key cryptosystems is simple:

If we know x, then to calculate f(x) must be easy, if we know f(x), then calculate x must be really hard(no effecient way to do this). Similar property has modular exponentiation.

Modular exponentiation

We've got c, m, e, n and d values. Let's take a look on first expression. We've got c, m, e and n values: m stands for text which we want to encrypt, c stands for decrtypted text. It's obvious that c depends on values e and n. So, (e, n) pair is public key.

Take a look on second expression. We've got new value d: d is value with using wich we got m(decrypted text). So, (e, d) pair is private key.

Prime values kept in secret. Any message can be encrypted with using public key, but can be decrypted by someone who knows private key. For now is no efficient way to decrypte message without knowing a private key.

Operation

RSA algorithm involves 4 steps: generation, distribution, encryption and decryption.

Key generation

Here it's necessary to make a reservation about my implementation. It's quite obvious that numbers better be big, it's popular to use 1024 bit length, for this need to use libraries for big numbers (such as GMP for c++). I don't use it. Later maybe I'll post article about RSA code with using GMP library.

Now let's be more specific about generating values and all details.

1. Choose 2 distinct prime numbers p and q in a random way. What we do is just generate 2 random numbers and chech if they're prime, if not - generate again. if you got any questions about is_prime function then visit this topic on StackOverFlow.

// should be compiled with c++17
#include <ctime>
#include <iostream>

#define u unsigned

// primarity test for numbers
bool is_prime(u int num){
    if (num != 2){
        if (num < 2 || num % 2 == 0) 
            return false; 
        for (int i = 3; i * i <= num; i += 2){ 
            if (num % i == 0) 
                return false; 
        }
    }
    return true; 
}

std::pair<int, int> generate_prime_numbers(u int low_lim, u int upper_lim){ 
    // u means unsigned, I defined this above
    u int first_num = 0; 
    u int second_num = 0; 
    do { 
        first_num = low_lim + (rand() % upper_lim); 
        second_num = low_lim + (rand() % upper_lim);  
    } while (!is_prime(first_num) || !is_prime(second_num)); 
     
    return std::make_pair(first_num, second_num); 
}

2. Compute n = p * q

// I use long long type because n probably is a big number 
long long n = p * q;

3. Calculate Euler's phi function(Euler's totient function). Function counts positive integers that a relatively prime to given n. Other words, this function counts numbers with gcd(great common devider, НОД рус.) 1 with n.

Why n has beed choosen exactly like this. We can get private d value with public e value. With p and q values is not a problem to calculate phi function, but in public key is n value. So, if we want to calculate phi(n) we need to solve factorization problem(there is no effecient way to do this).

4. Find e value: e value have to comply these conditions.

Conditions for e value

u int find_coprime(u int phi_res){ 
    u int e = 2; 
    while (e < phi_res){ 
        u int gcd_res = gcd(e, phi_res); 
        if (gcd_res == 1) 
            return e; 
        e++; 
    }     
    return e; 
}

5. Find d value

Conditions for d value

u int calculate_d(u int phi_res, u int e){ 
    u int k = 1; 
    u int d = 0; 
     
    while ((((k * phi_res) + 1) % e) != 0) 
        k++; 
    d = ((k * phi_res) + 1) / e; 
     
    return d; 
}

Main function

int main(){ 
    srand(time(0)); 
    // from 1k to 10k 
    auto [p, q] = generate_prime_numbers(1000, 10000); 
    long long n = p * q; 
    u int phi_res = phi(p, q); 
    u int e = find_coprime(phi_res); 
    u int d = calculate_d(phi_res, e); 
     
    std::cout << "(" << e << ", " << n << ") — public key" << std::endl; 
    std::cout << "(" << e << ", " << d << ") — private key"; 
    /* 
    (e, n) pair stands for public key, could be published anywhere 
    (e, d) pair stands for private key and keeps in secret 
    */ 
     
    return 0; 
}

Next article'll defenitely be 2 part about RSA.

Full code on GitHub: https://github.com/rastr-0/teletype_source_files/tree/main/rsa_generating_keys

See ya soon

@rastr

2D simulation of Solar system

2022-08-04T22:02:04.192Z

In this article we'll try to create 2D simulation of Solar system with python and pygame lib. I consider people that are reading it are familiar with pygame lib, just basics. Let's get started.

That's how looks framework of pygame app.

import pygame
import math

# colors in rgb type for drawing planets and Sun
BLACK = (0, 0, 0)
WHITE = (255, 255, 255)
YELLOW = (255, 255, 0)
BLUE = (26, 209, 255)
RED = (255, 92, 51)
GREY = (80, 71, 81)
ORANGE = (204, 163, 0)

pygame.init()
WIDTH, HEIGHT = 800, 800
WIN = pygame.display.set_mode((WIDTH, HEIGHT))
pygame.display.set_caption("Solar system simulation")
def main():
    run = True
    clock = pygame.time.Clock()
    
    while run:
        # set up 60 fps
        clock.tick(60)
        WIN.fill(BLACK)
        
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                run = False
    pygame.quit()

    
main()

If you start it, you'll see black sreen and working button for closing window.

Now let's define Planet class. It's also easy to change SCALE in simulation, just increase first number and check it out.

class Planet: 
    # astronomical unit, distance from the Sun to the Earth in meters 
    AU = 149.6e6 * 1000 
    G = 6.67428e-11 
    SCALE = 80 / AU # 1 AU = 100 pixels 
    TIMESTEP = 3600 * 24 # 1 day (3600 seconds = 1 hour)

Here is initializing function of Planet class, nothing complicated but I'd like to note I use sun variable to identify Sun. Technically sun isn't a planet, it's star but who cares? :) So, all planets have False value and only Sun has True.

def __init__(self, x, y, radius, color, mass): 
    self.x = x 
    self.y = y 
    self.radius = radius 
    self.color = color 
    self.mass = mass  
    self.sun = False 
    self.distance_to_sun = 0 
    self.orbit = []  
    self.x_velocity = 0 
    self.y_velocity = 0

For now let's create draw function basement.

def draw(self, win): 
    # WIDTH / 2 and HEIGHT / 2 give a chance to draw in the middle of the scren
    # in Pygame center of the screen is at the top left corner
    x = self.x * self.SCALE + WIDTH / 2 
    y = self.y * self.SCALE + HEIGHT / 2
    # draw circle with set color and radius in the middle of the screen 
    pygame.draw.circle(win, self.color, (x, y), self.radius)

Now we'll add Sun and other planets to the simulation and check if draw function works right. Code below should be added in the main function before while cycle. The reason why I put - in first value for Earth and Mars it's because I want to see planets in different sides(left or right).

By the way, why this project is calling simulation because I use real numbers to simulate movements of planets with gravity. All numbers easy to google and check.

sun = Planet(0, 0, 15, YELLOW, 1.98892 * 10**30) 
sun.sun = True
# further it's easy to add more planets
mercury = Planet(0.387 * Planet.AU, 0, 4, GREY, 0.330 * 10**23)
venus = Planet(0.723 * Planet.AU, 0, 7, WHITE, 4.8685 * 10**24)
earth = Planet(-1 * Planet.AU, 0, 8, BLUE, 5.9742 * 10**24)
mars = Planet(-1.524 * Planet.AU, 0, 6, RED, 6.39 * 10**23)

planets = [sun, mercury, venus, earth, mars]

def main():
    run = True
    clock = pygame.time.Clock()
    
    while run:
        # set up 60 fps
        clock.tick(60)
        WIN.fill(BLACK)
        
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                run = False
        for planet in planets:
            planet.draw(WIN)
        pygame.display.update()
    pygame.quit()

    
main()

That's what we got. Planets with actual distances reduced in many times

Planets of Solar system

Now I want to disscus the hardest part of article - realisation of gravity. We need to calculate distance beetwen two points and force that acts on two objects and farther with using cos and sin calculate Fy and Fx movement.

Formula illustration

def attraction(self, other):
    # calculating R(distance between 2 points) 
    other_x, other_y = other.x, other.y 
    distance_x = other_x - self.x 
    distance_y = other_y - self.y 
    distance = math.sqrt(distance_x ** 2 + distance_y ** 2)  
    if other.sun: 
        self.distance_to_sun = distance
    # calculating force_x and force_y to define how to move object    
    force = self.G * self.mass * other.mass / distance ** 2 
    angle = math.atan2(distance_y, distance_x) 
    force_x = math.cos(angle) * force 
    force_y = math.sin(angle) * force  
    
    return force_x, force_y

Next step is setup start y velocity for planets in main function and add new if your sreen is quite big for this :) Again minus before number determines direction of movement(clockwise or counterclockwise).

# start y velocity
mercury.y_velocity = -47.4 * 1000
venus.y_velocity = -35.02 * 1000
earth.y_velocity = 29.783 * 1000
mars.y_velocity = 24.077 * 1000

# new planet if your screen is big enough
jupiter = Planet(5.2 * Planet.AU, 0, 10, ORANGE, 1.898 * 10**27)    
jupiter.y_velocity = -13.1 * 1000

Now we'll complete update function. Here we count x velocity for planets. You can test and delete starting values for y velocity, you'll see something like falling planets on the Sun without moving around it.

def update_position(self, planets): 
    total_force_x = total_force_y = 0 
    for planet in planets: 
        if self == planet: 
            continue  
        fx, fy = self.attraction(planet) 
        total_force_x += fx 
        total_force_y += fy  
    # F = m * a, Newton's second law of motion then a = F / m  
    self.x_velocity += total_force_x / self.mass * self.TIMESTEP 
    self.y_velocity += total_force_y / self.mass * self.TIMESTEP
      
    self.x += self.x_velocity * self.TIMESTEP 
    self.y += self.y_velocity * self.TIMESTEP 
    self.orbit.append((self.x, self.y))

Of course add new function update_position to the main function!

planet.update_position(planets)

Let's add some orbits for moving planets. This code should be added to the draw function before drawing circle(planet).

if len(self.orbit) > 2: 
    updated_points = []
    # we get all points during the movement and with it draw line 
    for point in self.orbit: 
        x, y = point 
        x = x * self.SCALE + WIDTH / 2 
        y = y * self.SCALE + HEIGHT / 2 
        updated_points.append((x, y))  
    # False means it isn't enclosed line    
    pygame.draw.lines(win, self.color, False, updated_points, 1)

For now you get working simulation that looks pretty cool for me.

Working 2D simulation of Solar system

As always full code can be found at my GitHub: https://github.com/rastr-0/solar_system_simulation/blob/main/main.py

See ya soon

@rastr

Binary trees

2022-07-10T21:58:10.816Z

In this article i'm going to talk about binary trees. Binary tree is a data structure where each node have at most two children(other nodes), usually it's left child and right child

Sometimes it's possible to interpret binary trees as undirected or directed graph, in this case binary tree is ordered or rooted tree. Indeed, that binary tree is a type of M-ary tree, where M is 2.

Using of binary trees in programming

Representation of data with bifurcating structure(rus. разветвляющаяся структура), common use cases: Huffman coding
Using for searching and sorting as they provide hierarchical data storage

Example of binary tree, this one is "Huffman tree", generated fom the exact frequencies of the text "this is an example of a huffman tree"

Types of binary trees

I should say that tree terminology is not well-standardized and it could differ, especially if you'll open old books

a perfect binary tree: all interior nodes have 2 children and leaves have the same depth. An example of perfect tree is family tree, becuase all people have two parents.
a degenerate binary tree: every node has only one chlid, so tree will behave as linked list
a full binary tree: type of binary tree in which every node has 0 or 2 children. A full binary tree also is:

single vertex
tree whose root subtrees are full bynary trees

a complete binary tree: binary tree, in which level, except lpossibly ast, is completely filled and all nodes as far left as possible
a balanced binary tree: binary tree in which left and right subtrees of every nodes differ in height no more than 1

Illustration of binary trees

Properties of binary trees

Some obvious facts

the minimum number of nodes at height H = H + 1
the maximum number of nodes at height H = 2^H - 1
the maximum number of nodes at any level(n) = 2^n
minimum possible hieghts or levels = log2(n + 1)

if you want to see other properties you're free to visit wiki

Methods for storing binary trees

using of references and nodes
using of arrays(this one benefits from more compact storage and better locality to references)

Implementation

I'll implement solution in c++. I've done Search Binary tree, it's a little bit complicated, because we need to add elements in tree according to certain rules.

C++ solution of binary search tree

Creating structure for node, it's basically data, pointer to next left node and next right node. Also here is two constructions.

struct Node { 
    int data; 
    Node* left; 
    Node* right; 
    Node(int data) { 
        this->data = data; 
        left = nullptr; 
        right = nullptr; 
    }
    Node() { 
        data = 0; 
        left = nullptr; 
        right = nullptr; 
    }
};

This is class Binary_tree, which defines some functions for adding elements, printing in different order and destroing tree.

class Binary_tree 
{
private: 
    Node* root; 
    void destroy(Node* leaf); 
    void insert(int key, Node* leaf); 
    void inorder_print(Node* leaf); 
    void preorder_print(Node* leaf); 
    void postorder_print(Node* leaf); 
    Node* search(int key, Node* leaf);
public: 
    Binary_tree(); 
    void insert(int key); 
    void destroy(); 
    void inorder_print(); 
    void preorder_print(); 
    void postorder_print(); 
    Node* search(int key);};

Let's start from insert function. Code is well-commented, so you don't actually need my comments

void Binary_tree::insert(int key, Node* leaf) {
    if (key < leaf->data) { 
        // if leaf->right isn't a leaf, than go to the next and check 
        if (leaf->left != nullptr)
            insert(key, leaf->left); 
        // if it is a leaf, than create a new object 
        // and initialize data with key 
        else { 
            leaf->left = new Node(); 
            leaf->left->data = key; 
        } 
    } 
    else if (key >= leaf->data) { 
        // if leaf->right isn't a leaf, than go to the next and check 
        if (leaf->right != nullptr)
            insert(key, leaf->right); 
        // if it is a leaf, than create a new object 
        // and initialize data with key 
        else { 
            leaf->right = new Node(); 
            leaf->right->data = key; 
        } 
    }
}

Next function is destroy. It's pretty simple.

void Binary_tree::destroy(Node* leaf) {
    if (leaf != nullptr) { 
        destroy(leaf->left); 
        destroy(leaf->right); 
        delete leaf; 
    }
}

The last complicated function is search function.

Node* Binary_tree::search(int key, Node* leaf) { 
    if (leaf != nullptr) { 
        if (leaf->data == key) 
            return leaf; 
        else if (key > leaf->data) 
            return search(key, leaf->right); 
        else 
            return search(key, leaf->left); 
    } 
    else 
        return nullptr; // there are no elements in Binary_tree
}

Next important thing is different types of traversing tree, it means visiting and outputing all values of each node in particular order.

Each of traversing methods have a particular order they follow

For Inorder, you traverse from the left subtree to the root then to the right subtree.
For Preorder, you traverse from the root to the left subtree then to the right subtree.
For Post order, you traverse from the left subtree to the right subtree then to the root.

Let's have a look at code.

// left - > root - > right
void Binary_tree::inorder_print(Node* leaf) { 
    if (leaf != nullptr) { 
        inorder_print(leaf->left); 
        std::cout << leaf->data << " "; 
        inorder_print(leaf->right); 
    }
}

// root - > left - > right
void Binary_tree::preorder_print(Node* leaf) { 
    if (leaf != nullptr) { 
        std::cout << leaf->data << " "; 
        inorder_print(leaf->left); 
        inorder_print(leaf->right); 
    }
}

// left - > right - > root
void Binary_tree::postorder_print(Node* leaf) { 
    if (leaf != nullptr) { 
        inorder_print(leaf->left); 
        inorder_print(leaf->right); 
        std::cout << leaf->data; 
    }
}

I won't comment my public methods, it's done for encapsulation and mostly they just call private functions.

Full code at my GitHub profile: https://github.com/rastr-0/Simple_algorithms/blob/master/binary_tree/binary_tree.cpp

See ya soon

@rastr

Solving easy sudoku(backtracking)

2022-07-07T14:21:13.812Z

In this article I’d like to consider backtracking technique. Backtracking is a type of BFS (Brute-force-search) algorithm. Backtracking is DFS(depth first search), because it’ll completely go through one branch before moving to the next.

Short description of the algorithm

Briefly, the program would put 1 in the first cell and check if it’s allowed(checking row, column and box). If it is, go to the next cell, put 1 and check. If it finds out it’s invalid, then increase the number and check again. If a cell is discovered where none of the 9 digits are allowed, then leaves that cell blank and moves back to the previous cell, the number in that cell incremented by one.

illustration of solving sudoku with backtracking metho

Advantages of this method are

A solution is guaranteed(As long as sudoku is valid)
Quite simple code in comparison with another methods
Solving time is mostly unrelated to “degree of difficulty” of sudoku

The main disadvantage is that solving time might be so slow compared to algorithms modeled after deductive methods. Also sudoku can be designed against backtracking method.

Solution

I’m going to use python for solving it but solutions can be easily implemented in another language. First of all, I’d like to create three checking functions: used_row, used_col, used_box. Used_row function just checks if we find the same number in row. Here comes used_row function.

def used_row(puzzle, row, num):    
    for i in range(9):        
        if puzzle[row][i] == num:            
            return True    
    return False

Used_col checks if we find the same number in col. That’s pretty simple.

def used_col(puzzle, row, num):
    for i in range(9):
        if puzzle[i][col] == num:
            return True
    return False

Used_box checks if we find the same number in box 3 x 3. I think you shouldn't struggle with understanding it.

def used_box(puzzle, row, col, num):    
    for i in range(3):        
        for j in range(3):            
            if puzzle[i + row][j + col] == num:                
                return True    
    return False

Next function will be is_safe. It’s gonna check if one of these functions return true.

def is_safe(puzzle, row, col, num):    
    return not used_row(puzzle, row, num) and 
        not used_col(puzzle, col, num) and 
        not used_box(puzzle, row - row % 3, col - col % 3, num)

The reason why I pass this kind of arguments (row - row % 3 and col - col % 3) that's becuase we need to check if we find number in square 3x3, that's the easiest way to do it.

Next function is find_empty_cell. l_vars contain i and j indexes; in other words these list stores index of empty cell.

def find_empty_cell(puzzle, l_vars):    
    for i in range(9):        
        for j in range(9):            
            if puzzle[i][j] == 0:                
                l_vars[0], l_vars[1] = i, j                
                return True    
     return False

Last function is solve_sudoku. It is a recursive function, which returns False if sudoku is unsolvable

def solve_sudoku(puzzle):    
    l_vars = [0, 0]    
    if not find_empty_cell(puzzle, l_vars):        
        return True            
     
     row, col = l_vars[0], l_vars[1]
             
     for num in range(1, 10):        
         if is_safe(puzzle, row, col, num):            
             puzzle[row][col] = num            
             if solve_sudoku(puzzle):                
                 return True            
         puzzle[row][col] = 0                
     return False

So, that's it. If you still got problems with implementing it you can go thorugh my code.

Link to GitHub repo: https://github.com/rastr-0/teletype_source_files

See ya soon

@rastr