« first day (1763 days earlier)   

5:06 PM
oh, we can finally start abusing stars again!
Hey, is it necessary to credit people whose comments helped our solutions?
Cause two people helped on the Golfscript answer to Counting factors, and I only remember one was Peter Taylor
I think the other guy was Martin, but I don't remember now and they deleted their comment after I made the edit
Not necessary, but it's good etiquette. Which answer is this?
I'll take a look at the comments.
A: Count the divisors of a number

Sherlock9Golfscript, 19 18 17 13 bytes ~.,\{\)%!}+,, How it works ~ Evaluate the input, n ., Duplicate the input, create array [0..n-1] \ Swap array and n { }+ Add n to block == {n block} \ Swap n with i in array ) Increme...

Yes, Martin Büttner was the first to comment.
5:11 PM
Right then, I'll edit it in
@Dennis how does deleted comment appear for you in the ui ? just like deleted answers?
bruteforce for 3x6 = 10
3x7 = 12
@Optimizer Thankfully no. They're collapsed by default.
Thanks @Dennis
Gosh darn it, did the GOD dev team mess up the collision detection again?
5:15 PM
Yet another Bad Challenge idea: "When is new year?"
@Sherlock9 yup, there seems to be a bug in the road mesh.
I still like "When is Easter?"
Or Mayan Calendar stuff could work too
3x8 = 14
Or to be a general nuisance: "Predict any future lunar eclipse"
3x9 = 15
To recap,
Hi @TheNumberOne
5:19 PM
@orlp what were 3x4 and 3x5 again?
starting from N=3, 3xN is 6,7,9,10,12,14,15
Does anyone want to review my sandbox post?
N=10 is >= 17
@Mego Sorry :)
5:20 PM
in other words
3xN = floor((n+1)*pi/2)
Check up to N=20, and I can say "I THINK NOT!"
@TheNumberOne ?
Moar tags, plz.
@VoteToClose I'm going to provide a wrapper class with alternate instructions for writing a bot in other languages.
N=10 is 17 confirmed
5:24 PM
@randomra Do you have a proof for that?
Hello @undergroundmonorail
@orlp are you doing an exhaustive search or are you reusing previous results?
@MartinBüttner exhaustive
N=11 is >= 19
So the pi*(N+1) // 2 approximation breaks
5:36 PM
@orlp well, it has to be
I mean it has to be <= 19
so you can stop the search right there
@MartinBüttner why
because you can't add more than 2 when going from N-1 to N
So you are simply checking every combination of 1's and 0's in a 3xN array for 3 adjacent 1's and getting the maximum 1's?
well, assuming N-1 was optimal
5:37 PM
That's true
It may be optimal for N-1, but not continuing
@orlp right, but you did check N-1 exhaustively
you can't add more than 2, period
because adding 3 would be illegal :)
5:38 PM
Oh ok
no again
it is assuming that N-1 was optimal
because you could theoretically modify more than the last row :)
So 19 &lt; F(12) &lt; 21
Well, there is the idea that there could be more than one 3x10 arrays that are optimal for N=10, but they don't all lead to the optimal arrays for 3x11
F(12) is probably going to be 20
@orlp you could, but you still can't fit more than the maximum you've determined into the first N-1 rows
Could you print the optimal arrays for 3x9 and 3x10 here for comparison?
5:41 PM
@MartinBüttner I might misunderstood what you want, but the proof is simply that no other columns than the last two can make a 3-in-a-row when you add the next column to the grid, so you should use the grid with the most 1's from the ones which have the same last two column
I don't print all optimal arrays
@Sherlock9 I don't expect them to be unique.
((0, 0, 1, 0, 1, 0, 1, 0, 0), (1, 0, 1, 1, 0, 1, 1, 0, 1), (1, 1, 0, 1, 0, 1, 0, 1, 1))
for N = 9
((0, 0, 1, 0, 1, 0, 1, 0, 1, 0), (1, 0, 1, 1, 0, 1, 1, 0, 1, 1), (1, 1, 0, 1, 0, 1, 0, 1, 0, 1))
for N = 10
@randomra The grid with the most 1s from the previous solution might not permit adding any 1s, wheras a suboptimal grid with one or two 1s less might permit adding one or two 1s.
((0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0), (1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1), (1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1))
for N = 11
sometimes copy paste from terminal is finnicky
N=11 has a really simple pattern
5:43 PM
It appears, that the pattern is simple for N=9,10,11
@MartinBüttner that's why you keep the one from each of the distinct endings
@randomra right, but you need to keep the endings for suboptimal solutions as well
@MartinBüttner yes, but at most 2^6 of them
@randomra I'm not saying it's not possible... just saying you can't rely on the optimal solutions alone.
they are maximal between the ones with given ending
5:46 PM
@orlp yeah that pattern can be continued indefinitely and gives a ratio of 5/9
That upper bound is too high @randomra. Give me a minute
maybe my use of "optimal" was confusing, I meant as optimal between the ones with fixed last 2 columns
Q: HQ9+ implementation

