Inverser des listes de listes d'indices

14

Inspiré de ce post StackOverflow.

introduction

Le travail de Bob consiste à créer des feuilles de calcul et à les organiser. La façon dont il les organise est connue de très peu, à l'exception de Bob, mais il crée une liste de chacune des feuilles de calcul qui appartiennent au même groupe. Il y a un tas de données dans la feuille de calcul qu'il crée, mais il n'y a qu'une seule donnée que nous examinons en ce moment: le nombre de jours entre le jour où il a commencé ce travail et le jour où il a créé la feuille de calcul. Le premier jour, il a créé deux feuilles de calcul, les a notées 0et triées à leur emplacement approprié.

Maintenant, son patron demande un examen des types de feuilles de calcul qui se sont produits chaque jour, et c'est votre travail d'écrire du code qui va comprendre cela pour Bob; il a beaucoup trop de feuilles de calcul pour le faire à la main.

Contribution

Les informations de Bob qu'il vous donne se présentent sous la forme d'un tableau dentelé (indexé 0 ou 1) où chaque donnée est de la forme x = a[i][j]. aest ce que j'appelle le tableau dentelé lui-même, ile type de feuille de calcul et xla date de création du tableau. jest sans importance.

La tâche

Étant donné un tableau dentelé de jours de création de feuille de calcul organisés par leur type, renvoyez un tableau dentelé de types de feuille de calcul organisés par jour de création de feuille de calcul.

Exemples

Bob ne va pas simplement vous laisser avec ces données abstraites. Il m'a donné un sous-ensemble de certaines de ses feuilles de calcul pour vous aider à comprendre ce que tout est censé être.

Exemple d'entrée (indexé 0):

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

Exemple de sortie (avec commentaire, ce qui bien sûr n'est pas nécessaire):

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
]

Notez que Bob ne fait pas toujours deux feuilles de calcul tous les jours, et donc la sortie peut également être irrégulière. Mais il crée toujours au moins une feuille de calcul chaque jour, donc la sortie n'aura jamais besoin de contenir des tableaux vides - bien que si votre sortie a des tableaux vides à la fin, vous n'avez pas besoin de les supprimer.

Plus de cas de test:

[[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]]

Les listes internes de la sortie n'ont pas besoin d'être triées.

Comme toujours, aucune faille standard, et bien sûr le code le plus court gagne.

(Comme c'est ma première question, faites-moi savoir tout ce que je peux faire pour l'améliorer.)

Steven H.
la source
Bob ne pourrait-il pas faire des feuilles de calcul d'un certain type?
xnor
1
@xnor Non, Bob créera toujours une feuille de calcul tous les jours. Ces feuilles de calcul sont si cruciales pour le fonctionnement de l'entreprise que si Bob doit appeler un malade, une autre personne est temporairement affectée pour créer les feuilles de calcul du jour et Bob les organise le lendemain matin avant de créer ses propres feuilles de calcul.
Steven H.
1
@Dennis J'étais un peu fatigué lors de la mise en place de cet exemple, et je suppose que cela s'est montré. : P Fixe (les deux)!
Steven H.
6
Vous cherchez bien. C'est un très beau défi, d'autant plus qu'il s'agit de votre premier. :) Btw, au cas où vous ne seriez pas au courant, nous avons un bac à sable où la communauté peut fournir des commentaires avant de "mettre en ligne".
Dennis
1
J'ai édité dans une déclaration basée sur votre commentaire " Non, Bob créera toujours une feuille de calcul tous les jours ", mais maintenant que j'ai essayé d'optimiser ma propre réponse, je me suis rendu compte qu'elle est peut-être plus restrictive que ce que vous vouliez. Les tableaux vides de fin sont-ils autorisés? Par exemple, peut [[0 0]]donner une sortie [[0 0] []]?
Peter Taylor

Réponses:

5

Pyth, 13 octets

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

Essayez-le en ligne

Anders Kaseorg
la source
4

Brachylog , 28 octets

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

Explication

  • Prédicat principal, Input ( ?) = une liste de listes

    :1f.              Find all valid outputs of predicate 1 with ? as input
    
  • Prédicat 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
    
  • Prédicat 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]
    
Fatalize
la source
3

JavaScript (ES6), 58 octets

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

CJam ( 30 29 octets)

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

Démo en ligne

Curieusement, il est plus court de pirater Wque d'utiliser ee, principalement parce que je veux que l'index se retrouve de toute façon dans une variable. e]enregistré deux octets par rapport à la recherche de l'élément maximal met à l'initialisation d'un tableau de m+1tableaux vides.

Merci à Martin pour une économie d'un octet en stockant une valeur au Xlieu de la jongler autour de la pile.

NB Si les tableaux vides de fin sont autorisés, il existe une approche alternative de 29 octets en initialisant plutôt le tableau d'autant de jours vides qu'il y a de feuilles de calcul:

q~_e_,Ma*\{W):W;{_2$=W+t}/}/`
Peter Taylor
la source
3

CJam, 20 octets

Merci à Peter Taylor de m'avoir permis de baser ce code sur sa solution et d'avoir économisé 3 octets.

{ee::f{S*\+S/}:~:.+}

Un bloc sans nom qui attend l'entrée en haut de la pile et la remplace par la sortie.

Testez-le ici.

Explication

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.
Martin Ender
la source
2

Python 2, 82 octets

r=[];i=0
for t in input():
 for v in t:r+=[()]*-(~v+len(r));r[v]+=i,
 i+=1
print r

Testez-le sur Ideone .

Dennis
la source
2

Mathematica, 35 octets

Table[#&@@@#~Position~i,{i,Max@#}]&

Une fonction sans nom qui accepte et renvoie une liste irrégulière. Utilise des indices basés sur 1.

Heureusement, Maxaplatit automatiquement toutes ses entrées, ce qui nous donne l'index du dernier jour même si l'entrée est une liste irrégulière. Nous calculons ensuite simplement une liste d' #&@@@#~Position~iindices pour tous les jours i. Cette expression elle-même trouve la position de l' iintérieur de la liste irrégulière (retour sous forme de tableau d'indices à des profondeurs successives), donc les valeurs que nous voulons sont les premières valeurs de chacune de ces listes. #&@@@est une astuce de golf standard pour récupérer le premier élément de chaque sous-liste, en appliquant#& à chacune de ces sous-listes, qui est une fonction sans nom qui renvoie son premier argument.

Alternativement, nous pouvons définir un opérateur unaire pour le même nombre d'octets (en supposant un fichier source codé ISO 8859-1):

±n_:=#&@@@n~Position~#&~Array~Max@n
Martin Ender
la source
2

Java, 314 octets

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;

Détaillé

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;
}
Khaled.K
la source
1
En avez-vous vraiment besoin Map?
Leaky Nun
0

Perl 5, 48 octets

Un sous-programme:

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

Voyez-le en action comme ceci:

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])'
msh210
la source