# Inverting lists of lists of indices

Inspired by this StackOverflow post.

# Introduction

Bob's job is to create spreadsheets and organize them. The way he organizes them is known to very few except for Bob, but he creates a list of each of the spreadsheets that fall under the same group. There's a bunch of data in the spreadsheet he creates, but there's only one piece of data that we're looking at right now: The number of days between the day he started this job and the day he made the spreadsheet. The first day he created two spreadsheets, noted them both as 0 and sorted them in to their proper locations.

Now, his boss is asking for a review of what kinds of spreadsheet happened each day, and it's your job to write some code that will figure that out for Bob; he has far too many spreadsheets to do it by hand.

## Input

Bob's info that he gives you comes in the form of a (0-or-1 indexed) jagged array where each datum is of the form x = a[i][j]. a is what I'm calling the jagged array itself, i is the type of spreadsheet, and x is the date the array was created. j is unimportant.

## The task

Given a jagged array of spreadsheet creation days organized by their type, return a jagged array of spreadsheet types organized by spreadsheet creation day.

## Examples

Bob isn't going to just leave you with this abstract data. He's given me a subset of some of his spreadsheets to help you out with figuring out what everything is supposed to be.

Example input (0-indexed):

a = [
[3,2,5,0], # Bob doesn't necessarily sort his lists
[1,3],
[2,1,0,4],
[4,5,3],
[6,6]
]


Example output (with commentary, which of course is not required):

output = [
[0,2] # On day 0, Bob made one type 0 and one type 2 spreadsheet
[1,2] # On day 1, Bob made one type 1 and one type 2 spreadsheet
[0,2] # On day 2, Bob made one type 0 and one type 2 spreadsheet
[0,1,3] # On day 3, Bob made one type 0, one type 1, and one type 3 spreadsheet
[2,3] # On day 4, Bob made one type 2 and one type 3 spreadsheet
[0,3] # On day 5, Bob made one type 0 and one type 3 spreadsheet
[4,4] # On day 6, Bob made two type 4 spreadsheets
]


Note that Bob doesn't always make two spreadsheets every day, and so the output may be jagged as well. But he always makes at least one spreadsheet every day, so the output will never need to contain empty arrays - although if your output has empty arrays at the end, you don't need to remove them.

More test cases:

[[3,5,6,2],[0,0,0],[1,0,3,4]] -> [[1,1,1,2],,,[0,2],,,]
[[-1]] -> Undefined behavior, as all input numbers will be non-negative integers.
[,,[],] -> [[0,1,3]]


The output's inner lists do not need to be sorted.

As always, no standard loopholes, and of course shortest code wins.

(As this is my first question, please let me know of anything I can do to improve it.)

• Might Bob make no spreadsheets of some type? – xnor Jul 19 '16 at 23:46
• @xnor No, Bob will always create a spreadsheet every day. These spreadsheets are so crucial to the operation of the company that if Bob has to call in sick, another person is temporarily posted to create that day's spreadsheets and Bob organizes them the next morning before creating his own spreadsheets. – Steven H. Jul 20 '16 at 0:16
• @Dennis I was a little tired when putting that example together, and I guess it showed. :P Fixed (both)! – Steven H. Jul 20 '16 at 5:52
• Looking good. This is a very nice challenge, especially considering that it's your first. :) Btw, in case you're not aware, we have a sandbox where the community can provide feedback before "going live". – Dennis Jul 20 '16 at 5:57
• I edited in a statement based on your comment "No, Bob will always create a spreadsheet every day", but now that I've tried optimising my own answer I've realised that it's possibly more restrictive than you intended. Are trailing empty arrays permitted? E.g. can [[0 0]] give output [[0 0] []]? – Peter Taylor Jul 20 '16 at 8:36

# Jelly, 11 10 bytes

FṀ⁸ċþµJ€x"


Input and output are 1-based.

Try it online! or verify all test cases (0-based for easy comparison).

# Pyth, 13 bytes

eMM.ghkSs,RVU

,RV      vectorized right map of pair, over:
UQ      [0, …, len(input) - 1] and
Q     input
(this replaces each date with a [date, type] pair)
s         concatenate
S          sort
.ghk           group by first element (date)
eMM               last element (type) of each sublist


Try it online

# Pyth, 14 bytes

ms.e*]k/bdQS{s


Test suite.

# Brachylog, 28 bytes

:1f.
cdo:Im:?:2f.
t:.m:Im~h?


### Explanation

• Main predicate, Input (?) = a list of lists

:1f.              Find all valid outputs of predicate 1 with ? as input

• Predicate 1:

c                 Concatenate the list of lists into a single list
do               Remove duplicates and sort
:Im            Take the Ith element of that sorted list
:?:2f.      Find all valid outputs of predicate 2 with [Element:?] as input

• Predicate 2:

t:.m              Take the (Output)th element of the list of lists
:Im           Take the Ith element of that list
~h?        This element is the element of the input [Element:List of lists]


# Lua, 114 bytes

r={}for i,t in ipairs(...)do for _,v in ipairs(t)do if r[v] then r[v][#r[v]+1]=i else r[v]={i}end end end return r


Ideone it!

Inspired by Dennis' answer in Python 2.

## JavaScript (ES6), 58 bytes

a=>a.map((b,i)=>b.map(j=>(r[j]=r[j]||[]).push(i)),r=[])&&r


## CJam (30 29 bytes)

Mq~{W):W;{:X)Me]_X=W+X\t}/}/


