Array Tantangan # 2: Pisahkan Array Bertumpuk

36

Catatan: Ini adalah # 2 dalam serangkaian tantangan . Untuk tantangan sebelumnya, klik di sini .

Memisahkan Daftar Bersarang

Untuk memisahkan nilai dalam daftar bersarang, ratakan, lalu bungkus masing-masing nilai sehingga pada kedalaman yang sama seperti sebelumnya.

Artinya, daftar ini:

[1, [2, 3], [4, 4, [5, 2], 1]]

Akan menjadi:

[1, [2], [3], [4], [4], [[5]], [[2]], [1]]

Tantangan

Tugas Anda adalah menulis sebuah program yang mengambil semua daftar bilangan bulat positif (dalam batas bahasa Anda) dan melakukan operasi pemisahan ini.

Anda dapat mengirimkan fungsi yang menjadikan daftar sebagai argumen, atau program lengkap yang menjalankan I / O.

Karena ini adalah , pengiriman terpendek (dalam byte) menang! *

* Lubang golf standar dilarang. Kamu tahu latihannya.


Uji Kasus

Daftar input hanya akan berisi bilangan bulat dalam ukuran bilangan bulat standar bahasa Anda. Untuk menghindari kendala bahasa yang mencegahnya bersaing, nilai tidak akan disarangkan lebih dari 10.

Anda dapat berasumsi bahwa input tidak akan memiliki sub-daftar kosong: misalnya - [[5, []]]tidak akan diberikan. Namun, daftar utama bisa kosong.

[]            ->  []

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

Jangan ragu untuk meninggalkan komentar jika saya melewatkan sudut kotak.

Contoh

Aku melemparkan bersama-sama cepat (ungolfed) Python 3 solusi sebagai contoh - Anda bisa mengujinya pada repl.it .

FlipTack
sumber
Tambahkan testcase dengan angka lebih dari satu digit untuk jawaban berbasis string.
orlp
@ Atau ide bagus.
FlipTack
2
Bisakah kita mengasumsikan kedalaman maksimum tertentu? Katakan, 16?
orlp
@ Atau saya akan mengatakan ya, kedalaman maksimal bersarang akan menjadi 10, karena saya lebih tertarik pada algoritma dan eksekusi metode Anda daripada kendala bahasa Anda. Akan memperbarui utas sekarang.
FlipTack
Bolehkah saya menghasilkan sebagai string?
Rohan Jhunjhunwala

Jawaban:

4

Brachylog , 16 byte

:{##:0&:ga|g}ac|

Cobalah online!

Penjelasan

Example input: [1:[2:3]]

:{          }a     Apply the predicate below to each element of the list: [[1]:[[2]:[3]]]
              c    Concatenate: Output = [1:[2]:[3]]
               |   Or: Input = Output = []

  ##                 Input is a list: e.g. Input = [2:3]
    :0&              Call recursively the main predicate with this input: [2:3]
       :ga           Group each element in a list: Output = [[2]:[3]]
          |          Or (not a list): e.g. Input = 1
           g         Group into a list: Output = [1]
Fatalisasi
sumber
Apa yang dilakukan Zargumen tentang TIO? Tanpanya, ini sepertinya keluaran dengan true / false, yang membuatnya tampak Zperlu dalam hitungan byte.
FlipTack
@FlipTack Zmemberi tahu Brachylog bahwa argumen keluaran adalah variabel. Ini adalah variabel yang disatukan dengan output yang dihasilkan. Saat Anda menghapusnya, ini memberi tahu Brachylog bahwa outputnya adalah variabel anonim, dan sebagai gantinya akan mencetak apakah predikat utama berhasil atau gagal. Ini sama dengan di Prolog di mana hasilnya "dimasukkan" ke dalam variabel.
Fatalkan
Ok :) jawaban yang bagus!
FlipTack
19

Mathematica, 24 21 byte

##&@@List/@#0/@#&/@#&

atau salah satunya:

##&@@List/@#&/@#0/@#&
##&@@List@*#0/@#&/@#&
##&@@List/@#&@*#0/@#&

Penjelasan

