Makan Permen dalam Urutan yang Benar

36

Ketika berbicara tentang memakan permen, saya memegang standar yang lebih tinggi daripada orang awam pada umumnya. Ada keseimbangan halus antara "mencampurnya" dan "menyimpan yang terbaik untuk yang terakhir."

Dalam tantangan ini, Anda akan diberi serangkaian karakter di mana setiap karakter mewakili sepotong permen. Karakter yang berbeda (peka huruf besar kecil) mewakili berbagai jenis permen. Program Anda kemudian harus menentukan urutan konsumsi permen yang benar, berdasarkan prosedur di bawah ini. Anda dapat menulis program lengkap (STDIN / STDOUT) atau fungsi yang disebutkan untuk menyelesaikan tugas ini.

Katakanlah simpanan permen saya adalah oroybgrbbyrorypoprr. Pertama, saya mengurutkan permen menjadi tumpukan dari jenis yang sama, dengan jumlah yang lebih besar di bagian atas, menggunakan nilai karakter ASCII yang lebih rendah sebagai tie-breaker.

rrrrrr
oooo
bbb
yyy
pp
g

Kemudian, saya mengambil setiap baris permen dan menempatkannya dalam jarak yang sama. Misalnya, jika ada 3 potong permen, satu ditempatkan 1/3 dari jalan, 2/3 dari jalan, dan pada akhirnya.

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

Lalu, saya turun setiap kolom untuk membuat pesanan permen terakhir saya rorbyroprbyorrobypg,.

Memasukkan

Tali yang berisi simpanan permen. Input untuk contoh di atas bisa jadi:

oroybgrbbyrorypoprr

Keluaran

Seutas berisi permen ditata ulang ke dalam urutan konsumsi yang benar.

rorbyroprbyorrobypg

Mencetak gol

Ini kode golf. Jawaban terpendek dalam byte menang. Aturan standar kode-golf berlaku.

PhiNotPi
sumber
Apakah Anda hanya menambahkan ruang yang lebih besar jika angka permen tidak merata? Mari kita katakan dalam kasus ini jika Anda memiliki satu r permen lagi seperti apa grid itu?
Vajura
38
Akhirnya seseorang yang TAHU cara makan permen.
Michael M.
12
Jadi ... pada dasarnya permen dithering.
COTO
9
Ini sebenarnya sangat dekat dengan cara saya memakan permen saya. :)
Emil
3
Seberapa serakah satu orang bisa mendapatkan? Apakah ada batasan jumlah permen untuk dimakan?
Alchymist

Jawaban:

12

CJam, 78 68 61 45 42 39 31 30 byte

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

Mengambil string input melalui STDIN

Terinspirasi oleh pendekatan rekursif, tetapi sedikit berbeda. Tidak perlu transpos atau persegi panjang sama sekali !.

Bagaimana itu bekerja:

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";

(Sedih bahwa CJam tidak dapat lagi lengkap dengan Pyth karena membutuhkan begitu banyak mengasapi sintaksis)

Coba di sini

