Buatkan saya jumlah sihir minimum

27

Menjaga tantangan ini singkat.

Anda diberi 4 angka: p1, p2, p3 dan p4.

Jumlah ajaib dari angka didefinisikan sebagai berikut:

magic_sum = |p1 - p2| + |p2 - p3| + |p3 - p4| + |p4 - p1|

Anda hanya diperbolehkan mengubah salah satu dari nilai integer di atas (p1, p2, p3 atau p4). Anda perlu mengubah nilai sedemikian rupa sehingga jumlah ajaib nilai mencapai nilai minimumnya.

Sebagai contoh:

p1, p2, p3, p4 = 17, -6, 15, 33. Nilai dari jumlah ajaib adalah 78 dalam kasus ini.

Anda dapat mengubah -6 di sini menjadi 16, dan nilai jumlah ajaib akan menjadi 36, yang merupakan nilai minimum yang dapat dicapai.

Ingatlah bahwa angka dapat berupa bilangan bulat positif atau negatif.

Ini adalah kode-golf, jadi paling tidak byte dalam kode menang. Brownie menunjuk untuk menggunakan Bahasa Praktis daripada bahasa Rekreasi. Semoga tanggal 4 bersamamu.

Untuk mengulangi:

Contoh 1

Input 1

17 -6 15 33

Keluaran 1

36

Penjelasan 1

-6 dapat diganti dengan 16 dan itu memberi kita jumlah magic minimum yang bisa dicapai.

Contoh 2

Input 2

10 10 10 10

Keluaran 2

0 or 2

keduanya bisa diterima

Penjelasan 2

Jumlah magic minimum yang dapat dicapai adalah 0 karena jumlah minimum dari 4 bilangan bulat positif adalah 0. Jika angka harus diubah, maka salah satu dari 10 dapat diubah menjadi 9 dan dengan demikian menghasilkan output 2.

Contoh 3

Input 3

1 2 3 4

Keluaran 3

4

Penjelasan 3

Input dengan sendirinya menghasilkan 6 sebagai jumlah ajaibnya. Mengubah 4 ke 1 dan jumlah magic minimum tercapai, yaitu 4.

Koishore Roy
sumber
10
+1, tetapi dapat dilakukan dengan lebih banyak contoh.
Jonathan Allan
2
Sebuah contoh yang berfungsi penuh dan beberapa lagi kasus uji dan itu +1dari saya.
Shaggy
@ Shaggy selesai. di mana +1 saya? : P
Koishore Roy
1
@ KoishoreRoy Tidakkah test case 3 menjadi 6 tanpa perubahan?
wizzwizz4
@ wizzwizz4 | 1 - 2 | + | 2 - 3 | + | 3 - 4 | + | 4 - 1 | = 1 + 1 + 1 + 3 = 6. Anda benar. Edit.
Koishore Roy

Jawaban:

14

Jelly , 6 byte

ṢŒœIṂḤ

Cobalah online!

Port jawaban Python saya .

     (input)        [17, -6, 15, 33]
Ṣ    sort           [-6, 15, 17, 33]
Œœ   odd-even elts  [[-6, 17], [15, 33]]
I    increments     [23, 18]
M    minimum        18
Ḥ    double         36 
Tidak
sumber
20

Python 2 , 44 byte

a,b,c,d=sorted(input())
print min(c-a,d-b)*2

Cobalah online!

Mengurutkan input seperti a,b,c,d,dalam urutan menaik, mengambil yang lebih kecil dari c-adan d-b, dan menggandakannya. Mengapa ini bekerja?

Pertama, perhatikan bahwa ketika kita mengubah elemen untuk memaksimalkan ke jumlah total siklus siklik, itu optimal (atau terikat untuk optimal) untuk mengubahnya menjadi sama dengan tetangga, seperti 17, -6, 15, 33 -> 17, 17, 15, 33. Itu karena jarak total barunya ke tetangga siklik kiri dan kanannya setidaknya jarak antara tetangga-tetangga itu, jadi menjadikan ini sama adalah yang terbaik yang bisa kita lakukan.

