Binary Search in JavaScript

Binary Search is a computer science term used in programming and software engineering. It is a way of determining if a value exists in an ordered data set. It’s considered a textbook algorithm. It is useful because it reduces the search space by half on each iteration.

Imagine we are asked to search for an integer in an array that is sorted in ascending order. The challenge is to return the target number’s index.

binary search

We could use a built in JavaScript function indexOf():

var search = function(nums, target) {
    var answer = nums.indexOf(target);
    console.log(answer);
    return answer;
};
console.log(search([-1,0,3,4,5,9,12], 5)); // returns '4'

But that is an abstraction, which can be slow and expensive. Instead, we should implement our own binary search code.

Binary Search Implementation

Binary search starts in the middle of a collection, and checks if that is the requested term. The initial middle position is determined by taking the length of the array and dividing it by two. If the array has an even number of elements, then the ‘halfway position’ is considered close enough. I use a JavaScript Math function to round down, making sure I am not left with a decimal floating number:

cursor =  Math.floor( ((left + right) / 2) ); // about the middle

If the search term is not found, the position (the cursor) is moved. Since the collection is ordered from smallest to largest we know which direction to move the search cursor. If the target is less than the current value, we shift one to the left. If the target is greater than the current value, we shift two to the right.

This continues until the target query is found. That sequence is ran inside of a loop. The loop repeats while the left boundary is less than (or equal to) the right. The search cursor’s index is changed by adjusting the left or right bounds. Once adjusted, the cursor is recalculated on the subsequent iteration.

var search = function(nums, target) {
    var left = 0; // first element, initial left boundary
    var right = nums.length;
    right = right - 1; // last element, initial right boundary
    var cursor = 0;
    while(left <= right){
        cursor =  Math.floor( ((left + right) / 2) ); // about the middle to start
        console.log(cursor + ": " + nums[cursor]);
        if(nums[cursor] === target){
            return cursor; // query found!
        }
        if(target < nums[cursor]){
            right = cursor - 1; // move cursor to the left by one
            console.log("cursor moved to the left  by one")
        }else{
            left = cursor + 1; // move cursor to the right by two
            console.log("cursor moved to the right by two")
        }
    }
    return "false"; // not found
};
console.log(search([-1,0,1,2,3,4,5,6,7,8,9,10,11,12], 10));

The above code starts to search in the central location, nums[6] == 5. Look at the output below to see how the cursor moves until it finds the target value of 10 (at a zero-based index of 11):

binary search output

This algorithm has an O(log n) runtime complexity. That Big-O notation describes how it would scale as the input increases. Imagine an array with thousands of elements. O(log n) means that the time to execute this code will increase linearly only as the number of input items increase exponentially. That means our code is performant and efficient.

Why did the computer scientist use binary search to find his lost pencil? Because he wanted to reduce the search space by half every time he checked a desk drawer!

Magic Squares in JavaScript

magic square

In mathematics, a “magic square” is a matrix of numbers where each row, column, and diagonal add-up to the same number. That number is called the “magic constant“. The integers used are only positive, and do not repeat. The constant sum is determined by the size of the square and is described by a formula:

M = n * ((n^2 + 1) / 2)

Facts about the properties and classifications of these numeric formations have been discussed by scholars for millennia. Knowledge of this topic goes back thousands of years, and can be found referenced throughout the world.

History & Culture

Magic squares have a fascinating historical and cultural significance, often with mystical undertones. They are mentioned in the I Ching, Brhat Samhita, and other works concerned with the transcendental and occult. They can be seen used in art, divination, perfumery, recreational gaming, computer science, and more.

a computer programmer using the Brhat Samhita to generate a talismans

In the Brhat Samhita, the magic square is used as a symbolic representation of the planets. It makes use of magic squares in the creation of talismans for astrological purposes.

For the purposes of this blog post, we’ll view them through the lens of software engineering.

3×3 Magic Squares

There’s so much to cover on this topic. I’ll narrow it down to 3×3 lattices (magic squares can actually be any size), specifically in the context of the JavaScript programming language. A quad of numbers, like the one pictured above, can be described as a two-dimensional array:

const magicSquare = [[4, 9, 2], [3, 5, 7], [8, 1, 6]];

