Süßigkeiten in der richtigen Reihenfolge essen

36

Wenn es darum geht, Süßigkeiten zu essen, halte ich mich an höhere Standards als der typische Laie. Es gibt ein empfindliches Gleichgewicht zwischen "Verwechseln" und "Das Beste zum Schluss".

In dieser Herausforderung erhalten Sie eine Zeichenfolge, in der jedes Zeichen ein Bonbon darstellt. Verschiedene Zeichen (Groß- und Kleinschreibung beachten) stehen für verschiedene Arten von Süßigkeiten. Ihr Programm muss dann die richtige Reihenfolge für den Verzehr von Süßigkeiten anhand der folgenden Prozedur ermitteln. Sie können entweder ein vollständiges Programm (STDIN / STDOUT) oder eine benannte Funktion schreiben, um diese Aufgabe auszuführen.

Nehmen wir an, mein Süßigkeitenvorrat ist oroybgrbbyrorypoprr. Zuerst sortiere ich die Süßigkeiten in Stapel des gleichen Typs, wobei größere Mengen oben liegen, wobei niedrigere ASCII-Zeichenwerte als Auslöser dienen.

rrrrrr
oooo
bbb
yyy
pp
g

Dann nehme ich jede Reihe Süßigkeiten und verteile sie in gleichmäßigen Abständen. Wenn es zum Beispiel 3 Süßigkeiten gibt, wird eine 1/3 des Weges, 2/3 des Weges und am Ende platziert.

.r.r.r.r.r.r
..o..o..o..o
...b...b...b
...y...y...y
.....p.....p
...........g

Dann gehe ich jede Spalte durch, um meine endgültige Süßigkeitenbestellung zu erstellen rorbyroprbyorrobypg.

Eingang

Eine Zeichenfolge, die den Süßigkeitenbestand enthält. Die Eingabe für das obige Beispiel könnte gewesen sein:

oroybgrbbyrorypoprr

Ausgabe

Eine Zeichenfolge, die die Süßigkeiten enthält, wurde in der richtigen Reihenfolge des Verbrauchs reorganisiert.

rorbyroprbyorrobypg

Wertung

Das ist Code Golf. Die kürzeste Antwort in Bytes gewinnt. Es gelten die Standardregeln für Code-Golf.

PhiNotPi
quelle
Fügen Sie einfach ein größeres Leerzeichen hinzu, wenn die Bonbonzahlen ungerade sind? Sagen wir in diesem Fall, wenn Sie noch eine Süßigkeit hätten, wie würde das Gitter aussehen?
Vajura
38
Endlich jemand, der weiß, wie man Süßigkeiten isst.
Michael M.
12
Also ... im Grunde Candy Dithering.
COTO
9
Dies kommt tatsächlich sehr nahe, wie ich meine Süßigkeiten esse. :)
Emil
3
Wie gierig kann eine Person werden? Gibt es ein Limit für die Anzahl der Süßigkeiten, die gegessen werden sollen?
Alchymist

Antworten:

12

CJam, 78 68 61 45 42 39 31 30 Bytes

l$:L{L\/,~}${:DM+:MD/,LD/,d/}$

Übernimmt die Eingabezeichenfolge über STDIN

Inspiriert von rekursiven Ansätzen, aber ein bisschen anders. Überhaupt kein Transponieren oder Rechteck nötig !.

Wie es funktioniert:

l$:L                              "Sort the input line and store it in L";
    {     }$                      "Sort the string based on this code block output";
     L\/,~                        "Sort based on number of occurrences of each";
                                  "character in the full string";
            {               }$    "Sort the sorted string again";
             :DM+:M               "Store each character in D, add to M and update M";
                   D/,            "Count occurrences of D in M";
                      LD/,        "Count occurrences of D in L";
                          d/      "Sort string based on the ratio of two occurrences";

(Schade, dass CJam mit Pyth nicht mehr fertig werden kann, weil so viel Bloat wie Syntax benötigt wird)

Probieren Sie es hier aus

