13/10/2021

[Java] Kerberos login and retrieve GSSCredentials from KerberosTicket

A scenario that popped up recently was to login a user via Java code to Kerberos and retrieve a GSSCredential object containing the Kerberos ticket. I used Java 8, but this works since Java 7 onwards.

Java offers a Krb5LoginModule class which can be used in conjuction with a LoginContext to achieve this.

The flow is quite simple (once you have read all the Kerberos documentation):

  • on the machine where the code runs, place a correct krb5.conf file in the default location for your OS (Windows uses krb5.ini) OR set the java.security.krb5.conf system property pointing to the file
  • define a PasswordCallback handler class
  • create a LoginContext with a configuration using Krb5LoginModule and provide the password callback handler. The configuration must force the login to request a user input, which will then be routed to the callback handler. It is possible to use a keytab or cache credentials, but it's not shown here
  • login the user and get its KerberosTicket
  • create a GSSCredentials object using the ticket

This procedure allows handling multiple login mechanisms in the application and even multiple Kerberos realms.

11/10/2021

[Java] Calculate the angle between clock hands

return null;

Unless it's an analog clock, in which case:

The hour hand makes a 360 degree turn every 12 hours or 12*60 = 720 minutes, therefore each minute the hand moves 360/720 = 0.5 degrees

The minute hand makes a 360 degree turn every hour or 60 minutes, therefore each minute the hand moves 360/60 = 6 degrees

Setting 12 as the 0 position, to calculate the angle of each hand we can:

  •     hours = 0.5 * current minutes for that hour (60 * hours + minutes)
  •     minutes = 6 * minutes


We now have the position of both hand with respect to the 12 o'clock, the angle between them will simply be the difference, between the two positions (absolute value!)

If the difference is more than 180 degrees, the angle is a reflex angle and since we want the smallest angle between the hands, we take its complement by subtracting it from 360 (again, absolute value unless we did a modulo before to account for 24 hour format)

You can check my implementation of clockAngle on my Gist along with some tests in ClockAngleJTests.

[Java] Distribute items in K buckets

Something simple which comes up often when problems require some sort of item distribution.

Given an amount of items N and K buckets, distribute the items in the buckets as uniformly as possible.

Amount of items each bucket would hold in perfect distribution: N/K (integer division)

Amount of remaining items which could make some buckets hold extra items compared to others: N%K

Therefore simply place N/K items in each bucket, then calculate the remainder N%K and place 1 item in each bucket until remainder is 0.

Of course if K is bigger than N, some buckets will be empty.

[Java] Number of trailing zeroes in factorial

Given a number N, return the amount of trailing zeroes in its factorial.

Example:

4! = 24, no trailing zeroes

10! = 3628800, two trailing zeroes

100! = something big with 24 trailing zeroes

We could compute the factorial then count the zeroes, which is O(N) time and might work for small values of N, however multiplication can be indeed expensive.

02/10/2021

[Java] Generate the K-th number made only of primes 3, 5, 7

Generate the K-th number made only of primes 3, 5, 7.

Expected results up to K = 15: 1, 3, 5, 7, 9, 15, 21, 25, 27, 35, 45, 49, 63, 75, 81

This exercise is one of those that once the solution is known it's extremely easy but getting to the optimal solution requires work.

An initial suboptimal idea could be to start with a queue and placing only 1 in it.

Then execute some iterations where the top of the queue is polled, multiplied by 3,5,7 and then all results are added back to the queue, including the polled value.

We need to track generated values to avoid duplicating them. After some iterations, sort the queue, then poll until the k-th value is reached.

However the numbers generated this way quickly stray from the natural ordering so we end up generating more numbers that we need to get the actual solution.

After a long examination and paper examples (try drawing a matrix that expands with each new generated value and keep generating until the solution is reached), we notice that the emerging pattern is:

  • use a queue for 3s, 5s, 7s 
  • take the smallest top from all queues
  • multiply this value by 3,5,7 UNLESS it is bigger that the top of a queue, in which case we skip that queue, then push it back to the corresponding 3,5 or 7 queue
  • stop at k-th iteration, the min value generated at that step is the answer

This uses O(N) time and space and most importantly stops as soon as a result is reached.

You can check my implementation of generateKth357 on my Gist along with some tests in GenerateKth357JTests.

30/09/2021

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

26/09/2021

[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