[Java] Partition array in K subsets of equal sum

Given an array of positive integers and a target K, determine whether it's possible to partition the array in K subsets of equal sum.

Example:

1,1,1,1 k = 2

it's possible to have two sets, each with a total sum of 2

1,1,1,1 k = 3

it's not possible to have 3 sets of equal sum

We first determine if this is generally feasible by looking at the total sum of elements in our array and comparing with K. If possible, each set should sum up to total / K, which means K must be a divisor of our total sum.

We then need to explore all possibilities to generate each subset, this is evident in this sample:

1,1,1,2,2,2 k = 3

The only solution is to pair each 1 with a 2, we cannot apply a greedy approach as we might miss this solution.

A bit similar to the house painting problem, we need to recursively explore our options keeping track of:

• number of "full" subsets, that is subsets we created so far that reached our target sum
• available elements, as we can only place each element in a single subset
• current sum of each subset

We start with no subset existing and all elements available and try an add each available element to a set until we reach the target sum. Everytime we use an element, we mark it as unavailable.

When a set reaches the target sum, we increase the number of "full" subsets and start creating a new subset repeating this logic.

When we have no more available elements, if the amount of "full" subsets is reached, we have our answer, otherwise we need to backtrack and explore a different configuration.

When we backtrack we simply mark the current element as available again, remove it from the current subset sum and proceed on the next element.

This approach gives us a (N * 2^N) time complexity as for each element we explore the option of choosing it or not for the current subset and worst case we repeat this process for each element in our array before we realize no solution exists. Not sure whether sorting the array would have a significant impact on the runtime since there can exist a configuration where the total sum is divisible by K but no arrangement of elements is possible, maybe sorting descending can on average be faster but not in worst case.

