6 kyu
Pascal's Triangle
5,574 of 11,682boatmeme
Loading description...
Arrays
Mathematics
Algorithms
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
sorry for my importunity, but there's a typo here: "but depending on seleced method" -> selected method
Fixed.
Thanks!
What to do if I have reached max buffer size? I have no idea how to solve this in a different way.
Your solution is almost good, but has a bug, and becomes inaccurate at some point. See following:
Here is row 57 (yours vs expected), which is correct:
Here is row 58 (yours vs expected), which starts getting inaccurate:
See how your solutions gets
9929472283517788vs9929472283517787incorrectly at row 58. Similarly, all rows beyond 58 contain more and more incorrect numbers. You need to fix a bug in your solution (a very small one!)Odd that you have to flatten the triangle, but I guess it's a diferential.
python new test framework is required. updated in this fork
Approved by someone
it was a nice one but i'm confused as to why when n=2 it has to return [1,1,1] not [1,1]
Because you need to return the first
nrows. The first row is1, the second row is1,1, so forn = 2, you need to return both rows:[1, 1,1]thank you dude
Common Lisp translation, please approve / reject (author inactive).
There is an error in the test cases when n > 2. In my program when n = 3 my result is length = 6 and array(1,1,1,1,2,1) In my program when n = 6 my result is length = 21 and array(1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,1,5,10,10,5,1) etc... All my tests have a correct answer, but something is wrong with the test cases because it tells me that it is not correct. Please, solve the bug.
I have seen another error in the Sample Tests: move 3 to n move 6 to el move 1 to e(1) e(2) e(3) e(4) move 2 to e(5) perform doTest end tests.
It is wrong, the correct one is: move 3 to n move 6 to el move 1 to e(1) e(2) e(3) e(4) e(6) move 2 to e(5) perform doTest end tests.
Can someone fix the tests? Please
I can't see what is the language you have problems with? Seeing your code would also help.
Ups. I am sorry. It is COBOL.
I'll try to fix it, but I haven't touched COBOL in ages.
This translation is unmanageable. I've fixed the ref sol, but had to lower random test cases. If you want more random test cases, try to get in touch with original author of the translation on Discord.
dfhwze, with your fix it is now working much better. Now, the only error is when the input n is greater than 44, which must be truncating something in the tests
For example: Testing n = 45 , it returns Incorrect length Expected 35, but got 1035. The correct one is mine (1035) but it must be truncating 3 positions and that is why it does not go beyond 999 and says that the correct thing is 035 instead of 1035
Try again now. I lower limit even more. There's probably a pic 9(3) that needs to be pic 9(4) somewhere in the test setup.
I have passed the tests trying again and again until in the random tests there were no entries with n > 44 and I was able to submit the solution and it can be seen in "Solutions". My solution is correct, but it gives an error with n > 44 (and it should not give an error)
Okkk dfhwze. Now is working ok all the time. Thaaaaanksss
That was really satisfying to solve. The rules found on the wikipedia article helped a lot.
This comment has been hidden.
Just want to give a thumbs up for the formatting of the C tests (although there's some misalignment with the spaces)
I just refactored my solution from the version 2 of this since i did that first, still nice kata!
Was doing it in C, passed all the tests, tried to attempt but got this error:
Since the string is already allocated and we don't need to free, i guess there is a problem with the free in the test.
C tests work fine (I've just tried them). The problem comes from your code. You may post it with a spoiler flag for someone to try to find what's the problem.
Ruby 3.0 should be enabled (Refer this & this for more detail)
function name should use
snake_casedone
COBOL translation.
approved
C translation (author gone)
Approved :)
using Rust i can pass "Test" without overflowing by "u128" type - ok, nice at attempt i've got error "mismatching types" - my "u128" can't be compared with your "usize" at your function - ok, maybe i should change "u128" to "usize" ? - no, it's overflowing
my opinion is that it's not ok am i made a mistake somewhere?
(sorry my english, not native)
The instructions promise that the final result fits in usize, but they mention that intermediate values may be larger, maybe that's what's going on for you?
thanks, i got it)
Is this info related to a specific language? Because I don't get it at all.
It's the other way round: there's just a couple of languages where this remark is irrelevant.
Okay, and I'm guessing one of those languages is JavaScript? xD
Actually, the remark about overflow applies to JavaScript, and, at the same time, JS tests had a bug being affected by exactly this problem. Upper limit of JS tests got decreased so requested terms do not exceed
MAX_SAFE_INTEGERanymore.Languages which are not affected by overflow in this kata are languages where the default integer type is unbounded: python, ruby.
Very good description. Good Job putting the gif in there.
I really liked it, thanks!
This comment has been hidden.
You changed the required signature of the function. It should return, quotint the description, "top rows of Pascal's Triangle flattened into a one-dimensional list/array", and you changed it to
int[,].I have almost the same "Expected" and "but was" in the error for random and 60th, but it's quite hard to check all numbers. Anyway, any number i check is correct aaccording to "expected". What can be the problem?
Usually problems are related to overflow, and you can verify this by comparing your results to, for example, results returned by Wolfram: https://www.wolframalpha.com/input/?i=binomial%2860%2C30%29 . Run your solution locally for n=60, dump the answer to the console, and check numbers in the middle of the row, because these are the largest: (59 28), (60 30) etc.
It's possible that your calculations either overflow, or are inaccurate due to floating point division.
This comment has been hidden.
CoffeeScript: no random tests
added + chai assertions
Updated fork of Haskell translation, with added random tests, enabled GHC 8.2, and resolved merge conflicts.
Please review, and since I am not really good with Haskell, update if necessary or let me know what has to be fixed.
approved by someone
Fork of C++ translation with fix for non-compiling sample tests
Approved.
I think the formula in the description is flawed: (n k) = n!/(n-k)! According to this wiki page, the formula is: (n k) = n!/k!(n-k)! https://en.wikipedia.org/wiki/Binomial_coefficient
I tried the formula from the description and the generated elements are not correct. As for the second one, it is fine.
Oh dear, I am an idiot.
Sorry for that, will fix it.
Fixed in C++ translation
This comment has been hidden.
choosefunction is buggy, it introduces inaccuracies.Thank you very much!
K i didnt figure it out. How come my factorials are wrong for levels 60+ ?
How come my factorials are wrong for levels 60+ ?:)))))) does it has anything to do with my RAM or something?
Neverming I got it ;)
How did you handle it?
Used the right data format
what is the right data format? I know my logic is correct but it fails for n > 60
It's a common problem with python and bigger numbers using integer division gets rid of it, // instead of /
This comment has been hidden.
Your solution has floating point errors.
Rust translation kumited! :-)
Java translation with added random tests and resolved merge conflicts.
alr approved by someone
This comment has been hidden.
You are probably printing debug information. After 1.5 MB of that, the runner cuts you off. Don't print debug information.
This is very probably not a kata issue, and should have been labeled
Question.Issueis for when you're really quite sure the kata has a problem, and not your code.Also, tell us which language you're having this problem with, and post your code ( properly marked up and spoilered ). Help us help you!
Closing.
Some languages do not have random tests, e.g Haskell.
Already added
Module Sympy is not working. It was forbidden or something???
It's not installed, see List of supported Python modules.
( Haskell, possibly others ) ( Not JavaScript, possibly not others )
No random tests.
in python : OverflowError: Python int too large to convert to C long
all my tests pass but the "random test" due to the above line
how to overcome it?
"Don't use python 2"
?
im not ... its set on python 3.6
Forked Python translation, the author is long gone, so any power-user that can check it in a week or so...
Done.
This kata is REALLY good
I liked this kata, managed to find the numbers in only one loop :)
this kata is great, but I did not earn points ... do you know why?
Not kata-related.
It is throwing me an error "Cannot set property '0' of undefined" when I try to submit my solution. Although, I have tried the solution on other web based tools like jsbin and codepen and it works just fine there. I am not sure what is causing this problem. Any guesses ?
Have you edited the test cases? That should be the only difference between CodeWars and other tools.
No, I finally resolved it.
c# sample test wrong : n = 1 must reurn {1,1,1} not {1}.
n is the amount of rows, not the row number. The general convention is first row should be 0, son with n = 4 you should show 4 rows (0 to 3) and with n = 1 you should show row 0 only.
Added random tests to Ruby
Very good
This is supper KATA to show power of TDD. Because of this amazing gif image. When I stareted I had no idea about this algorithm, but step by step using tdd I made pretty nice solution. Thank you
JavaScript version. My code works fine in Atom. When I run the sample tests here I get this failure:
Test Results: Solution should test for something This is just an example of how you can write your own TDD tests - Expected: 'expected', instead got: 'actual'
Is there a mystery direction that requires I also write some tests for this!?
When I submit my code it works fine. The error only exists for the sample tests.
Just remove or comment the sample test case. It's hidden under the sample tests at the bottom.
I'm passing every test in Javascript except for n=25, which maybe means 25 has some clerical error in it (as AndrewsAnthony has also suggested, I think, below). Not encountering any timeout or similar. Any chance it could be checked? Nice Kata otherwise!
Just checked, its fine. Maybe you should look at your code instead.
Also, if you have problems with your own code you should raise it as a
questioninstead.Thanks for the reply, I'll look at it again and see if I can see an error and if not post as a question.
New to the site, so not familiar with how to categorise posts!
Managed to make it work in the end. Weirdly there were some slight inaccuracies in my numbers around n=24/25, at around the tenth decimal place! Not quite sure why/how, but fixed easily enough.
Watch out for floating point errors!
http://0.30000000000000004.com/
Ah, very interesting, thanks for the link!
Does have last test (25 rows) on Javascript the error? (sorry for my english)
No, I ran the top solutions and they work just as fine. So it's just you.
Some datatypes don't have sufficient precision to do the calculations accurately. Try using a decimal instead of a double (C#).
http://0.30000000000000004.com/
Javascript tests are not written.
They aren't random but there are here, but sure it lack random ones.
Yeah, the sample tests aren't there but the Attempt tests are.
Sad that noone tried to golf it in JS :/
Using recursive and got "Process was terminated. It took longer than 12000ms to complete". //PHP Version
Not a issue, simply optimize your code.
The only possible way to optimize is to use for loop instead of recursive. But recursive version is more understandable.
This comment has been hidden.
Please see my solution and guide me.
I can't unless you publish it here: is so, don't forget to use the spoiler flag. But my advise would be to use for loops on a first version, make it pass the tests then try to peak other solutions and to integrate recursion in yours.
Code problems belong to
question, notissue.You should add random tests too.
Added random tests to Ruby. Crystal, JS, PHP, Python already has them.
Coffee, C#, Haskell still needs them.
Reraised as issue
Ruby level 2 triangle is failing when producing the array [1,1] Problem specifies that the result should be a single dimensional array.
This is the first time I created my own test cases. Thought I followed the directions properly and created this line:
Test.assertEquals(pascalsTriangle(5), [ 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1 ]); The first argument being the function with its argument stated, and the 2nd argument being the answer expected. ...not sure what I did wrong.
Secondly, I hit submit to have the creaters test cases run and passed all the tests. ...Also did not get a final submit button to show.
Help would be greatly appreciated.
Very nice Kata! At first it seemed impossible, but then after studying a little of the Pascal's triangle it just kind of clicked you know? "It's array, everything is a array"
This comment has been hidden.
Take a look at row 11 (
[1, 11, …, 11, 1]). Compare it to what your outputs.Be careful with floating points!
Even after passing all the tests ("You have passed all tests! :)", the button "Submit Final" does not appear !!
What is wrong ?
Sometimes Codewars is a bit buggy. Try refreshing your page or come back at a later time and the submit final just reappear.
This comment has been hidden.
(i-1)(i-2)thinks you are trying to call the function instead of multiplying it. Just add a multiplication sign in between the brackets.Also, you should try to use three backticks (`) to format your code - see here
This comment has been hidden.
Your code works fine for me - maybe refresh the page? If you console.log()
nyou can see the tests. One example would be:I did tried the same. The console.log doesn't print the test cases. The error that I get is:
Solution should test for something ✘ This is just an example of how you can write your own TDD tests - Expected: 'expected', instead got: 'actual' Completed in 2ms Completed in 5ms
P.S. : I did tried submitting the solution this time. It worked. (Though 'Run Tests' button doesn't work even now for this problem. Please list an assertion in the test case. After submission, the problem solution works. :)
Thanks for your feedback.
If this is some kind of technical error, can you please redirect me where I should log this issue?
The tests you are looking at are example test cases or Test-driven development (TDD) tests. This box is for example tests and custom written tests - you can create your own tests and see how your solution matches up with the actual answer.
The Kata author can either provide you with some examples or let you write some of your own. This isn't a technical error, it has this box for all Katas. These tests do not needed to be passed to be able to pass and submit your solution, they are merely examples. Only the "submit" button tests need to pass in order to submit your solution.
'looks like u solved it'
Really fun Kata. I think you should explain in the description that the final array must have all the lower levels of the triangle and not just the level n.
Description seems to be clear:
PHP Translation Kumited, please accept :D
Here are test cases for the ruby people, so they can understand indexing and what the output should be
thanks, description is confusing
The description in Ruby version could be indeed made better with examples; I first looked over the "returns a single-dimensional array representing Pascal's Triangle to the n-th level." as a possible typo ("why not arrays in arrays? could it mean a single row instead?").
Also, it would be helpful if the test showed exactly what went wrong - I apparently had some problems with floating point accuracy on my first attempt, failing on larger numbers of the triangle.
Ruby example added to description.
Ruby version lacks an example output.
Ruby example added to description.
Returning a 2-dimensional array works as well as a 1-dimensional array for the "submit" (javascript).
I actually ran into the same issue. This needs to be solved.
Problem is the stringifying the testing does. Should use
Test.assertDeepEqualsinstead ofTest.expect . (===) `on` String.It is an issue and it can be solved, but I don't think the world will stop turning if it isn't.
JS version got updated (it had a serious bug in tests), and this issue should be resolved.
I enjoyed doing this kata is C#, but I'm going to do it later in Haskell. Solving it in something purely functional would be fun.
IMHO tests for this Kata should contain cases with some big N to force padavans to read some Wiki and to think about some code optimizations. Most of solutions have very straightforward algorithm but pass tests.
Or mark this Kata with higher kyu.
This comment is here for others starting on the kata so they can get the most out of what is an intriguing little kata.
From the wikipedia page the kata author cites: "The rows of Pascal's triangle (sequence A007318 in OEIS) are conventionally enumerated starting with row n = 0 at the top (the 0th row)."
However, the tests for this kata enumerate the rows starting with row n = 1 at the top (the 1st row). (The instructions do not warn that the kata is not following the conventional enumeration and give no worked examples.)
It's a fun kata which is not particularly difficult to solve. It's more interesting to solve with the kata author's variant, in fact. (I would have constructed my solution differently had I known about the unusual enumeration on the way in. As it was, I just tweaked a parameter to make it work and moved on.)
Uhm, but this is not a issue!
Shouldn't this be on higher kyu? Definitely fun but not really on the same par as efficient finding Hammond's numbers for example.
Agreed. This is about on par with most 5 kyu kata that I've done.
agreed. It's too easy for a 4 kyu.
It's been changed to 6 kyu some time ago.
Description is idiotic, what author actually wants is a WHOLE triangle mapped into one-dimensional array, not the n-th row. E.g.
2 -> [1,1,1] # first row then second row 3 -> [1,1,1,1,2,1,1,3,3,1] # first row, then second row, then third row
OH. God, I was wondering how [1,1] could possibly not be the second row of the triangle.
If the description is so short, they should be just some tests.
Thanks! It was driving me crazy!
yep
Seriously? If that's the case it should be asking for a List<List<int>> rather than just a List<int>.
Updated description to say:
(although it seemed to be clear enough for 7000+ users...)
This comment has been hidden.
Haskell test cases are probably bugged:
Factorials above 20 was a pain in the butt!
This comment has been hidden.
I thing type declaration
will work better for Haskell. Numbers in Pascal triangle grow pretty fast.
I spent 20 minutes debugging this, before realizing one of the tests I added had a typo... Not really a hard kata
Was going to do a Haskell translation but I noticed there are Python and Java translations sitting there that have not been added. I think I will wait until those are added, first.
I've done a Haskell one but yeah, it seems the author is no longer active. :(
The mods are supposed to add translations in this case, but apparently there is no reliable way to contact them on this site. I marked this as an issue to try to get their attention but that obviously did not work. I suppose it will just happen at random whenever a mod happens by the comments here.
Not a issue.
Thanks for this kata. I translated it to
java, feel free to merge it if you are happy with the translation.Solution have so much code.. check my best practice solution!
So this is a level 4, but I get only 1 honor point for completion?
How come?
I came here to ask this. Took me long enough. Was expecting at least 15 or so, like others. I did another 4 kyu that was worth 30! What gives?
This should be the n-th level of the pascal triangle Level 0 : [1] Level 1 : [1,1] Level 2 : [1,2,1] Level 3 : [1,3,3,1] Level 4 : [1,4,6,4,1] if you write pascalsTriangle(n)[k] with these values you have the binomial coeff of (n choose k).
Instead the test force us to level 4 == [1,1,1,1,2,1,1,3,3,1] which are binomial coefficient up from (0 choose 0) to (3 choose 3) no really the good value for 4. and with indexes all over the place, this kind of result would be very difficult to use in a real program
Please, Please, PLEASE, do not use animations which cannot be stopped, paused or hidden. See WCAG 2.1 and 2.3 http://www.w3.org/TR/WCAG20/.
Some of us have trouble thinking with the animation flashing. It is a little better if you click on the output tab.
Not a issue.
It should really be pascals_triangle rather than pascalsTriangle for Ruby style :)
This one certainly made me think. My first attempt failed on level 20 due to rounding errors, so I re-wrote it in a different way.
Your comment helped me, I wondered why it didn't work for 20 and came to read the comments to see if there was a problem with the test cases, but no it was my own code. Rounding errors on rows 11 and 15.
I thought I solved that kata - but can't find my solution anymore - did I dream (well, I could always blame my connection, couldn't I)?
The same from me
when I hit the "compare" to my solution button I only see part of my submitted code?
Ranking feedback? 4 kyu or 3 kyu?
This doesn't feel any higher than a 4 kyu or 5 kyu to me. Anybody who solved it wanna chime in?
I think the different algorithms possible make this a little less challenging, so 5 kyu feels about right.
Thanks guys. I'm going to go with 4 kyu for now as it seems more inline with the current crop of 4 kyu than it is the 5 kyu. Once the full-spectrum of kata difficulty is established I have a feeling a lot of these will need to be realigned later.
From experience it feels like a 4/5kyu.
The 25th level test case was a good catch for my factorial based solution, which ran into accuracy problems. I simplified the factorial expression to overcome the problem, but I am sure larger triangles would reveal this weakness in my solution whereas other algorithms that reference previous cells would not have any problems.
I think a good variant of this kata would be to ask for a single cell's value that is deep within the triangle.
That's a good suggestion for a kata variant.
In fact, I initially started off writing a more complicated kata that would've called for something similar - a Plinko-like pegboard game where the input is a target bottom slot and a 2d array of pegs and missing pegs, while the output is the optimal (highest-probability) top slot to drop the ball. I wanted to structure the problem in such a way that Dynamic Programming was required, but I hit some snags with the constraints of the sandbox. In the meantime, I distilled the basic idea down to Pascal's Triangle and wrote this kata.
Before I return to my initial idea, it might be worth it to implement your variation. Feel free to do so yourself. If you beat me to it, I won't be mad =)
What were the snags? The Ruby sandbox has been recently revamped and doesn't have many of the undefined method issues it had before.
Based on the error message, the snags seemed timeout-related, but I suspect it could have also been memory related; hitting a maximum stack-frame limit during recursion or simply due to the size of the arrays needed for memoization in a Dynamic Programming scenario.
I may just need to scale back the test scenarios to a maximum size that, while amenable to Dynamic Programming, might not necessarily rule-out brute-force solutions.
Hmm. I wonder if the timeout was increased to 5 or 6 seconds if it would do the trick. We could maybe add an optional flag to the kata editor that indicates that an increased timeout is necessary for that particular kata.
That could possibly work. My desktop executes the worst test-case with DP solution in under two-seconds. Brute force solution takes 18 minutes.
Some Kata could be solved using naive algorithms that require longer run times. Allowing for these could put a given kata at a lower ranked kyu. Making the long run times an option would be an easy way to make two katas from one problem - encouraging novice coders at first by allowing the longer running solutions and then tightening up the requirements as the novice coders learn how to refactor and improve their code.