Squares of this size always have a magic constant of 15. And, the number 5 will be in the middle. There’s additional logic that explains which numerals can appear where and why. Those ideas are explored in the comments section of a HackerRank coding challenge titled “Forming a Magic Square”.

HackerRank Coding Challenge

This coding problem found on HackerRank asks programmers to figure out what it would take to convert a 3×3 matrix of integers into a magic square. The input array is almost valid, but requires a few replacements. For each change, we must track the difference between the numbers and return the total variance – referred to as the “cost”. The correct answer will be the lowest cost required to convert the input data into a magic square.

hackerrank coding challenge

The difficulty of this assignment is considered “medium”. The first step is realizing that there are a finite number of valid magic square configurations. As it turns out, there are exactly eight 3×3 permutations:

const magicSquares = [[[4, 9, 2], [3, 5, 7], [8, 1, 6]], 
                [[6, 1, 8], [7, 5, 3], [2, 9, 4]], 
                [[8, 1, 6], [3, 5, 7], [4, 9, 2]], 
                [[2, 9, 4], [7, 5, 3], [6, 1, 8]], 
                [[8, 3, 4], [1, 5, 9], [6, 7, 2]], 
                [[4, 3, 8], [9, 5, 1], [2, 7, 6]], 
                [[6, 7, 2], [1, 5, 9], [8, 3, 4]], 
                [[2, 7, 6], [9, 5, 1], [4, 3, 8]]];

Starting with any one of these, we can generate the other seven programmatically. The subsequent arrangements can be derived through rotation and reflection. Using JavaScript, I rotate an initial seed square three times to have the first four series. Then, I flip each one of those to get the final records.

function generateMagicSquares(magicSquare1){
	const magicSquares = [];
	magicSquares.push(magicSquare1);

	// we need to rotate it 3 times to get all rotations
	for(let i = 0; i < 3; i++){
		var rotation = magicSquares[i].map((val, index) => magicSquares[i].map(row => row[index]).reverse());
		// console.log(rotation)
		magicSquares.push(rotation);
	}

	// and then flip each one
	for(let i = 0; i < 4; i++){
		var flipped = magicSquares[i].map((_, colIndex) => magicSquares[i].map(row => row[colIndex]));
		magicSquares.push(flipped);
	}
	
	return magicSquares;
}

const magicSquare1 = [[4, 9, 2], [3, 5, 7], [8, 1, 6]];
const magicSquares = generateMagicSquares(magicSquare1);
console.log(magicSquares);

To solve this exercise, we’ll take the input array and compare it to each of the valid magic squares. We keep track of the cost on each iteration, and finally return the minimum.

function formingMagicSquare(s){
	const magicSquares = [[[4, 9, 2], [3, 5, 7], [8, 1, 6]], [[6, 1, 8], [7, 5, 3], [2, 9, 4]], [[8, 1, 6], [3, 5, 7], [4, 9, 2]], [[2, 9, 4], [7, 5, 3], [6, 1, 8]], [[8, 3, 4], [1, 5, 9], [6, 7, 2]], [[4, 3, 8], [9, 5, 1], [2, 7, 6]], [[6, 7, 2], [1, 5, 9], [8, 3, 4]], [[2, 7, 6], [9, 5, 1], [4, 3, 8]]];
	
	// let minCost = 100000;
	let minCost = Number.MAX_SAFE_INTEGER;
	let cost = 0;
	for(let i = 0; i < magicSquares.length; i++){
		cost = determineCost(s, magicSquares[i]);
		if(cost < minCost){
			minCost = cost;
		}
	}
	return minCost;
}

You’ll notice that the initial minimum cost is set to a very high number. As I loop through each of the valid magic squares, I check if the cost is lower than the current minimum and then replace the value.

With each comparison, subtraction is used to determine the cost to complete the transformation. That code loops through each digit of each row on both 2D arrays. The absolute value of the difference between each coordinate is tallied and returned.

function determineCost(inputArray, validMagicSquare){
	let cost = 0;
	for(let i = 0; i < 3; i++){ // each row
		
		for(let j = 0; j < 3; j++){ // each digit

			cost += Math.abs(inputArray[i][j] - validMagicSquare[i][j]);
		}
	}
	return cost;
}

