Forem: Dilli Babu R

Hyperspace travel in JavaScript Canvas

Dilli Babu R — Sun, 22 May 2022 17:29:41 +0000

We have seen cool hyperspace visuals in Starwars. Here we are going mimic the same using Javascript canvas.

So, first we create a canvas element in our html file and also a script tag to hold our javascript.

<body>
    <canvas></canvas>
    <script></script>
</body>

then in our script tag, we get the canvas element.

const canvas = document.querySelector("canvas");
const ctx = canvas.getContext("2d");

Stars

Now lets define a blueprint for a Star. Each star has a location (x,y), radius, color and a draw function that draws the star on the canvas.

function Star(x,y,radius,color){
    this.x = x;
    this.y = y;
    this.radius = radius;
    this.color = color;
    this.draw = function (){
        ctx.strokeStyle = color;
        ctx.fillStyle = color;
        ctx.beginPath();
        ctx.arc(this.x, this.y, this.radius, 0, Math.PI * 2, false);
        ctx.stroke();
        ctx.fill();
    }
}

lets create an array to hold the star objects and const to specify how many stars we create.

const NUMBER_OF_STARS = 1000;
let stars = [];

Lets write a function to create the stars, we use random locations so lets use a simple random number generator.


function getRandomInt(min, max) {
    min = Math.ceil(min);
    max = Math.floor(max);
    return Math.floor(Math.random() * (max - min) + min);
}

function createStars() {
    for (let counter = 0; counter < NUMBER_OF_STARS; counter++) {
        let radius = getRandomInt(1, 3);
        let x = getRandomInt(radius, (canvas.width - radius));
        let y = getRandomInt(radius, (canvas.height - radius));
        let color = "lightblue";
        stars.push(
            new Star(x, y, radius, color)
        );
    }
}

Another quick loop to draw them on the screen.

createStars();
stars.forEach(star => star.draw());

Creating stars with different radius makes it feel like few are far and few are near.

Now to the important stuff, How do we jump to hyperspace.

Movement

By movie scenes we can see that when we travel at lightspeed, each star moves from it's location to the edge of the screen, but we need to calculate the angle or linepath.

To simplify this, we can assume a center point and if we draw a line from center to the star, that essentially is the path that star will follow until it reaches the edge of the screen. like below

Now, we have two point for each line, 1st is the center of the screen and second point is the Star's location. Using the following formula, we can calculate the slope of the line, which we can use to move the star later.

$\frac {(y_2-y_1)} {(x_2-x_1)}$

so, lets add slope attribute to Star

function Star(x,y,radius,color, slope){
    this.x = x;
    this.y = y;
    this.radius = radius;
    this.color = color;
    this.slope = slope;
    this.draw = function (){
        ctx.strokeStyle = color;
        ctx.fillStyle = color;
        ctx.beginPath();
        ctx.arc(this.x, this.y, this.radius, 0, Math.PI * 2, false);
        ctx.stroke();
        ctx.fill();
    }
}

and define a function as follows:

function slopeFromCenter(x, y) {
    let x1 = x;
    let y1 = y;
    let x2 = centerX;
    let y2 = centerY;
    return (y2 - y1) / (x2 - x1);
}

Now change the Star Object creation as follows.

stars.push(new Star(x, y, radius, color, slopeFromCenter(x, y)));

Animation Loop

For the animation, we use requestAnimationFrame method which will be called once every frame, and to start & stop the travel using spacebar key, we will create a variable travel as follows.

let travel = null;

lets create a basic jump method too, will make changes to it later.

function jump() {

    for (let i = 0; i < stars.length; i++) {
        const star = stars[i];
        ctx.beginPath();
        ctx.moveTo(star.x, star.y);
        // we will work these in a minute
        const nextXY = [star.x + 1, star.y + 1];
        const nextX = nextXY[0];
        const nextY = nextXY[1];
        ctx.lineTo(nextX, nextY);
        ctx.strokeStyle = star.color;
        ctx.lineWidth = star.radius;
        ctx.stroke();
        ctx.closePath();
        star.x = nextX;
        star.y = nextY;
    }
}

All we are doing is simply adding 1 to star's xy coordinates.

let travel = null;
function animate() {
    travel = requestAnimationFrame(animate);
    jump();
}

window.addEventListener("keypress", function (event) {
    if (event.key === " ") {
        if (travel == null) {
            travel = window.requestAnimationFrame(animate);
        } else {
            window.cancelAnimationFrame(travel);
            travel = null;
        }
    }
});

We can see that stars are going to right bottom cornor as we are incrementing xy values by 1. Now lets do the actual movement code by defining a nextStop function as follows.

