Timeline for Find highest scoring matrix without property X
Current License: CC BY-SA 3.0
34 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:39 | history | edited | CommunityBot |
replaced http://codegolf.stackexchange.com/ with https://codegolf.stackexchange.com/
|
|
| Nov 15, 2014 at 8:01 | vote | accept | CommunityBot | moved from User.Id=9206 by developer User.Id=3572 | |
| Nov 14, 2014 at 17:18 | history | bounty ended | CommunityBot | ||
| Nov 14, 2014 at 9:43 | history | edited | Peter Taylor | CC BY-SA 3.0 |
added 314 characters in body
|
| Nov 12, 2014 at 13:52 | history | edited | Peter Taylor | CC BY-SA 3.0 |
34/18
|
| Nov 11, 2014 at 17:30 | comment | added | Suboptimus Prime | @PeterTaylor Cool, thanks. Calculating the sum of columns on each iteration was the second biggest bottleneck for my program. That still leaves the biggest bottleneck which is the hashset performance, even though my hashset is almost twice as fast as the default one. | |
| Nov 11, 2014 at 17:12 | comment | added | Peter Taylor | @SuboptimusPrime, go for it. We're already both stealing from each other, no reason to stop now ;) | |
| Nov 11, 2014 at 16:47 | comment | added | Suboptimus Prime | @PeterTaylor Can I borrow your revolving door implementation? It's seems better than the algorithm I'm currently using. | |
| Nov 11, 2014 at 16:39 | history | edited | Peter Taylor | CC BY-SA 3.0 |
Ahem
|
| Nov 11, 2014 at 16:36 | comment | added | Peter Taylor | @SuboptimusPrime, I found it at people.math.sfu.ca/~kya17/teaching/math343/16-343.pdf and fixed a bug. Interestingly the algorithm I'm now using to iterate through Lyndon words is one of a class of related algorithms which also does k-of-n subsets, so I might be able to refactor and share some code. | |
| Nov 11, 2014 at 16:29 | history | edited | Peter Taylor | CC BY-SA 3.0 |
added 1598 characters in body
|
| Nov 11, 2014 at 16:26 | comment | added | Suboptimus Prime | @PeterTaylor I've been trying to understand your revolvingDoorDifference function and I can say that that's some high level sorcery :) Is that your own implementation or did you find it somewhere? | |
| Nov 10, 2014 at 8:28 | history | edited | Peter Taylor | CC BY-SA 3.0 |
added 785 characters in body
|
| Nov 10, 2014 at 1:26 | comment | added | justhalf |
Wah, 28/15, a good result! I'm curious to see the detailed results for each n. Is there a pattern that can be observed in what kind of Lyndon words satisfy the requirement? If we can find any, then we might be able to find a constructive proof.
|
|
| Nov 9, 2014 at 17:59 | comment | added | COTO | Ah, OK. I read something different out of your sentence structure, but I get it now. | |
| Nov 9, 2014 at 17:54 | comment | added | Peter Taylor | @COTO, "otherwise we can rotate". I'm partitioning the matrices into equivalence classes and only testing one representative from each equivalence class. | |
| Nov 9, 2014 at 17:51 | comment | added | COTO | "[W]e can consider only circulant matrices in which the first row is a Lyndon word". Ergo if the first row is not a Lyndon word, we cannot consider the resulting circulant matrix. Ergo the resulting circulant matrix must have property X, otherwise we would have to consider it. What am I getting confused? | |
| Nov 9, 2014 at 17:37 | comment | added | Peter Taylor | @COTO, I haven't stated that, and it's not true. It would imply that every matrix has property X. | |
| Nov 9, 2014 at 17:36 | comment | added | COTO | OK, thanks. I meant to say "the absence of property X implies Lyndon wordity" since you've stated the contrapositive: that the absence of Lyndon wordity implies property X. | |
| Nov 9, 2014 at 17:16 | comment | added | Peter Taylor | @COTO, that's not the implication. There are three types of words: non-prime words, Lyndon words, and rotations of Lyndon words. The only one for which there's an implication is that non-prime implies that every column has an identical twin (or maybe even more identical siblings) and hence has property X. | |
| Nov 9, 2014 at 16:59 | comment | added | COTO | It isn't at all obvious to me why "we can consider only circulant matrices in which the first row is a Lyndon word". I certainly believe you, but would you indulge me in explaining why property X implies Lyndon wordity? I'd appreciate it. :) | |
| Nov 8, 2014 at 12:27 | history | edited | Peter Taylor | CC BY-SA 3.0 |
added 9913 characters in body
|
| Nov 6, 2014 at 8:17 | comment | added | Peter Taylor |
@justhalf, I reckon that I can check up to MAX_N=24 in 12 hours on a fast computer using one thread, but that seems to be about as far as I can go because of memory constraints.
|
|
| Nov 6, 2014 at 7:55 | comment | added | justhalf | I think we're practically limited to this score, since the property X checking is very time consuming, unless we found another equivalent condition which can be evaluated faster. That's why I was so eager to see that "non-prime" implies property X =D | |
| Nov 6, 2014 at 7:28 | history | edited | Peter Taylor | CC BY-SA 3.0 |
added 287 characters in body
|
| Nov 6, 2014 at 7:23 | comment | added | justhalf | I see, so the purpose of that sentence is only to claim that the only first rows that we need to brute force are all those Lyndon words. | |
| Nov 6, 2014 at 7:18 | comment | added | Peter Taylor | @justhalf, I don't think that's implied and I certainly don't intend to imply it. A prime word can have property X or not: the point is that rotating it doesn't change whether or not it has property X, so we can consider the Lyndon word in the rotational set as a representative element. | |
| Nov 6, 2014 at 0:18 | comment | added | justhalf | Can you explain more about the "non-prime iff no property X" that you seem to imply in your sentences? | |
| Nov 5, 2014 at 21:51 | history | edited | Peter Taylor | CC BY-SA 3.0 |
Bugfix, performance improvement by quick-reject
|
| Nov 5, 2014 at 21:50 | comment | added | Peter Taylor |
@KennyTM, note that the second parameter is the radix. There is a small bug: I should be using n rather than rows, although it's fail-safe in the sense that it would discard valid solutions rather than accept invalid ones. It also doesn't affect the results.
|
|
| Nov 5, 2014 at 20:15 | comment | added | kennytm | As you are using each digit of BigInteger as a matrix cell, won't there be wrong answer when n > 10? | |
| Nov 5, 2014 at 20:15 | comment | added | user9206 | This is a good improvement. It seems using Lyndon words means you only need to check roughly 2^n/n binary strings for the first row, instead of 2^n. | |
| Nov 5, 2014 at 17:35 | history | edited | Peter Taylor | CC BY-SA 3.0 |
added 319 characters in body
|
| Nov 5, 2014 at 17:22 | history | answered | Peter Taylor | CC BY-SA 3.0 |