Masalah

Buat fungsi yang dapat menentukan apakah string DNA sewenang-wenang adalah palindrom Watson-Crick. Fungsi ini akan mengambil string DNA dan menghasilkan nilai sebenarnya jika string tersebut adalah palindrom Watson-Crick dan nilai palsu jika tidak. (Benar dan Salah masing-masing dapat direpresentasikan sebagai 1 dan 0.)

String DNA dapat berada dalam semua huruf besar atau semua huruf kecil tergantung pada preferensi Anda.

Juga, string DNA tidak akan kosong.

Penjelasan

Sebuah string DNA adalah palindrom Watson-Crick ketika komplemen dari kebalikannya sama dengan dirinya sendiri.

Diberikan string DNA, pertama-tama membalikkannya, dan kemudian melengkapi setiap karakter sesuai dengan basis DNA (A ↔ T dan C ↔ G). Jika string asli sama dengan string pelengkap-terbalik, itu adalah palindrom Watson-Crick.

Untuk lebih lanjut, lihat pertanyaan ini . Ini adalah tantangan yang berbeda di mana Anda harus menemukan substring terpanjang dari string DNA di mana substring itu adalah palindrom Watson-Crick.

Tujuan

Ini adalah kode-golf dan kode terpendek menang.

Uji Kasus

Formatnya adalah <input> = <output>.

ATCGCGAT = true
AGT = false
GTGACGTCAC = true
GCAGTGA = false
GCGC = true
AACTGCGTTTAC = false
ACTG = false

05AB1E , 10 7 byte

Kode:

Â'š×‡Q

Penjelasan:

Untuk memeriksa apakah string adalah palindrom, kita hanya perlu memeriksa input dengan input, dengan atbertukar dan cgbertukar dan kemudian membalikkannya. Jadi itulah yang akan kita lakukan. Kami mendorong input dan input terbalik menggunakan Â(bifurcate). Sekarang sampai pada bagian yang sulit. 'š×adalah versi terkompresi untuk creating. Jika kami membalikkannya, Anda dapat melihat mengapa ada dalam kode:

CreATinG
|  ||  |
GniTAerC

Ini akan digunakan untuk transliterasi input yang dibalik. Transliterasi dilakukan dengan ‡. Setelah itu, kami hanya memeriksa apakah input dan input yang transliterasi benar Qdan mencetak nilai itu. Jadi begini tampilannya seperti untuk input actg:

          # ["actg", "gtca"]
 'š×       # ["actg", "gtca", "creating"]
    Â      # ["actg", "gtca", "creating", "gnitaerc"]
     ‡     # ["actg", "cagt"]
      Q    # [0]

Yang juga dapat dilihat dengan bendera debug ( Coba di sini ).

Menggunakan pengodean CP-1252 . Cobalah online! .

Jelly , 9 byte

O%8µ+U5ḍP

Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

O%8µ+U5ḍP  Main link. Argument: S (string)

O          Compute the code points of all characters.
 %8        Compute the residues of division by 8.
           This maps 'ACGT' to [1, 3, 7, 4].
   µ       Begin a new, monadic link. Argument: A (array of residues)
    +U     Add A and A reversed.
      5ḍ   Test the sums for divisibility by 5.
           Of the sums of all pairs of integers in [1, 3, 7, 4], only 1 + 4 = 5
           and 3 + 7 = 10 are divisible by 5, thus identifying the proper pairings.
        P  Take the product of the resulting Booleans.

Python 2, 56 45 44 byte

lambda s:s==s[::-1].translate("_T_GA__C"*32)

Perl, 27 byte

Termasuk +2 untuk -lp

Berikan masukan pada STDIN, cetak 1 atau tidak sama sekali:

dnapalin.pl <<< ATCGCGAT

dnapalin.pl:

#!/usr/bin/perl -lp
$_=y/ATCG/TAGC/r=~reverse

Ganti $_=dengan $_+=untuk mendapatkan 0alih-alih kosong untuk kasing palsu