The working code all stitched together looks like this:

<script>

function generateMagicSquares(magicSquare1){
	const magicSquares = [];
	magicSquares.push(magicSquare1);

	// we need to rotate it 3 times to get all rotations
	for(let i = 0; i < 3; i++){
		var rotation = magicSquares[i].map((val, index) => magicSquares[i].map(row => row[index]).reverse());
		// console.log(rotation)
		magicSquares.push(rotation);
	}

	// and then flip each one
	for(let i = 0; i < 4; i++){
		var flipped = magicSquares[i].map((_, colIndex) => magicSquares[i].map(row => row[colIndex]));
		magicSquares.push(flipped);
	}
	
	return magicSquares;
}

function determineCost(inputArray, validMagicSquare){
	let cost = 0;
	
	for(let i = 0; i < 3; i++){ // each row
		
		for(let j = 0; j < 3; j++){ // each digit

			cost += Math.abs(inputArray[i][j] - validMagicSquare[i][j]);
		}
	}

	return cost;

}

function formingMagicSquare(s){
	// const magicSquares = [[[4, 9, 2], [3, 5, 7], [8, 1, 6]], [[6, 1, 8], [7, 5, 3], [2, 9, 4]], [[8, 1, 6], [3, 5, 7], [4, 9, 2]], [[2, 9, 4], [7, 5, 3], [6, 1, 8]], [[8, 3, 4], [1, 5, 9], [6, 7, 2]], [[4, 3, 8], [9, 5, 1], [2, 7, 6]], [[6, 7, 2], [1, 5, 9], [8, 3, 4]], [[2, 7, 6], [9, 5, 1], [4, 3, 8]]];
	const magicSquare1 = [[4, 9, 2], [3, 5, 7], [8, 1, 6]];
	const magicSquares = generateMagicSquares(magicSquare1);
	
	// let minCost = 100000;
	let minCost = Number.MAX_SAFE_INTEGER;
	let cost = 0;
	for(let i = 0; i < magicSquares.length; i++){
		cost = determineCost(s, magicSquares[i]);
		if(cost < minCost){
			minCost = cost;
		}
	}
	return minCost;
}

const finalCost = formingMagicSquare([[4, 9, 2], [3, 5, 7], [8, 1, 5]]);
console.log(finalCost);
</script>

This solution was not intuitive to me and took some research and experimentation. It was interesting to learn about the concept of magic squares (and other shapes) along the way.

HackerRank challenge completed

Ideas for Engineers

Weekly inspiration

I hope you had a good weekend. As programmers and engineers, we’re always looking for inspiration. To start your week in the best place possible, I’m here to provide you with a bit of wisdom.

In this series I’ll share three ideas, two quotes, and a question. The topics I cover are usually computer science, problem solving, design improvement, and business development. If you enjoy this then be sure to sign up for my newsletter.

Ideas

Artificial Intelligence to Optimize Code

AI is rapidly becoming a programmer’s best friend. Tools like ChatGPT and GitHub Copilot can be used to develop solutions and assist engineers.

Some of my colleagues have expressed concern that this sort of technology may eventually replace the need for software engineers. I see it as a resource to increase productivity and improve quality. Read this article I wrote about how I used an artificial general intelligence chatbot to code a side project for one of my clients.

Computationalism

Computationalism is the idea that likens to the human mind to a computer. Before the rise of the digital age, other technologies were often used as metaphors for how our brain works. During the Industrial Revolution, the steam engine was used as a metaphor for the human mind. Other examples include the clock, the camera, and even the telephone.

This topic is explored in “The Beginning of Infinity“, a book by physicist and philosopher David Deutsch. He argues that computers and machines can be useful analogies for certain aspects of the mind, but it is ultimately a unique and irreducible phenomenon that cannot be fully understood or replicated using any kind of technology.

Mind metaphors

Resources:

Face It, Your Brain Is a Computer

The Beginning of Infinity: Explanations That Transform the World

Business is a form of alchemy

Just as the ancient tradition that sought to transform base metals into gold, so too does a successful business transform raw materials and resources into valuable products and services. Moreover,  it contributes to the greater good of society. I hope this idea inspires you to be a wizard amongst engineers and make the world a better place.

