Inverting lists of lists of indices

Question

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],[2],[0],[0,2],[2],[0],[0]]
[[-1]] -> Undefined behavior, as all input numbers will be non-negative integers. 
[[0],[0],[],[0]] -> [[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.)

Answer 1

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

Answer 2

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

Answer 3

Pyth, 14 bytes

ms.e*]k/bdQS{s

Test suite.

Answer 4

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]
  

Answer 5

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.

Answer 6

JavaScript (ES6), 58 bytes

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

Answer 7

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}/}/`

Answer 8

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. [[] [] [] [0]].
}
:~    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.

Answer 9

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.

Answer 10

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

Answer 11

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

Answer 12

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