Coding a fast O(n) solution for the TwoSum problem

One of the more common problems asked during tech interviews is 'Two Sum'.

You are given an array (or list) of integer values, along with a target integer, and must return the two indices of the two integer values that add up to the given target value. 

Here are a couple of examples:

Example #1:
---------------------
Input array:             [2, 5, 7, 15, 22]
Target value:           29
Expected output:    [2, 4]

Example #2:
---------------------
Input array:             [1, 4, 9, 6]
Target value:           5
Expected output:    [0, 1]

The easiest and fastest solution is a brute-force approach, where we have a nested loop scanning the array, and checking every possible pair to see if it adds up to our target sum. Such a solution would be coded like this (Java version):

public int[] twoSum_Bruteforce(int[] nums, int target) {

int numsLen = nums.length;

for(int indexA = 0; indexA < numsLen; indexA++) {

for(int indexB = indexA + 1; indexB < numsLen; indexB++) {

int numA = nums[indexA];

int numB = nums[indexB];

if(numA + numB == target) {

return new int[]{indexA, indexB};

}

}

}

return new int[]{-1, -1};

}

As a first-time approach to this problem, it's not bad - but its far from ideal. If you were to supply this solution during an actual coding interview, you'd get some credit since there's no denying it actually works, but the interviewer will most likely coax you into writing a more optimized solution. 

Here's why: although our brute-force method works perfectly fine for smaller array inputs, it's extremely inefficient for larger arrays.

Below is a graph that illustrates the speed issues for larger arrays. Size of the array is represented on the X-Axis, while runtime (in seconds) is on the Y-Axis. Each runtime was measured with the worst-case scenario - meaning that the correct pair is always located at the end of the array (the last 2 integers). Runtime is measured in seconds, so the results are going to vary a bit from one device to the next (and also from one langauge to another) - but for all intents and purposes - assuming a typical standard Desktop PC running Java... it's going to be about the same. The goal here was to use a inutitive metric to drive the point home.

For relatively small arrays with only a couple to a few thousand integers, the runtime is respectable and pretty much "fast" enough. However, once we get into the several thousands, and north of 10,000 elements, the runtime starts to increase exponentially. By the time we get to 100,000 elements, the worst-case runtime is close to 2 seconds! This is expected since the brute-force approach runs with a O(n^2) time complexity. In a real-world environment this type of runtime speed would simply be downright unacceptable - especially for the simple purpose of what this algorithm is trying to achieve to begin with. 

The main bottleneck here is that nested loop, which, if we study the problem a little harder, we find that we can actually get rid of it altogether.

Let's look at one of our examples from the top again (Example #1), and see what we can do to find the correct output without needing a nested loop.

The array input is: [2, 5, 7, 15, 22], our target sum is 29, and the expected output is [2, 4] (Remember: we want to return the 2 indices of the solution pair, so 2 is the index of 7, and 4 is the index of 22)

This time, we'll use one loop, and we'll do the following for each integer in the list until we've found the solution:

-> Current Integer: 2, Current Index: 0
     Subtract 2 from our target sum (29) = 29 - 2 = 27.
     Have we seen 27 before? No.
     Store someplace that we have seen the integer 2 at index 0.
     Continue

-> Current Integer: 5, Current Index: 1
     Subtract 5 from our target sum (29) = 29 - 5 = 24
     Have we seen 24 before? No.
     Store someplace that we have seen the integer 5 at index 1.
     Continue

-> Current Integer: 7, Current Index: 2
     Subtract 7 from our target sum (29) = 29 - 7 = 22
     Have we seen 22 before? No.
     Store someplace that we have seen the integer 7 at index 2
     Continue

-> Current Integer: 15, Current Index: 3
     Subtract 15 from our target sum (29) = 29 - 15 = 14
     Have we seen 14 before? No.
     Store someplace that we have seen the integer 15 at index 3
     Continue

-> Current Integer: 22, Current Index: 4
     Subtract 22 from our target sum (29) = 29 - 22 = 7
     Have we seen 7 before? Yes - we saw 7 at index 2
     Stop loop and return 2 along with the current index of 4 -> Return [2, 4]

To summarize the above steps: Each time we encountered an integer we hadn't seen yet, we stored that integer along with its respective array index somewhere so we could retrieve it later. We do this every iteration of the loop. If we come across an integer X and see that we've already encountered the value of (target sum - x), then we're done!