Alasan mengapa hal ini begitu singkat adalah karena pada dasarnya rekursi yang tidak memerlukan kasus dasar yang eksplisit.

Ada banyak gula sintaksis di sini, jadi mari kita mulai dengan ungolfing ini. &menunjukkan fungsi yang tidak disebutkan namanya yang tersisa, yang argumennya ditulis sebagai #. Di dalam fungsi ini #0mengacu pada fungsi itu sendiri, yang memungkinkan seseorang untuk menulis fungsi rekursif tanpa nama. Tapi mari kita mulai dengan memberi nama fungsi bagian dalam dan menariknya:

f[x_] := ##& @@ List /@ f /@ x
f /@ # &

Gula sintaksis penting lainnya adalah f/@xyang merupakan kependekan dari Map[f, x]yaitu gula yang memanggil fsetiap elemen x. Alasannya f[x_] := ... f /@ xtidak menyebabkan rekursi yang tak terbatas adalah bahwa pemetaan sesuatu di atas atom membuat atom tidak berubah tanpa benar-benar memanggil fungsi. Oleh karena itu, kita tidak perlu memeriksa kasus dasar (elemen saat ini adalah bilangan bulat) secara eksplisit.

Jadi fungsi fpertama kali berulang ke daftar terdalam di dalam x, di mana titik f/@menjadi no-op. Lalu kita sebut menggunakan ##& @@ List /@itu. Memetakan Listdaftar hanya membungkus setiap elemen dalam daftar yang terpisah, jadi {1, 2, 3}jadilah {{1}, {2}, {3}}. Kemudian kita menerapkannya ##& , yang berarti kepala (yaitu daftar luar) diganti oleh ##&, jadi ini berubah menjadi ##&[{1}, {2}, {3}]. Tetapi ##&hanya mengembalikan argumen itu sebagaiSequence (yang dapat Anda anggap sebagai daftar yang tidak terbuka, atau semacam operator "percikan" dalam bahasa lain).

Jadi ##& @@ List /@mengubah daftar {1, 2, 3}menjadi {1}, {2}, {3}(semacam, hal terakhir yang benar-benar terbungkus di kepalaSequence , tetapi itu menghilang begitu kita menggunakan nilai di mana saja).

Itu meninggalkan pertanyaan mengapa fitu sendiri belum menjadi solusi untuk tantangan tersebut. Masalahnya adalah bahwa daftar terluar harus diperlakukan secara berbeda. Jika kami memiliki input, {{1, 2}, {3, 4}}kami ingin {{1}, {2}, {3}, {4}}dan tidak {{1}}, {{2}}, {{3}}, {{4}} . Solusi asli saya memperbaikinya dengan meneruskan hasil akhir sebagai daftar argumen Joinyang akan mengembalikan level terluar dari daftar, tetapi yang ini hanya melompati level terluar dengan menggunakan f dirinya sendiri dalam peta pada output. Karenanya fhanya diterapkan pada elemen individual dari daftar terluar dan tidak pernah menyentuh daftar itu.

Adapun tiga solusi lainnya, yang pertama hanya menerapkan rekursi di luar fyang juga berfungsi. Dua solusi lainnya menghindari Mapoperasi berulang dengan terlebih dahulu menyusun dua fungsi dan kemudian memetakan hasilnya hanya sekali.

Martin Ender
sumber
8

J , 19 18 byte

