# Create a list of snaking numbers under 50,000

### Snaking Number Challenge

I wonder how many snaking numbers there are between 1 and 50,000?

Snaking Numbers, in this game, are numbers which can be typed out on a traditional numberpad (format below) by moving one key up, down, left, or right.

7 8 9
4 5 6
1 2 3
0


For example, if you start with the number 5, you could select 4, 6, 8, or 2 as your next valid move - however 7, 3, 9, and 1 are off-limits as they are positioned diagonally to the current key. So, if you have 5, then 2, your next viable key choices are 0, 1, 3, or 5 again.

In this Code Golf exercise, you are to output a list of all the positive snaking numbers between 1 and 50k, along with a final count of all the numbers that meet the criterion.

### Rules

2. Numbers must be whole positive integers.
3. Each consecutive number, read from left to right, must "snake" around the numberpad.
4. The snake cannot travel diagonally across keys
5. The number 0 can be accessed from both numbers 1 and 2
6. Numbers cannot be paired (eg: 22)

### Examples of valid Snaking Numbers:

12369
45201
1254
10102
1
12
987


### Examples of invalid numbers

1238 - 8 is not connected
159  - snake cannot travel diagonally
4556 - duplicate 5


As per normal Code Golfs, the aim is fewest bytes!

According to my maths and rules, you should have 670 valid snaking numbers in your list, plus 670 itself printed as the last number.

• Should the output be sorted? Or is it allowed in any order?
– tsh
Aug 29 '19 at 9:14
• Seeing as you're asking us to output a fixed and finite set of integers, I'd suggest including the full list in the spec. Aug 29 '19 at 9:34
• Related Aug 29 '19 at 10:20
• This is a subset of A215009. Aug 29 '19 at 13:20
• Would it be alright to print 670 first?
– dana
Sep 1 '19 at 23:38

# K (ngn/k), 60 57 60 bytes

