3
\$\begingroup\$

This is my solution to this SO question, which can formulated as

  • take the sequence A002260, i.e., 1, 1, 2, 1, 2, 3, ...
  • concatenate all its digits
  • find the digit at a given position (1-based)]

What bothers me is that my solution is rather complicated and fails near Long.MAX_VALUE due to overflow. I also wonder if this could be done in an error-proof way, since I ran through quite some off by one errors.

There's the code, a test and a demo.

public class Ogen {
    /** The length of the number {@code n} (in decimal representation) */
    int length(long n) {
        return LongMath.log10(n, RoundingMode.DOWN) + 1;
    }

    /**
     * The total number of digits in the sequence {@code 1, 2, ..., n}, i.e.,
     * the sum of {@code length(i)} of all positive {@code i} up to and including {@code n}.
     * */
    long cumulativeLength(long n) {
        if (n==0) return 0;
        long result = 0;
        final int maxLength = length(n);
        for (int numberLength=1; numberLength<=maxLength; ++numberLength) {
            // all numbers between min and max have the length numberLength
            final long min = LongMath.pow(10, numberLength-1); // 1, 10, 100, ... highest power of 10 not greater than n
            final long max = Math.min(10*min - 1, n); // 9, 99, 999, ..., n
            final long countOfDifferentNumbers = max - min + 1;
            result += numberLength * countOfDifferentNumbers * 1;
        }
        return result;
    }

    /**
     * The total number of digits in the sequence {@code 1, 1, 2, 1, 2, 3, ..., 1, ..., n}, i.e.,
     * the sum of {@code cumulativeLength(i)} of all positive {@code i} up to and including {@code n}.
     */
    long doublyCumulativeLength(long n) {
        if (n==0) return 0;
        long result = 0;
        final int maxLength = length(n);
        for (int numberLength=1; numberLength<=maxLength; ++numberLength) {
            // all numbers between min and max have the length numberLength
            final long min = LongMath.pow(10, numberLength-1); // 1, 10, 100, ... highest power of 10 not greater than n
            final long max = Math.min(10*min - 1, n); // 9, 99, 999, ..., n
            final double avg = 0.5 * (min+max);
            final double averageNumberOfOccurrences = n - avg + 1;
            final long countOfDifferentNumbers = max - min + 1;
            result += numberLength * countOfDifferentNumbers * averageNumberOfOccurrences;
        }
        return result;
    }

