Sunday, April 21, 2024

City Planning using k-means clustering algorithm

Problem

Given a city with coordinates of n houses, find the most optimal location for k hospitals so that the mean distance required to be traveled by the residents of the city is minimum.

Input

n (0 < n <= 100)
(x, y) coordinates of n houses
k (0 < n <= 5)

Output

k coordinates representing the locations of the hospitals.

Solution

This problem can be solved by using the k-means clustering algorithm which involves finding clusters in a scatter plot based on the condition that the mean distance of the points in a cluster from the cluster centroid is minimum
 

Python Code

import math
import random
import matplotlib.pyplot as plt
import matplotlib.collections as mcoll
import time

def generate_random_points(n):
    points = []
    for _ in range(n):
        x = random.uniform(0, 100)
        y = random.uniform(0, 100)
        points.append((x, y))
    return points

def calculate_mean_distance(points, centroids):
    total_distance = 0
    for x, y in points:
        min_distance = float('inf')
        for cx, cy in centroids:
            distance = math.sqrt((x - cx) ** 2 + (y - cy) ** 2)
            min_distance = min(min_distance, distance)
        total_distance += min_distance
    return total_distance / len(points)

'''
This method starts with k centroids randomly chosen from the given coordinates.
It then 
'''
def k_means(points, k):
    centroids = random.sample(points, k)
    iterations = 0
    while True:
        iterations += 1
        clusters = [[] for _ in range(k)]
        for x, y in points:
            min_distance = float('inf')
            closest_centroid = None
            for i, (cx, cy) in enumerate(centroids):
                distance = math.sqrt((x - cx) ** 2 + (y - cy) ** 2)
                if distance < min_distance:
                    min_distance = distance
                    closest_centroid = i
            clusters[closest_centroid].append((x, y))
        new_centroids = []
        for cluster in clusters:
            x_sum = sum(x for x, y in cluster)
            y_sum = sum(y for x, y in cluster)
            new_centroids.append((x_sum / len(cluster), y_sum / len(cluster)))
        if new_centroids == centroids:
            break
        centroids = new_centroids
        plot_iteration(points, centroids, clusters, iterations)
        time.sleep(1)  # Pause for 1 second
    return centroids, clusters

def plot_iteration(points, centroids, clusters, iteration):
    plt.clf()  # Clear the previous plot
    colors = ['b', 'g', 'r', 'c', 'm']  # Colors for clusters

    # Plot the random points
    x_coords, y_coords = zip(*points)
    plt.scatter(x_coords, y_coords, c='k', marker='o', s=10, alpha=0.5, label='Random Points')

    # Plot the centroids
    centroid_x, centroid_y = zip(*centroids)
    plt.scatter(centroid_x, centroid_y, c='r', marker='*', s=100, label='Centroids')

    # Plot the line segments and clusters
    for i, cluster in enumerate(clusters):
        x_coords, y_coords = zip(*cluster)
        plt.scatter(x_coords, y_coords, c=colors[i], marker='o', label=f'Cluster {i+1}', alpha=0.5)
        line_segments = []
        for x, y in cluster:
            line_segments.append([(x, y), (centroids[i][0], centroids[i][1])])
        line_collection = mcoll.LineCollection(line_segments, colors=colors[i], linewidths=0.5, alpha=0.5)
        plt.gca().add_collection(line_collection)

    plt.xlim(0, 100)
    plt.ylim(0, 100)
    plt.title(f'Iteration {iteration}')
    plt.xlabel('X')
    plt.ylabel('Y')
    plt.grid(True)
    plt.legend()
    plt.pause(0.01)  # Pause for a brief moment to update the plot

# Example usage
n = 100  # Number of random points
k = 5    # Number of centroids to find
points = generate_random_points(n)
centroids, clusters = k_means(points, k)
mean_distance = calculate_mean_distance(points, centroids)
print(f"Mean distance of {k} centroids from {n} points: {mean_distance:.2f}")

