# The Arena

### May 30, 2022

Every week, we have a coding challenge; they get posted in our #arena channel on Slack. Practice is what keeps us all sharp after all!

So, without further adieu, enjoy these challenges (ordered by most recent ones on top). Happy coding!

##### 30.Subsequences and Memoization

Recursion is beautiful, but can lead to some awful performance. Consider the fibbonacci sequence:

```const fib = n => {  if (n <= 0) return 0  if (n === 1) return 1  return fib(n-1) + fib(n-2)}
```

Beautiful, simplistic definition, but it has a big problem. We are computing the same value thousands of times. For `fib(40)`, we end up calling fib 331,160,281 times. That's a lot. Ideally we would have called it a maximum of like 41 times.

This is where the concept of Memoization comes into play. Memoizing is a fancy way of saying you are going to cache values and use the cached value if it exists.

Here's how we would memoize fib:

```const fibMap = new Map()const fib = n => {  if (fibMap.has(n)) return fibMap.get(n)  let value = 0  if (n <= 0) value = 0  else if (n === 1) return 1  else value = fib(n-1) + fib(n-2)  fibMap.set(n, value)  return value}
```

Slightly uglier, but much more performant. `fib(40)` only made 79 calls. Much better. Next week, we'll take it up even further.

So, let's improve last week’s code and memoize it.

Recursion is beautiful and tricky at first. It's all about figuring how to frame the solution in terms of the question.

So, here's the problem. We need to find the largest subsequence from an array where the elements are strictly increasing. A subsequence is any array which has some of the elements removed from the original array, but the remaining elements are still in the same relative orders.

So, for example:

• [10,9,2,5,3,7,101,18] would have either [2,3,7,101] , [2,5,7,101] , [2,3,7,18] , or [2,4,7,18] as the solution. Note that [3,7,101] is NOT the correct solution, even though it is the largest continuous segment.
• [7,7,7,7,7,7,7] would just have [7]

Create a recursive solution to this problem.

Now you are feeling pretty confident. You have a Palidrome checker, unit tests, so all is well with the world. Brace yourself, because new requirements just came in.

Given input text, return all possible partitions of the string which are palindromes.

For example:

• Geek => [ [g, e, e, k, s], [g, ee, k, s]]
• Nitin => [ [n, i, t, i, n], [n, iti, n], [nitin] ]
• Racecars => [ [r,a,c,e,c,a,r,s], [r,a,cec,a,r,s], [r,aceca,r,s], [racecar,s] ]

Using your tests from last week, go through the following flow:

1. Write the simplest code to turn the first test green.
2. Refactor your code to look clean and make sure the test still passes.
3. Repeat until all tests are passing.

For example, my first test might test mom, the second blah the third racecar.

mom

Taco cat

Al lets Della call Ed "Stella?"

These are all palindromes. Reverse the letters, ignore the spaces and punctuation, and it will be the same.

What are the test cases we should look for here? Test cases should validate the correct and the incorrect.

Next, write those test cases in mocha / chai or your test suite of choice. They should all fail.

What is the benefit of writing these tests first? Disadvantage?

Mobile games have completely changed the gaming landscape (for better or for worse (looking at you loot boxes)). Because they are small, can connect to the network, and have other limitations, developers have gotten creative with ways to make their games engaging, take advantage of time, allow players to interact with each other, and more.

Come up with 3 different features that are common in mobile games. For each, answer the following:

1. Why do you think this is a common feature?
2. Does this feature make the game more or less fair?
3. Is there a different way you could structure this to make the game more fair / fun while also still making a profit?

Igpay atinly isway osay uchmay unfay.

Itewray away ogrampray atthay anslatestray englishway intoway igpay atinlay.

Extension of last weeks challenge. Now, you have a date class that you feel pretty proud of. However, there's a chance you made some assumptions when building the class out. For example, consider the following assumptions:

• If allowing strings in the constructor, assumption regarding the format of the string.

• If adding / subtracting months, assumption needs to be made about going from a 31 day month to a 30 / 28 / 29 day month.

