8
\$\begingroup\$

(Adapted from Problem C of the first qualifier of the ACM Programming Contest of 2012/2013)

You have several arrays, named A1, A2, ... , An, each sorted in ascending order. Every item in the array will be a 32-bit integer.

A sandwich is a set of indices j1, j2, ... , jn such that A1[j1] ≤ A2[j2] ≤ .... ≤ An[jn].
Ai[0] is the first element of Ai.

Given some arrays, output every possible sandwich that you can have from those arrays, seperated by a newline.

If there is somehow a built-in function which does this in your language, don't use it.

Input can be given in any way, output must be seperated with whitespace, but can given in any order.

Test Case:
[[1, 5, 7, 10], [2, 6, 6, 8, 12], [4, 5, 9]]

Output:

0 0 0
0 0 1
0 0 2
0 1 2
0 2 2
0 3 2
1 1 2
1 2 2
1 3 2
2 3 2

Test Case:
[[10, 20, 30], [1, 2, 3]]

Output:

Shortest code wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ What values can the arrays contain? Only positive integers? \$\endgroup\$ – Ilmari Karonen Sep 23 '12 at 18:47
  • \$\begingroup\$ @IlmariKaronen: They will contain negative integers as well. \$\endgroup\$ – beary605 Sep 23 '12 at 21:08
  • \$\begingroup\$ @PeterTaylor: For simplicity, they will be 32-bit integers. \$\endgroup\$ – beary605 Sep 23 '12 at 21:46
  • \$\begingroup\$ @DavidCarraher: It's the next test case. I should make it more clear. \$\endgroup\$ – beary605 Sep 23 '12 at 22:50
  • \$\begingroup\$ Thanks. Now I see that my current solution only works for arrays of 3 elements. I'll have to work a bit more to generalize it. \$\endgroup\$ – DavidC Sep 23 '12 at 23:22
2
\$\begingroup\$

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

Mathematica 120 130

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

\$\endgroup\$
  • \$\begingroup\$ I dislike this answer since you artificially simplify your answer by fixing the number arrays. \$\endgroup\$ – FUZxxl Sep 24 '12 at 13:32
  • \$\begingroup\$ If you mean that it only works for arrays of 3 "rows", I share your dislike. The problem has to do with enabling LessEqual to work with arrays of indeterminate size. There may be other instances where the same assumption impedes generality. When I get a chance, I'll generalize the approach. \$\endgroup\$ – DavidC Sep 24 '12 at 13:49
  • \$\begingroup\$ @FUZxxl I was able to generalize the approach. Take a look. \$\endgroup\$ – DavidC Sep 24 '12 at 19:24
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ They must be seperated by whitespace, so spaces or tabs work as well. \$\endgroup\$ – beary605 Sep 23 '12 at 21:10
  • \$\begingroup\$ OK, I've changed the output format. \$\endgroup\$ – Ilmari Karonen Sep 23 '12 at 21:25
1
\$\begingroup\$

R - 89 chars

i=do.call(expand.grid,lapply(x,seq_along))
i[apply(diff(t(mapply(`[`,x,i)))>=0,2,all),]-1

where

x = list(c(1, 5, 7, 10), c(2, 6, 6, 8, 12), c(4, 5, 9))

or

x = list(c(10, 20, 30), c(1, 2, 3))
\$\endgroup\$
1
\$\begingroup\$

Python, 149 141 140

import itertools as I;x=input();r=range;print[p for p in I.product(*map(r,map(len,x)))if all(x[i][p[i]]<=x[i+1][p[i+1]]for i in r(len(x)-1))]

Python has a useful itertools library that can generate permutations. This just iterates over all possible permutations of valid indices and checks whether they satisfy the criteria.

I think I can make this shorter, still working on it.

Edit: Now all one line for your reading (in)convenience!

\$\endgroup\$
  • \$\begingroup\$ r=range will save one character. \$\endgroup\$ – beary605 Sep 25 '12 at 23:17
  • \$\begingroup\$ Thanks for the tip. It never occurred to me that I can alias library functions. \$\endgroup\$ – scleaver Sep 26 '12 at 13:48
1
\$\begingroup\$

Python 120

f=lambda p,k=0:['%i '%j+m for j,v in enumerate(p[0])if v>=k for m in f(p[1:],v)]if p else['']
print'\n'.join(f(input()))

... still think, "enumerate" is a very long word.

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

GolfScript (44 chars)

~{.,,]zip}%{{`{+}+1$\/}%\;}*{2%.$=},{(;2%}%`

Same input and output format as Ilmari's entry.

Demo

Rough breakdown:

Map each input row into an array of pairs [value index]

{.,,]zip}%

Fold a Cartesian product over the rows

{{`{+}+1$\/}%\;}*

Filter to those whose 0th, 2nd, 4th, etc. entries are non-decreasing.

{2%.$=},

Map each one down to its 1st, 3rd, 5th, etc. entries.

{(;2%}%
\$\endgroup\$
0
\$\begingroup\$

Q, 43

{f(&)m~'(asc')m:x@'/:f:(cross/)(!:')(#:')x}
\$\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.