# Plot the final points, centroids, and line segments
plt.figure(figsize=(8, 6))
colors = ['b', 'g', 'r', 'c', 'm']  # Colors for clusters

for i, cluster in enumerate(clusters):
    x_coords, y_coords = zip(*cluster)
    plt.scatter(x_coords, y_coords, c=colors[i], marker='o', label=f'Cluster {i+1}', alpha=0.5)
    centroid_x, centroid_y = centroids[i]
    plt.scatter(centroid_x, centroid_y, c='k', marker='*', s=100)
    line_segments = []
    for x, y in cluster:
        line_segments.append([(x, y), (centroid_x, centroid_y)])
    line_collection = mcoll.LineCollection(line_segments, colors=colors[i], linewidths=0.5, alpha=0.5)
    plt.gca().add_collection(line_collection)

plt.xlim(0, 100)
plt.ylim(0, 100)
plt.title('Random Points, Centroids, and Line Segments')
plt.xlabel('X')
plt.ylabel('Y')
plt.grid(True)
plt.legend()
plt.show()
  
 
The above code requires matplotlib library to be installed. 

Scatter Plot

The circles represent the coordinates of the houses, stars represent the cluster centroids (or hospitals) and the line segments represent the nearest centroid.

Saturday, April 13, 2024

Sliding Window Mean and Standard Deviation Calculation and Visualization


 

1. Create a folder named sliding-window.

2. Create a file named script.js inside the folder and paste the following content:

