Array Sandwiches

Question

(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:

Test Case:

[[10, 20, 30], [1, 2, 3]]

Output:

Shortest code wins.

@IlmariKaronen: They will contain negative integers as well. — beary605, Commented Sep 23, 2012 at 21:08
@DavidCarraher: It's the next test case. I should make it more clear. — beary605, Commented Sep 23, 2012 at 22:50
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. — DavidC, Commented Sep 23, 2012 at 23:22

marinus · Accepted Answer · 2012-09-27 00:40:20Z

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)

Ilmari Karonen · Accepted Answer · 2012-09-25 12:54:10Z

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.

They must be seperated by whitespace, so spaces or tabs work as well. — beary605, Commented Sep 23, 2012 at 21:10

DavidC · Accepted Answer · 2021-02-12 03:10:07Z

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

I dislike this answer since you artificially simplify your answer by fixing the number arrays. — FUZxxl, Commented Sep 24, 2012 at 13:32
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. — DavidC, Commented Sep 24, 2012 at 13:49
@DavidC Why did you rollback my edit? Looks like the x_ /; etc. part is code and should be in a code block? — caird coinheringaahin g, Commented Feb 11, 2021 at 4:10

caird coinheringaahin g · Accepted Answer · 2021-02-10 21:58:31Z

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?

flodel · Accepted Answer · 2012-09-25 01:45:16Z

1

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))

answered Sep 25, 2012 at 1:45

flodel

2,40716 silver badges16 bronze badges

Add a comment |

scleaver · Accepted Answer · 2012-09-26 13:47:38Z

1

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!

edited Sep 26, 2012 at 13:47

answered Sep 25, 2012 at 14:28

scleaver

5072 silver badges5 bronze badges

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

Add a comment |

Daniel · Accepted Answer · 2012-09-26 22:07:16Z

1

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.

answered Sep 26, 2012 at 22:07

Daniel

1,8011 gold badge12 silver badges10 bronze badges

Add a comment |

Peter Taylor · Accepted Answer · 2012-10-02 08:49:06Z

1

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%}%

answered Oct 2, 2012 at 8:49

Peter Taylor

43.1k4 gold badges70 silver badges169 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2021-02-11 08:43:31Z

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)

naffetS · Accepted Answer · 2022-07-26 21:16:19Z

1

Vyxal, 10 bytes

vẏΠ'?¨£iÞṠ

Try it Online!

Port of Jelly.

answered Jul 26, 2022 at 21:16

naffetS

12.8k2 gold badges20 silver badges53 bronze badges

Add a comment |

tmartin · Accepted Answer · 2012-10-11 21:41:53Z

0

Q, 43

{f(&)m~'(asc')m:x@'/:f:(cross/)(!:')(#:')x}

answered Oct 11, 2012 at 21:41

tmartin

4,00815 silver badges16 bronze badges

Add a comment |

att · Accepted Answer · 2021-02-12 05:11:37Z

0

Wolfram Language (Mathematica), 30 bytes

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

Try it online!

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

answered Feb 12, 2021 at 5:11

att

21.7k2 gold badges16 silver badges62 bronze badges

Add a comment |

Leaf · Accepted Answer · 2022-07-27 01:11:26Z

0

JavaScript, 138 bytes

x=a=>(f=(a,p)=>a[0].flatMap((v,i)=>v<p?null:a[1]?(r=f(a.slice(1),v))&&r.map(j=>j&&[i,...j]):[[i]]))(a).map(i=>i?i.join(' ')+'\n':'').join('')

or more readable:

x = a => (f = (a, p) => a[0].flatMap(
  (v, i) => v<p
    ? null
    : a[1]
      ? (r = f(a.slice(1), v)) && r.map(j => j && [i, ...j])
      : [[i]]
  )
)(a).map(
  i => i
    ? i.join(' ') + '\n'
    : ''
).join('')

answered Jul 27, 2022 at 1:11

Leaf

5014 silver badges6 bronze badges

Add a comment |

Jonah · Accepted Answer · 2022-07-27 01:52:27Z

0

J, 22 bytes

#&>#:[:I.(-:/:~)@>@,@{

Try it online!

Takes input as boxed lists, as J does not allow heterogeneous arrays.

>@,@{ The open > of the flatten , of the Cartesian product {. This is just one big matrix whose rows are the elements of the Cartesian product.
(-:/:~)@ Which of those matches itself sorted? Returns a single 0-1 boolean list.
[:I. Indices of the ones.
#&>#: Convert to a mixed base number, where the bases are the lengths of the original input lists.

answered Jul 27, 2022 at 1:52

Jonah

33.8k4 gold badges40 silver badges94 bronze badges

Add a comment |

Stack Exchange Network

Array Sandwiches

14 Answers 14

APL (33)

GolfScript, 51 chars

Mathematica, 120 130 bytes

Edit

Usage

Explanation

Jelly, 10 bytes

How it works

R - 89 chars

Python, 149 141 140

Python 120

GolfScript (44 chars)

05AB1E, 20 bytes

Vyxal, 10 bytes

Q, 43

Wolfram Language (Mathematica), 30 bytes

JavaScript, 138 bytes

J, 22 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
array
or ask your own question.

Hot Network Questions

Array Sandwiches

14 Answers 14

APL (33)

GolfScript, 51 chars

Mathematica, 120 130 bytes

Edit

Usage

Explanation

Jelly, 10 bytes

How it works

R - 89 chars

Python, 149 141 140

Python 120

GolfScript (44 chars)

05AB1E, 20 bytes

Vyxal, 10 bytes

Q, 43

Wolfram Language (Mathematica), 30 bytes

JavaScript, 138 bytes

J, 22 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfarray or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
array
or ask your own question.