Sequence of digits from natural numbers

Around a year ago I was taking a part, as a candidate, in a recruitment process in one of the world’s biggest and most innovative software companies. One question was to propose an algorithm to solve the following problem:

Given an infinite sequence made up of digits (in base of 10) from subsequent natural numbers find an element at a given position.

So the sequence goes like that: 123456789101112131415161718192021… At positions from 1 to 9 we have digits corresponding to numbers from 1 to 9. Next two elements are 1 and 0 because these are digits from number 10 which comes after number 9. And so on.

As I was not happy with an algorithm proposition I’ve presented to my interviewer I’ve decided to work it out. And here it is! And it’s in Java!

Solution description

The naive solution would be to generate the sequence in a loop by concatenating text representations of subsequent natural numbers until the sequence is longer than given position. Then one needs to get the element at the given position.

The complexity of the naive solution is linear: O(n). I wanted something better.

My solution consists of two parts:

  1. Determine (in a loop):
    1. How many digits (D) there are in a natural number that produced a sequence element (digit) at the given position?
    2. How many digits (elements of the sequence) were produced by natural numbers having less then D digits?
  2. Reduce the problem to finding an element of a sequence of digits made up from natural numbers having digits only.
    1. Transform the given position in the initial sequence into a new position into this simplified sequence by subtracting a total number of digits produces by all natural numbers having less than D digits.
    2. Which number having D digits is covering the element at the new position? This gives us an index of the D-digit number. It’s easy as every D elements of the new sequence is corresponding to a single D-digit number.
    3. What this D-digit number is? It’s easy as this is the first D-digit natural number (10 ^ (D – 1)) plus the calculated index.
    4. Which digit of this D-digit number corresponds to the given position? Easy again as this is the remainder of dividing the new position by D. This last step gives the answer to the problem.

Couple of findings:

  • The number of natural numbers having D digits: 9 * 10 ^ (D – 1)
    • There are 9 natural numbers with 1 digit, 90 natural numbers with 2 digits, etc.
  • The number of digits contained in all natural numbers having D digits: D * 9 * 10 ^ (D – 1)
    • All 1-digit natural numbers produce 9 digits, all 2-digits natural numbers produce 180 digits, and so on.

The algorithm in Java

public class WhatDigit {
	
	public static char solve(int position) {
		long n = position;

		// part 1
		int digits = 1;
		long offset = 0;
		long digitsCount = 9;
		while (Math.addExact(offset, digitsCount) < n) {
			offset += digitsCount;
			++digits;
			digitsCount = 9 * digits * BigInteger.TEN.pow(digits - 1).longValueExact();
		}
		
		// part 2
		n -= offset + 1;
		long numberIndex = n / digits;
		long number = BigInteger.TEN.pow(digits - 1).longValueExact() + numberIndex;
		int digitIndex = (int)(n % digits);
		if (digitIndex > 0) {
			number = number % BigInteger.TEN.pow(digits - digitIndex).longValueExact();
		}
		long element = number / BigInteger.TEN.pow(digits - digitIndex - 1).longValueExact();
		
		return (char)(element + '0');
	}
}

Remarks

I believe the complexity is in order of O(log(n)) because:

  1. The first part consists of a loop. The number of iterations is equal to the number of digits in the given position. Thus the number of iterations is proportional to the logarithm of the value of the given position.
  2. The second part could be considered as having a contant-time complexity. However this heavily depends on the complexity of the used implementation of a power function (BigInteger.pow(int) in my case). This is probably a weakness of my solution as the complexity of this implemetation of a power function is rather not O(1)… There is a solution however. As we need only powers of 10 we can iteratively calculate higher and higher powers in the loop in the 1st part using multiplication only and keep them in a dictionary. The highest power of 10 we need is 10 ^ (digits – 1).

In couple of places in calculations based on long values I used methods like Math.addExact(long, long) or BigInteger.longValueExact(). It’s because I wanted overflows on long to be detected and signaled with an exception.

Question at the end: can the part 1 be done in a constant time? 🙂

Nice mind exercise!

Advertisements
Posted in Java | Tagged , | Leave a comment

