9
\$\begingroup\$

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

You have several arrays, named \$A_1, A_2, ... , A_n\$, each sorted in ascending order. Every item in the array will be a 32-bit integer.

A sandwich is a set of indices \$j_1, j_2, ... , j_n\$ such that \$A_1[j_1] ≤ A_2[j_2] ≤ ... ≤ A_n[j_n]\$. \$A_i[0]\$ is the first element of \$A_i\$.

Given some arrays, output every possible sandwich that you can have from those arrays, separated 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 separated 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\$
7
  • 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

11 Answers 11

3
\$\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\$

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\$
2
  • \$\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
3
\$\begingroup\$

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

\$\endgroup\$
5
  • \$\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
  • 1
    \$\begingroup\$ @DavidC Why did you rollback my edit? Looks like the x_ /; etc. part is code and should be in a code block? \$\endgroup\$ – caird coinheringaahing Feb 11 at 4:10
  • \$\begingroup\$ you are right. I rolled back to your version. \$\endgroup\$ – DavidC Feb 12 at 3:11
2
\$\begingroup\$

Jelly, 10 bytes

J€Œpị"ṢƑ¥Ƈ

Try it online!

This uses 1-indexing which is the default for Jelly. +2 bytes to use 0-indexing.

How it works

J€Œpị"ṢƑ¥Ƈ - Main link. Takes a 2d array A on the left
 €         - Over each subarray:
J          -   Replace the subarray with its indices
  Œp       - Take the Cartesian product of these indices
        ¥Ƈ - Keep the indices for which the following is true:
    ị"     -   Index into each subarray of A
      ṢƑ   -   The resulting elements are in ascending order?
\$\endgroup\$
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\$
2
  • \$\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\$
1
\$\begingroup\$

05AB1E, 20 bytes

εεN].«â€˜ʒεINèsè}¥dP

Indexing into matrices is not 05AB1E's strong suit.. :/

Try it online.

Explanation:

εεN]         #Transform the input to a list of lists of indices:
ε            # Map over each list of the (implicit) input-list:
 ε           #  Map over each inner value in this list:
  N          #   Push the map-index
   ]         # Close both maps

.«â€˜        #Create all combinations of the indices in each list:
.«           # Left-reduce the list of lists by:
  â          #  Taking the cartesian product
   €         # Then map over each inner list of nested lists:
    ˜        #  And flatten the values to a single list

ʒεINèsè}¥dP  #Filter to keep just the indices that are in ascending order
ʒ            # Filter the list of lists of indices by:
 ε           #  Map over each index:
  INè        #   Use the map-index itself to index into the input list of lists
     sè      #   Then use the index we're mapping over to index into this list
       }¥    #  After the map: get all the deltas / forward differences
         d   #  Check for each that they're non-negative (>=0)
          P  #  And check if this is truthy for all of them
             # (after the filter, the result is output implicitly)
\$\endgroup\$
0
\$\begingroup\$

Q, 43

{f(&)m~'(asc')m:x@'/:f:(cross/)(!:')(#:')x}
\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 30 bytes

#<=##&~Outer~##~Position~True&

Try it online!

Returns 1-indexed. For 0-indexing, add -1 (+2 bytes).

\$\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.