Sekarang, menghapus satu dari dua salinan nomor yang berdekatan memberikan jumlah siklus yang sama. Dalam contoh ini 17, 15, 33, memberi jarak 2 + 18 + 16. Jadi alih-alih mengganti salah satu dari empat angka, itu sama saja dengan menghapusnya menyisakan tiga angka, dan menggunakan jumlah jarak siklik mereka.

Perhatikan bahwa dengan 3 angka, jarak terbesar adalah jumlah dari dua angka yang lebih kecil. Ini karena jika kita mengurutkan angka untuk dimiliki a ≤ b ≤ c, maka |a - c| = |a - b| + |b - c|. Dengan kata lain, kami melakukan perjalanan antara nomor terbesar dan terkecil dua kali, menggunakan nomor sedang sebagai pit stop satu kali. Jadi, jumlah dari ketiga jarak itu hanya dua kali jarak antara minimum dan maksimum, jadi (c-a)*2.

Jadi, pertanyaannya adalah nomor mana yang kita hapus untuk mendapatkan jarak terkecil antara minimum dan maksimum dari tiga angka yang tersisa. Jelas kami menghapus angka yang terkecil atau terbesar. Menyebut mereka a, b, c, ddalam urutan, menghapus adaun d - b, dan menghapus ddaun c - a, dan hasil akhirnya adalah dua kali lipat mana yang lebih kecil.

Tidak
sumber
bantu saya dengan test case di sini. bagaimana jika jumlah ajaib sudah 0, yang merupakan angka terendah yang dapat dicapai. dalam hal ini, haruskah jawabannya 0? atau angka serendah mungkin berikutnya. Jika inputnya [10,10,10,10], jumlah ajaibnya adalah 0, serendah mungkin yang kedua adalah 2. Biarkan saya tahu apa yang Anda pikirkan.
Koishore Roy
Apa yang saya dengar Anda katakan, adalah bahwa Anda bisa mengabaikan urutan empat angka yang diberikan (langkah pertama Anda adalah menyortirnya). Tetapi bagaimana jika kami telah meminta lima nomor p1melalui p5, dan masih hanya diperbolehkan mengubah satu nomor? Kasing empat angka sepertinya terlalu mudah (hanya setelah melihat jawaban Anda).
Jeppe Stig Nielsen
@ KoishoreRoy Saya suka solusi Anda untuk mengizinkan keduanya.
xnor
@JeppeStigNielsen Ya, fakta bahwa pesanan tidak masalah adalah spesial untuk 4 angka, dan itu terjadi karena setelah menghapus satu untuk membuat tiga angka, semua pasangan angka berdekatan secara siklikal. Dengan lima angka ini tidak akan berhasil (Anda pasti dapat menemukan contoh), dan tantangannya akan sangat berbeda.
xnor
Seandainya saya bisa membesarkan dua kali. Pengamatan yang indah, dijelaskan dengan baik.
Jonah
9

R , 66 33 byte

function(x)2*min(diff(sort(x),2))

Cobalah online!

Jauh lebih pendek dengan algoritme xnor (baca penjelasan mereka dan tingkatkan posnya!).

Versi lama:

R , 66 byte

function(x,m=matrix(x,3,4))min(colSums(abs(diff(rbind(m,m[1,])))))

Cobalah online!

Mengambil input sebagai vektor 4 bilangan bulat.

hal2hal2hal1hal2hal3|hal1-hal2|+|hal2-hal3|hal2=hal1.

Ada 4 cara memilih nomor mana yang kita ubah; untuk masing-masing ini, kita hanya perlu menghitung jumlah dari 3 perbedaan absolut.

3×4rbind

Robin Ryder
sumber
4

Jelly , 11 10 byte

I;SASƲ$-ƤṂ

Cobalah online!

Tautan monadik yang mengambil daftar jika bilangan bulat sebagai input. Harus bekerja untuk ukuran daftar yang berubah-ubah. Bekerja atas dasar bahwa jumlah minimum dapat diperoleh dengan menguji menghapus setiap nomor dari daftar, menghitung jumlah ajaib dan mengambil jumlah minimum.

Nick Kennedy
sumber
3

