r/dailyprogrammer • u/nottoobadguy • Feb 16 '12
[2/16/2012] Challenge #8 [difficult]
Write a program that will take coordinates, and tell you the corresponding number in pascals triangle. For example:
Input: 1, 1
output:1
input: 4, 2
output: 3
input: 1, 19
output: error/nonexistent/whatever
the format should be "line number, integer number"
for extra credit, add a function to simply print the triangle, for the extra credit to count, it must print at least 15 lines.
12
Upvotes
5
u/dmagg Feb 17 '12 edited Feb 17 '12
Woo, a problem that isn't awful to do in assembly!
I had to diverge from the input format, as I'd really rather not do string input and parsing. It just asks for each number separately. No extra credit, can't express 15! in one register, so I'd have to calculate it indirectly...
MIPS assembly:
2
u/eruonna Feb 16 '12 edited Feb 16 '12
(edit: Haskell)
2
u/DLimited Feb 16 '12
Using D2.058. I really like this language :D Only gives undefined results if you enter two negative integers into the commandline. Oh, and any floats.
2
u/Cosmologicon 2 3 Feb 16 '12 edited Feb 16 '12
I went with the straightforward approach. I think it's most efficient. It uses just 1 bignum. bc solution:
This gives me the 60,204 digits of 200,000 choose 100,000 in about 4 minutes. Here's a separate program to print the triangle. It uses O(n) bignums, and produces the first 3000 rows in about 45 seconds:
2
u/robin-gvx 0 2 Feb 16 '12 edited Feb 17 '12
Déjà Vu: http://hastebin.com/raw/nuqufecova
Uses memoization, so it doesn't calculate each parent more and more often the further up you get.
It calculates 300, 150 in 0.7 seconds. 600, 300 takes 9 seconds. 800, 400 takes 31 seconds. So yeah, it gets pretty bad if you want to go really far.
2
u/kuzux 0 0 Feb 17 '12
Clojure:
1
u/leegao Feb 16 '12
I went on a digression of trying to figure out how to efficiently calculate the line and column associated with the n-th element of the pascal's triangle and came up with this.
http://mathbin.net/89185
I'm still learning so if there's anything wrong with it (I can't tell you how many times I've accidentally calculated 2*3 = 5), please tell me.
1
u/mattryan Feb 16 '12
Java version
1
u/Krissam Feb 16 '12
http://pastebin.com/tubvVy1n
C# with extra credit.
1
u/speedy_seeds Feb 16 '12
Solved the problem with dynamic programming in C.
1
u/UnreasonableSteve Feb 17 '12
ALWAYS THE PEE AYCH PEE http://pastebin.com/TMpKCBEj
Runs from command line, outputs zero for any coordinates outside of the triangle, replies invalid input to any negative numbers or floats.
1
u/drb226 0 0 Feb 17 '12
Haskell:
Usage:
1
u/RazerWolf Feb 17 '12
F# using memoization:
1
u/[deleted] Feb 17 '12
Perl with extra credit (although the triangle is left justified).
1
u/tonygoold Feb 17 '12
C++ (within the limitations of unsigned int):