JavaScript, comparing numbers and null

Last time I’m programming quite a lot in JavaScript. And I discovered this kind of inconsistency when comparing a null value with numbers. Let’s consider this code in JavaScript:

var x = null;
var y = ... // some number

console.info('Comparing null with: ', y);
console.info('lt: ', x < y); 
console.info('gt: ', x > y);
console.info('eq: ', x == y);
console.info('lte: ', x <= y); 
console.info('gte: ', x >= y);

I was assuming null value compared to numbers will behave in a way somehow similar to that like NULL is behaving in SQL. Or at least I was assuming all above comparing expressions will be evaluated to false. The reality is even worse! Results are depending on a number which is value of y variable.

For y = 3 we get:

Comparing null with: 3
lt: true
gt: false
eq: false
lte: true
gte: false

So it looks null is considered in JavaScript to be less than 3.

For y = 0 we get:

Comparing null with: 0
lt: false
gt: false
eq: false
lte: true
gte: true

Total nonsense! null is not less than 0 and is not equal to 0 but… it’s less or equal to 0.

For y = -3 we get:

Comparing null with: -3
lt: false
gt: true
eq: false
lte: false
gte: true

At least we know JavaScript “thinks” null is greater than a negative number! 🙂

The conclusion is that you must be very cautious with null value in JavaScript. It should not be compared with numbers as results are against the logic.

Disclaimer: I was executing JavaScript in console of Firefox ver. 50.

BTW: It looks there are more inconsistencies in JavaScript! 😀

Solution

If you need to compare a variable against numbers in JavaScript and it’s possible this variable can be null then all these comparing expressions should use parseInt(x) instead of x. The value of parseInt(null) is NaN (not-a-number) which behaves nice (in line with common reason) when compared to numbers. So now we have:

console.info('Comparing null with: ', y);
console.info('lt: ', parseInt(x) < y); 
console.info('gt: ', parseInt(x) > y);
console.info('eq: ', parseInt(x) == y);
console.info('lte: ', parseInt(x) <= y); 
console.info('gte: ', parseInt(x) >= y);

Now all these expressions will evaluate to false no matter what number is the value of variable y.

NOTE: If your variable (like x in the example above) is going to hold floating-point numbers then use parseFloat instead of parseInt.

Posted in JavaScript | Leave a comment

Scala like Perl?

These days really many people (in the software development world) are fascinated by Scala. And on the other hand it’s practically impossible to find someone feeling similar about Perl. This is somehow surprising for me as I see similarities between these 2 programming languages. I think one of these similarities is rather unquestionable:

implicit parameters/variables

These are nasty things causing variables coming from nowhere with values silently assigned. Somewhere. In Scala these are called “implicit parameters”. In Perl these are “special variables”.

As far as I know there are no such things in Pascal, C, C++, Java or JavaScript. So you don’t need to study these languages hard to read source of programs written in them. That’s not true in case of Scala or Perl. You need to know these hellish language features to get an idea how the program works. Nice? Cool? Shorter? Unreadable? Expressive? Modern? Shitty?

Well, I don’t like it. And I don’t understand why people do accept one language having such things (Scala) but not the other one (Perl). I’ve found many comments about Scala that it’s modern and fresh. Each time I hear that I think it’s just trendy to use Scala. However “trendy” is something belonging to the world of fashion, not to the world of engineers. On the other hand people often find Perl as programming language hard to read. I guess thanks to these default variables (but maybe I’m wrong).

In that one I would agree: programs written in Scala and in Perl are unreadable (my opinion). And hard to maintain. Or at least it’s really easy to write programs in these languages that way. Such that it’s really unfeasible to fix a bug in such a program for someone not being Scala/Perl fanatic.

Actually I would say Perl has some advantages over Scala. It doesn’t need a JVM. It’s fast. It’s portable. It’s available almost everywhere (in the world of professional IT servers are driven by Unix/Linux which almost always has Perl installed). And Perl has one big disadvantage: it cannot easily use Java frameworks or libraries (what Scala can).

