Generate Numpad-Friendly Numbers

Question

Inspired by Generate Keyboard Friendly Numbers.

Background

Many number pads have the following layout:

789

456

123

0

We define a number's neighborhood as the set of cells orthogonally adjacent to it on the numpad shown, including itself. For example, 2's neighborhood is {1,5,3,0,2} and 0's neighborhood is {1,2,0}. There is a list of each number's neighborhood below, above test cases.

We define a numpad friendly number as a positive integer where, when written in decimal without leading zeroes, each digit except for the first is in the neighborhood of the previous digit.

For example,

• 7856 is a numpad friendly number because 8 is in the neighborhood of 7, 5 is in the neighborhoood of 8, and 6 is in the neighborhood of 5.
• 1201 is a numpad friendly number because 2 is in the neighborhood of 1, 0 is in the neighborhood of 2, and 1 is in the neighborhood of 0.
• 82 is not a numpad friendly number because 2 is not in the neighborhood of 8.
• 802 is not a numpad friendly number because 0 is not in the neighborhood of 8 (neighborhoods don't wrap around).

Related OEIS Sequence. Note that this related sequence is distinct because it counts 0 as adjacent to 7 instead of 1 and 2.

Challenge

Given a positive integer n, return the n-th or the first n numpad friendly numbers, where the first is 1. You may use 0-based indexing, where the 0-th numpad friendly number would be 1.

Neighborhoods

Each digits's neighborhood is listed here:

0:{0,1,2}
1:{0,1,2,4}
2:{0,1,2,3,5}
3:{2,3,6}
4:{1,4,5,7}
5:{2,4,5,6,8}
6:{3,5,6,9}
7:{4,7,8}
8:{5,7,8,9}
9:{6,8,9}

Test Cases / Sequence

These are the first 100 terms

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 20, 21, 22, 23, 25, 32, 33, 36, 41, 44, 45, 47, 52, 54, 55, 56, 58, 63, 65, 66, 69, 74, 77, 78, 85, 87, 88, 89, 96, 98, 99, 100, 101, 102, 110, 111, 112, 114, 120, 121, 122, 123, 125, 141, 144, 145, 147, 200, 201, 202, 210, 211, 212, 214, 220, 221, 222, 223, 225, 232, 233, 236, 252, 254, 255, 256, 258, 320, 321, 322, 323, 325, 332, 333, 336, 363, 365, 366, 369, 410, 411, 412, 414, 441, 444, 445, 447]

• Luis Mendo: I like how this challenge only considers positive integers (which keeps the essence and allows more languages to participate) and allows displaying either the n-th or the first n outputs for flexibility
• Magic Octopus Urn: I completely misread the challenge, here's an "is this term valid in the sequence" script: Try it online!

Answer 1

JavaScript (ES6), (削除) 104 (削除ここまで) (削除) 93 (削除ここまで) (削除) 89 (削除ここまで) 88 bytes

Returns the N-th term of the sequence, 1-indexed.

f=(i,k,n=k,N=n/5>>1)=>(N?8530025>>(n%10*6191^N%10*6191)%26&1:!i--)?N?f(i,k,N):k:f(i,-~k)

Demo

f=(i,k,n=k,N=n/5>>1)=>(N?8530025>>(n%10*6191^N%10*6191)%26&1:!i--)?N?f(i,k,N):k:f(i,-~k)
for(n = 1; n <= 50; n++) {
 console.log('a(' + n + ') = ' + f(n))
}

• Conor O'Brien: Best I could get is 151 k=(n,a=1)=>n?k(n-([...(x=a+[]).slice(0,-1)].reduce((a,c)=>a*!!~"012 0124 01235 236 1457 24568 3569 478 5789 689".split` `[c].indexOf(x[i++]),i=1)),a+1):a-1 maybe something there helps, my test is probably too long
• scottinet: This answer brings the concept of magic numbers to a whole new level... I don't even understand how you found them o_O
• Arnauld: @scottinet To a large extent, my explanation for this answer applies to this one as well. The absolute difference didn't work very well on that one, so I tried with XOR instead. As a side note, I found another formula that worked in 96% of cases without the need for a lookup bitmask. But processing the remaining 4% separately was too costly in JS. I didn't try in Jelly, and now I don't remember the formula anyway... ¯\_(ツ)_/¯
• scottinet: Thanks for the explanations. This is still impressive :-)

Answer 2

Perl 5, 123 + 1 (-p) = 124 bytes

