Project Euler with Befunge


Fork me on GitHub
2014-09-24

Problem 040: Champernowne's constant

Description:

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021...

It can be seen that the 12th digit of the fractional part is 1.

If d(n) represents the nth digit of the fractional part, find the value of the following expression.

d(1) × d(10) × d(100) × d(1000) × d(10000) × d(100000) × d(1000000)


Solution:
v
>01:55+*:55+*:55+*:55+*:55+*:55+*130p v
         v                                           <
>110p120p>:10g920g**`!#v_10g920g**-10g1+10p20g55+*20p^>v          <
  >30g.@               >1-:10g/20g+\      10g%10g\-1-:|>\55+/\1-:#^_v
  $                                   $               >           :^
^_^#:                                 <#                p03*g03%+55$<
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

This one is really great - I came up with an O(log n) algorithm (crazy fast) for determining the n-th digit.
First I tested it in LinqPad, so here the C# code for the algorithm:

public int digitAt(int pos) {
    int digitcount = 1;
    int digitvalue = 1;

    // Get DigitCount of current number
    while(pos > digitvalue * 9 * digitcount) {
        pos -= digitvalue * 9 * digitcount;
        digitcount++;
        digitvalue *= 10;
    }

    // current number and digit-position in number
    int value = digitvalue + (pos - 1)/digitcount;
    int digit = digitcount - (pos - 1)%digitcount - 1;

    return getInternalDigit(value, digit);
}

public int getInternalDigit(int value, int digit) {
    return (value / (int)Math.Pow(10, digit)) % 10;
}

Interpreter steps: 1 486
Execution time (BefunExec): 16ms (0.09 MHz)
Program size: 69 x 7 (fully conform befunge-93)
Solution: 210
Solved at: 2014-09-24



made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript