FastCode Challenge: Bank Loans

Create a program to determine ....

Imagine a group of banks. Each night banks must guarentee they have enough funds to cover some fraction of there holdings. If they do not have enough funds on hand, they may arrange with other banks to borrow the money overnight, assuming that bank has excess funds available. In fact, banks may act as "middle men", in effect passing along funds or debit to other banks. Thus as long as a group of banks has enough collective funds to cover their holdings, all banks in the group are in compliance. Data (N operations) ---- AVAILABLE,bank,excess REQUEST,bank,amount TRUST,bank,bank DOUBT,bank,bank (!!!) Output ------ number of groups number of banks in compliance 
{
    "groups" : 13,
    "banks" : 27
}
---------------------------------- B banks T trust relationships N days T x (bank,bank) N x (B x amount) ----------------------------------- OFFER,bank,excess REQUEST,bank,amount TRUST,bank,bank ----------------------------------- Data (~1B?? 64-bit operations) ---- TRUST,bank,bank 0 31-bit-bank-id 0 31-bit-bank-id OFFER,bank,amount 1 31-bit-bank-id 32-bit-signed-amount operations are sequential banks are initially compliant and untrusting (each bank forms its own "trust group") compliant banks may trust compliant banks (thus joining their trust groups) compliant banks who trust noncompliant banks become noncompliant noncompliant banks trust requests are ignored banks may offer funds to their trust group (positive amount) banks may request funds from their trust group (negative amount) banks with unsatisfied fund requests become noncompliant noncompliance is transitive (thus if any bank is noncompliant, all trust group members become noncompliant) noncompliance is permanent (once a bank is noncompliant it can never again be compliant) How many banks are compliant/non-compliant? How many trust groups are compliant/non-compliant? (this problem probably only takes 1-5 seconds to compute) ----------------------------------- Data (~1M 64-bit operations === 1T ops) ---- TRUST,bank,bank 0 31-bit-bank-id 0 31-bit-bank-id OFFER,bank,amount 1 31-bit-bank-id 32-bit-signed-amount operations are sequential banks are initially compliant and untrusting (each bank forms its own "trust group") compliant banks may trust compliant banks (thus joining their trust groups) compliant banks who trust noncompliant banks become noncompliant noncompliant banks trust requests are ignored banks may offer funds to their trust group (positive amount) banks may request funds from their trust group (negative amount) banks with unsatisfied fund requests become noncompliant noncompliance is transitive (thus if any bank is noncompliant, all trust group members become noncompliant) noncompliance is permanent (once a bank is noncompliant it can never again be compliant) How many banks are in compliance? consider operations as a queue, each iteration: pop one operation and push it on the back for each sequence of operations, determine if all banks are compliant Across all sequences, how many banks are in compliance? (there is no good way to create answers for this problem) -------------------------------- disjoint-set/union/find with agg(members) requires too much data -------------------------------- operations ---- add edge(a,b) remove edge(a,b) (if it exists) add attribute(a,t) remove attribute(a,t) (if it exists) conditions ---- (not) any connection has attribute (a,t) number of connections at least/most (a,n) is (not) connected (a,b) answer(s) ---- how many connected groups? how many edges? how many sum(|attributes in a group|)? (not very parallelizable) ----------------------------------- B banks B x (signed amount) T trusts T x (bank,bank) How many banks are non-compliant?

Problem ideas:

Input

Each dataset is a binary file whose length is a multiple of eight. Each 8-byte group is one little endian integer. For example the following shows the output from hexdump of input.bin, a possible input file.

$ hexdump -e '16/1 "%02x " "\n"' input.bin
01 00 00 00 00 00 00 00 02 00 00 00 00 00 00 00
03 00 00 00 00 00 00 00 04 00 00 00 00 00 00 00
06 00 00 00 00 00 00 00 FF FF FF FF FF FF FF FF
FE FF FF FF FF FF FF FF

The file described above contains the following sequence of integers: 1, 2, 3, 4, 6, -1, and -2.

Output

Your program should compute the sum of all integers provided and generate a JSON data structure containing a single integer member named sum. For example the above input should produce the following.

{
    "sum" : 13
}

Problem 1: Longevity

with gmp-size input

In general, run-length encoding is a trivial compression mechanism. It replaces a count of repeated data with a value-count pair. In the special case of encoding binary data, the value can be omitted since the values must alternate. For example, the run-length encoding for the binary number 1110000101100 is the sequence (3, 4, 1, 1, 2, 2).

If the binary value of each number in the sequence are concatenated together we obtain a new binary number: 11 100 1 1 10 10, which could, in turn, be run-length encoded.

The longevity of a number is the number of times a binary number can be run-length encoded and concatenated before the length of the bit sequence is reduced to two. For example, the longevity of 1110000101100 is eleven, as shown below.

1110000101100
    11100111010
    111011111
        111101
        10011
        11010
        10111
            1111
            100
            110
            101
            111
            11

Write a program to compute the longevity of several numbers. The first line of input will contain the number of binary numbers to process. Each binary number will appear on a line by itself without spaces. Binary numbers will contain at most 63 bits.

Each data set should produce one line of output indicating the longevity of the input number.

Sample Input

3
1110000101100
1010101010
0000000111111111111111

Sample Output

11
7
2

Problem ideas: