Forming Polyominoes with a Chain of Rods
code-golfcombinatorics
Consider a (closed) chain of rods, each of which has integer length. How many distinct hole-free polyominoes can you form with a given chain? Or in other words, how many different non-self-intersecting polygons with axis-aligned si...
@Sp3000 @PeterTaylor what do you think about code golf vs fastest code for the chain-of-rods challenge? I'm usually not a big fan of code golf for NP-complete problems, because there's little incentive in finding interesting ways to truncate the search space. At the same time, the necessary data structures probably do make a not-too-bad golf even with a naive algorithm.
How about posting separate challenges? One code golf, which only needs to handle small test cases, and a fastest-code challenge where answers are scored on large random inputs?
(And if I can find a 3rd scoring criterion that makes sense for this challenge, I might finally be able to do my triathlon :D)
@MartinBüttner So how do you like being an example for all the icy avatar image answers? :P
(Also, sorry to everyone for being decidedly less active on PPCG recently. It's been really crazy on Puzzling.SE and there's just been a lot of stuff IRL going on in general; I promise I'll be entirely back soon. :) )
@MartinBüttner Just realised I still count two angle-strings as equal if they're cyclically equal after you swap As with Cs. Not that it changes any results though, because you're requiring them to be anticlockwise :P
By the looks of it I'd say either fastest code (I feel the same way about NP-complete). Either that or code-golf with some sort of time limit to prevent purely brute force solutions
@Calvin'sHobbies For the 95 movie quotes challenge, I know a language prints the quote to stdout and exits abnormally, and prints an error message to stderr. Can I use it? I think better not. But if I post other answers, it will be likely no more usable...
well, some people don't like golfing, and some people aren't interested in fastest code, so with two questions, everyone could pick their preference or compete in both of them
we've had some discussion on meta about whether the same question with different winning criterion is a duplicate, but I think in this case it isn't... you can certainly always improve the fastest code answer by pruning the search space, which will inevitably cost you characters.
I wonder if you can actually speed things up by solving subset sum first
I mean, all valid configurations need an even total horizontal and even total vertical length, each of which can be split in half
@Sp3000 btw, that's the reason there was no solution for [1,2,3,4,5,6,7,8,9].
(Actually yes, subset sum is faster. The naive search space is 2^n, whereas the total search space for the rods is 3^n. However the latter might be easier to prune.)
@MartinBüttner I don't think it has much by way of data structure requirements. If I did a golfed implementation in GS I would just want to track the points visited (to detect self-intersection) and then I'd do a normalisation procedure to identify duplicates.
@Peter yes, data structures was the wrong word. I still think identifying the duplicates and checking counterclockwise traversal are interesting to golf.
If n>0and(n%2<1) then n is positive and even, so you could as well have n>1and(n%2<1). Am I correct in understanding that in Python that can be (n%2<1<n) ?
@MartinBüttner and @Optimizer, are you both making the same assumption that I mention in my comment on the question? If so, I'm inclined to edit the question. If not, I'll vote to close it as unclear.
I just noticed I need a few more characters to deal with the case that no result exists, but being able to assume that the top left corner is 0 saves some
and yes, I assume that, because that's what the OP said
@PeterTaylor it does (have bigints)
@PeterTaylor "obvious"... :D
the "obvious" way is to generate all permutations of [(N-1)*right, (N-1)*down], find the paths, sum them up, remove negative paths and take the minimum ;)
@PeterTaylor :P ... I did indeed study dynamic programming in the first year at uni... but that was a while ago, and I never actually had to use dynamic programming until joining PPCG ;)
As a side-effect, I was a student member of the IoP for three years. Apparently I remained on the list after the first year as an unrequested favour from the president of the student physics society, whom I knew vaguely and who knew that my dad taught his sister physics.
I personally wouldn't mind accepting earlier, because I change the accepted answer if something better comes along, but some people seem to take offence...
possibly, once I've sorted out where to collect it from and how to collect it... but I think 3 "levels" would be nice... a simple set from Rosetta Code... an advanced set from SO... and the Super Hexagon set right from PPCG
The comment at Sum of strings without converting displays strangely on Firefox 33.1 on OSX 10.9.5. Look at the numeral 1 inside the parens in each_cons(10).
Any idea why?
What is that character that got in there?
Longest reverse palindromic DNA substring
As you may know, in DNA there are four bases — adenine (A), cytosine (C), guanine (G) and thymine (T). Typically A bonds with T and C bonds with G, forming the "rungs" of the DNA double helix structure.
We define the complement of a base to be the base ...
and in "real" languages it's hard because keywords and builtins...
hmmm... Marbelous? :D
inserting spaces will definitely break it, but satisfying the layout in the first place is tough... and the problem itself is way too difficult for marbelous
okay... different topic... how would I score fastest code for the polyomino challenge? I'm thinking I could provide random test sets for N = 10, 11, 12, ... (say 20 to 50 for each N). your primary score is the highest N for which your code runs within 5 or 10 minutes, say. tie breaker is actual time taken on that test set.
my main issue is that the amount of solutions (and therefore probably also the relevant part of the search space) depends a lot on the actual rod lengths... if they are very uniform, you get a lot more solutions than if they aren't.
so on the one hand, using random sets will probably not include this worst case. on the other hand, the single case of [1]*N might actually outweigh several other test cases, so if I did include, scores could be largely dominated by the performance on this set
Forming Polyominoes with a Chain of Rods
code-golfcombinatorics
Consider a (closed) chain of rods, each of which has integer length. How many distinct hole-free polyominoes can you form with a given chain? Or in other words, how many different non-self-intersecting polygons with axis-aligned si...
The comment at Sum of strings without converting displays strangely on Firefox 33.1 on OSX 10.9.5. Look at the numeral 1 inside the parens in each_cons(10).
Any idea why?
What is that character that got in there?
Longest reverse palindromic DNA substring
As you may know, in DNA there are four bases — adenine (A), cytosine (C), guanine (G) and thymine (T). Typically A bonds with T and C bonds with G, forming the "rungs" of the DNA double helix structure.
We define the complement of a base to be the base ...
