perlweeklychallenge-club/challenge-329/ysth/perl/ch-2.pl at challenge-329-ysth · ysth/perlweeklychallenge-club · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
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
}