Then we just have to figure out what data structure to store the (integer, index) pairs in, and a good choice for that is a Map, since we can easily map Integer -> Index of integer.

Below are two versions of the same implementation of the above approach - one coded in Java, and the other in Go:

Java implementation of fast solution using a map:

public int[] twoSum_Fast(int[] nums, int target) {

Map<Integer, Integer> numsSeen = new HashMap();

for(int index = 0; index < nums.length; index++) {

int otherNum = target - nums[index];

if(numsSeen.containsKey(otherNum)) {

return new int[]{numsSeen.get(otherNum), index};

}

numsSeen.put(nums[index], index);

}

return new int[]{-1, -1};

}

Link to gist: https://gist.github.com/edev90/1d4c1c01cf4d1aec5040078eec6fbf33

Go implementation of fast solution using a map:

func twoSum(nums []int, target int) []int {

numsSeen := make(map[int]int)

for index := 0; index < len(nums); index++ {

otherNum := target - nums[index]

if indexOfOtherNum, isValidKey := numsSeen[otherNum]; isValidKey {

return []int{indexOfOtherNum, index}

}

numsSeen[nums[index]] = index

}

return []int{-1, -1}

}

Link to gist: https://gist.github.com/edev90/4228c5fd3e447e27ff3be6d60f42591c

As we can see, the HashMap solution is faster on average by multiple times more than the brute-force solution. The graph below shows the runtimes and performance for the Two Sum solution using one loop and a HashMap:

Large arrays - even up to 100,000 elements in size are well below sub-tenth of a second in runtime. This is drastically faster than the brute-force approach. In fact, on my machine I had to bump the array size up to 75 million elements to get a runtime with the fast method that matched the 2 second runtime of the brute-force approach for 100,000 elements - which in this case makes the HashMap solution about 500 times faster than the brute-force one.

In the end, we were able to write a solution to this problem with worst case O(n) time complexity. There is a trade-off of course, as we increased the space complexity to track integers we had already seen along with their corresponding index for later retrieval. However, most versions of the Two Sum question are asked with the assumption that time is the most important factor to be optimized. That being said, if you encounter this question in an interview it's always best to ask the interviewer(s) what aspect of the problem you should be optimizing on, and adjust your approach accordingly.

If you'd like to see more of these algorithm/data structure posts, or would like me to cover a specific problem, please drop a comment below letting me know what you'd like to see covered in a future post.

Returning multiple values in Java - My preferred approach

Java does not natively support the ability to return multiple values from a method.

It would be nice if we could do something like this: could

public int, int methodThatReturnsMultipleValues() {

return 1, 2;

}

But we can’t. You’ll likely find this particularly bothersome if you’ve migrated over to Java from another language that supports returning multiple values out of the box (like Golang, for instance).

Thankfully, there are workarounds we can use to emulate this behavior. One of the more common workarounds is to simply return an array that contains the return values, like below:

public int[] methodThatReturnsMultipleValues() {

return new int[]{1, 2};

}

In order to retrieve both integer values we returned, we read both elements of the array:

int[] returnValues = methodThatReturnsMultipleValues();

int firstValue = returnValues[0];

int secondValue = returnValues[1];

For smaller use cases this works fine, but it gets messier with scale — and that’s why I don’t like to use it. 

It’s easy to introduce errors that won’t be exposed until the application is running, such as issues pertaining to:

Array Indexing

Let’s say you forget to make your code zero-based and attempt to pull from returnValues[1] and returnValues[2] instead. At some point an ArrayIndexOutOfBoundsException is going to get thrown when this code executes.

Additionally, by only using indexes to identify which array element corresponds to which return value, you could inadvertently assign returnValue[1] to firstInteger, and returnValue[0] to secondInteger.

Casting

In a lot of situations where it’s handy to return multiple values, the values are of different types. Since Object is a parent class of all other classes in Java (the topmost class), we can have an Object[] array that returns anything we want:

public Object[] methodReturnsMultipleValuesDifferentTypes() {

String a = "This is a string";

int[] b = {1, 2};

return new Object[] {a, b};

}

We can put any object of any type into that array. Here, I’m putting a string and an integer array into the Object[] array.

But we then need to employ casting when we want to read those values back and assign to their appropriate type(s):

Object[] returnValues = methodReturnsMultipleValuesDifferentTypes();

String firstReturnValue = (String)returnValues[0];

