@PhiNotPi It's just a maximal pairing problem with the addition of the constraint that h must be paired. Maximal pairing is a well-studied problem; the constraint can be handled by iterating through the possible pairings with h and removing them temporarily from the set. It's still polynomial time.
Alternatively, this can be formulated as exact set cover. The universe to cover is the union of A and B; the sets which can cover it are the edges in the pairing, plus a one-element set for each element of B other than h, to allow for the fact that not every element in B needs to be paired. Then dancing links will find a solution quickly.
Happy Holidays!
Introduction
With the holidays upon us, I decided to make an appropriately themed challenge. Given a list of holidays and two dates, if the current date falls within the range when the program is run, output an appropriate holiday greeting.
Challenge
The preset list of recent ...
@Lembik Is the polygon specified or only the coordinates? That is, do you have to consider all polygons that could be made from the coordinates given, or just all possible triangulations of a specific polygon?
You could still recurse if each step checks the new potential triangle for correctness
Yes allowing concave shapes increases the complexity considerably
Sounds interesting with either shortest code or fastest code.
Presumably fastest code will favour more interesting algorithms - with shortest code I'd expect a brute force approach that simply creates the huge set including invalid solutions, and then culls them.
Could shortest code still lead to interesting algorithms if the number of points is sufficiently large? Or would it still be a brute force search with the culling done in progress to avoid surplus memory usage?
I'm not sure how to approach this problem. I'm not sure how complex a task it is. My aim is to have an algorithm that generates any polygon. My only requirement is that the polygon is not complex (i.e. sides do not intersect). I'm using Matlab for doing the maths but anything abstract is welcome....
bytes are better than characters, because otherwise you may get massive Unicode-encoded nonsense as answers. I learned about that recently, and it's a good point. APL characters actually count as bytes because of the historical character set (unless you use Unicode characters in the program), so that's pretty fair
@nyuszika7h That's true. On the other hand, counting bytes encourages unprintable code that has to be posted as a hex dump. I personally like "printable ASCII only", but then that's unfair to APL... :(
Of course, we could just tell all the APLers to write in J instead. ;)
looks like even with Rasterize it tries to build the vector graphic first
and apparently 120k point primitives require a lot of memory
@user23013 thanks for the comment on the battleblock challenge, I was afraid something like that might be the case. I was actually considering to just limit it to 3 blocks, but I need to figure out if hardcoding all solutions is actually shorter than solving it in that case.
Er, notation is number of times to toggle the block. Should probably have said that
Because e.g. if the first block is X then you just need to solve (number of toggles for first block) + (number of toggles for second block) + X = 0 mod 4
Say we have a solution where we toggle the blocks A, B or C times respectively. Then we're solving A+B = 4-X (mod 4), A+B+C = 4-Y (mod 4), B+C = 4-Z (mod 4)
Oh they just have to be the same level
Well in that case you can replace 4 with any other constant :P
@githubphagocyte btw, the generalisation that would actually make sense in the context of the game, is to not have a string of blocks, but a grid (where some cells might not contain a block), and each block toggles all adjacent ones
because you can build that in the level editor
(and you could only toggle blocks which have a free side)
yeah, I'll allow any (consistent) output for unsolvable inputs, as long as it's distinguishable from any potential solution (including toggling no blocks)
Print rotation-safe numbers
codegolf numbers
Background
You are working for some board-game manufacturer and need to produce wooden tiles with the numbers from 0 to n engraved on them for some game. However, some tiles would become indistinguishable, e.g., 6 and 9. To avoid this, you have to e...
I don't mind golfing languages like GS or CJam, which just stand on their own and use a paradigm that's really useful for golfing. But I really don't like stuff like Pyth, which just takes a language and replaces built-ins and keywords with single characters and removes superfluous syntax.
I updated my proposed challenge to require one specific format, I think it's unnecessary to support so many formats when you can't even use a library for it
Happy Holidays!
Introduction
With the holidays upon us, I decided to make an appropriately themed challenge. Given a list of holidays and two dates, if the current date falls within the range when the program is run, output an appropriate holiday greeting.
Challenge
The preset list of recent ...
Would a language design contest be of any interest? Is there a straightforward way of setting a challenge and then competing to design the language that can best golf that challenge?
@algorithmshark you don't get it. The spec of GS is not derived frmo any other language, while Pyth is just Python with minified literal and function names
I meant that the program has to take input and give output - but I see what you mean now - the language could just be defined such that null source code takes the input and gives the output as required, for arbitrarily many different values for the input
If you specify a problem space the language has to excel at, then the language mapping strings as short as possible to the solution of those problems is the trivial winner.
If you try to say that the language has to have some intuitive interpretation in the sense of every other language we've come up with, then that's fraught with ambiguities.
What about competing based on shortest average code length over solutions posted to future challenges? Say, 10 solutions to challenges over the next month?
Only challenges posted after the last edit to the answer containing the new language count
(and the challenge cannot be posted by the same person that posted the new language design...)
I'm happy leaving it open so that people are free to design arbitrarily opaque languages - that leaves them at a disadvantage when trying to find 10 challenges they can work out how to solve.
Or maybe it could be open-ended rather than just the next month. So that each time a solution is posted using the language, it's original post is updated to show its progress so far.
That's an interesting thought, but I don't envy the person tasked with organizing that.
Also, it would take a while to see any results.
I think perhaps PPCG itself is already a challenge of that nature. If you design a golflang, you get to pit it against every other language in problems of your choosing.
HQ9+ would have an astounding track record, in that case :P
I'd like to see what it would look like releasing a block of them along the x axis all at once, but I guess keeping track of them would mean a slightly longer program?
@MartinBüttner so in a brownian tree, a random particle is started at a random point , it walks until it reaches a white pixel (in this case) . If this walk is short enough, it is drawn, else, discarded
It does give the possibility of the tree growing through several particles at once if a particle moves to suddenly connect a string of others to the tree
You might get more variety in structure if they were permitted to move away from the origin but only a certain distance. Then branches could grow in 3 directions instead of just 2.
lets say, if your randomly created particles have a pattern (circular/triangular etc), and then if you discard longer walks, you can get nice patterns in your final image.
@githubphagocyte I know. uniformly filled, but still having holes only
@Optimizer I'm not sure if we're talking about the same thing. Even with arbitrarily long walks, if the particles always start at a large distance from the tree then as the branches grow closer together the growth rate approaches zero in the regions they have fenced off.
@MartinBüttner You could also allow 4 directions by limiting the particles in x and y directions. I would expect that to give a sparser tree as branches growing towards each other in both directions can cut off regions faster.
@MartinBüttner I mean the particle can move up, down, left or right, and is not permitted to move past the upper limit you set to the right or to the top (you might not need a limit to the top if the limit to the right prevents getting around the initial tree).
I was thinking of an initial line as the starting tree, but it's just a point, isn't it? I might have to try this in python to see what happens (even though it won't be any good for the question).
ugh, I've got an almost working ~90 byte solution for the graph construction (which is still very golfable), but representing an empty matrix is giving me headaches...
I thought this was a cool problem so I challenged myself to do it without looking at any of the existing answers. I wrote a fairly short program and then spent a while making it shorter and shorter. I felt proud and finally posted it, and now that I'm letting myself look at other answers I can see one in the same language that's 89 bytes shorter. :P
Happy Holidays!
Introduction
With the holidays upon us, I decided to make an appropriately themed challenge. Given a list of holidays and two dates, if the current date falls within the range when the program is run, output an appropriate holiday greeting.
Challenge
The preset list of recent ...
Print rotation-safe numbers
codegolf numbers
Background
You are working for some board-game manufacturer and need to produce wooden tiles with the numbers from 0 to n engraved on them for some game. However, some tiles would become indistinguishable, e.g., 6 and 9. To avoid this, you have to e...
