32
\$\begingroup\$

The puzzle:

Consider a console/hand-held game with a d-pad where you are required to enter a name of sorts. This appeared in many older games before the use of QWERTY was popularised in consoles (e.g. I believe the Wii uses a QWERTY keyboard layout for input). Typically, the on-screen keyboard looks to the effect of*:

Default:

0 1 2 3 4 5 6 7 8 9
A B C D E F G H I J
K L M N O P Q R S T
U V W X Y Z _ + ^ =

With the case switched:

0 1 2 3 4 5 6 7 8 9
a b c d e f g h i j
k l m n o p q r s t
u v w x y z - + ^ =

That is, all alphanumeric keys and the following:

_: A single space
-: A hyphen
+: Switch case for the next letter only
^: Toggle caps lock (that is, switch the case of all letters)
=: Enter, complete

*Obviously I replaced keys like "BKSP" and "ENTER" with shorter versions

And then the hardware would include a d-pad (or some form of control where you could go up, down, left and right)

The screen also typically let you move from one side directly to the other. That is, if you were focussed on the letter J, pressing right would allow you to move to the letter A.

Whenever I was entering my name, I'd always try to work out the quickest way to do so.

Goal:

Your program will take string input which may include any alphanumeric character including a space and hyphen, and your goal is to output the shortest amount of key presses on the d-pad to output the required string.

Considerations:

You do not need to include the key pressed for pressing the actual character.
Focus always starts at the A
Enter = must be pressed at the end

Example:

input: Code Golf
output: 43

Explained:
A -> C = 2
C -> ^ = 6 (moving to the left)
^ -> o = 5
o -> d = 2
d -> e = 1
e -> + = 5
+ -> _ = 1
_ -> + = 1
+ -> G = 3
G -> o = 3
o -> l = 3
l -> f = 5
f -> = = 6

Note that it is quicker to hit the + twice for a _ and a G than it is to hit ^ once, then swap back.

The winning submission (I'll allow at least 1w) will be the shortest solution (in bytes). As this is my first question, I hope this is clear and not too hard.

\$\endgroup\$
  • 12
    \$\begingroup\$ Nice challenge! Just one point, 48 hours is probably too little. That's how long it takes for bounties to be allowed, so it should be more around a week+. \$\endgroup\$ – Maltysen Jul 26 '15 at 3:20
  • \$\begingroup\$ @Maltysen thanks for the suggestion, I've updated the challenge \$\endgroup\$ – Tas Jul 26 '15 at 3:44
  • 1
    \$\begingroup\$ Can you wrap vertically, too, or just horizontally? \$\endgroup\$ – Alex Reinking Jul 31 '15 at 23:49
  • 2
    \$\begingroup\$ @AlexReinking that's a great point! Yes you can. \$\endgroup\$ – Tas Aug 1 '15 at 1:45
  • \$\begingroup\$ Great! My implementation does that, so I just wanted to double-check. \$\endgroup\$ – Alex Reinking Aug 1 '15 at 1:54
5
\$\begingroup\$

Ruby (369 bytes)

Takes input from command line.

K="0123456789"+('A'..'Z').to_a.join+" +^="
Q=K.downcase.sub' ','-'
def d x,y
t,s=(x/10-y/10).abs,(x%10-y%10).abs
[t,4-t].min+[s,10-s].min
end
def v s,i,l,a
return l if s.empty?
c,r=s[0],s[1..-1]
j=K.index(c.upcase)||36
return v(r,j,l+d(i,j),a)if a.include?c
s,p=d(i,37)+d(37,j),d(i,38)+d(38,j)
[v(r,j,l+s,a),v(r,j,l+p,a==K ? Q : K)].min
end
puts v("#{ARGV[0]}=",10,0,K)

Saved a bunch of bytes thanks to @Charlie :)

