Unikalny jest tani

93

Napisz funkcję lub program, który określa koszt danego ciągu, gdzie

  • koszt każdego znaku jest równy liczbie przypadków, w których znak wystąpił do tego momentu w ciągu, oraz
  • koszt ciągu jest sumą kosztów jego znaków.

Przykład

abaacabKoszt wejściowy obliczany jest w następujący sposób:

a b a a c a b
1   2 3   4    occurrence of a
  1         2  occurrence of b
        1      occurrence of c
1+1+2+3+1+4+2 = 14

Zatem koszt ciągu abaacabwynosi 14.

Zasady

  • Wynik przesłania jest kosztem kodu zdefiniowanego powyżej , to znaczy, że przesyłanie odbywa się na własnym kodzie źródłowym, przy czym niższy wynik jest lepszy.
  • Twoje zgłoszenie powinno działać na ciągach zawierających drukowalne znaki ASCII oraz wszystkie znaki użyte w przesłaniu.
  • W znakach rozróżniana jest wielkość liter, tzn. aI Asą to różne znaki.

Przypadki testowe

input -> output
"abaacab" -> 14
"Programming Puzzles & Code Golf" -> 47
"" -> 0
"       " -> 28
"abcdefg" -> 7
"aA" -> 2

Tabela liderów

Pokaż fragment kodu

string  code-challenge 
— Laikoni
źródło
2
W jaki sposób flagi programu, takie jak -nPerl, liczą się do wyniku? Tradycyjnie liczy się jako 1 bajt, ponieważ odległość edycji między standardem perl -ea perl -ne1 wynosi, ale czy w przypadku tego wyzwania będzie nliczona do celów liczenia duplikatów?
— Wartość tuszu
2
@ValueInk Tak, myślę, że liczenie nto najlepsza opcja.
— Laikoni
1
Naprawdę żałuję, że nie udało mi się znaleźć rozwiązania tego problemu.
— Peter1807
10
+1 za Wynik twojego zgłoszenia jest kosztem twojego kodu
— luizfzs
1
Koszt postaci jest zdefiniowany jako how often this character has already occurred in the string, prawdopodobnie zmieniłbym na, how many times the character has occurred up to this pointaby wyjaśnić, że pierwsze użycie kosztuje 1, a nie 0
— metro

Odpowiedzi:

83

MATL , wynik 4

&=Rz

Wypróbuj online!

Wyjaśnienie

Rozważ dane wejściowe 'ABBA'jako przykład.

&=   % Implicit input. Matrix of all equality comparisons
     % STACK: [1 0 0 1;
               0 1 1 0;
               0 1 1 0;
               1 0 0 1]
R    % Upper triangular part
     % STACK: [1 0 0 1;
               0 1 1 0;
               0 0 1 0;
               0 0 0 1]
z    % Number of nonzeros. Implicitly display
     % STACK: 6
— Luis Mendo
źródło
14
Czy jesteś profesorem algebry liniowej?
— Magic Octopus Urn
4
@carusocomputing Właściwie profesor komunikacji mobilnej. Moja tendencja do używania matryc wynika z wieloletniego programowania w Matlabie
— Luis Mendo
Schludny! Czy Matlab jest duży w tej dziedzinie? Nigdy tak naprawdę nie patrzyłem na GSM ani nic podobnego.
— Magic Octopus Urn
2
Dołączyłem do tej społeczności, aby pochwalić Cię tym wspaniałym rozwiązaniem!
— Wboy
1
@carusocomputing Matlab jest ogólnie bardzo popularnym narzędziem / językiem w inżynierii. Jest dobry w obliczeniach numerycznych: algebrze liniowej, przetwarzaniu sygnałów i tym podobnych. Ponieważ jest językiem interpretowanym, jest bardzo łatwy w użyciu
— Luis Mendo
17

Python , wynik 49

lambda S:sum(1+S.count(C)for[C]in	S)/2

Wypróbuj online!

Po tym jest zakładka in.

Podział punktacji:

  • +27 za 27 unikalnych znaków
  • +16 za 8 podwójnych znaków: ()Camnou
  • +6 za 1 potrójny znak: S