int[] secondReturnValue = (int[])returnValues[1];

And therein lies the possibility for casting mistakes to be made. If you mistakenly cast a value as the wrong type, a ClassCastException will occur during runtime.

My Preferred Approach: 

Because of all the considerations I mention above, I almost never use the array approach.

Instead, I use a generic class to store whatever values I need to return from my method.

I create a generic class named “ResultPair" (or something that clearly conveys what the class is used for), and then place it somewhere accessible to every other class in the project. 

I have a type parameter for every return value, and a constructor that accepts each return value that we want the ResultPair to store:

public class ResultPair <T1, T2> {

public T1 firstValue;

public T2 secondValue;

public ResultPair(T1 firstValue, T2 secondValue) {

this.firstValue = firstValue;

this.secondValue = secondValue;

}

}

Instead of using a convoluted array, now we just pass the values to our ResultPair constructor, and return that from a method:

public ResultPair<String, int[]> methodThatReturnsResultPair() {

String a = "This is a string";

int[] b = {1, 2};

return new ResultPair(a, b);

}

Now accessing the return values is much cleaner:

ResultPair<String, int[]> returnValues = methodThatReturnsResultPair();

String firstReturnValue = returnValues.firstReturnValue;

int[] secondReturnValue = returnValues.secondReturnValue;

There’s no need now to read from an Array, so ArrayIndexOutOfBounds exceptions are no longer a concern. We also don’t need to cast anymore, and if we even attempt to assign one of the return values to the wrong type (assigning the String return value to a Double, for example), we’ll get a heads up with IDE warnings we can resolve before running the application:

The other really nice thing about this approach is that you have a clear indication of how many, and what type of values you’re getting back from a method. In this case when I see ResultPair<String, int[]> in the method signature, I know that I’m getting a String and an Integer back from the method I called — whereas when dealing with an Object[] array I might have to trace through the method to discover what types of values I’ll be given.

When I did some quick benchmark tests, I found no significant speed impairments with this approach — and in fact often times the generic class approach was faster than the array method. 

Everything considered, unless there’s some niche case that calls for using an array, I highly encourage using the generic class approach to return multiple values in Java.

Unit tests are not the magic solution to code integrity

I’ve seen dev teams constantly tout the importance of having as many unit tests in a codebase as possible. 

This became such an important metric for one such group, that leadership overseeing the team started a competition between the developers to track the “leaders” who had the most unit tests. 

Engineering VPs began frequently sending out a chart listing the top unit test producers for each sprint. Each chart would be broken down like this:

Name	# of unit tests committed during sprint
Person A	12
Person B	5
Person C	2
Person D	2

They would stress in their communications for everyone to keep up the good work, and keep adding more “good” unit tests. “We need more and more good unit tests” they would constantly reiterate and repeat over and over in nearly every email or meeting regarding improving code quality of the codebase. 

Here’s the problem with this type of practice: this doesn’t promote the production of more, “good”, quality unit tests — it promotes the production of more frivolous unit tests.

Hyper-focusing on just the volume of unit tests goes against one of the main reasons they exist: to increase the testability, maintainability, extensibility, and clarity of code. If you’re throwing unit tests out there just for the sake of increasing unit test count, you’re actually hindering your ability to achieve these things — not helping them. Ironically, you end up adding one of the biggest things you aim to get rid of: wasteful, glitchy, code overhead that has no purpose. Additionally, keep in mind that unit tests need to get executed in order to actually perform the validation testing that they’re written to do. The unit tests that a developer coded just to reach an inconsequential goal and gain a top spot on a leader board is going to drag down the runtime of build tests (among other things) as well as impede the runtime of their own local testing (which can result in the delay of them rolling out bug fixes and new features).

With any mature codebase, there’s often a great deal of bloat or oversights inherit in the code resulting from past development decisions that prioritized speed over quality and thoroughness. This “Tech Debt” makes it harder for developers to test, debug, and extend the surrounding code due to the bloat and verbose nature of it. Unfortunately, addressing tech debt isn’t as “flashy” of an endeavor as adding new features to the product. At the same time, however, stakeholders understand that this bloat makes it harder to maintain and support the system, and impairs the organization’s ability to ship new functionality and bug fixes to customers.