Pyth - 10 byte

qQ_XQ"ACGT

Cobalah online di sini .

Ini akan menjadi 9 byte setelah perbaikan bug yang membuatnya tidak bersaing: Cobalah online di sini .

Retina , 34 33 byte

$
;$_
T`ACGT`Ro`;.+
+`(.);\1
;
^;

Cobalah online! (Sedikit dimodifikasi untuk menjalankan semua test case sekaligus.)

Penjelasan

$
;$_

Gandakan input dengan mencocokkan ujung string dan memasukkan ;diikuti oleh seluruh input.

T`ACGT`Ro`;.+

Cocokkan hanya bagian kedua input dengan ;.+dan lakukan penggantian pasangan dengan transliterasi. Adapun set target Ro: oreferensi set yang lain , yang odiganti dengan ACGT. Tetapi Rmembalikkan set ini, sehingga kedua set sebenarnya:

ACGT
TGCA

Jika input adalah palindrome DNA, kita sekarang akan memiliki input diikuti oleh kebalikannya (dipisahkan oleh ;)

+`(.);\1
;

Berulang-ulang ( +) menghapus sepasang karakter identik di sekitar ;. Ini akan berlanjut sampai hanya yang ;tersisa atau sampai dua karakter di sekitar ;tidak lagi identik, yang berarti bahwa string bukan kebalikan satu sama lain.

^;

Periksa apakah karakter pertama adalah ;dan cetak 0atau 1sesuai.

JavaScript (ES6), 59 byte

f=s=>!s||/^(A.*T|C.*G|G.*C|T.*A)$/.test(s)&f(s.slice(1,-1))

Yang terbaik yang bisa saya lakukan tanpa menggunakan Regexp adalah 62 byte:

f=s=>!s||parseInt(s[0]+s.slice(-1),33)%32%7<1&f(s.slice(1,-1))

Ruby, 35

Saya mencoba cara lain, tetapi cara yang jelas adalah yang terpendek:

->s{s.tr('ACGT','TGCA').reverse==s}

dalam program uji

f=->s{s.tr('ACGT','TGCA').reverse==s}

puts f['ATCGCGAT']
puts f['AGT']
puts f['GTGACGTCAC']
puts f['GCAGTGA']
puts f['GCGC']
puts f['AACTGCGTTTAC'] 

Haskell, 48 45 byte

(==)=<<reverse.map((cycle"TCG_A"!!).fromEnum)

Contoh penggunaan: (==)=<<reverse.map((cycle"_T_GA__C"!!).fromEnum) $ "ATCGCGAT"-> True.

Versi non-pointfree adalah

f x = reverse (map h x) == x           -- map h to x, reverse and compare to x
h c = cycle "TCG_A" !! fromEnum c      -- take the ascii-value of c and take the
                                       -- char at this position of string
                                       -- "TCG_ATCG_ATCG_ATCG_A..."

Sunting: @Mathias Dolidon menyimpan 3 byte. Terima kasih!

Retina, 52 byte