— xnor
źródło
13
Użyj tabulacji zamiast spacji, aby zapisać bajt.
— mbomb007
1
@ mbomb007 Właśnie miałem ten sam pomysł :-)
— xnor
1
@ mbomb007 Hah, to genialna sztuczka :-)
— ETHproductions
14
@ mbomb007, który jest tylko kartą kontra wojna
— kosmiczna w kodzie golfowym
2
Chciałem zasugerować użycie formularza feed (który jest również dozwolony spacją w składni Pythona), ale nie ma już więcej spacji do zastąpienia.
— user2357112,
8

T-SQL, wynik 775 579! 580

declaRe @ char(876),@x int,@v int=0Select @=q+CHAR(9)from z X:seleCT @x=len(@),@=REPLACE(@,LEFT(@,1),''),@v+=(@x-LEN(@))*(@x-LEN(@)+1)/2IF LEN(@)>0GOTO X prINT @v-1

EDYCJA : Upuściłem kilka zmiennych, trochę zagęściłem. Zejście do 16 @symboli zamiast 22, co samo w sobie zmniejsza mój wynik aż o 117 punktów!

Fajny konkurs, podoba mi się wymaganie optymalizacji czegoś oprócz całkowitej liczby postaci.

Dane wejściowe są poprzez pole varchar q w istniejącej tabeli z , zgodnie z naszymi regułami IO . W bazie danych zawierającej tę tabelę wejściową należy ustawić sortowanie z rozróżnianiem wielkości liter .

Sformatowany:

declaRe @ char(876), @x int, @v int=0
Select @=q+CHAR(9)from z
X:
    seleCT @x=len(@)
          ,@=REPLACE(@,LEFT(@,1),'')
          ,@v+=(@x-LEN(@))*(@x-LEN(@)+1)/2
IF LEN(@)>0 GOTO X
prINT @v-1

W słowach kluczowych SQL nie jest rozróżniana wielkość liter, więc użyłem mieszanych liter, aby zminimalizować liczbę zduplikowanych liter ( aaAA generuje lepszy / niższy wynik niż aaaa ).

Główna pętla porównuje długość przed i po usunięciu wszystkich wystąpień pierwszego znaku. Ta różnica n * (n + 1) / 2 jest dodawana do sumy bieżącej.

Irytująca LEN()funkcja SQL ignoruje końcowe spacje, więc musiałem dodać znak kontrolny i odjąć 1 na końcu.

EDYCJA : Naprawiono błędne obliczenie mojego własnego wyniku o 2 punkty (problem z cytowaniem cudzysłowów), zmniejszone o 1 przez zmianę obudowy o jeden R. Pracując również nad zupełnie inną strategią, opublikuję to jako własną odpowiedź.

— BradC
źródło
3
Na początku myślałem, że twój wynik to579! ≈ 8.22 x 10^1349
— Engineer Toast
8

C (gcc) , wynik:  113  103 100   96  91

Dzięki @ugoren, @CalculatorFeline, @gastropner, @ l4m2 i @ JS1 za wskazówki.

g(char*s){int y[238]={};while(*s)*y-=--y[*s++];*y/=1;}

Inicjuje tablicę zer, a następnie wykorzystuje wartości ASCII znaków w ciągu jako indeksy dla tej tablicy, aby śledzić liczbę wystąpień każdego znaku w ciągu.

Wypróbuj online!

— Steadybox
źródło
3
Podpowiedź: Użyj nazwy zmiennych, które nie są wykorzystywane w kluczowych, jak z, x, c.
— CalculatorFeline,
@CalculatorFeline charzawiera c...
— Neil
3
Ponadto potrzebujesz tylko tablicy \x7fskładającej się z 127 elementów ( nie można jej wydrukować) i dodaj wyjaśnienie.
— CalculatorFeline,
1
Późno na imprezę, ale powinna to być 96:z;g(char*s){int y[238]={z=0};while(*s)z+=--y[*s++];z/=~0;}
— gastropner
1
g(char*s){int y[238]={};while(*s)*y+=--y[*s++];*y/=~0;}
— l4m2
7

JavaScript (ES6), wynik 81 78

Zaoszczędź 3 punkty dzięki @Arnauld

s=>s.replace(d=/./g,z=>q+=d[z]=-~d[z],q=0)&&q

