29
\$\begingroup\$

Most common computer keyboard layouts have the decimal digit keys

1234567890

running along at their top, above the keys for letters.

Let a decimal digit's neighborhood be the set of digits from its own digit key and from the digit keys immediately to the left and right, if they exist.

For example, the neighborhood of 0 is {0, 9}, and the neighborhood of 5 is {4, 5, 6}.

Now, define a keyboard friendly number as a positive integer (in decimal form with no leading zeros) that can be typed on the layout above such that every consecutive digit in the number after the first digit is in the neighborhood of the preceding digit.

  • All single digit numbers (1-9) are trivially keyboard friendly.

  • A number such as 22321 is keyboard friendly because every digit (not counting the first) is in the neighborhood of the digit just before.

  • A number such as 1245 is not keyboard friendly because 4 is not in the neighborhood of 2 (nor vice versa).

  • A number such as 109 is not keyboard friendly because 0 is not in the neighborhood of 1. The ends do not loop around.

By putting the keyboard friendly numbers in order from smallest to largest, we can create an integer sequence.

Here are the first 200 terms of the keyboard friendly numbers sequence:

N KFN(N)
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 11
11 12
12 21
13 22
14 23
15 32
16 33
17 34
18 43
19 44
20 45
21 54
22 55
23 56
24 65
25 66
26 67
27 76
28 77
29 78
30 87
31 88
32 89
33 90
34 98
35 99
36 111
37 112
38 121
39 122
40 123
41 211
42 212
43 221
44 222
45 223
46 232
47 233
48 234
49 321
50 322
51 323
52 332
53 333
54 334
55 343
56 344
57 345
58 432
59 433
60 434
61 443
62 444
63 445
64 454
65 455
66 456
67 543
68 544
69 545
70 554
71 555
72 556
73 565
74 566
75 567
76 654
77 655
78 656
79 665
80 666
81 667
82 676
83 677
84 678
85 765
86 766
87 767
88 776
89 777
90 778
91 787
92 788
93 789
94 876
95 877
96 878
97 887
98 888
99 889
100 890
101 898
102 899
103 900
104 909
105 987
106 988
107 989
108 990
109 998
110 999
111 1111
112 1112
113 1121
114 1122
115 1123
116 1211
117 1212
118 1221
119 1222
120 1223
121 1232
122 1233
123 1234
124 2111
125 2112
126 2121
127 2122
128 2123
129 2211
130 2212
131 2221
132 2222
133 2223
134 2232
135 2233
136 2234
137 2321
138 2322
139 2323
140 2332
141 2333
142 2334
143 2343
144 2344
145 2345
146 3211
147 3212
148 3221
149 3222
150 3223
151 3232
152 3233
153 3234
154 3321
155 3322
156 3323
157 3332
158 3333
159 3334
160 3343
161 3344
162 3345
163 3432
164 3433
165 3434
166 3443
167 3444
168 3445
169 3454
170 3455
171 3456
172 4321
173 4322
174 4323
175 4332
176 4333
177 4334
178 4343
179 4344
180 4345
181 4432
182 4433
183 4434
184 4443
185 4444
186 4445
187 4454
188 4455
189 4456
190 4543
191 4544
192 4545
193 4554
194 4555
195 4556
196 4565
197 4566
198 4567
199 5432
200 5433

Challenge

Write a program or function that takes a positive integer N (via stdin/command line/function arg) and prints (to stdout) or returns the Nth term in the keyboard friendly numbers sequence.

For example, if the input is 191, the output should be 4544.

The output may optionally have a single trailing newline.

The shortest submission in bytes wins.

\$\endgroup\$
  • 7
    \$\begingroup\$ Random fact: OEIS has a related sequence for numpads \$\endgroup\$ – Sp3000 May 12 '15 at 7:36
  • \$\begingroup\$ Thanks, @Sp3000. I scrolled down to here wondering that very thing. \$\endgroup\$ – luser droog May 14 '15 at 10:09