Pengoptimal
sumber
4
Saya tidak berpikir Anda membutuhkan LCM; setiap beberapa harus bekerja. Ini akan memungkinkan Anda untuk mengganti {_@_@{_@\%}h;/*}dengan :.
Dennis
<facepalm> tidak memikirkan itu.
Pengoptimal
Selamat atas separuh panjang Anda!
isaacg
Saya merasakan sarkasme dalam hal itu: D
Optimizer
11

Pyth , 25

shCoc/NhN/zhNm>o_/zZSzdUz

Gunakan algoritme baru, yang terinspirasi oleh jawaban ini .

(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))

Selangkah demi selangkah:

  1. Pertama, kami mengurutkan karakter berdasarkan kesamaan mereka, ikatan rusak berdasarkan abjad. Ini o_/zZSz. osama dengan Python sorted(<stuff>,key=<stuff>), dengan ekspresi lambda untuk kunci, kecuali itu menyimpannya sebagai string.

  2. Kemudian kami membuat daftar awalan string itu, dari panjang len(z)ke panjang 1. >sama dengan python <stuff>[<int>:].

  3. Kemudian, kami menyusun ulang daftar string awalan ini dengan lokasi fraksional, 0 menjadi tepi kiri dan 1 menjadi kanan, dari karakter pertama dari awalan pada tata letak persegi panjang yang terlihat pada pertanyaan. /NhNmenghitung berapa kali karakter pertama dalam awalan terjadi di awalan, sementara /zhNmemberikan jumlah kemunculan karakter pertama dalam awalan dalam string sebagai lubang. Ini memberikan setiap awalan yang dipimpin oleh masing-masing karakter dalam suatu grup fraksi yang berbeda, dari 1/kuntuk yang paling sering terjadi dari karakter itu ke k/kuntuk yang paling kiri. Menyusun ulang daftar awalan dengan nomor ini memberikan posisi yang sesuai dalam tata letak. Ikatan rusak menggunakan pemesanan sebelumnya, yang pertama dengan hitungan kemudian alfabet, seperti yang diinginkan.

  4. Akhirnya, kita perlu mengekstraksi karakter pertama dari setiap string awalan, menggabungkannya menjadi string tunggal, dan mencetaknya. Mengekstrak karakter pertama adalah hC. Cmelakukan matriks transpos pada daftar, sebenarnya zip(*x)dalam Python 3. hmengekstrak baris pertama dari matriks yang dihasilkan. Ini sebenarnya satu-satunya baris, karena keberadaan awalan 1 karakter mencegah baris lengkap lainnya terbentuk. smenjumlahkan karakter dalam tuple ini menjadi satu string. Pencetakan tersirat.

Uji:

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

Potongan program tambahan tentang 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

Jawaban lama:

Pyth , 34

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

Program ini berfungsi dengan menghitung berapa kali mereplikasi sublist tertentu. Sub-daftar terlihat seperti ['', '', '', '', ... , 'r']. Panjang total dari sub-daftar ini adalah produk dari jumlah kemunculan semua permen lainnya, yaitu u*G/zHS{-zd1. Sublist lengkap dibuat dengan mereplikasi daftar string kosong ]k,, yang berkali-kali, kemudian menghapus dan elemen dengan tdan menambahkan nama permen ke akhir +d.

Kemudian, sub-daftar ini direplikasi sebanyak permen yang ditemukan di input /zd, memastikan setiap daftar permen memiliki panjang yang sama.

Sekarang, dengan fungsi ini dipetakan di atas semua permen unik dalam urutan yang tepat ( o_/zNS{z), kami memiliki persegi panjang yang mirip dengan yang ada di pernyataan pertanyaan, tetapi dengan string kosong sebagai ganti titik. Melakukan matriks transpos ( C) diikuti oleh dua penjumlahan ( ss) memberikan string terakhir.

Verifikasi:

$ pyth programs/candy.pyth <<< 'oroybgrbbyrorypoprr'
rorbyroprbyorrobypg
isaacg
sumber
4
Sepertinya Pyth mendukung enkripsi dalam sintaks bahasa itu sendiri!
Pengoptimal
@Optimizer Enkripsi? Apa yang kamu bicarakan?
isaacg
Bagus! Saya mungkin tidak akan pernah berpikir untuk mengubah loop for menjadi peta. Jauh lebih bersih.
FryAmTheEggman
Lihatlah kode sumbernya. Tampaknya seperti pesan terenkripsi.
Pengoptimal
2
Bisakah Anda memberikan contoh langkah demi langkah algoritma terbaru? Cukup menyenangkan :)
Pengoptimal
6

Perl 5 - 62

61 kode + 1 bendera.

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

Pertama-tama pisahkan input ke dalam array karakter - /./g.

Tambahkan indeks kemunculan ke setiap huruf meninggalkan jumlah dalam variabel $a.. $zdengan map++$$_.$_. Sekarang arraynya adalah:

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

Kemudian mengonversinya menjadi semacam kunci gabungan: rasio $_/$$1, count tie breaker ~$_dan ASCII value tie breaker $_. Ini akan menghasilkan (di sini dengan ruang tambahan untuk kejelasan).

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

Ini dapat diurutkan dengan urutan lexicographical (default). Pada akhirnya ekstrak karakter terakhir dan cetak:print map/(.$)/

nutki
sumber
5

Python 3.x - 124 byte

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]))))
rekursif
sumber
Ini jauh lebih keren dari suatu algoritma daripada metode persegi panjang!
isaacg
4

Mathematica, 123 119 118 byte

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

Menentukan fungsi bernama f. Tidak Disatukan:

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

Menggunakan tipe rasional bawaan sepertinya ide yang bagus untuk ini. Tentu saja, ini tidak ada di dekat CJam. Pada dasarnya, saya mewakili kotak yang ditampilkan dalam tantangan sebagai daftar pasangan. Hal pertama dalam pasangan adalah kode karakter, yang kedua adalah posisinya sebagai fraksi kurang dari atau sama dengan 1 (kolom terakhir adalah 1). Setelah memastikan bahwa masing-masing karakter sudah dalam urutan yang benar, saya hanya perlu mengurutkan secara stabil dengan fraksi tersebut untuk mendapatkan hasil yang diinginkan.

Martin Ender
sumber
3

Pyth 45 47 48 51

Ini juga hampir bisa dipastikan golf;)

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

Bekerja dengan membangun daftar daftar, di mana setiap daftar bagian dalam adalah deretan string kosong dan nama permen. Daftar ini diubah dan kemudian daftar bagian dalam bergabung diikuti oleh daftar ini yang bergabung.

Terima kasih @isaacg untuk mengingatkan saya tentang jumlah!

FryAmTheEggman
sumber
2
spada daftar string berfungsi sebagai j"".
isaacg
3

APL: 38

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

Penjelasan:

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

Dapat diuji di tryapl.org

Moris Zucca
sumber
2

R - 166 karakter

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="")}

versi tanpa ungolfed

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 = "")
}

Penjelasan:

  • Dibagi menjadi beberapa karakter
  • Tabulasikan jumlah setiap karakter
  • Sortir tabel menjadi yang paling sering dan kemudian dengan urutan leksikal
  • Posisi indeks untuk seleksi di 1 / n, 2 / n, 3 / n, ... n-1 / n, 1 di mana n adalah jumlah permen
  • Urutkan nama permen berdasarkan indeks (order stabil dalam penyortiran, sehingga akan mempertahankan urutan penamaan paling sering / leksikal ketika dasi dalam indeks, khususnya penting dengan permen terakhir)
  • Gabungkan nama-nama permen bersama untuk membuat string output

Sifat matriks dari masalah ini membuat saya berpikir R mungkin bisa melakukan ini, tetapi interpretasi literal terbaik dari algoritma yang bisa saya lakukan adalah 211 karakter:

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
sumber
2

Pyth, 29 byte

Ini adalah terjemahan langsung CJam answe r saya di Pyth

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

Cobalah online di sini


Ada cerita yang agak panjang di balik solusi ini dan @isaacg banyak membantu saya dalam memahami bahasa baru ini.

Idealnya ini adalah terjemahan kata demi kata yang tepat dari kode CJam saya ( 17 byte ):

oc/~kNN/zNo_/zZSz

yang berarti:

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)))

Tapi sayangnya Python tidak mengembalikan apa pun dalam +=panggilan, jadi itu bukan kode Python yang valid, sehingga kode Pyth tidak valid juga seperti dalam Pyth, lambda hanya bisa menjadi pernyataan kembali.

Kemudian saya melihat ke berbagai metode dan akhirnya menemukan bahwa Python list.appendmengembalikan Nonenilai, yang dapat saya gunakan. Membuat kode menjadi ( 19 byte ):

oc/|aYNYN/zNo_/zZSz

yang berarti:

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)))

Tetapi sayangnya, dukungan a(append) telah dihapus dari Pyth dan versi yang memang memiliki dukungan, tidak memiliki dukungan untuk o.

Perbarui: a dukungan telah ditambahkan kembali dalam Pyth sekarang sehingga kode 19 byte di atas akan berfungsi di kompiler online. Tetapi karena ini adalah fitur baru yang ditambahkan setelah OP, saya tidak meletakkannya sebagai skor saya dan membiarkan kode 29 byte sebagai solusi saya.

Karena itu saya harus bergantung pada Python mentah dalam kasus itu, membuat kode menjadi

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)))
Pengoptimal
sumber