    /**
     * The biggest number {@code n} such that the sequence {@code 1, 1, 2, 1, 2, 3, ..., 1, ..., n} ends before
     * position {@code pos}, i.e., such that {@code doublyCumulativeLength(n) < pos}.
     */
    long fullSequenceBefore(long pos) {
        long lo = 0;
        // find upper bound
        long hi = (long) (Math.sqrt(pos)) / 2;
        while (doublyCumulativeLength(hi) < pos) {
            lo = hi;
            hi += 1 + (hi >> 4);
        }
        // binary search
        while (hi>lo+1) {
            final long mid = (hi+lo) / 2;
            if (doublyCumulativeLength(mid) >= pos) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        assert doublyCumulativeLength(lo) < pos;
        assert doublyCumulativeLength(lo+1) >= pos;
        return lo;
    }

    public char digitAt(long pos) {
        pos -= doublyCumulativeLength(fullSequenceBefore(pos));
        long lo = 0;
        long hi = pos;
        while (hi>lo+1) {
            final long mid = (hi+lo) / 2;
            if (cumulativeLength(mid) >= pos) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        pos -= cumulativeLength(lo);
        return String.valueOf(lo+1).charAt((int) pos - 1);
    }
}
\$\endgroup\$
5
\$\begingroup\$

Frankly I have been staring at the code for ... 20 minutes, and I can't figure out your algorithm. I can't even throw out a good guess as to whether the result is right, or not.

There are some style-related issues that do not help:

  • Cumulative is not spelled with 2 m's, and no e as you have it in doublyCummulativLength
  • The self-referential comments are not useful if you can't figure out where the logic/code should start from. Building up on the algorithm would be more possible if the right starting point was given. In other words, your comments assume too much about what people reaing your code will know (or otherwise I am too dumb to see the obvious stuff so the comments are not helping me).
  • You reference the class LongMath but that class is not included in the code. Your comments mention things like: // ... and occur on the average count2/2 times What does that mean? How can you be accurate to an exact digit with reasoning like that?
  • Code like:

        final long count2 = 2*n - (min+max) + 2;
        result += i * (max-min+1) * count2 / 2;
    

    makes little, or no sense to me. count2? What does that mean? max and min are not great either. Lots of constants too.

In general, the code is not primed for a sight-unseen review. I would need you sitting beside me so I can ask questions as I go through. That is not really suitable for Code review.

As an aside, I believe having a class that represents the sequence that is being used would make a really big difference for this code. You need to extract out the class, and iterate it to find 'the spot'.


I played around with this problem, and specifically targetted an overflow-safe solution, so that digitAt(Long.MAX_VALUE) will work. This is the code I have.

Note that I use a class, which allows me to keep a state, and then add to the state.

On my computer the test for digitAt(Long.MAX_VALUE) returns 4 in less than 2.5 seconds. I do not know if this is a good result, or not.

Also, I compared my results with a naive implementation for relatively small values.

Make of this what you will:

import static org.junit.Assert.*;
import org.junit.Test;


public class Seq2260 {

    public static char digitAt(final long index) {
        if (index < 1) {
            throw new IllegalArgumentException("No such position " + index);
        }
        Seq2260 sequence = new Seq2260();
        sequence.incrementPast(index);
        // OK, spans have been added until the current span contains the index.
        // locate the actual digit in the current span.
        return sequence.seekChar(index - sequence.nextOffset);
    }

    // SCALES indicate the number of digits in each scale, and the value where the scale changes too.
    // for example, SCALES[1] are 1-digit values, and when you hit the value 10, you are no longer
    // in SCALES[1].
    // SCALES[0] is only there to make the indexes line up.
    // The Long.MAX_VALUE is only there to make the range end.
    // Note that only Scales up to SCALES[9] will actually be used.
    // by the time you reach SCALES[10] (10,000,000,000) each number is 10 digits long
    // and the cumulative effect means that the index is now huge.
    private static final long[] SCALES = {0L, 10L, 100L,
        1_000L, 10_000L, 100_000L,
        1_000_000L, 10_000_000L, 100_000_000L,
        1_000_000_000L, 10_000_000_000L, 100_000_000_000L,
        1_000_000_000_000L, 10_000_000_000_000L, 100_000_000_000_000L,
        1_000_000_000_000_000L, 10_000_000_000_000_000L, 100_000_000_000_000_000L,
        1_000_000_000_000_000_000L, Long.MAX_VALUE 
    };

    //number of digits in a number
    private int scale = 1;
    // how far along the next span will start
    // start at 1 to be 1-based
    private long nextOffset=1;
    // how long the current span is.
    private long length = 0;
    // the last value in the span
    private long span = 0;

    private void incrementPast(final long index) {
        // this is an overflow-safe compare
        // nextOffset could hypothetically be a very small negative number (wrapped). The math
        // here is safe though, because a very large number subtract a very negative number
        // will overflow again and still be less than length.
        while (index - nextOffset >= length) {
            extendSpan();
        }
    }

    private void extendSpan() {
        if (nextOffset < 0) {
            // we have previously overflowed our limit. We only support a single overflow.
            throw new IllegalStateException("Attempt to extend mapping beyond Long.MAX_VALUE");
        }
        span++;
        if (span == SCALES[scale]) {
            scale++;
            if (span == Long.MAX_VALUE) {
                throw new IllegalStateException("Overflowed Long in a span....");
            }
        }
        // for large values, this will overflow. That is the limit of where we can map to.
        // we can handle one overflow (a negative offset). After that, we fail.
        nextOffset += length;
        length += scale;
    }

    private char seekChar(long seek) {
        int sc = 1;
        long pos = 0;
        long val = 0;
        while (pos <= seek) {
            val++;
            if (val == SCALES[sc]) {
                sc++;
            }
            pos += sc;
        }
        // OK, so val includes the char, and it is....
        int charfromright = (int)(pos - seek);
        String value = String.valueOf(val);
        return value.charAt(value.length() - charfromright);
    }



    public static void main(String[] args) {
        System.out.printf("Confirm %s is %s%n", Seq2260.digitAt(1000), "" + smallGet(1000));
        System.out.printf("Confirm %s is %s%n", Seq2260.digitAt(10000), "" + smallGet(10000));

    }

    @Test
    public void testNaieveMatch() {
        for (int i = 3; i < 64 * 1024; i += 19) {
            assertTrue(smallGet(i) == Seq2260.digitAt(i));
        }
    }

    @Test
    public void testNaieveSequential() {
        for (int i = 1; i < 4 * 1024; i++) {
            assertTrue(smallGet(i) == Seq2260.digitAt(i));
        }
    }

    private static char smallGet(int i) {
        StringBuilder sb = new StringBuilder(i + 10);
        sb.append("-");

        int oldmax = 1;
        int current = 0;
        while (sb.length() <= i) {
            current++;
            sb.append(current);
            if (current == oldmax) {
                current = 0;
                oldmax++;
            }
        }
        return sb.charAt(i);
    }

    @Test
    public void testGetDigitAt() {
        assertEquals('1', Seq2260.digitAt(1));
        assertEquals('1', Seq2260.digitAt(2));
        assertEquals('2', Seq2260.digitAt(3));
        assertEquals('1', Seq2260.digitAt(4));
        assertEquals('2', Seq2260.digitAt(5));
        assertEquals('3', Seq2260.digitAt(6));
        assertEquals('1', Seq2260.digitAt(7));
        assertEquals('2', Seq2260.digitAt(8));
        assertEquals('3', Seq2260.digitAt(9));
        assertEquals('4', Seq2260.digitAt(10));

        assertEquals('5', Seq2260.digitAt(20));
        assertEquals('5', Seq2260.digitAt(33));

        assertEquals('9', Seq2260.digitAt(54));
        assertEquals('1', Seq2260.digitAt(55));
        assertEquals('0', Seq2260.digitAt(56));

        assertEquals('0', Seq2260.digitAt(67));
        assertEquals('2', Seq2260.digitAt(99));
    }

    @Test
    public void testLongMax() {
        assertEquals('4', Seq2260.digitAt(Long.MAX_VALUE));
    }

}
\$\endgroup\$
  • \$\begingroup\$ My comments are clearly not the best, but I don't get "self-referential". ++ LongMath is from Guava, which can be seen in the imports (not given here, but in the linked code. ++ The comment starting with the ellipses is a continuation of the previous one. ++ I'm sorry that it's so hard to understand, I guess I have to work on it. ++ My code works till index 4e18, so extracting the sequence won't finish before the cold dead of the universe. ++ Thanks a lot. \$\endgroup\$ – maaartinus Aug 31 '14 at 3:58
  • \$\begingroup\$ The referential comment for doublyCummulativLength is: The sum of cummulativLength(i) of all positive i up to and including n. 'i' is an internal variable, and it does not explain what cumulativLength is. The comment is not self-standing, it requires other comments, and the code, to work. That's what I meant by 'self-referential'. \$\endgroup\$ – rolfl Aug 31 '14 at 12:49
  • \$\begingroup\$ I wouldn't call it self-referential as it points to a different method, but otherwise I full agree and will improve it. It can be formulated much better and I wonder why I didn't do it. \$\endgroup\$ – maaartinus Aug 31 '14 at 13:19
  • \$\begingroup\$ Added an alternate solution using a class system to keep state data. This solves the problem up to Long.MAX_VALUE. \$\endgroup\$ – rolfl Aug 31 '14 at 22:46
  • 1
    \$\begingroup\$ All the errors were on my side. One of them was using double for count (precision loss above 2**56) which I introduced when beautifying the code). Others were overflows due to inconsequent use of unsigned comparison. As always: 1. longer code => more bugs, 2. optimization => more bugs. \$\endgroup\$ – maaartinus Sep 3 '14 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.