function nextStop(currentX, currentY, m, velocity) {
    let s = velocity / Math.sqrt(1 + m * m);
    let nextX = currentX + s;
    let nextY = currentY + m * s;
    return [Math.ceil(nextX), Math.ceil(nextY)];
}

this function simply takes (x,y), slope and velocity and returns a new coordinates, by adjusting the velocity we can adjust the travel speed too.

lets update the jump function to use nextStop function as follows.

function jump() {

    for (let i = 0; i < stars.length; i++) {
        const star = stars[i];
        ctx.beginPath();
        ctx.moveTo(star.x, star.y);
        // update the following line
        const nextXY = nextStop(star.x, star.y, star.slope, 20);
        const nextX = nextXY[0];
        const nextY = nextXY[1];
        ctx.lineTo(nextX, nextY);
        ctx.strokeStyle = star.color;
        ctx.lineWidth = star.radius;
        ctx.stroke();
        ctx.closePath();
        star.x = nextX;
        star.y = nextY;
    }
}

but...

We can see, we got right half right but left half of the screen is in reverse... This is because the slope we calculated. To fix that update the slopeFromCenter function as follows.

function slopeFromCenter(x, y) {

    let x1 = x;
    let y1 = y;
    let x2 = centerX;
    let y2 = centerY;
    let q = null; // Quadrant
    let direction = 1;

    if (x > centerX && y <= centerY) {
        q = "Q1";
    } else if (x <= centerX && y <= centerY) {
        q = "Q2";
    } else if (x <= centerX && y > centerY) {
        q = "Q3";
    } else if (x > centerX && y > centerY) {
        q = "Q4";
    }

    if (q == "Q2" || q == "Q3") {
        direction = -1;
    }

    return [(y2 - y1) / (x2 - x1), direction];
}

And update the createStars method as follows

function createStars() {
    for (let counter = 0; counter < NUMBER_OF_STARS; counter++) {
        let radius = getRandomInt(1, 4);
        let x = getRandomInt(radius, (canvas.width - radius));
        let y = getRandomInt(radius, (canvas.height - radius));
        let color = "white";
        let slopeAndDirection = slopeFromCenter(x, y);
        stars.push(
            new Star(x, y, radius, slopeAndDirection[0], slopeAndDirection[1], color)
        );
    }
}

Also update the jump function to use the direction as well re-creating the stars at random location if they reach the edge of the screen. Instead of creating the new object we are simply changing it's location so it would feel like it's new star. It's better for memory & performance.

function jump() {
    for (let i = 0; i < stars.length; i++) {
        const star = stars[i];
        if (
            star.x <= 0 ||
            star.x > canvas.width ||
            star.y <= 0 ||
            star.y > canvas.height
        ) {
            star.x = Math.ceil(
                Math.random() * (window.innerWidth - star.radius * 2 + star.radius)
            );
            star.y = Math.ceil(
                Math.random() * (window.innerHeight - star.radius * 2 + star.radius)
            );
            const slopeAndDirection = slopeFromCenter(star.x, star.y);
            star.slope = slopeAndDirection[0];
            star.direction = slopeAndDirection[1];
        }
        ctx.beginPath();
        ctx.moveTo(star.x, star.y);
        const nextXY = nextStop(
            star.x * star.direction,
            star.y * star.direction,
            star.slope,
            20
        );
        const nextX = nextXY[0];
        const nextY = nextXY[1];
        ctx.lineTo(nextX * star.direction, nextY * star.direction);
        ctx.strokeStyle = star.color;
        ctx.lineWidth = star.radius;
        ctx.stroke();
        ctx.closePath();
        star.x = nextX * star.direction;
        star.y = nextY * star.direction;
    }
}

Now, it will be working fine... but over the time screen will be filled complete... to have nice animation, we modify the animate function. Here using ctx.fillRect we are filling the screen with black transparent color, which prevents the screen from getting completely filled.

function animate() {
    travel = requestAnimationFrame(animate);
    ctx.fillStyle = "rgba(0,0,0,0.1)";
    ctx.fillRect(0, 0, window.innerWidth, innerHeight);
    jump();
}

The final result can be accessed here.
Hit Spacebar to start or stop,
+ key to increase speed,
- key to slowdown and enjoy the journey :)

The complete code with few other improvements are linked here

Thank you...

Better way to handle paths in python

Dilli Babu R — Mon, 22 Feb 2021 15:18:04 +0000

What this is about?

You might have seen python code handling paths like this.

folder_path = 'C:\\users\\dr\\Documents'
# in unix based machines like below
# folder_path = "/home" + "/" + "dr"
file_name = 'test.txt'
file_path = folder_path + '\\' + file_name

with open(file_path) as file_data:
    do_something_with(file_data)