Online demo

Curiously it's shorter to hack around with W than to use ee, mainly because I want the index to end up in a variable anyway. e] saved two bytes over first finding the maximum element m and initialising an array of m+1 empty arrays.

Thanks to Martin for a one-byte saving by storing a value in X instead of juggling it around the stack.

NB If trailing empty arrays are permitted, there's alternative 29-byte approach by instead initialising the array of as many empty days as there are spreadsheets:

q~_e_,Ma*\{W):W;{_2$=W+t}/}/  ## CJam, 20 bytes Thanks to Peter Taylor for letting me base this code on his solution and saving 3 bytes. {ee::f{S*\+S/}:~:.+}  An unnamed block which expects the input on top of the stack and replaces it with the output. Test it here. ### Explanation ee e# Enumerate the input. E.g. if the input is e# [[3 5 6 2] [0 0 0] [1 0 3 4]] e# this gives: e# [[0 [3 5 6 2]] [1 [0 0 0]] [2 [1 0 3 4]]] ::f{ e# The exact details of how this works are a bit tricky, but in effect e# this calls the subsequent block once for every spreadsheet and e# its correspond index, so the first time we'll have 0 and 3 on the e# stack, the next time 0 5, and at the last iteration 2 and 4. e# Note that this is a map operation, so we'll end up with an array e# on the stack. S* e# So the stack holds [... index date] now. We start by creating e# a string of 'date' spaces, so " " on the first iteration. \+ e# We swap this with the index and append the index. S/ e# Now we split this thing on spaces, which gives us 'date' empty e# lists and a list containing the index, e.g. [[] [] [] ]. } :~ e# This flattens the first level of the result, so that we get a list e# of all those lists we just created. This is simply one list for e# every spreadsheet with its type in the last element. :.+ e# Finally we fold pairwise concatenation over this list. All the e# empty lists won't affect the result so we'll just end up with all e# the types in lists for the correct date.  # Python 2, 82 bytes r=[];i=0 for t in input(): for v in t:r+=[()]*-(~v+len(r));r[v]+=i, i+=1 print r  Test it on Ideone. ## Mathematica, 35 bytes Table[#&@@@#~Position~i,{i,Max@#}]&  An unnamed function which accepts and returns a ragged list. Uses 1-based indices. Thankfully Max automatically flattens all its inputs, so this gets us the last day index even though the input is a ragged list. We then simply compute a list of #&@@@#~Position~i for all day indices i. This expression itself finds the position of i inside the ragged list (return as an array of indices at successive depths), so the values we want are the first values of each of those lists. #&@@@ is a standard golfing trick to retrieve the first element from every sublist, by applying #& to each of those sublists, which is an unnamed function that returns its first argument. Alternatively, we can define a unary operator for the same byte-count (assuming an ISO 8859-1 encoded source file): ±n_:=#&@@@n~Position~#&~Array~Max@n  # Java, 314 bytes int[][]f(int[][]n){int w=0;Map<Integer,List<Integer>>m=new TreeMap<>();for(int i=0;i<n.length;i++)for(Integer x:n[i]){if(m.get(x)==null)m.put(x,new ArrayList<>());m.get(x).add(i);w=x>w?x:w;}int[][]z=new int[w+1][];for(int i=0,j;i<w+1;i++){z[i]=new int[m.get(i).size()];j=0;for(int x:m.get(i))z[i][j++]=x;}return z;  Detailed public static Integer[][] f(Integer[][]n) { int w=0; Map<Integer,List<Integer>>m=new TreeMap<>(); for(int i=0;i<n.length;i++) { for(Integer x : n[i]) { if(m.get(x)==null) m.put(x,new ArrayList<Integer>()); m.get(x).add(i); w=x>w?x:w; } } Integer[][]z=new Integer[w+1][]; for(int i=0,j; i<w+1; i++) { z[i]=new Integer[m.get(i).size()]; j=0;for(Integer x : m.get(i))z[i][j++]=x; } return z; }  • Do you really need Map? – Leaky Nun Jul 20 '16 at 9:45 # Jelly, 9 bytes œẹⱮFṀ$Ḣ€€


Try it online!

Input and output is 1-indexed, the Footer converts from 0-indexing to 1-indexing and back for I/O purposes.

## How it works


œẹⱮFṀ$Ḣ€€ - Main link. Takes a 2D array, a, on the left$    - To a:
F      -   Flatten
Ṁ     -   Maximum
Ɱ       - Over each number i in [1, 2, ..., max(flat(a))]:
œẹ        -   Get the multidimensional indices of i in a
This returns [x, y] for each occurrence of i in a
where x is the index of the array in a in which i is in
and y is the index of i in that array. For example

[[1,2,3],[4,5,6],[7,8,9]] œẹ 7 = [[3,1]]

as 7 is in the 3rd subarray at index 1 (using 1 indexing)

Ḣ€€ - Extract the x values only and return them


# Perl 5, 48 bytes

A subroutine:

{for$i(0..@_){map{push@{$b[$_]},$i}@{$_[$i]}}@b}


See it in action like this:

perl -e'print "@$_$/" for sub{for$i(0..@_){map{push@{$b[$_]},$i}@{$_[$i]}}@b}->([3,2,5,0],[1,3],[2,1,0,4],[4,5,3],[6,6])'