^G(.*)C$
$1
^A(.*)T$
$1
^T(.*)A$
$1
}`^C(.*)G$
$1
^$

Julia, 47 38 byte

s->((x=map(Int,s)%8)+reverse(x))%5⊆0

Ini adalah fungsi anonim yang menerima Chararray dan mengembalikan boolean. Untuk menyebutnya, tetapkan ke variabel.

Ini menggunakan algoritma Dennis, yang lebih pendek dari solusi naif. Kami mendapatkan sisa dari setiap titik kode dibagi dengan 8, menambahkan bahwa untuk itu sendiri dibalik, dapatkan sisanya dari pembagian dengan 5, dan memeriksa apakah semua adalah 0. Langkah terakhir dicapai menggunakan ⊆, versi infix issubset, yang melemparkan kedua argumen ke Setsebelum memeriksa. Ini berarti bahwa [0,0,0]dinyatakan sebagai himpunan bagian dari 0, sejak Set([0,0,0]) == Set(0). Ini lebih pendek dari cek eksplisit terhadap 0.

Cobalah online!

Disimpan 9 byte berkat Dennis!

Jolf, 15 Bytes

Cobalah!

=~A_iγ"AGCT"_γi

Penjelasan:

   _i            Reverse the input
 ~A_iγ"AGCT"_γ   DNA swap the reversed input
=~A_iγ"AGCT"_γi  Check if the new string is the same as the original input

Jolf, 16 byte

Coba di sini!

pe+i~Aiγ"GATC"_γ

Penjelasan

pe+i~Aiγ"GATC"_γ
    ~Aiγ"GATC"_γ  perform DNA transformation
  +i              i + (^)
pe                is a palindrome

Sebenarnya, 19 byte

O`8@%`M;RZ`5@Σ%Y`Mπ

Ini menggunakan algoritma Dennis .

Cobalah online!

Penjelasan:

O`8@%`M;RZ`5@Σ%Y`Mπ
O                    push an array containing the Unicode code points of the input
 `8@%`M              modulo each code point by 8
       ;RZ           zip with reverse
          `5@Σ%Y`M   test sum for divisibility by 5
                  π  product

Oracle SQL 11.2, 68 byte

SELECT DECODE(TRANSLATE(REVERSE(:1),'ATCG','TAGC'),:1,1,0)FROM DUAL; 

Julia 0,4, 22 byte

s->s$reverse(s)⊆""

String berisi karakter kontrol EOT (4) dan NAK (21). Input harus dalam bentuk array karakter.

Pendekatan ini XOR karakter input dengan karakter yang sesuai di input terbalik. Untuk pasangan yang valid, ini menghasilkan karakter EOT atau NAK. Pengujian untuk dimasukkan dalam string karakter tersebut menghasilkan Boolean yang diinginkan.

Cobalah online!

C, 71

r,e;f(char*s){for(r=0,e=strlen(s)+1;*s;s++)r|=*s*s[e-=2]%5^2;return!r;}

2 byte disimpan oleh Dennis. Tambahan 2 byte disimpan dengan mengadaptasi input huruf kecil: konstanta 37dan 21direvisi menjadi 5dan 2.

C, 75

i,j;f(char*s){for(i=j=0;s[i];i++)j|=s[i]*s[strlen(s)-i-1]%37!=21;return!j;}

Disimpan satu byte: kurung dihilangkan dengan mengambil produk dari dua kode ASCII mod 37. Pasangan yang valid mengevaluasi ke 21. Mengasumsikan input huruf besar.

C, 76

i,j;f(char*s){for(i=j=0;s[i];i++)j|=(s[i]+s[strlen(s)-i-1])%11!=6;return!j;}

Menggunakan fakta bahwa kode ASCII dari pasangan yang valid berjumlah 138 atau 149. Ketika diambil mod 11, ini adalah satu-satunya pasangan yang berjumlah 6. Asumsikan input huruf besar.

ungolfed dalam program tes

i,j;

f(char *s){
   for(i=j=0;s[i];i++)                  //initialize i and j to 0; iterate i through the string
     j|=(s[i]+s[strlen(s)-i-1])%11!=6;  //add characters at i from each end of string, take result mod 11. If not 6, set j to 1
return!j;}                              //return not j (true if mismatch NOT detected.)

main(){
  printf("%d\n", f("ATCGCGAT"));
  printf("%d\n", f("AGT"));
  printf("%d\n", f("GTGACGTCAC"));
  printf("%d\n", f("GCAGTGA"));
  printf("%d\n", f("GCGC"));
  printf("%d\n", f("AACTGCGTTTAC"));
} 

Faktor , 72 byte

Sayangnya regex tidak dapat membantu saya di sini.

[ dup reverse [ { { 67 71 } { 65 84 } { 71 67 } { 84 65 } } at ] map = ]

Terbalik, tabel pencarian, bandingkan dengan yang sama.

Bash + coreutils, 43 32 byte

[ `tr ATCG TAGC<<<$1|rev` = $1 ]

Tes:

for i in ATCGCGAT AGT GTGACGTCAC GCAGTGA GCGC AACTGCGTTTAC; do ./78410.sh $i && echo $i = true || echo $i = false; done
ATCGCGAT = true
AGT = false
GTGACGTCAC = true
GCAGTGA = false
GCGC = true
AACTGCGTTTAC = false

J - 21 byte

0=[:+/5|[:(+|.)8|3&u:

Berdasarkan metode Dennis

Pemakaian

   f =: 0=[:+/5|[:(+|.)8|3&u:
   f 'ATCGCGAT'
1
   f 'AGT'
0
   f 'GTGACGTCAC'
1
   f 'GCAGTGA'
0
   f 'GCGC'
1
   f 'AACTGCGTTTAC'
0
   f 'ACTG'
0

Penjelasan

0=[:+/5|[:(+|.)8|3&u:
                 3&u:    - Convert from char to int
               8|        - Residues from division by 8 for each
            |.           - Reverse the list
           +             - Add from the list and its reverse element-wise
        [:               - Cap, compose function
      5|                 - Residues from division by 5 for each
    +/                   - Fold right using addition to create a sum
  [:                     - Cap, compose function
0=                       - Test the sum for equality to zero

Labirin , 42 byte

_8
,%
;
"}{{+_5
"=    %_!
 = """{
 ;"{" )!

Berakhir dengan kesalahan pembagian-oleh-nol (pesan kesalahan pada STDERR).

Cobalah online!

Tata letaknya terasa sangat tidak efisien tapi saya tidak melihat cara untuk golf sekarang.

Penjelasan

Solusi ini didasarkan pada trik aritmatika Dennis: ambil semua kode karakter modulo 8, tambahkan pasangan dari kedua ujungnya dan pastikan itu habis dibagi 5.

Primer labirin:

• Labyrinth memiliki dua tumpukan bilangan bulat presisi-arbitrary, main dan aux (iliary), yang awalnya diisi dengan jumlah nol tak terbatas (implisit).
• Kode sumbernya menyerupai sebuah labirin, tempat penunjuk instruksi (IP) mengikuti koridor ketika bisa (bahkan di sekitar sudut). Kode dimulai pada karakter valid pertama dalam urutan membaca, yaitu di sudut kiri atas dalam kasus ini. Ketika IP datang ke segala bentuk persimpangan (yaitu beberapa sel yang berdekatan selain dari yang berasal dari), ia akan memilih arah berdasarkan bagian atas tumpukan utama. Aturan dasarnya adalah: belok kiri saat negatif, teruskan ke depan ketika nol, belok kanan saat positif. Dan ketika salah satu dari ini tidak mungkin karena ada dinding, maka IP akan mengambil arah yang berlawanan. IP juga berbalik ketika mengenai jalan buntu.
• Digit diproses dengan mengalikan bagian atas tumpukan utama dengan 10 dan kemudian menambahkan digit.

Kode dimulai dengan 2x2 kecil, searah jarum jam, yang membaca semua input modulo 8:

_   Push a 0.
8   Turn into 8.
%   Modulo. The last three commands do nothing on the first iteration
    and will take the last character code modulo 8 on further iterations.
,   Read a character from STDIN or -1 at EOF. At EOF we will leave loop.

Sekarang ;buang -1. Kami memasukkan loop searah jarum jam yang menggerakkan bagian atas tumpukan utama (yaitu karakter terakhir) ke bawah:

"   No-op, does nothing.
}   Move top of the stack over to aux. If it was at the bottom of the stack
    this will expose a zero underneath and we leave the loop.
=   Swap top of main with top of aux. The effect of the last two commands
    together is to move the second-to-top stack element from main to aux.
"   No-op.

Sekarang ada sedikit linier pendek:

{{  Pull two characters from aux to main, i.e. the first and last (remaining)
    characters of the input (mod 8).
+   Add them.
_5  Push 5.
%   Modulo.

IP sekarang berada di persimpangan yang bertindak sebagai cabang untuk menguji kemampuan dibagi dengan 5. Jika hasil dari modulo adalah nol, kita tahu bahwa input bukan palindrom Watson-Crick dan kami berbelok ke timur:

_   Push 0.
!   Print it. The IP hits a dead end and turns around.
_   Push 0.
%   Try to take modulo, but division by zero fails and the program terminates.

Kalau tidak, kita harus terus memeriksa sisa input, sehingga IP terus ke selatan. The {tarikan atas bawah masukan yang tersisa. Jika kami telah kehabisan input, maka ini akan menjadi 0(dari bawah aux ), dan IP terus bergerak ke selatan:

)   Increment 0 to 1.
!   Print it. The IP hits a dead end and turns around.
)   Increment 0 to 1.
{   Pull a zero over from aux, IP keeps moving north.
%   Try to take modulo, but division by zero fails and the program terminates.

Jika tidak, ada lebih banyak karakter dalam string yang akan diperiksa. IP berubah ke barat dan bergerak ke loop 2x2 (searah jarum jam) berikutnya yang sebagian besar terdiri dari no-ops:

"   No-op.
"   No-op.
{   Pull one value over from aux. If it's the bottom of aux, this will be
    zero and the IP will leave the loop eastward.
"   No-op.

Setelah loop ini, kami mendapat input pada tumpukan utama lagi, kecuali untuk karakter pertama dan terakhir dan dengan nol di atas. The ;membuang yang 0kemudian =swap puncak tumpukan, tapi ini hanya untuk membatalkan pertama =dalam lingkaran, karena kita sekarang sedang memasuki loop di lokasi yang berbeda. Bilas dan ulangi.

sed, 67 61 byte

G;H;:1;s/\(.\)\(.*\n\)/\2\1/;t1;y/ACGT/TGCA/;G;s/^\(.*\)\1$/1/;t;c0

(67 byte)

Uji

for line in ATCGCGAT AGT GTGACGTCAC GCAGTGA GCGC AACTGCGTTTAC ACTG
do echo -n "$line "
    sed 'G;H;:1;s/\(.\)\(.*\n\)/\2\1/;t1;y/ACGT/TGCA/;G;s/^\(.*\)\1$/1/;t;c0' <<<"$line"
done

Keluaran

ATCGCGAT 1
AGT 0
GTGACGTCAC 1
GCAGTGA 0
GCGC 1
AACTGCGTTTAC 0
ACTG 0

Dengan menggunakan ekspresi reguler yang diperluas, jumlah byte dapat dikurangi menjadi 61.

sed -r 'G;H;:1;s/(.)(.*\n)/\2\1/;t1;y/ACGT/TGCA/;G;s/^(.*)\1$/1/;t;c0'

C #, 65 byte

bool F(string s)=>s.SequenceEqual(s.Reverse().Select(x=>"GACT"[("GACT".IndexOf(x)+2)%4]));

.NET memiliki beberapa nama metode kerangka kerja yang cukup panjang di waktu, yang tidak selalu membuat kerangka golf kode terbaik. Dalam hal ini, nama metode kerangka terdiri dari 33 karakter dari 90. :)

Berdasarkan trik modulus dari tempat lain di utas:

bool F(string s)=>s.Zip(s.Reverse(),(a,b)=>a%8+b%8).All(x=>x%5==0);

Sekarang berbobot 67 karakter dimana 13 adalah nama metode.

Optimalisasi kecil lainnya untuk mengurangi 2 karakter:

bool F(string s)=>s.Zip(s.Reverse(),(a,b)=>(a%8+b%8)%5).Sum()<1;

Jadi, 65 di antaranya 13 adalah nama kerangka kerja.

Sunting: Menghilangkan beberapa "boilerplate" terbatas dari solusi dan menambahkan beberapa kondisi membuat kita memiliki ekspresi

s.Zip(s.Reverse(),(a,b)=>(a%8+b%8)%5).Sum()

Yang memberi 0 jika dan hanya jika string s adalah jawaban yang valid. Seperti yang ditunjukkan oleh kucing, "bool F (string s) =>" sebenarnya dapat diganti dengan "s =>" jika dinyatakan jelas dalam kode bahwa ekspresi adalah a Func<string,bool>, yaitu. memetakan string ke boolean.

REXX 37

s='ATCGCGAT';say s=translate(reverse(s),'ATCG','TAGC')

R, 101 byte

g=function(x){y=unlist(strsplit(x,""));all(sapply(rev(y),switch,"C"="G","G"="C","A"="T","T"="A")==y)}

Uji Kasus

g("ATCGCGAT")
[1] TRUE
g("AGT")
[1] FALSE
g("GTGACGTCAC")
[1] TRUE
g("GCAGTGA")
[1] FALSE
g("GCGC")
[1] TRUE
g("AACTGCGTTTAC")
[1] FALSE
g("ACTG")
[1] FALSE

Oktaf, 52 byte

f=@(s) prod(mod((i=mod(toascii(s),8))+flip(i),5)==0)

Mengikuti trik Denis ... ambil nilai ASCII mod 8, balik dan tambahkan bersama; jika setiap jumlah adalah kelipatan dari lima, Anda adalah emas.

Clojure / ClojureScript, 49 karakter

#(=(list* %)(map(zipmap"ATCG""TAGC")(reverse %)))

Bekerja pada string. Jika persyaratan dilonggarkan untuk memungkinkan daftar, saya bisa melepas (list* )dan menyimpan 7 karakter.

R, 70 byte

f=function(x)all(chartr("GCTA","CGAT",y<-strsplit(x,"")[[1]])==rev(y))

Pemakaian:

> f=function(x)all(chartr("GCTA","CGAT",y<-strsplit(x,"")[[1]])==rev(y))
> f("GTGACGTCAC")
[1] TRUE
> f("AACTGCGTTTAC")
[1] FALSE
> f("AGT")
[1] FALSE
> f("ATCGCGAT")
[1] TRUE

C, 71 byte

Memerlukan kode ASCII untuk karakter yang relevan, tetapi menerima input huruf besar, huruf kecil atau campuran.

f(char*s){char*p=s+strlen(s),b=0;for(;*s;b&=6)b|=*--p^*s++^4;return!b;}

Kode ini mempertahankan dua petunjuk, sdan p, melintasi string ke arah yang berlawanan. Pada setiap langkah, kami membandingkan karakter yang sesuai, menetapkan btrue jika mereka tidak cocok. Pencocokan didasarkan pada XOR dari nilai karakter:

'A' ^ 'T' = 10101
'C' ^ 'G' = 00100

'C' ^ 'T' = 10111
'G' ^ 'A' = 00110
'A' ^ 'C' = 00010
'T' ^ 'G' = 10011
 x  ^  x  = 00000

Kita dapat melihat pada tabel di atas bahwa kita ingin mencatat keberhasilan xx10xdan kegagalan untuk hal lain, jadi kita XOR dengan 00100(empat) dan menyamarkan dengan 00110(enam) untuk mendapatkan nol untuk ATatau CGtidak nol sebaliknya. Akhirnya, kita mengembalikan true jika semua pasangan mengumpulkan hasil nol b, false jika tidak.

Program uji:

#include <stdio.h>
int main(int argc, char **argv)
{
    while (*++argv)
        printf("%s = %s\n", *argv, f(*argv)?"true":"false");
}

𝔼𝕊𝕄𝕚𝕟, 13 karakter / 17 byte

⟮ïĪ`ACGT”⟯ᴙ≔Ⅰ

Try it here (Firefox only).

Penjelasan

Input transliterasi dari ACGTke TGCAdan periksa apakah string yang dihasilkan adalah palindrom.