Create a list of snaking numbers under 50,000

Question

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

1. Numbers cannot start with a Zero.
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
0001 - multiple leading 0s
0101 - leading 0
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.

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

Python 2, 101 bytes

print[n for n in range(1,50000)if all(`n`[i:i+2]in`0x20b33ec8bc49a10589e76b15`for 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.

Answer 5

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!

Answer 6

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.

Answer 7

PHP, 145 bytes

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.

Answer 8

05AB1E, 23 bytes

ŽÅKLʒSÌYX;:3‰üαï€OP}=g=

Try it online!

Port of Jonathan Allan's Jelly answer.

Answer 9

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

Answer 10

JavaScript (SpiderMonkey), 179 173 151 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))

Answer 11

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!

Answer 12

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.

Answer 13

Haskell, 118 bytes

(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.

Ungolfed code.

Answer 14

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.

Answer 15

Japt, 34 bytes

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

Try it

Answer 16

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

Answer 17

Pyth, 68 65 45 bytes

l
f.Am}dCtB+J`65874589632012541_PJCtB`TS50000

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";shdCtB`TS50000

---

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