I had to use Scala for integration tests for one project I was working on in 2015. These implicit parameters were my nightmare. So in the huge mass of enthusiastic opinions about Scala I’m really happy there exist others who can take a critical look on it – see the article I Don’t Like Scala by Bozho.

PS. Perl has one funny application of “special variables”. They’re crucial in “Perl golf”!

Posted in Uncategorized | Tagged , , | Leave a comment

Gaming controllers for Linux!

Surprisingly I do sometime play computer games. Of course under Linux! With my sons I like car racing games so I needed a gaming wheel or a gamepad. And here the question arises to which I came as well:

Which gaming wheels or gamepads work well under Linux?

I can recommend 2 of such devices which I’ve checked personally. As I am a casual player please do keep in mind that these are probably not for “professional gamers”. But they’re good enough, have good quality and are not expensive. Both controllers have USB interface. Both are working out of the box under Linux (Linux Mint 17 at least):

  • Genius Speed Wheel 5 Pro – it looks like it can be not available in shops now as I bought it in 2012. These days it costed around 33 USD (105 PLN).
    Genius Speed Wheel 5 Pro

    Genius Speed Wheel 5 Pro

  • Logitech F310 Gamepad – bought at the beginning of 2017 for some less than 20 USD (75 PLN).
    Logitech F310 Gamepad

    Logitech F310 Gamepad

Both controllers are working very well in Grid Autosport under Linux (and it’s the best car racing game I’ve seen on Linux)! On the last Black Friday I’ve bought this game for just 10 EUR! This game is awesome also because it offers split-screen racing mode what I’ve checked with both above-mentioned controllers being in use at the same time!

And I can recommend this application for the initial testing (and some configuration): jstest-gtk

Posted in hardware, Linux | Tagged | Leave a comment

EasyMock vs Mockito

Just wanted to share my personal opinion on these 2 great mocking frameworks for Java. After years of experience with both of them…

…I say Mockito is better.

Mainly because it requires less code to do the same.

I don’t want to provide a detailed evidence. It’s just my personal preference which is a result of my professional experience with both frameworks.

One thing worth to mention: EasyMock was the first mocking framework for Java I started to use and I do not replace things without a reason. So I was likely not to switch to Mockito at the beginning. Yet it convinced me to do so. 🙂

Posted in Java | Tagged , , , | Leave a comment

Base64 utils for Java

Last time I needed to add Base64 encoding to represent some binary data as a text. Especially I needed the functionality of translating a part (with given offset and length) of a byte array and get a result as a String object (listed in point “D” below). Surprisingly such an operation is not provided by most Base64 utils for Java. Below is the summary of my findings. I’ve focused on operations matching following signatures:

  1. byte[] encode(byte[] data)
  2. String encode(byte[] data)
  3. ByteBuffer encode(ByteBuffer data)
  4. String encode(byte[] data, int offset, int length)
  5. byte[] decode(byte[] base64)
  6. byte[] decode(String base64)
  7. ByteBuffer decode(ByteBuffer base64)
Name Remarks Operations
Java SE API Since Java 8, rather uncomfortable API (separate classes for coder and decoder) A, B, C, E, F, G
Apache Commons Codec It’s additional 293 KB. Many exotic operations. Maven dependency. A, B, E, F
Spring Framework Only an option if already using Spring, however it’s mostly an adapter using the one of the above libraries or JAXB DatatypeConverter as a fallback. Maven dependency. A, B, E, F
iHarder.net Base64 It weights only 17 KB! Many additional operations. Home page. Maven dependency. A, B, C, D, E, F
Guava Really heavy: 2.3 MB. Only an option if you’re already using Guava. Maven dependency. B, D, F

My personal favourite is iHarder.net Base64. Small and does the job. If performance is your strong requirement please refer to this article: Base64 encoding and decoding performance.

Posted in Java | Tagged | 2 Comments

AES 256 without JCE Unlimited Strength Jurisdiction Policy Files

