"When voting, keep in mind, that in general, answers won't necessarily just depend on the answer, but potentially on some or all or the existing answers (we didn't really have that yet, but we might not want to preclude the tag from including those)."
hm, I wonder if I should make the mean and variance parameters for the next round of Random Golf of the Day (random numbers from a normal distribution), or whether I should just say mean = 0, variance = 1.
The number grows exponentially. I'm not sure what the best complexity to calculate it is, but the code which I said could be trivially adapted fills a quadratic number of elements in a table.
Here is some code that does it. This is O(n2) the first time you call it, but it builds a cache so that subsequent calls are O(n).
import random
cache = {}
def count_partitions(n, limit):
if n == 0:
return 1
if (n, limit) in cache:
return cache[n, limit]
x = cache[n...
BTW I was thinking about the random shuffle question while I walked home, because "You know what I mean" is a bit lower than the standard we normally hold questions to, and someone might come along who hasn't seen the whole discussion in chat.
I think that the simplest way of removing ambiguity is to say that a) you may assume that a library function which is documented to return elements (approximately) uniformly selected from a given set does actually select them uniformly; b) you must ensure that each individual conversion from elements uniformly selected from one set to elements approximately uniformly selected from another has a factor of no more than 65537/65535 between the highest and lowest probabilities.
That essentially requires 48 bits of entropy, so prohibits directly using random 32-bit floats to Fisher-Yates shuffle 2^31 elements, and it still falls a long way short of actually requiring the stated requirement "Every possible permutation must be returned with the same probability", but at least it's unambiguous and doesn't rule out any existing answer.
@PeterTaylor I'm pretty sure that'll put a lot of people of who have no clue why I'm requiring such specific probabilities... like Rainbolt said earlier "I'll just revoke my submission because I have no clue what random functions I may or may not use" (paraphrased)
Hmmm... I should make a challenge like "Write a connect four bot in less than 1000 bytes. Submissions will round robin each other a hundreds times. Winner has the highest win rate."
Do you think less than 1000 bytes makes it interesting enough?
I dunno. It's a solved game IIRC, so I guess it just depends on how much it takes to make it optimal. Once an optimal one comes out, the challenge is boring.
@MartinBüttner How would you make this clearer? 1. Ask Red for move X. 2. Drop a Red token into column X. 3. If Red has not won, then ask Black move Y. 4. Drop a Black token into column Y. 5. If Black has not won, repeat this process.
Tokens fall down a column until they collide with another token beneath it. You win a match if you connect four tokens in a row.
I'm making progress on my hovercraft battle physics. When the hovercraft is accelerating purely linearly or rotationally, I can calculate each tick exactly.
@Rainbolt This question has considerably less than 1000 bytes per answer, but only covers one move so they are a bit smaller than a program to play a complete game. Probably gives you an order of magnitude estimate though
(ignore the title - it's not really connect four factorial)
Doesn't show up in the SE search due to using 4 instead of four. Probably best to use both "connect four" and "connect 4" at some point in your question if you want to maximise the chance of being found by an in-site search
Write a Connect Four Bot
Your task is to write a Connect Four bot. Connect Four is solved, and so to avoid optimal solutions, your submission must be no longer than 1000 bytes.
Gameplay
Your submission will play against each other submission one hundred times. Each player will play first for...
"along the 8 directions of the compass" is not a single word (and not even shorter than "orthogonally or diagonally") but it's a single phrase and pretty clear I think
I glanced around for an implementation, but the best I found was an 8-or-so depth negamax. It was around 8k in JS, but terribly bloated. I'm sure it could be golfed down to the limit. I don't know how fast it runs, though. The one-second limit in addition to the 1k bytes probably works pretty well.
I started to write a 3d fractal tree generator. It's basically a render window, and two smaller XZ and YZ views where you can move the tips of the branches around (which will then recurse)
but I just realized that each branch also has to have a rotation with respect to the trunk, and I don't know how to represent it in a way that's obvious in the two views. an arrow pointing to the "right" will look really strange and not helpful in the side views
@Rainbolt the problem with the size limit is that at some point you'll actually get golfed koth entries, which I don't think you're interested in. so a 1k byte limit seems reasonable to tell people "you can't just encode a lookup table". but the time limit is probably more important to rule out optimal algorithms. even so, I think it shouldn't be too hard to solve a 4x4 board optimally... the tree is only up to 4 moves wide and up to 16 deep (but in practice you can probably prune a lot)
@MartinBüttner Removed character limit. Edited the bullet point to say: - Failing to output anything to STDOUT within one second double freaking indent - This should eliminate optimal entries. Thoughts on this?
kk... although my thoughts are you should implement a minmax solver yourself and make sure it doesn't complete in 10 times your time limit to be sure ;)
if it turns out not to be possible, I'll probably try MCTS... it should perform pretty well on this kind of small state space
Here is some code that does it. This is O(n2) the first time you call it, but it builds a cache so that subsequent calls are O(n).
import random
cache = {}
def count_partitions(n, limit):
if n == 0:
return 1
if (n, limit) in cache:
return cache[n, limit]
x = cache[n...
The queen in chess can move octoflectively.
Write a Connect Four Bot
Your task is to write a Connect Four bot. Connect Four is solved, and so to avoid optimal solutions, your submission must be no longer than 1000 bytes.
Gameplay
Your submission will play against each other submission one hundred times. Each player will play first for...