Jelly , 8 byte

ṁ-Ƥ⁸IA§Ṃ

Tautan monadik yang menerima daftar bilangan bulat * yang menghasilkan bilangan bulat

* dapat berupa angka apa saja asalkan ada lebih dari 1; menggunakan formula sihir gaya yang sama menjumlahkan perbedaan tetangga membungkus.

Cobalah online!

Bagaimana?

ṁ-Ƥ⁸IA§Ṃ - Link: list of integers, X       e.g. [17,-6,15,33]
 -Ƥ      - for overlapping "outfixes" of length length(X)-1:
         -                                      [[-6,15,33],[17,15,33],[17,-6,33],[17,-6,15]]
ṁ  ⁸     -   mould like X                       [[-6,15,33,-6],[17,15,33,17],[17,-6,33,17],[17,-6,15,17]]
    I    - incremental differences              [[21,18,-39],[-2,18,-16],[-23,39,-16],[-23,21,2]]
     A   - absolute (vectorises)                [[21,18,39],[2,18,16],[23,39,16],[23,21,2]]
      §  - sums                                 [78,36,78,46]
       Ṃ - minimum                              36
Jonathan Allan
sumber
3

Japt -Q , 11 byte

ñÍó ®r- ÑÃn

Menggunakan algoritma xnor, yang menyelamatkan saya 4 byte.

Disimpan 5 byte berkat @Shaggy

Cobalah

Perwujudan Ketidaktahuan
sumber
tampaknya berfungsi dengan baik, tetapi apakah Anda akan menjelaskan mengapa ini berhasil?
Koishore Roy
@ KoishoreRoy Menambahkan penjelasan
Perwujudan Ketidaktahuan
29 byte (saya pikir )
Shaggy
@Shaggy ketika saya memperbarui jawaban saya, saya secara tidak sengaja mengganti jumlah dengan peta, membuat beberapa golf tidak valid, tetapi yang lain bagus
Perwujudan Ketidaktahuan
Baik (lanjut) bermain golf :) Anda dapat menyimpan 1 byte lebih banyak dengan mengganti ÃÃdengan baris baru.
Shaggy
3

J , 24 20 18 17 byte

versi alternatif menggunakan algoritma xnor:

