-5
\$\begingroup\$

Output the variant NC_045512 of SARS-CoV-2. The genome's raw form is available here.

  • Lowercase and uppercase are both acceptable
  • You must output with the letters A, C, T, and G.
  • An arbitrary number of newlines are allowed any place in the output, it does not matter.
  • Standard PPCG loopholes are in force.
  • Special Rule: To make it easier to golf, you may define an X-bit encoding for a particular contiguous section of your program. If you use all ASCII charactters in one part of your program, each character costs only 7 bits. The Python program a="11001100" could count for only 5 bytes, because the single section "11001100" counts for just one byte.

This is , so the shortest answer in bytes wins.

For reference, 7-Zip manages (with PPMd as the algorithm) to squeeze the genome into 8,149 bytes, so your program should aim to be shorter than that.

\$\endgroup\$
  • 2
    \$\begingroup\$ Are you sure this was actually sniped, as opposed to 2 people coming up with the same idea independently of each other? \$\endgroup\$ – pppery Jun 10 at 1:30
  • 4
    \$\begingroup\$ @ppery It may have been developed independently, I have no idea. But a search would have shown my Sandbox entry. And this challenge wasn't posted in the Sandbox first, which I did. Once you post in the Sandbox, you should have dibs on the challenge (just like any duplicate). If we don't do that, nobody will post in the Sandbox first, because they'll be wary of being undercut. \$\endgroup\$ – Mitchell Spector Jun 10 at 1:32
  • 4
    \$\begingroup\$ I’m voting to close this question because this is a near-duplicate of a recent post in the Sandbox, and posting in the Sandbox first is the recommended procedure. \$\endgroup\$ – Mitchell Spector Jun 10 at 1:35
  • 3
    \$\begingroup\$ I see no reason why users should be expected to search the sandbox for any possible duplicates of a question they are about to ask. \$\endgroup\$ – pppery Jun 10 at 1:48
  • 2
    \$\begingroup\$ With the question over priority in the background, I don't want to lose sight of another issue, which is the "special rule" for scoring on this challenge. It's not at all clear how this would be implemented -- is the answerer supposed to check every partition of the program into sections to see what the reduced score would be? I think a score for any challenge should be easily determinable in an automated manner. \$\endgroup\$ – Mitchell Spector Jun 10 at 2:22
2
\$\begingroup\$

Python 2, 51 bytes

s=len('...')
t=''
while s:t='tacg'[s%4]+t;s/=4
print t

Try it online!

Substitute the '...' on the first line with the unary encoding of the genome in base 4, which can be produced using the following program:

s=raw_input()
s=['tacg'.index(c) for c in s]
print reduce(lambda x,y: x*4+y,s)

Try it online!

The unary encoding part is supposed to count as 0 bytes due to the special rule. I'm posting this to show how broken that rule is.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The "special rule" was reworded. This may change the score of this answer. \$\endgroup\$ – pppery Jun 10 at 15:13
1
\$\begingroup\$

Ruby -p, 11,799 bytes

NOTE: I've posted an almost identical answer to an almost identical question here. There is dispute over which question has priority. I've posted answers to both questions simply to claim my own priority as an answerer.

Decoder (365 bytes):

gsub(/./){|i|Hash[[*32..51,*58..96,112,113,*115..121,*123..126].map(&:chr).zip(%w[45 46 47 49 4a 4b 4f 4j 54 56 57 58 5a 5b 5c 5f 5g 5j 64 65 67 68 69 6b 6c 6f 74 75 76 78 79 7a 7c 7e 85 86 87 89 8a 8b 8f 94 96 97 98 9b a4 a5 a7 a8 ab b4 b5 b6 b8 b9 ba bc c5 c6 c7 cb d7 e7 f4 f5 f6 f8 g6 g7 j4 j6])][i]||i};$_=$_.chars.map{|i|'ACGT'[(j=i.to_i 36)%4].*j/4}*''+?A*33

Input (11,434 bytes):

%cav@Sd4VHc9KHw2AA[@2ABZAF)HfgABBE*:(*,*3"3Y:3 A 3!@C\C*M BA=2(T()!C*)A@AZB(UB- af)D:=3!P"(A!((A@af)Du:2PcaC2E!!S:taf+)!g5  :R*(?<B}(X)) :3A: :Ufa! D:TTV-"(2U :+(A_2E(-:UY:!I[ka)~Q+-;(6d@BB$$0Z".)ZTB*)HB(Q(EA"="X23E@3!HA;U%(: V)@:V22(-V:S:t(BG)q#!E-#3LZZZ:IHVJca!*Va9"!Y,)P"*pA&2-$) 23^(*2DYBI'+6g*W(*`"!(:V=4d:;*(B)B!-HTi5"  A3@BA2C+-*:adB"U@t-2:3%p#Z@3 :3EF3Z"3 xD;+*T/%2(*I4iB@@*3BPBH"23">[-V  W)ZB{!*";[(2(9j>_^.>x #ZJi8BDcj:&dbsOCAI @ZK8e[{k6-2E/"u!M)"*:*"O=3:(9cBJ3Kq:<wHAA";::2A%:V>-(E(25e)'=pO-3;~E(*2;x F;V< @-:X YhgB*==gf%:O3":(+Z!I@TQ23"!A[PJ#"J;AE-6gOZZ:8eEA3 @[9fTUBBBZAYB^[OC+::<@be] :3@33C(@X:K" $B[^!L];V-J2+S->@*9k2>:+(AJ%=V2/`\BI!")OYja(An5B-O+:3~E`BBcafa%"p(Z`s=;DBECjc= ga{*oaBQW@^BH!q+@*2:Q/"3&3"(2UB*)B[@)"+j57d3 A[`B*0ZBB)B}(;a93@C+@*!"Ww !@Z B! A%2B*"2BZ "*2fa* C+A@=:Ja9@(Y(VV==(=2-)(:UC*H"/U BvBk5Acd:S2^-;2;?LLB@2?-!! Xec[_vAAKBB-:>[AVT.[A#BB.ac\T2:=(2(Zy3[FFna/::3B A@A%%VT3F-pS;vV>(xA 3 Ace%: !pBB_D!!I`EQ A"<A7g6h{s"--!4e!` bd !IB\(2W=:-6g*V2v+OY;+Q @:;3B[I*O^^@(O?:%He5YB[*)q.2((6g: BBdb3#C@B"VH`J#Z  Aca,B(R.X jaB"2(*:2@;:3LY+2::;@A ~H[">T["p@-J2;:3ABQ" ![HAV !IFB!Z<BB[E(2B*:(7k/3K!@ABM Y(O*e5%2v2B!E!@E* " @-&2B!AEB!fc^-((@B@[Zw@tO2B$";;;V2[BIII!x!OAHAJ"2:"V BI"2YRVc9faNV< ZB*3AZKBII!+;;2^Y2B"2@:+.*=V++2,(:2T+A! H@*%.+[[$ZKAM!!"W- #![Z! @[IBJ!}:X&g5Y*2+B@@(bkB(2([EII*ka7gR(:X=J3!RBvS`"TTV=3$!SqL* C+BOB+=;AB"2Y(@3@*JTO-pGE@=:6jI,  J-3F(*:-(B[Aadq=HcaBI %+--I!B-"6gj8A!()IZ@-3#%%"(3E@naB*2t" %/I!xB@2@*=)(.BA@-!*:/27kAA@B `[wI5nacBI!B{+=;02A3B!%Qp$I\<&"HBpFS(=;(26g+2B"I|.3[B[IIY++**W>*I]A !g5[Y/"%2(\E+AZ"O2ZBO*-=!B %2(A w_>2B*O@@@:u2B[ZI4eBj8*3BEY@Q 7kUEE(* Bq3@3>3x!{BR(2+Y@CO-4du(efqX  B@2TUp !B-k6B7g:<}(Z@OA@YAACB!I+>Z^HBw^N32>B-3 "3!I` 3sJ<BABBE`F<"!wH@@(3:q"8e@bg@+2u:X2YEB*!' }(O:g5HB@3:(-"+((-H2AFB`A[Y+BO-U@BC((E-cfW;3B*,@@B!"**.:<!* !wBwZ#B"3BY(3:"JX"- ZZZ7g(Q;;(}[c9"*(-3E]@F2^D@ZE J*  H@V"!N-I!$B"{B@@Y(*!CD@O(]#@2EBIYA#x J-I  Zwx!!IB$ @\V? H!@2+(\QO()+=:T(BAJ2(@E H!faDHYfa"T3B"= 7g7gQ(CZ ";Vg5'"6j#CB"2(** :=2U~!@*#  HB"Q!j5G@V ":(3%q((*k6Eq4d I\Ey-*%qe5!"HHBYA[O*3%=H DHq!![IyD#B** I"3YY(238e*V;3B*H~B(-"-!Q BCC2(:$B!YV2BY2>+B!Y-?+(BRv2Z[02:-;)EBB7g-:T+(3! 8d\u:!I*=": "e5  wYBHNIcaBZ!"#[@)BEF+3@0@A@: H$!A#~YB":(3##B*(:";-I(E@(v-:3@:2:  ECYO::V(*"`""HZF>/:%3"! V3v- pDA!J caD@Y,"6j* pg5!Y(++O7gO= YF^"V=?: !s2tI^ M%"Ip M-&((23KM2A[@9cRO@D`3I-)"8jIx@BB"J".x*2B&c9!\*X"Ic9B-+223_= 4nt2-qV2BEE*%2YF(*  4dAj8>T3F[Y(FQ%?U"=HJ3HCF< :"c9q#EB@@)[Afa!(0O=>(As)x": BIA!$ 334eJTCA[Q3;2A7gO:**;;:!E|Q#" !p =-2::J:6g*#;=:$! %" _O3qJ!fkY(;2Xa9  !"*JUB-":! M*!AY*%Ic9CBM"*!!@Yaf6gdb3@*(Ev3B*=J!B7dbe" @@3CYB*I9j-Hp[Y: H@*H"!Y(,BfcPBx@*M""<Ywv/%3@+[B@1 @;: s*!Mp(A@BP @*"!.;@*=I!BAVcj:*!$-(yYxIA#Cn5F*2F@YCfan4*%IBxQ$ZyA@*+P*3vV6jJ:*N$(BS- B@*X !!L*&;** CBA @[+Q B@*X*"#[@:?:-!Ev2Zv2(Q"S/!`@@.YOw"1qe4y*3ja-![(2:anU""%1(*$n5@B@-T^*3J(B+[n5!*'3!@(}Y:M-UYBE\C\A[@.Eh6&(3@EY;B@(AZx(A'%":"ag=":3"=:! X:M(AH[@B":= `:J!!++2:)J: H@[\EBY;V9j":*"3CE$FU~.*  MW[B\[B" %*:3E@: &%!B";=3222-:(* !fg2RFD@*2O:-- ")["!BY(:;;E]"OAv/2F3EA{ YBp %****(~\-! KB!!*JH FX([Q%J="!n6"Vq0BBIJ(AB0A!)ABv* !A!-"::+Q" BY*!"(U%!BAB"=V2@:3W=3!bgBx"3Y)\@)j5"+1H:#Jak*0(*![+*3!I*;-3pJ::S! J:-"* }w!(3AU8ex[%(2B@>*p"==;BA_[A "+AB "!IY*U2@=:JH@@B*(Q"Hp[g5"2(h6B#^B-:%2*:!B))A"%J33$@3k6A H%3x""W)_2w":([ABHH@)g5q :!B*37k;C-#j8=2(BB+* @2+==J=:HHp"!(-8eE7g[\C^[I(=MpY(-:=9n=3B*'*&JH#BZ":(BAF(@*21+:>A"$" L*%2EEBA A:2(@3"* !" [~*H`"3B'2((Ev<!)EE@=" CB p-6d%2[*3!A"HI!IG~A:<ExQU 2@Y)(+*JV25n3&-#@26n!B(=VH"*=  #"0-"!!@(*2/3H"(3[Bja*3BJ: 8np"3ZEC<!@O@[YB"#J: @;X*=3YBpv)t2(()YBB*(E"UA@YZNQH#@S;X*=!!EC+12ZB!@*:$(,(-:>2A!I*V?::"* @:V!"u \+B%% !"/#$!j5BEB@2B*:cf Y*J"? # CZK@^B/T(@A!(A@@:!*VV%:!*")@:H"<[Q @}B$v;23jaBJ !A":![9fJ v*%S":(Z B@**?H#!v*(ZYQV?%*=& [@-2(}AY*J2Bwr43 "%(:TEYBZ #v:#wE"HM3Y@A&:&O.3&*%X/!CYQp! ::!AyEBf9v: ~II*33BB(9n=qpq:"*p[)@:2BB*%#AY)+@C@2@-!*/"JI@+:'!E!+E" H@3@(2;3B-=:(AA3ca**+B Z!C*(X*2BZvROO.Q*"(Q(3B~(2:aj!k7U%d4AEF=2eb:"V IC-:V H@(-HV/U["2)@? BDI ":2AB(Q*;2(B-8dCYBI& A%)C:*J(Cw^@(UECBZHA4eY^ %*"3gb:: \3\X2@(<JQI #C:"IxZ3%+OT(25n(:=!-= JX(OAEBvRBB*"2adN(*%8eZ%SJX(BE@:=ajH"!%"2*::*5n= "3#""WYR*T=(B*U ! Y;VH}E#~[ $.(3 I(3E@,  H@Y(=J6j!-X: 3B*="qT2(Vaf*+A2vO+*-J2/K[E*";: M";Q*H I#"=2(@*$#AwB*.*W[P}2@BBB-(bg;Y*3|V";E :#"%u!B/%!I";v(9j2B[Y2+B*(V= f9pB(:6g;+A8e@((O*X= A 8j2-(1!}:O2: AJV/=5z:"6gB9n#~*"u%%3@BAB13J2BxA`"I(B(wABxn6YS*-< B@3Yj8@EA@@BQ3@=u2B)@YB "XT@E[" @?:*ajI*{ BBYB@B(A!*:!BY*JS"2(3IHBB@B"2EB*$!!BE  YBJ:-2(*)vF?%"VJ3v2AIOf9":e5AYCAABY-*H@*(V:!Y+*:(BnaO2V%6n"::=2:%6d@j5Z"HEC@(-(::"J3@?%?-$*4n: [Y/a9A~v*+P* v2*2*-V?"2Y-!w@((T?!""";Z 4e @*d4d8;@3"!"<Z`AH%s=u=VUc9[@Ap@< B@(:*|:(2BF:3 "(:!AY**(6j3HHA!!@;A"(AF[G*+BBD!Y(+B %*-!*p" @*;<xo7af(* wB~/OB(u3B@2(F+3xBIq3E H4e+S I*"!Q(2?!bd]"(@B(3~* B*+;3YB!(UB[*JV2ZBI[Zbk=;;:/;BE*q*;x#:2B(<"3H:I^{"UB"+3@B4dq:"`$*!"*2T+2e5{Y*!B*"3! J3j5 @B-!p^"J2B(*++(YAHJ3I!"X:=db;(C@Q- H!(<`CE[A"#! @C((@7k@)BB"V H& YB(A!([GqR(X:!"3!"!7g[ZHY:>Y:"T+Z#Cv3"a9AY[C(3ye9M*3BAs !JJ23Y:Q=3 @) !":-:3B9a@*  `B-3 B"2+B)Y3Y* H Hce$@af: [(*="P& $&>G*!%tI!B"W*V @A@@(;*WOS:$xY(2((QcaDF:;:&" v_T_+Qq!$@E@-V!v3BO(: :* I*VJ3H!IBQ<M+*:%"/*:3~*:!"3B*p- p%"*!*!7m KJ(*M:=I"=::    E@*V(UJH!Y(9aIR@E"+;DfaEB(A:=:*: BP[O(@2A"9cDFT~B bgVI@B@.@Q H[B*J2t:ej  bk((:*:#:*3V":acX"UB@=:2AHD3;d4B-(:(3B"3 J)nc5ex,BC:3!d6AY(PB,((U @: B":)@@(e5~ "* J2F:!*aj3F]7k*M=:)-R6gT)I"2+y[%- x@=I!   wAC*#H";>+vCv-L%:O3B[*`"2-/Iv;@2,B "V# """()AH:- F@(+E(2Q)A@B/L(~";VM:2((bg>@-:((@+[[B"2B%&+7kT*V"2~@6gd42@@Y))@@)R-$BH:: <I/=k5!@+ZBB"<"3>B*V%=V: B %!"J+2AAJVHE@B&,B&(@.O)OV!E!]B[@2ZYYZ%=J<@@\S2Oe5y*3!!A "=2(*2-HpS %IG&=|"2-(,I!$bg*/2PYjc@be"(2(@Odc[B\*?TB !"3%*3%:3`yB}ZA@(:=d4Q Ija# @:26k@x["V=Ox@?+*T@O-(223@V=: "J(TBF- "!**! Y6jLM [B@B*3B4dB*"3 3B-*VJ*% @2F)(* :3j5!@3B(- C+B[1.*:.daCj8.2-*"2/3BBACef/LLIZB[Mg5 ZZx*(TECB*3@A!)%"2* @A="J*#HJ::2@A! H@*&:![I[["I@/2[Y)"VUB@\B*KIA")AHK@2.A!*ajOyF7iCU@2/%"2ZJ2="2TAI"3 j53"" g5:J:(7d@*"HAq;A\:"<%!B.;@23A3#:!*V:**"*:!@*"2R@2(?(Akb%>AJ!PO*!$!* B@:MW+3s*"VXU H"=k5Bv@:2B@6gt(S"ebe4YDFBB"!!OBQH"3Y;YEQ(-=-3A3`" H:=:!-:((Pw@@2Y3CB!BB*+:%2:>EA"::UX(*""=c9$EKA"(T2BO+*3YB*J!Bn8(xAI*:(,RB\B(1"* B"VHgb<2C:":P+v+((2/"2::**"!q!!"=2((2/:;B!})(@x)F(wAJ2B" AAB 2B*=::?+@3 YB(AALA@:U@3"pHy:(=/%"0+Bn4BABI0B^ B! B#Y*ca#A";~**+(@+B*!_(u2B%"::#]Yd42D"+;D@i9UB~@2B"")7k(2E@(-"2[HX)BAv3@@2B-4d Y*`"QJ(T:"3B":/(x@- J "Ip* "2B!\(T((BY2(B@ZBYB- CB"H ZL@beKB!}B$*":  #3" !AY(UBbi-:=/3M((2-(\2BEB-3" :!#%-"=:q3BY)#":(@AH"((FY:-:*=JP@Bx+B*OX:2BA !":2*+/ YTV"23@Y[FA "c94d%!j9%::3CE Inav@7k@(BB^@32CBY*2/J3M3H":2*T.B*V2Y(}3C(Q: Bp AI5n3!(>)*.3@*2T2(fc*:-"V%3@*: :;:3BAB !!M "/(GI^FQ!## \Ps":/ EYA::H7k(:p@.@T2: #xkaB @EB"3B[vP$@++- sq=V2Y~B*2(A " !CBO\:3#@(*!BO+23 @BY;Y*UY@d8(*+@AA!"26j*!+B[.YAga^@B0:%*  D4e##E@*VI!A'3@^Q!*** @db*3A3"!B@@(3[**(BP*=2B(*":2;U%|&<@@2FB@:!M"#B()B*)B@2:6j2FZpBM+(Y;(:":1: BFB([Q22) !(2@@=:/2Bcf+EO.YB&2:=:+BO2Y)B*I(*":: %U2t3AM#B(O)(([*HCe5  @;O;@wM(:::! YBg5@@VO2(B]AW-:,)[DB*>[[  BB!B/af"2CC3_3 "p q(3AJ3fgB}Cu="()(B"?(AB+\(a9 q$)EC2;]Y()Ct3^!{*:/&(S"M((;B*:!Q.2je @R*.*=2Z"((e5A!J"2*":(@Z Ac9 B`!*(*-:J:`!&J=3@YO23{@U" x(CBAB"!!#vB I[+v+:->] :$J:UHv+3B|:H$ Afc2[@:LCA GY(D@((U#@((Q(:=2(*s0*;af":=2(@QU"#CT(B#@@;2*(AA@B"ej|;YAI\EYtH"?"(d6)II*"I ": :3"T^-)":)4iBA"3@*!!I*=V#N#v(3@an* $B\Q![*:#@(X"=2@(QJJ !4nO2=!B*c9#<E!"+fc(Q(@O-": ca ]^J:!B)@F2[@.B\:2((-k7***2(2:)@xAYG((E/2=2(A@BI@~B|$#B!)(Q=:*":2@2)BO(B1O*3Z!  YBQ=U"(Z@^&2Y)A@CD?"2["=++7i}(VK@.3K"2AB@[AID"VJ3 ":!*![B"3J(B @V:*!*:O)!B/=I)B[ E @[J"Q"MV2BHBI%J3U[@>X+((E[_3B(YY3! sd4=-() %V8dF3@\:::#AI*2B@;EIZ@B"3 !S:!B p-"|!IM%*%-"<  %*2.Z !"V:"<@jaM3J:)"!""Q3C]%?:!&2(*!!B*"*K\-<E[B"VU!x@BFF(B(]  #!127g:3~\fg+YOn5@Y**2(:OBB!AA"ag+:!BA!""!%":# F:*3@)B@C()[+vVV3BAB@2(A"3CB!@(2[@AA2B-"H"2B"*(3E/!-:ef `N2@-"KAEH }+2-(2?!|:Uj8B[FCe4(/2E H4eBI@O?*"(\C(*?  {["V=2B@;[x|g5H%#B\B@3&23fe*I)+(_O:#!$B| AJNu:T([*3C@*:2AG @022B*O3 """* @^BxZ@B B "!R>R*>)&:3# A BAr6"V!!["V+:! Yv>Bd6CEBZYY(;V!B_af K"*:$7d`I*!A\E!A %MT;<:k5 !ZM%"Ip["V=:R+YQ>- v*(2:!cf INcd$!Aqac[&-!M!*"TBM([HV"s!L*"<Z;(@A?"T2}:(@:(=$Ev(A@*2^ @3F)j8WA#~M!I'%Q"T(: !bk*&(C(2B).(X(AC::::=*=%2vY-2B'=>C7g7dI&"*:!wCX:.:2*%2*" !cf(vB/V:p"a9":!`'4dgb J*!AI)E+9eB[*"<CAv0B.;B*%!{BB#Zgb"V2@:3H%#FU"J2BJ:)0@@*+*::+@fc((\(Y3B@t"J"22=" 'V3EZB"ca![(OV !*6jI !E[Q u 3B-:)%(2A\B xAAB"3!%+/2^B%:3HB@(@(3CFG"*(YY:2@B@)4dC2*k7= {|2**p4er5 Y(xGv@+03@3A^$]:U@F2C(;(Z^J3B"/"I*(G  Z3"VT(<xY*J:;B)A"(ABI(n8^":M"-Uc9 3;.@2EYBA"3"3s "'TW@.DM(=:-Q%/&2(B!Ffh_\i7 B*=":/{LAq+B""2}AAZY:ca@2-"M!!g5H!![Yw@:2BZ[\+*`;+Bxn5[}[O*!AA@:(::=J- K!HAM4lB(@(*M/(()EBvYt2.6j(2DA!}(ZHA$ [ZY9f1RBY-XOB*" ":**e4RE@*I$x"8dBD@OyB"V?'3] B!IAC(CC2UE4nV @/!%)I4d!7d@-%=JH3@*J==%pABBN+~CB"OneBvYO5k+0=TEpB!Z!!vZ@:3;C[(1;@BAAA!9j-"TS;ag(uN5kAYe8xBy;@["X'|"%*I(()Q%N!B)B"*t(en,/!K%V!&<J$@\(A @af./ [/ "!IYx DEB%--(XT(3EB*3!-%":eb"-+Q$ j5@bg@CB|WOY(2B*:! BB(-2t**(>.:: =>DZ B@6kWA@A`ZC/!!DKH!J*%=!&QJ% `[BdjV;6nH<#!&3"*?"3^H$I!J(3HBB[*2YZBD@@C]3"(j9 j8:="T::*Q F_B"**3v*J:*"3!%(xCY2V2BIA! q)*Oe5`Ep%3B%"M"s#!"2}(UB)Y@3^M*HJ-2ZCXVVM"M#B@@2[vW:*J*.9j2222@wHBq*"(a9V!((S:JV=;ajM= f9v+A""afRd4*JV=X#K" !!@:!@/1;-* "3#!+*?:TQk6A@*NXk5q::+wHZJafH$((V=- B!AC5k?*<f9HNU!! %3B  @*2B*:PB"O(2(-22Z[ % #"=1VV:(:="H#$Hq ZCOX3BZvA$"=HB((;:t=3@Z"3!"+- D@-U:?%* $ZCBn5` :3$*?J4i*;(BAHHA""2::2(@d4^B(V""33@="(2*(2*M*Q,5e()@::!*!AJOA%<@(*":(-V3!gb(=3Y**JHA@[O@d4.}*%!BYO(>Z@O::*"2R2(A!@2[@+B@(xEB%+*;B(3J1=3J"U!n6@(+_PB/HEJ!*=;+25k(d8;6n3 IA`cf g5##Mp'Vaj8n(.@YO2D"0R3I$A&%;2A@1+.:2(-3!"3E-(A`J"V2[SV2@[*3@22Q(xB(0?Ha9Y*6j<#x*((2Bq2[*+@(-*3 BY3u J(-*XT9fV3$B*3% q#&3@B.E-"$yE@^!Y((;BZA@B!Kkb2[RRy@:3@^0ZI A w] !+:3 ^g5ZI":V+9gB(+3fc()-=`HY3D8jV3N+:6jq2@Dw :-2.=2UBIB.["$["((U! Zpx(2(@BB AHMM!!*3!q(23ZB*J-3B* 7gBA!!BB@-T+Ak6![4n:ace5@A"-":St(:(3#A"V:!AZ[(BB YB7dB(+6g;-(+*3DBOxA"2E{((/Q)BLBAxwqU   ExC(.Wn4BK q(Y* ! H &::*VHBB"=:J$M:++((?"2Dx+Q;Y2*(ZL$!Y2F@j8;A" "(O2B[&$B "**U%J3Z![F(Zk6s2PQ+B$[R;fcBJ**(A2ADIH^p@B!(:""|a9"V &U@aj"!*U[%<"!CEB M"3x*:"2O=3B@=:*+e5B[Z[E"Q3B.x";2) AB!O:3Aca!As %  "`;-"TxvB!J-(+^HBC/;3LBq+TB* DZ!'=))* B+)"#2@+<A 7dwTE-%=U=3 Z[*6n(233]|(Ct5k22E+*!(**Ru=(/?3H[*==?:H!v*((9j3A=3B*a9[Ihj**"/"3v:* Z[(2:"`xC;CCB$/Ux*acBP]kd% vB"<H@j5x*U" C[Y) @[@@S J!BC--+[A% Z$B"U HID@wBH"2*#!%VX" Bk7e8AE!7g2*:=:%  !Y-(-(2*%#!*: AHAM2: !  EB[H"=#ZZ"* Jgb=2B!Q;;(BDs((+A2,Z"9a![\D!CEKN"2BK2) 2* @3:<xC3 I*2B!@)HYB@*(Z?,I! $@)\@=J!)@-5n-3w:V%-3@=  @<"S B)-)%::3: B*3J%=H:2:-:g9Zn4)v**)BbkABM-*!!]B"-*V*`;*q%"%!n5BfaHy}<"U!%R,@*%#=;23bk3D[HJWQ!C@afQ%S "TxAZ@+xQ"<H$J$n6@@C\=8jQ*UBYEO:Hv3[~B-3B*? !JsTA#VW[*")+E-:-:$-2BE*(3@-([-/(2*?33: 3=OBEA%+D!`C(ZZAH:< D"U @ZB#!#3Z@>:;*)CAT3BB"S)E "-)@[*T(OA@T)*:2(AL#BQpq(*=3@(A ;)/-% se43Z3!)B@3$B A$~*3" !A3@(T^+*"s` !#%O:!(:2+@[/3[@(:IB H!"?(AA=2/(X @@3!!"% CYYB$ jc?OfaJ-2Y(A"c9A"Mkf"*IA C*2;F@ZAM!";23KJT2[%`;(Bgb%1-U B"H A3@-:23vA @R2::=!$@+(: jg;S3AZEH" 2e5M(Ow"Q*!*2C.x(*2-3v3 AN3~-:Q2,)7g()A@A!Y)BO2A!w#F*=(A! I$IZIHv**Rn5Y[[,+@:?"H x-((*0>2(;B%;/(\[ Z@xB5n!9f*3@][j8YB-%"1X*(-;*3I"(CB`[A <F)H">w[j5YWA"(+*:!*3&(R;B@? !A": AH"+O@B@=2B4d::Q%(-*%*qV"%!!@T3@6gA!(9fM;[B)E"2UEZFA4d%(: ")"",CY@(?Q?#}+\[OWQsu!A[@:3==)Z@BI n42:"(B =)B[}2w"*`;.*|:*2CE4h|(3>B(h6(Y)faE4dA!%+*U!CO;E!H3!7i))"0+)AahLvd8C@*3:-X(P**(*+(E+W2Sst)$ L)]MH#J!(:O2B#sU@*#;23@O2)M)EEB V|>2AA!DI"V&* @Q$HGO;3E bd@EB*Hp U"(@G[+*2e4<[J #{"((^(d6+DB*HJ3B+A:3@+-Q+W+([9gUZ@)(;e43!$,(:+<AZA=Q(A :!A3H!ZIs+*OU!(:4iHZDB*!JUE+E,B"3B*-3x*3B-2(2[K!-223|:*VcaR+++a9`BA C>AB*3B$-*IIQ,5k)@*< F3" J:H I/,(2)ED!HcdLcji4OW*J(2+W*2Y.(^P.[(+xl433Z!)ZZWBA33%U"W:((S5eH:X2Q  $BOAsTB p"9cwp"+:(~*;C3"%2)(@0(bd#H!!Qka k6IL*2B`AIS#3!! !I`!.*:2*--Q3B(2fa"2wD`M3HJOB!(:3B AHA$Q`A"3!#  L(2G*""`6j)1Pv)"""!A@*-:3!J;ZA:H@(@3 I@2B@=HyAA "!+AyA!BBC(Ye4T->2<# '(P$O),!@)")!B@(:;+B*4e!!*<@@EI!tJ::gb8j!@:3@7h":2j8@3ZYT;B 

(note last character is a space).

Try it online!

How does it work?

The original DNA sequence is encoded in two steps to create the input string.

  1. Observe that, apart from the pesky run of 33 As at the very end of the DNA sequence (which we deal with separately), no DNA base appears more than 8 times consecutively. We can therefore use a single base-32 digit to encode a run of any of the four DNA bases. Actually a base-36 digit (coincidentally the largest natively supported radix) is preferred here to allow us to take advantage of 1-indexing. The resulting compressed string is 21,826 bytes (unfortunately too long to include in the answer). For each digit \$i\$, \$i\bmod 4\$ indexes the DNA base (A, C, G, or T) and \$\lfloor i/4\rfloor\$ gives the number of repetitions of that base (1-indexed) at that position in the sequence. This base-36 encoded string is about 27 % shorter than the original DNA sequence.

  2. Taking a quick glance at the base-36 string, we see that there are pairs of digits that appear frequently. (Here, pairs are counted beginning with the first character of the string; starting with the second character results in marginally worse compression. Each digit counts towards exactly one pair.) The most common pair, 76 (representing the sequence UG, aptly enough), occurs 687 times. There are six other pairs that occur more than 500 times, and 189 different pairs in total. This observation motivates a second compression step in which pairs of digits are replaced by single bytes. There are 72 one-byte printable ASCII characters that do not appear in the base-36 string (most because they are not base-36 digits, the exceptions being p, q, sy, and 03). We therefore associate each of the 72 most frequently occurring pairs in the base-36 string with a unique single-byte character and then use this mapping to further compress the string. The result is the input string given above, which is more than 60 % shorter than the original DNA sequence.

The decoding program simply reverses the encoding process, and then tacks 33 As back on at the end.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I'd encourage you to post this in the other challenge as well, which I have moved from the Sandbox to the main site. \$\endgroup\$ – Mitchell Spector Jun 10 at 1:51

Not the answer you're looking for? Browse other questions tagged or ask your own question.