Once upon a time I wanted my Java application to encrypt/decrypt some data. I decided to use AES (Advanced Encryption Standard, Rijndael) encryption algorithm with 256-bit key. AES is supported by Java SE by a built-in JCA (Java Cryptography Architecture) provider so in theory no 3rd party library needed. So I turned first to JCA-based solution. However to use 256-bit keys with AES we need to install Java Cryptography Extension (JCE) Unlimited Strength Jurisdiction Policy Files. At least we have to do it with Sun/Oracle JVM. This document explains cryptographic key limits in JCA and here is an interesting citation:

If stronger algorithms are needed (for example, AES with 256-bit keys), the JCE Unlimited Strength Jurisdiction Policy Files must be obtained and installed in the JDK/JRE.

A working example of a code for encryption/decryption with 256-bit AES using JCA:

import java.nio.charset.Charset;
import java.security.Key;
import java.util.Arrays;
import javax.crypto.Cipher;
import javax.crypto.spec.IvParameterSpec;
import javax.crypto.spec.SecretKeySpec;
import net.iharder.Base64;

public class AesExample {

	private static final Charset utf8Charset = Charset.forName("UTF-8");

	// placeholder, real key should be loaded from a key store
	static Key loadAes256bitKey() {
		byte[] aesKey = new byte[32];
		for (int i = 0; i < aesKey.length; ++i) {
			aesKey[i] = (byte)i;
		}
		return new SecretKeySpec(aesKey, "AES");
	}

	// placeholder, real IV should be somehow better
	static byte[] loadIvBytes() {
		byte[] data = new byte[16];
		for (int i = 0; i < data.length; ++i) {
			data[i] = (byte)i;
		}
		return data;
	}	

	// opmode: javax.crypto.Cipher.ENCRYPT_MODE or javax.crypto.Cipher.DECRYPT_MODE
	static Cipher getJcaCipher(int opmode) {
		try {
			Cipher cipher = Cipher.getInstance("AES/CBC/PKCS5Padding");
			Key key = loadAes256bitKey();
			byte[] iv = loadIvBytes();
			cipher.init(opmode, key, new IvParameterSpec(iv));
			return cipher;
		} catch (Exception ex) {
			throw new RuntimeException("Cannot intialize cipher. " + ex.getMessage(), ex);
		}
	}

	static String encode(String value) {
		try {
			byte[] encoded = getJcaCipher(Cipher.ENCRYPT_MODE).doFinal(value.getBytes(utf8Charset));
			return Base64.encodeBytes(encoded);
		} catch (Exception ex) {
			throw new RuntimeException("Data encryption failed. " + ex.getMessage(), ex);
		}
	}

	static String decode(String encodedStr) {
		try {
			byte[] encoded = Base64.decode(encodedStr);
			byte[] decoded = getJcaCipher(Cipher.DECRYPT_MODE).doFinal(encoded);
			return new String(decoded, utf8Charset);
		} catch (Exception ex) {
			throw new RuntimeException("Data decryption failed. " + ex.getMessage(), ex);
		}
	}

	public static void main(String... args) {

		for (String inputText : Arrays.asList("", "a", "ab", "abc", "And here we have some longer message.")) {
			String encoded = encode(inputText);
			String decoded = decode(encoded);
			System.out.format("%40s => %s => '%s' (%b)\n", inputText, encoded, decoded, inputText.equals(decoded));
		}
	}
}

And maven dependencies for the above:

<dependency>
    <groupId>net.iharder</groupId>
    <artifactId>base64</artifactId>
    <version>2.3.9</version>
</dependency>

NOTE: the above example will not work with Sun/Oracle JVM without JCE Unlimited Strength Jurisdiction Policy Files. Installing these files turned out to be really annoying, at least for me. Solutions:

  1. Use another JVM instead of Oracle’s one, that is allowing stronger cryptography. Here I’ve found something about it (but haven’t tested): http://derjan.io/blog/2013/03/15/nevermind-jce-unlimited-strength-use-openjdk
  2. Use another encryption library to create a solution that is not depending on a JVM used… which is why I’ve created this article.

Bouncy Castle to the rescue!

