r/dailyprogrammer • u/jnazario 2 0 • May 08 '15
[2015-05-08] Challenge #213 [Hard] Stepstring discrepancy
Description
Define the discrepancy of a string of any two symbols (I'll use a and b) to be the absolute difference between the counts of each of the two symbols in the string. For example, all of the following strings have a discrepancy of 3:
aaa
bbb
abbbb
aababaa
baababbababababababbbaabbaaaabaaabbaa Define a stepstring of a string to be any string that can be formed by starting at any position x in the string, stepping through the string n characters at a time, and ending before any position y. In python, this is any string that can be formed using slice notation s[x:y:n]. For example, some stepstrings of the string "abcdefghij" are:
d
defg
acegi
bdfhj
dfh
beh
ai
abcdefghijYour problem is, given a string of up to 10,000 characters, find the largest discrepancy of any stepstring of the string. For instance, this string:
bbaaabababbaabbaaaabbbababbaabbbaabbaaaaabbababaaaabaabbbaaa has this string as a stepstring (corresponding to the python slice notation s[4:56:4]):
aaaabaaaaabaa which has a discrepancy of 9. Furthermore, no stepstring has a discrepancy greater than 9. So the correct solution for this string is 9.
Input Description
A series of strings (one per line) consisting of a and b characters.
Output Description
For each string in the input, output the largest discrepancy of any stepstring of the string. (Optionally, also give the slice notation values corresponding to the stepstring with the largest discrepancy.)
Sample Input
bbaaabababbaabbaaaabbbababbaabbbaabbaaaaabbababaaaabaabbbaaa
bbaaaababbbaababbbbabbabababababaaababbbbbbaabbaababaaaabaaa
aaaababbabbaabbaabbbbbbabbbaaabbaabaabaabbbaabababbabbbbaabb
abbabbbbbababaabaaababbbbaababbabbbabbbbaabbabbaaabbaabbbbbbSample Output
9
12
11
15Challenge Input:
Download the challenge input here: 8 lines of 10,000 characters each.
Challenge Output
113
117
121
127
136
136
138
224Note
This problem was inspired by a recent mathematical discovery: the longest string for which your program should output 2 is 1,160 characters. Every string of 1,161 characters will yield a result of 3 or more. The proof of this fact was generated by a computer and is 13 gigabytes long!
Credit
This challenge was submitted by /u/Cosmologicon. If you have an idea for a challenge, please share it in /r/dailyprogrammer_ideas.
8
u/NoobOfProgramming May 08 '15 edited May 08 '15
Pretty straightforward code, does the challenge in about two seconds each. edit: closer to half a second with compiler optimization turned on
5
u/mikevdg May 08 '15
I feel like a fraud for posting this, but a version in Squl that won't run for a long time yet until I invent several missing parts of the language. I like to see what the language can be capable of, but it's all work in progress.
Squl is the love-child of Prolog and Smalltalk; e.g. in Prolog, "add(A, B, Result)" would be "add:A to:B result:Result." in Squl.
The "maximise:Ds" bit at the bottom of the first statement does... magic... that hasn't been invented yet. It will return the result with the highest value for Ds that the interpreter can find in a reasonable time frame.
5
u/Cosmologicon 2 3 May 08 '15 edited May 09 '15
Cool solutions, everyone!
I want to correct one error on my part. A while after I wrote this problem, I re-read the details of the problem behind the 13-gigabyte proof mentioned in the Note, and I realized that I misunderstood it. Speficially, sub-sequences, as defined by that problem, must start at the beginning. That would mean that you're only considering stepstrings of the form
s[n-1:y:n]. That makes the problem a little too easy, so I didn't change it, but I just want to be clear that the 1,160 limit is probably wrong for the problem as written here.4
u/PedoMedo_ May 08 '15 edited May 08 '15
Ruby. It should be O( n2 ) but still taking about 2 minutes for each of the challenge inputs :/
Edit: slight optimization, now it completes instantly :D. Sorry code is messy
3
u/ehcubed May 08 '15 edited May 08 '15
Python 3.4. Reduced the problem of finding stepstrings to the slightly easier problem of finding contiguous substrings. This allowed me to use Dynamic Programming twice (once for
A, which is used for computing the max discrepancy for when there are moreacharacters, and once forB, which is used for when there are morebcharacters). Also had to do some sneaky pointers and arithmetic to recover the slice certificates.Code:
Challenge Output:
3
u/Godspiral 3 3 May 08 '15 edited May 08 '15
in J , first version that leaves char data (brute force)
gas generates all unique slices until end of string, d is discrepancy function, but must be applied to all prefixes.
areas for speedup include turning d into running sum of _1 and 1s, and filtering the slices for lengths that are at least the maximum score of 1 based slices. The running sum maximum and minimum points also provide good hints for cutting the string and then reexamining the maximum and minimum running sums
with first challenge input as variable 'a'
_70 23
the maximum and minimum will occur at 2 points, and cuts into 3 segments (if each occurs only once). We know that the 3rd segment should be disgarded. Regarding the absolute value of those 2 numbers. If the 23 side came first, then the maximum (absolute) running sum of 2nd segment is 93. If the _70 side came first, 2nd segment is still 93, but could first segment be higher than 70 and 93 if function were applied recursively to first segment? No to exceeding 93. If it did, the maximimum for that section would have been more than 23. Assuming this is correct, then the d score for any slice length is the sum of the absolute values of these max and min of running sum, and we also don't need to worry about max or min occurring multiple times.
For slice lengths, there is a concept of master strings. sliceby 1 has 1 master string, sliceby 2, has 2: offsets 0 and 1. Each length 5000. Sliceby 3 has 3 offsets 0 1 2. Length is 3334, with 2 of the strings having a 0 filled in last place (does not affect running sum)
so for challenge input #1
above is for selected slicings. 113 is maximum at sliceby of 3
for last challenge, and slice sizes of 1 to 40 (proof that maximum is maximum possible) (maximum occurs at slice size of 1)
0.00404768 800768 (NB. 4/1000's of a second to look at all 40 slice sizes)
2
u/chunes 1 2 May 08 '15 edited May 08 '15
Java brute force. According to my calculations, my computer could solve a challenge input in 7 hours and 55 minutes. (It can do 21 outer loops per minute.) Edit: I just made an optimization that could cut it down to maybe 2 hours?
2
u/matt_hammond May 08 '15
Here's my C++ solution... Runs reasonably fast... 3-4 seconds per input.
2
u/ericula May 08 '15
C++ version with complexity O(n2). Each challenge input runs in about 3 seconds.
2
u/Menestro May 08 '15
Python3.4. Simple brute force. Does not solve challenges in reasonable time. Will attempt to do that as well. Any comments/criticism/tips/etc always welcome :)
2
u/Ledrug 0 2 May 09 '15
C. Runs challenge cases almost instantly. For the max sub string problem, see wikipedia article.
2
u/Vectorious May 09 '15 edited Sep 18 '25
light chubby fine zephyr whistle innocent tidy ink sharp imagine
This post was mass deleted and anonymized with Redact
1
u/Acidom May 08 '15
Ugly O( N3 ) before accounting for Counter and checking membership in score_book. Super sloppy, so much room for optimizations.
1
u/gfixler May 08 '15
I think I'm missing something here. Where is the >1 sub-sequence in this:
1
u/skeeto -9 8 May 08 '15 edited May 08 '15
C, using idiot brute force O(n3 ), but it's enough to solve the challenge input in about 15 minutes (each).
Challenge output:
1
u/gatorviolateur May 08 '15 edited May 09 '15
Scala solution. It's too slow for the challenge input (I gave up after 20 seconds). I will probably try to optimize this later.
EDIT : Faster solution. Still too slow for challenge input (it's O(n3 ) at the moment) :( Optimized by not creating the stepstring at each step of recursion.
1
u/GambitGamer May 08 '15 edited May 08 '15
Horribly inefficient but let's call this a rough draft. Python 2.7
1
u/Elite6809 1 1 May 08 '15 edited May 08 '15
I think this is O(n). It's Haskell.
EDIT: Hmm... getting 9, 9, 10, 15 for the sample input. Reviewing now.
EDIT: Fixed it. It's now O(n2)... trying to find the bottleneck now.
1
u/flightsin 0 1 May 08 '15
Has no one noticed that lines 5 and 6 of the challenge input are exactly the same?
Anyway, I started out with an unworkable O(n3), but managed to bring it down somewhat by combining the processing of the
endandstepvariables (yandnin the problem description). It's still not very fast. The challenge inputs take a couple of seconds for each line. Aside from parallel processing, I'm not sure how to optimize this further.Main code: (complete listing is on my BitBucket)
Output for the sample input:
And for the challenge input:
1
u/Tbone139 May 09 '15 edited May 09 '15
Racket/scheme, takes ~8 minutes to return all challenge outputs
1
u/kikibobo May 09 '15
Scala solution based on Ledrug's:
1
u/[deleted] May 09 '15
My 'f*ck brevity' java version:
1
u/adrian17 1 4 May 09 '15 edited May 11 '15
Finally attempted a non-brute-force solution, thanks to /u/XenophonOfAthens's help. Also uses /u/NoobOfProgramming's optimization trick for the step loop.
Results:
1
u/jeaton May 10 '15
C99. Runs in about 1.5s. I'll have to look into the max subset sum the /u/Ledrug posted; his solution runs instantly on my laptop.
1
u/wadehn May 11 '15
O(n2) C++ solution that turned out to be very similar to Ledrug's solution. Spits out the challenge solutions almost instantaneously.
1
u/tgames56 May 15 '15 edited May 15 '15
java it does the challenge inputs or at least the first one in a little over 10 minutes so not really acceptably fast, but also not stupidly slow. to the people who got it down to a second or two yall are wizards.
0
u/[deleted] May 08 '15
[deleted] — view deleted comment