of course, this will work. But, if we want our program to work in other OS such as Mac or Linux, then the code will fail, because Windows handles path differently compared to UNIX based Operating Systems.

So, another way is to use join method from os.path module like below.

import os
file_path =  os.path.join("C:\\", "users", "dr", "Documents", "test.txt")
print(file_path) # C:\users\dr\Documents

But, a better way to handle paths would be

Using `Path` from `pathlib`

first lets import Path from pathlib

from pathlib import Path

Then we will initiate path like follows, note we use / even in Windows OS instead of \\.

folder_path = Path('C:/Users/dr/Documents')

Then to append path we simply have to use / like so

file_path = folder_path / file_name

Even if we have a long paths it would be easier to write and read.

long_file_path = root / folder_a / folder_b / filename

this will work properly in Windows, Mac & Linux, we don't have to worry about \\ or /.

Apart from this advantage, Path also provides lot of functions such as is_file, is_dir, mkdir, which we normally use from os.path module.

# few methods
import Path from pathlib
path = Path("/home/dr")
path.exists() # returns True if folder exists else False
path.home() # "/home/dr"
path.is_dir() # True
path.is_file() # False
path.mkdir() # create folder
# and a lot more

A python package with selenium to download high-res image using Google Search by Image

Dilli Babu R — Sat, 09 Jan 2021 19:02:15 +0000

highres

A python package to download high resolution image using Google Search by Image feature

Prerequisites:

Instructions are below

Python with pip selenium package
A browser with Webdriver

Install selenium via pip

pip install selenium

Webdriver Setup

Click and download the driver from their official websites.

Add webdriver folder path to System path

Add downloaded driver folder path to System path.

Todo

Now, before we start coding, lets break down our goal into smaller components.

Set up Code for:

Input & Output folders
Identify image files in a folder.
Detect browser and launch
Navigate and use Google's 'Search by Image'
Download image based on it's URL and save in a folder
Create a pip package

Code for Input & Output folders

Nomally we can simply use string variable to store paths, but using Path from pathlib is OS neutral and has many useful features. Like for combining paths, we can simply use / instead + "//" + like we do with strings.

so, lets import that one.

import os
from pathlib import Path
# this is come as command line input for completed code.
images_folder_path = Path(r'/home/dr/Pictures/low-res')
highres_folder_name = Path(r'highres')
success_folder_name = Path(r'old')
error_folder_name = Path(r'error')

if not os.path.exists(images_folder_path / highres_folder_name):
    os.mkdir(images_folder_path / highres_folder_name)
if not os.path.exists(images_folder_path / success_folder_name):
    os.mkdir(images_folder_path / success_folder_name)
if not os.path.exists(images_folder_path / error_folder_name):
    os.mkdir(images_folder_path / error_folder_name)

image_extensions = [".jpeg", ".jpg", ".png", ".bmp"]

if not os.path.exists(images_folder_path):
    raise SystemExit("{} is a invalid folder".format(images_folder_path))

Identify image files in a folder.

As I mentioned before Path from pathlib has lot of features,
one of them is getting the file extention easily.
like

Path('/home/dr/Pictures/image.jpeg').suffix # returns ".jpeg"

# lets get all the images in the folder
files = os.listdir(images_folder_path)

# lets filter all the files having this extensions,
# using list comprehension here
image_extensions = [".jpeg", ".jpg", ".png", ".bmp"]

files = [file for file in files if Path(file).suffix.lower() in image_extensions]
if len(files) == 0:
    raise SystemExit("No images found in the input folder")

Detect Browser and define code

Normally, we can launch a webpage simpy with following three lines...

from selenium import webdriver
browser = webdriver.Firefox()
browser.get("https://dev.to")

But we want to support most popular browsers. So, will try to launch with a browser, if we get an error, we will try to check next browser.

browser = None
url = r"https://google.com/images"

if browser is None:
    try:
        browser = webdriver.Chrome()
        browser.get(google_images_url)
    except (Exception) as err:
        print(err)
if browser is None:
    try:
        browser = webdriver.Firefox()
        browser.get(google_images_url)
    except (Exception) as err:
        print(err)
if browser is None:
    try:
        browser = webdriver.Safari()
        browser.get(google_images_url)
    except (Exception) as err:
        print(err)
if browser is None:
    try:
        browser = webdriver.Edge()
        browser.get(google_images_url)
    except (Exception) as err:
        print(err)
if browser is None:
    raise SystemExit(
        "Browser is not available or Webdriver is not set up properly")

Navigation in Google Image Search

Now, for this, we will be waiting for few elements to load completely, before we click on that.
For this reason, we will define a re-usable method, which we will reuse later.

