[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.

[Java] Array of doubled pairs

Given an array of integers return true if it is possible to reorder its elements in pairs so that arr[2 * i + 1] = 2 * arr[2 * i] for all i up to length/2

In other words, given an array of integers allowing negatives and duplicates, find if it is possible to use each element in a pair where the first element in the pair is half the value of the second element of that pair. Elements cannot be reused among different pairs.

[Java] Satisfiability of equations

Given a series of equality and inequality equations, determine whether they can be satisfied.

Equations are in the form:

a==b

a!=b

where a,b are the two variables involved.

Example:

a==b, b==c, c==a: OK

a==b, b==c, c!=a: KO

Similar to the graph coloring we saw before, we can apply the same method here but expand it to more colors.

We create an adjacency list from all equality equations, the linked variables (connected components) must all have the same color, we proceed by starting with a color and then assigning it to all variables connected to each other, we repeat this process for all variables without color, each time using a different color.

Then we parse all inequality equations and verify if any conflict arises.

This algorithm runs in O(V) space and O(E) time as we explore all edges (equations) once. We use V space for the stack when coloring as at most we can add each vertex only once (we only add if vertex has no color).

You can check my implementation of equationsPossible on my Gist along with some tests in EquationsPossibleJTests.

[Java] Graph bipartition (2 coloring)

Given a graph, return a possible 2 coloring of it.

The algorithm is simple, for each node in the graph, if it doesn't yet have a color, run a DFS from it.

The DFS will assign a default color (eg; 1) to the node, if it doesn't already have one, then for each neighbor:

• if it already has a color which is NOT different from the current node color, break and fail
• if it doesn't have a color, assign the OPPOSITE of the current node color (eg use formula 1 - node color to invert between 0 and 1), then run a DFS from that node

In the end, if we stopped early it means the graph can't be colored with only 2 colors (there is no possible bipartition), otherwise we will have a possible 2 coloring or our graph as output.

This algorithm runs in O(V) space and O(E) time as for each node we explore all its neighbors once (we don't invoke DFS again unless neighbor had no color) and at most we can put V nodes on the callstack for recursion.

You can check my implementation of twoColor on my Gist along with some tests in TwoColorBipartitionJTests.