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 22:58

>>39
Thank you.

Name: Anonymous 2012-01-05 23:00

>>37
Only appears to make correct answers for first 20 rows; 21 and later are completely wrong, and the 66th row causes a SIGFPE.

Name: Anonymous 2012-01-05 23:03

>>1
I've also discovered that going up into high row numbers, there are lots of huge negative values in the triangle, immediately signalling that your program gives the wrong result.

Name: Anonymous 2012-01-05 23:07

>>43
ould be integer overflow

Name: Anonymous 2012-01-05 23:08

>>44
That is true. Still, >>1 takes over ten times as long for row 10000 as >>38, according to >>40.

Name: Anonymous 2012-01-05 23:46

>>38
Amazing. The NTH_IN_ROW macro is specially clever. Hats off to you.

Name: Anonymous 2012-01-05 23:57

>>46
2/10

Name: Anonymous 2012-01-06 0:09

>>46
Thank you. I wanted my implementation to be as memory-efficient as possible.

Name: Anonymous 2012-01-06 0:12

>>42
Yes, that is because I use factorials. When fact(n) starts returning UINT64_MAX (18446744073709551615) or overflowing, the division in pascal() stops working properly. The SIGFPE happens when pascal() tries to divide by zero because of an overflow in either fact(col) or fact(row-col) which perchance happens to make either of them 0.
It shows up as early as row 20 because factorials grow faster than the binomial coefficients.

If one tried hard enough they could exploit the fact that n!/k! for k < n is the same as n*(n-1)*...*(k+1), to make it not overflow as quickly.

Name: Anonymous 2012-01-06 0:14

>>49
Isn't the use of factorials extremely slow, especially as your factorial results aren't cached? Wouldn't it be faster to iteratively add?

Name: Anonymous 2012-01-06 0:30

>>50
I don't particularly care about the speed, though. It would certainly be faster to add, as well as less error prone, because you can't trivially eliminate the factorial divisions and so things overflow rapidly.

The below works properly with row 20, but still gives incorrect results quickly:

uint64_t mul(uint64_t n, uint64_t k) {
    if (k >= n || n == 0) { return 1; }
    if (k == n-1) { return n; }
    uint64_t r = 1;
    while (n > k) {
        r *= n--;
    }
    return r;
}

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

Not to mention that going as far as implementing caching for something like this would be going way too far. I'm sure the cleanest, simplest and probably most efficient version will end up being >>38's.

Name: Anonymous 2012-01-06 0:32

sub pascal { [1], -> @p { [0, @p Z+ @p, 0] } ... * };

http://rosettacode.org/wiki/Pascal's_triangle

Name: Anonymous 2012-01-06 0:33

>>38
You could save a lot more memory by storing only the last and current rows, but I believe the malloc time overhead would be large.

Name: Anonymous 2012-01-06 0:35

>>53
How about allocating two arrays of n_rows length? That'd make the memory complexity O(2r) => O(r) (as opposed to O((r*r+r)/2) => O(r^2)) and still only require one or two (constant) malloc calls.

Name: Anonymous 2012-01-06 0:36

>>54
Hmm, didn't think of that. I could modify my pascal.c to implement that, thanks.

Name: Anonymous 2012-01-06 1:52

>>11
C89 doesn't have int64_t so of course that code doesn't conform.

Name: Anonymous 2012-01-06 5:31

Just to let you know, I've just finished scrubbing another toilet. What have you done in the meantime?

Name: Anonymous 2012-01-06 6:48

>>57
I added a bunch of mutexes to my functions.

Name: Anonymous 2012-01-06 7:45

>>57
I've begun a C and FastCGI-based imageboard.

Name: Anonymous 2012-01-06 7:59

From article:
>That gives a row from a Pascal triangle



#!/bin/python
def main():
    print("Gief number plox")
    row = input()
    print "row", row, "is"
    for i in xrange(row+1):
        print(fac(row)/(fac(i) * fac(row-i)))

def fac(x):
    if x<=1:
        return 1
    else:
        return x * fac(x-1)

main()
herpderp

Name: Anonymous 2012-01-06 8:08

>>60
>using the slower factorial method over the faster iterative addition method (time complexity: O(fuckingretarded))
>using input() instead of int(raw_input()) (allowing user code injection)
>using python
>using /bin/python which no known distribution uses instead of /usr/bin/python or better /usr/bin/env python

Name: Anonymous 2012-01-06 8:14