Moje oryginalne rozwiązanie rekurencyjne score-81:

f=([c,...s],d={})=>c?(d[c]=-~d[c])+f(s,d):0
— ETHprodukcje
źródło
7

Siatkówka , ocena 34

s(O`.
M&!`^|(?<=(.))\1*
.

Wypróbuj online!

Wyjaśnienie

s(O`.

Zaczynamy od sortowania wszystkich znaków na wejściu, aby identyczne znaki były zgrupowane w jednym przebiegu. s(Aktywuje tryb SingleLine na wszystkich etapach (tj sprawia .karetki meczu).

M&!s`^|(?<=(.))\1*

Celem jest przekształcenie ciągu n znaków w T n znaków ( n- ta liczba trójkątna), ponieważ jest to wynik występowania tej postaci. Aby to zrobić, znajdujemy nakładające się mecze. W szczególności dla każdego i w [1, n] dołączymy do meczu znaki i-1 . Wszystkie te mecze otrzymujemy z powodu nakładającej się flagi &. To daje nam n * (n-1) / 2 = T n-1 = T n - n znaków tylko z dopasowań. Ale etap dopasowania połączy je z liniami, które są n liniami dla nmecze. Jest tylko jeden problem. Po ostatnim dopasowaniu nie będzie podawania linii, więc ogólna liczba znaków na wyjściu jest o jeden mniejsza niż potrzebujemy. Naprawiamy to, dopasowując również początek danych wejściowych, co daje nam jeden wiodący kanał, jeśli istnieje co najmniej jedno dopasowanie.

.

Wreszcie, po prostu liczymy, ile znaków jest w ciągu.

— Martin Ender
źródło
6

Haskell, wynik 52 51

f(a:b)=1+sum[1|c<-b,c==a]+f b;f _=0

Istnieje zakładka pomiędzy fi _.

Wypróbuj online!

Wartość pustego ciągu wynosi 0. Wartość ciągu s, gdzie ajest pierwszym znakiem, a breszta ciągu to 1 plus wystąpienia ain bplus wywołanie rekurencyjne z b.

— nimi
źródło
5

J , wynik 16

1#.,@(*+/\"1)&=

Wypróbuj online!

Wyjaśnienie

1#.,@(*+/\"1)&=
              =  Self-classify: bit matrix of equality between input
                 and its unique elements.
     (      )&   Apply verb in parentheses to it:
       +/\         running sums
          "1       of each row
      *            multiplied with original matrix.
                 This causes the i'th 1 on each row to be replaced by i.
   ,@            Flatten the resulting matrix
1#.              and interpret as a base-1 number, computing its sum.

Użycie 1#.zamiast +/@sumy pozwoliło zaoszczędzić kilka punktów i &może być użyte zamiast @w kontekście monadycznym, aby zaoszczędzić jeszcze jeden. Powtarzanie 1kosztuje mnie jeden dodatkowy punkt, ale nie byłem w stanie się go pozbyć.

— Zgarb
źródło
„później” czeka kwadrans
— CalculatorFeline
2
@CalculatorFeline 10 godzin później jest jeszcze później. : P
— Zgarb
Zróbmy teraz sesquisemiday.
— CalculatorFeline,
Osobiście używam tego formatu do odpowiedzi TIO, aby odzwierciedlić dokładną liczbę bajtów w sekcji kodu, być może chciałbyś go użyć
— Conor O'Brien
5

R , wynik: 67 83 95 128

-61 dzięki najlepszym wskazówkom Giuseppe 

function(x,y=table(utf8ToInt(x)))y%*%{y+1}/2

Wypróbuj online!

Ciąg jest dzielony za pomocą utf8ToInti każda wartość ascii jest liczona table. Wynik jest obliczany przy użyciu mnożenia macierzy %*%ponad to samo w sobie + 1 i ostatecznie o połowę.

— MickyT
źródło
użyj tablezamiast rle; możesz się go również pozbyć sort(i nie musisz indeksować [[1]]wyniku strsplit)
— Giuseppe
@Giuseppe Wielkie dzięki. Nawet nie pomyślałem o stole, dołączy wkrótce.
— MickyT,
2
Myślę, że możesz zaoszczędzić jeszcze kilka bajtów, używając innej nazwy zmiennej zamiast n(ponieważ jest ona functionpodwojona), a także zmieniając (n+1)na{n+1}
— Giuseppe
wynik: 67 . Niektóre warianty tego mogą umożliwić dalsze zmniejszenie wyniku.
— Giuseppe,
@Giuseppe ... Powinienem był to przeczytać. Ups
— MickyT
4

Pyth , ocena 6

1 bajt dzięki isaacg.

+F/V._

Zestaw testowy.

Jak to działa

+F/V._
+F/V._QQ  implicit input
  /V      vectorize count: for each element in the first argument,
                           count the number of occurrences of the
                           second argument:
    ._Q       all prefixes of input
       Q      input
+F        fold (reduce) on +, base case 0.
— Leaky Nun
źródło
s+0jest taki sam jak +F.
— isaacg,
Dobry! Najlepsze, co mogłem zrobić, to usaShHGrScQ1 8Z16 lat. Czy możesz dodać wyjaśnienie?
— Digital Trauma
1
@DigitalTrauma Dodałem wyjaśnienie.
— Leaky Nun
s/LQjest wynikiem 4, czy korzysta z funkcji, które datują wyzwanie?
— Dave
4

Galaretka , wynik 7

ċЀQRFS

Wyjaśnienie:

   Q    get unique letters
ċЀ     count the occurences of each letter in the original string
    R   [1..n] for n in list of frequencies
     F  flatten list
      S sum
        (implicit output)

Wypróbuj online!

— ellie
źródło
2
Witamy w PPCG!
— Laikoni
4

C, 60 bajtów, wynik 108 95

g(char*s){int y[256]={},z=0;while(*s)z-=--y[*s++];return z;}

Wypróbuj online!

Zwykle operatorzy przed i po inkrementacji są świetni do gry w golfa kodowego, ale naprawdę bolą w tym wyzwaniu!

EDYCJA: Odejmując liczby ujemne zamiast dodatnich, zapisałem całą masę wyników. Wymiana for()z while()wyeliminowane średnik jako dobrze.

— ErikF
źródło
3

C # (.NET Core) , wynik ∞ (mam na myśli, 209)

b=>b.Distinct().Select(z=>{var w=b.Count(p=>p==z);return w*(w+1)/2;}).Sum()

Wypróbuj online!

Wynik obejmuje:

using System.Linq;
— Charlie
źródło
Wiem, że minęło trochę czasu, ale możesz się zmienić return w*(w+1)/2na return-~w*w/2(wynik 196). EDYCJA: Możesz utworzyć port mojej odpowiedzi Java 8 za wynik 149 : using System.Linq;b=>{int[]x=new int[256];return\nb.Select(z=>++x[z]).Sum();} Wypróbuj online.
— Kevin Cruijssen
1
@KevinCruijssen: Twoje rozwiązanie spadło do 111:b=>{var x=new int[256];return\nb.Sum(z=>++x[z]);}
— raznagul
@raznagul ( * nadchodzi odpowiedź półroczna * ) 109, jeśli zmienisz drugą spację na tabulator. ;) Wypróbuj online.
— Kevin Cruijssen
1
@KevinCruijssen (nadchodzi kolejna półroczna odpowiedź) 49 z interaktywnym kompilatorem i myślę, że nigdy nie spadnie poniżej 48. Wydaje mi się dziwne, że im więcej odpowiedzi C # w golfa, tym bardziej czytelne wydają się być. Wypróbuj online!
— ktoś
3

PowerShell, wynik 64

$z=@{}
$ARGS|% getE*|%{$u+=($Z.$_+=1)};$U

(Wynik oparty jest na nowej linii nowego wiersza, która nie jest standardem Windows, ale działa w PS).

PS C:\> D:\unique-is-cheap.ps1 (gc D:\unique-is-cheap.ps1 -raw)
64
  • Licznik haszowany @{}
  • Iteruj po literach; $argsjest tablicą parametrów - w tym przypadku łańcuch wejściowy czyni go tablicą pojedynczego elementu; |%wykonuje pętlę foreach nad elementami i używa getE*skrótu, aby dopasować GetEnumerator()metodę ciągu i wywołać ją, aby przekształcić ciąg w strumień znaków.
  • |%zapętlaj znaki i zwiększaj ich hashtable, dodaj go do bieżącej sumy. ($x+=1)Forma z parens zarówno modyfikuje zmienną i wysyła nową wartość do użycia.
  • Podaj sumę bieżącą.

(Kiedy napisałem to po raz pierwszy, było to $c=@{};$t=0;[char[]]"$args"|%{$c[$_]++;$t+=$c[$_]};$tz wynikiem 128 i czułem, że nie obniżyłby się znacznie. Zmniejszenie do 64 jest całkiem przyjemne).

— TessellatingHeckler
źródło
1
61 pkt / 38 bajtów przez mieszanie się z przyrostem
— Veskah
— mazzy
3

Julia 0,6 , 45 bajtów, wynik: 77

Zainspirowany rozwiązaniem MATL:

f(w)=sum(UpperTriangular([z==j for z=w,j=w]))

Wypróbuj online!

Mniej ładne rozwiązanie, używając liczby:

Julia 0.6 , wynik: 82

F(w)=sum(l->[l+1]l/2,count(x->x==i,w)for i=Set(w))

Wypróbuj online!

Dzięki Guiseppe za wskazanie punktacji i wskazówki. Te komentarze pomogły mi ładować.

— niczky12
źródło
1
Wynik twojego zgłoszenia to koszt twojego kodu , który moim zdaniem wynosi 135.
— Giuseppe
1
Nie znam bardzo dobrze Julii, ale myślę, że możesz zmniejszyć wynik do 110 , zmieniając nazwy zmiennych i usuwając zestaw nawiasów. Jeśli powrót do pojedynczego elementu wektora jest dozwolone, to można zastąpić (x+1)w [x+1]celu dalszego zmniejszenia wynik.
— Giuseppe
Możesz zapisać wynik, zmieniając drugie pole na tabulator lub nowy wiersz: wynik 104 . I wskazówka @Giuseppe [x+1]zamiast używania (x+1)obniża ją do wyniku 98 .
— Kevin Cruijssen
3

Java 10, wynik: 149 138 137 134 133 130 103 102 101 100

( Bajty: 72 73 74 75 64 62 61 ) Bajty rosną, ale wynik spada. :RE

x->{int j=0,q[]=new int[256];for(var    C:x)j+=++q[C];return
j;}

Wynik -28 (i -11 bajtów) dzięki @Nevay .
-1 wynik (i -2 bajty) dzięki @ OlivierGrégoire .
Wynik -1 (i -1 bajt) poprzez konwersję Java 8 na Java 10.

Wyjaśnienie:

Wypróbuj tutaj.

x->{                     // Method with character-array parameter and integer return-type
  int j=0,               //  Result-integer, starting at 0
      q[]=new int[256];  //  Integer-array with 256 times 0
  for(var   C:x)         //  Loop over the characters of the input array
    j+=++q[C];           //   Raise the value in the array by 1,
                         //   and then add it to the result-integer
  return                 //  Return 
  j;}                    //         the result
— Kevin Cruijssen
źródło
1
Możesz usunąć ~jeśli używasz j=0i return-j;(133).
— Nevay
1
103:x->{int[]q=new int[256];return\nx.chars().map(v->++q[v]).sum();}
— Nevay
1
@Nayay 103 faktycznie, kiedy używam jzamiast u( returnzawiera u) i nowego wiersza i tabulacji zamiast spacji. EDYCJA: Hehe, edytowałeś właśnie wtedy, kiedy skomentowałem ten komentarz. :)
— Kevin Cruijssen
3