(x;#x:({*/1=3!5&+/x*x:+1_-':(+0 1,'2*!3 3)@10\x}')#1+!50000)


Try it online!

!50000 list of 0 .. 49999

1+ add 1 to all

({ }')# filter with the function in { }

10\x decimal digits of the argument

( )@ use as indices in ...

• !3 3 a pair of lists: (0 0 0 1 1 1 2 2 2;0 1 2 0 1 2 0 1 2)

• 2* multiply all by 2

• 0 1,' prepend 0 to the first list and 1 to the second

• + transpose (pair of lists -> list of pairs). this gives us the approx button coords.

-': subtract from each pair the previous pair. use 0 0 as an imaginary element before the first.

1_ drop the first

+ transpose

x*x: square (assign to x and multiply by x). here x is a pair of lists - ∆x-s and ∆y-s

+/ sum the two lists (element by element)

5& min with 5

3! mod 3

1= boolean list of where it's equal to 1

*/ product (boolean "and")

(x;#x: ) make a pair of the result and the length (#) of the result

# Jelly,  24  23 bytes

5ȷ4µDo1.’d3ZIASĊ’ẸµÐḟṄL


A full program which prints a list of all the results and then the number of results.

Try it online!

### How?

5ȷ4µDo1.’d3ZIASĊ’ẸµÐḟṄL - Main Link: no arguments
5ȷ4                     - 5*10^4 = 50000
µ              µÐḟ   - filter discard those for which this is truthy:
-                  e.g.: 8520        ... or           4559
D                   -   decimal digits       [8,5,2,0]                    [4,5,5,9]
1.                -   literal 1.5
o                  -   logical OR           [8,5,2,1.5]                  [4,5,5,9]
’               -   decrement            [7,4,1,0.5]                  [3,4,4,8]
d3             -   div-mod by 3         [[2,1],[1,1],[0,1],[0,0.5]]  [[1,0],[1,1],[1,1],[2,2]]
Z            -   transpose            [[2,1,0,0],[1,1,1,0.5]]      [[1,1,1,2],[0,1,1,2]]
I           -   deltas               [[-1,-1,0],[0,0,-0.5]]       [[0,0,1],[1,0,1]]
A          -   absolute value       [[1,1,0],[0,0,0.5]]          [[0,0,1],[1,0,1]]
S         -   sum (vectorises)     [1,1,0.5]                    [1,0,2]
Ċ        -   ceiling              [1,1,1]                      [1,0,2]
’       -   decrement            [0,0,0]                      [0,-1,1]
Ẹ      -   any?                 0 (i.e. keep)                1 (i.e. discard)
Ṅ  - print and yield
L - length
- implicit print

• I'd love to know how this one works. Any chance you could give a breakdown? Aug 29 '19 at 10:01
• @MightBeAlon will do later... Aug 29 '19 at 10:04
• I am curious, how does 1.evaluate to 1.5? Aug 30 '19 at 2:40
• @EmbodimentofIgnorance during literal parsing a missing digit after a period is treated as being a five. See the final else clause of parse_literal in interpreter.py Aug 30 '19 at 6:53

# Python 3, 140 bytes

f=lambda s:''==s[1:]or s[1]in'10021234562216565878 43 749 9   5  8'[int(s[0])::10]and f(s[1:])
print(*filter(f,map(str,range(1,50000))),670)


Try it online!

I'm positive someone will be able to do this with an expression instead of a lookup string.

# Python 2, 101 bytes

print[n for n in range(1,50000)if all(n[i:i+2]in0x20b33ec8bc49a10589e76b15for i in range(4))],670


Try it online!

The hex number is decimal 10120214525632365878969854741, which encodes every ordered pair of digits that can appear adjacent to one another.

# JavaScript (V8),  112 106  104 bytes

Saved 2 bytes thanks to @NahuelFouilleul

A full program.

for(n=0;++n<5e4;)[...n+''].every(x=>'6589632145201478'.match(x+p+'|'+p+(p=x)),p='')&&print(n)
print(670)


Try it online!

Or 96 bytes if we can output the numbers in reverse order:

for(n=5e4;n--;)[...n+''].every(x=>'6589632145201478'.match(x+p+'|'+p+(p=x)),p='')&&print(n||670)


Try it online!

• works also removing the last 3 maybe because 36 is already in string Aug 29 '19 at 12:21
• @NahuelFouilleul Good catch. Thanks! Aug 29 '19 at 12:23
• also 6589632145201478 is one byte shorter Aug 29 '19 at 12:31

# Stax, 37 35 bytes

ü╞╡~▄ⁿ♪eµïê◙ü╔ï▼ΔJr¥æ≤PH╟♀I♣Δz8─¶Γ╞Ç▓


Run and debug it at staxlang.xyz!

It was so nice and short, until it wasn't.

### Unpacked (42 bytes) and explanation

49999{E2B{{om"#qYY>!(AFI"%A|E2B{{om-C_Qf%p
49999{                                 f      Filter range [1..49999]:
E2B                                       All adjacent pairs of digits
{{om                                   Each sorted
"#qYY>!(AFI"%A|                    Literal 2012365478963258741
E2B{{om             Pairs of digits, each sorted
-            Set difference
C           Cancel block execution if any remain
_Q         Print current value
%p    Print length


2012365478963258741 encodes the keypad. Look at pairs of adjacent digits. Perhaps if I could get a decently short alternative that goes in both directions for each pair, I could cut the eight bytes of {{om.

Without that trailing 670, a simple filter would suffice: f..! instead of {..C_Qf%p. There might be a better way to go about handling this irregularity. In either case, this filter-range behavior is undocumented.

• Sorry about the documentation gaps. FWIW, that one will be in the next release, 1.1.7. You can see a preview at stax.tomtheisen.com , but it's a secret so don't tell anyone. ;) Aug 29 '19 at 18:03

for(;$i++<5e4;$f&&print$i._)for($f=1,$l=b;''<$d=("$i")[$$i++];$l=$d)$f&=$l>a||strstr([12,240,1053,26,157,2468,359,48,579,68][$l],$d)>'';echo 670;  Try it online! For every number from 1 to 50,000, checks every digit of that number from left to right. If all digits are in the list of valid digits of the previous digit, that number is printed. At the end prints a hard coded 670 since it takes less bytes than actually counting it. # 05AB1E, 23 bytes ŽÅKLʒSÌYX;:3‰üαï€OP}=g=  Try it online! Port of Jonathan Allan's Jelly answer. • Ah, smart of just compressing the 50000 in 3 bytes. I was using ₄50* or 4°5* when I was making an attempt earlier. And at first I was confused why you had €OP instead of just OP, but then I realized the single digit numbers (being an empty list after the üα) would then be [] → 0 → 0 instead of [] → [] → 1. :) Aug 29 '19 at 14:07 • @KevinCruijssen Why 4°5* when you can 5°;? I like ZAK better though. And yeah, that edge-case for single-digit numbers is a pain. Aug 29 '19 at 14:47 # Perl 5 (-M5.01), 96, 92 bytes -4 bytes thanks to @Xcali $r=join"|",map$t++."[^$_]",12,240,1350,26,157,2648,359,48,579,68;map/$r/||say,1..5e4;say 670  TIO • 92 Aug 29 '19 at 18:12 • thanks indeed, over-complicated because first answer was positive match Aug 29 '19 at 19:10 # JavaScript (SpiderMonkey), 179173151 129 bytes [12,240,1350,26,157,2468,359,48,579,68].map((_,i,l)=>i&&(f=(v,t)=>print(v)|v<5e3&&[...l[t]+''].map(k=>f(v+k,k)))(i,i)),print(670)  Try it online! -22 bytes thank to Arnauld -22 bytes thank to dana # explanation: [12,240,1350,26,157,2468,359,48,579,68] // an array where keys are current position and values, the possible destinations .map((_,i,l)=> // loop over it i&&( // if key is not 0 f=(v,t)=> // create a function print(v)| // which print the value v<5e3&& // and if the limit is not attained [...l[t]+''].map(k=>f(v+k,k)) // recurcively call itself with for each destinations )(i,i)), // make the first call with each digit print(670) // finally print 670  @dana also gave a 123 bytes solution if we can print 670 first [21,420,5310,62,751,8642,953,84,975,86].map((_,i,a)=>(f=(v,t)=>print(i?v:640)|i&v<5e3&&[...a[t]+''].map(k=>f(v+k,k)))(i,i))  • @Arnauld thank I forgot this rule Aug 29 '19 at 13:00 • Some optimizations Aug 29 '19 at 20:48 • 129? – dana Sep 1 '19 at 6:55 • 123 if 640 can be printed first. – dana Sep 1 '19 at 23:46 # Ruby, 99 bytes 1.upto(5e4){|n|w,*x=n.digits;x.all?{|d|[6,21,43,68,162,340,552,272,672,320][w][w=d]>0}&&p(n)} p 670  Try it online! # Stax, 28 26 bytes Δh┤♣É╦&·é╝n$K»à¶▲v═NÆ;↨m≥8


Run and debug it

Unpacked, ungolfed, and commented, it looks like this.

G               Call to unbalanced trailing '}', then resume here
670P            Print 670
}               Call target
219J            219 squared (47961)
f               Filter 1-based range by the rest of the program; implicitly output
$2B Convert to string and get adjacent pairs; e.g. 213 -> ["21", "13"] O Push 1 under list of pairs F Iterate over pairs, using the rest of the program o Order each pair; e.g. "21" -> "12" "{<f:[/T8Z" string literal with code points [123 60 102 58 91 47 84 56 90]$           concate as string i.e. "12360102589147845690"
s#          How many times does the current pair appear in the constant string?
*           Multiply this by running total.  Any zero will cause the result to be zero.


Run this one

The secret sauce is in the string literal "{<f:[/T8Z". After jamming all the codepoints together, you get 12360102589147845690. The ascending pairs in this string are the valid snake moves.

• 15JJ instead of 219J would work as well, but I don't think you can golf any byte from there unless there's a 1-byte constant for 15. Aug 30 '19 at 13:56

(filter(and.(zipWith elem.tail<*>map f).show)[1..50000],670)
f c=words"12 024 0135 26 157 2468 359 48 579 68"!!read[c]


Try it online!

A first pass; I'm not good at compression.

The s= doesn't count, since we don't actually need to bind the result.

# Charcoal, 42 bytes

≔ΦＩ…·¹×⁵⁰φ⬤ι№”)¶∧XRτ_ΠＧêＲ⁵m⎇λ”✂ιμ⁺²μ¹θθＩＬθ


Try it online! Link is to verbose version of code. Explanation:

≔ΦＩ…·¹×⁵⁰φ


Process the inclusive range from 1 to 50,000 cast to string.

⬤ι№”)¶∧XRτ_ΠＧêＲ⁵m⎇λ”✂ιμ⁺²μ¹θ


Filter out those that have pairs of digits not contained in the compressed string 01478963202125458565236987410.

θＩＬθ


Output the remaining array and its length.

# Japt, 34 bytes

5e4õs f_ä@"-Pì[/Z8"mc øZñÃe
pUl


Try it

# Perl 6, 64 bytes

{670,grep {[+&](:36<12HGX91H8VCL3MG0FDVQ>X+>m:ov/../)%2},1..5e4}


Try it online!

### Explanation

{670,grep {...},1..5e4}  # Meet questionable output requirements

# Actual decision problem

:36<12HGX91H8VCL3MG0FDVQ>  # Bit field of allowed transitions
# encoded in base 36
m:ov/../  # All 2-digit substrings
X+>  # Right shift by each substring
# (implicitly converted to an integer)
[+&](                                    )  # Binary and
%2  # Modulo 2

• It's a pity ~> isn't implemented yet, otherwise you might be able to do this with just string operators, with the bit field being a string
– Jo King
Sep 1 '19 at 22:42

# Pyth, 6865 45 bytes

l
f.Am}dCtB+J65874589632012541_PJCtBTS50000


Try it online!

Inspiration for the revised lookup process came from Khuldraeseth na'Barya's Stax answer, go give them an upvote!

Edit 2: Rewrote to save a bunch of bytes, previous version:

l
f.Am}ed@c"12 024 0135 26 157 2468 359 48 579 68";shdCtBTS50000


Edit: Golfed 3 bytes by using string lookups, previous version:

l
f.Am}ed@sMMc"12 024 0135 26 157 2468 359 48 579 68";hdCtBjT;S50000
`