Optimierer
quelle
4
Ich glaube nicht, dass Sie das LCM brauchen. Ein beliebiges Vielfaches sollte funktionieren. Auf diese Weise können Sie ersetzen {_@_@{_@\%}h;/*}mit :.
Dennis
<facepalm> hat daran nicht gedacht.
Optimierer
Herzlichen Glückwunsch zur Halbierung Ihrer Länge!
Isaacg
Ich fühle mich Sarkasmus, dass: D
Optimizer
11

Pyth , 25

shCoc/NhN/zhNm>o_/zZSzdUz

Verwendet einen völlig neuen Algorithmus, der von dieser Antwort inspiriert ist .

(implicit)          z = input()
(implicit)          print
s                   combine list of strings into one string
 h                  first list in
  C                 matrix transpose of (e.g. first characters in first list, etc.)
   o                order_by(lambda N:
    c                        float_div(
     /NhN                              N.count(N[0]),
     /zhN                              z.count(N[0])),
    m                        map(lambda d:
     >                           slice_head(
      o                                     order_by(lambda Z:
       _/zZ                                          -1*z.count(Z),
       Sz                                            sorted(z)),
      d                                     d),
     Uz                          range(len(z))

Schritt für Schritt:

  1. Zuerst haben wir die Zeichen nach ihrer Häufigkeit sortiert und die Verbindungen alphabetisch getrennt. Das ist o_/zZSz. oist dasselbe wie bei Python sorted(<stuff>,key=<stuff>), mit einem Lambda-Ausdruck für den Schlüssel, außer dass er als Zeichenfolge beibehalten wird.

  2. Dann generieren wir eine Liste der Präfixe dieses Strings von Länge len(z)zu Länge 1. >Entspricht Pythons <stuff>[<int>:].

  3. Anschließend ordnen wir diese Liste der Präfix-Zeichenfolgen nach der Bruchstelle des ersten Zeichens des Präfixes auf dem in der Frage gezeigten rechteckigen Layout neu an, wobei 0 der linke Rand und 1 der rechte Rand ist. /NhNZählt, wie oft das erste Zeichen im Präfix im Präfix vorkommt, während /zhNdie Anzahl der Vorkommen des ersten Zeichens im Präfix in der Zeichenfolge als Loch angegeben wird. Dies weist jedem Präfix, das von jedem Zeichen in einer Gruppe angeführt wird, einen anderen Bruch zu, von 1/kdem am weitesten rechts liegenden Vorkommen dieses Zeichens bis k/kzum am weitesten links liegenden. Wenn Sie die Präfixliste nach dieser Nummer neu ordnen, erhalten Sie die entsprechende Position im Layout. Die Aufteilung der Krawatten erfolgt nach der vorherigen Reihenfolge, die zuerst gezählt und dann nach Wunsch alphabetisch sortiert wurde.

  4. Schließlich müssen wir das erste Zeichen aus jeder Präfixzeichenfolge extrahieren, sie zu einer einzelnen Zeichenfolge kombinieren und sie ausdrucken. Extrahieren der ersten Zeichen ist hC. CFührt eine Matrixtransponierung für die Liste durch. zip(*x)Tatsächlich hextrahiert Python 3. die erste Zeile der resultierenden Matrix. Dies ist tatsächlich die einzige Zeile, da das Vorhandensein des 1-Zeichen-Präfix verhindert, dass andere vollständige Zeilen gebildet werden. sfasst die Zeichen in diesem Tupel zu einer einzigen Zeichenfolge zusammen. Drucken ist implizit.

Prüfung:

$ pyth -c 'shCoc/NhN/zhNm>o_/zZSzdUz' <<< 'oroybgrbbyrorypoprr'
rorbyroprbyorrobypg

Inkrementelle Programmteile zu oroybgrbbyrorypoprr:

Sub-Piece                  Output

Sz                         bbbgoooopprrrrrryyy
o_/zNSz                    rrrrrroooobbbyyyppg      (uses N because o uses N on first use.)
m>o_/zNSzdUz               ['rrrrrroooobbbyyyppg', 'rrrrroooobbbyyyppg', 'rrrroooobbbyyyppg', 'rrroooobbbyyyppg', 'rroooobbbyyyppg', 'roooobbbyyyppg', 'oooobbbyyyppg', 'ooobbbyyyppg', 'oobbbyyyppg', 'obbbyyyppg', 'bbbyyyppg', 'bbyyyppg', 'byyyppg', 'yyyppg', 'yyppg', 'yppg', 'ppg', 'pg', 'g']
oc/NhN/zhNm>o_/zZSzdUz     ['roooobbbyyyppg', 'obbbyyyppg', 'rroooobbbyyyppg', 'byyyppg', 'yppg', 'rrroooobbbyyyppg', 'oobbbyyyppg', 'pg', 'rrrroooobbbyyyppg', 'bbyyyppg', 'yyppg', 'ooobbbyyyppg', 'rrrrroooobbbyyyppg', 'rrrrrroooobbbyyyppg', 'oooobbbyyyppg', 'bbbyyyppg', 'yyyppg', 'ppg', 'g']
Coc/NhN/zhNm>o_/zZSzdUz    [('r', 'o', 'r', 'b', 'y', 'r', 'o', 'p', 'r', 'b', 'y', 'o', 'r', 'r', 'o', 'b', 'y', 'p', 'g')]
shCoc/NhN/zhNm>o_/zZSzdUz  rorbyroprbyorrobypg

Alte Antwort:

Pyth , 34

ssCm*+t*u*G/zHS{-zd1]kd/zdo_/zNS{z

Dieses Programm berechnet, wie oft eine bestimmte Unterliste repliziert werden muss. Die Unterliste sieht aus wie ['', '', '', '', ... , 'r']. Die Gesamtlänge dieser Unterliste ergibt sich aus der Häufigkeit aller anderen Bonbons u*G/zHS{-zd1. Die vollständige Unterliste wird erstellt, indem die Liste der leeren Zeichenfolge so oft wie möglich repliziert ]kund anschließend ein Element mit entfernt tund der Bonbonname am Ende mit hinzugefügt wird +d.

Diese Unterliste wird dann so oft repliziert, wie diese Süßigkeit in der Eingabe gefunden wird /zd, um sicherzustellen, dass die Liste jeder Süßigkeit gleich lang ist.

Mit dieser Funktion, die in der richtigen Reihenfolge ( o_/zNS{z) auf alle eindeutigen Bonbons abgebildet wird , haben wir ein Rechteck, das dem in der Frageanweisung ähnelt, aber leere Zeichenfolgen anstelle von Punkten enthält. Wenn Sie eine Matrixtransponierung ( C) gefolgt von zwei Summierungen ( ss) durchführen, erhalten Sie die endgültige Zeichenfolge.

Nachprüfung:

$ pyth programs/candy.pyth <<< 'oroybgrbbyrorypoprr'
rorbyroprbyorrobypg
isaacg
quelle
4
Es sieht so aus, als ob Pyth die Verschlüsselung in der Sprachsyntax selbst unterstützt!
Optimierer
@Optimizer-Verschlüsselung? Worüber redest du?
Isaacg
Nett! Ich hätte wahrscheinlich nie gedacht, die for-Schleife in eine Map umzuwandeln. Viel sauberer.
FryAmTheEggman
Schauen Sie sich den Quellcode an. Es sieht aus wie eine verschlüsselte Nachricht.
Optimierer
2
Können Sie ein schrittweises Beispiel für den neuesten Algorithmus geben? Ziemlich bitte :)
Optimierer
6

Perl 5 - 62

61 Code + 1 Flag.

#!perl -n
print map/(.$)/,sort map/(.$)/*$_/$$1.~$_.$1,map++$$_.$_,/./g

Teilen Sie die Eingabe zunächst in das Zeichenfeld - auf /./g.

Fügen Sie jedem Buchstaben einen Vorkommensindex hinzu und lassen Sie dabei die Anzahl der Variablen $a.. $zmit map++$$_.$_. Jetzt ist das Array:

1o
1r
2o
1y
1b
1g
2r
2b
3b
2y
3r
3o
4r
3y
1p
4o
2p
5r
6r

Konvertieren Sie es dann in eine Sortierschlüssel-Verkettung aus Verhältnis $_/$$1, Zählwert ~$_und ASCII-Wert $_. Dies führt zu (hier mit zusätzlichen Leerzeichen zur Klarheit).

0.25 18446744073709551614 o
0.166666666666667 18446744073709551614 r
0.5 18446744073709551613 o
0.333333333333333 18446744073709551614 y
0.333333333333333 18446744073709551614 b
1 18446744073709551614 g
0.333333333333333 18446744073709551613 r
0.666666666666667 18446744073709551613 b
1 18446744073709551612 b
0.666666666666667 18446744073709551613 y
0.5 18446744073709551612 r
0.75 18446744073709551612 o
0.666666666666667 18446744073709551611 r
1 18446744073709551612 y
0.5 18446744073709551614 p
1 18446744073709551611 o
1 18446744073709551613 p
0.833333333333333 18446744073709551610 r
1 18446744073709551609 r

Dies kann in lexikografischer (Standard-) Reihenfolge sortiert werden. Am Ende letzten Buchstaben extrahieren und ausdrucken:print map/(.$)/

nutki
quelle
5

Python 3.x - 124 Bytes

C=input()
print("".join(s[1]for s in sorted(enumerate(C),key=lambda
t:((C[:t[0]].count(t[1])+1+1e-10)/C.count(t[1]),t[1]))))
rekursiv
quelle
Das ist so viel cooler als die Rechteckmethode!
isaacg
4

Mathematica, 123 119 118 Bytes

f=FromCharacterCode[s=SortBy;#&@@@s[Join@@(s[Tally@ToCharacterCode@#,-Last@#&]/.{x_,n_}:>({x,#/n}&~Array~n)),{Last}]]&

Definiert eine benannte Funktion f. Ungolfed:

f = FromCharacterCode[
   s = SortBy;
   # & @@@ s[
     Join @@ (
       s[
         Tally@ToCharacterCode@#,
         -Last@# &
         ] /. {x_, n_} :> ({x, #/n} &~Array~n)
       ),
     {Last}
     ]
   ] &

Die Verwendung integrierter rationaler Typen schien hierfür eine gute Idee zu sein. Natürlich ist dies nicht in der Nähe von CJam. Grundsätzlich stelle ich das in der Challenge gezeigte Gitter als eine Liste von Paaren dar. Das erste im Paar ist der Zeichencode, das zweite ist die Position als Bruch kleiner oder gleich 1 (die letzte Spalte ist 1). Nachdem ich sichergestellt habe, dass die einzelnen Zeichen bereits in der richtigen Reihenfolge sind, muss ich diese nur stabil nach dem genannten Bruch sortieren, um das gewünschte Ergebnis zu erzielen.

Martin Ender
quelle
3

Pyth 45 47 48 51

Dies könnte auch mit ziemlicher Sicherheit weiter golfen werden;)

Ko_/zNS{zFGK~Y]*+*t/u*GHm/zdK1/zG]k]G/zG)ssCY

Erstellt eine Liste mit Listen, wobei jede innere Liste aus einer Reihe leerer Zeichenfolgen und dem Namen der Süßigkeit besteht. Diese Liste wird transponiert und dann werden die inneren Listen verbunden, gefolgt von diesen Listen, die verbunden werden.

Danke @isaacg, dass du mich an die Summe erinnert hast!

FryAmTheEggman
quelle
2
sauf einer Liste von Zeichenfolgen funktioniert als j"".
isaacg
3

APL: 38

v⌷⍨⊂⍋⌽(n/-n),⍪∊+\¨n⍴¨÷n←{≢⍵}⌸v←{⍵[⍋⍵]}

Erläuterung:

v←{⍵[⍋⍵]}    orders input string
n←{≢⍵}⌸v     counts how many times each element appears in v
∊+\¨n⍴¨÷n     makes incremental sums in each letter "group" 
⍋⌽(n/-n),⍪   appends number of elements in letter group and orders the obtained matrix
v⌷⍨⊂         orders vector v with computed indices

Kann auf tryapl.org getestet werden

Moris Zucca
quelle
2

R - 166 Zeichen

library("plyr");s=function(a){l=table(strsplit(a,s="")[[1]]);l=ldply(l[order(-l,names(l))],function(n)data.frame(seq_len(n)/n));paste(l[order(l[[2]]),1],collapse="")}

ungolfed version

library("plyr")
s <- function(a) {
    tbl <- table(strsplit(a, split = "")[[1]])
    tbl <- tbl[order(-tbl, names(tbl))]
    tbl <- ldply(tbl, function(n) {data.frame(seq_len(n)/n)})
    paste(tbl[order(tbl[[2]]),1], collapse = "")
}

Erläuterung:

  • In einzelne Zeichen aufteilen
  • Tabellarische Nummer jedes Zeichens
  • Sortieren Sie die Tabelle in die häufigste und dann in die lexikalische Reihenfolge
  • Indexpositionen zur Auswahl bei 1 / n, 2 / n, 3 / n, ... n-1 / n, 1 wobei n die Anzahl der Bonbons ist
  • Süßigkeiten nach Index sortieren (order sortieren ist in der Sortierung stabil, behält also die häufigste / lexikalische Benennungsreihenfolge bei, wenn ein Gleichstand im Index vorliegt, besonders wichtig bei den letzten Bonbons)
  • Verketten Sie die Bonbonnamen, um die Ausgabezeichenfolge zu erstellen

Die Matrixnatur des Problems ließ mich denken, dass R vielleicht eine Chance hat, aber die beste wörtliche Interpretation des Algorithmus, den ich tun konnte, waren 211 Zeichen:

l=function(a){l=table(strsplit(a,s="")[[1]]);l=l[order(-l,names(l))];o=Reduce(`*`,l);m=matrix("",nc=o,nr=length(l));for(r in seq_along(l)){x=l[r];for(c in seq_len(x)*o/x){m[r,c]<-names(x)}};paste(m,collapse="")}

ungolfed:

l <- function(a) {
    tbl <- table(strsplit(a, split = "")[[1]])
    tbl <- tbl[order(-tbl, names(tbl))]
    o <- Reduce(`*`, tbl)
    m <- matrix("", ncol = o, nrow = length(tbl))
    for (r in seq_along(tbl)) {
        for (c in seq_len(tbl[r])*o/tbl[r]) {
            m[r,c] <- names(tbl[r])
        }
    }
    paste(m, collapse="")
}
Brian Diggs
quelle
2

Pyth, 29 Bytes

Dies ist eine direkte Übersetzung meines CJam Answe R in Pyth

oc/|$Y.append(N)$YN/zNo_/zZSz

Probieren Sie es hier online aus


Diese Lösung hat eine ziemlich lange Geschichte und @isaacg hat mir sehr geholfen, diese neue Sprache zu verstehen.

Im Idealfall ist dies die genaue Wort-zu-Wort-Übersetzung meines CJam-Codes ( 17 Byte ):

oc/~kNN/zNo_/zZSz

was bedeutet:

o         order_by(lambda N:
 c                 div(
  /                    count(
   ~kN                       k+=N,                #Update k (initially ""), add N
   N                         N),                  #Count N in updated k
  /zN                  count(z, N)),
 o                 order_by(lambda Z:
  _                         neg(
   /zZ                          count(z, Z)),
  Sz                        sorted(z)))

Leider gibt Python in a nichts zurück += Aufruf , so dass es sich nicht um einen gültigen Python-Code handelte, also auch um einen ungültigen Python-Code, da ein Lambda nur eine return-Anweisung sein kann.

Dann habe ich verschiedene Methoden untersucht und festgestellt, dass Python list.appendeinen NoneWert zurückgibt , den ich verwenden kann. Code auf ( 19 Byte ) setzen:

oc/|aYNYN/zNo_/zZSz

was bedeutet:

o         order_by(lambda N:
 c                 div(
  /                    count(
   |aYN                      (Y.append(N) or
    Y                         Y)                 #Update Y (initially []), append N
   N                         N),                 #Count N in updated Y
  /zN                  count(z, N)),
 o                 order_by(lambda Z:
  _                         neg(
   /zZ                          count(z, Z)),
  Sz                        sorted(z)))

Leider wurde die Unterstützung von a(append) aus Pyth entfernt und die Version, die die Unterstützung hat, hat nicht die Unterstützung für o.

Update: aIn Pyth wurde Unterstützung hinzugefügt, sodass der oben genannte 19-Byte-Code im Online-Compiler funktioniert. Da es sich jedoch um eine neue Funktion handelt, die nach dem OP hinzugefügt wurde, stelle ich sie nicht als mein Ergebnis dar und lasse den 29-Byte-Code als meine Lösung zu.

Deshalb musste ich mich in diesem Fall auf Raw Python verlassen, um den Code zu erstellen

o         order_by(lambda N:
 c                 div(
  /                    count(
   |$Y.append(N)$            (Y.append(N) or
    Y                         Y)                 #Update Y (initially []), append N
   N                         N),                 #Count N in updated Y
  /zN                  count(z, N)),
 o                 order_by(lambda Z:
  _                         neg(
   /zZ                          count(z, Z)),
  Sz                        sorted(z)))
Optimierer
quelle