The JVM-independent solution for using 256-bit AES is to use Bouncy Castle library and stick to its own API. It should not be a problem as the library is really stable and alive. I’ve seen it for the first time in a production-running code in 2007 and the last version of the library was released in December 2016 (as of 09.01.2017 it was 1.56). My solution was based on this handy article: BouncyCastle Lightweight API encryption example by “ofsdeveloper99”.

Let’s add following imports to the above example:

import org.bouncycastle.crypto.CipherParameters;
import org.bouncycastle.crypto.engines.AESEngine;
import org.bouncycastle.crypto.modes.CBCBlockCipher;
import org.bouncycastle.crypto.paddings.PKCS7Padding;
import org.bouncycastle.crypto.paddings.PaddedBufferedBlockCipher;
import org.bouncycastle.crypto.params.KeyParameter;
import org.bouncycastle.crypto.params.ParametersWithIV;

Let’s add following methods:

	static PaddedBufferedBlockCipher getBcCipher(boolean forEncryption) {
		try {
			Key key = loadAes256bitKey();
			byte[] iv = loadIvBytes();
			CipherParameters params = new ParametersWithIV(new KeyParameter(key.getEncoded()), iv);
			PaddedBufferedBlockCipher cipher = new PaddedBufferedBlockCipher(new CBCBlockCipher(new AESEngine()), new PKCS7Padding());
			cipher.init(forEncryption, params);
			return cipher;
		} catch (Exception ex) {
			throw new RuntimeException("Cannot intialize Bouncy Castle cipher. " + ex.getMessage(), ex);
		}
	}

	static String encode2(String value) {
		try {
			PaddedBufferedBlockCipher cipher = getBcCipher(true);
			byte[] input = value.getBytes(utf8Charset);
			byte[] output = new byte[cipher.getOutputSize(input.length)];
			int len = cipher.processBytes(input, 0, input.length, output, 0);
			len += cipher.doFinal(output, len);
			return Base64.encodeBytes(output, 0, len);
		} catch (Exception e) {
			throw new RuntimeException("Data encryption failed. " + e.getMessage(), e);
		}
	}

	static String decode2(String encodedStr) {
		try {
			PaddedBufferedBlockCipher cipher = getBcCipher(false);
			byte[] encoded = Base64.decode(encodedStr);
			byte[] output = new byte[cipher.getOutputSize(encoded.length)];
			int len = cipher.processBytes(encoded, 0, encoded.length, output, 0);
			len += cipher.doFinal(output, len);
			return new String(output, 0, len, utf8Charset);
		} catch (Exception e) {
			throw new RuntimeException("Data decryption failed. " + e.getMessage(), e);
		}
	}

And let’s change the main method to this:

	public static void main(String... args) {

		for (String inputText : Arrays.asList("", "a", "ab", "abc", "And here we have some longer message.")) {
			String encoded = encode(inputText);
			String encoded2 = encode2(inputText);
			String decoded = decode2(encoded);
			System.out.format("%40s => %s => '%s' (%b, %b)\n", inputText, encoded2, decoded, encoded.equals(encoded2), inputText.equals(decoded));
		}
	}

We need to add this dependency as well:

<dependency>
    <groupId>org.bouncycastle</groupId>
    <artifactId>bcprov-jdk15on</artifactId>
    <version>1.56</version>
</dependency>

Now the output should be:

                                         => 6cPvirI0U+bwdJzWNueojg== => '' (true, true)
                                       a => L854J/PY0dXgLD70k+z+sQ== => 'a' (true, true)
                                      ab => JOZH1E2V4fpZ+Ips93ZIfw== => 'ab' (true, true)
                                     abc => 6YtQ2v/uDI5Se7p4Weg3Ew== => 'abc' (true, true)
   And here we have some longer message. => LRY2Ny5DM1v2AMIhx1h7/edAZdHDOS+N0oywoERCSxAHpFvq45LtPC8wNkxapVXY => 'And here we have some longer message.' (true, true)

As you can see, both implementations of encryption/decryption with use of 256-bit AES are interchangeable. But the second one, based on Bouncy Castle, is JVM-independent. Forget JCE Unlimited Strength Jurisdiction Policy Files!!!

Posted in Java | Tagged , , , | Leave a comment