This conflict — juggling the realization that tech debt hinders the ability to deliver quality results faster to clients, but not wanting to prioritize and allocate the proper time necessary to clean it up, is what results in leadership pushing these sorts of “more unit test” campaigns. They view past redundant, slow, and disorganized spaghetti code baked into the software as a sort of sunk cost. They find it hard to understand why any time should be spent on rewriting it, and instead believe that everyone should just move on and switch their attention and energy into writing unit tests for future code commits. This view is compounded by the fact that implementing new features is what keeps customers engaged and interested in a product — customers don’t care about your tech debt or past development oversights, they just want new features built, and current features to be faster.

As such, it’s often tricky to get product managers and leadership onboard with the idea of dedicating an entire sprint (or more) to tackling tech debt when there is a backlog of customer requested features waiting to be implemented. That’s why the push for tech debt removal needs to be sold in a skillful way. Whenever possible, point out the fact that that removing the convoluted code in Module X would cut the development time for Feature Y in half, or make a report 200% times faster for a client to run. Hold routine meetings with PMs, management, and support staff reviewing any recent escalations and bugs. Show how an issue could have been mitigated faster if getting down to the root cause of the issue hadn’t involved hours of untangling spaghetti code. It’s easier to get buy-in when everyone realizes that messy code resulted in a customer not getting a fix in time and escalating a complaint up to the president of the company.

The Bottom Line

Unit tests should absolutely be included in code wherever possible to strengthen the quality of the codebase. However, they should be added strategically, and not just thrown around for the sake of adding more unit tests. Trying to gamify such metrics is pointless in general anyway, especially when there are so many additional actions that need to be taken to foster a stable system. Unit testing is not the sole magic solution to improving code integrity.

Moreover, adding new unit tests alongside new code does not retroactively fix existing tech debt and alleviate the overhead costs such debt poses to the maintainability of a system. If this tech debt isn’t proactively taken care of, someone will just have to clean it up to allow them to support unit tests eventually, so past tech debt is never avoidable for very long.

Refactoring efforts and initiatives to optimize current modules and remove existing debt should be prioritized. This will strip existing overhead from the code, and facilitate the process of writing higher quality unit tests in the future. A strong foundation of clean, organized, well structured code will lead the way for higher quality, and better unit tests down the line.

GACubeSolver version 1.0 release

I've released version 1.0 of GACubeSolver on my github page.

GACubeSolver is a Rubik's cube solver I wrote in Java. It uses the Swing framework for the UI. 

