Array Sandwiches

GolfScript, 51 chars

~:A{,}%{*}*,{A{,.@.@/\@%}%\;}%{:k,,{.A=\k==}%.$=},`

Example input (on stdin):

[[1 5 7 10] [2 6 6 8 12] [4 5 9]]

Example output (to stdout):

[[0 0 0] [0 0 1] [0 0 2] [0 1 2] [1 1 2] [0 2 2] [1 2 2] [0 3 2] [1 3 2] [2 3 2]]

(Note that input must be given without commas, otherwise the program will most likely crash.)

I guess I should add some explanation about how this code works:

  • ~:A just evaluates the input as GolfScript code and assigns the result (an array of arrays) to A. It also leaves a copy of A on the stack for the next step.

  • {,}% replaces each sub-array with its length, and {*}* multiplies those lengths together, giving the total number of possible sandwich candidates. This number is then converted by , to an array of that many successive integers starting from 0.

  • {A{,.@.@/\@%}%\;}% converts each number into a the corresponding sandwich candidate (i.e. an array of valid indices into each sub-array in A). For example, given the input above, 0 would map to [0 0 0], 1 to [1 0 0], 2 to [2 0 0], 3 to [3 0 0], 4 to [0 1 0] and so on. (Figuring out exactly how the code accomplishes that is left as an exercise for the interested reader.)

  • {:k,,{.A=\k==}%.$=}, filters the sandwich candidates by mapping each of them to the corresponding elements of the sub-arrays of A (so that e.g. [0 0 0] would yield [1 2 4], [1 0 0] would yield [5 2 4], and so on, for the input above), sorting the resulting array and comparing it with an unsorted copy. If they are equal, the array was already sorted, and thus the candidate is indeed a sandwich.

  • Finally, ` just turns the filtered array of sandwiches into a string for output.


Mathematica, 120 130 bytes

Edit

This version works with arrays of varying sizes.

l = List;
g = Grid@Cases[Outer[l, Sequence @@ MapIndexed[l, #, {2}], 1]~Flatten~(Length[#] - 1), 
x_ /; LessEqual @@ x[[All, 1]] == True :> x[[All, 2, 2]] - 1] &

Usage

g@{{10, 20, 30}, {1, 22, 3}}
g@{{1, 5, 7, 10}, {2, 6, 6, 8, 12}, {4, 5, 9}}
g@{{10, 20, 30}, {1, 2, 3}}
g@{{1, -2, 3}, {-12, -7, 8, 9, 6}, {3, 99, 9}, {100, 10, -23}, {90, 10}}

results

Explanation

Using the first example from above,

a = {{10, 20, 30}, {1, 22, 3}}

MapIndexed sets indices for all the elements. N.B.: Mathematica begins counting with 1. (We'll later take that into account.)

MapIndexed[l, a, {2}]

{{{10, {1, 1}}, {20, {1, 2}}, {30, {1, 3}}}, {{1, {2, 1}}, {22, {2, 2}}, {3, {2, 3}}}}

Outer generates all lists, each a candidate as a sandwich array, and the indices of their elements; % contains the results from the prior output. The numbers, 10 and 22 which I highlighted after they were output, refer to a sandwich array {10,22} that has yet to be identified as such.

Outer[l, Sequence @@ %, 1]~Flatten~(Length[a] - 1)

{{{10, {1, 1}}, {1, {2, 1}}}, {{10, {1, 1}}, {22, {2, 2}}}, {{10, {1, 1}}, {3, {2, 3}}}, {{20, {1, 2}}, {1, {2, 1}}}, {{20, {1, 2}}, {22, {2, 2}}}, {{20, {1, 2}}, {3, {2, 3}}}, {{30, {1, 3}}, {1, {2, 1}}}, {{30, {1, 3}}, {22, {2, 2}}}, {{30, {1, 3}}, {3, {2, 3}}}}

Cases tests each element of the above to determine whether a LessEqual (less than or equal) relation holds.  The results shown below are those instances in which array sandwiches were detected. Once again, I highlighted {10,22} in the output.

Cases[%, x_ /; LessEqual @@ x[[All, 1]] == True]

{{{10, {1, 1}}, {22, {2, 2}}}, {{20, {1, 2}}, {22, {2, 2}}}}

%% refers to the penultimate results. :>, [ RuleDelayed]  returns thos parts of the instances of interest, namely, the indices of the array sandwiches.  -1 corrects for the fact that Mathematica begins arrays with 1 instead of 0. 

Cases[%%, x_ /; LessEqual @@ x[[All, 1]] == True :> x[[All, 2, 2]] - 1]

{{0, 1}, {1, 1}}

Grid displays the results in a grid. The first row 0 1 means the that element 0 from the first sublist (i.e. 10) and the element 1 from the second sublist (i.e. 22) constitute the first sandwich array that was found.

Grid@%

0 1

1 1


APL (33)

↑1-⍨B/⍨{(⍳⍴A)∘≡⍋⍵⌷¨A}¨B←,⍳⊃∘⍴¨A←⎕

Input is read from the keyboad, but it must be given as an APL list, i.e.

(1 5 7 10) (2 6 6 8 12) (4 5 9)

Explanation:

  • B←,⍳⊃∘⍴¨A←⎕: A is evaluated input, B is all possible sets of indices in the lists given in A.
  • {(⍳⍴A)∘≡⍋⍵⌷¨A}¨B: for each set of indices, get the values from the lists (⍵⌷¨A) and see if they are sorted ((⍳⍴A)∘=⍋)
  • B/⍨: select from B all sets of indices where the previous expression was true (i.e. all the sandwiches)
  • 1-⍨: subtract one from all indices, because this question assumed 0-based arrays and APL-arrays are 1-based by default.
  • ↑: arrange the list of sets of indices as a matrix (so each set is on its own line)

Tags:

Code Golf

Array Manipulation

Recent Posts