Wprowadzenie

Ostatnio przyzwyczaiłem się do pisania na Swype .

Zauważyłem, że niektóre słowa można wytworzyć, rysując prostą linię od litery początkowej do litery końcowej lub pomijając powtarzające się litery.

Na przykład mogę wpisać słowo balloon, przesuwając między następującymi literami:

b> a> l> o> n.

Wyzwanie

Zdefiniujmy Najkrótszą Ścieżkę Swype lub SSP, jako minimalną liczbę możliwych do odróżnienia segmentów linii potrzebną do wpisania łańcucha. Segment linii jest ciągłą linią prostą między dowolnymi dwiema lub więcej literami. Każda zmiana kierunku rozpoczyna nowy segment linii - choć niektóre słowa można przesuwać, rysując tylko jedną linię prostą.

Użyj tego prostego układu klawiatury QWERTY :

q w e r t y u i o p
a s d f g h j k l
  z x c v b n m

W powyższym przykładzie, słowo balloonbędzie mieć SSPod 4jak wyszczególniono w poniższej kolejności:

1) Start at `b` (line segments = 0)
2) slide to `a` (line segments = 1)
3) slide to `l` (line segments = 2)
4) slide to `o` (line segments = 3)
5) slide to `n` (line segments = 4)

Łańcuch qwertyma SSP= 1, ponieważ podczas przesuwania tego słowa nie jest wymagana zmiana kierunku.

Wejście

Ciąg jednego słowa zawierający dowolny parametr a-zSTDIN, argument funkcji lub wiersz poleceń.

Wynik

Drukuj przez STDOUT, return lub w najbliższych językach, liczba nreprezentująca ciąg SSP.

Jeden końcowy nowy wiersz jest opcjonalny w outut. Standardowe luki zabronione. Najkrótsze przesłanie w bajtach wygrywa.

Notatki

• Zmiana kierunku rozpoczyna nowy segment linii.
• Powtarzające się litery są liczone tylko raz (np .: bookkeeperpowinny być traktowane jak bokeper).
• Zwykle Swpye koryguje brakujące litery, patrząc na sąsiednie litery i wypełniając swoje najlepsze domysły. W przypadku tego wyzwania załóżmy, że nie ma żadnych rozszerzeń języka naturalnego, tekstu predykcyjnego ani korekcji błędów.
• Wielkie A-Zlitery są traktowane jak ich małe odpowiedniki.
• Zignoruj ​​dowolne liczby 0-9na wejściu.
• Ukośne ścieżki mogą - to jest linia prosta, która obejmuje litery o, k, nna przykład, liczone jako 1segment. Zasada ta dotyczy wszelkich nachylenia przekątnej (np liter c, h, isą zgodne).

Przykłady

Input          Output
---------------------
a                0
aa               0
aaaaaa           0
aaaaaabc         2
in               1
int              2
java             3
qwerty           1
chicago          5
balloon          4
BALLOON          4
typewriter       5
bookkeeper       6
stackexchange    11
2hello7          3
2HELLO7          3

CJam, 78 76 73 68 62 bajtów

relA,s-:_2ew{:-},{{i"x8LÑejPG ÀÏi"225b28b=A+Ab}/.-:ma}%e`,

Pamiętaj, że kod zawiera znaki niedrukowalne.

Sprytna idea pożyczania @ isaacg, polegająca na użyciu RLE do zliczania ścieżek zapisanych 6 bajtów.

Wypróbuj online w interpretatorze CJam . Jeśli link nie działa, skopiuj kod z tej pasty .

Jak to działa

rel      e# Read a token from STDIN and cast it to lowercase.
A,s-     e# Remove all digits.
:_       e# Duplicate each element of the argument (string/array).
2ew      e# Push all overlapping slices of length 2.
{:-},    e# Filter out slices where both elements are equal.
{        e# For each slice:
  {      e#   For each character of the slice:
    i    e#     Push its code point.

    "x8LÑejPG ÀÏi"225b28b

         e#     Convert the string from base 225 to base 28, pushing the array
         e#     [15 7 16 17 18 27 26 8 9 0 3 11 4 6 24 1 22 5 21 10 25 23 12 2 13 14].
         e#     These are the positions on the QWERTY keyboard, starting from the
         e#     upper left corner and going right.

    =    e#     Select the element that corresponds to the code point.

         e#     Arrays wrap around in CJam. Since 'a' has code point 97, the array has
         e#     length 26 and 97 % 26 == 19, 'a' corresponds to the 20th element.

    A+Ab e#     Add 10 and convert to base 10. Example: 8 -> [1 8]
  }/     e#
  .-     e#     Vectorized subtraction. [a b] [c d] -> [a-c b-d]
  :ma    e#     atan2. Pushes the angle of the direction. [y x] -> arctan(y/x)
}%       e#
e`       e# Apply run-length encoding.
,        e# Count the runs.

Pyth, 53 50 49 bajtów

lrPMfT-VJm.jF.D@jC"XÖ;¿ìÇ×;¤ð$  _"28CdT@GrzZtJ8

Format kompresji klawiatury dzięki @Dennis.

Ta odpowiedź zawiera niektóre niedrukowalne znaki. Prawidłowy kod znajduje się w poniższych linkach.

Demonstracja . Uprząż testowa.

Wyjaśnienie:

lrPMfT-VJm.jF.D@jC"..."28CdT@GrzZtJ8
                              rzZ      Convert input to lowercase.
                            @G         Take the intersection with G.
                                       This removes the numbers.
         m                             Map over the characters
                 C"..."                Treat the string as a base 256 number.
                j      28              Convert this number to base 28, giving:
                                       [15, 7, 16, 17, 18, 27, 26,  ... ]
                                       which is the character positions 
                                       from top left, rotated by 97 places.
               @         Cd            Index this list by ord(character)
             .D            T           divmod by 10, giving the x-y position.
          .jF                          Convert this to a complex number.
        J                              Save the result to J.
      -VJ                        tJ    Vectorize - over J and J[1:]. This gives
                                       pairwise diffeences between J's elements.
    fT                                 Filter the differences on being truthy.
                                       This removes letter pairs with no movement.
  PM                                   Map the remaining complex numbers to their
                                       phases, which indicates their directions.
 r                                 8   Run-length encode the result.
l                                      Print out the number of separate RLE groups.