# Generate a congruent list with the smallest sum

Two lists A and B are congruent if they have the same length, and elements that compare equal in A compare equal in B.

In other words, given any two valid indices x and y:

• If A[x] = A[y], then B[x] = B[y].
• If A[x] != A[y], then B[x] != B[y].

For example, the lists [1, 2, 1, 4, 5] and [0, 1, 0, 2, 3] are congruent.

Given a nonempty list of nonnegative integers A, return a new list of nonnegative integers B such that is congruent to A, while minimizing the sum of the integers in B.

There are potentially many possible valid outputs. For example, in the list [12, 700, 3], any permutation of [0, 1, 2] would be considered valid output.

## Test Cases

Format:
input ->
one possible valid output

[1 2 1 4 5] ->
[0 1 0 2 3] (this is the example given above)

[3 2 2 1 5 7 2] ->
[1 0 0 2 3 4 0]

[8 8 8 8 8] ->
[0 0 0 0 0]

[2] ->
[0]

[8 6 8 4 6 8 2 4 6 8 0 2 4 6 8] ->
[0 1 0 2 1 0 3 2 1 0 4 3 2 1 0]

[14 1] ->
[1 0]

[19 6 4 9 14 17 10 9 6 14 8 14 6 15] ->
[8 0 3 2 1 7 5 2 0 1 4 1 0 6]

[15] ->
[0]

[1 18 4 8 6 19 12 17 6 13 7 6 8 1 6] ->
[1 8 3 2 0 9 5 7 0 6 4 0 2 1 0]

[9 10 11 9 7 11 16 17 11 8 7] ->
[2 4 0 2 1 0 5 6 0 3 1]

[1 3 16 19 14] ->
[0 1 3 4 2]

[18 8] ->
[1 0]

[13 4 9 6] ->
[3 0 2 1]

[16 16 18 6 12 10 4 6] ->
[1 1 5 0 4 3 2 0]

[11 18] ->
[0 1]

[14 18 18 11 9 8 13 3 3 4] ->
[7 1 1 5 4 3 6 0 0 2]

[20 19 1 1 13] ->
[3 2 0 0 1]

[12] ->
[0]

[1 14 20 4 18 15 19] ->
[0 2 6 1 4 3 5]

[13 18 20] ->
[0 1 2]

[9 1 12 2] ->
[2 0 3 1]

[15 11 2 9 10 19 17 10 19 11 16 5 13 2] ->
[7 2 0 5 1 3 9 1 3 2 8 4 6 0]

[5 4 2 2 19 14 18 11 3 12 20 14 2 19 7] ->
[5 4 0 0 2 1 9 7 3 8 10 1 0 2 6]

[9 11 13 13 13 12 17 8 4] ->
[3 4 0 0 0 5 6 2 1]

[10 14 16 17 7 4 3] ->
[3 4 5 6 2 1 0]

[2 4 8 7 8 19 16 11 10 19 4 7 8] ->
[4 1 0 2 0 3 7 6 5 3 1 2 0]

[15 17 20 18 20 13 6 10 4 19 9 15 18 17 5] ->
[0 1 3 2 3 9 6 8 4 10 7 0 2 1 5]

[15 14 4 5 5 5 3 3 19 12 4] ->
[5 4 2 0 0 0 1 1 6 3 2]

[7 12] ->
[0 1]

[18 5 18 2 5 20 8 8] ->
[2 0 2 3 0 4 1 1]

[4 6 10 7 3 1] ->
[2 3 5 4 1 0]

[5] ->
[0]

[6 12 14 18] ->
[0 1 2 3]

[7 15 13 3 4 7 20] ->
[0 4 3 1 2 0 5]

[10 15 19 14] ->
[0 2 3 1]

[14] ->
[0]

[19 10 20 12 17 3 6 16] ->
[6 2 7 3 5 0 1 4]

[9 4 7 18 18 15 3] ->
[4 2 3 0 0 5 1]

[7 4 13 7] ->
[0 1 2 0]

[19 1 10 3 1] ->
[3 0 2 1 0]

