24
\$\begingroup\$

Snaking Number Challenge

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

Snake on a Nokia

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Should the output be sorted? Or is it allowed in any order? \$\endgroup\$ – tsh Aug 29 at 9:14
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Shaggy Aug 29 at 9:34
  • \$\begingroup\$ Related \$\endgroup\$ – Arnauld Aug 29 at 10:20
  • 4
    \$\begingroup\$ This is a subset of A215009. \$\endgroup\$ – bigyihsuan Aug 29 at 13:20
  • \$\begingroup\$ Would it be alright to print 670 first? \$\endgroup\$ – dana Sep 1 at 23:38

17 Answers 17

14
\$\begingroup\$

K (ngn/k), 60 57 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

\$\endgroup\$
9
\$\begingroup\$

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
\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ works also removing the last 3 maybe because 36 is already in string \$\endgroup\$ – Nahuel Fouilleul Aug 29 at 12:21
  • \$\begingroup\$ @NahuelFouilleul Good catch. Thanks! \$\endgroup\$ – Arnauld Aug 29 at 12:23
  • 1
    \$\begingroup\$ also 6589632145201478 is one byte shorter \$\endgroup\$ – Nahuel Fouilleul Aug 29 at 12:31
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. ;) \$\endgroup\$ – recursive Aug 29 at 18:03
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 23 bytes

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

Try it online!

Port of Jonathan Allan's Jelly answer.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. :) \$\endgroup\$ – Kevin Cruijssen Aug 29 at 14:07
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Grimmy Aug 29 at 14:47
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 92 \$\endgroup\$ – Xcali Aug 29 at 18:12
  • \$\begingroup\$ thanks indeed, over-complicated because first answer was positive match \$\endgroup\$ – Nahuel Fouilleul Aug 29 at 19:10
3
\$\begingroup\$

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))
\$\endgroup\$
  • \$\begingroup\$ @Arnauld thank I forgot this rule \$\endgroup\$ – jonatjano Aug 29 at 13:00
  • \$\begingroup\$ Some optimizations \$\endgroup\$ – Arnauld Aug 29 at 20:48
  • \$\begingroup\$ 129? \$\endgroup\$ – dana Sep 1 at 6:55
  • \$\begingroup\$ 123 if 640 can be printed first. \$\endgroup\$ – dana Sep 1 at 23:46
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Arnauld Aug 30 at 13:56
2
\$\begingroup\$

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.

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

Charcoal, 42 bytes

≔ΦI…·¹×⁵⁰φ⬤ι№”)¶∧XRτ_ΠGêR⁵m⎇λ”✂ιμ⁺²μ¹θθILθ

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

≔ΦI…·¹×⁵⁰φ

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

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

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

θILθ

Output the remaining array and its length.

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

Japt, 34 bytes

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

Try it

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

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
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Jo King Sep 1 at 22:42
1
\$\begingroup\$

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