• If format to string, assumption on what the format looks like, or the distinguishing of what those special characters are.

• Assumption that a year has 365 days. (366 if a leap year).

We make hundreds of assumptions as we program daily, but rarely do we take notice of them. Even things we feel like are constants of the universe (gravitational constant, etc), physics is finding may have varied slowly over time.

Find the assumptions you used in your program. How can you mitigate those assumptions?

You know, just in case a country / business decides to adopt the IFC calendar (13 months, 28 days each, with an extra holiday "YEAR DAY", which doesn't belong to any year, or any week day)? Before you think that's crazy talk, remember that Kodak (the camera company?) used it from 1928 to 1989... dang.

Dates are awful to work with in most language libraries. Most languages have a date implementation which ends up covering up a lot of errors. Consider entering 04/30/2022. What date should that correspond to? Ideally, none - it should throw an error or return an invalid date object. Sadly, most languages will either push it to May 2, back to 4/28, or something else random. Worse, most languages make dates mutable which leads to odd side effects.

Write a Date class which uses best programming practices.

Sorry, not dragons. Drag and drop.

A variety of "No Code" solutions come, and go. Typically, the most successful ones are able to really nail keeping everything super stinking simple.

So, put on your thinking caps and consider the following. We want the ability to program anything with as much drag and drop as possible, and with as little keyboarding as possible.

Here are a few questions that come up from this:

• What programming paradigm(s) would work best for this?
• Traditional programs abstract things into functions, classes, modules, etc. How would this best handle abstractions?
• How would you allow 3rd party plugins?
• Would this include a type system, or would it be entirely loosely typed like JavaScript?
• What would be some of the advantages of a system like this?
• What are the pitfalls of a system like this?

I feel terrible. PI day was last week and we did nothing to celebrate it. So, here's a challenge to make up for it.

PI is a really weird number. So, let's play with it. Generate a program which returns the 1st, 10th, 100th, and 1,000th digits of pi.

Recently on Twitter, I came across an opinion that said comparing software development to martial arts was a terrible comparison. So, let's look at it ourselves!

Belts

Many martial arts assign belts to signify how deep into the discipline the student has progressed. Typically, you start at White, and end at Black, with an assortment of colors in between. To progress from one belt to the next, there is typically a demonstration performed to highlight the student's progress.

What would a belt system in development look like? Would this be something useful to follow to grow as a developer, or does it not really apply?

Katas

Many martial arts additionally perform katas or sets of movements designed to train particular responses to the point that they are muscle memory. Combining katas in different ways allows for unique offensive and defensive techniques. What connection to katas could we make to software? How do we train? Can they become muscle memory?

Dojos

Dojos are dedicated spaces for the practicing of martial arts. The most authentic are far more than just gym space - they include an alter, shoes must be removed before entering, and the utmost respect must be given to both the sensei and the dojo. Additionally, students are expected to be well groomed, show respect to each other, and be fully present in the now while at the dojo.

Contrast the attitudes of the dojo with the stereotypes of software developers. What could we learn from the dojo if anything?

Triangle Number: A number which is the summation of natural numbers. So, the 4th number in the set would be 1 + 2 + 3 + 4 = 10. The first few numbers in this set are 1, 3, 6, 10, 15, 21, 28 and so on.

28 has over 5 divisors: 1, 2, 4, 7, 14, and 28

What's the smallest triangle number with over 500 divisors?

Clicker games are one of my foibles. And my wife thinks I'm crazy for it haha. Basic clicker games look something like this:
```Step 1. Click a lot.Step 2. Spend clicks to upgrade your auto-clickersStep 3. Repeat.
```

I mean, there are also things like prestiges, and bonuses, and other things too, but those are the basics within the game most of the time.

Let's have a click game like follows:

```AutoClicker: 1 click / AutoClicker level / secondAutoClicker Cost: floor(1 click * (AutoClicker level)^(AutoClicker level * 0.01))
```

So, we have a nice little game which will slowly ramp up in difficulty.

There is 1 problem - we will quickly reach Number.MAX_INTEGER. What will you do as a workaround so we don't end up overflowing?

Arrays are fantastic. Sometimes, we need to remove all elements from them, making them empty once more.
```- List every possible way you can think of to make an array empty.- Which is the best? Why? (you may need define the definition of best haha)
```
There are a ton of apis that are just part of most modern browsers, yet we hardly use any of them.

Choose one api from MDN's list (link follows) that sounds interesting. Read about it. Make a fast summary which includes the following:

```- What is it?- Why would you use it?- What piqued your interest in this api?
```
Object collisions are an important part of many graphic applications (think space invaders, trello, etc). However, done poorly, it becomes incredibly expensive. If there are 100 objects, over 10,000 operations would be needed to compare each of them. However if one object is on one side of the screen, and another object is on the opposite side, we really don't need to compare them.

Enter Quadtrees. In English, it sounds something like this:

```1. Define a max number of objects in a quad2. Insert all of your objects into a quad and dimensions of quad3. If a quad exceeds the max number of objects**, quad quarters its own dimensions, creates a new quad for each, and inserts objects into each quad that it belongs to*.4. The above process repeats until either a max depth is reached or each quad has <= the max number of objects.
*  any objects which fit into more than one child quad must be added to each such child quad.** max depth is needed in case you have MAX_SIZE + 1 objects of same size on top of each other
```

This effectively groups objects which are close together into small clusters. How does this help? If 100 objects become 26 quads of 4 objects each (26 because of objects on boundary lines), we end up with 26 * 4!, or only 312 comparisons.

Write a quad tree implementation. Objects have a collides method which lets you know if they intersect with dimensions.

`object.collides(dimensions)`

A distance matrix is an nxn matrix with (i,j) representing the cost to travel from p_i to p_j. You can think of it as a fully connected directional weighted graph. Finding the shortest path that connects all points via brute force takes n! operations, making it increasingly less feasible as the matrix grows.

Create a solution which does not scan the entire set of paths but does create a decent approximation of the total cost and what that path looks like.

For kicks and giggles, here's one to play with:

```  const distanceMatrix = [    [0,648,2625,549,2185,1898,1458,1752,1963,427,1743,1817,1899,1060,1148,2084,732,1095,1725,2524],    [648,0,2363,481,2129,2030,1641,1594,1638,557,1214,1492,1710,1126,825,1861,811,1195,1375,2262],    [2625,2362,0,1965,669,1274,1541,920,744,2172,1623,875,720,1595,3085,543,3113,1734,1111,103],    [549,481,1965,0,1667,1605,1194,1132,1242,431,963,1096,1280,664,1249,1464,1276,799,979,1866],    [2185,2129,669,1667,0,621,906,541,643,1733,1504,733,459,1187,2880,479,2791,1169,932,566],    [1898,2030,1274,1605,621,0,443,662,978,1482,1669,925,839,1007,2855,929,2541,843,1107,1172],    [1458,1641,1541,1194,906,443,0,754,1106,1074,1447,976,968,638,2477,1148,2132,435,1027,1442],    [1752,1594,920,1132,541,662,754,0,347,1293,1015,261,209,724,2319,389,2346,841,443,818],    [1963,1638,744,1242,643,978,1106,347,0,1511,961,170,183,970,2361,287,2389,1124,388,688],    [427,557,2172,431,1733,1482,1074,1293,1511,0,1318,1363,1447,585,1378,1631,1063,641,1275,2071],    [1743,1214,1623,963,1504,1669,1447,1015,961,1318,0,813,1078,918,1571,1182,1882,1147,582,1583],    [1817,1492,875,1096,733,925,976,261,170,1363,813,0,271,826,2215,373,2242,979,241,774],    [1899,1710,720,1280,459,839,968,209,183,1447,1078,271,0,882,2453,192,2408,1049,504,621],    [1060,1126,1595,664,1187,1007,638,724,970,585,918,826,882,0,1891,1066,1667,251,798,1495],    [1148,825,3085,1249,2880,2855,2477,2319,2361,1378,1571,2215,2453,1891,0,2583,559,2042,2108,2984],    [2084,1861,543,1464,479,929,1148,389,287,1631,1182,373,192,1066,2583,0,2612,1220,611,442],    [732,811,3113,1276,2791,2541,2132,2346,2389,1063,1882,2242,2408,1667,559,2612,0,1701,2125,3012],    [1095,1195,1734,799,1169,843,435,841,1124,641,1147,979,1049,251,2042,1220,1701,0,977,1634],    [1725,1375,1111,979,932,1107,1027,443,388,1275,582,241,504,798,2108,611,2125,977,0,1011],    [2524,2262,103,1866,566,1172,1442,818,688,2071,1583,774,621,1495,2984,442,3012,1634,1011,0]  ]
```
Power set is the set that contains all possible subsets of a set including the empty set.

Ex: the power set of `{1, 2}` follows:

`{ {}, {1}, {2}, {1, 2} }`

Implement a power set implementation however you'd like, and explain why you chose to do it that way

Wordle is a daily word game that is going viral on Twitter. Check it out here:

Ignoring the UI, DB, and non-game critical features like those, implement wordle using either an FP or OOP approach. Why did you choose that approach?

Is node.js a framework, language, something else? What does that mean?

What is the event loop in JavaScript?

How can node take advantage of multiple cores on a machine if it is single threaded?

What kinds of apps is node best suited for?

Data structures of Rectangles could look like this:
```
Point = { x, y }
Rectangle = {  topLeft: Point,  height,  width}
```

Write OOP code that compares rectangles and returns the overlapping region (if any).

Remember that most drawing programs are a little backwards with regards to y. Increasing y takes you down the screen, not up it, hence topLeft in place of bottomLeft for Rectangle.

Function Generators
```function * oneForever() {yield 1}for(const v of oneForever()) console.log(v)
```

The above program would run until cancelled by the user, logging 1 to the screen until done so.

```function * oneHundred(){ for(let i = 0; i < 100; i++) yield 100 }const oneHundredArray = [...oneHundred()]
```

The above program would fill the array with one hundred ones. Coolish, but check this out:

```const mySet = new Set(oneHundred())
```

This set would give you all of the unique values within oneHundred and do it in a single pass.

Generator functions conform to the iterable protocol, meaning you can use them with the spread operator, as initial values to the common data structures like Array, Set, and Map, and so on. This allows the function to be separated from the data structure and be more reusable.

Create a function which has a signature kinda like this:

```function * numStrTargetValueGenerator(numStr, targetValue) {} // yields a new valid combo on each pass
```

`numStr` is a string of number characters such as '123456789'.

`targetValue` is an integer such as 100.

A valid combo is the initial string with optional + and - between any of the characters such that running through the operations actually gives you the target value. For example, for '123456789' and 100, a valid combo would be '1+2+3-4+5+6+78+9' as when the string is evaluated, it returns 100. All numbers must be used, and the order may not be changed.

Let's have some fun! Let X_1 be an arbitrary positive integer:

If X_1 is even, X_2 = X_1 / 2. Else, X_2 = 3 * X_1 + 1

So, 4 -> 2 -> 1 -> 4 -> 2 -> 1.... oops. If we ever get to 1, we end up in a loop. So, for our intents, getting to 1 is getting to the end of the run.

Let stop distance = number of steps to get to 1. So stop distance for 4 is 2.

What is the smallest integer to get a stop distance >= 100?

It being December, it's time for Santa to check and double check his list. As it is massive, he keeps K different copies of list across a few different databases. His first step is to check and see what differences (if any) exist between the two lists.

Because of the size of the list, it can't be stored in RAM, let alone K copies at the same time. Also, even though he is a magical toy maker, he is subject to the same computational limits as most of us... so a naive O(N^2) approach for a few billion children is not really an option.

It doesn't really matter what each record line looks like, but if you really want to know, let's go with something like this:

```{  name: 'Steve Wonderlie',  address: 'Broomstick Cupboard, 13 Private Dr, London, England',  chimney: true,  goodScore: 0.75,}
```

So, the question:

What would you recommend Santa do to help this year's (and future years') comparisons?

Pareto Principle

80% of consequences come from 20% of causes.

In other words, a majority of the things that happen in life come from a very small portion of decisions.

Applied to business, 80% of our revenue comes from 20% of our clients (certainly true haha).

Applied to programming, 80% of the value of software comes from 20% of the code. How much of a project is boilerplate, and how much is actual algorithm? Another application, 80% of the value of most software comes from 20% of the features. How many of the features have you actually used within Microsoft Word?

The Pareto principle, applied well, allows you to focus on the critical 20% first which will generate the highest return on investment of time / energy / money / cpu cycles.

All of us is dumber than one of us

This is one of the quotes at Nasa. Turns out that we are heavily influenced by the responses of others. It "pre-seeds" our head to come up with similar responses.

For example, consider the difference between these two prompts:

```// 1. Come up with a unique, new pasta name:
// 2. Come up with a unique, new pasta name, you know, like Macaroni, Tortellini, etc:
```

People receiving the second are far more likely end their pasta with an `ni`, while the first generates more unique responses

Come up with 5 potential open source projects that you could create. Which of the ideas is the best? How much better is it?

If you have a team, have every team member do the above, and then evaluate together as a team.

DynamoDB is composed of Items which have the following structure:
```{  pk, // partition key  sk, // sort key  ...rest // whatever you want}
```