[8 14 20 4] ->
[1 2 3 0]

[17 20 18 11 1 15 7 2] ->
[5 7 6 3 0 4 2 1]

[11 4 3 17] ->
[2 1 0 3]

[1 9 15 1 20 8 6] ->
[0 3 4 0 5 2 1]

[16 13 10] ->
[2 1 0]

[17 20 20 12 19 10 19 7 8 5 12 19] ->
[7 2 2 1 0 6 0 4 5 3 1 0]

[18 11] ->
[1 0]

[2 16 7 12 10 18 4 14 14 7 15 4 8 3 14] ->
[3 9 2 7 6 10 1 0 0 2 8 1 5 4 0]

[5 7 2 2 16 14 7 7 18 19 16] ->
[3 0 1 1 2 4 0 0 5 6 2]

[8 6 17 5 10 2 14] ->
[3 2 6 1 4 0 5]


This is , so the shortest valid submission (counted in bytes) wins.

# Python 2, 62 54 bytes

lambda L:map(sorted(set(L),key=L.count)[::-1].index,L)


Try it online!

Edit: saved 8 bytes via map thanx to Maltysen

• less bytes: lambda L:map(sorted(set(L),key=L.count)[::-1].index,L) – Maltysen Aug 13 '17 at 0:42

# Pyth - 1211 10 bytes

