6
\$\begingroup\$

Challenge

You are given the following function:- enter image description here which is the same as:-

enter image description here

with the base cases q(r, b, L) = 1 whenever r ≤ L, q(r, 0, L) = 0, if r > L and q(r, 0, L) = 1, if r ≤ L.

Your task is to code a program that takes r as input, and outputs the value of q(r, r - L, L) for all L taking integer values from 1 to (r-1), where r is any nonnegative integer.

Example 1

Input

Enter the value of r: 2

Output

q(2,1,1) = 0.3333333333

Example 2

Input

Enter the value of r: 3

Output

q(3,2,1) = 0.1

q(3,1,2) = 0.5

Winning criterion

The code that can correctly output q(r, r-L, L) for all L taking integer values from 1 to (r-1), for the highest value of r, in less than 300 seconds. In case of a tie, the code with lesser runtime will be considered. As this is a runtime-based challenge, I shall test all submissions on my machine.

\$\endgroup\$
24
  • 1
    \$\begingroup\$ Your sum/product notations both use the letter k as their variable. I think this is technically valid, but it might be easier to read if you used two different letters. \$\endgroup\$
    – stokastic
    Commented Dec 7, 2014 at 19:03
  • 2
    \$\begingroup\$ Which of the two base cases takes priority when r < L and b = 0? And what value of b will be used in the winning criterion? \$\endgroup\$ Commented Dec 7, 2014 at 23:21
  • 1
    \$\begingroup\$ @PeterTaylor let me guess: are you working on a closed-form? \$\endgroup\$ Commented Dec 8, 2014 at 7:42
  • 3
    \$\begingroup\$ q(r, r-1, 1) == 2(r!)^2/(2r)! (oeis.org/A001700) and r(r, 1, r-1) == (r-1)/(r+1) (trivial). Haven't checked the others yet. \$\endgroup\$
    – kennytm
    Commented Dec 8, 2014 at 17:23
  • 3
    \$\begingroup\$ In the interests of clarity, q(r,r-1,1) is the reciprocal of A001700. \$\endgroup\$ Commented Dec 10, 2014 at 10:12

2 Answers 2

7
+25
\$\begingroup\$

Java

I've applied some algebraic transformation and dynamic programming.

public class CodeGolf42234 {
    public static void main(String[] args) {
        int r = Integer.parseInt(args[0]);
        for (int L = 1; L < r; L++) System.out.println(qDouble5(r, r-L, L));
    }

    private static double qDouble5(int _r, int _b, int L) {
        double[][] q = new double[_r+1][_b+1];
        for (int r = 0; r <= L; r++) {
            for (int b = 0; b < q[r].length; b++) q[r][b] = 1;
        }
        for (int r = L + 1; r < q.length; r++) {
            for (int b = 1 + (r - L - 1)/L; b < q[r].length; b++) {
                double sum = 0, m = 1;
                for (int k = 0; k <= L; k++) {
                    sum += m * q[r-k][b-1];
                    m = m * (r - k) / (r + b - 1 - k);
                }
                q[r][b] = sum * b / (r + b);
            }
        }
        return q[_r][_b];
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ Thank you for the submission. On my system (Windows, Netbeans IDE), the highest value of r that can be evaluated using this code, in under 300 seconds (297 seconds) is 731. Good job, Peter! :) \$\endgroup\$ Commented Dec 10, 2014 at 10:36
1
\$\begingroup\$

Java

Here's a recursive solution. Just like you wanted. You can always uncomment the output and display it if you want.

import java.util.ArrayList;
import java.util.Scanner;


public class HeaderFinder
{
static ArrayList<Double> answers = new ArrayList<Double>();
public static void main(String[]args)
{
    Scanner scanner = new Scanner(System.in);
    int r = scanner.nextInt();
    for(int b=r-1; b!=0; b--)
        for(int L=r-1; L!=0; L--)
            answers.add(formulate(r,b,L));

//  int i=-1;
//      for(int b=r-1; b!=0; b--)
//          for(int L=r-1; L!=0; L--)
//              System.out.println("q("+r+", "+b+", "+L+") = "+answers.get(++i));

}

public static double formulate(double r, double b, double L)
{
    if(b==0)
        if(r>L)
            return 0.0;
        else
            return 1;
    if(r<=L)
        return 1;
    double partone = (b/(r+b));
    double result = 0.0;
    for(int k=1; k<=L; k++)
    {
        result+=summation(r, b, k) * (b/(r+b-k)) * formulate(r-k, b-1, L);
    }
    return (partone * formulate(r, b-1, L)) + result;
}

public static double summation(double r, double b, int k)
{
    double rb = r+b;
    double mul=r/rb;
    for(int i=1; i<k; i++)
    {
        mul*=(r-i)/(rb-i);
    }
    return mul;
}
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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