F #, wynik 120 118

let j z=Seq.countBy id z|>Seq.sumBy(fun x->List.sum[0..snd x])

-2 dzięki Kevin Cruijssen !

Wypróbuj online!

Pobiera stringjako dane wejściowe. Seq.countByparuje każdy odrębny znak z jego liczbą ( idjest funkcją tożsamości), dzięki czemu otrzymujesz kolekcję podobną do 'a' = 4, 'b' = 2itp.

Seq.sumByTrwa odliczanie do każdego listu i sumuje wszystkie numery od 0do zliczania dla danej litery. Więc jeśli 'a' = 4kolekcja byłaby 0, 1, 2, 3, 4sumą, która jest razem 10. Następnie Seq.sumBysumuje wszystkie te sumy.

— Ciaran_McCarthy
źródło
2
Możesz obniżyć swój wynik o 2, zmieniając let qna let j, ponieważ qjest on już używany w obu Seq.
— Kevin Cruijssen
2

APL (Dyalog) , wynik 15

+/1 1⍉+\∘.=⍨⍞

Wypróbuj online!

⍞ uzyskać wprowadzanie tekstu

∘.=⍨ tabela równości z jaźnią

+\ skumulowana suma w poprzek

1 1⍉ przekątna (dosł. zwiń oba wymiary do wymiaru pierwszego)