\$\endgroup\$
  • \$\begingroup\$ j=(K.index(c.upcase) or 36) can be replaced with j=K.index(c.upcase)||36 to save 4 bytes. def d(x,y) can replaced with def d x,y to save a byte, and same goes for def v. v(...) if to v(...)if for another byte. On the last line, v(...) can be replaced with v ... to save 1 byte, and true with !!0 to save another byte. \$\endgroup\$ – Charlie Aug 2 '15 at 20:52
  • \$\begingroup\$ Thanks! I don't really know Ruby. I translated this from python... \$\endgroup\$ – Alex Reinking Aug 2 '15 at 23:59
  • \$\begingroup\$ I can also replace && with & and || with |. \$\endgroup\$ – Alex Reinking Aug 3 '15 at 0:04
  • \$\begingroup\$ Your first line (K=...) can be replaced with a range (K='0123456789'+('A'..'Z').to_a.join+' +^=') \$\endgroup\$ – Charlie Aug 3 '15 at 22:04
  • \$\begingroup\$ Shaves another 2 off! \$\endgroup\$ – Alex Reinking Aug 3 '15 at 22:42
9
+100
\$\begingroup\$

Swift 1.2, 812 588 670 bytes

Edit: Removed 224 bytes by replacing the large arrays of numbers with a Range and converting it to an Array instead.

Edit2: Added looping vertically

typealias S=String
typealias I=Int
var A:(I)->S={S(UnicodeScalar($0))},B:(I)->(I,I)={a in(a%10,a/10)},a=Array(48...57).map{A($0)},b=[a+(Array(65...90)+[32,43,94,61]).map{A($0)},a+(Array(97...122)+[45,43,94,61]).map{A($0)}],z=Process.arguments
z.removeAtIndex(0)
func C(e:I,f:I)->I{let(a,b)=B(e),(c,d)=B(f)
return min(abs(d-b), abs(4-(d-b)))+min(abs(c-a),abs(10-(c-a)))}
func D(c:S,_ e:I=10,_ f:Bool=false,_ g:Bool=false)->I{if count(c)==0{return C(e,39)}
let h=c.startIndex,i=c.endIndex,j=S(c[h])
if let k=find(b[f ?1:0],j){return C(e,k)+D(c[advance(h,1)..<i],k,(g ?(!f):f),false)}else{return min(C(e,37)+D(c,37,!f,true),C(e,38)+D(c,38,!f,false))}}
print(D(" ".join(z)))

To run, put the code in a .swift file and run it with swift <filename> <your name>


This uses the simple approach where the two 'keyboards' are stored as arrays.

B:(I)->(I,I)={a in(a%10,a/10)} Converts an index from the array to an x,y position on the virtual keyboard.

func C(e:I,f:I)->I{let(a,b)=B(e),(c,d)=B(f) return abs(d-b)+min(abs(c-a),abs(10-(c-a)))} Takes a start/end index and returns the minimum number of moves to get from once to the other (accounting for horizontal wrap)

func D(c:S,_ e:I=10,_ f:Bool=false,_ g:Bool=false)->I Is the main recursive function that does most of the calculations. It calculates the distance from the current position to the target character, unless the case should change, then it calculates both the shift and the caps lock methods and takes the smallest.

Running swift codegolf.swift Code Golf prints 43

\$\endgroup\$
  • \$\begingroup\$ Needs to account for vertical wrap. \$\endgroup\$ – Alex Reinking Aug 1 '15 at 1:54
  • \$\begingroup\$ Updated to account for vertical wrap too. \$\endgroup\$ – David Skrundz Aug 1 '15 at 6:51
4
\$\begingroup\$

Python 679 661 619 602 589 576 539 520 496 482 Bytes

Run this and it will ask for a input (without prompt text). For the input Code Golf it prints 43.

a=input()+'=';b=0;c="0123456789abcdefghijklmnopqrstuvwxyz-+^=";d=0;e=[0,1];f='+';g='^';h=[i.isupper()or i==' 'for i in a];i=abs;p=lambda z:all([i==b for i in z]);q=0
def l(z):global s;k=c.index(z.lower().replace(' ','-'));s=[k%10,int(k/10)];m,n=s;return sum([min(i(m-e[0]),i(10-(m-e[0]))),min(i(n-e[1]),i(4-(n-e[1])))])
def o(z):global d,e;d+=l(z);e=s
for r in a:
 if p(h[q:q+3]):o(g);b^=1
 if p(h[q:q+2]):
  if l(f)<l(g):o(f)
  else:o(g);b^=1
 if p([h[q]]):o(f)
 o(r);q+=1