13 Answers 13

8
\$\begingroup\$

Pyth, 27 24 bytes

uf!f/h-FY3.:metsd`T2hGQ0

Demonstration.

Improvements to the original:

  • Using metd, instead of .r ... _UJ: 2 less bytes. 1 direct, 1 for not having to use J.

  • Using s and `T instead of JT10: 1 less byte.


We start with the string representation of a number: `T.

Then, we convert the string to a list of digits, and rotate the digits digits backwards by one, (9876543210) with metsd. Then, we take the 2 element subsequences with .: ... 2. These subsequences are filtered on /h-FY3. This expression corresponds to ((a-b)+1)/3, which is zero if and only if the difference between a and b is at most 1. Thus, the filtered list will be empty if and only if the number is keyboard friendly. With !, the result is true only if the number is keyboard friendly.

f ... hG filters upwards from G+1 until the result is true, giving the first keyboard friendly number at G+1 or above. u ... Q0 applies this function to its own output Q times, starting from 0, where Q is the input. This gives the Qth Keyboard Friendly Number, as desired.

\$\endgroup\$
4
\$\begingroup\$

Python 3, 112 102 bytes

f=lambda n,k=0:n+1and f(n-all(-2<~-int(a)%10-~-int(b)%10<2for a,b in zip(str(k),str(k)[1:])),k+1)or~-k

We keep track of the count of friendly numbers still needed to find in n and the last checked number in k.

5 and 5 bytes saved thanks to @isaacg and @Sp3000.

\$\endgroup\$
  • \$\begingroup\$ Use a lamba expression instead of a def return. Lambas allow defaults. \$\endgroup\$ – isaacg May 12 '15 at 7:28
  • \$\begingroup\$ @isaacg Thanks, I didn't know how to recurse with lambda. \$\endgroup\$ – randomra May 12 '15 at 7:33
  • \$\begingroup\$ Ah right. Unary ops come first. My mistake. \$\endgroup\$ – mbomb007 May 12 '15 at 19:28
  • \$\begingroup\$ You can drop the [:-1] in the zip \$\endgroup\$ – Sp3000 May 13 '15 at 1:01
4
\$\begingroup\$

CJam, 29 28 bytes

ri_4#{AbAfe|_1>.-W<3,:(-!},=

Try it online in the CJam interpreter.

\$\endgroup\$
  • \$\begingroup\$ Is there an easy proof that the upper limit of N-th friendly number is N**2 \$\endgroup\$ – Optimizer May 13 '15 at 11:18
  • \$\begingroup\$ Haven't found one yet. The proof for N ** 4 is pretty easy, since there are at least 2 ** k KFN below 10 ** k < 16 ** k. Replacing _* with 4# wouldn't alter the byte count, but it would make the code horribly inefficient. \$\endgroup\$ – Dennis May 13 '15 at 12:53
  • \$\begingroup\$ Then isn't your code incorrect for some large input number ? \$\endgroup\$ – Optimizer May 13 '15 at 12:56
  • 1
    \$\begingroup\$ Hopefully not. But I'll change it until I know. grumbles \$\endgroup\$ – Dennis May 13 '15 at 12:58
3
\$\begingroup\$

CJam, 34 31 bytes

3 bytes saved by Dennis.

I'm sure the gap to Pyth can be closed somehow, but I don't have time right now to golf this further...

0q~{{)_s:_2ew{A,s(+f#~m2/},}g}*

Test it here.

\$\endgroup\$
  • \$\begingroup\$ You can replace )_++ with :_ to save 2 chars and -z1> with m2/ to save another. \$\endgroup\$ – Dennis May 12 '15 at 20:35
  • \$\begingroup\$ @Dennis Oh, those are nice, thank you! \$\endgroup\$ – Martin Ender May 12 '15 at 20:48
3
\$\begingroup\$

JavaScript (ES6), 95

F=k=>{for(i=0;k;k-=(f=1,p=NaN,[for(d of''+i)(d=(8-~d)%10,d-p>1|p-d>1?f=0:p=d)],f))++i;return i}

Ungolfed

F=k=>{
  for(i=0; k>0; )
  {
    ++i;
    f = 1; // presume i it's friendly
    p = NaN; // initial value so that first comparison gives false
    for(d of ''+i) // loop for each digit of i
    {
      // rotate digits 1->0, 2->1 ... 9->8, 0->9
      // note d is string, ~~ convert to number (golfed: 8-~d)
      d = (~~d+9) % 10 
      if (p-d>1 || p-d<-1) 
        f = 0 // not friendly
      else 
        // this can go in the 'else', if not friendly I don't care anymore
        p = d // move current digit to prev digit
    }
    k -= f // count if it's friendly, else skip
  }
  return i
}

Test : execute snippet in Firefox

F=k=>{
  for(i=0;k;k-=(f=1,p=NaN,[for(d of''+i)(d=(8-~d)%10,d-p>1|p-d>1?f=0:p=d)],f))++i
  return i
}
<input id=N><button onclick="R.value=F(N.value)">-></button><input readonly id=R>

\$\endgroup\$
  • \$\begingroup\$ I don't know much JS, but couldn't you do something like abs(p-d)>1 rather than p-d>1|p-d<-1? \$\endgroup\$ – Alex A. May 14 '15 at 20:09
  • \$\begingroup\$ @AlexA. The expressions in expanded and golfed are equivalent. Math.abs(p-d)>1 is longer than p-d>1|p-d<-1 \$\endgroup\$ – edc65 May 14 '15 at 20:14
  • \$\begingroup\$ Ah, okay. I knew they were equivalent, I just didn't know that you needed the Math. prefix. \$\endgroup\$ – Alex A. May 14 '15 at 20:15
2
\$\begingroup\$

Haskell, 90 80 bytes

([x|x<-[0..],all((<2).abs)$zipWith(-)=<<tail$[mod(1+fromEnum c)10|c<-show x]]!!) 

This is a function without a name. To use it, call it with a parameter, e.g.:([x|x<-[0..],all((<2).abs)$zipWith(-)=<<tail$[mod(1+fromEnum c)10|c<-show x]]!!) 199 which returns 5432.

How it works:

[x|x<-[0..]           ]  make a list of all integers x starting with 0
           ,             where
             c<-show x   each character in the string representation of x
  mod(1+fromEnum c)10    turned into the number '(ascii+1) mod 10'
 zipWith(-)=<<tail       then turned into a list of differences between neighbor elements
all((<2).abs)            only contains elements with an absolute value less than 2


                   !!    ... take the element given by the parameter (!! is 0 
                         based, that's why I'm starting the initial list with 0)

Edit: @Mauris found some bytes to save. Thanks!

\$\endgroup\$
  • \$\begingroup\$ Instead of x<-[1..] ... !!n-1, you can do x<-[0..] ... !!n. \$\endgroup\$ – Lynn May 15 '15 at 12:50
  • \$\begingroup\$ And then of course f n=[...]!!n can be f=([...]!!). \$\endgroup\$ – Lynn May 15 '15 at 12:55
  • \$\begingroup\$ I got it down to a single function, eliminating a: f=([x|x<-[0..],all((<2).abs)$zipWith(-)=<<tail$[mod(1+fromEnum c)10|c<-show x]]!!) \$\endgroup\$ – Lynn May 15 '15 at 13:12
  • \$\begingroup\$ @Mauris: wow, thank you! Without a we can eliminate f, too. \$\endgroup\$ – nimi May 15 '15 at 15:54
2
\$\begingroup\$

Dart, 92 bytes

f(n,[x=0]){t(x)=>x>9?((x+9)%10-((x~/=10)+9)%10).abs()>1||t(x):--n>0;while(t(++x));return x;}

With linebreaks:

f(n,[x=0]){
  t(x)=>x>9?((x+9)%10-((x~/=10)+9)%10).abs()>1||t(x):--n>0;
  while(t(++x));  
  return x;
}

See/run it on DartPad

\$\endgroup\$
1
\$\begingroup\$

Batch - 520 Bytes

Shudder.

@echo off&setLocal enableDelayedExpansion&set a=0&set b=0
:a
set/ab+=1&set l=0&set c=%b%
:b
if defined c set/Al+=1&set "c=%c:~1%"&goto b
set/am=l-2&set f=0&for /l %%a in (0,1,%m%)do (
set x=!b:~%%a,1!&set/an=%%a+1&for %%b in (!n!)do set y=!b:~%%b,1!
set z=0&set/ad=x-1&set/ae=x+1&if !e!==10 set e=0
if !d!==-1 set d=9
if !y!==!d! set z=1
if !y!==!e! set z=1
if !y!==!x! set z=1
if !y!==0 if !x!==1 set z=0
if !y!==1 if !x!==0 set z=0
if !z!==0 set f=1)
if !f!==0 set/aa+=1
if %a% NEQ %1 goto :a
echo %b%
\$\endgroup\$
1
\$\begingroup\$

Bash + coreutils, 120 bytes

seq $1$1|tr 1-90 0-9|sed 's#.#-&)%B)/3)||(((C+&#g;s/^/(0*((/;s/$/))*0)/'|bc|nl -nln|sed '/1$/d;s/   0//'|sed -n "$1{p;q}"

Some testcases:

$ for i in 1 10 11 99 100 200; do ./kfn.sh $i; done
1     
11    
12    
889   
890   
5433  
$ 
\$\endgroup\$
0
\$\begingroup\$

JavaScript ES6, 126 bytes

f=n=>{b=s=>[...++s+''].every((e,i,a,p=(+a[i-1]+9)%10)=>i?p==(e=+e?e-1:9)|p-e==1|e-p==1:1)?s:b(s)
for(p=0;n--;)p=b(p)
return p}

Ungolfed code and tests below. This could certainly be improved more.

f=function(n){
  b=function(s){
    return (s+'').split('').every(function(e,i,a){
      e=+e?e-1:9
      p=i?(+a[i-1]+9)%10:e
      return p==e|p-e==1|e-p==1
    })?s:b(s+1)
  }
  for(p=i=0;i<n;i++){
    p=b(p+1)
  }
  return p
}

var input = document.getElementById('n'), results = [];
input.onchange = function(){
  document.getElementById('s').innerHTML = f(input.value)
}
for(var i=0;i<200;i++){
  results.push(i + ':&nbsp;' + f(i))
}
document.getElementById('r').innerHTML=results.join('<br />')
N = <input type="number" id="n" min="1" value="191" /><br />
KBD(N) = <samp id="s">4544</samp>
<div id="r"></div>

\$\endgroup\$
0
\$\begingroup\$

Cobra - 135

Haven't done this in a while, but here goes:

def f(n,i=0)
    while n,if all for x in (s='[i+=1]').length-1get s[x+1]in' 1234567890'[(int.parse(s[x:x+1])+9)%10:][:3],n-=1
    print i

Ungolfed:

def fn(n as int)
    i = 0
    while n <> 0
        i += 1
        s = i.toString
        l = s.length - 1
        v = true
        for x in l
            k = (int.parse(s[x].toString) + 9) % 10
            if s[x + 1] not in ' 1234567890'[k : k + 3], v = false
        if v, n -= 1
    print i
\$\endgroup\$
0
\$\begingroup\$

Jelly, 11 bytes

Do⁵IỊẠ
1Ç#Ṫ

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Pyth, 19 bytes

e.f.AgL1.aM.+|RTjZT

Try it here.

Note: Uses commit newer than this challenge, so shouldn't be considered as an outgolf of isaacg's answer. This is still competing, though.

\$\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.