Ah... I did not document this adequately.
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
)
Look at the 0 on the phone keypad.
You can reach 4 and 6 using knight moves, and you can reach 7 and 9
using bishop moves.
Next, look at the 2 on the phone keypad.
You can reach 4 and 6 using bishop moves and you can reach 7 and 9
using knight moves.
More generally, each row of the "nextdigits" array corresponds to a
digit of a phone number, and the values within that row represent the
possible "next" digit which can be reached using bishop or knight
moves. And, since 0 is a valid digit, I padded these rows using _1.
Hopefully this helps make my code be more readable?
Thanks,
--
Raul
On Fri, Oct 16, 2015 at 10:41 PM, Raul Miller <[email protected]> wrote:
> 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
