Bagaimana TIDAK untuk mengurangi pecahan

13

Mengurangi pecahan dengan cara yang salah

Dalam tantangan kode-golf ini Anda harus menemukan pecahan yang dapat direduksi dengan cara yang salah tetapi masih berakhir dalam jumlah yang sama.

Catatan: mengurangi pecahan dengan cara yang salah di sini memiliki definisi yang tepat, lihat detailnya.

Contoh:

64/16 = 6 4/1 6 = 4/1 = 4

Tentu saja Anda tidak bisa hanya menyerang kedua 6es tetapi di sini Anda masih berakhir dengan nilai yang benar. Dalam tantangan ini, Anda harus menemukan contoh seperti ini.

Detail

Anda harus menulis fungsi / program yang menerima satu bilangan bulat positif nsebagai input dan output / mengembalikan daftar / array fraksi dalam format
numerator1,denominator1,numerator2,denominator2,...

Program harus mencari tahu untuk setiap fraksi a/bdengan a+b=ndan a,b>0apakah itu dapat dikurangi dengan cara yang salah . (Tidak masalah apakah jika dapat dikurangi dengan cara konvensional atau apakah ada banyak kemungkinan pengurangan, itu hanya harus dimungkinkan untuk menguranginya dengan cara yang salah dalam setidaknya satu cara.)

Definisi cara yang salah: Fraksi dapat dikurangi dengan cara yang salah jika dan hanya jika urutan angka yang sama berturut-turut muncul dalam a dan b dan jika nilai fraksi tetap sama jika Anda menghapus substring.

Contoh: 1536/353 dapat 'direduksi' menjadi 16/3 tetapi kedua nilai tersebut tidak sama sehingga Anda tidak dapat mengurangi fraksi ini dengan cara yang salah .

Perhatikan bahwa definisi mengurangi cara yang salah juga dapat mencakup fraksi yang dikurangi dengan cara yang benar: 110/10 = 11/1ada dalam definisi mengurangi cara yang salah meskipun itu merupakan langkah yang valid.

Mencetak gol

Jumlah byte terkecil yang menang. Anda dapat menulis fungsi atau program yang menerima bilangan bulat dan mengembalikan array atau program yang menggunakan stdin / stdout atau Anda dapat mempertimbangkan dan disimpan dalam variabel dan pada akhir program daftar harus disimpan dalam variabel lain.

Uji kasus

Harap sertakan berikut testcases (Katakan padaku mana yang harus saya tambahkan, saya tidak tahu berapa banyak fraksi yang ada / berapa banyak contoh yang diharapkan)

n=80 (64/16 should be in this list)
n=147 (98/49 should be in this list)
n=500 (294/196 should be in this list) WRONG since 294+196 != 500 Thanks Falko
cacat
sumber
3
Pertimbangkan mendefinisikan istilah untuk "jalan yang salah", seperti "konyol" atau "aneh". Saya pikir posting akan lebih mudah dimengerti, karena pembaca segera grok bahwa harus ada definisi untuk istilah tersebut.
Michael Easter
3
Bagaimana jika ada beberapa cara untuk mengurangi pecahan dan hanya beberapa yang salah? 1010/10 = 101/1 && 1010/10 /= 110/1
John Dvorak
1
Varian projecteuler.net/problem=33 ?
user80551
1
Uji kasus kedua ( n=147) tidak benar: 49/89 != 4/8.
Beta Decay
1
Jika ada lebih dari satu cara untuk mengurangi pecahan, dapatkah kita memasukkannya beberapa kali dalam hasil yang ditetapkan?
John Dvorak

Jawaban:

3

Python 2 - 183 180

r=range
s=lambda a:[(a[i:j],int(a[:i]+a[j:]))for i in r(len(a))for j in r(i+1,len(a)+(i>0))]
l=sum([[a,n-a]for a in r(n)for p,x in s(`a`)for q,y in s(`n-a`)if(n-a)*x==a*y<p==q],[])

input harus disimpan dalam n, output akan disimpan dalam l.

Kasus uji:

n = 80:

[10, 70, 16, 64, 20, 60, 30, 50, 40, 40, 40, 40, 50, 30, 60, 20, 64, 16, 70, 10]

n = 147:

[49, 98, 98, 49]

n = 490:

[10, 480, 20, 470, 30, 460, 40, 450, 50, 440, 60, 430, 70, 420, 80, 410, 90, 400, 90, 400, 98, 392, 100, 390, 100, 390, 110, 380, 120, 370, 130, 360, 140, 350, 150, 340, 160, 330, 170, 320, 180, 310, 190, 300, 190, 300, 196, 294, 200, 290, 200, 290, 210, 280, 220, 270, 230, 260, 240, 250, 245, 245, 245, 245, 245, 245, 245, 245, 245, 245, 250, 240, 260, 230, 270, 220, 280, 210, 290, 200, 290, 200, 294, 196, 300, 190, 300, 190, 310, 180, 320, 170, 330, 160, 340, 150, 350, 140, 360, 130, 370, 120, 380, 110, 390, 100, 390, 100, 392, 98, 400, 90, 400, 90, 410, 80, 420, 70, 430, 60, 440, 50, 450, 40, 460, 30, 470, 20, 480, 10]

Jika duplikat dalam output dilarang, ia mendapat 10 karakter lebih lama:

r=range
s=lambda a:[(a[i:j],int(a[:i]+a[j:]))for i in r(len(a))for j in r(i+1,len(a)+(i>0))]
l=sum(map(list,{(a,n-a)for a in r(n)for p,x in s(`a`)for q,y in s(`n-a`)if(n-a)*x==a*y<p==q}),[])
Wrzlprmft
sumber
3

Haskell, 207 206 (209?) Karakter

import Data.List
x![]=[x];(w:x)!(y:z)|w==y=x!z;_!_=[]
a@(w:x)%b=a!b++[w:e|e<-x%b];a%b=a!b
h=show
f n=[(c,n-c)|c<-[1..n-1],i<-inits$h c,s<-init$tails i,s/=h c,a<-h c%s,b<-h(n-c)%s,read a*(n-c)==read('0':b)*c]