Things that share the same pk will be sorted by their sk. Querying can happen only by prefix searches of the sk.

For example, consider the following records:

```[  { pk: 'User', sk: 'User#1', name: 'blah' },  { pk: 'User', sk: 'Apple', tool: true },  { pk: 'Tool', sk: 'Apple' },]
```

I can get an item by providing the pk + sk like follows:

```db.get({pk: User, sk: User#1 })// { pk: User, sk: User#1, name: blah }
```

Or I could query like follows:

```db.query({pk: User, sk: begins_with(A) })// [{ pk: User, sk: Apple, tool: true }]
```

This means that if I want to be a little crazy, I could create a composite sk. Look at this:

```{ pk: Order, sk: 2020#01#01#Slippers },{ pk: Order, sk: Slippers#2020#01#01 },
```

An sk like the first would allow me to search across all Orders, all orders in 2020, all orders in january 2020, and so on.

An sk like the second allows me to search across all orders, search all slipper orders, search all slipper orders in 2020, and so on.

So, composite keys are pretty powerful and dictate what my system can and can't do. I can always insert the data twice to get both if I need.

With the refresher on DynamoDB above, let's assume we are going to custom build an ORM. It allows us to define models, runs get, query, update, delete commands, etc. What classes, interfaces would you define, what challenges do you see, and what other insights do you have?

The sum of primes < 10 = 2 + 3 + 5 + 7 === 17.

What\'s the sum of primes < 2 million?

Remember in your terminal you can run node to create a REPL to run your code, or you can run a js file by running `node myFile.js`

Aidia has a cash register that operates on a subset of JavaScript. It does not support iterative loops (sorrry for of) nor Array.forEach(), meaning solutions must use recursion. Additionally, this subset is so broken, you cannot get the size of the array using Array.length, but you can use the non-standard Array.empty() which returns true / false. Array expansion and destructuring, thankfully, do work. Given that change can be given correctly by using a greedy algorithm and the following function signature, what are the innards of this algorithm?
```/*  changeToGive: Int  cashDrawers: Int[] Denomination Size ordered by largest to smallest. For example, [2000, 1000, 500, 100, 25, 10, 5, 1] might represent common change between \$0.01 and \$20.00*/
const makeChange = (changeToGive, cashDrawers) => {  // Returns array of how many bills to give from each cash drawer}
```
Aidia has grown and now has many remote employees. They all have different schedules and need to find a time to meet every week. You choose what those input schedules look like, and what outputted meeting time is, but you need to write the algorithm in JS. What does that look like?