while($_){$r=@d=++$\=~/./g;map$r&&=(120,1240,12350,236,1457,24568,3569,478,5789,689)[$d[$_-1]]=~/$d[$_]/,1..$#d;$r&&$_--}}{

Try it online!

Answer 3

Jelly, (削除) 27 (削除ここまで) 24 bytes

Returns the N first terms of the sequence.

D(×ばつ^2\%26"7wð’æ»ḂẠ
1Ç#

Try it online!

This is a port of my JS answer.

D(×ばつ^2\%26"7wð’æ»ḂẠ - helper link: test numpad-friendliness of a number, e.g. 1257
D - get decimal digits -> [1, 2, 5, 7]
 ×ばつ - multiply by ...
 (ÞȦ - ... the integer 6191 -> [6191, 12382, 30955, 43337]
 ^2\ - bitwise XOR overlapping reduce -> [10353, 18613, 53666]
 %26 - modulo 26 -> [5, 23, 2]
 æ» - right-shift by each value ...
 "7wð’ - ... the integer 8530025 -> [266563, 1, 2132506]
 Ḃ - isolate the LSB -> [1, 1, 0] which means that 1->2
 and 2->5 are OK and 5->7 is not
 Ạ - all (0 if there's any 0) -> 0, i.e. not numpad-friendly :'(
1Ç# - main link: return the [input] first matching numbers,
 using our helper link as a monad and starting with 1

Answer 4

05AB1E, (削除) 24 (削除ここまで) 23 bytes

μNSü‚εW_iO<ë<3BÆ}ÄR2‹}P

Try it online!

Returns the nth number in the sequence.

Explanations:

μNSü‚εW_iO<ë<3BÆ}ÄR2‹}P Full program
μ Until counter is equal to input
 N Push current iteration number (e.g. 1025)
 S Split to a list of chars (-> ['1', '0', '2', '5'])
 ü‚ Group into pairs (-> ['1', '0'], ['0', '2'], ['2', '5'])
 ε For each pair
 W_ Is smallest digit equal to 0?
 iO< True: sum all digits and decrement 
 ë False: 
 < - decrement all digits
 3B - convert to base 3
 Æ - reduced substraction
 } End if
 Ä Absolute value
 R Reverse 
 2‹ 1 if result is < 2, 0 otherwise
 } End for each
 P Cumulative product (1 if all pair results are 
 1, 0 otherwise)
 -- implicit counter increment if stack value is 1

The main idea is that, apart from the 0 key, any digit decremented and converted to base 3 has the following properties:

• left and right neighbours have an absolute difference of 1
• up and down neighbours have an absolute difference of 10 which, reversed, is conveniently equal to 1
• any other pair of numpad keys result in different values, even when reversed

Of course we need a if statement to handle the 0 numpad key.

• Magic Octopus Urn: Solid answer, came to offer more improvements, can't find any. Oooo... and that pairwise put you in the lead too :).
• Magic Octopus Urn: I don't think I would've been able to come up with those 3 rules, pretty impressive tbh; what gave you the idea?

Answer 5

MATL, (削除) 29 (削除ここまで) 27 bytes