Quotes

AI is the most important technology ever developed by humans. It is likely to become more powerful than any other technology in history.”

– Max Tegmark, physicist and AI researcher

 

I love people who make me laugh. I honestly think it’s the thing I like most, to laugh. It cures a multitude of ills. It’s probably the most important thing in a person.

– Audrey Hepburn, actress and humanitarian

Question

What is your next challenge?

This is a question I borrowed from a previous mentor who had a great influence on how I think and do business. I still ask myself and others this regularly.

Leave your answers in the comment section below.

Palindromes in PHP

A palindrome is a word (or a string of characters) that can be read identically either forwards or backwards. Examples include:

racecar
madam
mom
level
civic
kayak
rotavator

The logic for determining a palindrome is simple. Take the input, reverse it, and then compare it to the original. PHP even has a built-in operation, strrev(), to reverse strings. We can write a function to judge if an input string is a palindrome:

function determinePalindromeWithReverse($value){
	$reverse = strrev($value);
	if($reverse === $value){
		echo "true \n";
		return true;
	}
        return false;
}

During an interview, for a role as a Software Engineer, I was asked “Given a string, determine if you can make it a palindrome by removing at most 1 character.”

To solve that challenge, I can loop through the string while increasing the value of a counter variable. On each iteration, I’d remove a single character (whose index is determined by the count), reverse the result, and then compare it.

function determinePalindromeWithReverseRemoveCharacter($value){
	$reverse = strrev($value);
	if($reverse === $value){
		echo "true \n";
		return true;
	}

	for($i=0;$i<=strlen($value);$i++){
		$first_half = substr($value, 0, $i); // first half of string
		$second_half = substr($value, $i + 1);
		$string_with_one_char_removed = $first_half . $second_half;
		echo "$string_with_one_char_removed \n";
		$reverse = strrev($string_with_one_char_removed);
		if($reverse === $string_with_one_char_removed){
			echo "true \n";
			return true;
		}
	}

}
determinePalindromeWithReverseRemoveCharacter("racecfar"); // true

I use PHP’s substr() function to get the each half of “the new string with one character removed.” The first division starts from the beginning (zero index) and continues up until the counter determined position (zero on the first loop, one on the second, and so on). The second part starts one step past the iterative count, and finishes with the string’s end. This results is the original input with a single letter deleted.

To illustrate how this works, I printed out the concatenation each time. You can see that the program continues until the result is a palindrome.

Although this works, reversing the string each time is costly. It reduces the algorithmic efficiency, making the solution “not scalable.” How can we decide if a string is a palindrome without reversing it?

Validating a palindrome using recursion

Judging a string to be a palindrome can be done using recursion. In programming, recursion is when a function calls itself.

Before we worry about removing any characters like we did above, we need a new function to verify a palindrome without reversing it:

function determinePalindromeRecursively($value){
    if ((strlen($value) < 2)){
        // echo "true \n";
        return true;
    }else{
        if (substr($value,0,1) == substr($value,(strlen($value) - 1),1)){
            echo substr($value,1,strlen($value) - 2) . "\n";
            return determinePalindromeRecursively(substr($value,1,strlen($value) -2));
        }else{
            // echo " Not a Palindrome"; 
            return false;
        }
    }
}

This method compares the first and last characters of the input. If they match, our code will remove them and pass the updated $value back around to itself, recursively. This continues until we get down to a single letter, or less – when we know that the original string was a palindrome.

To get the first character, we tell the substr() method to take the $value, start at the beginning (zero index), and collect a single element: substr($value,0,1)

To get the last character, we tell the substr() method to take the $value, start at the end (the string’s length minus one), and collect a single element: substr($value,(strlen($value) – 1),1)

To remove both the first and last letters, we tell substr() to start just past the first element (represented by an index of 1), and to collect the string’s length worth of characters minus two.

Notice that on each recursive loop, the string loses the front and back symbols.

Now, remember the original challenge: “Given a string, determine if you can make it a palindrome by removing at most 1 character.”

All that is left is to use our recursive function in tandem with removing a single character per loop.

function determinePalindromeRecursively($value){
    if ((strlen($value) < 2)){
        // echo "true \n";
        return true;
    }else{
        if (substr($value,0,1) == substr($value,(strlen($value) - 1),1)){
            echo substr($value,1,strlen($value) -2) . "\n";
            return determinePalindromeRecursively(substr($value,1,strlen($value) -2));
        }else{
            // echo " Not a Palindrome"; 
            return false;
        }
    }
}

function determinePalindromeRecursivelyWhileRemovingOneCharacter($value){

    for($i=0;$i<=strlen($value);$i++){
        $first_half = substr($value, 0, $i); // first half of string
        $second_half = substr($value, $i + 1);
        $string_with_one_char_removed = $first_half . $second_half;
        // echo "$string_with_one_char_removed \n";
         
        if(determinePalindromeRecursively($string_with_one_char_removed)){
            echo "true \n";
            return true;
        }
    }
    echo "false \n";
    return false;

}

determinePalindromeRecursivelyWhileRemovingOneCharacter("racecadr");

Give it a try, refactor my code, and see if you can solve this problem in a different way. There are other computer science puzzles about palindromes that you can apply this logic towards. Have fun!

Sort an HTML table using JavaScript

sort an html table using JS

For a recent side project I was tasked with enhancing an existing HTML table. That table displayed search results. The records were dynamic, populated by an AJAX call after the “search” button was pressed. One of the requests was to let users click on the column headers to sort the table. Each click would organize the data, toggling ascending and descending, based on the column values.

A table with data about dogs

My first idea was to use a front-end library. I love abstractions, and hate reinventing the wheel. I’ve used the DataTables jQuery plug-in before, and thought it might be a good fit. All I had to do was include two CDN file references – one for CSS styles and another for JavaScript functionality. After that, I could select the table by ID and call a single function:

<link href='//cdn.datatables.net/1.13.2/css/jquery.dataTables.min.css' rel='stylesheet' type='text/css'>
<script src="//cdn.datatables.net/1.13.2/js/jquery.dataTables.min.js"></script>

<script>
$(document).ready( function () {
	$('#dog-table').DataTable();
} );
</script>

This added quick and easily out-of-the-box functionality, with bells and whistles.

It seemed great, but the extras that it added, such as pagination and front-end search were unnecessary, and actually got in the way of the design specification. Those might be easy enough to clean up by passing options into the method call, or even with a bit of custom CSS, but still seemed like overkill.

Further, the DataTables library would occasionally throw errors about an “incorrect column count”, depending on what results my back-end provided. That was because the data model, and possible front-end actions for this app were more complex that you might think. The HTML wasn’t strictly semantic and the information wasn’t just tabular.

The more I thought about it, the more I felt that plain vanilla JavaScript should be enough to get the job done. And, since we’re living in the future, I decided to ask an AI chat-bot called ChatGPT.

I asked “How can I use jQuery to sort an HTML table by a specific column?”

Asking ChatGPT about coding

It told me that “You can use the sort method of JavaScript arrays combined with the map method to sort an HTML table by a specific column,” and gave me a specific code example!

I was very impressed. Here is the JavaScript code it provided:

<script>
$(document).ready(function() {
  var table = $('#myTable tbody tr').get();

  table.sort(function(a, b) {
    var A = $(a).children('td').eq(1).text();
    var B = $(b).children('td').eq(1).text();

    if(A < B) {
      return -1;
    }

    if(A > B) {
      return 1;
    }

    return 0;
  });

  $.each(table, function(index, row) {
    $('#myTable').children('tbody').append(row);
  });
});
</script>

I added this code to a click-handler in my app, after adjusting the element selectors. Although it worked (kind of), it did not operate quite as I expected. It only performed the sort on a single column, and did not alternate the order on each click.

I continued to ask the chat-bot more questions, making refinements to the functionality. I wanted the code to toggle between ascending and descending on each click. Also, I figured it could be nice to avoid jQuery completely and just use basic JS.

Chat bot solving code problems

Eventually, it told me “To toggle between ascending and descending order when sorting the table, you can keep track of the current sorting order for each column in a separate array”. Below, you can see the full code implementation:

<style>
  table {
  border-collapse: collapse;
  width: 100%;
}

