6 kyu
Find the total white and black areas in a strange chessboard
321 of 664benjaminzwhite
Loading description...
Fundamentals
Algorithms
Puzzles
Mathematics
.avif)
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.
Nice kata.
Difficult one, got a bit mad at my first try cause I didn't completely read the description, and was then dumbfounded when I saw the part about solutions with loops inevitably being to inefficient, resulting in timeouts. But then taking a look at the puzzle with a fresh mind I finally got it :)
Props to the author
Hi @miggo1999 - thanks for the kind words, and congrats to you for sticking with it!
This comment has been hidden.
Even though you say there is "no loop", you need to understand that your sum() isn't magic - it is doing essentially the exact same thing as a loop; it is performing all of those (many) area calculations inside the () and then summing them.
If I tell you, for example, "add all the areas in the board" and "for each area in the board, add it to the total" - are these 2 fundamentally different algorithms? No! The 2nd command obviously has a "for loop" in its syntax, but the 1st command has the exact same calculations also!
If you're struggling still, forget about coding/loops/etc and go back to basics - try to solve this away from your computer, as if it were a puzzle on paper.
first of all .. i am relly happy that i am getting repl,ies
pen and paper really helped me thnx
with no loop also this kata is timed out :(
took so much time, but very great kata. tbh I think it should be like kata 5, maybe less.
This comment has been hidden.
Print out the 5x5 example on a piece of paper, and then cut it a few times with scissors, then try to re-arrange it in a simpler configuration.
This comment has been hidden.
That particular test is a
Fixed_Test, so it will run every single time you clickATTEMPT. Examine your results for this test per each run for a clue as to what's going on in your code.This comment has been hidden.
Neither compiler has the duty of giving right or wrong values, that's up to the code. Yours gives erroneous values to the compiler.
Submittedis what your code returned.Expectedis the correct answer for the current input....so run the code several times and look at the error message for "That particular
Fixed_Test" (the one that should return{61, 49}).Marking question as resolved as kata has since been solved 30+ times in C with no further issues, so everything seems to be OK with random tests in C.
This comment has been hidden.
This comment has been hidden.
with no loop also kata is timed out :(
can we use numpy?
Why couldn't you?
Sure, you can even use a quantum supercomputer if you want; the point of this kata is that clever > brute force!
There is a clever solution, that I can use with only pen and paper, which will be faster than someone using a brute force solution using NumPy etc.
LC translation
This translation changes the description ( LC needs some extra information ).
Thanks! Approved, and noted for the change in description.
Hi There!, I found a solution for this Kata using "product" from itertools package but it is also time out, please help!
ìtertools.productdoes fundamentally the same as a nested loop. This won't work.Hi Akar-0, thank you for your advise. I have just little expirience in coding and so far I only found the solutions by using nested loops, but allof them are time out, could you share a hint?
Try reading other comments.
Hi @ChichoZeDo - if you'd like a little hint: forget about coding/modules/packages/loops/etc. for now, and just think about how you could solve this problem in the real world - maybe if the board were printed on a piece of paper for example.
Hi @bejaminzwhite. Thank you verymuch for yout hint!, it works, I could find the right solution. I have so little coding experience, so I was much focused on loops, packages,functions etc, but having the diagram on a piece of paper came many other ideas. I now know that many solutions of coding problems are actually not hidden behind a complex code, just as you say, it is like solving problems in real world. Great hint, Thanks
Hi @ChichoZeDo - thanks for your message! You did the hard work, and you learned in one single day some of the most important things about coding puzzles: 1) never give up and 2) think first, code second.
Congratulations, and good luck with Codewars and on your coding journey.
How to optimize nested loops for
I have the right solution, but its time out
You cannot (really) optimize nested loop. You need to find a solution with a single loop or it won't pass.
Hi @semki - the tests are designed to time out nested loops.
You've made good progress - you've found a correct way to add up the areas. Now ask yourself, how can you improve it? Do you really need to perform ALL the calculations in your nested loops? Hopefully this will help you find an even better solution.
maybe dont use loops at all - i tried to do it with one loop and it timed out
There is a way to nest 2 loops to get it ro pass. There is a clue in the 40000 N test case set description.
Haskell translation
Approved, and thank you for translating!
JavaScript translation
Approved, and thanks for your translation!
COBOL translation.
Approved, thanks on behalf of the COBOL fans out there!
Hi there. Im really confused about this test [3, 1, 2, 7, 1, 11, 12, 3, 8, 1], [1, 8, 4, 5, 2, 21, 5, 2, 2, 17] where answer = (1583,1700). I dont really get it. Shouldnt we multiply and add the even indeces for white and odd indeces for black? Cause after adding up the i get (89, 297), separately. Please help, author or anyone else.
Hi @amirymax , thanks for attempting this kata.
The numbers in the 2 lists are referring to the widths of the N individual columns and the heights of the N individual rows.
If you focus on a specific column (say it has WIDTH = 5) and a specific row (say it has HEIGHT = 8) then the "intersection" of that column and that row will define a region on the board that has an AREA 5 * 8 = 40.
It's much clearer if you refer to the N = 5 example on the kata, with the nice picture:
Use the picture to see if you can match my calculations of the areas. For example, moving from left to right on the top row of the example, there are 5 different regions: 1st one is is WHITE and has area = 1x3, 2nd one is BLACK and has area 1x1, 3rd one is WHITE and has area 1x2, 4th one is BLACK and has area 1x7, 5th one is WHITE and has area 1x1.
Repeat this for the entire N = 5 board, on a piece of paper (it's quick), and see if you can find the values: total white area = 146, total black area = 134.
i got it, thanks a lot. Now im tryna solve problem with time out :)
I have two for loops in my solution, and despite passing all the cases it says that I timed out
Hi @conconTheCoder - Yes this is the expected behavior for the tests; your solution with 2 for loops will pass the BASIC test cases since the maximum size in the basic tests is N = 10.
In the FULL tests, i.e. when you click "Attempt" in the kata, your algorithm will be tested on values of N = 41,000. This is designed to time out brute force solutions with 2 for loops. The timeout limit is = 12 seconds on Codewars Python katas.
You can generate a random 41000 x 41000 board on your computer/IDE and see how long your current solution takes with an input of this size! (don't actually do this, it will take hours and/or crash your computer - test your algorithm on boards of size N=100, 200, 300... and notice how much time it is taking to find the solution)
does this problem require the use of algorithms then? i am not thay experienced of a coder
This comment has been hidden.
ok, i will try to do it using one for loop, i see what you mean
This comment has been hidden.
Never mind well done. It wasn't even a algorithm though
Glad you solved it! I was just replying to say that your solution looked fine to me then I saw your updated message.
Any "way of doing things" is an algorithm - as you just saw with this exercise, just because it's simple doesn't mean it's not powerful (your second "algorithm" finds the same result as your first attempt, but much much faster!).
The performance requirements are not mentioned anywhere.
Literally stated in the description
Edit: I guess the upper bound isn't stated by the author?
Hi @FArekkusu ; I have now updated the Inputs paragraph in description to explicity include the performance requirements, by telling people that O(N^2) solutions to kata will timeout, and showing the largest possible N value used in random tests.
Thanks,
@benjaminzwhite I think it is better to put the input constrain like this
N ranges in 1 < N < 40000(inclusive <= or exclusive <)@Insisted - done; my original idea with separating the min and max N was to emphasize that N=1 is an important test case, but this is now included in the preloaded Example Test Cases so user will be tested against this N=1 case early on.
Thanks!
Thank you. Enjoyed :)
Thanks for the feedback!
Execution Timed Out
Yes, this is normal - if you attempt to brute force this kata, your algorithm will be O(n^2) and you will time out on the large random tests where n > 40,000.
You are looking for a clever solution for a 6 kyu problem ;)
even with one loop i am getting timeout
Using
sumis like using a nested loop. Each time you callsumit needs to parse the whole array.are we aming for O(n) or O(n2) here?
Hi @shaun112345 , the kata just got approved today so maybe you "slipped through" as the final tests were being confirmed!
In the final version, O(n^2) will fail as there are 10 tests with n = 40_000.
I've re-run your O(n^2) solution and it does in fact fail (timeout) now that the tests are finalized.
To answer your question, therefore, we are aiming for an O(n) solution! Congrats on the free points if you don't want to re-try, but if you want to find the answer then have fun finding the O(n) solution.
Thanks for the info!! I'll have another go!
C Translation kumited.
hi @rowcased ! First of all, thanks for translating my kata.
It's my first kata, so I don't know if I'm replying to this correctly: I got a notification that you have published the translation, so I then selected green button Approve.
Is that all I need to do? Let me know if I need to do anything else.
One thing of which to be aware of in approving any translation is that it becomes your material to manage, although the translator should be on hand to make immediate adjustments / corrections, but there's no guarantees. So, if you don't know the language or doubt the abilities of the translator, proceed with caution. Anyway, you're welcome! Cheers
Ah OK I understand.
Well, I certainly don't doubt the ability of the translator in this case but I don't know any C yet - learning Python is going well so far, so I will attempt C as my first real grown-up language to learn afterwards ;)
Thanks for the helpful reply, cheers.
Tests allow
O(n^2)solutions to pass again.you'd have put the link in the original issue, I'd have seen that was what you were actually talking about there...
.
Sample tests should also follow the testing framework usage.
Hi @Voile again, thanks for this - as mentioned, these are my first attempts at submitting katas; I'm having a hard time understand what you mean by the testing framework usage - I've read all the following on the documentation pages: -Creating a Kata -Authoring Python Content -Writing Submission Tests -Python Codewars Test Framework and also on GitHub the "Random Test Cases for complete Beginners".
Could you point me to maybe a full work-through example of what's expected please, as I must be missing something? If there's a good approved kata for example that I can unlock the solution to and read through its test layout for example.
Thanks so much for any feedback or suggestions, I will use them to improve my submissions.
done
Hi @Blind4Basics - I just logged in and noticed all the work you had done on solving the outstanding issues before approving the kata, and wanted to thank you a lot.
Most importantly, your re-design of the tests mean that I now finally understand what the mods/feedback are talking about with the testing framework usage!
I've saved your test layout locally, so I can refer to it from now on - it's been really useful this evening for understanding good testing practice in general.
So thanks again for all your contributions and advice, it's really been helpful to me as a newbie!
There is no point in testing the type and length of returned value as
test.assert_equalsalready does that automatically, and also format and print the returned value.Hi @Voile , thanks so much for taking the time to comment on my kata.
The reason I did this is because on my 1st attempt at making a kata (this is only my 2nd!), one of the reviews said that solvers could get error messages if they deliberately attempted to return wrong type in the solution, so I thought that meant I had to manually test type/length etc.
done
This is an interesting kata, but the description is longer than is likely necessary, while still leaving people confused. This is a case where an image can really clear things up. I'd recomend adding the following or something similar, to clarify:
holy shit... Varying SIZES!!! XD
That's what I missed...
hi @scarecrw - thanks so much for the feedback, and also for providing the illustration.
As a new user to Codewars, now that I know I can add pictures in kata descriptions I will definitely use them more in future.
I will rework the description following your suggestion to be more concise.
I will try to make it clear also that the topleft square will always be white, since I anticipate that solvers might miss this otherwise, especially if they aren't chess players.
added
hi,
I definitely want to see the full chessboard of the example, because so far:
?
'got my answer above... The image is a must have... x)
hi @Blind4Basics , thanks as always for the feedback - sorry for slow reply, I was away yesterday; I see that scarecrw above did a much better picture than my attempt in MSPaint, I'm glad it clears things up.
Does Codewars have a preferred hosting site for images that I can use to insert in my kata description? If so I'll add one with clarifications.
Hi,
unfortunately, there is no "best way" to host the image. Just pick one you like...
Cheers
Hi @Blind4Basics - OK, will do. By the way I just found out about the Codewars discord, so I'll ask for advice there in future instead of on kata discussion; thanks for your patience with newbies!
The user can modify the input.
done
Input generation is terribly slow.
done
The performance requirements are too lenient.
This comment has been hidden.
This comment has been hidden.
tests were FAR TOO BIG. The goal is to differentiate O(N²) from (ON), not to make the user wait for 9s when the solution is the expected one.
Corrected
The output type should be a tuple.
Thanks @FArekkusu - Noted; I've changed output type to be a tuple.