function id(id) { 
    return document.getElementById(id); 
} 
var count = 0; 
var pattern, text, Psize, Tsize; 
var idcountrater = 0; 
var conti = 0; 
const slidingWindowTech = async (pattern, Psize, sum, k) => { 
    console.log("hola") 
    var max_sum = 0; 
    let maxi = document.createElement('div'); 
    maxi.id = "message"; 
    maxi.classList.add("message"); 
    maxi.innerText = `Fluidity incident count is ${max_sum}` 
    console.log(maxi) 
    id("pattern_text").appendChild(maxi); 
    console.log(`Setting incidenetActive to false`);
    let incidentActive = false;
    let current_sum = 0; 
    let windowMean = 0;
    let windowSD = 0;
    let current = document.createElement('div'); 
    current.id = "message"; 
    current.classList.add("message"); 
    current.innerText = `CurrentSum is ${current_sum}` 
    id("pattern_text").appendChild(current);

    let mean = document.createElement('div');
    mean.id = "message";
    mean.classList.add("message");
    mean.innerText = `Mean is ${current_sum}`
    id("pattern_text").appendChild(mean);

    let sd = document.createElement('div');
    sd.id = "message";
    sd.classList.add("message");
    sd.innerText = `SD is ${current_sum}`
    id("pattern_text").appendChild(sd);

    let upfd = document.createElement('div');
    upfd.id = "message";
    upfd.classList.add("message");
    upfd.innerText = `UPFD (Mean + 2SD) is ${current_sum}`
    id("pattern_text").appendChild(upfd);

    for (let i = 0; i < Psize - k + 1; i++) { 
        await new Promise((resolve) => 
            setTimeout(() => { 
                resolve(); 
            }, 1000) 
        ) 
        console.log(i + " " + (i + k - 1)); 
        id(i).style.borderLeft = "2px solid white"
        id(i).style.borderTop = "2px solid white"
        id(i).style.borderBottom = "2px solid white"
        id(i + 1).style.borderBottom = "2px solid white"
        id(i + 1).style.borderTop = "2px solid white"
        id(i + 2).style.borderTop = "2px solid white"
        id(i + 2).style.borderBottom = "2px solid white"
        id((i + k - 1)).style.borderRight = "2px solid white"; 
        id(i + k - 1).style.borderTop = "2px solid white"
        id(i + k - 1).style.borderBottom = "2px solid white"
        if (i != 0) { 
            // current_sum=current_sum-pattern[i-1] 
            id(i - 1).style.color = "Red"
            await new Promise((resolve) => 
                setTimeout(() => { 
                    resolve(); 
                }, 1000) 
            ) 
            current_sum = current_sum - pattern[i - 1] 
            current.innerText = 
                `CurrentSum after subtracting ${i - 1}th ` + 
                `element from ${i} window is ${current_sum}` 
            id(i - 1).style.color = "white"
            await new Promise((resolve) => 
                setTimeout(() => { 
                    resolve(); 
                }, 1000) 
            ) 
            id(i + k - 1).style.color = "green"
            await new Promise((resolve) => 
                setTimeout(() => { 
                    resolve(); 
                }, 1000) 
            ) 
            current_sum = current_sum + pattern[i + k - 1] 
            current.innerText = 
`CurrentSum after adding ${i + k - 1}th in ${i} window is ${current_sum}` 
            windowMean = current_sum / k;
            mean.innerText = `Current mean is ${windowMean}`

            // Compute window standard deviation
            squared_sum = 0;
            for (let j = i; j < i + k; j++) {
                squared_sum += (pattern[j] - windowMean)*(pattern[j] - windowMean);
            }
            windowSD = Math.sqrt(squared_sum / k);
            sd.innerText = `Current SD is ${windowSD}`
            upfd.innerText = `Current UPFD is ${windowMean + 2 * windowSD}`
            id(i + k - 1).style.color = "white"
            await new Promise((resolve) => 
                setTimeout(() => { 
                    resolve(); 
                }, 1000) 
            ) 
        } 
        else { 
            for (let j = 0; j < k; j++) { 
                console.log("hola 1 " + current_sum) 
                id((i + j)).style.color = "Red"
                await new Promise((resolve) => 
                    setTimeout(() => { 
                        resolve(); 
                    }, 1000) 
                ) 
                current_sum = current_sum + pattern[i + j]; 
                current.innerText = 
                    `CurrentSum is for ${i}th window ${current_sum}` 
                await new Promise((resolve) => 
                    setTimeout(() => { 
                        resolve(); 
                    }, 1000) 
                ) 
                id((i + j)).style.color = "white"
            } 
            windowMean = current_sum / k;
            mean.innerText = `Current mean is ${windowMean}`

            // Compute window standard deviation
            squared_sum = 0;
            for (let j = i; j < i + k; j++) {
                squared_sum += (pattern[j] - windowMean)*(pattern[j] - windowMean);
            }
            windowSD = Math.sqrt(squared_sum / k);
            console.log(`Current Mean here is ${windowMean}`) 
            sd.innerText = `Current SD is ${windowSD}`
            upfd.innerText = `Current UPFD is ${windowMean + 2 * windowSD}`
        } 
        id(i).style.borderLeft = "none"
        id(i).style.borderTop = "none"
        id(i).style.borderBottom = "none"
        id(i + 1).style.borderBottom = "none"
        id(i + 1).style.borderTop = "none"
        id(i + 2).style.borderTop = "none"
        id(i + 2).style.borderBottom = "none"
        id((i + k - 1)).style.borderRight = "none"; 
        id(i + k - 1).style.borderTop = "none"
        id(i + k - 1).style.borderBottom = "none"
        //console.log(current_sum) 
        // Update result if required. 
        // max_sum = max(current_sum, max_sum); 
        //if (current_sum > max_sum) max_sum = current_sum; 

        // Report one incident when and until UPFD is above threshold.
        console.log(`incidentActive is ${incidentActive}`)
        if (windowMean + 2 * windowSD > 16 && !incidentActive) {
            max_sum += 1;
            incidentActive = true;
            console.log(`Setting incidentActive to true`)
        }
        // Reset once UPFD is back to normal
        if (incidentActive && windowMean + 2 * windowSD <= 16) {
            incidentActive = false;
        }
        maxi.innerText = `Fluidity incident count is ${max_sum}` 
    } 
    current.style.display = "none"
} 
let idcount = 0; 
window.onload = async () => { 
    id("displayer").style.display = "none"; 
    id("start").addEventListener('click', () => { 
        id("start").style.display = "none"
        id("displayer").style.display = "flex"; 
        //pattern = [16, 16, 16, 32, 16, 16, 16, 16, 16, 32, 16, 16, 16] 
        pattern = [32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32] 
        Psize = 13
        sum = 24 
        let idcount1 = 0; 
        for (let i = 0; i < Psize; i++) { 
            let tile = document.createElement('span'); 
            tile.id = idcount; 
            tile.classList.add("tile"); 
            tile.innerText = pattern[i]; 
            id("pattern").appendChild(tile); 
            idcount++; 
        } 
        slidingWindowTech(pattern, Psize, sum, 4) 
    }) 
}