def wait_for_element(driver, byType, byValue, maxWait: int):
    """
    This method, takes properties of an element and looks for the element in page.
    if the element is found, it will return the element else None is returned

    Args:
        driver ([webdriver]): [Selenium webdriver]
        byType ([By Type]): [Which property we are using to get element. ex: By.XPATH or BY.Id]
        byValue ([type]): [value of property]
        maxWait (int): [wait for element to be found]

    Returns:
        [webdriverelement]: [identified element]
    """
    try:
        element = WebDriverWait(driver, maxWait).until(
            EC.presence_of_element_located((byType, byValue)))
        return element
    except TimeoutException:
        print("Element not found")
        return None

Now the actual code for navigation, we are just getting the element and clicking the element, one by one.

dr.get(url)
print("working on file:", file)
file_name = Path(file)
image_icon = wait_for_element(dr,
                              By.XPATH, "/html/body/div[2]/div[2]/div[2]/form/div[2]/div[1]/div[1]/div/div[3]/div[2", 10)
image_icon.click()
upload_image_link = wait_for_element(dr,
                                     By.XPATH, "/html/body/div[2]/div[2]/div[2]/div/div[2]/form/div[1]/div/a", 10)
upload_image_link.click()
browse_image_button = wait_for_element(dr,
                                       By.XPATH, '//*[@id="awyMjb"]', 10)
browse_image_button.send_keys(str(images_folder_path) + "/" + file)
try:
    all_sizes_button = wait_for_element(dr,
                                            By.XPATH, '/html/body/div[7]/div[2]/div[10]/div[1]/div[2]/div/div[2]/div[1]div/div[1]/div[2]/div[2]/span[1]/a', 10)
    all_sizes_button.click()
    first_image = wait_for_element(dr,
                                       By.XPATH, '/html/body/div[2]/c-wiz/div[3]/div[1]/div/div/div/div/div[1]/div[1]/di[1]/a[1]/div[1]/img', 10)
    first_image.click()
    time.sleep(wait_time)
    preview_image_link = wait_for_element(dr,
                                              By.XPATH, '/html/body/div[2]/c-wiz/div[3]/div[2]/div[3]/div/div/div[3]/di[2]/c-wiz/div[1]/div[1]/div/div[2]/a/img', 10)
    src = preview_image_link.get_attribute('src')

Save image file

import urllib.request

urllib.request.urlretrieve(
    src, images_folder_path / highres_folder_name / file_name)
# os.renames is used to move the file, which will automatically create folders if not exits already.
os.renames(images_folder_path / file_name,
           images_folder_path / success_folder_name / file_name)
print("success for file:", file)

creating a pip package

for this we want our script to execute from command line, so we will put above codes in appropriate functions and create a handler method, then put them in a module and create a command-line entry point as follows.

Note: for simplicity, the function definition and argparse code is not included here, completed code at Github is linked at the end.

# command_line.py
from highresmodule import highres

def main():
    highres.highres_handler()

Finaly the most important pip setup code, we will use built-in setuptools to create a pip package, as follows.

# setup.py
import os
import setuptools


def read(fname):
    # for reading the description
    return open(os.path.join(os.path.dirname(__file__), fname)).read()


setuptools.setup(
    name='highres',
    version='1.0.3',
    author="Dilli Babu R",
    author_email="dillir07@outlook.com",
    description='A script to download hi-resolution images using google search by image feature',
    long_description=read('pip-readme.rst'),
    long_description_contect_type="text/markdown",
    url="https://dillir07.github.io/highres/",
    packages=['highresmodule'],
    install_requires=['selenium'], #specifying dependency
    entry_points={
        "console_scripts": ['highres=highresmodule.command_line:main']
    },
    classifiers=[
        "Programming Language :: Python :: 3",
        "Operating System :: OS Independent",
    ],
)

now, finally we can have the package created and installed locally with the following command.

python setup.py develop

Once we are okay, we can upload to pypi registry by following instructions at pip package creation

The final code is available at Github and demo at highres

As usaul comments are welcome, thanks for reading :)

Genetic Algorithm - Travelling Salesman with Julia

Dilli Babu R — Sat, 07 Nov 2020 13:00:06 +0000

Genetic Algorithm

Genetic algorithm (GA) is a type of algorithm inspired by the process of natural selection to generate high-quality solutions to problems, which otherwise would be too difficult to solve.

Travelling Salesman Problem

Travelling Salesman Problem or TSP for short, is a infamous problem where a travelling sales person has to travel various cities with known distance and return to the origin city in the shortest time/path possible.

Like below, each circle is a city and blue line is a route, visiting them.

Why not brute-force ??

Okay, lets try to brute force to solve the problem.
for starters lets take 5 cities, i.e., we have to calculate 5!, i.e., 120 routes to ensure we got the shortest path.

Now, if we are to do that for 50 cities,

