Temukan yang aneh secara berurutan

20

Tantangan:

Pertimbangkan fungsi di F(N) = 2^N + 1mana Nbilangan bulat positif kurang dari 31. Urutan yang didefinisikan oleh fungsi ini adalah:

3, 5, 9, 17, 33, 65, 129, 257, 513, 1025, 2049, 4097, 8193, 16385, 32769, 65537, 131073, 262145, 524289, 1048577, 2097153, 4194305, 8388609, 16777217, 33554433, 67108865, 134217729, 268435457, 536870913, 1073741825

Input akan dihasilkan sebagai berikut:

  • Ambil 5 bilangan bulat yang berdekatan dari urutan di atas.
  • Ganti salah satunya dengan bilangan bulat positif yang berbeda (yang mungkin atau mungkin bukan bagian dari urutan di atas).
  • Atur ulang secara opsional 5 angka yang dihasilkan.

Diberikan daftar 5 bilangan bulat seperti itu, temukan salah satu yang ditukar dan karenanya bukan bagian dari 5 bilangan bulat yang berdekatan yang asli.

Contoh:

  • Sublist asli: 5, 9, 17, 33, 65.
  • Mengganti satu: 5, 7, 17, 33, 65.
  • Reorder: 33, 17, 5, 7, 65.

Output yang diharapkan adalah 7.

5 nilai dalam input akan selalu berbeda dan selalu ada solusi unik. (Misalnya, Anda tidak perlu berurusan dengan input seperti di 3, 9, 17, 33, 129mana salah satu 3atau 129mungkin telah bertukar.)

Kasus uji:

5,9,17,33,829
o/p: 829

9,5,17,829,33
o/p: 829

33, 17, 5, 7, 65
o/p: 7

5,9,177,33,65
o/p: 177

65,129,259,513,1025
o/p: 259

129,259,513,1025,65
o/p: 259

63,129,257,513,1025
o/p: 63

65,129,257,513,4097
o/p: 4097

5, 9, 2, 17, 33
o/p: 2

536870913, 67108865, 1073741825, 1, 268435457
o/p: 1
Ajay
sumber
4
Untuk referensi di masa mendatang, kebingungan dan kesalahpahaman seperti ini sering dapat dihindari dengan memposting ide tantangan di kotak pasir terlebih dahulu, di mana Anda bisa mendapatkan umpan balik dari komunitas sebelum orang-orang mulai menyelesaikan tantangan Anda.
Martin Ender
@ Jay Karena masih ada sedikit kebingungan tentang spesifikasi saya telah mengedit tantangan sekali lagi dengan apa yang saya pikir maksud Anda di balik tantangan ini. Saya harap saya tidak salah mengartikannya, tetapi beri tahu saya jika ada yang salah.
Martin Ender
@MartinEnder test case baru seharusnya536870913,67108865,134217729,1,268435457
Jörg Hülsermann
@ JörgHülsermann Jangan ragu untuk menambahkannya juga, tetapi maksud saya adalah untuk menambahkan test case yang mencakup N = 30sebagai salah satu nilai input.
Martin Ender
1
Tantangan yang menarik karena sangat mudah untuk membuat algoritma yang salah. Dan memang saya belum pernah melihat begitu banyak jawaban yang salah diposting. Akan lebih buruk jika duplikat diizinkan (banyak metode berbasis set (termasuk metode saya) akan gagal)
Ton Hospel

Jawaban:

6

Jelly, 15 byte

⁹R2*‘ṡ5ḟ@€µEÐfQ

TryItOnline
Semua test case juga ada di TryItOnline

Mengembalikan daftar yang berisi satu daftar yang berisi daftar aneh.

Bagaimana?

⁹R2*‘ṡ5ḟ@€µEÐfQ - Main link, a (list)
⁹               - literal 256 (saving a byte over literal 30)
 R              - range, [1,2,3,...]
  2*            - 2 ** x, [2,4,8,...]
    ‘           - increment, [3,5,9,...]
     ṡ5         - all contiguous slices of length 5
       ḟ@€      - filter with reversed arguments for each
          µ     - monadic chain separation
            Ðf  - filter on condition:
           E    - all equal (those previously filtered lists with only one value)
              Q - unique (there can be two, but both will have the same odd-one-out)
