Timeline for Find max number you can create from an array of numbers
Current License: CC BY-SA 4.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 4, 2019 at 18:57 | comment | added | Eric Duminil |
Sigh... The whole code in Ruby would be numbers.sort{|a,b| [b, a].join <=> [a, b].join } because sorting by comparator hasn't been removed. Python is a great language with many good design decisions but this one doesn't feel right.
|
|
| Jul 4, 2019 at 15:38 | comment | added | Baldrickk |
@BobRoberts ah, damn. thanks. I'd actually tried [50, 505, 5050] as a test and it passed that... needed to go a bit further...
|
|
| Jul 4, 2019 at 15:20 | comment | added | Bob Roberts | @Baldrickk That method fails on [50501,50] (5050150 instead of 5050501). | |
| Jul 4, 2019 at 15:04 | comment | added | Baldrickk |
I've come up with (what I think is) a working key. (it passes @AlexV 's asserts) It's actually in line with an earlier attempt, but with a minor tweak. We were looking at sorting with strings, but sorting with lists as a key is subtly different. k=list(str(num))``return k + k[0:1] re-uses the adding the first character method, but in a way that sorts correctly. (though I came to it via an alternative approach this time). I haven't been able to find a way to break it so far. Now I guess we need to profile this vs the cmp approach. to see which is superior?
|
|
| Jul 4, 2019 at 13:02 | comment | added | Eric Duminil |
@BobRoberts: sorted(numbers, key= lambda i:itertools.cycle(str(i)), reverse=True) would be nice. Sadly, cycles aren't comparable.
|
|
| Jul 4, 2019 at 12:08 | comment | added | Eric Duminil |
@AlexV: Having to use cmp_to_key isn't very elegant. It would be interesting to know if there's a good key function. In the meantime, sorted(numbers, key=lambda i: str(i) * 1000, reverse=True) should work fine for many examples, but isn't very elegant either.
|
|
| Jul 4, 2019 at 11:32 | comment | added | AlexV |
@BobRoberts: I'm aware how cmp_to_key works. Me question was mainly out of curiosity.
|
|
| Jul 4, 2019 at 11:27 | comment | added | Bob Roberts |
@AlexV cmp_to_key just creates an object whose magic methods (__lt__, __gt__, etc.) call the supplied function. As for why do it instead of using a comparator function, to quote the Python docs on sorting, This technique is fast because the key function is called exactly once for each input record. That and a user expressed interest in this method in the comments.
|
|
| Jul 4, 2019 at 11:11 | comment | added | AlexV |
What's wrong with the comparator based solution in my answer? If you really want to go for key, maybe check the implementation of cmp_to_key to see if there are possible shortcuts.
|
|
| Jul 4, 2019 at 11:06 | comment | added | Bob Roberts | @Baldrickk Multiplying the string only creates a closer approximation of a number's real value as part of the resulting number. Without a ceiling on how large the numbers can be you would have to be infinitely precise. The only way I could see this happening would be by analyzing the list beforehand to find the largest number, then based on that we could know how much precision is required and therefore how many times to multiply the string. But that would defeat the point of a simple sort by key method in the first place, wouldn't it. | |
| Jul 4, 2019 at 10:49 | comment | added | Baldrickk | hmmm I think we just need to find the correct key fn. we have two competing issues - value of digits in increasing order (higher is better) and number of digits in decreasing order (less is more valuable) We just need to find a way of bringing those two together | |
| Jul 4, 2019 at 10:33 | history | edited | Bob Roberts | CC BY-SA 4.0 |
fixed for case [50,501]
|
| Jul 4, 2019 at 10:29 | comment | added | Bob Roberts | @Baldrickk Actually, after thinking about it some more, I realized that you were right, my method would dictate that [50,505] is arbitrary when it clearly isn't. But I'm afraid str(num)*2 is still not enough, because now [50,505040] is still sorted wrong. You continue this indefinitely, basically I think that sort by key just doesn't work for this problem. | |
| Jul 4, 2019 at 10:18 | comment | added | Baldrickk |
ah, so my 2*str(num) was overzealous - of course the most significant digit is the most important, and the digits beyond(/below?) that should be covered by the original ordering.
|
|
| Jul 4, 2019 at 10:12 | comment | added | Bob Roberts | @Baldrickk Thanks for pointing that out. You can account for that by using the first digit, rather than the last. I've edited the answer occordingly. | |
| Jul 4, 2019 at 10:10 | history | edited | Bob Roberts | CC BY-SA 4.0 |
fixed for case [50,501]
|
| Jul 4, 2019 at 10:08 | comment | added | Baldrickk |
2*str(num) appears to be a better sorting key - I haven't checked to see it it is optimal
|
|
| Jul 4, 2019 at 10:02 | comment | added | Baldrickk |
maximum_number([50,501])?
|
|
| Jul 4, 2019 at 9:49 | review | First posts | |||
| Jul 4, 2019 at 10:54 | |||||
| Jul 4, 2019 at 9:46 | history | answered | Bob Roberts | CC BY-SA 4.0 |