(<@]/@,~>)S:0 1{::

Ini adalah kata kerja anonim yang mengambil dan mengembalikan array kotak, yang merupakan versi bertumpuk array J (agak rumit). Lihat lulus semua kasus uji.

Penjelasan

Ini menggunakan operasi yang agak eksotis {::( peta ) dan S:( menyebar ), yang beroperasi pada array kotak. {::mengganti setiap daun dengan jalur kotak ke daun itu. S:menerapkan kata kerja yang diberikan ke kedalaman bersarang yang diberikan, kemudian memercikkan hasilnya ke dalam array.

(<@]/@,~>)S:0 1{::  Input is y.
(        )          Let's look at this verb first.
        >           Open the right argument,
      ,~            append the left argument to it,
    /               then reduce by
 <@]                boxing. This puts the left argument into as many nested boxes
                    as the right argument is long.
                    This verb is applied to y
               {::  and its map
            0 1     at levels 0 and 1.
                    This means that each leaf of y is paired with its path,
                    whose length happens to be the nesting depth of y,
                    and the auxiliary verb is applied to them.
          S:        The results are spread into an array.
Zgarb
sumber
3

R, 199 byte

function(l){y=unlist(l);f=function(x,d=0){lapply(x,function(y){if(class(y)=='list'){f(y,d=d+1)}else{d}})};d=unlist(f(l));lapply(1:length(d),function(w){q=y[w];if(d[w]){for(i in 1:d[w])q=list(q)};q})}

Pertanyaan ini SULIT. Daftar R agak aneh dan sama sekali tidak mudah untuk mengulang semua elemen sublists. Juga tidak mudah untuk kemudian menentukan kedalaman daftar itu. Kemudian tantangannya adalah menciptakan kembali daftar dengan semua elemen yang terpisah, jadi kita juga perlu cara untuk secara adaptif membuat daftar kedalaman tertentu.

Solusinya terdiri dari dua bagian besar. Fungsi rekursif yang melingkupi semua daftar dan mencatat kedalaman:

  f=function(x,d=0){
    lapply(x,function(y){
      if(class(y)=='list'){
        f(y,d=d+1)
      } else {
        d
      }})
  }

Ketika kami memiliki kedalaman dari setiap entri vektor unlist(l), disimpan d, kami secara implisit membuat daftar melalui lapply, dan mengisinya dengan fungsi berikut:

  lapply(1:length(d),function(w){
    q=y[w]
    if(d[w]){
      for(i in 1:d[w]){
        q=list(q)
      }
    }
    q
  })

Dalam panggilan yang berlaku ini, kami membuat objek qdengan nilai entri dalam daftar, memeriksa kedalamannya dan melihat apakah itu bukan nol. Jika nol, kita bisa membiarkannya sebagai nilai numerik. Jika bukan nol, kita perlu membuatnya dalam jumlah daftar itu. Jadi kami memanggil for-loop dkali dan berulang kali menelepon q=list(q).

lapplykemudian masukkan semua nilai ini ke qdalam daftar, buat output yang diinginkan.

Selesaikan program dengan jarak yang tepat dan semacamnya:

function(our.list){
  values <- unlist(our.list)
  f <- function(part.list, depth = 0){
    lapply(part.list, function(y){
      if(class(y)=='list'){
        f(y, depth <- depth + 1)
      } else {
        return(depth)
      }})
  }
  depths <- unlist(f(our.list))
  new.list <- lapply(1:length(depths), function(w){
    q <- values[w]
    if(depths[w] != 0){
      for(i in 1:depths[w]){
        q <- list(q)
      }
    }
    return(q)
  })
  return(new.list)
}
JAD
sumber
Bagusnya
is.list(y)bukan class(y)=='list'? tidak dapat memverifikasi bahwa itu benar-benar berfungsi.
Giuseppe
180 byte
Giuseppe
3

Retina , 34 byte

+`(.(?>()\[|(?<-2>)]|.)+)\2,
$1],[

Cobalah online!

Martin Ender
sumber
Bagaimana cara (?<-2>)kerjanya?
Kritixi Lithos
@KritixiLithos Ini adalah grup penyeimbang . Ini muncul dari capture stack 2 yang memungkinkan saya melacak kedalaman sarang saat ini.
Martin Ender
2

C (gcc), 147 byte

d=0,l,i;
P(n,c){for(;n--;)putchar(c);}
main(c){for(;~(c=getchar());l=i)i=isdigit(c),P((l<i)*d,91),P(i,c),P((l>i)*d,93),P(l>i,32),d+=(92-c)*(c>90);}

Input contoh:

1 [23 3] [40 4 [5 2] 1]

Contoh output:

1 [23] [3] [40] [4] [[5]] [[2]] [1]
orlp
sumber
2

ditumpuk , tidak bersaing, 25 byte

{e d:e$wrap d 1-*}cellmap

Ini adalah fungsi yang memodifikasi anggota atas tumpukan. Jika Anda ingin fungsi bonafide, cukup tambahkan [dan ]ke awal dan akhir. Coba di sini!

Ini versi yang bisa dibaca:

{ arr :
  arr { ele depth :
    ele   $wrap depth 1- * (* execute wrap n times, according to the depth *)
  } cellmap (* apply to each cell, then collect the results in an array *)
} @:a2
(1 (2 3) (4 4 (5 2) 1)) a2 out

Kasus cobaan:

(1 (2 3) (4 4 (5 2) 1))    (* arg on TOS *)
{e d:e$wrap d 1-*}cellmap
out                        (* display TOS *)

Output tanpa baris baru:

(1 (2) (3) (4) (4) ((5)) ((2)) (1))
Conor O'Brien
sumber
Apakah *seperti argumen ke blok kode?
Downgoat
@Downgoat dalam hal ini membungkus waktu argumen d-1. $funcadalah fungsi yang dapat dimanipulasi.
Conor O'Brien
2

PHP, 101 94 byte

disimpan 1 byte berkat @Christoph, disimpan 6 lainnya terinspirasi oleh itu.

function s($a){foreach($a as$b)if($b[0])foreach(s($b)as$c)$r[]=[$c];else$r[]=$b;return$r?:[];}

fungsi rekursif, cukup lurus ke depan

kerusakan

function s($a)
{
    foreach($a as$b)                // loop through array
        if($b[0])                       // if element is array
            foreach(s($b)as$c)$r[]=[$c];    // append separated elements to result
        else$r[]=$b;                    // else append element to result
    return$r?:[];                   // return result, empty array for empty input
}
Titus
sumber
Di mana hasilnya diinisialisasi?
Neil
@Neil: PHP tidak memerlukan inisialisasi eksplisit. Entah $rmendapatkan elemen dalam loop atau fungsi mengembalikan array kosong. Ini mungkin menghasilkan pemberitahuan, tetapi itu tidak dicetak dengan konfigurasi default.
Titus
Bukankah itu berarti bahwa Anda hanya akan dapat memanggilnya sekali saja?
Neil
1
Anda mungkin juga mendapatkan gila: !cos(). cos()mengembalikan nulluntuk setiap larik dan float! = 0 untuk setiap bilangan bulat positiv. Maksud saya ... siapa yang peduli dengan peringatan?
Christoph
1
@Christoph: peringatan dicetak, pemberitahuan tidak (dalam konfigurasi default). Tapi itu ide bagus! Hidup is_int: Membalikkan kondisi tidak menyelamatkan apa pun; Saya membutuhkan ruang antara elsedan foreach. TAPI: $b[0]untuk integer adalah NULL.
Titus
2

Python 2, 122 106 byte

Skor yang sangat buruk, hanya implementasi yang mudah.

Terima kasih kepada Zachary T karena telah membantu menghemat 16 byte!

def x(l,a=[],d=0):
 n=lambda b:b and[n(b-1)]or l
 if'['in`l`:[x(e,a,d+1)for e in l];return a
 else:a+=n(d)

Panggil xdengan satu argumen untuk dijalankan. Untuk beberapa alasan hanya dapat dijalankan sekali.

Biru
sumber
Anda dapat mengubah a+=[n(l,d)]ke a+=n(l,d),(perhatikan tanda koma)
FlipTack
Apakah Anda bahkan perlu menetapkan t?
Zacharý
Apakah ini berfungsi saat Anda memanggilnya lebih dari sekali?
Zacharý
Anda dapat pindah nke fungsi dan menghapus argumen pertama karena selalu akan begitu l.
Zacharý
repl.it/EwPz
Zacharý
2

JavaScript (Firefox 30-57), 53 byte

f=a=>[for(e of a)for(d of e.map?f(e):[e])e.map?[d]:d]

Jawaban ES6 terbaik yang saya miliki sejauh ini adalah 76 byte:

f=(a,r=[],d=0)=>a.map(e=>e.map?f(e,r,d+1):r.push((n=d=>d?[n(d-1)]:e)(d)))&&r
Neil
sumber
2
Di kedua blok kode, saya pikir Anda menghilangkan yang memimpin f=.
Conor O'Brien
@ ConorO'Brien Sekali lagi ...
Neil
1

Perl 6 , 60 47 byte

sub f{[$_~~List??|([$_] for .&f)!!$_ for |$^a]}

( Cobalah online. )

Penjelasan:

  1. [... for |$^a]: Iterate atas array input, dan buat array baru dari array tersebut.
  2. $_ ~~ List ?? ... !! ...: Untuk setiap elemen, periksa apakah itu sendiri array.
  3. |([$_] for .&f): Jika elemen adalah array, secara rekursif terapkan fungsinya, lakukan iterate pada elemen-elemen array baru yang dikembalikan dari panggilan rekursif itu, bungkus setiap elemen dalam arraynya sendiri, dan selipkan ke dalam daftar luar.
  4. $_: Jika elemen tersebut bukan sebuah array, berikan itu apa adanya.
seseorang
sumber
1

Haskell, 71 byte

data L=N Int|C[L] 
d#C l=((C .pure.d)#)=<<l
d#n=[d n]
f(C l)=C$(id#)=<<l

Sekali lagi saya harus mendefinisikan tipe daftar saya sendiri, karena daftar asli Haskell tidak dapat disarangkan secara sewenang-wenang. Tipe baru ini Ldapat dikembalikan dari suatu fungsi tetapi tidak dicetak secara default, jadi untuk melihat hasilnya, saya mendefinisikan showinstance untukL :

instance Show L where
  show (N n)=show n
  show (C l)=show l

Sekarang kita dapat melakukan beberapa tes di REPL:

*Main> f $ C[N 1, C[N 2, N 3], C[N 4, N 4, C[N 5, N 2], N 1]]
[1,[2],[3],[4],[4],[[5]],[[2]],[1]]

*Main> f $ C[C[N 6, C[C[N 7]]]]
[[6],[[[7]]]]

Cara kerjanya: rekursi sederhana yang melewati level bersarang sebagai fungsi Ckonstruktor. Kami mulai dengan fungsi identitas iddan setiap kali ada daftar (-> pencocokan pola d#C l=) kami menambahkan lapisan lebih lanjut C(-> C .pure.d) ke panggilan rekursif #ke semua elemen daftar. Jika kita menemukan nomor, kita cukup menerapkan fungsi level-bertelur dke nomor tersebut.

nimi
sumber
0

APL (Dyalog) , 44 byte *

Fungsi awalan diam-diam anonim. Mengambil daftar APL bersarang sebagai argumen dan mengembalikan array APL bersarang.

∊{⊃⊂⍣⍵,⍺}¨{⊃¨(j∊⎕D)⊆+\-'[]'∘.=j←⎕JSON⍵}

Cobalah online!

{... } terapkan fungsi eksplisit berikut di mana argumen diwakili oleh :

⎕JSON⍵ ubah argumen menjadi JSON

j← simpan di j

'[]'∘.= tabel di mana jsama dengan kurung buka (baris atas) dan tutup (baris bawah)

-⌿ baris atas dikurangi baris bawah (pengurangan perbedaan vertikal)

+\ jumlah kumulatif (ini memberikan tingkat bersarang untuk setiap karakter)

(... )⊆ partisi, memulai partisi baru setiap kali 1 tidak didahului dengan 1 in ...

  j∊⎕D di mana setiap karakter jadalah anggota dari set D igits

⊃¨ pilih yang pertama dari masing-masing (ini memberikan tingkat bersarang per nomor multi-digit)

∊{...  terapkan fungsi berikut ini untuk setiap level bersarang ( ), menggunakan elemen yang sesuai dari argumen ϵ nlisted (diratakan) sebagai argumen kiri ( ):

,⍺ ravel (sebutkan) nomornya (karena skalar tidak dapat dilampirkan)

⊂⍣⍵ lampirkan kali

 mengungkapkan (karena daftar yang paling dalam itu sendiri adalah sebuah selungkup)


* Menggunakan Dyalog klasik dengan ⎕ML←3(default pada banyak sistem), menggantikan untuk dan untuk . Tio!

Adm
sumber