5! = 120
10! = 3628800
15! = 1307674368000
20! = 2432902008176640000
50! = 30414093201713378043612608166064768844377641568960512000000000000

We can see how brute forcing our way is simply not going to be helpful here.

Let's try GA

So, we will see how Genetic Algorithm can help us find a optimal shortest path here.

In simple, Genetic Algorithm works the following way,

Choosing Random initial solutions/chromosomes (Called as Initial Population or Chromosomes)
crossover (generating new solution or chromosome, by kind of mixing two parent chromosomes/solutions)
mutate (making a minor change in the solution)
fitness (checking if the solution is useful or fullfills our requirement), if yes, we use them to create new offsprings (parents in next generation) and the cycle continues for an many generations we want.

So.. for our TSP problem, we will do the following:

Generate Cities

function generate_cities(number_of_cities, map_limit)

    cities = []
    for city_counter in 1:number_of_cities
        push!(cities, 
            Dict(
                "id" => city_counter, 
                "x" => round(rand() * map_limit), 
                "y" => round(rand() * map_limit)
            )
        )
    end
    println("Cities Generated:", size(cities)[1])
    return cities
end
# calling generate_cities method to create cities
generate_cities(5,500)

We are storing the city as a Dictionary.

Each city has an id, and (x,y) location

 ("id" => 1,"x" => 480.0,"y" => 157.0)
 ("id" => 2,"x" => 4.0,"y" => 465.0)
 ("id" => 3,"x" => 57.0,"y" => 25.0)
 ("id" => 4,"x" => 411.0,"y" => 322.0)
 ("id" => 5,"x" => 44.0,"y" => 460.0)

Representing the solution as chromosome.

The solution for our problem is a route from one city to another city. We can write it as an array of integers, where each number represents a city id.

[1,2,5,4,3,1]

So, for above mentioned route or chromosome, we are starting from city1 -> city 2 and so on... finally coming back to city1.

Crossover function

Here, we generate a new chromosome by taking values from two parent chromosomes.
For this problem we simply have to ensure the genes/city id is not getting repeated, while generating new chromosome.

There are many ways to do a crossover like, Unipoint crossover, multi-point crossover, etc.
We will do a unipoint crossover, simply by choosing a random point in chromosome and doing a simple swap to create new chromosome.

function crossover(parent_one_chromosome, parent_two_chromosome, crossover_point)
    offspring_part_one = parent_one_chromosome[1:crossover_point]
    for gene in offspring_part_one
        if gene in parent_two_chromosome
            gene_loc = findfirst(el -> el == gene, parent_two_chromosome)
            splice!(parent_two_chromosome, gene_loc)
        end
    end
    return vcat(offspring_part_one, parent_two_chromosome)
end

Mutation function

In simple terms mutation can be defined as making a random change in the chromosome.
Here we will simply swap two gene's positions.

function mutate(offspring)
    random_mutation_point1 = rand(1:length(offspring))
    random_mutation_point2 = rand(1:length(offspring))
    offspring[random_mutation_point1], offspring[random_mutation_point2] = offspring[random_mutation_point2], offspring[random_mutation_point1]
    return offspring
end

Fitness function

Fitness function's responsibility is to calculate each chromosome's score, so that we can decide if we want to use this
chromosome in next generation or to discard.

For our problem, the score is the travel distance for a given route/chromosome. The lower the travel distance the better.

To calculate the travel distance, we simple start from 1st city, go to next and then to next, so..on and return to origin city, by adding the distance we travelled, we get the score of this particular route.

function calculate_distance_between_two_points(point1, point2)
    return sqrt((((point2[1] - point1[1]))^2) + (((point2[2] - point1[2]))^2))
end

function calculate_chromosome_travel_distance(chromosome)
    travel_distance = 0
    chromosome = vcat(1, chromosome, 1)
    for geneId in 1:length(chromosome) - 1
        point1 = (
            cities[chromosome[geneId]]["x"],
            cities[chromosome[geneId]]["y"]
            )
        point2 = (
            cities[chromosome[geneId + 1]]["x"],
            cities[chromosome[geneId + 1]]["y"]
            )
        travel_distance += calculate_distance_between_two_points(point1, point2)
    end
    println("travel distance:", chromosome, " : ", travel_distance)
    return travel_distance
end

Generating intial population:

We will define a function that can generate initial populations.

# We shuffle the chromosome here
function shuffle_chromosome(chromosome)
    for i in 1:size(chromosome)[1]
        random_point = rand(1:5, 1)[1]
        chromosome[i], chromosome[random_point] = chromosome[random_point], chromosome[i]
    end

    println("Created chromosome", chromosome)
    return chromosome
end