HelloQuineWorldWrite the shortest possible implementation of HQ9+ in a language of your choosing. Bonus points if you can do it in HQ9+ itself.

Q: Check my program!

OldBunny2800Challenge Make an error-checker in the least amount of possible bytes! If you received an HTML program as a string through standard input, your program will be able to find all the errors and return to standard output. If the program is over 2000 characters, return that as an error too. Scoring...

Unfortunately it seems like the pattern can't be extended densely in the vertical direction
so yeah
5:49 PM
still worth an answer though
tiles horizontally for 3xN to get 5*N/3
N=12 becomes 20
never mind... I was thinking N was the number of 3x3 blocks, not the columns.
@MartinBüttner there is a question?
Q: Maximal tiling without any 3-in-a-rows

MrTiYou are given an arbitrarily large grid, where each square can either be off or on (think Game-of-life type board). You need to tile such a grid to maximize the number of "on" squares without there being any 3-in-a-row of "on" squares. A 3-in-a-row can be horizontal, vertical, or diagonal. 3-i...

5/9 is worse than 7/12 already posted
oh that does not tile
5:53 PM
Yeah the only "answer" so far doesn't extend to an unbounded grid
@orlp does yours extend in 2D?
@orlp it's "better" in that it lowers the upper bound ;)
A: Maximal tiling without any 3-in-a-rows

orlpYou can achieve 5/9 density by infinitely tiling this pattern horizontally: 010101 110110 101010

@randomra not without a filler row which you can only fill sparsely
@randomra No
5:55 PM
@orlp I think your answer should state explicitly that this only provides an upper bound, but doesn't extend to the full plane.
@MartinBüttner what do you get if you fill that row? >50%?
I only got <50% so far
@MartinBüttner It is not an upper bound either?
oh right
but I think you can show that it gives an upper bound that tends to 5/9
no, it is an upper bound
because 5/9 is optimal for 3x6
@MartinBüttner why can't a 4xN solution not be more dense?
for example
5:57 PM
it could be, but the full plane can't be
@MartinBüttner why not?
and the fact that you can tile it shows that we can't lower the bound further by examining 3xN
3x6 does not imply 6x6
no it does imply 6x6
and 6x6 implies 36x36
@orlp pick any 3x6 section of the full plane.
and 6^n x 6^n
5:58 PM
it can't contain more than 5/9 tiles... so the average can't be higher than that
@MartinBüttner well, I didn't prove that 5/9 was optimal
I did prove it was achievable
so I guess it puts a lower bound on the upper bound?
you proved it optimal for 3x6
@MartinBüttner how?
that's enough
@orlp I thought you did an exhaustive search
@MartinBüttner for certain N
5:59 PM
that's sufficient
you've proven that in the entire plane, no 3x6 segment can contain more than 10 ones
so the average in the entire plane can't be higher than 5/9
the only thing the tiling of the horizontal strip gives us beyond that, is the fact that we can stop examining the 3xN strip because it won't lower the bound any further.
I don't see how me finding a pattern for 5/9 implies that no pattern for (5+delta)/9 exists
just by checking up to N=~12
because if the average in the entire plane was (5+delta)/9, there would have to be 3x6 segments with 11 tiles, or otherwise the average would be <= 10/18
it's the same argument as that of the 7/12 answer
Midpoint theorem woohoo
@MartinBüttner right
A: Sandbox for Proposed Challenges