Instead of having hard-coded algorithms (like beginner's method, CFOP, Roux, etc) that the solver follows, the solver must figure out entirely on its own how to solve a scrambled cube. In order to achieve this, genetic algorithms are used. Traditionally speaking, this isn't the best use case for genetic algorithms due to the highly combinatorial nature of the Rubik's cube - but that's what makes this a fun and interesting challenge. 

So far, GACubeSolver can completely solve the pocket cube aka the 2x2 mini Rubik's cube (solve times vary depending on how scrambled the cube is). Getting the 3x3 fully solvable is the ultimate goal, and so far is a work in progress. 

The source code as well as a brief overview of the tech details and more details regarding the current support for the 3x3, can found on the project's github page.

260 Colors Generated with Cellular Automata

The block of code below produces the image shown above... can you figure out how?

(Continue reading on for the answer)

A couple weeks ago I wrote a post about using Rule 30, a type of cellular automaton, to build a PRNG (pseudo random number generator).

Since then, I've been playing around with the code used in that tutorial to see how much smaller I could make it. Turns out I was able to golf it a lot -- down to just 264 characters of javascript in fact (264 chars of JS + 70 of HTML).

This was the code before:

And this is the code now:

For the most part it was just about compressing the code, removing unnecessary html tags, and stripping as many semicolons as I could without breaking the code. I also changed the way I'm building the colors: you'll notice that instead of breaking the integer out into an RGB string, I'm now formatting them as hex codes so I could get back some of the chars I had spent on string concatenation and bitshifting.

I also ditched the arrow function after taking a closer look and realizing it wasn't even necessary. The whole reason I had this to begin with is that I need to know when I'm looking at cells 'outside' the bounds of a row in the Rule30 grid (the 2 leading and trailing blank cells that are always present on each row). 

So I golfed this line: b.push(f(i) ^ (f(i+1) || f(i+2)));

Down to: b.push(a[i]^(a[i+1]|a[i+2]));

Why are we able to do this? You might wonder, won't there now be cases when an index will be out of bounds and error out? Well actually no, because in JS attempting to fetch an element from an out of bounds index will just return undefined, which in this case is actually useful. When we use undefined as part of boolean logic, it will become false, (aka 0 when interpreted in math) anyway, which is what we want!

A couple other minor differences included notching up the main loop from 3120 to 6240 iterations so there are 260 colors instead of 130. And instead of a circle I let each color fan out off screen because I think it looks a lot cooler than the colorwheel.

A practical takeaway from this is getting to visualize Rule 30 from a different perspective. It's clear from looking at all the colors generated from such condensed code that Rule 30 is a truly interesting cellular automaton and there are likely a myriad of other use cases it can be applied to that have yet to be discovered.

If you happen to golf the code down even further, or want to share some other piece of code using Rule 30 in some unique way, go ahead and share in a comment below!

Generating Pseudo Random Numbers with Cellular Automata

Below is an image of a color wheel on an HTML5 canvas:

This is code that produces that image: 

Only 31 lines of JavaScript code, and yet the wheel is comprised of 130 unique colors. The same 130 unique colors each time too. Notice there's no loading data from external calls made to fetch data from other scripts or pages, no Math.random(), and no compressed data used. So how was this accomplished?

The answer to this puzzle is Rule 30, a cellular automaton introduced by Stephen Wolfram. As we'll see in a moment, the bits in the center column of Rule 30 are chaotic and complex and follow no easily discernible pattern. In this case, I collect those bits and concatenate them into integers that I use as RGB values in the wheel.

The rule set for Rule 30 is: Bitwise concatenate each group of 3 cells in a row. If the bitwise concatenation of the group is 1, 2, 3, or 4, then the resulting cell underneath will be 1 (represented by dark shaded cells).  Otherwise, 0, 5, 6, or 7 will be 0 (represented by light color cells).

Even simpler: for every 3 bit group, the resulting bottom cell will be the value of the left cell, XOR’d by the the result of the center cell OR’d by the right cell (Bottom Cell = Left Cell XOR (Center Cell OR Right Cell).

The GIF below illustrates how the first 4 rows of the Rule 30 automata are built when the initial input seed is 1:

Similar to other cellular automata, the rows are built repeatedly one after the other. The interesting thing about Rule 30 is that, unlike other automata, the rule set here produces a center column that exhibits complex and seemingly random behavior for many seed inputs (the input of 1 is an example of a seed that produces a complex behavior).

There are pretty much 2 ways you can exploit the center column to implement a pseudo random number generator. 

1.) At runtime populate Rule 30 data for n rows (i.e: 100). Then take some other runtime value that isn’t exactly random, but changes constantly and reliably — say the system current timestamp. Then mod this by the number of rows, and then start collecting the bits starting at that row in the center column for as many bits as you like (wrapping around if needed).

For instance, given a current timestamp of 1626103527, and 100 rows of generated Rule 30 data, and we want to build a 32 bit integer. We’d start at row 27 (1629103527 mod 100 = 27). Select bits from row 27 to 58 which yields the 32 bit number. 

2.) Take the timestamp and convert it to a string of bits (1626103527 in base 2 = 1100001000110100010010110100111) and then use that as the start seed. Only 32 rows would have to be generated to get a random number. Beware that a downside to this is there’s no guarantee the current seed will produce a random output. For instance, no combination of XOR and ORs will produce 1s given all nonzero inputs, so a seed of 0 will produce a ‘0’ in every row of the center. 

How you set up the data structures/arrays to accomplish either of the 2 methods is up to you.

In short: the first method requires generating more rows up front, but then we don’t need to generate any further rows after that. In the second scenario we plug in varying seed inputs each time and only need to generate the # of rows for the # of bits that we want our number to consist of, but it’s harder to guarantee that our dataset will be complex.

One more example with a visual:

We want to generate a random 8 bit value using the first method. We build 8 rows of the automata using an initial seed of 1. 

Then we bitwise concatenate those 8 bits together, which makes 11011100 in binary, or 220 in decimal.

Found this interesting and up for a challenge? Check out the contest that Stephen Wolfram has going offering $30,000 in total prizes to solve questions regarding the chaotic behaviors surrounding Rule 30 and why precisely it occurs.

Questions, comments, feedback, or have your own code snippets that uses Rule 30 or other cellular automata in unique or fun ways? Please share below in the comments!

Genetic algorithms vs. Genetic Programming