We use O(N) space instead for the recursion stack (can't have more than N calls as we pick each element once in a branch) and the array tracking the available elements.

You can check my implementation of canPartitionInKSubsetsOfEqualSum on my Gist along with some tests in CanPartitionInKSubsetsOfEqualSumJTests.

[Unity] Fury Farm

A sample 3D shooter game made with Unity.

Get the code from the repo or play online.

The animals have gone mad, defend your farm from their rage.

Controls:

AD - move left/right

SPACE - shoot

R - restart level

Q - quit

Interesting notes:

• FindObjectOfType<OBJECT_NAME>(); get an object in a script without binding it in input
• "this" is actually gameObject within a script
• InvokeRepeating("METHOD_NAME", START_DELAY, REPEAT_RATE); added to an Awake or Start method, will ensure the given method is called repeatedly according to configuration
• Random.Range(MIN, MAX) gives a random float between MIN and MAX both inclusive
• WebGL default screen size is 960x600, the game default aspect is "Free Aspect" (top left of Game tab), change in File->Build Settings->Player Settings the resolution for WebGL to match a different one and set the Game aspect to the same to test how would it look like on the user screen
• Cooldown logic can be added by tracking a float variable and updating it with -Time.deltaTime every frame, then checking if its value is less than some threshold to allow the player to execute the action again
  

[Java] Matrix path with at most K obstacle deletions

Given a MxN matrix of 0s and 1s where 1 is an obstacle, find the shortest path from 0,0 to M-1,N-1 (top left to bottom right) deleting at most K obstacles.

We for sure need a BFS, but need to tweak it a bit so we prefer fast paths that use as many deletions as other paths or fewer.

We therefore track for each cell the amount of deletions we have left when we reach it. If another path reached that cell before us AND had MORE deletions left, then the current path is not an optimal solution and we can discard it. This is because some faster (shorter) path exists that has higher chances of deleting obstacles down the road, so we should explore that path instead.

We use a queue of Integer[] to track the data we need: i, j, current path length, deletions left.

This gives us a O(MN) space and time solution.

You can check my implementation of shortestPathWithMaxKDeletions on my Gist, this time without tests because I am lazy so you can simply run leetcode instead.

[Unity] Fury Skies

A sample 3D plane flying project made with Unity.

Get the code from the repo or play online.

Much anticipated sequel to the exciting Fury Roads, it's time to elevate your rage to the skies.

Controls:

WS - pitch (up/down)

SPACE - turbo

X - invert pitch controls (down/up)

R - restart level

Q - quit

PrintScreen - take a screenshot of that beauty in action

Alt+F4 - close your browser and go take a walk with your mask on

CapsLock - bring that rage to the comments section

 

Interesting notes:

• GameObject component inheritance seems to behave differently from OOP inheritance, not all parent Components are inherited by the children (but are accessible via GetComponentInParent)
• Time.deltaTime can be used in transforms to equalize values between different systems running at different framerates
• FixedUpdate should be used to update physics related stuff (eg movement)
• 3D is weird: X axis = depth, Y axis = height, Z axis = width. So movement forward is on Z axis. Camera is not considered in the default transforms. I understand this is because Z axis is the direction the player is facing, making "forward" a Z change rather than X.
  
• Instantiate(PREFAB_PARTICLE_OBJECT, transform.position, Quaternion.identity).Play(); will spawn the particle effects in the current object position. Invoke this before destroying whatever you collided with and get an explosion animation.
• 3D particles are weird, provide a material, shape and color or you get pink cubes even if you change the startColor
• Input.GetAxis("Vertical") gives the current player input on Y axis (even in 3D)
• 3D is weird part2: right side view of an object in coordinates 0,0,0 is a camera with Y axis rotation -90 and X axis delta of +10
  

[Unity] Fury Roads

A sample 3D car driving project made with Unity.

Get the code from the repo or play online.

How to play is in readme or in game menu. Hit the barrier, avoid the boulder, be fast, release the rage.

Interesting notes:

• AudioSource.PlayOneShot: use this passing an AudioClip as input to play a sound file once when triggered
• Input.GetKeyDown(KeyCode): use this to determine whether the user pressed a particular key and avoid multiple triggers if the key was pressed over multiple frames
• GameObject.SetActive: parent can trigger child objects active/inactive with this, eg to swap models for same object on a certain event
• LateUpdate is invoked after Update, so if you have a follow camera, update position there to avoid jerky movement
• transform.Translate: move object (slide)
• transform.Rotate: move object (rotate)
• Vector3 has many static predefined vectors available eg: forward, up, one, zero
• Can tag objects and then check whether interaction happened with an object type looking at its tag eg: collision.gameObject.CompareTag(TAG) will be true if this object collided with TAG object
• Time.timeScale set to 0 stops game time, but can still read player inputs
• SceneManager requires import (using) UnityEngine.SceneManagement

[Java] Group anagrams

Given a list of strings, group all anagrams together.

Example:

asd, lol, dsa

return:

[lol], [asd,dsa]

Anagrams are words of the exact same length with the exact same characters, potentially in different places.

We can use this to our advantage to easily determine whether two strings are anagrams of each other using an idea similar to a basic string compression algorithm. We create a fixed size array with a slot for each character in the alphabet (26 total, 0 = 'a' and 25 = 'z') and we process each string counting how many times each character appears in it.

We then create a string from that array using a fixed format: Xchar1...YcharN

We can now use this string as key for a map, which will quickly determine whether two strings are anagrams of not. All strings that are anagrams are added as values to the same map bucket, we then simply collect all values in an output list.

This uses O(N) time as we process all strings once and do constant work for each (alphabet size is fixed at 26) and O(N) space as we store all strings in our map.

You can check my implementation of groupAnagrams on my Gist along with some tests in GroupAnagramsJTests.

[Java] Verify is string can be rotated to match target

Given two strings, check whether the first can be rotated any number of times to match the second.

Example:

asd, lol: not possible

asd, sda: yes with one rotation

The key insight to solve this problem is to realize that a string concatenated with itself will contain all possible strings resulting from all its rotations:

asd becomes asdasd

All rotations of asd are: asd, sda, das and we can see that asdasd contains all of them.

Then the problem becomes a search for substring, after having checked that both strings have same length.

We can use KMP algorithm to do a N+N search using N space, stopping as soon as we find the first match, if there is none, then the string can't be rotated in the other one.

You can check my implementation of isRotation on my Gist along with some tests in IsRotationJTests.

[Java] Make biggest number from list of numbers

Given a list of integers, combine them to form the biggest number possible using all given numbers. Example:

500,60 return 60500

1,2,3 return 321

We can cheat a bit and get the input as array of strings, but the approach is the same. The idea is we need to sort this input in a way that provides us with the highest numbers first.

However, it is not enough to simply compare numbers since the example shows that approach would lead to the wrong result: 500,60 the biggest number is 60500 and not 50060 even though 500 is bigger than 60.

This example does show the solution though: given two numbers we want to order them based on the resulting number, since 60500 is bigger than 50060, the order is then 60,500

To solve our problem in O(N logN) time and O(logN) space (use Arrays.sort()) we simply need to provide a comparator that does what we want, then take each number and combine it in the result.

You can check my implementation of makeBiggestNumber on my Gist along with some tests in MakeBiggestNumberJTests.