Sure, shouldn't be too hard to implement in any language.
Here's a J implementation:
nextdigits=: ".;._2]0 :0
4 6 7 9 _1 NB. 0
5 6 8 9 _1 NB. 1
4 6 7 9 _1 NB. 2
4 5 7 8 _1 NB. 3
2 3 8 9 0 NB. 4
1 3 7 9 _1 NB. 5
1 2 7 8 0 NB. 6
2 3 5 6 0 NB. 7
1 3 4 6 _1 NB. 8
1 2 4 5 0 NB. 9
)
startdigits=: ,.2}.i.10
repcnts=: +/"1 nextdigits>:0
adddigit=: (([ #~ repcnts {~ ]) ,. _1 -.~ nextdigits ,@:{~ ]) {:"1
phones=: adddigit^:6 startdigits
And here's some peeks into the resulting data:
$phones
61618 7
({.,:{:) phones
2 4 2 4 2 4 2
9 0 9 0 9 0 9
({~ ?@(5##)) phones
2 4 0 6 0 9 5
9 0 9 5 1 9 1
2 9 1 6 8 4 3
8 3 7 6 7 5 7
4 2 7 5 1 6 7
Takes about 3 milliseconds to compute phones, and on a 64 bit machine
would take about 4 megabytes to store the value. So you would have
some space/time tradeoffs to play with if resources were constrained.
Or, if you're going to be like the comment responder and try to solve
a different problem (the "arbitrary length phone numbers formed by
knight/bishop moves", and/or if you really just wanted the count and
you were concerned about those milliseconds and/or megabytes you could
go like this:
startstate=: 1 < i.10
connections=: (i.10) e."1 nextdigits
nextstate=: +/ .*&connections
+/ nextstate^:6 startstate
61618
Of course, as you can see, that commenter's answer was wrong for the 7
digit phone number's case. (The moral of the story is: first make sure
you're computing the right answer, only after that should you concern
yourself with speed. Otherwise you usually wind up computing the wrong
answer really fast...)
So let's see how many "100 digit knight bishop phone numbers" you
would get (if that somehow made sense):
+/ nextstate^:99 x: startstate
100369027067545989664091067142173016509466346625113672524533731962
Good enough?
Thanks,
--
Raul
On Fri, Oct 16, 2015 at 2:30 PM, Devon McCormick <[email protected]> wrote:
> This looks like an interesting problem that shouldn't be too hard to state
> in J:
> http://codereview.stackexchange.com/questions/107470/find-total-number-of-phone-numbers-formed-by-the-movement-of-knight-and-bishop-o
> .
>
> --
>
> Devon McCormick, CFA
>
> Quantitative Consultant
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