ghosts_in_the_codeNote: I think the question is fine. I just need some more testcases for it. You are given the priority order of alleles for a particular trait. For example, A B O means that A and B are equally dominant and O is recessive to both of them. An organism has exactly two alleles, but only the ...

6:02 PM
@MartinBüttner but this is an independent result of my 5/9 tiling
@orlp indeed
which is why you should mention that you've proven 10/18 optimal for 3x6
because that implies an upper bound of 5/9. and the tiling implies we can stop looking at 3xN to find a better bound.
Quick question. Isn't 7/12 for 3x4 larger than 5/9 for 3x3 and 3x6? Or does that not work because the 3x4 tile doesn't tessellate?
@Sherlock9 that
6/9 for 3x3 is even larger
but that's useless because it doesn't tile
(if it did, that would be a lower bound as well)
we haven't found a specific tiling better than 1/2 yet
At this point, let's call 5/9 the upper bound
1/2 the lower bound
And start on a new M for MxN arrays
6:09 PM
@orlp exhaustive search over 4xN? :)
Consider the possibility, gentlemen, that the answer may be 1/2
but can you prove it? ;)
I like to think I'm a math nerd, but my actual math skills are rather weak
So probably not
This is probably relevant en.wikipedia.org/wiki/M,n,k-game
oh haha
I'm dumb
5/9 was already right in the question
uh, what?
6:17 PM
it's the pattern from the question, just sliced and rotated a bit
I don't think the pattern in the question can be rotated to have rows-of-2 in both orthogonal directions
the pattern in the question also has 1/2 density
check what I posted
it's a horizontal 5/9 pattern
I can see that
but I can't find it in the pattern in the question
using that "Y" shape in the question
or V
well right, but you've shifted the tiles off grid
6:20 PM
"You can perform this action again in 1 seconds"
I believe I've got the answer
exhaustive search for 4x6 gives 12 as the optimal
or 4x4
oh no
I had some old printing check in there, to check for horizontal tilability
false alarm!
ye, 13/24 is possible on 4x6
6:24 PM
so that already disproves the 5/9 as upper bound
(since 13/24 was exhaustive)
guess it's 1/2 after all
just need to find the smallest NxM that proves it
This question reminds me of the integers as sums-of-powers question
16/30 still possible
There's absolute maximum you need, 9 cubes for any integer, IIRC
wouldn't it be pretty troll if it was like N+1 / 2N for some huge N?
lol it certainly would be
6:26 PM
And then there's the supremum, where after a certain N, you only need ... 6 cubes? I don't recall if the cube one has been proved
16/30 optimal?
like N = ackermann(3^2, 3^2)
@MartinBüttner still running
13/24 is optimal though
which is already lower than 5/9
You always need four squares and after a point, you need 16 fourth powers I think
funnily enough 4x6 proved a stronger bound than 5x6
well that happened on 3xN as well
where it increased for two before dropping back down to 5/9
the same could happen here with some period
6:29 PM
trying to tackle 6x6 now
oh wait, you're doing 6xN
I already tried 4x5
was 12/20
sure, but why not check 4x7 and 4x8 first?
I guess I could try 4x7
@MartinBüttner I don't have to bother checking odd x odd, right?
since that can never be 1/2
en.wikipedia.org/wiki/Waring's_problem This is the thing I mentioned
6:30 PM
so it can't disprove it (because we already have a lower bound of 1/2), nor prove it (since it would have to hit exactly 1/2 to make the bound tight)
4x7 is >= 16
so nope
oh it finished while I was alt-tabbed, it IS == 16
@orlp they might help for finding a tiling for 4xN though?
@MartinBüttner we already have a working tiling
at this point only brute force to prove the bound 1/2 tight is useful
unless you conjecture that 1/2 is not tight
It would be nice to have a second one
lacks some panache
no, I mean we could get the same result as for 5/9 by finding a better tiling for 4xinfinity which tells us we can stop checking 4xN
Can we parellelize this?
Send us the code
And we'll do some of the checking at the same time?
6:34 PM
super ugly
and I suggest pypy to execute
4x8 is not fruitful
I'm doing 6x6
Isn't 17/32 < 13/24 ?
Tell you what, I'll check 4x8
run this
I added a line that prints if something tiles horizontally
@Sherlock9 that's what we want
@orlp not necessarily... whatever we find for 4x8 might be a valid tiling
I guess you can also add this
    if valid_matrix(M*2):
        print("TILES VERTICALLY!")
