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

Pascal's triangle

Name: Anonymous 2012-01-05 17:41

Motivated by the Hacker News challenge in http://news.ycombinator.com/item?id=3429466 I just made this.


#include <stdio.h>
#include <stdlib.h>

int64_t* next_pascal_row(int64_t* previous_row, int64_t previous_size)
{
  int64_t* retval = (int64_t*)malloc(sizeof(int64_t)*(previous_size+2));
  int64_t i;
  for (i=0;i<previous_size+1;i++) {
    if (i==0 || i == previous_size) {
      retval[i] = 1;
    } else {
      retval[i] = previous_row[i-1] + previous_row[i];
    }
  }
  return retval;
}

void print_row(int64_t* row, int64_t size)
{
  int64_t i;
  for(i = 0; i < size; i++) {
    printf("%lld ",row[i]);
  }
  printf("\n");
}

int main()
{
  int64_t* first_row = (int64_t*)malloc(sizeof(int64_t));
  int64_t* previous_row;
  int64_t* next_row;
  int64_t i,size;
  first_row[0] = 1;
  size = 1;
  print_row(first_row,size);
  previous_row = first_row;
  for(i = 0; i<30;i++) {
    next_row = next_pascal_row(previous_row,size);
    size++;
    print_row(next_row,size);
    free(previous_row);
    previous_row = next_row;
  }
  free(next_row);
}
Opinions? Yeah, int64_t is probably a GNU extension, I don't care as long as it works with gcc. U mad? Also, post you're own solutions. If you can't do the Pascal, you can just go ahead and apply to your're nearest McDonald's, because you ain't worth shit.

Name: Anonymous 2012-01-05 17:41

Not PASCAL, didn't read.

Name: Anonymous 2012-01-05 17:47