th, td {
  text-align: left;
  padding: 8px;
  border-bottom: 1px solid #ddd;
}

tr:nth-child(even) {
  background-color: #f2f2f2;
}

th {
  background-color: #4CAF50;
  color: white;
  cursor: pointer;
}

td:first-child {
  font-weight: bold;
}

td:nth-child(3), td:nth-child(4) {
  text-transform: capitalize;
}
#search-input {
  padding: 8px;
  margin-bottom: 12px;
  width: 100%;
  box-sizing: border-box;
  border: 2px solid #ccc;
  border-radius: 4px;
  font-size: 16px;
}

#search-input:focus {
  outline: none;
  border-color: #4CAF50;
}
</style>
<input type="text" id="search-input" placeholder="Search breeds...">
<button>Search</button>
<table id="dog-table">
  <thead>
    <tr>
      <th>Breed</th>
      <th>Origin</th>
      <th>Size</th>
      <th>Temperament</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>Labrador Retriever</td>
      <td>Canada</td>
      <td>Large</td>
      <td>Friendly, outgoing, and active</td>
    </tr>
    <tr>
      <td>German Shepherd</td>
      <td>Germany</td>
      <td>Large</td>
      <td>Loyal, confident, and courageous</td>
    </tr>
    <tr>
      <td>Poodle</td>
      <td>France</td>
      <td>Small to Large</td>
      <td>Intelligent, elegant, and proud</td>
    </tr>
    <tr>
      <td>Bulldog</td>
      <td>England</td>
      <td>Medium</td>
      <td>Determined, friendly, and calm</td>
    </tr>
    <tr>
      <td>Beagle</td>
      <td>England</td>
      <td>Small to Medium</td>
      <td>Cheerful, determined, and friendly</td>
    </tr>
  </tbody>
</table>


<script>
// Get the table element
const table = document.querySelector('table');

// Get the header row and its cells
const headerRow = table.querySelector('thead tr');
const headerCells = headerRow.querySelectorAll('th');

// Get the table body and its rows
const tableBody = table.querySelector('tbody');
const tableRows = tableBody.querySelectorAll('tr');

// Initialize sort order for each column
let sortOrders = Array.from(headerCells).map(() => null);

// Attach a click event listener to each header cell
headerCells.forEach((headerCell, index) => {
  headerCell.addEventListener('click', () => {
    // Extract the column index of the clicked header cell
    const clickedColumnIndex = index;
    
    // Toggle the sort order for the clicked column
    if (sortOrders[clickedColumnIndex] === 'asc') {
      sortOrders[clickedColumnIndex] = 'desc';
    } else {
      sortOrders[clickedColumnIndex] = 'asc';
    }
    
    // Sort the rows based on the values in the clicked column and the sort order
    const sortedRows = Array.from(tableRows).sort((rowA, rowB) => {
      const valueA = rowA.cells[clickedColumnIndex].textContent;
      const valueB = rowB.cells[clickedColumnIndex].textContent;
      const sortOrder = sortOrders[clickedColumnIndex];
      const compareResult = valueA.localeCompare(valueB, undefined, { numeric: true });
      return sortOrder === 'asc' ? compareResult : -compareResult;
    });
    
    // Rebuild the table in the sorted order
    tableBody.append(...sortedRows);
  });
});

</script>

Using predictive language models as a coding assistant is very helpful. I can’t wait to see what other uses we find for this technology, especially as it gets better.

Mindfulness for Programmers

Our senses keep us plugged into reality. They instantly create a connection to the present. Paying attention is the only way to experience this moment in life. If you’re feeling distracted, panicked, or out-of-touch with reality, try taking time to intentionally notice the things that stimulate you. Note-taking and blogging is a great way to do that.

Writing about how the world seems through your own particular lens fosters mindfulness and appreciation. It keeps your mind grounded in this realm. Journaling is an important ritual that I practice daily, but it is hard to take note of and digest everything that happens in our lives. Doing it here is a way that I can highlight the stuff that has truly touched me.

In diaristic fashion, I will periodically take note of the things I saw, heard, felt, smelt, read, or otherwise consumed. This will give me a chance to share (and keep track of) the things that I love.

