Then you go through every permutation of the alphabet and perform KMP. So supppose you have the permutation DACB, then you're effectively doing KMP with the substring DADCB
I think my first thought (when I pinged you about hashing) was to keep track of the substitutions in a sliding window and counting how many unique ones there are
@Lembik maybe emphasize the "substring in "Given two strings X and Y, with X no longer than Y, the task is to determine if there is a substring of Y which is an isomorph with X.", as it isn't obvious that you have to search for substring not somplete isomorphs\
@Sp3000 I would have expected find to change to KMP if the Boyer–Moore takes linear time already, but maybe that is too complex to be implemented
which was the username-related golf? I can't recall?
I can't think of a recent challenge that required this; could you link to one where having a specific username would give you an advantage? — M. I. Wright8 hours ago
@Sp3000 yes but the worst case linear algorithms can also have O(n/m) expected time (assuming n >= m)
so I don't see any advantage in making the worst case worse
the first link is interesting!
I feel that they are wrong though :)
"After some tweaking, I came up with a simplication of Boyer-Moore, incorporating ideas from Horspool and Sunday.".. well. there is a famous algorithm called Boyer-Moore-Horspool!
@Sp3000 that's interesting. I did know about the ordereddict thing. Not wanting to start a flame war, but I still remember their reasons for banning tail recursion elimination
@Sp3000 yes in a sense... I mean you could turn off the optimisation you would have thought for debugging. And python is essentially impossible to debug in any case due to its dynamic typing :)
@Lembik Yes, so in def f(x): return x*x + 3, there is no issue. But if you start to use variable names like x for variables with a larger scope, then... the problem is with your code, not the language.
I am reading in fractions from a file such as 2062330148916048489838634780764846257988806287128462353767378575301307559770949938188026163059947233642890831794529781335182628532224348874969607100610492653202421704420391651/8104522595470689372094546608771799123071184047348509570304018222052056272290836223436927829974812098219136497287696853871865529444163623648216552410378835326291370709768573288448
what's the simplest (and most accurate) way to convert them to decimals?
so I really need to split it into two ints for example first?
A Chinese checkerboard looks like this (based on this question, but this time it has a fixed size):
G
. G
G G G
G G . G
B B B B . . Y G . Y . Y Y
B B B . . G . . . Y Y Y
B . B . . . . . Y . Y
B . . . . . . . . Y
. . . . . . . . .
. P . . . ....
Language: PHP
A Company went to a college campus for hiring purpose. Various candidates participated in the recruitment exam conducted by the employer. There are 10 final candidates left who qualified for the vacancy. Employer maintains the marks of the candidate in the first test. Given a numbe...
@Sp3000 Yes - I know it's painful at the moment but I will update it after the first answer arrives, and there is a lot of room for improvement so I expect at this point it will be much quicker
@Sp3000 It takes about 5 or 10 minutes on my machine. You mean loop over the required offsets rather than looping over all the pixels? Is that sufficiently obvious to not wait for the first answer?
Longest day of the year - here's something to waste the extra time...
Overview
Note this is not a popularity contest and not a graphical output challenge - you are only required to output a string of 65,536 zeroes and ones. The Stack Snippet at the bottom of the question will display this as ...
Fair points - I'll edit now before anyone else gets stuck in that tarpit. I don't want it obfuscated - it's there as a baseline implementation. If it's obvious enough there's no point in hiding it.
I think it's a good compromise - there's still plenty of room for efficiency improvements but it only takes a few seconds to calculate a score now
I guess even if your implementation doesn't give the exact same score as long as it's close enough it should still take you in the direction of images which will also score well in the snippet
It's correct to 10 sig fig, which is good enough :P - and yeah, I'd like to see efficiency improvements too. I can only really think of one more for calculating the score atm
@Sp3000 I linked to your profile and just noticed that the first person to take an interest in my "longest day" challenge is in Australia where it's the shortest day...
I was trying to find a scoring method that would not have a trivial solution, but it took me so long to spot the trivial solution for this scoring method that I thought I'd post it and see how long it takes. Thanks to Jimmy only an hour...
The results I was getting were converging on tangles and weaves, and not heading towards the checkerboard pattern, so I only realised it was a solution when I read up on pythagorean triples: The non-hypoteneuse sides of a primitive pythagorean triple are always one even and one odd, so the scoring pixels of a black square on a chess board are always all white.
I took a long time to notice it myself, which is why I thought it would be worth posting...
The same checkerboard pattern would be optimal for any subset of primitive pythagorean triples, even if it wasn't restricted to just primes. It left me struggling to think of a scoring method that wouldn't become trivial.
@MartinBüttner Was it immediately obvious to you? I thought the time it took me to realise would make it a worthwhile question but that's 2 people in the first hour or so...
Were you just going to post it as a competitive answer or did you already know it was optimal?
I don't think it hurts to mention that it's optimal now though - anyone using the checkerboard pattern as the starting image for their code will find that out immediately...
Lol I thought I might get a few days out of this question, rather than an hour.
And the images could have been interesting to see too
@MartinBüttner I can't see there being any more answers. I'll understand if the question needs to be closed on that basis, but I'm hoping it will stay open until I can assign a bounty to Jimmy. Will the bounty survive the question being closed afterwards?
There doesn't seem any point posting a bounty for second best/best suboptimal answer, as finding one would just require changing a single pixel from the checkboard. My hope was that there would be a series of gradually improving answers narrowing down on the optimal one, but it's dead in the water now :)
btw, if you haven't retracted it already, I believe you upvoted my procedural noise on the sphere question on the computer graphics proposal. that just hit 11, so you could reuse one of your votes now.
@trichoplax the problem in this case is that this isn't only optimal... I even would have posted this first even if it merely beat the random submission, just because it's the simplest thing anyone could think of
I'll put that down to the current desperation - hopefully meta in beta will define what's on topic well enough that the example questions won't be too relevant. Hopefully...
@Sp3000 @MartinBüttner do you think a proof of optimality of Jimmy's answer would be best edited into the question, posted as a self-answer, or left out?
Stretching Words
Write a program or function that stretches a word by an array of letters to duplicate.
For example:
input: chameleon, [c,a,l,n]
output: cchaamelleonn
Input
The starting word (e.g. chameleon)
An array of characters ([c,a,l,n]) or a string to represent an array (caln), or som...
Background:
MtDNA is a part of the human DNA that is passed from a mother to a child and it rarely mutates. Since this is true for all humans it is possible to create a huge tree that visualize how all humans is related to each other through their maternal ancestry all the way back to the hypoth...
A covering array is an N by k array in which each element is one of {0, 1, ..., v-1} (so v symbols in total), and for any t columns chosen (so an N x t array) contains all possible v^t tuples at least once. The applications of Covering Arrays range from software and hardware testing, interaction ...
code-golf ascii-art
A MIDI Track Display
Background
MIDI files are quite different from WAV or MP3 audio files. MP3 and WAV files contain bytes representing a "recording" of the audio, while MIDI files have a series of MIDI messages stored in MIDI events informing a MIDI synthesizer which virt...
A Chinese checkerboard looks like this (based on this question, but this time it has a fixed size):
G
. G
G G G
G G . G
B B B B . . Y G . Y . Y Y
B B B . . G . . . Y Y Y
B . B . . . . . Y . Y
B . . . . . . . . Y
. . . . . . . . .
. P . . . ....
Longest day of the year - here's something to waste the extra time...
Overview
Note this is not a popularity contest and not a graphical output challenge - you are only required to output a string of 65,536 zeroes and ones. The Stack Snippet at the bottom of the question will display this as ...
Stretching Words
Write a program or function that stretches a word by an array of letters to duplicate.
For example:
input: chameleon, [c,a,l,n]
output: cchaamelleonn
Input
The starting word (e.g. chameleon)
An array of characters ([c,a,l,n]) or a string to represent an array (caln), or som...
code-golf ascii-art
A MIDI Track Display
Background
MIDI files are quite different from WAV or MP3 audio files. MP3 and WAV files contain bytes representing a "recording" of the audio, while MIDI files have a series of MIDI messages stored in MIDI events informing a MIDI synthesizer which virt...
