🔒 Best and worst duplicate binary parts

[orchid magnet]

So I found an interesting task,
I have to give a 100 characters length string of 1s and 0s and I have to give one with the worst and one with the best score, that this function gives:

def main():
    sorozat = input().strip()
    points = 0
    for i in set(sorozat[i:j] for i in range(len(sorozat)) for j in range(i+1, len(sorozat)+1)):
        if i + i in sorozat:
            points += 1
    print(points)
main()

[round scroll]

@orchid magnet

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[orchid magnet]

I only need to report the best and worst pointed sequence I find

in theary the worst point possible is 3 and the best points in 84

there are 2^100 possible sequences so its not an option to check them all

I wrote my current solution in cpp that checks random numbers but there surely is a better way:

#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
#include <random>
#include <ctime>

int count_strength(const std::string &s) {
    int n = s.size();
    std::unordered_set<std::string> seen;

    for (int i = 0; i < n; ++i) {
        int max_L = (n - i) / 2;
        for (int L = 1; L <= max_L; ++L) {
            if (s.substr(i, L) == s.substr(i + L, L)) {
                seen.insert(s.substr(i, 2 * L));
            }
        }
    }
    return seen.size();
}

const int FIXED_LEN = 100;
std::string random_binary_string(std::mt19937 &rng) {
    std::uniform_int_distribution<int> dist(0, 1);
    std::string s;
    s.reserve(FIXED_LEN);
    for (int i = 0; i < FIXED_LEN; ++i) {
        s += dist(rng) ? '1' : '0';
    }
    return s;
}

int main() {
    std::mt19937 rng(static_cast<unsigned>(std::time(nullptr)));

    std::string best_s, worst_s;
    int best_score = -1;
    int worst_score = INT32_MAX;

    while (1)
    {
        std::string s = random_binary_string(rng);
        int sc = count_strength(s);
        if (sc < worst_score) {
            worst_score = sc;
            worst_s = s;
            std::cout << "worst " << worst_score << " " << worst_s << "\n";
        }
        if (sc > best_score) {
            best_score = sc;
            best_s = s;
            std::cout << "best " << best_score << " " << best_s << "\n";
        }
    }

    return 0;
}

[grizzled trail]

That function is a mess, reusing i. Please rename one of them.
main's counting the number of times any substring in sorozat appears twice in a row. The maximisers are probably all 1s or all 0s. The minimisers are probably alternating 1s and 0s

It's pretty easy to take bin of an integer and get a binary string by the well. I don't think 2**100 is too high just to brute force this and prove it, even with the O(^2) function?

[orchid magnet]

renamed: ```py
def main():
seq = input().strip()
points = 0
for subseq in set(seq [i:j] for i in range(len(seq)) for j in range(i+1, len(sorozat)+1)):
if subseq + subseq in seq:
points += 1
print(points)
main()

[grizzled trail]

Thankyou 🙂

[orchid magnet]

I calculated it if on average it takes ~ 20 ms to run the function on a 100 length sequence then it would take about 7042503334601274452759462 hours

[grizzled trail]

You could save that set of all the subsequences too, and reuse it for every double subsequence look up, making that bit O(1) instead of O(N)

[orchid magnet]

oooh

you are saying something

[arctic lion]

I think it would be reasonable to assume that you're supposed to do this by clever construction rather than any type of brute force

[orchid magnet]

yes, but I couldn't think of one so I'm tring my best to get the closest

[orchid magnet]

Do you have any idea?

[arctic lion]

brain is not braining good, but am thinking

[arctic lion]

well, I seem to have found something for getting the input that gets you 3:
https://www.researchgate.net/publication/2810849_How_Many_Squares_Must_a_Binary_Sequence_Contain

[orchid magnet]

it has to be with 100 length

either I can't find it or idk

or should I read the whole thing?

[arctic lion]

yeah, but skimming through the paper doesn't it say you can create an infinitely long sequence that still only scores 3?
wouldn't you be able to just chop it at the 100th character

[orchid magnet]

hmm

0110001110101100011101011000111010110001110101100011101011000111010110001110101100011101011000111010 doesn't work

[arctic lion]

how did you get this string?

[arctic lion]

I think I found the relevant part to your problem tho:

[orchid magnet]

so I thinked its 010011000111001101 repeating

oh I missread the bits :D

[arctic lion]

so you first need a square-free word that uses 3 characters a, b, c that avoids aca and bcb
then replace all bc with bdc, and cb with ceb
then replace all abcde with the C(...) and you're done

at least I think

[orchid magnet]

ok, I'm tring to understand it

got it!

0110001110010111000110010110001011100101100111000101100011100101100111000101110010110001011100011001

[orchid magnet]

Now we just need the 84 one

really thanks :)

[round scroll]

Python help channel closed for inactivity

This help channel has been closed. Feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.