diff options
| -rw-r--r-- | challenge-329/ysth/perl/ch-2.pl | 125 | ||||
| -rw-r--r-- | challenge-329/ysth/python/ch-2.py | 113 |
2 files changed, 238 insertions, 0 deletions
diff --git a/challenge-329/ysth/perl/ch-2.pl b/challenge-329/ysth/perl/ch-2.pl new file mode 100644 index 0000000000..063510cb75 --- /dev/null +++ b/challenge-329/ysth/perl/ch-2.pl @@ -0,0 +1,125 @@ +use 5.036; + +my @inputs = @ARGV; + +# if given command line arguments, do those +if (@inputs) { + for my $string (@inputs) { + printf "%-30s -> %s\n", $string, longest_nice_substring($string); + } +} +# otherwise, run an endless test of random values, comparing to simple version (stopping if an unexpected difference was found) +else { + my $checked; + STDOUT->autoflush(); + { + my @ascii_letters = ('A'..'Z', 'a'..'z'); + my $string = join '', map $ascii_letters[rand @ascii_letters], 1..rand 200; + printf "$checked\r" unless ++$checked % 1000; + redo if simple_longest_nice_substring($string) eq longest_nice_substring($string); + printf "string: %s\nsimple: %s\ncomplex: %s\n", $string, simple_longest_nice_substring($string), longest_nice_substring($string); + } +} + +sub simple_longest_nice_substring($string) { + my $longest_nice_substring = ''; + for my $starting_index (0..length($string)-1) { + my %nice; + my %not_yet_nice; + for my $ending_index ($starting_index..(length($string)-1)) { + my $c = substr $string, $ending_index, 1; + if (! $nice{$c} && ! $not_yet_nice{$c}) { + if ($not_yet_nice{$c ^. ' '}) { + delete $not_yet_nice{$c ^. ' '}; + $nice{$c} = $nice{$c ^. ' '} = 1; + } + else { + $not_yet_nice{$c} = 1; + } + } + if (! %not_yet_nice && $ending_index - $starting_index + 1 > length $longest_nice_substring) { + $longest_nice_substring = substr $string, $starting_index, $ending_index - $starting_index + 1; + } + } + } + + return $longest_nice_substring; +} + +sub longest_nice_substring($string) { + + # longest nice substring found so far + my $longest_nice_substring = ''; + + # characters that we know can't form part of a not yet found nice substring + my %never_nice = map(($_ => 1), split //, $string); + delete @never_nice{map $_ ^. ' ', keys %never_nice}; + + # loop over starting indexes while it is possible to find a longer nice substring + my $next_starting_index; + for (my $starting_index = 0; length($string) - $starting_index > length($longest_nice_substring); $starting_index = $next_starting_index) { + my $c = substr $string, $starting_index, 1; + ++$next_starting_index; + + # can we rule out any substring starting here? + next if $never_nice{$c}; + # shortest substring that may be nice will end with the opposite character + my $ending_index = index($string, $c ^. ' ', $next_starting_index) + 1; + if ($ending_index == 0) { + $never_nice{$c} = 1; + next; + } + + # what we know so far about substrings starting at this starting index + my $substring_prefix = substr $string, $starting_index, $ending_index - $starting_index; + my %nice = my %not_yet_nice = map(($_ => 1), split //, $substring_prefix); + delete @not_yet_nice{map $_ ^. ' ', keys %not_yet_nice}; + delete @nice{keys %not_yet_nice}; + + # found a nice substring? + if (! %not_yet_nice) { + if (length $substring_prefix > length $longest_nice_substring) { + $longest_nice_substring = $substring_prefix; + } + # any nice strings starting in the middle of or just after this nice + # string will also be nice if started at the beginning of it, so + # this iteration of the outer loop will find them and the next + # iteration can be farther on + $next_starting_index = $ending_index + 1; + } + + # look for longer nice substrings starting at this starting index + for my $ending_index ($ending_index..(length($string)-1)) { + $c = substr $string, $ending_index, 1; + + # character we know there's no match for later? + last if $never_nice{$c}; + + # character not yet seen in this substring? + if (! $nice{$c} && ! $not_yet_nice{$c}) { + # completes an upper/lower pair? + my $c_opposite = $c ^. ' '; + if ($not_yet_nice{$c_opposite}) { + delete $not_yet_nice{$c_opposite}; + $nice{$c} = $nice{$c ^. ' '} = 1; + } + else { + $not_yet_nice{$c} = 1; + } + } + if (! %not_yet_nice) { + if ($ending_index - $starting_index >= length $longest_nice_substring) { + $longest_nice_substring = substr $string, $starting_index, $ending_index - $starting_index + 1; + } + # any nice strings starting in the middle of or just after this + # nice string will also be nice if started at the beginning of + # it, so this iteration of the outer loop will find them and the + # next iteration can be farther on + $next_starting_index = $ending_index + 2; + } + } + } + + return $longest_nice_substring +} + diff --git a/challenge-329/ysth/python/ch-2.py b/challenge-329/ysth/python/ch-2.py new file mode 100644 index 0000000000..444e31c8d3 --- /dev/null +++ b/challenge-329/ysth/python/ch-2.py @@ -0,0 +1,113 @@ +import sys +from string import ascii_letters +import random +from enum import IntEnum + +def longest_nice_substring(string: str) -> str: + + # longest nice substring found so far + longest_nice_substring: str = '' + + # characters that we know can't form part of a not yet found nice substring + never_nice: set[str] = set(string) - set(string.swapcase()) + + # loop over starting indexes while it is possible to find a longer nice substring + next_starting_index: int = 0 + while len(string) - next_starting_index > len(longest_nice_substring): + starting_index: int = next_starting_index + c: str = string[starting_index] + next_starting_index += 1 + + # can we rule out any substring starting here? + if c in never_nice: + continue + # shortest substring that may be nice will end with the opposite character + ending_index: int = string.find(c.swapcase(), next_starting_index) + 1 + if ending_index == 0: + never_nice.add(c) + continue + + # what we know so far about substrings starting at this starting index + substring_prefix: str = string[starting_index:ending_index] + nice: set[str] = set(substring_prefix) & set(substring_prefix.swapcase()) + not_yet_nice: set[str] = set(substring_prefix) - nice + + # found a nice substring? + if not not_yet_nice: + if len(substring_prefix) > len(longest_nice_substring): + longest_nice_substring = substring_prefix + # any nice strings starting in the middle of or just after this nice + # string will also be nice if started at the beginning of it, so + # this iteration of the outer loop will find them and the next + # iteration can be farther on + next_starting_index = ending_index + 1 + + # look for longer nice substrings starting at this starting index + for ending_index in range(ending_index, len(string)): + c = string[ending_index] + + # character we know there's no match for later? + if c in never_nice: + break + + # character not yet seen in this substring? + if c not in nice and c not in not_yet_nice: + # completes an upper/lower pair? + c_opposite: str = c.swapcase() + if c_opposite in not_yet_nice: + not_yet_nice.remove(c_opposite) + nice.update(c, c_opposite) + else: + not_yet_nice.add(c) + + # found a nice substring? + if not not_yet_nice: + if ending_index - starting_index >= len(longest_nice_substring): + longest_nice_substring = string[starting_index:ending_index+1] + # any nice strings starting in the middle of or just after this + # nice string will also be nice if started at the beginning of + # it, so this iteration of the outer loop will find them and the + # next iteration can be farther on + next_starting_index = ending_index + 2 + + return longest_nice_substring + +def simple_longest_nice_substring(string: str) -> str: + longest_nice_substring: str = '' + for starting_index in range(0, len(string)): + nice: set[str] = set() + not_yet_nice: set[str] = set() + for ending_index in range(starting_index, len(string)): + c: str = string[ending_index] + if c not in nice and c not in not_yet_nice: + if c.swapcase() in not_yet_nice: + not_yet_nice.remove(c.swapcase()) + nice.update(c, c.swapcase()) + else: + not_yet_nice.add(c) + if not not_yet_nice and ending_index - starting_index + 1 > len(longest_nice_substring): + longest_nice_substring = string[starting_index:ending_index+1] + return longest_nice_substring + +def main() -> None: + inputs: list[str] = sys.argv[1:] + + # if given command line arguments, do those + if len(inputs): + for string in inputs: + print(f'{string:<30} -> {longest_nice_substring(string)}') + + # otherwise, run an endless test of random values, comparing to simple version (stopping if an unexpected difference was found) + else: + checked: int = 0 + while True: + checked += 1 + string = ''.join(random.choice(ascii_letters) for i in range(random.randint(0,200))) + if simple_longest_nice_substring(string) != longest_nice_substring(string): + print(f'string: {string}\nsimple: {simple_longest_nice_substring(string)}\ncomplex: {longest_nice_substring(string)}') + break + if checked % 1000 == 0: + print(f'{checked}', end='\r') + +if __name__ == '__main__': + main() |