Jika tidak dapat mengembalikan rasio yang sama lebih dari sekali (400/400 = 40/40 = 4/4), gunakan f n=nub[...untuk memfilternya.

Mengembalikan daftar pasangan. Daftar pasangan dua elemen harganya sama. Daftar fraksi aktual akan membutuhkan impor Data.Ratioatau kualifikasi penuh Data.Ratio.%(yang juga bertabrakan dengan %fungsi yang didefinisikan di sini)

uji kasus (dengan nub):

Prelude Data.List> f 80
[(10,70),(16,64),(20,60),(30,50),(40,40),(50,30),(60,20),(64,16),(70,10)]
Prelude Data.List> f 147
[(49,98),(98,49)]
Prelude Data.List> f 500
[(10,490),(20,480),(30,470),(40,460),(50,450),(60,440),(70,430),(80,420),(90,410
),(100,400),(110,390),(120,380),(130,370),(140,360),(150,350),(160,340),(170,330
),(180,320),(190,310),(200,300),(210,290),(220,280),(230,270),(240,260),(250,250
),(260,240),(270,230),(280,220),(290,210),(300,200),(310,190),(320,180),(330,170
),(340,160),(350,150),(360,140),(370,130),(380,120),(390,110),(400,100),(410,90)
,(420,80),(430,70),(440,60),(450,50),(460,40),(470,30),(480,20),(490,10)]

ungolfed dan berkomentar :

import Data.List

-- haystack ! needle - the haystack with the needle removed, wrapped in a single-element list
--                       or an empty array if the haystack does not start with the needle

x ! [] = [x]                        -- case: empty needle = match with the full haystack left
(h:hs) ! (n:ns) | h == n = hs ! ns  -- case: needle and haystack match
_ ! _ = []                          -- case: no match

-- haystack % needle - the haystack with the needle removed 
--                       for all positions of the needle in the haystack

a@(h:hs) % b = a ! b ++ map (h:) (hs%b) -- either remove the needle here, or elsewhere
a % b = a                               -- empty haystack cannot be popped

-- f - the function we are interested in

f total = [ (num, total - num) 
          | num   <- [1 .. total-1],            -- for each numerator in range
            i     <- inits $ show num,          -- for each postfix of the numerator
            sub   <- init $ tails i,            -- for each prefix of the postfix except the last (empty) one
            sub /= show num,                    -- that isn't equal to the numerator
            reNum <- show num % sub,            -- remove the substring from the numerator
            reDiv <- show (total - num) % sub,  -- as well as from the denominator.

                                                -- the resulting ratios must be equal by value:
            (read reNum) ^ (total - num) == (read '0':reDiv) * num]
John Dvorak
sumber
dapatkah Anda mengubah ';' ke baris baru (dalam kode golf)? itu tidak mengubah jumlah byte dan itu membuat kode jauh lebih mudah dibaca
bangga haskeller
@proudhaskeller Itu disengaja; Saya suka memiliki lebih sedikit baris dalam kode golf. Selain itu, panjang garis lebih seimbang dengan cara ini. Apakah Anda pikir saya harus berubah?
John Dvorak
lakukan apa pun yang Anda inginkan, tetapi saya ingin agar baris-barisnya tersebar sehingga saya dapat membaca kode dengan lebih baik (daripada menggunakan kode yang tidak dikenali)
bangga haskeller
Apakah Anda setuju dengan versi saat ini? Saya tidak dapat membagi baris terakhir, sayangnya (kecuali pada spasi, yang akan membunuh keterbacaan)
John Dvorak
seperti yang saya katakan, lakukan apa pun yang Anda suka
haskeller bangga
1

Python 2 - 236

n=input()
r=range
f=float
l=len
for a in r(n):
 A=`a`;B=`n-a`
 for i in r(l(A)):
  for j in r(i+1,l(A)+1):
   for u in r(l(B)):
    C=A[:i]+A[j:];D=B[:u]+B[u+j-i:]
    if A[i:j]==B[u:u+j-i]and l(C)*l(D)and f(C)==f(A)/f(B)*f(D):print A,B
Falko
sumber
1

Python 3 - 302

Catatan: Karena kesulitan penguraian, tidak ada pecahan dengan angka 0 dalam (jadi tidak ada pecahan yang dihitung menggunakan metode yang benar).

n=int(input());s=str;r=range
print([[a,b]for a in r(1,n)for b in r(1,a)for i in r(1,n)if i!=a and i!=b and s(i)in s(a)and s(i)in s(b)and s(a).count(s(i))<len(s(a))and s(b).count(s(i))<len(s(b))and not'0'in s(a)and not'0'in s(b)and eval(s(a).replace(s(i),'')+'/'+s(b).replace(s(i),''))==a/b and a+b<=n])

Dengan n = 80:

[[64, 16]]

Dengan n = 147

[[64, 16], [65, 26], [95, 19], [98, 49]]

Dengan n = 500

[[64, 16], [65, 26], [95, 19], [98, 49], [136, 34], [192, 96], [194, 97], [195, 39], [196, 49], [196, 98], [231, 132], [238, 34], [238, 136], [242, 143], [253, 154], [264, 165], [268, 67], [275, 176], [286, 187], [291, 97], [291, 194], [294, 49], [294, 98], [294, 196], [295, 59], [297, 198], [298, 149], [325, 13], [341, 143], [345, 138], [392, 49], [392, 98], [395, 79]]
Peluruhan Beta
sumber
Untuk n=80cetakan ini [[64, 16], [65, 26]], tapi jelas 65 + 26 = 91 > 80.
Ingo Bürk
Ubah semua ifmenjadi satu besar ifdengan andmenghubungkan semua kondisi? Menghemat beberapa karakter, saya pikir.
Soham Chowdhury
@Soham Ya, benar, terima kasih!
Beta Decay
Bisakah Anda juga memasukkan testcases yang saya tambahkan? (Dan bisakah Anda melihat apakah Anda menemukan beberapa test case yang menarik yang harus saya tambahkan juga?)
flawr
2
Dimana 10/70, 20/60dan 30/50?
John Dvorak