>>61
I haven't used python in a year. Cut me some slack.
Also, if I do raw_input() it'd be a string and I'd have to recast it.

Name: Anonymous 2012-01-06 8:17

>>62
There is no excuse for using Python at all. Also, using input(), like I said but you couldn't read, allows users to break your program with errors, and/or run code in the program with their input. This is fucking retarded.

Name: Anonymous 2012-01-06 8:24

>>63
This isn't meant to be enterprise code that millions of dollars depend on. It's a small sample to demonstrate a way of generating a row of Pascal's triangle.
If you can write better code than this, that's great for you. But don't get so worked up over every irrelevant detail, being butthurt doesn't help anyone.
You don't want to get a heart attack before you're 50.

Name: Anonymous 2012-01-06 8:40

>>64
Having a shitty time complexity is a BIG FUCKING DEAL.

Name: Anonymous 2012-01-06 8:50

>>65
It's a real deal in other situations and not relevant in this one.

Name: Anonymous 2012-01-06 8:50

>>66
Not relevant? How's blowing out reasonable runtime for any non-trivial triangle size?

Name: Anonymous 2012-01-06 8:53

>>67
I  don't do much mathematical processing (like in graphics or physics or other calculations), and I've never needed to deal with triangles like this in any of my work.

Name: Anonymous 2012-01-06 8:57

>>68

I
And therein lies the fallacy in your argument.

Name: Joseph D. Darcy 2012-01-06 12:56

Here is the ROBUST SCALABLE ENTERPRISE SOLUTION, it came out a lot faster than the program in >>38 I'm guessing this is more cache efficient. It's also more robust when it comes to bad input. I decided not to comment this time since some of you showed some ill-will the last time I did that.

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

int main (int argc, char **argv) {
  unsigned long int * over = NULL, * under = NULL;
  unsigned long int n = 0, i = 0;

  if (argc < 2) {
    fprintf(stderr,
        "usage: %s n\n",
        argv[0]);
    exit(EXIT_FAILURE);
  }

  errno = 0;
  n = strtoul(argv[1], NULL, 0);

  if (errno) {
    fprintf(stderr,
        "invalid literal for an unsigned integer: %s\n",
        argv[1]);
    exit(EXIT_FAILURE);
  }

  if (!n) {
    fprintf(stderr,
        "invalid value for n: %lu\n"
        "must be greater than zero\n",
        n);
    exit(EXIT_FAILURE);
  }

  over = malloc(n * sizeof(unsigned long int));

  if (over == NULL) {
    fprintf(stderr,
        "failed to allocate array\n");
    exit(EXIT_FAILURE);
  }

  under = malloc(n * sizeof(unsigned long int));

  if (under == NULL) {
    fprintf(stderr,
        "failed to allocate array\n");
    exit(EXIT_FAILURE);
  }

  over[0] = 1;

  for (i = 1; i < n; i++) {
    unsigned long int * temp = NULL;
    unsigned long int j = 0;

    under[0] = under[i] = 1;

    for (j = 1; j < i; j++)
      under[j] = over[j-1] + over[j];

    temp = over;
    over = under;
    under = temp;
  }

  for (i = 0; i < n; i++) {
    printf("%lu", over[i]);
    if (i != n-1)
      putchar(' ');
  }
  putchar('\n');

  free(over);
  free(under);

  exit(EXIT_SUCCESS);
}

Name: Anonymous 2012-01-06 12:56

>>68
Enjoy your O(22n) ``intuitive'', ``gets the shit done'' algorithms.

Name: Anonymous 2012-01-06 13:47

ENTERPRISE JAVA SOLUTION


[ @ ~/fhost/prog/pascal ] $ cat p.java
import java.util.ArrayList;
import java.util.List;

public class p
{
    private static final String SPACE = " ";
    public static void main(String args[])
    {
        print(pascal(Integer.parseInt(args[0])));
    }

    private static void print(final List<StringBuilder> a)
    {
        StringBuilder cur;
        int len = a.get(a.size()-1).length();
        int len2 = len/2;
        for(int i=0;i<a.size();++i){
            cur = mkspc(len2-a.get(i).length()/2,len);
            cur.append(a.get(i));
            System.out.println(cur);
        }
    }

    private static StringBuilder mkspc(int len,int max)
    {
        StringBuilder sb = new StringBuilder(max);
        for(int i = 0;i<len;++i)
            sb.append(SPACE);
        return sb;
    }

