3 kyu
Alphametics Solver
171 of 431docgunthrop
Loading description...
Puzzles
Performance
Cryptography
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.
This comment has been hidden.
How come?
I've managed to pass the timeout by executing several times afterwards. But the question remains - what eactly 16000 msec timeout includes?
Typically when you are printing some large lists or arrays / when you have an inefficient algorithm or infinite loop, the timeout will occur.
Thanks, I know this. The question was: Why the execution completion is printed out to be 8987ms and there is timeout despite the limit of 16000ms Anyway as I wrote, I've managed to pass the tests on next execution Thank you for your reply :)
because you time out on the next section of tests, which doesn't print anything before the timeout? (edit: looks like there are only 2 groups, so dunno)
I am trying to solve this in C#, but I get an error in the beginning with "using Math.NET;", which was preset here (this is the message: "src/Solution.cs(1,7): error CS0246: The type or namespace name 'Math' could not be found(are you missing a using directive or an assembly reference?)"). Any ideas with this? I am new to programming and C# especially, so I apologize if this is some trivial error.
Not an issue. Did you try searching online for a solution to your problem?
Did you include
using System?Yeah, I tried, but Math.NET still doesn't work even if I include using System https://www.nuget.org/packages/MathNet.Numerics/#readme-body-tab
I assume this has to do with my poor knowledge, so I'll keep learning and searching.
Thanks!
timed out with python code
I have no idea how to improve brute-force algorithm except some evident heuristics. However, they do not let avoid n! complexity
Can you explain precisely how this is a valid issue?
Your code not working is not a kata issue. An issue is a bug in the kata. Please refer to the documentation and don't raise issues so lightly in the future: https://docs.codewars.com/training/troubleshooting/
I think 25-30 test cases can be enough for python.
Python 3.8 should be enabled.
.
@Blind4Basics: thanks for handling this!
np. ;)
You'll have to do the last one on your own: it's one of the few I didn't enter the edit panel yet.
This comment has been hidden.
How do you color your description?
Do not use colors in description if not necessary :)
You can add color in descriptions by mixing in HTML elements. But keep in mind that doing so may make things kind of wonky, so I"d say use it sparingly if you plan to incorporate it.
is it css?
Use inline styling, like:
This comment has been hidden.
result of my code is: 7411 + 642 = 8053
No, it's not ok.
Din this exmple cannot represent 0.can you tell me answer for BILL + JIM = DUDES i find only this one 7411 + 642 = 08053
upd: 9422 + 743 = 10165
)))
My solution returns:
"Each unique letter may only be assigned to one unique digit" Just to clarify, a number can be assigned to multiple letters, right? For example, can A and B can both have the value 5?
No, IIRC the mapping between a letter and a digit is always 1:1.
Cheers.
Fixed
I tried python first, but time out. Then I switch to JS. Had spent a lot of time to improve the efficiency. I have finished couple of 2kyu and 3kyu katas. To me, this complexity worths a 2kyu.
This comment has been hidden.
Hi, I have passed this kata in GoLang. But the same algorithm doesn't even come close to passing in Python. So what this means is that Python coders are being unfairly treated. Users on the Gitter forum have suggested I mention this here.
Also, Python is running REALLY slowly on the CW runner just now. This seems to be a known problem. So I guess this needs to be taken into account now please.
@doc: I tried yesterday and python's runner problem is applying. My solution, which was one of the fastest times out almost 50% of the time, now (variations in perfs being still huge, ofc. Like going from 8s to... more than 12. When the kata was published, my solution generally went down to 3-5s, iirc).
@Davo36 This is actually an issue with the Codewars Python runner rather than the actual kata. There's nothing I can do from my end to make it execute faster; it's a sitewide issue. If an issue is to be posted here, then an issue would have to be posted for a large number of Python katas, so I'm going to mark it resolved here.
@B4B I also get similar results when running my solution; at the time when it was published, there were zero issues with timeouts.
With that said, I'm adding a note to the Description so that Python users are aware.
I suggest to add following extra-long test for more fun (found on internet). Columnwise algorithm would probably choke on it but a more generic approach can do it in fraction of second ;)
"THIS + A + FIRE + THEREFORE + FOR + ALL + HISTORIES + I + TELL + A + TALE + THAT + FALSIFIES + ITS + TITLE + TIS + A + LIE + THE + TALE + OF + THE + LAST + FIRE + HORSES + LATE + AFTER + THE + FIRST + FATHERS + FORESEE + THE + HORRORS + THE + LAST + FREE + TROLL + TERRIFIES + THE + HORSES + OF + FIRE + THE + TROLL + RESTS + AT + THE + HOLE + OF + LOSSES + IT + IS + THERE + THAT + SHE + STORES + ROLES + OF + LEATHERS + AFTER + SHE + SATISFIES + HER + HATE + OFF + THOSE + FEARS + A + TASTE + RISES + AS + SHE + HEARS + THE + LEAST + FAR + HORSE + THOSE + FAST + HORSES + THAT + FIRST + HEAR + THE + TROLL + FLEE + OFF + TO + THE + FOREST + THE + HORSES + THAT + ALERTS + RAISE + THE + STARES + OF + THE + OTHERS + AS + THE + TROLL + ASSAILS + AT + THE + TOTAL + SHIFT + HER + TEETH + TEAR + HOOF + OFF + TORSO + AS + THE + LAST + HORSE + FORFEITS + ITS + LIFE + THE + FIRST + FATHERS + HEAR + OF + THE + HORRORS + THEIR + FEARS + THAT + THE + FIRES + FOR + THEIR + FEASTS + ARREST + AS + THE + FIRST + FATHERS + RESETTLE + THE + LAST + OF + THE + FIRE + HORSES + THE + LAST + TROLL + HARASSES + THE + FOREST + HEART + FREE + AT + LAST + OF + THE + LAST + TROLL + ALL + OFFER + THEIR + FIRE + HEAT + TO + THE + ASSISTERS + FAR + OFF + THE + TROLL + FASTS + ITS + LIFE + SHORTER + AS + STARS + RISE + THE + HORSES + REST + SAFE + AFTER + ALL + SHARE + HOT + FISH + AS + THEIR + AFFILIATES + TAILOR + A + ROOFS + FOR + THEIR + SAFE == FORTRESSES"
Thanks for the suggestion, but there are 2 conditions under
Technical Detailsthat prohibit this:But I would encourage users to try out this test case at their leisure.
nice example but it looks like it has leading zeroes or dublicates (every letter starts a word), so my solution returns nothing
return nothing
@Twilight_Sun, it is actually a valid puzzle:
There are 10 distinct letters: AEFHILORST, nine distinct leading letters: AFHILORST, and solution without leading zeroes does exist. (It's easy to deduce here that E is 0 although no special-case for this deduction is needed to code it).
9874 + 1 + 5730 + 980305630 + 563 + 122 + 874963704 + 7 + 9022 + 1 + 9120 + 9819 + 512475704 + 794 + 97920 + 974 + 1 + 270 + 980 + 9120 + 65 + 980 + 2149 + 5730 + 863404 + 2190 + 15903 + 980 + 57349 + 5198034 + 5630400 + 980 + 8633634 + 980 + 2149 + 5300 + 93622 + 903375704 + 980 + 863404 + 65 + 5730 + 980 + 93622 + 30494 + 19 + 980 + 8620 + 65 + 264404 + 79 + 74 + 98030 + 9819 + 480 + 496304 + 36204 + 65 + 20198034 + 15903 + 480 + 419745704 + 803 + 8190 + 655 + 98640 + 50134 + 1 + 91490 + 37404 + 14 + 480 + 80134 + 980 + 20149 + 513 + 86340 + 98640 + 5149 + 863404 + 9819 + 57349 + 8013 + 980 + 93622 + 5200 + 655 + 96 + 980 + 563049 + 980 + 863404 + 9819 + 120394 + 31740 + 980 + 491304 + 65 + 980 + 698034 + 14 + 980 + 93622 + 1441724 + 19 + 980 + 96912 + 48759 + 803 + 90098 + 9013 + 8665 + 655 + 96346 + 14 + 980 + 2149 + 86340 + 56350794 + 794 + 2750 + 980 + 57349 + 5198034 + 8013 + 65 + 980 + 8633634 + 98073 + 50134 + 9819 + 980 + 57304 + 563 + 98073 + 501494 + 133049 + 14 + 980 + 57349 + 5198034 + 30409920 + 980 + 2149 + 65 + 980 + 5730 + 863404 + 980 + 2149 + 93622 + 81314404 + 980 + 563049 + 80139 + 5300 + 19 + 2149 + 65 + 980 + 2149 + 93622 + 122 + 65503 + 98073 + 5730 + 8019 + 96 + 980 + 144749034 + 513 + 655 + 980 + 93622 + 51494 + 794 + 2750 + 4863903 + 14 + 49134 + 3740 + 980 + 863404 + 3049 + 4150 + 15903 + 122 + 48130 + 869 + 5748 + 14 + 98073 + 1557271904 + 917263 + 1 + 36654 + 563 + 98073 + 4150 = 5639304404
My algorithm seems to be able to quickly find several solutions for this... they are just too long to be double-checked manually :-)
Just curious how far off I am.. passing the sample tests at 2.7s but timing out on the main test. Am I way off or close? :s (python)
Sounds like you may need to optimize some more; my solution passes the sample tests at < 1.1 seconds, but generally takes upwards of 5.5 seconds for the full test suite.
There was some update to the test runner for Python sometime back which may have directly led to a significant increase in completion time for several Python katas; my solution now takes close to 2x as long to complete than it did a year ago (though it's possible there are other factors like server load, etc.).
With that said,the reference solution still has room for micro-optimization, so as long as your fundamental algorithm is efficient enough it should be able to pass.
I did some extra things, but it seems hopeless. Down to 1.7s on the samples but too much time on the attempt. Does it also make sense that if I run 'KGKK + WMWDO + EMCKK + XEOGTEDE + KKMCWT + WKEKET + KEWCEW = XOMTDWMG','4544 + 92903 + 12644 + 81357101 + 442697 + 941417 + 419619 = 83270925' in the sample tests it takes over 8 seconds, but only takes ~2seconds on my machine...
Looks like your example is from a random test. I'm not able to explain the considerable difference in completion times between your machine and CW, but it wouldn't be due to the random tests; the random tests are designed such that some number of random integers for the equation is selected first, then a random letter to match each unique digit. This way there is no need to check against a reference solution, and the CPU resources used is negligible.
So I took a second look today, but it seems that modules (numphy) are not allowed. Is this intended?
Yes, importing numpy is prohibited.
@Doc: you should say it in the description, then!
My bad. Updated the Description for Python and JS.
This comment has been hidden.
After viewing your linked video, I tested my solution against the 2 example tests you had; after giving it a few runs in CW, I got a pretty consistent 3.5 second completion time. When I run the same two tests locally, it takes 2.25 seconds and my laptop runs on a 5th gen Intel Core M @ 800Mhz (dual core). Not that powerful, but that's the trade-off for going fanless ¯\_(ツ)_/¯
So in this case, I'd say your algorithm still needs to be optimized.
sir, you rock. :D thanks
Could you include the constraint that leading zeroes are not allowed to the description?
Updated ✔️
C# translation published.
Go translation published.
This comment has been hidden.
@doc: "collateral" question: do you want I increase the number of tests in java? x)
This comment has been hidden.
I don't think that increasing a number of test cases/loop runs will be good strategy. Maybe it would be better to pick a reference solution, randomize an input set, and run both solutions against the same set of cases and compare their performance. Difference larger than 150% (or whatever you choose) would reject the solution.
OTOH I wonder how helpful the calculation of the last remaining digit is. I did not bother to check yet, but I'd guess that since problem domain is quite small (10 digits), you won't win an order of magnitudes increase of performance. But factor of 2, probably yes.
I guess that in this case I will hold on with C# translation until we get to some agreement. And I do not mind having my current solution invalidated, with this additional performance check kata will suit better its 3 kyu rank :)
@hobovsky, if you wish to write a C# translation and it passes the same rigid tests as in the java translation, I encourage it. 🖖
Ruby translation!
conform to the python version, for the random tests. Perf are varying from 3 to 9s, average around 6.
Approved 👍
Java translation!
I used the fastest version I could come up with, so I'm not sure that the perf constraint isn't a bit "too much". Hard to tell... For now: around 5-6s to complete (2.5s of those are compile time), while the timeout is at 16s in java. But since I do a lot of tests (17 loops against only 3 in python), the timings seems pretty consistent (1s of variation, 2 at most).
Now the really hard part...: I'll try to do a ruby version... x)
Nicely done with a very performant solution!
Hi doc,
I found some ideas of edge cases that you could add. Some of them are "out of the constraints" for now, because they have 10x10 letters are even more, but none of them will cause any performances issue, they are very simple to solve. I designed them to have one unique solution that checks if the implementation behaves correctly in some special cases:
Pis a zero. ;) (note: this one need an update of your regex because it's considered invalid)Cheers!
@B4B, thanks for providing these additional test cases. I went ahead and added the first three to the tests, but modified the first test case to keep it within the constraints (8 characters instead of 10).
The last one wasn't added because the first summand falls below the minimum length of
2.There are now
15fixed tests and21random tests.As always, your contributions are much appreciated 👍
:+1:
(note: why this minimal length, btw? :o It's not problematic to get one stp lower tho? But as you want!)
cheers
I can't say I have a strong reason against lowering the limit to
1character in length, but I think the kata is fine as is; I guess you could say I don't feel compelled to rewrite the solution and random test generator for that reason alone. I suppose someone else could also suggest including invalid tests that have no solution, but again I think the kata is fine in its current state.actually, about your solution, there is almost nothing to do: one single if statement to put in
nonzero, and for the verification part, I already made the modification there. Though, ofc, if you wanna push that in the random generator, that might be a bit more of work. But as I said, your choice!Can there be leading zeroes?
No leading zeroes.
Hi,
Just to be sure (might be useful to add those ino in the description?):
That's confirmed, now. Could be of use in the description.
Though, I have another question: are you using different threads in the tests??? :o Because I curently use a global variable to be sure that all the tests won't pass, and the one I make fail doesn't show up as the last one (though it should be).
Ok, updated description.
JavaScript translation coming soon...
JavaScript translation published.
Thanks, it was an interesting challenge. Maybe you could increase the number of random tests to really push the optimization part (i.e. solving the most obvious letters first)
I had considered further optimizations on my solution, but at the same time I don't want to make the constraints too difficult to pass. Glad to hear you enjoyed working on this kata.