+/ suma

— Adám
źródło
2

Siatkówka , wynik 68 45 43

s`(.)(?<=((\1)|.)+)
$#3$*
1

Wypróbuj online! Link pokazuje wynik. Edycja: Dzięki @MartinEnder, który zaoszczędził 20 bajtów, używając nakładających się dopasowań zamiast oczekujących, i kolejne trzy bajty, grupując etapy, tak aby sflaga mogła być zastosowana tylko raz. Zaoszczędzono kolejne dwa bajty, obliczając liczbę trójkątną inaczej, unikając potrzeby sortowania.

— Neil
źródło
2

Wynik Perla 5 91 83

Używa -pflagi, która dodaje 2 z powodu pw podziale.

$x=$_;$b+=++$a{$_}for(split//,$x);$_=$b
— użytkownik1937198
źródło
Witamy w PPCG!
— Laikoni
1
Wykorzystując twoją odpowiedź jako podstawę i stosując niektóre techniki ze strony porad, udało mi się obniżyć twój wynik do 31: Wypróbuj online! . $` is automatically print ed after each call so we can use that to store the score and /./ g` zwraca listę wszystkich znaków $_, która jest tańsza niż split//.
— Dom Hastings,
Wiem, że to stare wyzwanie, ale możesz jeszcze bardziej obniżyć wynik: wypróbuj online!
— Xcali,
2

Oktawa , 39 bajtów, wynik 69

@(a)sum((b=hist(a,unique(1*a))).^2+b)/2

Wypróbuj online!

Chociaż istnieje inna odpowiedź Octave, ta jest całkowicie moja i ma inne podejście, a ponadto ma mniej punktów :).

Podejście sprowadza się do pierwszego znalezienia liczby (b) każdego unikalnego znaku, którą uzyskuje się za pomocą funkcji histogramu. Następnie dla każdego elementu obliczamy sumę 1 do b, która odbywa się za pomocą wzoru (b*(b+1))/2. Następnie poszczególne sumy są sumowane do końcowego wyniku.

W testach wydaje się, że nawiasy są bardzo kosztowne w ocenie, ponieważ wiele jest potrzebnych. Zoptymalizowałem od początkowego wyniku wynoszącego około 88, zmieniając układ pytań, aby zminimalizować liczbę nawiasów otwierających / zamykających - dlatego teraz wykonujemy / 2 na końcowej sumie, a nie indywidualnie, a także zmodyfikowałem formułę, aby (b^2+b)/2ponieważ wymaga to mniejszej liczby nawiasów.

— Tom Carpenter
źródło
1
Niestety wydaje się, że zawiedzie to na pustym ciągu:error: hist: subscript indices must be either positive integers less than 2^31 or logicals
— Laikoni
2

Common Lisp, wynik 286 232 222

(loop with w =(fill(make-list 128)0)as z across(read)sum(incf(elt w(char-code z))))

Wysoko ceniony wynik ze względu na mylną składnię wbudowanych operatorów Common Lisp.

Wypróbuj online!

Nieskluczony kod:

(loop with w = (fill (make-list 128) 0)  ; create a list to count characters
   as z across (read)                   ; for each character of input
   sum (incf (elt w (char-code z))))     ; increase count in list and sum
— Renzo
źródło
2

Mathematica, ocena 54

Total[#(#+1)/2&@Counts@Characters@#]&

Wejście

[„abcdefg”]

dzięki hftf

— J42161217
źródło
Total[#(#+1)/2&@Counts@Characters@#]&wyniki 54.
— hftf
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.