function generate_initial_population(initial_population_size)
    chromosomes = []
    for population_counter in 1:initial_population_size
        chromosome = shuffle_chromosome(copy(initial_chromosome))
        push!(chromosomes, 
            Dict(
                "chromosome" => chromosome,
                "distance" => calculate_chromosome_travel_distance(chromosome)
            )
        )
    end
    return chromosomes
end

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

main part

Here, we have defined a function, which run GA for given number of generations, and creates given number of offsprings for each generation, then checks it's fitness and the cycle continues for each generation.

function evolve(generation_count, offsprings_count, crossover_point)
    for generation in 1:generation_count

        for offspring_count in 1:offsprings_count
            println("generation: ", generation, " offspring: ", offspring_count)
            random_parent_one_id = rand(1:size(chromosomes)[1])
            random_parent_two_id = rand(1:size(chromosomes)[1])
            random_parent_one = copy(chromosomes[random_parent_one_id]["chromosome"])
            random_parent_two = copy(chromosomes[random_parent_two_id]["chromosome"])
            offspring = crossover(random_parent_one, random_parent_two, crossover_point)
            offspring = mutate(offspring)
            push!(chromosomes, 
                Dict(
                    "chromosome" => offspring,
                    "distance" => calculate_chromosome_travel_distance(offspring)
                    )
            )
        end
        sort!(chromosomes, by=x -> x["distance"], rev=false)
        splice!(chromosomes, 6:size(chromosomes)[1])
    end
end

Now, lets execute the GA

# creating 10 cities randomly
cities = generate_cities(10, 500)
initial_chromosome = [2:length(cities);]
# generating 10 initial chromosomes
chromosomes = generate_initial_population(10)

# we are running GA for
# 5 generations
# 5 offsprings per generation
# random crossover point as 2
evolve(5, 5, 2)
println("--------------------------------------------------------")
println("Optimal route:", vcat(1, chromosomes[1]["chromosome"], 1))
println("travel_distance:", chromosomes[1]["distance"])

If we execute, we get the following output.

output:

generation: 1 offspring: 1
travel distance:[1, 3, 9, 10, 7, 5, 4, 6, 8, 2, 1] : 2780.551726305925
generation: 1 offspring: 2
travel distance:[1, 5, 10, 6, 9, 3, 2, 4, 7, 8, 1] : 2236.035984494435
generation: 1 offspring: 3
travel distance:[1, 10, 7, 3, 9, 5, 4, 6, 8, 2, 1] : 2627.3533869849102
generation: 1 offspring: 4
travel distance:[1, 7, 6, 4, 10, 3, 5, 2, 8, 9, 1] : 3078.2871083508203
generation: 1 offspring: 5
travel distance:[1, 3, 9, 10, 7, 2, 4, 5, 8, 6, 1] : 3074.581278954089
generation: 2 offspring: 1
travel distance:[1, 9, 8, 5, 10, 4, 3, 2, 6, 7, 1] : 2882.8847896850843
generation: 2 offspring: 2
travel distance:[1, 5, 10, 6, 2, 3, 9, 4, 7, 8, 1] : 1864.9566066991729
generation: 2 offspring: 3
travel distance:[1, 9, 8, 5, 10, 2, 3, 4, 6, 7, 1] : 2889.200659672017
generation: 2 offspring: 4
travel distance:[1, 4, 10, 6, 9, 3, 2, 5, 7, 8, 1] : 2520.4527035595024
generation: 2 offspring: 5
travel distance:[1, 9, 10, 6, 3, 5, 2, 4, 7, 8, 1] : 2443.441192706744
generation: 3 offspring: 1
travel distance:[1, 2, 10, 6, 9, 8, 5, 7, 4, 3, 1] : 2177.1886229349225
generation: 3 offspring: 2
travel distance:[1, 2, 10, 5, 6, 9, 8, 7, 4, 3, 1] : 1745.6328718972204
generation: 3 offspring: 3
travel distance:[1, 5, 4, 2, 6, 9, 8, 7, 10, 3, 1] : 2491.210252809206
generation: 3 offspring: 4
travel distance:[1, 7, 5, 6, 9, 3, 2, 4, 10, 8, 1] : 2867.790574182069
generation: 3 offspring: 5
travel distance:[1, 10, 6, 5, 9, 3, 2, 7, 4, 8, 1] : 2158.331962819929
generation: 4 offspring: 1
travel distance:[1, 4, 10, 6, 2, 3, 9, 5, 7, 8, 1] : 2375.395804596975
generation: 4 offspring: 2
travel distance:[1, 4, 10, 2, 6, 9, 8, 5, 7, 3, 1] : 2696.2819714580255
generation: 4 offspring: 3
travel distance:[1, 5, 3, 6, 9, 10, 2, 7, 4, 8, 1] : 2585.1841206421177
generation: 4 offspring: 4
travel distance:[1, 4, 6, 2, 9, 8, 5, 7, 10, 3, 1] : 2927.589295286965
generation: 4 offspring: 5
travel distance:[1, 5, 3, 10, 6, 9, 7, 2, 4, 8, 1] : 2610.376635133937
generation: 5 offspring: 1
travel distance:[1, 3, 10, 5, 6, 9, 8, 7, 4, 2, 1] : 1919.461172591361
generation: 5 offspring: 2
travel distance:[1, 10, 6, 8, 9, 3, 2, 7, 4, 5, 1] : 2488.399757690674
generation: 5 offspring: 3
travel distance:[1, 6, 10, 3, 5, 9, 8, 7, 4, 2, 1] : 1962.725547491429
generation: 5 offspring: 4
travel distance:[1, 10, 6, 8, 9, 4, 2, 7, 3, 5, 1] : 2626.455096698985
generation: 5 offspring: 5
travel distance:[1, 2, 6, 5, 10, 3, 9, 4, 7, 8, 1] : 1631.463753062698
--------------------------------------------------------
Optimal route:[1, 2, 6, 5, 10, 3, 9, 4, 7, 8, 1]
travel_distance:1631.463753062698

