Here is a recursive solution, it stops processing when the alternating
invariant becomes false. It is similar in principal to the sequential
machine solution but uses $: to implement the machine.
NB. assuming that the right list contains the first one, there are four cases
NB. 0 0 -> true, process remaining pairs
NB. 0 1 -> true, process commute of remaining pairs
NB. 1 0 -> false, stop
NB. 1 1 -> false, stop
NB. this is the boolean table of 'not x'
notx=. -.@[
ci=. ($:&}.) ` ($:~&}.) @. (~: &{.)
li=. 0: ` (1: *. ci f.) @. (notx &{.)
si=. 1: ` (li f.) @. (*@#@])
NB. si is the size invaraint. Empty lists are true (alternating)
NB. li is the logic invariant. If not x then process the rest
NB. ci is the commute invariant. If this pair alternates process
the commute of the rest
0 0 0 si 0 0 0
1
0 1 0 si 1 0 1
1
0 1 1 si 1 0 0
0
NB. If 1 1 is acceptable then the boolean table becomes less than or equal to
NB. and li becomes:
ci=. ($:&}.) ` ($:~&}.) @. (~:&{.)
li=. 0: ` (1: *. ci f.) @. (<:&{.)
si=. 1: ` (li f.) @. (*@#@])
0 0 0 si 0 0 0
1
0 1 0 si 1 0 1
1
0 1 1 si 1 0 0
0
0 1 1 si 1 1 0
1
On Tue, Jul 31, 2012 at 10:23 AM, Raul Miller <[email protected]> wrote:
> Here's an implementation which uses ;:
>
> smalt=: 12 > (3;1,~&>0 1 2 3,1 3 2 3,2 1 3 3,:3)&;:@:#.@|:
>
> Example use:
>
> smalt 1 0 0 1 0 1,:0 1 0 0 1 0
> 1
> smalt 0 1 0 1 0,:1 0 1 0 1
> 1
> smalt 0 0 1 0 0 0 0 1,:1 0 0 0 1 0 0 0
> 1
> smalt 1 0 0 0 1,:0 1 1 0 0
> 0
> smalt 1 0 0 1 0 1 1,: 0 1 0 0 1 0 0
> 0
> smalt 0 1 0 0 1 0,:1 0 1 1 0 0
> 0
> smalt 1 0 ,:1 0
> 0
>
> Here's a slightly more compact way of obtaining the state transition matrix:
>
> 4#.inv 27 123 159 255
> 0 1 2 3
> 1 3 2 3
> 2 1 3 3
> 3 3 3 3
>
> rows are state, columns are selected by the result of #.@|:
>
> Here's an illustration of the intermediate state results:
>
> (5;1,~&>0 1 2 3,1 3 2 3,2 1 3 3,:3);:#.|: 1 0 0 0 1,:0 1 1 0 0
> 0 _1 0 2 2 1
> 1 0 2 1 1 1
> 2 1 1 1 3 1
> 3 2 3 0 3 1
> 4 3 3 2 3 1
>
> The result from the (3;...) version is derived from the shape prefix
> of the state matrix (2 {. 4 4 2) and the middle two values in the last
> row (3 2):
> 4 4 #.3 2
> 14
> (3;1,~&>0 1 2 3,1 3 2 3,2 1 3 3,:3);:#.|: 1 0 0 0 1,:0 1 1 0 0
> 14
>
> I hope this makes sense.
>
> (More and more, I have been wishing that Iverson had stuck to his guns
> and given us a state matrix which was rank 2 (0.1#.|."1 M where M
> would be the current rank 3 state transition matrix). The rank 3
> variant makes sense for 32 bit machines, which were prevalent in
> schools back then, but he's right that the rank 2 version is simpler
> to work with and is for all practical cases at least as efficient,
> nowadays...)
>
> --
> Raul
>
>
> On Mon, Jul 30, 2012 at 4:12 PM, Peter B. Kessler
> <[email protected]> wrote:
>> R.E. Boss wrote:
>>>
>>> My 2 cents:
>>>
>>> (>./-<./)+/\+/1 _1 *A
>>> 1
>>>
>>> (>./-<./)+/\+/1 _1 *B
>>> 2
>>>
>>> So A qualifies, B does not.
>>>
>>>
>>> R.E. Boss
>>
>>
>> This doesn't address the case where both inputs have 1's in the same column
>>
>> ]C=:2 5 $ 1 0 0 1 0 0 1 0 1 0
>>
>> 1 0 0 1 0
>> 0 1 0 1 0
>> (>./-<./)+/\+/1 _1 *C
>> 1
>>
>> The original statement of the problem doesn't say what to do with
>> simultaneous 1's, but I would think they fail the "alternating" description.
>>
>> I am a total newb when it comes to J programming, though I did some APL
>> programming in the early 1970's. I find that what's missing from this
>> example (and lots of other examples of J programs) is a statement of why it
>> is written the way it is. I find J expressions to be wonderfully precise on
>> *what* the expression is doing, but not *why* the author wrote it that way.
>> (E.g., whether it's taking advantage of some special case, or should be
>> studied by us newbs for its deep insights.) It often takes me a long time
>> to figure out what a given expression does, then I have to figure out how
>> that combination solves the problem at hand, and guess at why that's the
>> best way to solve this particular problem. For example, I love the use of
>> "+/\" in the above to propagate the state of the match. (Though, I worry a
>> little about the efficiency of it, if prefix really reapplies the verb to
>> each of the possible prefixes, especially as the inputs get long.) Raul
>> Miller and especially Ma
>> rshall Lochbaum are wonderful exceptions in this thread, describing how
>> their solutions work.
>>
>> In the "alternating binary array" case, it seems, to me, like what's called
>> for is a small finite state machine (or regular expression parser, if that's
>> how you think). Start in a neutral state, and move to a new state on
>> reading a column of the input. I think there are only 4 states:
>> TooSoonToTell, MostRecently01, MostRecently10, and Error. TooSoonToTell
>> just moves to one of the MostRecently states based on the input (or to Error
>> on 1 1). The MostRecently states transition to the other MostRecently on
>> the "other" input, or to Error on the same input (or on 1 1). Error just
>> stays in Error regardless of the input. The state machine seems almost
>> J-friendly, since it can be represented as a matrix with rows for states and
>> columns for inputs, yielding a new state. I see that J *has* a Sequential
>> Machine (dyadic :;) operator. Why isn't that the right solution to the
>> alternating 1's problem?
>>
>> Conversely, why is it not J-like to filter out the 0 0 columns (and check
>> for 1 1 columns while you are there), then match successive 2x2 blocks to
>> make sure they are all the same? Either "2 2 $ 0 1 1 0" or "2 2 $ 1 0 0 1",
>> whichever comes first? (Or use Raul Miller's sort trick to impose an
>> order.) I'm sure it would take me hours to construct that expression, and
>> maybe I shouldn't spend the time, if that's not the J way to do things like
>> this. Is that not J-like because I shouldn't be thinking in terms of
>> iterating over the input?
>>
>> I'm trying to learn to think like a J programmer. Thanks for teaching me to
>> fish.
>>
>> ... peter
>>
>>
>>>> -----Oorspronkelijk bericht-----
>>>> Van: [email protected]
>>>> [mailto:[email protected]] Namens Linda Alvord
>>>> Verzonden: zaterdag 28 juli 2012 9:43
>>>> Aan: [email protected]
>>>> Onderwerp: Re: [Jprogramming] Determining an 'alternating' binary array
>>>>
>>>> In this case the tacit version leads to a better explicit definition:
>>>>
>>>>
>>>> al=: 13 :'(-:((2 2$0 1 1 0)$~#))(|: y) -. 0 0'
>>>> al
>>>> [: (-: ((2 2$0 1 1 0) $~ #)) 0 0 -.~ |:
>>>>
>>>> al2=: 13 :'(-:(2 2$0 1 1 0)$~#)0 0 -.~|:y'
>>>> al2
>>>> [: (-: ((2 2$0 1 1 0) $~ #)) 0 0 -.~ |:
>>>>
>>>> Linda
>>>>
>>>> -----Original Message-----
>>>> From: [email protected]
>>>> [mailto:[email protected]] On Behalf Of Linda
>>>> Alvord
>>>> Sent: Saturday, July 28, 2012 3:14 AM
>>>> To: [email protected]
>>>> Subject: Re: [Jprogramming] Determining an 'alternating' binary array
>>>>
>>>> This seems to work as well:
>>>>
>>>> (|:A)-: |: A/:A
>>>> 1
>>>> al=: 13 :'(-:((2 2$0 1 1 0)$~#))(|: y) -. 0 0'
>>>> al
>>>> [: (-: ((2 2$0 1 1 0) $~ #)) 0 0 -.~ |:
>>>>
>>>> al A
>>>> 1
>>>> al B
>>>>
>>>> -----Original Message-----
>>>> From: [email protected]
>>>> [mailto:[email protected]] On Behalf Of Linda
>>>> Alvord
>>>> Sent: Saturday, July 28, 2012 2:45 AM
>>>> To: [email protected]
>>>> Subject: Re: [Jprogramming] Determining an 'alternating' binary array
>>>>
>>>> Here's an alternative to 'alternative'
>>>>
>>>> ]A=:2 8$ 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0
>>>> 0 0 1 0 0 0 0 1
>>>> 1 0 0 0 1 0 0 0
>>>> ]B=:2 5$1 0 0 0 1 0 1 1 0 0
>>>> 1 0 0 0 1
>>>> 0 1 1 0 0
>>>> alt=: 13 :'(-:((2 2$0 1 1 0)$~#))(|: y /:y) -. 0 0'
>>>> alt
>>>> [: (-: ((2 2$0 1 1 0) $~ #)) 0 0 -.~ [: |: /:~
>>>>
>>>> alt A
>>>> 1
>>>> alt B
>>>> 0
>>>>
>>>> Linda
>>>>
>>>> -----Original Message-----
>>>> From: [email protected]
>>>> [mailto:[email protected]] On Behalf Of Marshall
>>>> Lochbaum
>>>> Sent: Friday, July 27, 2012 11:56 AM
>>>> To: [email protected]
>>>> Subject: Re: [Jprogramming] Determining an 'alternating' binary array
>>>>
>>>> Here's another option: convert the two rows into one using base 2,
>>>> discard
>>>> the ones that are 0, and check if the remaining ones are 1 2 1...
>>>> I borrowed the sort in Raul's solution so that they must be in that
>>>> order,
>>>> not 2 1 2... .
>>>>
>>>> alternate =: (-: 1 2$~$)@:(0 -.~ #.@|:)@:/:~
>>>>
>>>> Note that we don't have to convert to binary. In this case, we end up
>>>> with
>>>>
>>>> alternate =: (-: (0 1,:1 0)$~#)@:(0 0 -.~ |:)@:/:~
>>>>
>>>> Marshall
>>>>
>>>> On Fri, Jul 27, 2012 at 10:39 AM, Brian Schott
>>>> <[email protected]>wrote:
>>>>
>>>>> Another approach?
>>>>>
>>>>> alternates =: [: -. 1 e. [: +/ 0 1 |."0 1 ] #"_ 1~ +./ noAnds =:
>>>>> *./@(-.@(*./)) check =: noAnds *. alternates
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> (B=)
>>>>> ----------------------------------------------------------------------
>>>>> For information about J forums see http://www.jsoftware.com/forums.htm
>>>>>
>>>> ----------------------------------------------------------------------
>>>> For information about J forums see http://www.jsoftware.com/forums.htm
>>>>
>>>> ----------------------------------------------------------------------
>>>> For information about J forums see http://www.jsoftware.com/forums.htm
>>>>
>>>> ----------------------------------------------------------------------
>>>> For information about J forums see http://www.jsoftware.com/forums.htm
>>>>
>>>> ----------------------------------------------------------------------
>>>> For information about J forums see http://www.jsoftware.com/forums.htm
>>>
>>>
>>> ----------------------------------------------------------------------
>>> For information about J forums see http://www.jsoftware.com/forums.htm
>>
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