    private static List<StringBuilder> pascal(int n)
    {
        List<StringBuilder> r = new ArrayList<StringBuilder>();
        StringBuilder sb;
        long coe;
        int i,j;
        for(i=0;i<n;++i){
            sb = new StringBuilder(i*2);
            for(j=0;j<=i;++j){
                coe = fact(i)/(fact(j)*fact(i-j));
                sb.append(Long.toString(coe));
                sb.append(SPACE);
            }
            r.add(sb);
        }
        return r;
    }

    private static long fact(int n)
    {
        return(n<=1 ? 1 : n * fact(n-1));
    }
}
[ Fri Jan 06 01:43:30 ]
[ @ ~/fhost/prog/pascal ] $ java p 10
             1
            1 1
           1 2 1
          1 3 3 1
         1 4 6 4 1
       1 5 10 10 5 1
      1 6 15 20 15 6 1
    1 7 21 35 35 21 7 1
   1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
[ Fri Jan 06 01:46:44 ]
[ @ ~/fhost/prog/pascal ] $ java p 20
                                               1
                                              1 1
                                             1 2 1
                                            1 3 3 1
                                           1 4 6 4 1
                                         1 5 10 10 5 1
                                        1 6 15 20 15 6 1
                                      1 7 21 35 35 21 7 1
                                     1 8 28 56 70 56 28 8 1
                                  1 9 36 84 126 126 84 36 9 1
                              1 10 45 120 210 252 210 120 45 10 1
                            1 11 55 165 330 462 462 330 165 55 11 1
                          1 12 66 220 495 792 924 792 495 220 66 12 1
                      1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
                   1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
               1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
           1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1
       1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1
    1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1
1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1


u jelly?

Name: Anonymous 2012-01-06 16:08

int main()
{
   int col;
   printf("Which column to print? ");
   scanf("%d",&col);
   printPascal(col);
   return 0;
}
Implementation of printPascal function is left as an exercise for the reader.

Name: Anonymous 2012-01-06 18:39

This one should use up the least memory. Works until integer overflow happens.
#include <stdio.h>
#include <stdlib.h>

int main (int argc, char **argv) {
    unsigned long int inputrow, i, j;
    unsigned long int *row;
    scanf("%ld", &inputrow);
    row = malloc(inputrow*sizeof(unsigned long int));
    row[0] = 1;
    for(i=1; i<inputrow; i++) {
        row[i]=1;
        for(j=i-1; j>0; j--)
            row[j]+=row[j-1];
    }
    for(i=0; i<inputrow; i++)
        printf("%ld ", row[i]);
    free(row);
    return 0;
}

Name: Anonymous 2012-01-06 21:06

>>73
int main(/* ... */)
{
   /* ... */
}
Implementation of main() function is left as an exercise for the reader.

Name: Anonymous 2012-01-06 21:56

>>71

O(22n)
mother of god
what kind of silly algorithm would do this

Name: Anonymous 2012-01-06 22:11

>>76
According to Wikipedia ( https://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities ):
22n: Deciding the truth of a given statement in Presburger arithmetic

Name: Anonymous 2012-01-06 23:56

>>77
But it is capable of doing Strong AI after all!

Name: Anonymous 2012-01-07 4:06

>>78
Is it? You can't even multiply (by any variable) in Presburger arithmetic. It's much weaker than Peano Arithmetic, which allows multiplication, but then if you add multiplication, you can encode entire programs within arithmetic, making the deciding the truth value of some sentences undecidable (this result is known in some forms as Godel's incompleteness theorems). No Strong AI will be able to solve the general halting problem, but any strong AI (or even human "AI"), should be able to decide on various specific cases, and they can self-improve to decide on more and more of them, just never 'all'.

Name: Anonymous 2012-01-07 5:22

#/usr/bin/env python

def get_row (previous_row):
    new_row = []
    new_row.append (1)

    for i in range (len(previous_row) - 1):
        new_row.append (previous_row[i] + previous_row[i + 1])

    new_row.append (1)
    return new_row

def get_nth_row (n):
    i = 0
    row = [1]
    while i < n - 1:
        row = get_row (row)
        i += 1
    return row

def main ():
    # Print first 15 rows, rows start at 1
    for i in range (1, 15):
        print get_nth_row (i)

if __name__ == "__main__":
    main ()

Not the best implementation, but what do you think?
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 -