Something I saw: The tallest waterfall in New York State. This summer, I drove a few hours north from NYC to Ithaca, NY. It’s a city known for its gorges, cut into stone by natural running water.

It was a short hike (maybe twenty minutes) through Taughannock Falls State Park to get this awe-inspiring view of nature.

Something I read: Catching the Big Fish: Meditation, Consciousness and Creativity by David Lynch. David Lynch is a filmmaker and artist. He discusses his development of ideas in this book and likens the process to catching fish:

The beautiful thing is that when you catch one fish, even if it’s a little fish—a fragment of an idea—that fish will draw in other fish, and they’ll hook onto it.

Lynch explains how meditation had helped him overcome the depression that gets in the way of creativity, “You must have clarity to create“.

Something I ate: I live in New York City. I eat a lot of good food. But, this culinary experience happened in Illinois this summer. I ate at the famous Lou Malnati’s Pizza in Chicago.

pizza pie

Deep dish with a few toppings hit the spot, washed down with a cold beer.

pizza slice

Stimulation == Simulation

To get philosophical about it, I think that what’s really out there and what we experience might be very different things.  Like how a the experience of a computer screen showing a beautifully drawn graphical user interface never hints at the reality of computer boards directing electrical circuits to represent the information we see. Our notion of reality is a digital simulation instigated by the sensory input interpreted through our senses.

Mindfulness & Awareness

Even under the richest of experiential excitement, without mindfulness there is no participation with, nor illusion of, reality. If you mindlessly read a book, you might as well have not read it. If you day-dream during a movie, you may know as much about the plot as someone who has never saw it. The same is true for life in its entirety. Don’t miss out – pay attention.

You can train yourself to get better at paying attention. The better you get at it, the more you will experience the richness of vibrancy of this world. The two best techniques I have found for this is: meditation and reading.

Software Engineering Internal Tools

internal tooling

At a recent Software Engineer position I worked on developing and improving internal tools. Internal tools are software systems that are developed and used within an organization to improve efficiency, productivity, and communication.

These tools are often not marketed to or made available to external customers, clients, or end users and are instead designed for internal usage by workers. Systems for project management, communication, time tracking, human resource management, business intelligence tools, IT management, and document management are a few examples.

As a programmer working on internal tools, there are a few vital things you can do to make the most impact:

  1. Recognize your users’ needs before beginning any tool development: It’s critical to recognize your users’ demands before beginning any tool development. This entails conversing with them, looking over their processes, and getting their comments. The key to success here is scheduling interviews with the people who will be using your work.
  2. Prioritize based on impact: As soon as you are aware of your users’ needs, focus on adding features and making enhancements that will have the biggest positive effects on their efficiency and effectiveness.
  3. Keep it (super) simple: Make an effort to keep the user interface straightforward and basic so that internal tools are simple to use and comprehend. Keep any extra features or complexity to a minimum.
  4. Continuously improve: Continue to gather user feedback and make ongoing adjustments to your tools. This will make it more likely that they will continue to be useful and satisfy the needs of their users.
  5. Make sure it’s maintainable: Internal tools’ long-term success depends on the creation of maintainable code. Ensure that your code is well-structured, commented, and adheres to standard practices.

Array Rotation in PHP

An operation to rotate an array will shift each element to the left. We can perform this function X number of times depending on the input parameters. Since the lowest index element moves to the highest index upon rotation, this is called a circular array.

All we need to do is remove the first element of the array, save it in a variable, and then attach it to the end of the array. This can be done inside of a loop that iterates the number of times that we want to rotate the data. The function can take in the original array and the number of rotations. It returns the newly rotated array:

function rotateLeft($array, $rotations) {     
    for($i=0;$i<$rotations;$i++){
        $firstElement = array_shift($array);
        array_push($array, $firstElement);
    }
    return $array;
}

Although this code will work, and gets the job done, it is slow. When I tried this as a solution on HackRank (a code challenge website) it passed 9/10 test cases. It failed once, citing “time limit exceeded”.

The problem is with array_shift. It’s a PHP function that removes “the first value of an array off and returns it.” This shortens the array by a single element, moving everything else down one index. The algorithmic efficiency (expressed in Big-O notation) of array_shift() is O(n). That means, the larger the input array, the more time it will take to complete.