2*[:<./2 2-/@$\:~

bagaimana

Dua kali 2 *min dari [:<./baris kedua dikurangi dari baris pertama [:-/matriks 2x2 yang dibentuk dengan membentuk 2 2$input yang diurutkan ke bawah\:~

Cobalah online!

jawaban asli: J , 24 byte

[:<./1(1#.2|@-/\],{.)\.]

Cobalah online!

Menggunakan ide Nick Kennedy.

  • 1(...)\.] menerapkan kata kerja dalam parens ke semua outfixes dari panjang 1 (outfix of length n adalah daftar dengan n elemen yang berdekatan dihapus, jadi ini menghasilkan setiap daftar yang mungkin dengan 1 elm dihapus)
  • (1 #. 2 |@-/\ ] , {.)ini menghitung jumlah ajaib dengan menambahkan elm pertama ke input ] , {.dan menerapkan perbedaan abs |@-/ke infiks panjang 2 2 ...\, dan menjumlahkan hasilnya 1 #..
  • [:<./ mengembalikan min
Jonah
sumber
2

05AB1E , 11 7 byte

Port of @xnor jawaban Jelly .
-4 byte terima kasih kepada @Emigna dan @Grimy .

{2ô`αß·

Cobalah online.

Alternatif 7 byte yang hanya berfungsi di versi lawas 05AB1E (akan memerlukan sebelum ¥versi baru):

{2ôø¥W·

Cobalah online.

Penjelasan:

{        # Sort the (implicit) input-list
         #  i.e. [17,-6,15,33] → [-6,15,17,33]
 2ô      # Split this list into parts of size 2
         #  → [[-6,15],[17,33]]
   `     # Push both separated to the stack
    α    # And take their absolute differences
         #  → [23,18]
     ß   # Pop and push the minimum
         #  → 18
      ·  # Double it (and output implicitly as result)
         #  → 36

{        # Sort the (implicit) input-list
         #  i.e. [17,-6,15,33] → [-6,15,17,33]
 2ô      # Split this list into parts of size 2
         #  → [[-6,15],[17,33]]
   ø     # Zip/transpose, swapping rows/columns
         #  → [[-6,17],[15,33]]
    ¥    # Get the deltas/forward differences of the inner lists
         #  → [[23],[18]]
     W   # Get the flattened minimum (without popping)
         #  → 18
      ·  # Double it (and output implicitly as result)
         #  → 36
Kevin Cruijssen
sumber
1
7 byte dalam warisan: {2ôø¥W·atau 8 dengan dalam penulisan ulang.
Emigna
2
7 byte dalam non-legacy:{2ô`αW·
Grimmy
@Emigna Smart, terima kasih!
Kevin Cruijssen
@ Terima kasih kotor juga!
Kevin Cruijssen
1

C ++ (gcc)

program lengkap: 138 byte

#include<iostream>
#include<regex>
using namespace std;int main(){int a[4];for(int&b:a)cin>>b;sort(a,a+4);cout<<min(a[2]-*a,a[3]-a[1])*2;}

Cobalah online!

fungsi inti: 84 byte

#include<regex>
int m(int*a){std::sort(a,a+4);return std::min(a[2]-*a,a[3]-a[1])*2;}

Cobalah online!

Juga menggunakan algoritma xnor yang dijelaskan dalam postingan Python 2-nya.

movatica
sumber
0

Arang , 20 byte

I⌊EEθΦθ⁻κμΣEι↔⁻λ§ι⊕μ

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Ternyata saya menggunakan ide @ NickKennedy. Penjelasan:

   Eθ                   Map over input array
     Φθ                 Filter over input array where
       ⁻κμ              Outer and inner indices differ
  E                     Map over resulting list of lists
           Eι           Map over remaining values in list
                §ι⊕μ    Get the next value in the list
             ↔⁻λ        Compute the absolute difference with the current value
          Σ             Take the sum of absolute differences
 ⌊                      Take the minimum sum
I                       Cast to string and implicitly print
Neil
sumber
0

JavaScript (ES6), 51 byte

Menggunakan metode xnor yang jauh lebih pintar :

a=>([a,b,c,d]=a.sort((a,b)=>a-b),b+c<a+d?c-a:d-b)*2

Cobalah online!


Jawaban asli, 96 byte

Mengambil input sebagai array dari 4 bilangan bulat. Mungkin bukan pendekatan yang terpendek.

a=>a.map(m=x=>a.map((y,i)=>a[m=a.map(v=>s+=Math.abs(p-(p=v)),a[i]=x,p=a[3],s=0)|m<s?m:s,i]=y))|m

Cobalah online!

Arnauld
sumber
0

Java 8 , 235 byte

Port jawaban dan algoritma Python @ xnor

import java.util.*;interface M{static void main(String[]A){Scanner I=new Scanner(System.in);int a[]={0,0,0,0};for(int i=0;i<4;a[i++]=I.nextInt());java.util.Arrays.sort(a);System.out.print(2*(a[2]-a[0]>a[3]-a[1]?a[3]-a[1]:a[2]-a[0]));}}

Cobalah online!

Java 10 , tidak terbukti, 222 byte

Dengan Java 10, saya harus dapat mengganti sisi kiri deklarasi Pemindai dengan var, meskipun saya tidak dapat mengompilasinya secara online dan karenanya saya hanya dapat menambahkannya sebagai hal yang sepele. Maaf.

interface M{static void main(String[]A){var I=new java.util.Scanner(System.in);int a[]={0,0,0,0};for(int i=3;i<4;a[i++]=I.nextInt());java.util.Arrays.sort(a);System.out.print(2*(a[2]-a[0]>a[3]-a[1]?a[3]-a[1]:a[2]-a[0]));}}
Debu berlian
sumber
1
AFAIK Anda hanya dapat memiliki fungsi sebagai kiriman Anda, seperti bagaimana jawaban lainnya telah dilakukan. Tidak perlu menyertakan kelas, antarmuka, dll.
Tau