oh, are we doing another get the best ratio out of this binary grid with pattern thingy?
6:39 PM
right below the horizontal
Peter would love it
Do I need to download Python 3.2 to run Pypy 3?
note that horizontal && vertical != plane
@Sherlock9 it's valid python2
I have 3.4.3
it works in both versions
6:40 PM
@orlp not true I think. you need M*3 to show that
what question is this discussion about?
(there are two seams)
Q: Maximal tiling without any 3-in-a-rows

MrTiYou are given an arbitrarily large grid, where each square can either be off or on (think Game-of-life type board). You need to tile such a grid to maximize the number of "on" squares without there being any 3-in-a-row of "on" squares. A 3-in-a-row can be horizontal, vertical, or diagonal. 3-i...

everyone grab that ^
shows if it tiles horizontal, vertical and/or the plane
is the ratio #1/total?
To save space, I just made it print when it tiles the plane
6:51 PM
talked 2d ago
chirp talked 2 days ago?
oh alex!
he must have make doing with his socks.
You totally missed everything.
23 hours ago, by Dennis
\o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/ \o/
6:53 PM
Congratulations! That's awesome!!!
Thanks. :)
Though I think anyone who's spent more than a minute or two on the site could tell that you're legendary anyway.
This question sent me over the edge:
Q: Legen… wait for it…

Dennisdary! In events entirely unrelated to what will hopefully happen to me in the next couple of days, I task you to write code that does the following: Print Legen... wait for it... immediately, with a trailing newline. Wait until the next full hour (when the cron job for awarding the badge ru...

6:56 PM
@MartinBüttner how would you generate a uniformly random latin square?
@orlp If you have a 4x4 with A, B, C, and D, you would just construct the rows (or columns) of the square with equally probable permutations.
@AlexA. how?
like, I understand the first row obviously
but let's say the first row is BCAD
how would you generate the second row with equally probable permutations?
@orlp just permute a working one, but I read that you said it doesn't work
wait, that's likely not uniform
You would select a random permutation of BCAD (excluding BCAD itself) for the next row. For the row after that, you select another random permutation, this time excluding BCAD and the one you just made.
because multiplicities
this might be a nice instalment for random golf of the day :)
7:00 PM
@AlexA. BACD is not BCAD, but not legal either
@MartinBüttner meh
everyone will just use the O(N!) sampling with rejection
you can easily rule that out if you know something better exists
@orlp Oh right
@MartinBüttner why?
I don't understand why
7:01 PM
well I suppose there could be non-uniform multiplicities
I mean, look at the element at the top left
it has equal chance to end up in any position
the same goes for any other element

« first day (1763 days earlier)