Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

DEVELOPERS

Name: Anonymous 2011-05-24 11:59

http://www.bittorrent.com/company/about/developer_challenge

Name: Anonymous 2011-05-24 12:10

The solution should be implemented using C, C++, or Python.
jews.

Name: Anonymous 2011-05-24 12:13

bittorrent.com
Solve this challenge. It is necessary for our main development work (bundling adware, adding adverstisements, slowly but surely ruining Ludvig's glorious code base).

BitTorrent creates advanced, innovative technologies to efficiently move large files across the Internet.
Actually, BitTorrent lives off its good name, and its business model is basically leeching off suckers who don't know any better.

A more appropriate challenge would be: How would you obfuscate the bundled software offers so they get installed onto more unsuspecting people's computers?

Name: Anonymous 2011-05-24 12:13

This is even easier than the Spotify one.

Name: Anonymous 2011-05-24 16:56

so if i post the solution here wouldn't they have to get a new challenge?

Name: Anonymous 2011-05-24 17:02

>>5
It's not about finding a single solution, it's about how well you do it.

Name: Anonymous 2011-05-24 17:26

You have 40 bowls, all placed in a line at exact intervals of 1 meter. You also have 9 oranges. You wish to place all the oranges in the bowls, no more than one orange in each bowl, so that there are no three oranges A, B, and C such that the distance between A and B is equal to the distance between B and C. How many ways can you arrange the oranges in the bowls?.

Name: Anonymous 2011-05-24 17:46

$ cat bc2.c; gcc -O3 -Wall bc2.c -o bc2; time ./bc2
#include <stdio.h>
#include <stdint.h>

#define BOWLS 40
#define ORANGES 9

int solutions = 0;

void rec(int oranges, int pos, int64_t bowls, int64_t distances)
{
    int i;
    if (pos >= BOWLS) return;

    rec(oranges, pos+1, bowls, distances);

    bowls |= (int64_t)1<<pos;
    oranges--;
    for(i = 0; i < pos; i++) {
        if (bowls & (int64_t)1<<i) {
            int dist = pos - i;
            if (distances & (int64_t)1<<dist) return;
            distances |= (int64_t)1<<dist;
        }
    }
    if (!oranges) {
        solutions++;
        return;
    }
    rec(oranges, pos+1, bowls, distances);
}

int main()
{
    rec(ORANGES, 0, 0, 0);
    printf("%d\n", solutions);
    return 0;
}

0

real    0m0.356s
user    0m0.355s
sys     0m0.001s

Nice challenge bro, took all of 5 minutes.

Name: Anonymous 2011-05-24 18:06

>>8
disqualified for misuse of int64_t as bitvectors

Name: Anonymous 2011-05-24 18:34

so that there are no three oranges A, B, and C such that the distance between A and B is equal to the distance between B and C.

What? This sentence just confused me. Can someone word this better?

Name: >>8 2011-05-24 18:39

>>10
Oh crap, I read it too fast, >>8 is wrong. Easy to fix but will cost some speed. I leave it as an exercise to the reader.

Name: Anonymous 2011-05-24 18:40

>>10
If you were to make a table of the distances between all of the oranges, none of the numbers would be the same (excepting the distance from A to B being the same as the distance from B to A.)

This is how mathematicians and computer scientists actually write and speak.

Name: Mathematician 2011-05-24 18:50

computer scientists
Don't try to get on my level (aka GOD TIER fags), CS fucktards. You just can't.

Name: Anonymous 2011-05-24 19:39

>>9,11
Fixed:

#include <stdio.h>
#include <string.h>
#include <stdint.h>

#define BOWLS 40
#define ORANGES 9

int solutions = 0;

typedef char t_bowls[BOWLS];
typedef char t_distances[ORANGES][BOWLS];

void rec(int oranges, int pos, t_bowls i_bowls, t_distances i_distances)
{
    int i, j;
    t_bowls bowls;
    t_distances distances;
    if (pos >= BOWLS) return;
    memcpy(bowls, i_bowls, sizeof(bowls));
    memcpy(distances, i_distances, sizeof(distances));

    rec(oranges, pos+1, bowls, distances);

    bowls[pos] = 1;
    oranges--;
    for(i = 0, j = ORANGES; i < pos; i++) {
        if (bowls[i]) {
            int dist = pos - i; j--;
            if (distances[oranges][dist] || distances[j][dist]) return;
            distances[oranges][dist] = distances[j][dist] = 1;
        }
    }
    if (!oranges) {
        solutions++;
        return;
    }
    rec(oranges, pos+1, bowls, distances);
}

int main()
{
    static t_bowls bowls;
    static t_distances distances;
    rec(ORANGES, 0, bowls, distances);
    printf("%d\n", solutions);
    return 0;
}

About 10x slower.

Name: Anonymous 2011-05-24 19:42

>>13
Hey mathematician. Why don't you try doing something like this for a change:

Name: Anonymous 2011-05-24 19:46

>>15
back to /b/ with you, please

Name: Fuck you, !Ep8pui8Vw2 2011-05-24 19:51

Fuck off, ``faggot''.

Name: Anonymous 2011-05-24 19:53

Man. Quote pyramids look totally rad with my custom /prog/ userstyle. Totally rad.

Name: Anonymous 2011-05-24 19:55

>>18
ur just jelly cuz u cant go past 4 nests lmao

Name: Anonymous 2011-05-24 20:00

>>9
How is using bitvectors a disqualification? You know nothing of computing.

Name: Anonymous 2011-05-24 20:09

>>20
It's not enterprise. You want to work in a company, right? First off, you should be using Java. Second, no tricky bits. All code must be self-documenting (identifiers should have at least 20  characters), and each line should be explained by two lines of comments. Finally, prepare your anus.

Name: Anonymous 2011-05-24 20:11

>>21
IHBT

I work in a company and I'm paid especially well for my EXPERT bit-twiddling skills.

Name: Anonymous 2011-05-24 20:16

>>22
...and then you woke up to your Visual J++ IDE. Game over.

Name: Anonymous 2011-05-24 20:40

Just for kicks:

#include <stdio.h>
#include <string.h>
#include <stdint.h>

#define BOWLS 40
#define ORANGES 9

int solutions = 0;

typedef char t_bowls[(BOWLS+7)/8];
typedef char t_distances[ORANGES][(BOWLS+7)/8];

void rec(int oranges, int pos, t_bowls i_bowls, t_distances i_distances)
{
    int i, j;
    t_bowls bowls;
    t_distances distances;
    if (pos >= BOWLS) return;
    memcpy(bowls, i_bowls, sizeof(bowls));
    memcpy(distances, i_distances, sizeof(distances));

    rec(oranges, pos+1, bowls, distances);

    bowls[pos>>3] |= 1<<(pos&7);
    oranges--;
    for(i = 0, j = ORANGES; i < pos; i++) {
        if (bowls[i>>3] & 1<<(i&7)) {
            int dist = pos - i; j--;
            if (distances[oranges][dist>>3] & 1<<(dist&7) ||
                distances[j][dist>>3] & 1<<(dist&7)) return;
            distances[oranges][dist>>3] |= 1<<(dist&7);
            distances[j][dist>>3] |= 1<<(dist&7);
        }
    }
    if (!oranges) {
        solutions++;
        return;
    }
    rec(oranges, pos+1, bowls, distances);
}

int main()
{
    static t_bowls bowls;
    static t_distances distances;
    rec(ORANGES, 0, bowls, distances);
    printf("%d\n", solutions);
    return 0;
}

This is about 22% slower, ergo be careful with bitfields. Using ints instead of chars has about the same speed impact.

With an instrumented build I see that the original version memcpy()s a bit over 16GiB, and the modified version accesses bit arrays about 2490 million times. So copying 6 bytes is faster than two shifts and a bitwise op. Kind of makes sense in retrospect.

Name: Anonymous 2011-05-24 21:53

Do you really need to write a program for this? BitTorrent devs don't know combinatorics?

The total number of arrangements is C(40,9). We wish to exclude any arrangement with 3 equidistant items. Subtract the total number of arrangements from the number of all arrangements with at least 1 set of 3 equidistant items. Pick any set of 3 equidistant items. Then there are C(37,6) ways to arrange the rest of them.

The rest of this problem is left as an exercise for the reader.

Name: Anonymous 2011-05-24 22:07

MATHEMATICS WINS AGAIN!!!

Fuck you Comp Sci fags.

Name: Anonymous 2011-05-24 22:48

>>27
You do know that CS is an application of discrete maths and other fun math stuff.

Name: Anonymous 2011-05-24 23:31

>>27
RECURSION!

Name: Anonymous 2011-05-25 1:54

Fuck you /prog/, now I have to solve it.

Name: Anonymous 2011-05-25 3:49

>>14
Is the output supposed to look like this? Seems very wrong to me.

0000000000000000000010100110000101100011
0000000000000000000011000110100001100101
0000000000000000000100010110100000011011
0000000000000000000100010110100000110011
0000000000000000000100110010100000011011
0000000000000000000101001100001011000110
0000000000000000000101100001100100001011
0000000000000000000101100011000000101101
0000000000000000000101101000000110001101
0000000000000000000110000110100000110011
0000000000000000000110001101000011001010
0000000000000000000110010100100000110011
0000000000000000000110011000001001010011
0000000000000000000110011000001011000011
0000000000000000000110011000001011010001
0000000000000000000110100001001100001101
0000000000000000000110110000001010011001
0000000000000000000110110000001011010001
0000000000000000001000101101000000110011
0000000000000000001000101101000000110110

Name: Anonymous 2011-05-25 7:42

>>30
No, the output is supposed to look like a single number. It looks like you modified it individual solutions. I do not see anything wrong with them though. Tell me which one doesn't have nine oranges, or find me three oranges A, B, and C within a solution such that the distance between A and B is equal to the distance between B and C. Otherwise tell me what seems wrong to you.

Name: Anonymous 2011-05-25 7:55

>>31
Oh, I think I read the question wrong.

Name: Anonymous 2011-05-25 8:05

Ricer version:

#include <stdio.h>
#include <string.h>

#define BOWLS 40
#define ORANGES 9

int solutions = 0;

typedef char t_bowls[BOWLS];
typedef char t_distances[ORANGES][BOWLS];

void rec(int oranges, int pos, t_bowls i_bowls, t_distances i_distances)
{
    int i, j, arec = pos+1 < BOWLS && oranges <= BOWLS-pos;
    t_bowls bowls;
    t_distances distances;
    memcpy(bowls, i_bowls, sizeof(bowls));
    memcpy(distances, i_distances, sizeof(distances));

    if (arec) rec(oranges, pos+1, bowls, distances);

    bowls[pos] = 1;
    oranges--;
    for(i = 0, j = ORANGES; i < pos; i++) {
        if (bowls[i]) {
            int dist = pos - i; j--;
            if (distances[oranges][dist] || distances[j][dist]) return;
            distances[oranges][dist] = distances[j][dist] = 1;
        }
    }
    if (!oranges) {
        solutions++;
        return;
    }
    if (arec) rec(oranges, pos+1, bowls, distances);
}

int main()
{
    static t_bowls bowls;
    static t_distances distances;
    rec(ORANGES, 0, bowls, distances);
    printf("%d\n", solutions);
    return 0;
}

This visits 30% less nodes (40568992 vs 57820588) but is less than 10% faster. I'm not sure heuristically stopping more searches earlier would be a worthwhile gain. I had another idea to speed it up but I forgot. In any case it should run in under 10 seconds in any decent modern computer.

Name: Anonymous 2011-05-25 11:04

#include <stdio.h>
#include <string.h>

#define BOWLS 40
#define ORANGES 9

int solutions = 0;

typedef char t_bowls[BOWLS];
typedef char t_dists[ORANGES][BOWLS];

void rec(int oranges, int pos, t_bowls i_bowls, t_dists i_dists)
{
    int i, j, arec = pos+1 < BOWLS && oranges <= BOWLS-pos;
    t_bowls bowls;
    t_dists distances;
    memcpy(bowls, i_bowls, sizeof(bowls));
    memcpy(distances, i_dists, sizeof(distances));

    if (arec) rec(oranges, pos+1, bowls, distances);

    bowls[pos] = 1;
    oranges--;
    for(i = pos-1, j = oranges; i >= 0; i--) {
        if (bowls[i]) {
            int dist = pos - i; j++;
            if (distances[j][dist]) return;
            distances[oranges][dist] = 1;
        }
    }
    if (!oranges) {
        solutions++;
        return;
    }
    if (arec) rec(oranges, pos+1, bowls, distances);
}

int main()
{
    static t_dists distances;
    rec(ORANGES, 0, (void*)distances, distances);
    printf("%d\n", solutions);
    return 0;
}

This is pointless, this damn thing just won't go much faster. Still waiting for that combinatorial solution, but I guess the mathematicians are satisfied just proving one exists.

Name: Anonymous 2011-05-25 14:01

>>34
C(37,6) is the combinatorial solution. This is first-year CS stuff.

Name: Anonymous 2011-05-25 14:18

>>35
C(37,6) as in 2324784? Because that's wrong, you fucking retard.

Name: Anonymous 2011-05-25 14:48

>>36
Okay cockmaster buttrange, put some different fucking numbers in. It's a combinatorics problem, the hamfisted ways in other solutions are just overcomplications.

Name: Anonymous 2011-05-25 15:10

>>37
No number C(x,y) or P(x,y) where
- x and y are natural
- x <= 100
- y < x
matches the problem's solution.

Maybe BitTorrent is a bit too much for you after all.

Name: Anonymous 2011-05-25 15:37

New challenge

The problem is the same, however, now no two oranges can be the same distance apart as any other two oranges.

For example, the first possible sequence would look like this:
1101001000100001000001000000100000001000

Name: Anonymous 2011-05-25 15:59

>>39
That version is way too easy. It's just a couple of special cases away from being permutations of the numbers from 1 to 9.
Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -