Putuskan keberadaan total pemesanan

8

Dalam tugas ini, kami mempertimbangkan array bilangan bulat positif seperti ini:

3 18 321 17 4 4 51 1 293 17

Input tersebut terdiri dari sepasang array seperti itu, baik dari panjang positif, sewenang-wenang, mungkin berbeda. Menentukan apakah pemesanan Total ≤ XN × N , di mana N adalah himpunan bilangan bulat positif, ada sehingga kedua array masukan dalam rangka sehubungan dengan ≤ X . Perhatikan bahwa (A ≤ X B ∧ B ≤ X A) ↔ A = B harus memegang, yaitu, dua angka dianggap sama di bawah ≤ X jika dan hanya jika mereka adalah nomor yang sama.

Misalnya, jika inputnya adalah sepasang array

7 2 1 1 4 12 3
9 8 7 2 5 1

maka Anda seharusnya mencari tahu apakah total pemesanan ≤ X ada sedemikian rupa

7 ≤ X 2 ≤ X 1 ≤ X 1 ≤ X 4 ≤ X 12 ≤ X 3

dan

9 ≤ X 8 ≤ X 7 ≤ X 2 ≤ X 5 ≤ X 1.

Kiriman Anda dapat berupa subrutin atau program yang menerima dua larik (sebagaimana ditentukan di atas) input dengan cara yang ditentukan implementasi, menghitung apakah total pemesanan ≤ X memenuhi permintaan yang disebutkan di atas ada dan mengembalikan satu nilai yang mewakili “ya” atau berbeda nilai yang mewakili "tidak." Pilihan nilai-nilai ini arbitrer, harap dokumentasikan.

Anda dapat mengasumsikan bahwa array input masing-masing berisi tidak lebih dari 2 15 - 1 elemen dan bahwa masing-masing elemen berada dalam kisaran dari 1 hingga 2 15 - 1 inklusif. Anda mungkin mengharuskan setiap array diakhiri oleh sentinel konstan di luar rentang yang disebutkan di atas seperti 0. Silakan tentukan sentinel apa yang dibutuhkan. Anda mungkin memerlukan panjang array sebagai input tambahan jika panjangnya tidak dapat disimpulkan dari array itu sendiri (mis. G dalam bahasa seperti C). Selain larangan celah standar, Anda tidak diperbolehkan menggunakan rutinitas penyortiran topologi.

Tantangan ini adalah golf kode. Kiriman dengan jumlah karakter paling sedikit menang.

FUZxxl
sumber
2
Untuk kemudahan semua orang, dapatkah Anda membuat beberapa contoh input / output untuk diuji?
orlp
1
Bisakah satu daftar bersifat paradoks dan memiliki loop sendiri?
jimmy23013
@ user23013 ya.
FUZxxl
@ Atau Tentu. Tolong beri saya waktu.
FUZxxl
1
@orlp Kesetaraan seharusnya tidak disentuh oleh urutan yang berbeda, tapi izinkan saya menambahkan paragraf.
FUZxxl

Jawaban:

4

Pyth, 28 22

L.AmqdSdmfhTmxhkbek^b2

Menciptakan fungsi yyang dapat Anda panggil dengan tuple yang berisi dua array. Mengembalikan "Benar" jika ada pemesanan total, "Salah" jika tidak.

Program pembantu yang mendefinisikan dan memanggil fungsi di atas dengan stdin:

L.AmqdSdmfhTmxhkbek^b2y,rw7rw7 

Coba di sini.

Kami pertama kali membaca kedua array. Kemudian kita akan membuat semua kombinasi dari kedua array. Kemudian untuk setiap kombinasi, kami akan menganggap array pertama adalah otoritatif, dan memeriksa apakah array konsisten dengan array kedua.

orlp
sumber
Apakah bilangan bulat positif sama untuk setiap output sejati? Ini adalah maksud dari spesifikasi bahwa ada satu bilangan bulat yang mewakili "ya" dan satu bilangan bulat yang mewakili tidak.
FUZxxl
@ FuZxxl Sekarang sudah.
orlp
Saya pikir Anda diizinkan untuk mengambil input apa pun yang Anda inginkan, yang akan menghemat banyak karakter. Receives two arrays ... in an implementation-defined way.Anda dapat menyimpan setidaknya 7 karakter.
isaacg
@isaacg Terima kasih, saya hanya bisa menyimpan 6, karena saya harus menggunakan lambda - saya harus memberikan subrutin atau program.
orlp
2

GolfScript, 25 byte

:A{:a;A{.a--.{a?}$=!},},!

Coba kode ini secara online.

Mengambil array dua (atau lebih!) Array di stack; mengembalikan 1 (benar) jika setiap pasang array input memiliki urutan total yang kompatibel, atau 0 (salah) sebaliknya.

Ia bekerja dengan mengulangi setiap pasangan array input yang mungkin (termasuk setiap array yang dipasangkan dengan dirinya sendiri), menyortir elemen-elemen dalam array pertama sesuai dengan posisi di mana mereka pertama kali terjadi pada array kedua (mengabaikan yang tidak ditemukan), dan memeriksa bahwa pesanan yang dihasilkan cocok dengan aslinya.

Walaupun kode ini dapat mengambil jumlah array input yang berubah-ubah, perlu dicatat bahwa kode ini hanya memeriksa konsistensi berpasangan . Sebagai contoh, ia mengembalikan true untuk input [[1 2] [2 3] [3 1]], karena dua dari tiga array memiliki total order yang konsisten. Namun, itu sudah cukup untuk kasus dua input, itulah yang dibutuhkan oleh tantangan.

Ini versi de-golf dengan komentar:

:A         # save input to "A", and leave it on the stack to be looped over
{          # run this outer loop for each input array:
  :a;      #   save this array to "a" (and pop it off the stack)
  A{       #   also run this inner loop for each input array:
    .a--   #     remove all elements not in "a" from this array
    .      #     make a copy of the filtered array
    {a?}$  #     sort it by the first location of each element in "a"
    =!     #     check whether the sorted copy differs from the original
  },       #   select those arrays for which there was a difference
},         # select those arrays for which at least one difference was found
!          # return 1 if no differences were found, 0 otherwise

Ps. Dimungkinkan untuk secara sepele menyimpan satu atau dua byte dengan meminta input untuk diberikan secara langsung dalam variabel bernama A, dan / atau dengan mengubah format output ke array kosong untuk "ya" dan array yang tidak kosong untuk "tidak" . Namun, itu tampak agak curang bagi saya.

Ilmari Karonen
sumber
Ini ide yang rapi. Mungkin saya sedang melakukan port solusi ini.
FUZxxl
2

J, 36 30 26 byte

[:*/@,(e.~(-:/:~)@#i.)&>/~

Mari kita panggil dua daftar input adan b. Fungsi memeriksa (dengan (e.~(-:/:~)@#i.)) apakah

  • aElemen diurutkan (sehubungan dengan a) dib
  • aElemen diurutkan (sehubungan dengan a) dia
  • bElemen diurutkan (sehubungan dengan b) dia
  • bElemen diurutkan (sehubungan dengan b) dib

Input adalah daftar dua vektor integer.

Hasilnya adalah 1jika ada pemesanan 0sebaliknya. (Runtime adalah O (n * n).)

Pemakaian:

   f=.[:*/@,(e.~(-:/:~)@#i.)&>/~

   a=.7 2 1 1 4 12 3 [b=.7 2 1 1 4 12 3 1 [c=.9 8 7 2 5 1
   f a;c
1
   f b;c
0

Cobalah online di sini.

randomra
sumber
Bagaimana btidak bisa disortir sehubungan dengan b?
FUZxxl
@FUZxxl misalnya b=1 2 1atau dalam contoh kedua sayab=7 2 1 1 4 12 3 1
randomra
Ok ... Agak masuk akal.
FUZxxl
1

Ruby, 79

!!gets(p).scan(r=/\d+/){|s|$'[/.*/].scan(r){s!=$&&~/\b#$& .*\b#{s}\b/&&return}}

Diharapkan input menjadi file dua baris angka yang dipisahkan oleh ruang. Kembali trueketika pemesanan ada, niljika tidak.

histokrat
sumber
Harap patuhi format keluaran: Kembalikan satu nilai yang menentukan keberadaan pemesanan atau nilai lain yang menentukan tidak adanya. Nilai-nilai ini harus independen dari input.
FUZxxl
Selesai Secara teknis bisa memenuhi spesifikasi dengan satu karakter lebih sedikit, tetapi kembali nilatau falsehanya merasa terlalu salah.
histokrat
Kembali nilatau falsesama sekali tidak masalah.
FUZxxl
1

Haskell, 98 byte

import Data.List
a%b=intersect(r a)$r b
r l=map head$group l
c l=nub l==r l
x#y=c x&&c y&&x%y==y%x

Pengembalian Trueatau False. Contoh penggunaan: [7,2,1,1,4,12,3] # [9,8,7,2,5,1]-> True.

Cara kerjanya: menghapus duplikat berturut-turut dari daftar input (misalnya:. [1,2,2,3,2] -> [1,2,3,2]Pesanan ada jika kedua daftar yang dihasilkan tidak mengandung duplikat dan persimpangan list1 dan list2 sama dengan persimpangan list2 dan list1.

nimi
sumber
Ini ide yang rapi.
FUZxxl