# Find the Shortest Swype Path

## Introduction

Lately, I've been getting used to typing with Swype.

I've noticed certain words can be produced by drawing a straight line from your starting letter to your ending letter, or by skipping letters that repeat.

For example, I can type the word balloon by Swyping across the following letters:

b > a > l > o > n.

## Challenge

Let us define the Shortest Swype Path, or SSP, as the minimum number of distinguishable line segments needed to type a string. A line segment is a continuous straight line between any two, or more, letters. Any change in direction starts a new line segment - though some words may be Swyped by drawing only a single straight line.

Use this simple QWERTY keyboard layout:

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


In the above example, the word balloon will have an SSP of 4 as detailed in the sequence below:

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)


The string qwerty has SSP = 1 since no change of direction is required when Swyping this word.

## Input

A single word string containing any a-z via STDIN, function argument, or command line.

## Output

Print via STDOUT, return, or your languages closest alternative, the number n representing the string's SSP.

One trailing newline optional in outut. Standard loopholes disallowed. Shortest submission in bytes wins.

## Notes

• A change in direction starts a new line segment.
• Letters that repeat are only counted once (e.g.: bookkeeper should be treated as bokeper).
• Normally, Swpye corrects missed letters by looking at neighboring letters and filling in its best guess. For this challenge, assume there is no natural language augmentations, predictive text or error correction.
• Uppercase A-Z inputs are treated like their lowercase counterparts.
• Ignore any numbers 0-9 in the input.
• Diagonal paths are allowed - that is, a straight line that covers letters o, k, n, for example, count as 1 segment. This rule applies to any diagonal slope (e.g.: letters c, h, i are in line).

## Examples

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

• h is on the line from c to i, but there are no letters between c and o? – Sparr Jun 11 '15 at 21:43
• If the submissions have to support uppercase letters as well, I suggest including some in the test cases. – Dennis Jun 11 '15 at 22:13
• @Sparr Correct. – CzarMatt Jun 11 '15 at 22:53
• @Dennis Good call - added test cases. – CzarMatt Jun 11 '15 at 22:54
• I do enjoy typing with Swype, but I don't know about programming for the lines... – mbomb007 Jun 12 '15 at 20:39

# CJam, 78767368 62 bytes

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


Note that the code contains unprintable characters.

Borrowing @isaacg's clever idea of using RLE to count the paths saved 6 bytes.

Try it online in the CJam interpreter. If the link doesn't work, copy the code from this paste.

### How it works

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.

• Very clever. Thank you for the explanation. – CzarMatt Jun 12 '15 at 4:47

# Pyth, 5350 49 bytes

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


Keyboard compression format thanks to @Dennis.

This answer contains some unprintable characters. See the links below for the correct code.

Explanation:

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.

• Over 20% shorter! Looking forward to see your explanation. – Dennis Jun 12 '15 at 16:06