In the Introduction to Genetic Algorithms video tutorial, we saw how GAs are powerful evolutionary algorithms that are used to synthesize solutions and optimize parameters for problems that are too complex or convoluted for humans to solve on their own. 

They work well in cases where semantics isn’t a huge concern. So in the case of the video, each possible step the mouse was able to take was encoded as an integer (gene). Strings of these genes (chromosomes) were built, and we kept evolving them through mutation and crossover until we found a chromosome that got the mouse from the start of the maze over to the cheese at the end. 

We weren’t concerned about what order the integers were in a chromosome, or if any of the states were “invalid”. Sure, there were some chromosomes that had a lot of noise or useless actions, but nothing that inherently didn’t make sense. This is what I mean by “semantics”.

So what happens if we wanted to use GA to evolve a mathematical expression? An area where semantics does matter.

The goal here will be to find a Mathematical expression that will yield the following outputs from inputs:

When input = 2, Output = 9

When Input = 0, Output = 5

When Input = 1, Output = 6

When Input = .5, Output = 5.125

The exact expression we’re looking for the computer to find is y = x^2 + 5.

We could encode each mathematical operation as an integer:

0: x

1: ^

2: *

3: +

4: -

5 through 9: (can be a number/digit in the range 0 to 5)

A few possible states we could generate:

701846 (would be 2x^3 - 1)

601846 (would be x^3 - 1)

031111 (would be x+^^^^)

222223 (would be *****+)

434343 (would be -+-+-+)

The first two states aren’t exactly the winning expression that we want, but they’re valid. The last 3 though are completely bogus. 

Even if we started with a proper string, a slight alteration during the mutation process can have a drastic result on the offspring. A generated expression such as 701846 undergoing a mutation could result in 101846, which now results in the expression ^x^3 - 1 — which doesn’t make much sense, does it? 

In order to deal with these invalid states, we'd need to include mechanisms into the parser that would repair or the damaged expressions prior to evaluating their fitness. It's certainly doable, but not very practical, and it’s definitely not scalable as we advance to building more complicated expressions. In theory, we’d need to manually code in more and more rules on how the computer should repair/handle invalid states. 

Enter Genetic Programming

Genetic programming has qualities that naturally safeguards it from spitting out faulty states like above.

Unlike GA, genetic programs are typically represented as a structure of “nodes” connected to each other somehow in memory. One of the more common structures used to represent them are trees.

The math function (4 + (X/25) - (9 * sqrt(X)) represented by a tree structure:

Since we’re dealing with a tree data structure now, we won’t be able to just mutate the genes by flipping a bit, or swapping the value of an integer - more effort will need to go in to the mutation and crossover operations (if you're looking for specifics on the code part, I'll be covering this part in detail in future articles).

But the nice thing here is that the restrictions are built directly into the tree, so we don’t need to deal with invalid states.

The root node, and also the internal nodes (nodes with child nodes) can only be operators. The terminal nodes (those without child nodes) can only contain constants or variables. We don’t connect an operator to a constant or variable node. Connecting nodes in this manner prevents us from generating a state like +X/-9+6.

It’s possible we could run into divide by zero errors, but these can be easily dealt with during the fitness evaluation stage of the GP. 

The bottom line

Practically speaking, there’s a fine line between what constitutes as a “genetic algorithm” or “genetic program”. At the end of the day — it really comes down to the classification and context of the problem you’re solving, the particular mechanics you’re using, and the format of the states that you’re generating.

In general, the primary differences come down to this:

Genetic Algorithms are traditionally built using strings of bits, integers, or characters that represent the genes that make up a chromosome. While this can make it pretty easy to manage and and evolve a GA, it can make evaluating them more cumbersome when they are applied to applications where they have a propensity to generate invalid states. Additionally, the fact that GA chromosomes are typically restricted by a fixed length results in decreased flexibility in the ability to scale as a problem becomes more complex.

With Genetic Programs, we adopt the same underlying evolutionary concepts and foundation from GA, but encode the individuals with a tree (or similar) structure rather than a string or list of genes. A consequence of this is that the overhead required to grow and maintain these structures is significantly increased. On the positive side, we have more control to enforce limits directly into the programs we build which greatly decreases the occurrence of invalid states. Due to the variable size of this type of representation, GP individuals are inherently more flexible than GA chromosomes, and can grow and scale as needed according to a problem's complexity — while efficiently preserving limits and rules throughout the tree.