Jonathan Allan
sumber
5

JavaScript (ES6), 62 byte

a=>a.find(n=>--n&--n|!n)||a.sort((a,b)=>a-b)[a[0]*16>a[3]?4:0]

Algoritma yang sama sekali baru, karena seperti @ edc65 tunjukkan yang sebelumnya rusak. Penjelasan: Kami pertama-tama menangani kasing yang mudah dengan mencari 2 atau angka yang tidak satu lebih besar dari kekuatan 2. Jika tidak ada yang ditemukan, maka ada dua kasing yang mungkin, tergantung pada apakah nilai ekstra di bawah atau di atas run asli dari lima, jadi kami memeriksa apakah nilai terkecil dan terbesar kedua milik menjalankan yang sama dari lima dan jika demikian menyalahkan nilai terbesar sebaliknya nilai terkecil.

Neil
sumber
Hampir ok tapi coba n-1&n-2dengan nilai2
edc65
@ edc65 Tidak berfungsi [3, 17, 33, 65, 257].
Neil
@ edc65 Apakah --n&--n|!nterlihat bagus untuk kasing 2?
Neil
Kelihatannya memang bagus
edc65
4

Python, 84 byte

def f(a,i=0):s=set(a)-{2**j+1for j in range(i,i+5)};return len(s)<2and s or f(a,i+1)

Semua test case ada di ideone

Untuk input yang valid mengembalikan satu set yang hanya berisi yang ganjil.
Untuk input yang tidak valid, batas rekursi akan tercapai dan kesalahan akan terjadi.

Jonathan Allan
sumber
4

Mathematica, 65 byte

f[a___,x_,b___]/;NestList[2#-1&,a~Min~b/. 2->0,4]~SubsetQ~{a,b}=x

Ini mendefinisikan fungsi fyang harus dipanggil dengan 5 argumen, misalnya

f[5, 9, 17, 33, 829]

Pada prinsipnya fungsi dapat dipanggil dengan sejumlah argumen (bukan nol), tetapi Anda mungkin mendapatkan hasil yang tidak diharapkan ...

Saya pikir ini adalah pertama kalinya, bahwa saya berhasil menempatkan seluruh solusi untuk tantangan non-sepele ke sisi kiri a =.

Penjelasan

Solusi ini benar-benar menempatkan kemampuan pencocokan pola Mathematica untuk kita. Fitur dasar yang kami gunakan adalah bahwa Mathematica tidak bisa hanya mendefinisikan fungsi-fungsi sederhana seperti f[x_] := (* some expression in x *)tetapi kita dapat menggunakan pola kompleks yang sewenang-wenang di sisi kiri, misalnya f[{a_, b_}, x_?OddQ] := ...akan menambahkan definisi fyang hanya digunakan ketika dipanggil dengan dua elemen daftar dan bilangan bulat ganjil. Mudahnya, kita sudah dapat memberikan nama ke elemen secara sewenang-wenang jauh di bawah ungkapan sisi kiri (misalnya dalam contoh terakhir, kita dapat langsung merujuk ke dua elemen daftar sebagai adan b).

Pola yang kami gunakan dalam tantangan ini adalah f[a___,x_,b___]. Berikut a___dan b___merupakan urutan nol atau lebih argumen dan xargumen tunggal. Karena sisi kanan definisi adalah sederhana x, apa yang kita inginkan adalah sihir yang memastikan yang xdigunakan untuk input yang kita cari dan a___dan b___hanya wildcard yang menutupi elemen yang tersisa.

Ini dilakukan dengan melampirkan kondisi ke pola dengan /;. Sisi kanan /;(semuanya hingga =) perlu kembali Trueagar pola ini cocok. Keindahannya adalah bahwa pencocokan pola Mathematica akan mencoba setiap penugasan tunggal a, xdan buntuk masukan bagi kita, sehingga pencarian elemen yang tepat dilakukan untuk kita. Ini pada dasarnya adalah solusi deklaratif untuk masalah tersebut.

Adapun kondisinya sendiri:

NestList[2#-1&,a~Min~b/. 2->0,4]~SubsetQ~{a,b}

Perhatikan bahwa ini tidak bergantung xsama sekali. Sebaliknya, kondisi ini hanya tergantung pada empat elemen yang tersisa. Ini adalah fitur nyaman lain dari solusi pencocokan pola: karena pola urutan, adan bbersama - sama berisi semua input lainnya.

Jadi kondisi ini perlu memeriksa apakah empat elemen yang tersisa adalah elemen yang berdekatan dari urutan kami dengan paling banyak satu celah. Ide dasar untuk memeriksa ini adalah bahwa kita menghasilkan empat elemen berikutnya dari minimum (via ) dan memeriksa apakah keempat elemen tersebut adalah bagian dari ini. Satu-satunya input yang dapat menimbulkan masalah adalah input yang mengandung a , karena ini juga menghasilkan elemen urutan yang valid, jadi kita perlu menanganinya secara terpisah.xi+1 = 2xi - 12

Bagian terakhir: mari kita lihat ekspresi yang sebenarnya, karena ada beberapa gula sintaksis yang lucu di sini.

...a~Min~b...

Notasi infiks ini adalah kependekan dari Min[a,b]. Tapi ingat itu adan bmerupakan urutan, jadi ini sebenarnya diperluas ke empat elemen Min[i1, i2, i3, i4]dan memberi kita elemen terkecil yang tersisa dalam input.

.../. 2->0

Jika ini menghasilkan 2, kami menggantinya dengan 0 (yang akan menghasilkan nilai yang tidak ada dalam urutan). Ruang diperlukan karena jika tidak, Mathematica mem-parsing float literal .2.

NestList[...&,...,4]

Kami menerapkan fungsi tanpa nama di sebelah kiri 4 kali untuk nilai ini dan mengumpulkan hasilnya dalam daftar.

2#-1&

Ini hanya mengalikan inputnya dengan 2 dan menurunkannya.

...~SubsetQ~{a,b}

Dan akhirnya, kami memeriksa bahwa daftar berisi semua elemen dari adan bmerupakan bagian dari ini.

Martin Ender
sumber
Saya tidak tahu Mathematica bisa melakukan ini!
DanTheMan
4

Racket 198 byte

(λ(m)(let((l(for/list((i(range 1 31)))(+ 1(expt 2 i))))(r 1)(n(length m)))(for((i(-(length l)n)))(let
((o(for/list((j m)#:unless(member j(take(drop l i)n)))j)))(when(eq?(length o)1)(set! r o))))r))

Versi tidak disatukan:

(define f
  (λ(m)
    (let ((l (for/list ((i (range 1 31))) 
               (+ 1 (expt 2 i))))
          (res 1)
          (n (length m)))
      (for ((i (- (length l) n)))
        (let ((o (for/list ((j m) 
                             #:unless (member j 
                                             (take (drop l i) n))) 
                    j)))
          (when (eq? (length o) 1)
            (set! res o))))
      res)))

Pengujian:

(f '(5 9 17 33 829))
(f '(9 5 17 829 33))
(f '(5 9 177 33 65))
(f '(65 129 259 513 1025))
(f '(129 259 513 1025 65))
(f '(63 129 257 513 1025))
(f '(65 129 257 513 4097))

Keluaran:

'(829)
'(829)
'(177)
'(259)
'(259)
'(63)
'(4097)
juga
sumber
2

05AB1E , 32 30 26 24 20 byte

30Lo>Œ5ùv¹yvyK}Dgi`q

Penjelasan

30Lo>    # list containing the sequence [3 .. 1073741825]
Œ5ù      # all sequence sublists of length 5
v        # for each such list
 ¹yvyK}  # remove it's elements from input
 Dgi     # if the remaining list has length 1
    `q   # end the program and print the final list flattened

Cobalah online!

Emigna
sumber
2

R, 97 byte

Ini ternyata lebih sulit dari yang saya kira. Saya yakin ini bisa bermain golf secara signifikan.

m=match(x<-sort(scan()),2^(1:31)+1);l=diff(m);ifelse(NA%in%m,x[is.na(m)],x[ifelse(l[4]>1,5,l>1)])

Tidak diikat dan dijelaskan

x<-sort(scan())                  # read input from stdin and sort, store as vector
m=match(x, 2^(1:31)+1)           # generate a vector of indices for which input matches the sequence
l=diff(m)                        # vector of the difference of indices (will only contain 4 elements)
ifelse(NA%in%m,                  # if m contains NA do:
       x[is.na(m)],              # return x where no match has been found, else:
       x[ifelse(l[4]>1,5,l>1)])  # return x by index where diff>1 unless it's the last object, then return x[5]

The match()fungsi akan kembali NAjika setiap elemen dari vektor input tidak dalam urutan dan akibatnya kita hanya dapat menemukan indeks di mana NAada di masukan dan kembali ini:x[is.na(m)]

Itu menjadi sedikit lebih rumit jika input adalah bagian dari urutan tetapi salah tempat. Karena input telah diurutkan, jarak antara masing-masing pasangan indeks harus 1. Karena itu kami dapat menemukan elemen yang salah tempat dengan menyelidiki 1stperbedaan dari indeks yang cocok l=diff(m)dan memilih indeks yang mana l>1. Ini hanya cukup jika bukan karena fakta yang lmengandung 4elemen daripada 5. Ini hanya masalah jika elemen terakhir dalam input yang disortir adalah anggota dari urutan NAMUN bukan bagian dari urutan berikutnya (seperti dalam kasus tes akhir). Akibatnya, jika 4thelemen >1mengambil 5thentri dalam input yang disortir lagi mencari indeks dalam 4vektor-panjang:x[ifelse(l[4]>1,5,l>1)]

Billywob
sumber
1
dalam versi terbaru R ada fungsi anyNAyang setara denganany(is.na(x))
JDL
2

Haskell, 66 64 byte

g x=[s|n<-[1..],[s]<-[filter(`notElem`[2^m+1|m<-[n..n+4]])x]]!!0

Contoh penggunaan: g [65,129,257,513,4097]-> 4097.

Putaran melalui semua daftar yang berdekatan dengan panjang 5 dari F(N), membuat elemen yang tidak ada dalam daftar input xdan pola cocok dengan panjang 1 (-> [s]).

Sunting: @xnatau menyimpan dua byte dengan menghapus batas atas loop luar. Karena sebuah solusi dijamin ada, kemalasan Haskell berhenti pada nomor pertama yang ditemukan.

nimi
sumber
Apakah Anda benar-benar membutuhkan batas atas 26?
xnor
1

Perl, 64 59 byte

Termasuk +2 untuk -an

Berikan daftar masukan pada STDIN:

perl -M5.010 oddout.pl <<< "5 9 2 17 33"

oddout.pl:

#!/usr/bin/perl -an
@a=grep$_,@a{@F,map{2**$_+++1}($.++)x5}=@F while$#a;say@a

Jika Anda tidak keberatan dengan jumlah ruang variabel di sekitar hasil, verson 58 byte ini berfungsi:

#!/usr/bin/perl -ap
$_=join$",@a{@F,map{2**$_+++1}($.++)x5}=@F while/\b +\b/

Kedua versi berulang selamanya jika input tidak memiliki solusi.

Ini kode yang sangat sakit, tapi saya tidak bisa memikirkan sesuatu yang elegan ...

Cara saya (ab) menggunakan %atrik perlgolf baru sejauh yang saya tahu.

Ton Hospel
sumber
1

Python 2, 73 byte

s=set(input());i,=d={1}
while~-len(s-d):i*=2;d=d-{i/32+1}|{i+1}
print s-d

Iterasi melalui set dlima elemen urutan berurutan hingga menemukan satu yang berisi semua kecuali satu elemen input, dan kemudian mencetak perbedaan, yang merupakan output dalam set singleton.

Rangkaian dlima elemen berturut-turut dibangun dari ketiadaan dengan menambahkan elemen baru berulang kali i+1dan menghapus elemen lama apa pun i/32+1yang muncul sebelum jendela 5. Saat ini, terlihat seperti apa progresnya.

{1}
{3}
{3, 5}
{3, 5, 9}
{3, 5, 9, 17}
{3, 5, 9, 17, 33}
{5, 9, 17, 33, 65}
{9, 17, 33, 65, 129}
{17, 33, 65, 129, 257}
{33, 65, 129, 257, 513}

Ada yang tersesat 1 di awal dari inisialisasi, tetapi tidak berbahaya karena segera dihapus. Set yang lebih kecil karena membangun hingga 5 elemen juga tidak berbahaya.

Tidak
sumber
1

PHP, 87 76 75 byte

for(;count($b=array_diff($argv,$a?:[]))-2;)$a[$n%5]=1<<++$n|1;echo end($b);

jalankan bersama php -r '<code>' <value1> <value2> <value3> <value4> <value5>

Titus
sumber
'a = [] `tidak perlu
Jörg Hülsermann
@ JörgHülsermann: Itu perlu untuk array_diff. Tapi saya bisa menyimpan satu byte di sana.
Titus
Ini menghasilkan array_diff peringatan (): Argumen # 2 bukan sebuah array. Cara yang bagus dengan mengisi array dengan mod 5. Ini akan menyelamatkan saya array_map dan berkisar dalam proposal saya
Jörg Hülsermann
1
endalih-alih maxdan catatan Anda tidak lebih penting
Jörg Hülsermann
1

C #, 69 byte

int M(int[]a)=>a.Except(new int[30].Select((_,i)=>(1<<i+1)+1)).Sum();

Patrik Westerlund
sumber
0

Java 7,85 byte

int f(int[]a,int l){int i=1;for(;i<l;)if(a[i++-1]*2-1!=a[i])return a[i];return a[0];}

Tidak disatukan

int f(int[]a,int l){
    int i=1;
    for(;i<l;)
    if(a[i++-1]*2-1!=a[i])
    return a[i];
   return a[0];

}
Numberknot
sumber
Hmm, apakah Anda yakin ini bekerja dengan benar? Karena saya mendapatkan output yang salah untuk test case 1, 5, 6, dan 7 (hanya output kedua, ketiga dan keempat yang benar). Juga, apakah parameter l31? Dalam pertanyaan saya hanya melihat int-array sebagai input, tetapi bukan int tambahan? : S
Kevin Cruijssen
Bukankah ini akan gagal jika nilai ganjil keluar adalah yang kedua (pada indeks 1)?
Ton Hospel
Maaf teman-teman, saya salah menafsirkan pertanyaan .. Sebenarnya sekarang saya di rumah sakit .. Saya akan mengubahnya dalam waktu singkat.
Numberknot
0

PHP, 76 Bytes

menerapkan ide Titus dengan mod 5

<?for(;count($x=array_diff($_GET[a],$r))-1;$r[++$i%5]=2**$i+1);echo end($x);

126 Bytes sebelumnya

<?for(;$x=array_diff($_GET[a],array_map(function($z){return 2**$z+1;},range(++$i,$i+4)));)if(count($x)<2){echo end($x);break;}
Jörg Hülsermann
sumber
fungsi anonim: array_map(function($z){return 2**$z+1;},range($i,$i+4)). $x[key($x)]->end($x)
Titus
Menempatkan 1-count($x=...)kondisi tersebut akan membuat Anda terbebas dari istirahat: for(;1-count($x=...););echo end($x);(-13)
Titus
0

Pyth, 18 byte

hhlD-LQ.:mh^2dSCd5

Bentuk urutan, ambil sublists dengan panjang 5, Hapus setiap sublist dari Q, ambil hasil terpendek, output satu-satunya elemen.

isaacg
sumber
Tidak bekerja untuk[5, 9, 2, 17, 33]
Emigna
0

Kotlin, 55 byte

fun f(a:IntArray)=a.find{it-1 !in(1..30).map{1 shl it}}

Patrik Westerlund
sumber