23
\$\begingroup\$

The objective of this challenge is to take an array of positive integers, and enumerate its indices, grouping like elements.

An enumeration without any duplicates is done by just outputting an array of pairs (value, index), for example, [3, 4, 13, 9, 2] => [[3,1],[4,2],[13,3],[9,4],[2,5]].

However, if a given element appears a second time, it isn't given its own pair, but is instead added to the group of its first occurrence. If in our above example we replaced the 9 with 3, then in the output we would remove [9,4] and replace [3,1] with [3,1,4].

In the output, groups must be ordered by their first occurrence, and indices must be in ascending order. The element must be first in a group, before its indices. Output may be 0 or 1 indexed. You may assume the array has at least one element.

Test cases:

Input           | Output (One-indexed)
[3, 2, 2, 3]    | [[3, 1, 4], [2, 2, 3]]
[17]            | [[17, 1]]
[1, 1]          | [[1, 1, 2]]
[1, 1, 2]       | [[1, 1, 2], [2, 3]]
[1, 2, 3, 4]    | [[1, 1], [2, 2], [3, 3], [4, 4]]
[1, 1, 1, 1]    | [[1, 1, 2, 3, 4]]

This is , fewest bytes wins!

\$\endgroup\$
  • \$\begingroup\$ Would it be acceptable for the indides to be output as strings, e.g. [[17,"1"]]? (Don't know yet if I can save any bytes that way, still working on it!) \$\endgroup\$ – Shaggy Jan 19 '18 at 18:52
  • \$\begingroup\$ @shaggy sure, that's fine \$\endgroup\$ – Pavel Jan 19 '18 at 19:02
  • 3
    \$\begingroup\$ Possible duplicate. \$\endgroup\$ – totallyhuman Jan 19 '18 at 21:13
  • 1
    \$\begingroup\$ Can we output something like [[3, [1, 4]], [2, [2, 3]]] instead? \$\endgroup\$ – Conor O'Brien Jan 20 '18 at 1:09
  • 1
    \$\begingroup\$ @Pavel that's no reason :p but sure \$\endgroup\$ – Conor O'Brien Jan 20 '18 at 1:34

26 Answers 26

8
\$\begingroup\$

Dyalog APL, 5 bytes

(⊂,)⌸

Try it online!

,⌸ for 2 bytes almost works, but has trailing zeroes :/

\$\endgroup\$
  • \$\begingroup\$ What in the world does do? \$\endgroup\$ – Mr. Xcoder Jan 19 '18 at 17:34
  • \$\begingroup\$ @Mr.Xcoder gets the indexes of each thing and calls the left operator with the thing and indices where it exists \$\endgroup\$ – dzaima Jan 19 '18 at 17:36
  • \$\begingroup\$ Since the isue with ,⌸ is trailing zeroes, and zeroes will never be in the input, would it be possible to drop all zeroes in less than 3 bytes? \$\endgroup\$ – Pavel Jan 19 '18 at 17:41
  • \$\begingroup\$ @Pavel the reason that there are the zeroes is that the result is a matrix, which has to have exact dimensions, so there's only 1 byte for dropping the zeroes for any byte gain. I feel like this might be golfable though. \$\endgroup\$ – dzaima Jan 19 '18 at 17:44
  • 2
    \$\begingroup\$ "fancy af" array output format: Try it online! \$\endgroup\$ – Adám Jan 22 '18 at 10:00
7
\$\begingroup\$

J, 12 bytes

~.,&.><@I.@=

Zero-indexed.

Try it online!

If you can remove all of the work I'm doing with boxes, you can probably reduce the bytecount by quite a bit. I'm going to see if I can figure that out.

Explanation

This is probably too early to be explaining (there ought to be more golfs).

~. ,&.> <@I.@=
             =  Self-classify (comparison of each unique element to array)
            @   Composed with
          I.    Indices of ones (where it's equal)
         @      Composed with
        <       Boxed (how we deal with arrays of unequal length)
   ,&.>         Joined with
      >          Unbox each
   ,             Concatenate
    &.           Box again
~.              Unique elements
\$\endgroup\$
  • 2
    \$\begingroup\$ That array output format is fancy af \$\endgroup\$ – Pavel Jan 19 '18 at 17:23
  • \$\begingroup\$ @Pavel it's also taking a lot of bytes Π.Π \$\endgroup\$ – cole Jan 19 '18 at 17:23
5
\$\begingroup\$

05AB1E, 10 bytes

ÙεDIQƶ0K)˜

Try it online!

Explanation

Ù             # remove duplicates
 ε            # apply to each element
  D           # duplicate
   IQ         # compare for equality with input
     ƶ        # multiply each element by its index (1-based)
      0K      # remove zeroes
        )˜    # wrap in a flattened list