Looks like crap. I did this, in C, in my college entrance exam (not in the US, I have no idea if there's such a thing there) and it didn't look like crap. I don't remember much else. Please, don't turn this into another fizzbuzz.

Name: Anonymous 2012-01-05 18:01

>>3
Listen, jerkface.

If you wish to assume the role of a post-USSR mathematical genius you better start posting some evidence that you're just a good-for-nothing blabbermouth.

Name: Anonymous 2012-01-05 18:33

>>1
And what do you do for a living? BTW, there are two three memory leaks in your program.

Name: Anonymous 2012-01-05 18:34

>>5
No there isn't. Every int64_t array that's malloced gets freed.

Name: Anonymous 2012-01-05 18:38

>>4
Fortunately, I missed USSR by one step to the west. I'm just about the furthest imaginable thing from a mathematical genius but I know how to write simple solutions to simple problems.

Name: kodak_gallery_programmer !!kCq+A64Losi56ze 2012-01-05 18:42

>>6
You still haven't told us what you do for a living. But yes, there is at least one memory leak. Pstt.. it's in main() you stupid fucker.

Name: Anonymous 2012-01-05 18:50

>>8
There is just one malloc()'d pointer in main() and it is free()'d because the for-loop is entered at least once. See, first_row is assigned to previous_row just before the loop and previous_row is free()'d after that. Pointers malloc()'d by next_pascal_row are free()'d by the same row, with the exception of the last one which is free()'d just after the loop.

But I provide expensive senior software engineering services to our client company as my nine to five job, if that was what you were asking.

Name: kodak_gallery_programmer !!kCq+A64Losi56ze 2012-01-05 18:54

>>9
Take a closer look at main(). 

int64_t* first_row = (int64_t*)malloc(sizeof(int64_t));

This line will cause a memory leak if the sign changes. Now there is another leak in main(). And for anyone that has a clue about C, please don't help this mental midget.

Name: kodak_gallery_programmer !!kCq+A64Losi56ze 2012-01-05 18:56

>>10
Also, I'm following ANSI/ISO C89 standards.

Name: Anonymous 2012-01-05 19:00

>>10
The sign of what? That does make zero sense. Sign of sizeof(int64_t)?

int64_t* represents a pointer to a memory area full of int64_ts.  A sign change here is an impossibility and makes no semantical sense.

WTF?

Name: kodak_gallery_programmer !!kCq+A64Losi56ze 2012-01-05 19:02

>>12
Listen you stupid fucker. What happens if the bit pattern is becomes unsigned? There will be a memory leak.

  A sign change here is an impossibility and makes no semantical sense.

A sign change is a possbility. The fact that you think it's impossible leads me to believe that you've never written a single line of real C code in your entire life. Also, a compiler can't detect a sementic error.

Name: Anonymous 2012-01-05 19:04

>>12
Now what's the range of int64_t you stupid shit jew? Now, compare this range to an unsigned int you stupid fucker. Now shut up and learn something.

Name: Anonymous 2012-01-05 19:05

>>13
sementic
Wanker.

Name: kodak_gallery_programmer !!kCq+A64Losi56ze 2012-01-05 19:07

>>15
Admit it. This guy is a bigger retard than FrozenRetard, I mean FrozenVoid.

Name: Anonymous 2012-01-05 19:09

>>13
uh what. int64_t* is a pointer type sharing the same value range as int*, void* or char*. The fact that it points to signed values is just a coincidence. Pointer is a pointer, and it's safe to cast the return value of malloc() to any kind of pointer.

I am not casting a pointer to a signed integer. Pay attention to the asterisks.

Name: kodak_gallery_programmer !!kCq+A64Losi56ze 2012-01-05 19:12

>>17
But what it points at will cause a memory leak. An yes, the bit pattern is signed. Maybe you should just shut the fuck up and take read the ANSI/ISO C89 standard. Also, you still haven't told me where the other memory leak in main() is?

Geeze, I'm I gonna have to run a memory profiler against your shit code and post the results for you?

Name: Anonymous 2012-01-05 19:12

Hacker News
I'm sorry, I can't hear you over the sound of a million dead Steve Jobs cocks in your mouth.

Name: kodak_gallery_programmer !!kCq+A64Losi56ze 2012-01-05 19:15

>>17
There is also a semenatic error in the for loop in print_row(). In other words, depending on the system, the results might not actually display to the screen.

void print_row(int64_t* row, int64_t size)
{
  int64_t i;
  for(i = 0; i < size; i++) {
    printf("%lld ",row[i]);
  }
  printf("\n");
}

Name: Anonymous 2012-01-05 19:15

>>18
As far as I know, I can malloc whatever I want and free cleans it up as far as I use the same pointer and don't do any dirty tricks. I also ran the code with instrumentation and checked that amounts of malloc and free match up.

GCC guarantees it.

Name: Anonymous 2012-01-05 19:17

>>20
But it works on my systems and adheres to the definition of printf(). If you're comjpiler doesn't support %lld, well, fuck you then.

Name: Anonymous 2012-01-05 19:19

>>21
Yes, that's true for a signed int. But again, what happens if the int becomes unsigned? Again, there will be a memory leak. And yes, there are trivial situations where something like this could happen.

Name: kodak_gallery_programmere !!kCq+A64Losi56ze 2012-01-05 19:20

>>22
I said it was a semantic error. In other words, the code will pass the compilation phase. However, the error will occur during run time. Holy shit you're one stupid fucker. Please tell me your trolling.

Name: kodak_gallery_programmer !!kCq+A64Losi56ze 2012-01-05 19:22

>>24
Now please refer to ANSI/ISO C89/99 for a more detailed explanation on what a semantic error is.

Name: Anonymous 2012-01-05 19:22

>>24
http://operatorchan.org/t/arch/src/t238339_2sqfmqy4.png

Name: kodak_gallery_programmer !!kCq+A64Losi56ze 2012-01-05 19:27

>>24
*you're*

Name: Anonymous 2012-01-05 20:23

My try. Please don't laugh too much. ANSI C.


/*public domain*/
#include <stdio.h>
#define MAX 512

int main() {
    int i, j, row_to_print, pascal[MAX][MAX];
    scanf("%d", &row_to_print);
    if (row_to_print == 1) {
        printf("1");
        return 0;
    }

    pascal[0][0]=1;
    for (i=1; i<row_to_print; i++) {
        pascal[i][0]=1;
        pascal[i][i]=1;
    }
    for (i=2; i<row_to_print; i++)
        for (j=1; j<i; j++)
            pascal[i][j]=pascal[i-1][j]+pascal[i-1][j-1];
    for (j=0; j<row_to_print; j++)
        printf("%d ", pascal[row_to_print-1][j]);
    return 0;
}

Name: Anonymous 2012-01-05 20:34

(define (p n)
  (define (q l)
    (if (null? (cdr l))
      '()
      (cons (+ (car l) (cadr l))
            (q (cdr l)))))
  (if (= n 0)
    '(1)
    (append '(1)
            (q (p (- n 1)))
            '(1))))

Name: Anonymous 2012-01-05 20:44

Apart from the memory leaks, malloc is still slow as fuck and should be avoided if possible.

Name: Anonymous 2012-01-05 20:54

'
>thread about Pascal's triangle
>not written in Pascal

Name: Anonymous 2012-01-05 20:56

>>28
This is actually a simple solution to a simple problem. Won't bother if it's O(fast) but it's way better than that faggot's convoluted answer to a simple problem.

Hey, kodak. Fuck off, ``faggot".

Name: Anonymous 2012-01-05 21:00

>>32
>implying it wasn't long established that kodak is a shitty troll

Name: Anonymous 2012-01-05 21:26



program Pascal;

var counter as integer;
var ptLine as integer[20];

procedure Step(istep as integer);
var couter as integer;
begin
ptLine[istep] := 1;
if (istep<>1) then write( " " + ptLine[1]);
if (istep>=3) then begin
for couter := 2 to istep-1 do begin
    ptLine[couter] = ptLine[couter] + ptLine[couter-1];
    write(" " + ptLine[couter]);
    end;
end;
writeln(" " + ptLine[istep]);
end;

begin
for counter:=1 to 20 do begin
    Step(counter);
    end;
end.

Name: Anonymous 2012-01-05 21:59



for couter := istep-1 downto 2 do begin
    ptLine[couter] = ptLine[couter] + ptLine[couter-1];
    write(" " + ptLine[couter]);
    end;
end;

^^ Fixed (? hopefully)

Name: Anonymous 2012-01-05 22:14

#include <cstdint>
#include <cstdlib>
#include <iostream>

uint64_t fact(uint64_t n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    uint64_t r = 1;
    while (n != 1) {
        r *= n--;
    }
    return r;
}

uint64_t pascal(uint64_t row, uint64_t col) {
    if (col > row) {
        return UINT64_MAX;
    }
    return fact(row)/(fact(col)*fact(row-col));
}

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cout << "Usage: " << argv[0] << " row1 row2" << std::endl;
        return 0;
    }
    unsigned int row1 = std::abs(std::atoi(argv[1]));
    unsigned int row2 = std::abs(std::atoi(argv[2]));
    for (int r = row1; r <= row2; ++r) {
        for (int i = 0; i <= r; ++i) {
            std::cout << pascal(r, i) << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

Name: Anonymous 2012-01-05 22:15

Truly embarassing! Apologies to all.

#include <cstdint>
#include <cstdlib>
#include <iostream>

uint64_t fact(uint64_t n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    uint64_t r = 1;
    while (n != 1) {
        r *= n--;
    }
    return r;
}

uint64_t pascal(uint64_t row, uint64_t col) {
    if (col > row) {
        return UINT64_MAX;
    }
    return fact(row)/(fact(col)*fact(row-col));
}

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cout << "Usage: " << argv[0] << " row1 row2" << std::endl;
        return 0;
    }
    unsigned int row1 = std::abs(std::atoi(argv[1]));
    unsigned int row2 = std::abs(std::atoi(argv[2]));
    for (int r = row1; r <= row2; ++r) {
        for (int i = 0; i <= r; ++i) {
            std::cout << pascal(r, i) << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

Name: Anonymous 2012-01-05 22:44

>>28
Square array = wasted memory. Also, using stack space is bad.
>>37
Using stack space is bad.
>>1
Multiple mallocs = slow.

And I present to you... the best pascal.c in this thread. Only uses enough memory to hold all the numbers. It's also the fastest-running program.

#include <stdio.h>
#include <stdlib.h>
#define NTH_IN_ROW(r, n) (((r) * (r) + (r)) / 2 + (n))
int main() {
        long *a, i, j, r;
        scanf("%ld", &r);
        a = malloc(sizeof(long) * ((r + 1) * (r + 1) + r + 1) / 2);
        for (i = 0; i <= r; i++) {
                a[NTH_IN_ROW(i, 0)] = 1;
                a[NTH_IN_ROW(i, i)] = 1;
                if (i > 1)
                        for (j = 1; j < i; j++)
                                a[NTH_IN_ROW(i, j)] =
                                        a[NTH_IN_ROW(i - 1, j)] +
                                        a[NTH_IN_ROW(i - 1, j - 1)];
        }
        for (j = 0; j <= r; j++)
                printf("%ld ", a[NTH_IN_ROW(r, j)]);
        putchar('\n');
        return 0;
}

Name: Anonymous 2012-01-05 22:56

>>38
not bothering to verify if correct, but, that is some nice looking code

Name: Anonymous 2012-01-05 22:57

./pascal = >>38
./a.out = >>1
delan@pluto ~ $ time echo 10000 | ./pascal > /dev/null

real    0m4.244s
user    0m3.690s
sys     0m0.530s
delan@pluto ~ $ time echo 10000 | ./a.out > /dev/null

real    0m47.387s
user    0m47.210s
sys     0m0.170s

OP is an idiot.
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 -