3. Create a file named style.css and paste the following content:

* { 
    color: white; 
    font-family: "Open sans", sans-serif; 
} 
  
html { 
    background-color: black; 
} 
  
body { 
    display: flex; 
    flex-direction: column; 
    align-items: center; 
    height: 100vmin; 
} 
  
h1 span { 
    font-size: 6vmin; 
    font-weight: normal; 
    text-shadow: 0 0 20px cyan, 
        0 0 40px cyan, 
        0 0 80px cyan; 
} 
  
#container { 
    display: flex; 
    flex-direction: column; 
    align-items: center; 
    justify-content: center; 
    height: 80%; 
    width: 80%; 
} 
  
#displayer { 
    display: flex; 
    flex-direction: column; 
    align-items: center; 
    width: 100%; 
    height: 90%; 
} 
  
#pattern, 
#message { 
    width: 100%; 
    height: 7vmin; 
    margin: 3vmin; 
    font-size: 5vmin; 
    display: flex; 
    align-items: center; 
    justify-content: center; 
} 
  
#message { 
    color: cyan; 
    font-size: 2vmin; 
} 
  
#pattern_text { 
    width: 100%; 
    height: 5vmin; 
    margin: 3vmin; 
    font-size: 5vmin; 
    display: flex; 
    align-items: center; 
    justify-content: center; 
    color: g; 
} 
  
#pattern_text { 
    width: 100%; 
    height: 5vmin; 
    margin: 3vmin; 
    font-size: 5vmin; 
    display: flex; 
    align-items: center; 
    justify-content: center; 
    color: g; 
} 
  
.tile { 
    width: 6vmin; 
    height: 6vmin; 
    margin: 10px; 
    text-align: center; 
    height: fit-content; 
    border: 2px pink; 
} 
  
#start { 
    align-self: center; 
    background-color: black; 
    font-size: 3vmin; 
    box-sizing: border-box; 
    padding: 1vmin; 
    color: white; 
    cursor: pointer; 
    border: none; 
    margin-top: 2vmin; 
    transition: 0.5s ease-in-out; 
    font-weight: bold; 
    letter-spacing: 4px; 
} 
  
#start:hover { 
    transform: scale(1.5); 
    text-shadow: 0 0 10px cyan, 
        0 0 20px cyan, 
        0 0 40px cyan; 
} 
  
h1 { 
    margin-top: 0; 
    text-align: center; 
    padding: 1vmin; 
    margin-bottom: 1vmin; 
    width: 100%; 
    font-size: 5vmin; 
    font-weight: normal; 
    letter-spacing: 2px; 
    border-bottom: 1px solid white; 
}

4. Create a file named index.html and paste the following content:


<!DOCTYPE html>
<html lang="en">
 
<head>
    <meta name="viewport" content=
        "width=device-width, initial-scale=1.0">
    <link href=
"https://fonts.googleapis.com/css2?family=Open+Sans:wght@300&display=swap"
          rel="stylesheet" />
    <link rel="stylesheet" href="style.css">
    <script src="script.js"></script>
    <title>Document</title>
</head>
 