I have created a TSP-GA playground using Typescript, checkout if you want to playaround: https://dillir07.github.io/Genetic-Algorithm-TSP/

Julia - Source code is available at Github

Thank for reading :)... Comments are welcome.

Tron game 🏍️ - A Combinatorial search in python

Dilli Babu R — Sat, 10 Oct 2020 18:42:00 +0000

About Tron game:

Tron is a two player game based on the popular movie Tron. The objective of the game is to cut off players movement through each others motorbikes that leave a wall behind them as they move.

Like this:

I came across this question in Hackerrank, where our programs will read the players position at each turn and will decide the movement, by printing one of (LEFT, RIGHT, UP, DOWN) to the console, and we can see the result visually.

Before we go further, I should tell you that the solution below is a naive and basic approach (scored 36/50) and there are a lot of algorithms available that provide better results.

Now the input we get are:

player's turn
bot player's current positions
the whole grid (15x15) values

Input is:

r
4 3 5 13
###############
#-rr--------gg#
#-rr--------gg#
#-rr--------gg#
#-rr--------gg#
#-r---------g-#
#-r---------gg#
#rr----------g#
#-------------#
#-------------#
#-------------#
#-------------#
#-------------#
#-------------#
###############

We will read the grid into a matrix like representation, where grid[0][1] means 1st row's second column.

Now the actual code ...
First reading the input part:

current_player =  input() # player_id (whose turn is it)

# here we are reading both players' positions
player_pos = input().split(" ")
player_pos = list(map(int, player_pos))
rpos = [player_pos[0], player_pos[1]]
gpos = [player_pos[2], player_pos[3]]
grid_size = 15

grid = [] # reading grid into an array
for gr in range(grid_size):
    grid.append(input())

Now to the important part, we have the player's current positions and where they went earlier from the grid, using this information we have to decide what direction we choose to move ahead by one step, so that we can avoid getting trapped and trap other opponents.

The following code, calculates how much free (movable) space available at each direction and chooses the direction which has the most free space. (Hoping it can help avoid traps), this is done at each iteration.

lets write code to calculate the free space...

# Here were writing code, that actually makes the decision
def calculate_free_steps(grid, pos):
    """
    Reads the current grid state, and current player's position
    and returns a dictionary with free spaces in each direction.
    returns: {"LEFT":4, "RIGHT":5, "UP":9, "DOWN":0}
    """
    # we are initializing the free steps
    # l = free steps available in left direction
    l = r = u = d = 0

    # We're calculating free steps in each direction
    # i.e., places in grid having '-' as value

    # reading player's current row & current column values
    row, col = pos[0]-1, pos[1]

    # calculating free steps in upward direction
    # if row is > 0, we can try to go 'UP'
    while row > 0:
        # if cell is '-', increment up_free_steps
        if grid[row][col] == "-":
            u += 1
            row -= 1 # go to top row
        else: # if cell is not '-' means it's not free
            break # so break the loop

    # do the same for 'DOWN'
    row, col = pos[0]+1, pos[1]
    # calculating free steps available in 'DOWN' direction       
    while row < len(grid):
        if grid[row][col] == "-":
            d += 1
            row += 1
        else:
            break

    # now for 'RIGHT'
    row, col = pos[0], pos[1]+1
    while col < len(grid[0]): #right
        if grid[row][col] == "-":
            r += 1
            col += 1
        else:
            break

    # and finally for 'LEFT'
    row, col = pos[0], pos[1]-1
    while col > 0: # left
        if grid[row][col] == "-":
            l += 1
            col -= 1
        else:
            break

    # returning the free steps for each direction
    return {"LEFT":l, "RIGHT":r, "UP":u, "DOWN":d}