print(d)

Full program:

input = input() + '='
capsOn = False

keys = "0123456789abcdefghijklmnopqrstuvwxyz-+^="
totalKeys = 0
caret = [0, 1]

shiftKey = '+'
capsKey = '^'

cases = [char.isupper() or char == ' ' for char in input]

def locate(char):
    """
        Find the location of the char on the keyboard
        regardless of case
    """
    location = keys.find(char.replace(' ', '-').lower())
    return [location % 10, int(location / 10)]


def dist(key):
    """
        Calculate the min dist to a char
    """
    nx, ny = locate(key)
    return sum([min(abs(nx - caret[0]), abs(10 - (nx - caret[0]))), min(abs(ny - caret[1]), abs(4 - (ny - caret[1])))])


def moveTo(char):
    """
        Move the caret to the char, ignoring case and
        adds the dist to the tally
    """
    global totalKeys, caret
    totalKeys = totalKeys + dist(char)

    print(keys[caret[0] + caret[1] * 10], '->', char, '=', dist(char))

    caret = locate(char)

diffCase = lambda case: all([i == capsOn for i in case])

for ind, ch in enumerate(input):
    if diffCase(cases[ind:ind + 3]): # use caps
        moveTo(capsKey)
        capsOn ^= 1
    elif diffCase(cases[ind:ind + 2]): # use closest
        if dist(shiftKey) < dist(capsKey):
            moveTo(shiftKey)
        else:
            moveTo(capsKey)
            capsOn ^= 1
    elif diffCase([cases[ind]]): # use shift
        moveTo(shiftKey)

    moveTo(ch) # apply the move

print('Total:', totalKeys)

Extended output from the full program:

Code Golf
a -> C = 2
c -> ^ = 6
^ -> o = 5
o -> d = 2
d -> e = 1
e -> + = 5
+ -> _ = 1
- -> + = 1
+ -> G = 3
g -> o = 3
o -> l = 3
l -> f = 5
f -> = = 6
Total: 43

Saved a byte thanks to @justin https://codegolf.stackexchange.com/a/18983/42736
4 @xnor https://codegolf.stackexchange.com/a/40791/42736 19 thanks to @Alex

\$\endgroup\$
  • \$\begingroup\$ Any help is appreciated as I'm still learning python and this is my first code golf. \$\endgroup\$ – J Atkin Jul 31 '15 at 16:07
  • \$\begingroup\$ You can use a space instead of an underscore in your internal tables. \$\endgroup\$ – Alex Reinking Aug 1 '15 at 0:55
  • \$\begingroup\$ I hadn't thought of that, thanks ;) \$\endgroup\$ – J Atkin Aug 1 '15 at 2:06
3
\$\begingroup\$

C 675 Bytes

Takes input from command line argument. Uses recursive main:

#define Y(_) (!isdigit(_)?!isalpha(_)?3:1+(toupper(_)-65)/10:0)
#define X(_) (!isdigit(_)?!isalpha(_)?_-32&&_-45?_-43?9-(_==94):7:6:(toupper(_)-5)%10:_-48)
x,y,z;char*s;main(a,_,p,q,r){a<2?s[_]?!isdigit(s[_])&&((s[_]-32&&!isupper(s[_]))||!a)&&((s[_]-45&&!islower(s[_]))||a)?q=x,r=y,main(3,43),p=z,x=X(43),y=Y(43),main(3,s[_]),p+=z,x=X(s[_]),y=Y(s[_]),main(a,_+1),p+=z,x=q,y=r,main(3,94),q=z,x=X(94),y=Y(94),main(3,s[_]),q+=z,x=X(s[_]),y=Y(s[_]),main(!a,_+1),q+=z,z=(q<p?q:p):(main(3,s[_]),q=z,x=X(s[_]),y=Y(s[_]),main(a,_+1),z+=q):(main(3,61)):(a<3?s=((char**)_)[1],x=0,y=1,main(1,0),printf("%d",z):(x=X(_)-x,y=Y(_)-y,x+=10*(x<0),y+=4*(y<0),z=(x>5?10-x:x)+(y>2?4-y:y)));}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.