<body>
    <h1>
        <span class="1">S</span>liding  
        <span class="2">W</span>indow  
        <span class="3">T</span>echnique
        <span>Visualizer</span>
    </h1>
    <div id="message">
        We will find the mean and UPFD using  
        sliding window technique in certain sized  
        window when window size is 4
    </div>
    <div id="threshold">
        <table>
            <tr>
                <td>Metric</td>
                <td>Expected Value</td>
            </tr>
            <tr>
                <td>Rolling FPS</td>
                <td>60</td>
            </tr>
            <tr>
                <td>Rolling UPFD</td>
                <td>16</td>
            </tr>
        </table>
    </div>
    <div id="container">
        <div id="displayer">
            <div id="pattern"></div>
            <div id="pattern_text"></div>
        </div>
          
        <div id="start">Begin</div>
    </div>
</body>
 
</html>

5. Open index.html in a Browser and click Begin button.


 

Sunday, June 11, 2023

Very nice iOS Development Resources

Creating a graph with Quartz 2D: http://www.sitepoint.com/creating-a-graph-with-quartz-2d/

 

Monday, October 10, 2022

Shell Script to detect events in ADB Logcat in a loop

The following shell script performs an action (tap) on the screen, then checks that a particular event does not happen on the device. It then performs another action (press back button) and then checks the target event happens only once. Then it closes a process and iterates through the same steps in a loop 50 times.

#!/bin/sh

# Clean up any reminiscent from previous run of the script
rm -rf script_logs
mkdir script_logs
for i in {1..50}
do
	echo $i
	echo "Clearing device logs"
	adb logcat -c
	echo "Starting log recording"
	adb logcat >> script_logs/script_logs$i.txt &
	logcat_pid=$!
	echo "Clicking at a point on the screen"
	adb shell input tap 200 300
	echo "Waiting for 4 seconds for event to happen and logs generated"
	sleep 4
	events=`grep "<log_pattern>" script_logs/script_logs$i.txt | wc -l`
	if [ $events == 0 ]
	then
		echo "No event found"
	else
		echo "$events were found, the test failed"
		kill -9 $logcat_pid
		exit 1
	fi
	adb shell input keyevent KEYCODE_BACK
	echo "Waiting for 4 seconds for another event"
	sleep 4
	echo "Checking how many events were sent"
	events=`grep "<log_pattern>" script_logs/script_logs$i.txt | wc -l`
	if [ $events == 1 ]
	then
		echo "One and only one event was found"
	else
		echo "$events were found, the test failed"
		kill -9 $logcat_pid
		exit 1
	fi
	echo "Killing target process"
	pid=`adb shell pidof <process_name>`
	adb shell kill -9 $pid
	echo "Stopping logcat"
	kill -9 $logcat_pid
	sleep 2
done

Pass by Pointer vs Pass by Reference in C++

Variables can be passed by pointer and by reference. Both produce the same result and have the same effect on the arguments passed in the calling function. The difference is that the pointer stores the address to a variable whereas a reference refers to an existing variable in a different name.

Reference: https://www.tutorialspoint.com/passing-by-pointer-vs-passing-by-reference-in-cplusplus

Pass by Pointer:

Code: 
#include <iostream>

using namespace std;

void swapNum(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int main()
{
    int i = 1;
    int j = 2;
    cout << "Before swapping " << i << " " << j << endl;
    swapNum(&i, &j);
    cout << "After swapping " << i << " " << j << endl;
    return 0;
}
Output:
Before swapping 1 2
After swapping 2 1

Pass by Reference:

Code: 
#include <iostream>

using namespace std;

void swapNum(int& a, int& b) {
    int t = a;
    a = b;
    b = t;
}

int main()
{
    int i = 1;
    int j = 2;
    cout << "Before swapping " << i << " " << j << endl;
    swapNum(i, j);
    cout << "After swapping " << i << " " << j << endl;
    return 0;
} 
Output:
Before swapping 1 2
After swapping 2 1  

Sunday, September 25, 2022

C++ Program for Tree Iterator

Problem

Given n-ary (n children per node) tree, write a C++ iterator to iterate over all the nodes.

Solution

Iterator Interface

One of the potential interface is as follows:

/**
* If there are more children to be traversed in the current layer
* @param index
* @return True if there are children yet to be traversed, false otherwise
*/
virtual bool hasMoreChildren(int index);

/**
* Move to child at index in a layer
* @param index
*/
virtual void moveToChildAt(int index);

/**
* Print the current node
* @param index
*/
virtual void printNode();

Implementation

For implementing the iterator, we will use a stack to keep track of the node being traversed in the tree.

private:
Node* mCurrentNode = nullptr;
std::stack<Node*> mNodeStack;
};