XQ_o/QN{QU

• Damn, that was quick! I'd only just managed to figure out what was being asked of us! – Shaggy Aug 12 '17 at 23:11
• You can save a byte with mx_o/QN{Q. – user48543 Oct 27 '17 at 20:13

# Japt, 11 bytes

£â ñ@è¦XÃbX


Test it online!

### Explanation

 £   â ñ@  è¦ XÃ bX
UmX{Uâ ñX{Uè!=X} bX}   Ungolfed
Implicit: U = input array
UmX{               }   Map each item X in the input to:
Uâ                   Take the unique items of U.
ñX{     }         Sort each item X in this by
Uè!=X            how many items in U are not equal to X.
This sorts the items that occur most to the front of the list.
bX      Return the index of X in this list.
Implicit: output result of last expression


# J, 11 bytes

i.~~.\:#/.~


Try it online!

## Explanation

i.~~.\:#/.~  Input: array A
#/.~  Frequency of each unique character, sorted by first appearance
~.        Unique, sorted by first appearance
\:      Sort down the uniques using their frequencies
i.~          First index in that for each element of A


# Röda, 55 bytes

{|l|l|indexOf _,[sort(l)|count|[[-_2,_1]]|sort|_|[_2]]}


Try it online!

import Data.List
f a=[i|x<-a,(i,y:_)<-zip[0..]$sortOn((0-).length)$group$sort a,x==y]  Try it online! EDIT: Thanks to @Laikoni for taking off 6 bytes! Not very short but I can't think of anything else. The idea is to iterate over the array (x<-a) and perform a lookup in a tuple list ((i,y:_)<-...,x==y) that assigns a nonnegative integer to each unique element in the input based on how common it is. That tuple list is generated by first sorting the input, grouping it into sublists of equal elements, sorting that list by the length of the sublists (sortOn((0-).length); length is negated to sort into "descending" order), then finally zipping it with an infinite list incrementing from 0. We use pattern matching to extract the actual element fromm the sublist into y. • You can match on the pattern (i,y:_) and drop the head<$> part and replace the parenthesis by $. – Laikoni Oct 28 '17 at 6:20 # Mathematica, 94 bytes (s=First/@Reverse@SortBy[Tally[j=#],Last];For[i=1,i<=Length@s,j=j//.s[[i]]->i+5!;i++];j-5!-1)&  # CJam, 17 14 bytes -3 bytes thanks to Peter Taylor This is a golfed version of the program I used to generate the testcases. {_$e$W%1f=f#}  This is an anonymous block that expects input as an array on top of the stack and outputs an array on top of the stack. Explanation: {_$e$W%1f=f#} Stack: [1 2 1 4 5] _ Duplicate: [1 2 1 4 5] [1 2 1 4 5]$            Sort:                   [1 2 1 4 5] [1 1 2 4 5]
e          Run-length encode:      [1 2 1 4 5] [[2 1] [1 2] [1 4] [1 5]]
$Sort lexicographically: [1 2 1 4 5] [[1 2] [1 4] [1 5] [2 1]] W% Reverse: [1 2 1 4 5] [[2 1] [1 5] [1 4] [1 2]] 1f= Second element of each: [1 2 1 4 5] [1 5 4 2] f# Vectorized indexing: [0 3 0 2 1]  • You can sort in reverse order for only three bytes by splitting it up: $W%. – Peter Taylor Aug 13 '17 at 19:46
• @PeterTaylor Ah, I keep forgetting lexicographic comparison for arrays is a thing. Thanks. – Esolanging Fruit Aug 14 '17 at 16:27

# TI-BASIC, 66 bytes

Ans+max(Ans+1)seq(sum(Ans=Ans(I)),I,1,dim(Ans→A
cumSum(Ans→B
SortD(∟A,∟B
cumSum(0≠ΔList(augment({0},∟A→A
SortA(∟B,∟A
∟A-1


# Explanation

seq(sum(Ans=Ans(I)),I,1,dim(Ans    Calculates the frequency of each element of Ans.
Comparing a value to a list returns a list of booleans,
so taking the sum will produce the number of matches.

Ans+max(Ans+1)                     Multiplies each frequency by one more than the max element,
This ensures that identical values with the same frequency
will be grouped together when sorting.
Additionally, all resulting values will be positive.

→A                                 Stores to ∟A.

cumSum(Ans→B                       Stores the prefix sum of the result into ∟B.
Since ∟A has only positive values, ∟B is guaranteed
to be strictly increasing.

SortD(∟A,∟B                        Sort ∟A in descending order (by frequency), grouping
identical values together. Also, dependently sort ∟B
so the original ordering can be restored.

0≠ΔList(augment({0},∟A      Prepends a 0 to ∟A and compares each consecutive difference
to 0. This places a 1 at each element that is different
from the previous element, and 0 everywhere else.
The first element is never 0, so it is considered different.

cumSum(                      →A    Takes the prefix sum of this list and stores to ∟A.
Since there is a 1 at each element with a new value,
the running sum will increase by 1 at each value change.
As a result, we've created a unique mapping.

SortA(∟B,∟A                        Sorts ∟B in ascending order with ∟A as a dependent,
restoring the original element ordering.

∟A-1                               Since we started counting up at 1 instead of 0,
subtract 1 from each element in ∟A and return it.


$c{$_}++for@F;%r=map{$_=>$i++.$"}sort{$c{$b}<=>$c{$a}}keys%c;print$r{$_}for@F  Try it online! # JavaScript (ES6), 91 bytes Using a list of unique values, sorted by frequency. x=>x.map(x=>Object.keys(C).sort((a,b)=>C[b]-C[a]).indexOf(x+''),C={},x.map(v=>C[v]=-~C[v]))  Test var F= x=>x.map(x=>Object.keys(C).sort((a,b)=>C[b]-C[a]).indexOf(x+''),C={},x.map(v=>C[v]=-~C[v])) Test=[1 2 1 4 5] -> [0 1 0 2 3] [3 2 2 1 5 7 2] -> [1 0 0 2 3 4 0] [8 8 8 8 8] -> [0 0 0 0 0] [2] -> [0] [8 6 8 4 6 8 2 4 6 8 0 2 4 6 8] -> [0 1 0 2 1 0 3 2 1 0 4 3 2 1 0] [14 1] -> [1 0] [19 6 4 9 14 17 10 9 6 14 8 14 6 15] -> [8 0 3 2 1 7 5 2 0 1 4 1 0 6] [15] -> [0] [1 18 4 8 6 19 12 17 6 13 7 6 8 1 6] -> [1 8 3 2 0 9 5 7 0 6 4 0 2 1 0] [9 10 11 9 7 11 16 17 11 8 7] -> [2 4 0 2 1 0 5 6 0 3 1] [1 3 16 19 14] -> [0 1 3 4 2] [18 8] -> [1 0] [13 4 9 6] -> [3 0 2 1] [16 16 18 6 12 10 4 6] -> [1 1 5 0 4 3 2 0] [11 18] -> [0 1] [14 18 18 11 9 8 13 3 3 4] -> [7 1 1 5 4 3 6 0 0 2] [20 19 1 1 13] -> [3 2 0 0 1] [12] -> [0] [1 14 20 4 18 15 19] -> [0 2 6 1 4 3 5] [13 18 20] -> [0 1 2] [9 1 12 2] -> [2 0 3 1] [15 11 2 9 10 19 17 10 19 11 16 5 13 2] -> [7 2 0 5 1 3 9 1 3 2 8 4 6 0] [5 4 2 2 19 14 18 11 3 12 20 14 2 19 7] -> [5 4 0 0 2 1 9 7 3 8 10 1 0 2 6] [9 11 13 13 13 12 17 8 4] -> [3 4 0 0 0 5 6 2 1] [10 14 16 17 7 4 3] -> [3 4 5 6 2 1 0] [2 4 8 7 8 19 16 11 10 19 4 7 8] -> [4 1 0 2 0 3 7 6 5 3 1 2 0] [15 17 20 18 20 13 6 10 4 19 9 15 18 17 5] -> [0 1 3 2 3 9 6 8 4 10 7 0 2 1 5] [15 14 4 5 5 5 3 3 19 12 4] -> [5 4 2 0 0 0 1 1 6 3 2] [7 12] -> [0 1] [18 5 18 2 5 20 8 8] -> [2 0 2 3 0 4 1 1] [4 6 10 7 3 1] -> [2 3 5 4 1 0] [5] -> [0] [6 12 14 18] -> [0 1 2 3] [7 15 13 3 4 7 20] -> [0 4 3 1 2 0 5] [10 15 19 14] -> [0 2 3 1] [14] -> [0] [19 10 20 12 17 3 6 16] -> [6 2 7 3 5 0 1 4] [9 4 7 18 18 15 3] -> [4 2 3 0 0 5 1] [7 4 13 7] -> [0 1 2 0] [19 1 10 3 1] -> [3 0 2 1 0] [8 14 20 4] -> [1 2 3 0] [17 20 18 11 1 15 7 2] -> [5 7 6 3 0 4 2 1] [11 4 3 17] -> [2 1 0 3] [1 9 15 1 20 8 6] -> [0 3 4 0 5 2 1] [16 13 10] -> [2 1 0] [17 20 20 12 19 10 19 7 8 5 12 19] -> [7 2 2 1 0 6 0 4 5 3 1 0] [18 11] -> [1 0] [2 16 7 12 10 18 4 14 14 7 15 4 8 3 14] -> [3 9 2 7 6 10 1 0 0 2 8 1 5 4 0] [5 7 2 2 16 14 7 7 18 19 16] -> [3 0 1 1 2 4 0 0 5 6 2] [8 6 17 5 10 2 14] -> [3 2 6 1 4 0 5] Test.split(\n).forEach(row => { row=row.match(/\d+/g) var nv = row.length/2 var tc = row.slice(0,nv) var exp = row.slice(nv) var xsum = eval(exp.join+) var result = F(tc) var rsum = eval(result.join+) var ok = xsum == rsum console.log('Test ' + (ok ? 'OK':'KO') + '\nInput [' + tc + ']\nExpected (sum ' + xsum + ') ['+ exp + ']\nResult (sum ' + rsum + ') [' + result + ']') }) # PHP, 92 bytes $b=array_unique($a);print_r(array_map(function($v)use($b){return array_search($v,$b);},$a));


Try it online!

# R, 58 bytes

x=scan();cat(match(x,names(z<-table(x))[rev(order(z))])-1)


Try it online!

Port of Chas Brown's Python answer.

table computes the counts of each element in x (storing the values as the names attribute), order returns a permutation of the indices in z, and match returns the index of the first match of x in names(z). Then it subtracts 1` because R indices are 1-based.