Next, I tried using array_reverse and array_pop. I figured that since array_pop() has a constant algorithmic efficiency, noted as O(1), it would help. Regardless of the size of the input, it would always take the same amount of time.  But, due to the use of array_reverse (twice!) it was even slower:

function rotateLeft($array, $rotations) {
    for($i=0;$i<$rotations;$i++){
        $array = array_reverse($array);
        $firstElement = array_pop($array);
        $array = array_reverse($array);
        array_push($array, $firstElement);
    }
    return $array;
}

Finally, I found a solution that was performant:

function rotLeft($array, $rotations) {
        $remaining = array_slice($array, $rotations);
        array_splice($array, $rotations);
        return array_merge($remaining, $array);
}

This code does not need to use any kind of loop, which helps to speed things up. First, array_slice() grabs the elements up to the point that the data should be rotated, and saves them to the variable $remaining. Next, array_splice() removes those same elements. Lastly, array_merge() glues the elements back together in the expected, rotated order.

This sort of computer science programming challenge can commonly be found during software engineering job interviews. When coming up with an answer, it is important to consider speed and performance. Understanding computing cost-effectiveness and Big-O can be a deciding factor in how your coding skills are judged.

Look-and-say in PHP

The look-and-say sequence is a series of integers. It can grow indefinitely. It is generated by reciting a number phonetically, and writing what you spoke numerically. Its popularity is attributed to famed cryptographer Robert Morris. It was introduced by mathematician John Conway. It looks like this:

1
11
21
1211
111221
312211
13112221

The first line would be pronounced as “one 1”, and then written as “11” on the second line. That record would be spoken as “two 1’s”,  giving us the third line “21”. The greatest individual symbol you’ll ever find in this consecution is a 3.

This topic has lots of trivia, variations, and history that could be dug up and expounded upon. Here, I’ll explain a solution written in PHP to produce this chain of numerals. The input will be the count of how many lines, or iterations, in the series to generate. Below is the code:

<?php

echo "Count And Say: \n";

function countAndSay($count=0){
	$value = 1; // initial seed
	for($i=1;$i<=$count;$i++){
		echo $value . "\n";
		$value = calcOutput($value);
	}
}
function calcOutput($value){
	$value = "$value";  // change it into a string, so we can iterate over each character
	$current = $value[0]; // first character
	$count = 1;
        $return = '';
	for ($i = 1; $i <= strlen($value); $i++) { // keep going until we get through the whole string
		if ($current != $value[$i] || $i == strlen($value)) { // found a different character, or end of the input string
			$return .= "$count$current";
			$count = 1; // reset count
			$current = $value[$i]; // set new current character
		} else {
			$count++;
		}
	}
	return $return;
}

countAndSay(7);

echo "\n\n";

?>

I separated my code into two functions. I think this is the best approach. As an exercise, see if you can figure out how to refactor it into one. This could help you to internalize the logic as you write it out for yourself.

The initial seed value is “1”, and that is hard-coded at the top. The for-loop iterates based on the count input parameter. That means the code circles back and re-runs, with updated values, until its internal count (represented by the variable $i ) matches the $count variable passed into countAndSay($count).

The code that we loop over outputs the current sequence value (starting with 1) as its own line (“\n” will output a new line in most programming languages) , and then calculates the next. The function that determines the next line of output, calcOutput($value), takes the current value as an argument.

The first thing we do is cast the integer value passed along into a string. This lets us refer to each character by index – starting at zero – and save it to a variable $current. We start a new $count, to keep track of how many times we see the same digit.

The next for-loop executes for the length of the $value string. On each loop, we check if the $current character we saved matches the subsequent one in that $value string. It is again referenced by index, this time based on the for-loop’s iteration count represented by the variable $i.

If it does match, one is added to the $count variable that is keeping track of how many times we see the same character is a row. If it doesn’t match (or we’ve reached the end of the input), the $count and $current number are concatenated to the $return element. At that point, the $count is reset to 1, and the $current value is updated.

Writing an algorithm to generate the look-and-say (also known as, count-and-say) sequence is a common coding puzzle. You might run into it during a job interview as a software engineer. As practice, see if you can simplify my example code, or even write it in a different programming language than PHP.