`@J3:qEt!J*+hYAd|2>~A?@]NG-

Outputs the first n numpad-friendly numbers.

Try it online!

Explanation

Each digit from 1 to 9 is encoded as a complex number representing its position in the numpad, using in a step-2 grid, where real part represents vertical position and imaginary part represents horizontal position. So 1 is 0+0j, 2 is 0+2j, 3 is 0+4j, 4 is 2+0j, ..., 9 is 4+4j.

Digit 0 is encoded as 0+1j, i.e. as if it were placed exactly between 1 and 2.

For each candidate numpad-friendly number, a "decimal" base conversion is applied using the above complex numbers instead of the digits 0, 1, ..., 9. This gives an array, of which the absolute consecutive differences are computed. The candidate number is numpad-friendly if and only if all absolute differences are at most 2 (i.e. the grid step). If that's the case, the number is left on the stack.

The code uses a do...while loop, which is exited when the amount of numbers in the stack equals the input n.

A unit grid would have been a more natural choice. Digits 1, 2 and 0 would then correspond to 0+0j, 1+0j and 0.5+0j respecrively. But it's golfier to use a step-2 grid, because multiplying by 2 (function E) and pushing 0+1j (function J) is one byte shorter than pushing 0+0.5j (J2/ or .5j)

Answer 6

Jelly, 26 bytes

’d-,.8?3μ€ạ/S
Dṡ2Ç€<2Ạ
1Ç#

Try it online!

-2 bytes thanks to caird coinheringaahing
-2 bytes thanks to Erik the Outgolfer

Explanation

’d-,.8?3μ€ạ/S Helper Link; compute the distance between two keys z = [x, y]
 ? Switch:
 8 If z (is not 0):
’ Decrement
 d Divmod by:
 -,. Else: [-1, 0.5] (special position for 0)
 3 3; right argument for divmod otherwise ignored
 μ Begin a new monadic link / end this link
 € Compute the position for each [x, y]
 / Reduce on
 ạ Absolute Difference
 S Sum (this gives the Manhattan Distance)
Dṡ2Ç€<2Ạ Helper Link; determine if a number <z> is numpad friendly
D Convert number to decimal digits
 ṡ Slice into overlapping slices of length
 2 2 (pairs)
 € For each pair,
 Ç The distance between the keys
 <2 Compare with 2 (the distance between two adjacent keys is 1; corners 2; 0 - 1 and 0 - 2 are 1.5)
 Ạ All; either all of the distances are less than 2 or there were no distances
1Ç# Main Link; find the first (input) numpad friendly numbers
 # nfind; counting up from _ collect the first _______ matches that are
1 1
 (input)
 Ç Numpad Friendly

• caird coinheringaahing: You can remove the [] for 2 bytes
• hyperneutrino: @cairdcoinheringaahing thanks!
• Erik the Outgolfer: Golf a couple off.

Answer 7

Python 2, 134 bytes

g=lambda n,k=1:n and g(n-(lambda l:all(abs(a-b)<1.2for a,b in zip(l,l[1:])))([~-d%3+~-d/3*1j-d/~d*1.5for d in map(int,`k`)]),k+1)or~-k

Try it online!

• Jonathan Frech: As you define f and then use it once, you could inline it and save two bytes.

Answer 8

Mathematica, (削除) 249 (削除ここまで) (削除) 234 (削除ここまで) 202 bytes

(a=o=1;While[a<=#,s=IntegerDigits@o;t=1;p=0;While[t+p<Length@s,If[!FreeQ[(IntegerDigits/@{210,4210,53210,632,7541,86542,9653,874,9875,986})[[s[[t]]+1]],s[[t+1]]],t++,p++]];If[t==Length@s,a++];o++];o-1)&

Try it online!

thanks user202729 for compressing data (-32 bytes)

My results:

100 ->447
1000 ->20023
10000 ->788777

• user202729: I think you can compress the data by using IntegerDigits : IntegerDigits/@{210,4210,53210,632,7541,86542,9653,874,9875,986}, and use FreeQ, Tr, use Do instead of For, use infix notation for AppendTo and use Do instead of While to repeat Tr[1^s] times, also eliminate the variable p. Also you haven't proven that the algorithm is correct, that is, the resulting number is always less than its index squared, which is necessary to make an answer valid.
• ZaMoC: @user202729 I changed a lot of things.My answer is definately valid. I'll compress the data now.
• ZaMoC: why the downvote?

Answer 9

PHP, 124+1 bytes

while($argn-=$r)for($p=$r=~0,$x=++$n;$x>=1;$p=[7,23,47,76,178,372,616,400,928,832][$c],$x/=10)$r&=!!($p&1<<$c=$x%10);echo$n;

Run as pipe with -nR or try it online.

Answer 10

Java 8, (削除) 192 (削除ここまで) 190 bytes

n->{int r=1,p;a:for(;n>0;){p=-1;for(int c:(r+++"").getBytes())if(p>-1&!"012;0124;01235;236;1457;24568;3568;478;5789;689".split(";")[c-=48].contains(p+""))continue a;else p=c;n--;}return~-r;}

Returns the (1-indexed) n'th number in the sequence.

This was surprisingly harder than I thought.. Probably just having some brain-farts this afternoon..

Explanation:

Try it here.

n->{ // Method with integer as both parameter and return-type
 int r=1, // Return-integer
 p; // Previous digit
 a:for(;n>0;){ // Loop (1) as long as the input is larger than 0
 p=-1; // Start `p` at an integer that is not 0-9 (-1 in this case)
 for(int c:(r+++"").getBytes())
 // Loop (2) over the digits of the current number
 if(p>=0 // If this is not the first digit (`p` != -1),
 &!"012;0124;01235;236;1457;24568;3568;478;5789;689".split(";")[c-=48]
 .contains(p+""))
 // and the adjacent digits are NOT part of a NumberPad-Friendly Nr:
 continue a; // Go to the next iteration of loop (1)
 else // Else:
 p=c; // Set `p` to the current digit for the next iteration
 // End of loop (2) (implicit / single-line body)
 n--; // If we haven't encountered the `continue`, decrease `n` by 1
 } // End of loop (1)
 return~-r; // Return the result-integer - 1
} // End of method