Re: [Pharo-users] how to use indexes to copy a substring out of a string

[Richard O'Keefe via Pharo-users]

--- Begin Message ---

Let us approach this as simply as we can.
(1) There are two numbers 1 <= i <= n-3, i+2 <= j <= n-1
    such that (s at: i) = (s at: j) and (s at: i+1) = (s at: j+1)

    Brute force will get us where we want to go:
    String
      hasTwoCharacterNonoverlappingRepeat
        1 to: self size - 3 do: [:i |
          i + 2 to: self size - 1 do: [:j |
            ((self at: i  ) = (self at: j  ) and:
            [(self at: i+1) = (self at: j+1)])
              ifTrue: [^true]]].
        ^false

    This is pretty much how you would do it in C or Java.
    This takes O(n**2) time where n is the size of the string.

    If you want to be *really* clever, you can do something with
    suffix arrays, but if you just want to be a little bit clever,
    you can sort the two-character substrings and their positions
    by just sorting the positions.
    Make an array a of the integers 1..n-1.
    Sort it by viewing each i in the array as the triple
    (s[i],s[i+1],i).  You don't *make* the triples, just do the
    comparisons as if they existed.
    Now a linear scan of the array will find a match if there is one.
    The whole process is O(n.lg n).  It's only worth doing when n is
    large.

(2) Finding xyx.  You did not say whether the middle letter can be the same
    as the outer ones or must be different.  I'm going to suppose that it
    does not matter.

    hasXYX
      3 to: self size do: [:i |
        (self at: i-2) = (self at: i) ifTrue: [^true]].
      ^false

    Again, this is just what you would do in Java or C:
    public static boolean hasXYX(String s) {
        final int n = s.length();
        for (int i = 2; i < n; i++)
            if (s.charAt(i-2) == s.charAt(i)) return true;
        }
        return false;
    }

For what it's worth, in my system this scans a Scrabble dictionary
with 146522 words (1,220,068 bytes), finding 2779 "nice" words,
in 0.18 seconds, so there's not a lot of point in improving it.

In both cases, DON'T copy.  DON'T make substrings.
Just state the problem simply and convert it to obvious code.
Simple boring code is GOOD.


On Sun, 30 Dec 2018 at 05:29, Roelof Wobben <r.wob...@home.nl> wrote:

> Hello,
>
> Still working on AdventOfCode
>
> Im struggeling to see how this can be solved.
>
> Now, a nice string is one with all of the following properties:
>
>    - It contains a pair of any two letters that appears at least twice in
>    the string without overlapping, like xyxy (xy) or aabcdefgaa (aa), but
>    not like aaa (aa, but it overlaps).
>    - It contains at least one letter which repeats with exactly one
>    letter between them, like xyx, abcdefeghi (efe), or even aaa.
>
> my game plan was this
>
> 1) group the characters and filter everything out which has a count not
> equal to two
>
> 2) find the indexes of the characters and with the indexes use a copy
> method so I have a substring out of it
>
> 3) do the same with the substring so again 1 and 2
>
> but how can I make 2 work.
>
> Roelof
>
>
>

--- End Message ---