current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 5 down vote favorite
2

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.

share|improve this question
1  
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. –  stokastic Dec 7 '14 at 19:03
2  
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? –  Peter Taylor Dec 7 '14 at 23:21
1  
@PeterTaylor let me guess: are you working on a closed-form? –  Soham Chowdhury Dec 8 '14 at 7:42
3  
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. –  kennytm Dec 8 '14 at 17:23
3  
In the interests of clarity, q(r,r-1,1) is the reciprocal of A001700. –  Peter Taylor Dec 10 '14 at 10:12

2 Answers 2

up vote 7 down vote accepted
+25

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];
    }
}
share|improve this answer
    
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! :) –  Anton Schigur Dec 10 '14 at 10:36
up vote 1 down vote

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;
}
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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