6 kyu
Estimating Amounts of Subsets
983 of 2,100raulbc777
Loading description...
Fundamentals
Data Structures
Algorithms
Mathematics
Logic
Strings
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.
https://en.wikipedia.org/wiki/Pascal%27s_triangle The sum of the elements of row 2 ** n.
The solution is 2 ** n -1. From a mathematical point of view, why -1?
This comment has been hidden.
You should not use float division when you are performing integer calculations, floats are error prone. Next time please refer to this documentation to format properly your code: https://docs.codewars.com/references/markdown/#code-block
This comment has been hidden.
you are only using integers (except
nafter the first loop), you should make sure not to use floats at any moments because floats cannot hold large values accurately. For example :factorial(100)is not equal tofloat(factorial(100)).nshould never be a float.Hint: I could have your code passing all tests by just adding two characters.
This comment has been hidden.
C++:
This is incorrect.
According to Wolfram Alpha the result is in fact correct.UPD:
Nevermind, I was looking for completely different thing at Wolfram Alpha =)
Should be fixed now.
This issue still exists.
Please review: C++ Translation
Approved +1
I am timing out with itertools.combinations.
then don't use it
This comment has been hidden.
Please don't post solutions in the discourse page.
@HeberDamianAlturria you can't do that
Ohhhh, excuse me. I am noob XD
JavaScript fork
Can you publish a new fork fixing merge conflict in description?
done
Approved
PHP translation: https://www.codewars.com/kumite/634211ec3254ae40c6f17465?sel=634211ec3254ae40c6f17465
Approved +1
Fork attempting to improve description (motivated by this complaint and this complaint): https://www.codewars.com/kumite/633ee9e88968915a64235667?sel=633ee9e88968915a64235667
Note: to (hopefully) avoid merge conflicts, approve after all other translations are approved.
I want to cooperate in improving the descrption when a user points out a mistake in a sentence or in the use of English in general. I didn't see those ones.
Sure, feel free to reject, or fork and modify the translation.
I asked eloise for help after the user complained and there were no answer from you for some time. If you just missed it, now you know. You can handle it any way you want.
Fork fixing this along with better assertion messages and Chai
TypeScript translation: https://www.codewars.com/kumite/63361b0070a2b2004a718688?sel=63361b0070a2b2004a718688
Thanks @hobovsky for your work. Approved! +1
Also, and probably more importantly: "we need to know the amount of subsets that none of their values have repetitions" isn't a grammatical clause, which makes it harder to work out what the author intended
What would be your proposal of a grammatical clause?
How about something like this?: https://www.codewars.com/kumite/633ee9e88968915a64235667?sel=633ee9e88968915a64235667
"amount of subsets that don not"
Who is Don Not? ;)
Don Knotts?
File "/workspace/default/tests.py", line 6 @test.it('Sample tests'): ^ SyntaxError: invalid syntax
I tried testing my solution with python, but I got this error and I don't know how to fix it.
Hi, @trstnjrmm. Yesterday a new fork was submitted according with the new frame tests for python. Hope that @Siddharth114 could have a look. Thanks for your observation.
there was a mistake in my indentation
this fixes it
Thanks a lot @Siddharth114 for your fasts response.
.
C Translation
Thanks 👍+ 1
.
python fork with new test framework
Approved
Thanks @Kacarott. I woke up an hour and a half ago. :)
Thanks @Siddharth114 for your work +1
This comment has been hidden.
Your approach is correct, but implementation has a bug. What would be an expected answer for
est_subsets(list(range(63)))? What does your solution return?It returns 9223372036854774784
I just can't figure out what the mathematical equation is to be able to do this problem...
it turns out there are several ways
This comment has been hidden.
This comment has been hidden.
I will take a closer look but looking at your code, there indeed is a bug in your solution. Your code will fail for some inputs. The message does not seem right tho.
You need to fix your code, and I need to fix the message, I think.
I found my mistake, its a stupid copy/paste error :|
I will fix it soon. I am sorry for the problem.
Fixed.
Java translation.
Approved +1 Thanks
RISC-V translation Kumited - please accept :-D
It's approved. +1
Julia translation
It´s approved. +1
Cheers!
@depial Studying Julia. It has great features: speed and an easy to code for maths. Cheers!
It has a bit of everything :)
Scala translation
I tried to approve it. Some changes were made.
Doesn't look like it successfully approved. What does it say when you try to?
Ah looks like it was a description merge conflict, should be approvable now.
I tried to but I couldn't approve it due to some changes have been
I forked and approved (some invisible change in the description).
The system doesn't allow me to approve
Thanks akar!
Now it's running the Scala version. Thanks @KayleighWasTaken for your job and for considering my work, too + 1 for you.
I'll translate more of your stuff to Scala if you want, looks like most of your kata need it and you respond fast.
Excellent! I'm working at home these days, so I can he notifications fast. Go ahead with the translations.
Thanks @akar-0 for the help!
And if raulbc777 is sleeping, there is always a chance I review/approve your translations instead ;)
I'm in Paraguay, South America. (GMT -4) :)
Ok, I will go to bed before you :)
Sorry @KayleighWasTaken. I made a mistake. An user send me a solicitude of translation into Scala version of this kata. I approved it and I shouldn't have done it. I respect the job of all my codewarsmates here. I thought that it was related of one of my another katas.
@jcsahnwaldt, I hope that you're not going to feel bad about the previous message above. I'll be willing to approve your translations. All the languages available except Ruby, JavaScript, Python, Rust, D, Go, Julia, C# and Lua. You may choose one from the remaining 51 ones. Cheers!
Seems like a bug here. Once a language version has been approved, it is not possible to make new translations to this language that are not rooted by the one that has been approved. My fork of KayleighWasTaken's translation has been approved first. How is it possible that jcsahnwaldt's translation also appears as the approved one on the translation page?
I explained that in the previous message. Sorry for that. You deserve the apologies expressed above, too. And much more if there's a bug.
And for all you've worked on my katas. My bad
Don't feel so sorry, I think there is no harm. And if there is a bug you're not responsible. Now something else I cannot see any difference between the two versions...
https://www.codewars.com/kumite/63027209fedd5417e38da5f2?sel=63027209fedd5417e38da5f2
Pretty sure he changed the typing of the function signature from
List[Int|Char]toList[Int]|List[Char]. Not really a fan of either, I'm gonna switch it to generics.It's easy to restaure KayleighWasTaken's version if it is prefered. What do you want raul?
Here's a version with generics
Choose whichever you want raul.
KayleighWasTaken's one. I'm pretty sure jcsahnwaldt will understand.
Sure, no problem. I just wanted to try whether
estSubsets(lst: List[Int]|List[Char])would work at all, and creating a fork seemed to be the easiest way to do that. I didn't expect or even really intend that my translation would get approved.List[Int]|List[Char]is the most specific parameter type (and in a way the 'most correct' one), butList[A]is much easier to read. And for the semantics of the kata it doesn't really matter what's in the list. Scala isn't Haskell. :-)Lua translation!
Approved +1
Thank you!
Gracias Francisco por considerar este desafío y traducirlo a Lua. Estaba buscando tu solución en Python para darte otro punto. A la orden. va Vamo' arriba la celeste! :)
What is this? Is this a thing with data types in Lua?
Or sometimes -1 is expected
This comment has been hidden.
This comment has been hidden.
I guess we can do like in javascript and reduce the range to 50, so that this is no longer an issue.
Good! So Lua has the a similar problem as JavaScript has with integer overflow. We'll be waiting your fork.
@raulbc777: Here's the Lua fork
Great job! +1. Let´s see now.
Thanks @dfhwze for your observations. +2
I'd change test size to 63 max if overflow is a concern, thats what I did for Scala.
great job and fantastic insights in the world of Lua!
This comment has been hidden.
I would say that its quite important when a solution does one arithmetic operation instead spinning in a loop thousands or millions of times :) Your solution timing out is not a kata issue, really.
Even with counting permutations, it can be solved in <1 second: https://www.codewars.com/kata/reviews/5848c0ffa71baafa600015d4/groups/62e9514bf5c607000154fda2
This comment has been hidden.
This comment has been hidden.
( Haskell-specific )
This solution, which changes the constraint from
OrdtoEnum, should not pass.There should be a test with list elements that are
Ordbut notEnuminstances.Hm... I'd say it's OK to change the function type in this case. The description says the input elements will be either integers or characters, and both happen to be
Enumas well asOrdin Haskell.I don't think there's an integer or character type in Haskell that is
Ordbut notEnum, so I think it won't be possible to write such a test while making sure the Haskell version still does what's promised in the description.We had a similar discussion about the parameter type of the Scala version in this thread. The Scala solutions have several variations of the parameter type, and they all pass, because the tests just call the function, and don't check the exact type.
So I'd say we can close this issue and accept a solution that changes the type to
Enum. It's a nice solution. Why not? :-)But I won't close it. I'd be interested to hear what others think.
OrdandEnumoverlap some, but are not ( at all ) the same thing. If the solution is intended to work for both integers and characters, the correct signature would be:: (Ord a,Enum a) => [a] -> solution- and even then, it would not properly express the full intent ( I don't know if Haskell actually can correctly express the intent in this case ), but at least it would express that you may assume bothOrdandEnumare satisfied. ( It would not express that the input type must be either(Integral a) => aorChar. )Testing with
Ordbut notEnummight require a custom datatype, which would of course violate "integer or character", so that would not be appropriate here. Expanding the initial signature seems like the better solution.( I was going off the initial signature only; hadn't read the description closely enough. )
I think that desperate attempts to reflect the requirement of "ints or chars" in the solution interface are a misguided attempt to carry a concept from untyped languages (the initial language) to strongly typed languages. The task does not care about "chars or ints" at all, it jsut uses these two types for convenience in the initial language, and other untyped languages. In strongly typed languages, rigidly sticking to this idea is just pointless. The solution should be either limited to one, well defined type (ints, or chars), or, if in scope of the rank, generic with types bounded on a level sufficient for determinig of uniquess (which in Haskell would be, i don't know,
Eq?).Shenanigans of
List[Char] | List[Int]orEither(List Char, List Int)or similar are, in my opinion, totally not justified for this task.Please take the "estimation" part out of the title. Calculating an exact amount is not estimating.
You could make the adjustments for Cobol. Congrats. Approved
This comment has been hidden.
Thanks. You're doing a great job.
Stringstag should be removedInitial solution in JS, Python and Ruby should just be
return 0Description should be language-agnostic
Tests in Crystal and Haskell should also be specified clearly and if possible, unified to the same number (array length)
I suggest to clarify that only nonempty subsets should be counted: "the amount of subsets" -> "the amount of nonempty subsets".
In JAvaScript tests have nested
itblocks, what leads to incorrect, red/green output of successful test runs.Thanks. I'll be checking it. In Python seems to be ok. Perhaps we may translated it to other languages if this issue is solved.
In python it seems similar to JavaScript: there are nested
its, what leads to red arrows in successful tests.ok
Fixed in Python. No more misleading red arrows.
Python new test framework should be used (Refer this & this for more detail)
Ruby 3.0 should be enabled (Refer this & this for more detail)
For any set, the empty set is a subset ...
Nice Kata
Unable to submit this kata. Server error or memory error.
Codewars doesn't support BigInts in Crystal, so it's not even possible to return answers for those tests as numbers. The tests are expecting wrong answers, like
-1for[-21, -37, -2, -38, -16, 23, 41, 18, 12, 45, 2, 21, -5, 14, -28, 6, -19, -31, 0, 46, 49, -15, -39, -29, -4, 25, -26, 11, -30, -42, -6, 48, -10, -46, 27, -23, 19].Thanks for pointing this out. I'll message to the author of the Crystal version.
Done a fix, let me know if you still got problems!
Haskell translation kumited. Please review and approve. Thanks, suic
Thanks for translating to Haskell :)
estSubsets :: Ord a => [a] -> IntWouldn't this overflow
Int?Hi, very good point! :) I've changed
InttoIntegerwhich should prevent overflow issues. Regards, suicP. S.: Thanks a lot for beta-testing my translations and for your useful comments. :)
Thanks suic for the translation and thanks kazk for the correction of the integer overflow.
Confirmed the fix. I had to edit that comment multiple times because the code block doesn't seem to have overflow :) to scroll and changed the width of this page :|
No problem, thanks again for the translation :)
@kazk, perhaps you can help to approve this one that you solved it: https://www.codewars.com/kata/identifying-top-users-and-their-corresponding-purchases-on-a-website/solutions/python
Please see this issue.
This was a kata I struggled with and it is actually easy. Work through a somewhat complicated version of it, finally get it to work, and proceed to look at the super simple way other people solved it. #facepalm
Crystal translation submitted: it took me a while longer, but I kept all your original test cases :)
It's approved. Thanks a lot Giacomo.
Thank you for yet another brilliant kata who taught me something new :)
Hi Giacomo. Unnamed marked an issue for the Crystal version.
An empty set counts as a subset of any set. You should put into the description that empty subsets are not counted.
From my POV it's clear in the given examples but as you suggested I'll add that in the description.
It's not clear that the empty set should be there, and that's the point. It might confuse people later on. Thanks for adding something about it.
This comment has been hidden.
This comment has been hidden.
Thanks for approving the kata. :)