Now to the final and main part of the code..

We have the free steps available in each direction, how do we choose which direction to go...🤔🤔🤔?

For simplicity we will just pick the direction which has most free steps.

🙏 Do note this is not an ideal solution, comments are welcome. 🙏

direction_to_go = None # initially unknown
free_steps_available = 0

# read the current player's position
ppos = rpos if current_player == "r" else gpos

# calling the method we created above
free_steps_data = calculate_free_steps(grid, ppos)

# looping each direction
# and choosing the one with max free steps
for direction in free_steps_data:
    if free_steps_data[direction] > free_steps_available:
        direction_to_go = direction
        free_steps_available = free_steps_data[direction]

# finally printing to the console
print(direction_to_go)

output will be like:

DOWN

Following are the couple of visualization of the game (We are blue)

Won:

Lost:

Author (orange) written a nice algorithm to fill as much space as possible by avoiding opponent, so opponents can run out of space and trap themselves.

Thank you for reading.. comments & suggestions are welcome.

Here is how Python list's memory size changes w.r.t it's length

Dilli Babu R — Sat, 01 Feb 2020 14:24:13 +0000

We use python's Lists pretty much everywhere. Since we don't declare it's size and we just add items, Ever wondered how and when the memory allocation and consumption is done under the hood?

Lets analyze the same now, for that we need...

sys package to get the list size
matplotlib for plotting graphs

import sys
from matplotlib import pyplot as plt

Lets print and see the length and memory of our list for 10 items.

l = [] # our list
size = 10

# here we are just adding some values to our list

for counter in range(size):
    l.append(counter)
    print("length {}, memory in bytes {}".format(
        length[counter], memory[counter]))

We can see the following in console.

length 1, memory in bytes 96
length 2, memory in bytes 96
length 3, memory in bytes 96
length 4, memory in bytes 96
length 5, memory in bytes 128
length 6, memory in bytes 128
length 7, memory in bytes 128
length 8, memory in bytes 128
length 9, memory in bytes 192
length 10, memory in bytes 192

We can see that after about 4 iterations each time, the memory is increased.
Now lets increase the loop counter to 1000 and graph it out...

size = 1000 # increasing the size
length = [] # to hold lengths at each iteration
memory = [] # to hold memory values at each iteration

And then change the for loop

for counter in range(size):
    l.append(counter)
    # capture and store the length
    length.append(len(l)) 
    # Capture and store the memory in bytes
    memory.append(sys.getsizeof(l))

Now lets plot the graph using the captured values and see what is shows.

plt.plot(length, memory)
plt.title("Python List length - Memory comparison")
plt.xlabel("Length")
plt.ylabel("Memory in bytes")
plt.show()

We can see that when ever list is running out of size, its getting added with additional memory.

Now, Lets change the code to capture the difference in memory only when there is a change.

# declaring two more lists
counter_at_which_memory_changed = []
changed_memory_difference = []

and changing the for loop as follows

for counter in range(size):
    l.append(counter)
    # capture and store the length
    length.append(len(l))
    # Capture and store the memory in bytes
    memory.append(sys.getsizeof(l))

    if memory[counter] != memory[counter - 1]:
        counter_at_which_memory_changed.append(counter)
        changed_memory_difference.append(
            memory[counter] - memory[counter - 1])

# Lets try checking the first 10 values of length and difference in memory

for counter in range(10):
    print("at list length {}, memory increase in bytes {}".format(
        counter_at_which_memory_changed[counter],
        changed_memory_difference[counter]))

The first 10 values of memory changes is as follows.

at list length 4, memory increase in bytes 32
at list length 8, memory increase in bytes 64
at list length 16, memory increase in bytes 72
at list length 25, memory increase in bytes 80
at list length 35, memory increase in bytes 88
at list length 46, memory increase in bytes 96
at list length 58, memory increase in bytes 112
at list length 72, memory increase in bytes 128
at list length 88, memory increase in bytes 144
at list length 106, memory increase in bytes 160

# And the graph for index - memory difference is as follows
plt.plot(counter_at_which_memory_changed, changed_memory_difference)
plt.title("Counter - Memory difference")
plt.xlabel("Counter")
plt.ylabel("Memory difference")
plt.show()

So, by checking the difference we can see that the memory increase is follows..
8, 8, 8, 8, 16, 16, 16, 16, 16, 24, 24, 32, 32, 32, 40, 48, 48, 56, 64, 72, 88, 88, 104, 112.

Thanks for your time, this is my first post. Comments are welcome :)