\$\endgroup\$
5
\$\begingroup\$

Python 3, 83 82 bytes

-1 byte thanks to Mego

lambda x:[[n]+[j for j,m in enumerate(x)if m==n]for n in sorted({*x},key=x.index)]

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ j+1 -> j (indices may be zero-indexed) \$\endgroup\$ – Mego Jan 19 '18 at 17:30
5
\$\begingroup\$

Haskell, 48 bytes

import Data.List
f l=nub[k:elemIndices k l|k<-l]

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Attache, 15 bytes

Flat=>Positions

Try it online!

This is an interesting case of =>, the operator form of Map. When given two functional arguments f and g, Map returns a function f => g[x] over x. That is, the RHS is applied to the input, then the LHS is mapped.

The builtin Positions generates an array representing the grouping of entries by indices. By default, when not supplied with a second argument, Positions will use the first argument. Flat is then mapped over each item, as that is what the question requires.

Alternative solutions

31 bytes

MapArgs[Concat#~Indices,Unique]

Try it online!

A pretty short, builtin-less alternative. MapArgs is a function like Map, except you can feed extra arguments into it. For example, MapArgs[{_1 + _2}, 1..3, 3] is [4, 5, 6]. Like Map, it becomes curried when supplied with two functional arguments. The function be mapped is Concat#~Indices, which is a fork. This fork is applied to the Unique items of the input and the input itself. This translates to Concat[_, Indices[_2, _]] (with the arguments of Indices swapped through ~), which pairs the element being mapped (_) with the indices of said element _ in the input array, which is _2 (as ffed through MapArgs).

43 bytes

{Flat=>Zip[Unique[_],Indices[_,Unique[_]]]}

Try it online!

This is really just a more verbose (yet a tad more readable) combination of solutions #1 and #2.

\$\endgroup\$
4
\$\begingroup\$

Jelly, 6 bytes

Q;"ĠṢ$

Try it online!

Explanation:

Q;"ĠṢ$
Q      Keep the first occurrence of each element
     $ Last two links as a monad
   Ġ    Group indices of equal elements, then sort the resulting list of groups by the element they point to
    Ṣ   Sort; used to re-order the list of groups based on first occurrence instead
  "    Vectorize link between two arguments (the first occurrences and the group list)
 ;      Concatenate
\$\endgroup\$
  • \$\begingroup\$ Doesn't work for the last test case. The array should be nested another layer, the output is alway two-dimensional. \$\endgroup\$ – Pavel Jan 19 '18 at 17:13
  • \$\begingroup\$ @Pavel yes it does, I just forgot to add a footer (answer is a function) \$\endgroup\$ – Erik the Outgolfer Jan 19 '18 at 17:14
  • \$\begingroup\$ Ok then, cool. Explanation soon, yes? :P \$\endgroup\$ – Pavel Jan 19 '18 at 17:16
  • \$\begingroup\$ @Pavel added explanation \$\endgroup\$ – Erik the Outgolfer Jan 19 '18 at 17:19
4
\$\begingroup\$

Pyth, 7 bytes

0-indexed.

{+VQxRQ

Try it here! Alternative.

How?

{+VQxRQ – Full program.

     RQ – For each element...
    x   – Get all its indices.
 +V     – And apply vectorised concatenation.
   Q    – With the input.
{       – Deduplicate.
\$\endgroup\$
4
\$\begingroup\$

MATL, 8 bytes

u"@tG=fh

Try it at MATL Online

Explanation

        # Implicitly get the input
u       # Compute the unique values
"       # For each unique value, N
  @     # Push the value N to the stack
  t     # Duplicate N
  G     # Grab the input
  =f    # Get the 1-based indices of the elements that equal N
  h     # Horizontally concatenate N with the indices
        # Implicitly display the result
\$\endgroup\$
  • \$\begingroup\$ ooooohhh that's clever! I had like 18 bytes trying to use &f but never did get it to work. \$\endgroup\$ – Giuseppe Jan 20 '18 at 14:57
3
\$\begingroup\$

Actually, 24 bytes

;;╗⌠╝╜r⌠╜E╛=⌡░⌡M@Z⌠♂i⌡M╔

Try it online!

Explanation:

;;╗⌠╝╜r⌠╜E╛=⌡░⌡M@Z⌠♂i⌡M╔
;;                        make two copies of input
  ╗                       save a copy to register 0
   ⌠╝╜r⌠╜E╛=⌡░⌡M          map over input:
    ╝                       save the element in register 1
     ╜r                     indices for input
       ⌠╜E╛=⌡░              filter:
        ╜E                    element in input at index
          ╛=                  equals element for outer map (from register 1)
                @Z        swap, zip input with map result
                  ⌠♂i⌡M   flatten each element in zipped list
                       ╔  uniquify
\$\endgroup\$
3
\$\begingroup\$

R, 56 bytes

function(x)lapply(unique(x),function(y)c(y,which(x==y)))

Try it online!


This is my first attempt at codegolf, so any feedback is welcome!

\$\endgroup\$
  • 3
    \$\begingroup\$ Welcome to PPCG! Nice first answer. \$\endgroup\$ – Pavel Jan 19 '18 at 18:39
  • 1
    \$\begingroup\$ Hey there Florian! Very nice answer. This is actually a snippet rather than a program or function -- it assumes the input is hardcoded into x, but there has to be a way of reading input -- typically we use scan or define a function. Additionally, it has to output, so'd have to wrap this in a print or a cat. \$\endgroup\$ – Giuseppe Jan 19 '18 at 19:03
  • 1
    \$\begingroup\$ see this question for more handy R golfing tricks :) \$\endgroup\$ – Giuseppe Jan 19 '18 at 19:17
  • 1
    \$\begingroup\$ Thanks guys! And the link to the r tips is certainly useful! \$\endgroup\$ – Florian Jan 19 '18 at 19:24
  • 2
    \$\begingroup\$ @Florian R isn't so bad as you think (except on string challenges...) so long as you remember you're golfing against other R golfers! Feel free to ping me in chat if you have questions. There's a couple of R golfers who are active, and they'll definitely offer suggestions, and appreciate yours as well! Welcome to golfing :) \$\endgroup\$ – Giuseppe Jan 19 '18 at 20:38
3
\$\begingroup\$

Wolfram Language (Mathematica), 40 bytes

Saved a byte thanks to Martin Ender.

KeyValueMap[{#,##&@@#2}&]@*PositionIndex

Try it online!

\$\endgroup\$
  • \$\begingroup\$ How does @*PositionIndex work? \$\endgroup\$ – Pavel Jan 19 '18 at 17:46
  • \$\begingroup\$ @Pavel @* is composition of functions. PositionIndex basically does all the job, but returns an association instead of a list. \$\endgroup\$ – alephalpha Jan 19 '18 at 17:52
  • 1
    \$\begingroup\$ {#,##&@@#2}& saves a byte. \$\endgroup\$ – Martin Ender Jan 19 '18 at 18:02
3
\$\begingroup\$

JavaScript (ES6), 64 bytes

0 indexed

a=>a.map((v,i)=>a[-v]?a[-v].push(i):a[-v]=[v,i]).filter(x=>x[0])

Note, this assume input numbers being positive, so v > 0

Test slightly modified (1 indexed) to match the test cases

var F=
a=>a.map((v,i)=>a[-v]?a[-v].push(i+1):a[-v]=[v,i+1]).filter(x=>x[0])

test = [ // output 1 indexed
  [3, 2, 2, 3],//    | [[3, 1, 4], [2, 2, 3]]
  [17], //           | [[17, 1]]
  [1, 1], //         | [[1, 1, 2]]
  [1, 1, 2], //      | [[1, 1, 2], [2, 3]]
  [1, 2, 3, 4], //   | [[1, 1], [2, 2], [3, 3], [4, 4]]
  [1, 1, 1, 1] //    | [[1, 1, 2, 3, 4]] 
]

test.forEach(t => {
  x = F(t)
  console.log(JSON.stringify(t)+ ' -> ' + JSON.stringify(x))
})

\$\endgroup\$
3
\$\begingroup\$

APL NARS, 24 bytes, 12 chars

{∪⍵,¨⍸¨⍵=⊂⍵}

-4 bytes thanks to Adam test:

  f←{∪⍵,¨⍸¨⍵=⊂⍵}

  ⎕fmt f 3 2 2 3
┌2────────────────┐
│┌3─────┐ ┌3─────┐│
││ 3 1 4│ │ 2 2 3││
│└~─────┘ └~─────┘2
└∊────────────────┘
  ⎕fmt f 17
┌1──────┐
│┌2────┐│
││ 17 1││
│└~────┘2
└∊──────┘
  ⎕fmt f 1 1
┌1───────┐
│┌3─────┐│
││ 1 1 2││
│└~─────┘2
└∊───────┘
  ⎕fmt f 1 2 3 4
┌4──────────────────────────┐
│┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐│
││ 1 1│ │ 2 2│ │ 3 3│ │ 4 4││
│└~───┘ └~───┘ └~───┘ └~───┘2
└∊──────────────────────────┘
  ⎕fmt f 1 1 1 1
┌1───────────┐
│┌5─────────┐│
││ 1 1 2 3 4││
│└~─────────┘2
└∊───────────┘
\$\endgroup\$
  • \$\begingroup\$ Shave a 4 bytes/2 chars: {∪⍵,¨⍸¨⍵=⊂⍵} \$\endgroup\$ – Adám Jan 22 '18 at 11:04
3
\$\begingroup\$

SWI-Prolog, 165 117 bytes

-48 bytes thanks to Prolog golfing tips.

h(I):-I+[]-1.
[H|T]+R-N:-(select([H|A],R,[H|L],S),!,append(A,[N],L);append(R,[[H,N]],S)),O is N+1,(T+S-O,!;write(S)).

Try it online!

Explanation

% The predicate that prints the grouped duplicates. It's a wrapper because we
% need some extra arguments to keep state:
enumerate_duplicates(Input) :- enumerate(Input, [], 1).

% In the golfed code, operators are used to represent this predicate.
% See https://codegolf.stackexchange.com/a/153160
% Go through the input, build up the result on the way and print it.
enumerate([Head|Tail], Result, Index) :-
    (
        % If our current Result already contains a list that starts with the
        % current first element in our input, Head, NewIndexes will become the
        % new "tail" of that list in our next result list:
        select([Head|OldIndexes], Result, [Head|NewIndexes], NextResult),
        % Don't backtrack before this if goals below this fail:
        !,
        % The as-yet-unknown NewIndexes above should in fact be the same as
        % OldIndexes with our current Index appended:
        append(OldIndexes, [Index], NewIndexes)
    % Use ; instead of separate predicate rules.
    % See https://codegolf.stackexchange.com/a/67032
    ;
        % If our current Result did not already contain Head, append a new list
        % for it with the current index:
        append(Result, [[Head, Index]], NextResult)
    ),
    % Increment our index counter:
    NextIndex is Index + 1,
    (
        % And continue with the rest of our input:
        enumerate(Tail, NextResult, NextIndex),
        % Don't backtrack if the above succeeded:
        !
    ;
        % If Tail is no longer a multi-element list, we're done. Print:
        write(NextResult)
    ).
\$\endgroup\$
3
\$\begingroup\$

K (oK), 10 bytes

Solution:

(!x),'.x:=

Try it online!

Examples:

(!x),'.x:=,17
,17 0
(!x),'.x:=1 1
,1 1 2
(!x),'.x:=1 0 1
(1 1 2
2 3)
(!x),'.x:=1 2 3 4
(1 0
2 1
3 2
4 3)

Explanation:

Evaluation is performed right-to-left. I still think this is golf-able further...

(!x),'.x:= / the solution
         = / group input into dictionary, item!indices
       x:  / save as variable x
      .    / value of x (the indices)
    ,'     / concatenate (,) each-both (') with
(  )       / do this together
 !x        / the key of x (i.e. the items)

Notes:

  • 14 bytes without declaring x, (,/)'+(!;.)@'=, gave up with this approach...
\$\endgroup\$
  • 1
    \$\begingroup\$ You may return 0-indexed result, so I think you can skip the 1+. \$\endgroup\$ – Adám Jan 22 '18 at 11:06
2
\$\begingroup\$

Julia 0.6, 37 bytes

Thanks to Pavel for 1 byte off.

y->[[x;findin(y,[x])]for x=unique(y)]

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Remove the space between ] and for for -1 byte. \$\endgroup\$ – Pavel Jan 19 '18 at 18:02
2
\$\begingroup\$

JavaScript (ES6), 68 bytes

0-indexed.

a=>a.map(p=(x,i)=>1/p[x]?b[p[x]].push(i):b.push([x,p[x]=i]),b=[])&&b

Test cases

let f =

a=>a.map(p=(x,i)=>1/p[x]?b[p[x]].push(i):b.push([x,p[x]=i]),b=[])&&b

console.log(JSON.stringify(f([3, 4, 13, 9, 2]))) // [[3,0],[4,1],[13,2],[9,3],[2,4]]
console.log(JSON.stringify(f([3, 4, 13, 3, 2]))) // [[3,0,3],[4,1],[13,2],[2,4]]
console.log(JSON.stringify(f([3, 2, 2, 3]    ))) // [[3,0,3],[2,1,2]]
console.log(JSON.stringify(f([17]            ))) // [[17,0]]
console.log(JSON.stringify(f([1, 1]          ))) // [[1,0,1]]
console.log(JSON.stringify(f([1, 1, 2]       ))) // [[1,0,1],[2,2]]
console.log(JSON.stringify(f([1, 2, 3, 4]    ))) // [[1,0],[2,1],[3,2],[4,3]]
console.log(JSON.stringify(f([1, 1, 1, 1]    ))) // [[1,0,1,2,3]]

\$\endgroup\$
  • \$\begingroup\$ Input numbers are != 0, that could be useful to avoid the 1/x trick \$\endgroup\$ – edc65 Jan 20 '18 at 17:21
2
\$\begingroup\$

PHP 4.1, 88 bytes

Yeah, it is pretty long.

This assumes a default php.ini file (short_open_tag = On and register_globals = On).

<?foreach($A as$k=>$v){!$b[$v]&&$b[$v]=array($v);$b[$v][]=$k;}print_r(array_values($b));

This presents the array in an human-readable way.
The values can be passed by POST, GET and COOKIE, inside the key "A".


For a modern version, one can use (90 bytes):

<?foreach($_GET[A]as$k=>$v){if(!$b[$v])$b[$v]=[$v];$b[$v][]=$k;}print_r(array_values($b));

The result is the same, except all values have to be passed over GET parameters inside the key "A".

\$\endgroup\$
2
\$\begingroup\$

Perl 6,  63  61 bytes

*.pairs.classify(*.value).map({.key,|.value».key}).sort(*.[1])

Test it (0-based)

{sort *.[1],map {.key,|.value».key},classify *.value,.pairs}

Test it (0-based same algorithm)

Expanded:

# WhateverCode lambda (this is the parameter) 
*\                                            # [3,2,2,3]

# get a list of Pairs (zero based index => value)
.pairs                                        # (0=>3,1=>2,2=>2,3=>3)

# classify based on the values (unordered result)
.classify(*.value)                            # {2=>[1=>2,2=>2],3=>[0=>3,3=>3]}

# simplify the structure
.map({
  .key,         # the value
  |.value».key  # slip in the indexes
})                                            # ((3,0,3),(2,1,2))

# sort based on first index
.sort(*.[1])
\$\endgroup\$
2
\$\begingroup\$

Japt, 14 9 bytes

0-indexed.

â £ð¶X iX

Try it

â £ð¶X iX
â             :Deduplicate
  £           :Map each X
   ð          :  Get 0-based indices of elements in the input
    ¶X        :    That are equal to X
       iX     :  Prepend X
\$\endgroup\$
1
\$\begingroup\$

Clean, 61 60 bytes

import StdEnv,StdLib
$l=removeDup[[e:elemIndices e l]\\e<-l]

Try it online!

Output is 0-indexed

\$\endgroup\$
1
\$\begingroup\$

Kotlin, 83 bytes

{it.mapIndexed{i,c->c to i}.groupBy({(a,b)->a},{(a,b)->b}).map{(a,b)->listOf(a)+b}}

Beautified

{
    it.mapIndexed { i, c -> c to i }
        .groupBy({ (a, b) -> a }, { (a, b) -> b })
        .map { (a, b) -> listOf(a) + b }
}

Test

var f: (List<Int>) -> List<List<Int>> =
{it.mapIndexed{i,c->c to i}.groupBy({(a,b)->a},{(a,b)->b}).map{(a,b)->listOf(a)+b}}

data class Test(val input: List<Int>, val output: List<List<Int>>)

val tests = listOf(
        Test(listOf(3, 2, 2, 3), listOf(listOf(3, 0, 3), listOf(2, 1, 2))),
        Test(listOf(17), listOf(listOf(17, 0))),
        Test(listOf(1, 1), listOf(listOf(1, 0, 1))),
        Test(listOf(1, 1, 2), listOf(listOf(1, 0, 1), listOf(2, 2))),
        Test(listOf(1, 2, 3, 4), listOf(listOf(1, 0), listOf(2, 1), listOf(3, 2), listOf(4, 3))),
        Test(listOf(1, 1, 1, 1), listOf(listOf(1, 0, 1, 2, 3)))
)

fun main(args: Array<String>) {
    for (c in tests) {
        val o = f(c.input)
        if (o != c.output) {
            throw AssertionError("${c.input} -> $o != ${c.output}")
        }
    }
}

TIO

TryItOnline

\$\endgroup\$
  • \$\begingroup\$ This sollution is a snippet, not a complete function or program. It requires the variable i to be predefined. You can make this valid by converting it to a lambda that takes a parameter i. \$\endgroup\$ – Pavel Jan 20 '18 at 23:50
  • \$\begingroup\$ Reworked to solve issue raised by @Pavel \$\endgroup\$ – jrtapsell Jan 21 '18 at 0:26
1
\$\begingroup\$

Swift 4, 107 bytes

... Yikes.

{a in Dictionary(grouping:a.enumerated()){$0.1}.sorted{$0.1.first!.0<$1.1.first!.0}.map{[$0]+$1.flatMap{$0.0}}}

Ungolfed:

let f = { (input: [Int]) -> [[Int]] in
    return Dictionary(grouping: input.enumerated(), by: { $0.element })
        .sorted { pairA, pairB in // Sort by order of first appearence (lowest offset)
            return pairA.value.first!.offset < pairB.value.first!.offset
        }.map { element, pairs in
            return [element] + pairs.map{ $0.offset /* +1 */} // add 1 here for 1 based indexing
        }
}

It's too bad that dictionary loses ordering, forcing me to waste so many characters on sorting back again. This sort of abuse of implicit closure arguments ($0, $1, ...) and implicit tuple members (.0, .1, ...) is uhhhhh not pretty.

\$\endgroup\$
1
\$\begingroup\$

Perl 5, 63 + 1 (-a) = 64 bytes

map$k{$_}.=$".++$i,@F;say$_.$k{$_}for sort{$k{$a}-$k{$b}}keys%k

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Ruby, 54 52 bytes

->a{a.map{|i|[i]+(0..a.size).select{|j|a[j]==i}}|[]}

This version allows nil (53 bytes):

->a{a.map{|i|[i]+(0...a.size).select{|j|a[j]==i}}|[]}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ The challenge specifies the array will only contain positive integers, and there will be at least one element. nil is not a positive integer. \$\endgroup\$ – Pavel Jan 20 '18 at 23:47
  • \$\begingroup\$ @Pavel thanks, I checked but missed it somehow \$\endgroup\$ – Asone Tuhid Jan 20 '18 at 23:59

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.