The mCurrentNode and mNodeStack are used in the implementation as follows:

C++ Code

bool TreeIterator::hasMoreChildren(int index) {
if (mNodeStack.empty()) return false;
mCurrentNode = mNodeStack.top();
// If no children, return false.
if (mCurrentNode->children().empty()) {
mNodeStack.pop();
if (!mNodeStack.empty()) {
mCurrentNode = mNodeStack.top();
}
return false;
}
auto it = mCurrentNode->children().begin();
it += index;
// If all children in this layer are traversed, return false.
if (it == mCurrentNode->children().end()) {
mNodeStack.pop();
if (!mNodeStack.empty()) {
mCurrentNode = mNodeStack.top();
}
return false;
}
// There are more children to be drawn, return true
return true;
}

void TreeIterator::moveToChildAt(int index) {
if (mCurrentNode->children().empty()) {
// No children, nothing to do in current layer
return;
}
auto it = mCurrentNode->children().begin();
it += index;
if (it == mCurrentNode->children().end()) {
// All children visited once, nothing to do in current layer
return;
}
mNodeStack.push(*it);
mCurrentNode = mNodeStack.top();
}

void TreeIterator::printNode() {
cout << mCurrentNode->data() << endl;
}

Using the iterator

/**
* Recursively traverse the tree hierarchy
*/
void traverse() {
int i = 0;
while (hasChildren(i)) {
moveToChildAt(i);
traverse();
i++;
}
}

int main() {
TreeIterator *it;
it->traverse();
}

Explanation

The above code is a recursively traverses the children of each node in the tree. The stack maintains the current node at the top and the index passed from the traverse() method determines how many children of a particular node have been visited.

Alternate Solutions

Alternate solutions may use the following approach.

Visitor Pattern

Yet to write a working code, but this approach would mark a node as visited once it has been traversed to keep track of which child of a particular node should be visited next.

Parent Tracking

This requires modifying the tree node to contain a pointer to the parent node so that the mCurrentNode can be moved to the parent when all the children of a particular node are visited.

Python code to find the time difference between all occurrences of a pair of events in a log file

from datetime import datetime
import re

def parse_file(filename, expression1, expression2):
    lines = tuple(open(filename, 'r'))
    expression1Found = False
    expression2Found = False
    pattern = '(0[1-9]|1[0-2])-(0[1-9]|[1-2][0-9]|3[0-1]) (2[0-3]|[01][0-9]):[0-5][0-9]:[0-5][0-9].[0-9][0-9][0-9]'

    for line in lines:
        if expression1 in line:
            timeString1 = re.search(pattern, line).group()
            expression1Found = True
        if expression2 in line:
            timeString2 = re.search(pattern, line).group()
            expression2Found = True

        if expression1Found and expression2Found:
            timePattern = '%m-%d %H:%M:%S.%f'
            epoch = datetime(1970, 1, 1)
            time1 = (datetime.strptime(timeString1, timePattern) - epoch)
            time2 = (datetime.strptime(timeString2, timePattern) - epoch)
            if int((time2 - time1).total_seconds() * 1000) > 1:
                print(int((time2 - time1).total_seconds() * 1000))

            # Reset and start searching for the next pair of occurrences of expression1 and expression2
            expression1Found = False
            expression2Found = False

if __name__ == "__main__":
    parse_file('filepath', 'even1', 'event2')