Rosetta Stone Challenge: Genkartierung

11

Das Ziel einer Rosetta Stone Challenge ist es, Lösungen in möglichst vielen Sprachen zu schreiben. Zeigen Sie Ihre Programmier-Mehrsprachigkeit!

Die Herausforderung

Ihre Herausforderung besteht darin, ein Programm zu implementieren, das einige Gene mithilfe von Überkreuzungsfrequenzen in so vielen Programmiersprachen wie möglich abbildet . Sie dürfen jede Art von Standardbibliotheksfunktion verwenden, über die Ihre Sprache verfügt, da dies meistens eine Sprachpräsentation ist.

Was ist "Genkartierung"?

Bei der Genkartierung wird die relative Position von Genen auf Chromosomen lokalisiert. Dies erfolgt durch Messen der Überkreuzungshäufigkeit von Genpaaren, die dem Prozentsatz der Nachkommen entspricht, bei denen das Paar nicht zusammen vererbt wird. Die Entfernung wird in Karteneinheiten gemessen , wobei eine Karteneinheit einem Prozent der Überfahrt entspricht. Wenn beispielsweise die Gene C & D eine Überkreuzungsfrequenz von 11% haben, ist Gen C ein Abstand von 11 Karteneinheiten von Gen D entfernt.

Die Genkartierung wird mit mehreren Genpaaren durchgeführt, um deren relative Reihenfolge zu bestimmen. Die Daten (A,B,12) (D,B,7) (A,D,5) (D,H,2) (H,B,9)erzeugen beispielsweise die folgende Karte:

A..H.D......B

Möglicherweise haben Sie bemerkt, dass dies B......D.H..Aauch eine gültige Karte ist. Dies ist wahr, weil es nicht möglich ist, zwischen Spiegelgegensätzen zu unterscheiden. Ihr Programm kann auswählen, welches ausgegeben werden soll. Obwohl die Eingabe möglicherweise nicht jedes mögliche Paar enthält, gibt es immer genügend Informationen, um die gesamte Karte zu rekonstruieren (es werden also nie mehr als 2 gültige Ausgaben vorhanden sein). Außerdem funktionieren die Zahlen immer (im Gegensatz zur tatsächlichen Biologie), was bedeutet, dass Sie keine Sachen wie haben (A,B,3) (B,C,4) (A,C,13).

Eingang

Die Eingabe beginnt mit einer Zahl, ngefolgt von einer Liste von Genen (Großbuchstaben). Es wird dann nDrillinge von Daten geben. Jeder Satz besteht aus einem Paar von Genen und deren Überkreuzungsfrequenz (Entfernung).

3,P,H,I
P,H,3
H,I,1
P,I,4

7,A,B,G,Q,U
B,Q,4
A,B,10
G,U,13
Q,U,10
A,G,9
G,Q,3
A,Q,6

Die Eingabe ist nicht starr definiert, da verschiedene Sprachen möglicherweise Einschränkungen hinsichtlich der Machbarkeit aufweisen. Beispielsweise können Sie die Trennzeichen in andere Zeichen als Kommas und Zeilenumbrüche ändern. Die Formatierung der Eingabe liegt weitgehend bei Ihnen.

Ausgabe

Die Ausgabe wird eine Wiedergabe der Genkarte sein. Es besteht aus den Genen (Großbuchstaben), die durch Punkte voneinander beabstandet sind, so dass die Entfernungen genau dargestellt werden. Hier sind die Ausgaben für die obigen Beispiele.

P..HI  *or*  IH..P

BG..Q.....A...U  *or*  U...A.....Q..GB

Dies ist auch keine völlig starre Anforderung. Sie können beispielsweise etwas anderes als Punkte verwenden, z. B. Kommas oder Leerzeichen.

Das objektive Gewinnkriterium

Ein objektives Gewinnkriterium ist hier: Jede Sprache ist ein separater Wettbewerb darüber, wer den kürzesten Beitrag schreiben kann, aber der Gesamtsieger wäre die Person, die die meisten dieser Unterwettbewerbe gewinnt. Dies bedeutet, dass eine Person, die in vielen ungewöhnlichen Sprachen antwortet, einen Vorteil erzielen kann. Code-Golf ist meistens ein Tiebreaker, wenn es in einer Sprache mehr als eine Lösung gibt: Die Person mit dem kürzesten Programm erhält eine Gutschrift für diese Sprache.

Regeln, Einschränkungen und Hinweise

Ihr Programm kann in jeder Sprache geschrieben werden, die vor dem 20. Dezember 2013 existierte. Ich muss mich auch auf die Community verlassen, um einige Antworten zu validieren, die in einigen der ungewöhnlicheren / esoterischeren Sprachen geschrieben wurden, da ich wahrscheinlich nicht testen kann Sie.


Aktuelle Rangliste

Dieser Abschnitt wird regelmäßig aktualisiert, um die Anzahl der Sprachen und die jeweils führenden Personen anzuzeigen.

  • AutoHotkey (632) - Avi
  • dj (579) - rubik

Aktuelle Benutzerrankings

  1. Avi (1): AutoHotkey (632)
  2. Rubik (1): DJ (579)
PhiNotPi
quelle
Sollten wir Code zum Lesen der Eingabe einfügen? Oder sollten wir einfach annehmen, dass die Eingabe als erstes Argument der Funktion übergeben wird?
Schuh
@ Jefffrey Ich nehme an, einer von beiden ist in Ordnung.
PhiNotPi
.. die Rangliste? :-)
Avi
1
Was sind die Eingabegrenzen? Nicht so sehr n, sondern vor allem die Grenzen für die Überkreuzungsfrequenz (Distanz). Können wir davon ausgehen, dass es immer weniger sein wird als 1000?
Rubik
@PhiNotPi: Können Sie noch ein paar Testfälle bereitstellen? Ich bin fast fertig und würde es gerne mehr testen.
Rubik

Antworten:

2

AutoHotkey (632)

f(i){
o:={},f:={},n:=0
loop,parse,i,`n
{
a:=A_LoopField
if A_index!=1
{
@:=Substr(a,1,1),#:=Substr(a,3,1),n+=($:=Substr(a,5))
if !IsObject(o[@])
o[@]:={}
if !IsObject(o[#])
o[#]:={}
o[@][#]:=o[#][@]:=$
}
}
f[n+1]:=@,f[@]:=n+1,a:=""
while !a
{
a:=0
for k,v in o
{
if !f[k]
{
c1:=c2:=s:=0
for k1,v1 in v
{
if f[k1]
if s
{
if (r1==f[k1]-v1)or(r1==f[k1]+v1)
c1:=r1
else r1:=c1:=""
if (r2==f[k1]-v1)or(r2==f[k1]+v1)
c2:=r2
else r2:=c2:=""
}
else
c1:=r1:=f[k1]+v1,c2:=r2:=f[k1]-v1,s:=1
}
if c1
f[c1]:=k,f[k]:=c1,a:=1
else if c2
f[c2]:=k,f[k]:=c2,a:=1
}
} 
}
loop % 2*n+1
{
v:=f[A_index]
if v
z:=1
r.=z?(!v?".":v):v
}
return Rtrim(r,".")
}

Der Code kann verkürzt werden, indem alle Variablen in 1 Zeichen umbenannt werden. Dann sollten es ungefähr 610 Zeichen sein.

Testfälle

v := "
(7,A,B,G,Q,U
B,Q,4
A,B,10
G,U,13
Q,U,10
A,G,9
G,Q,3
A,Q,6 
)"

msgbox % f(v)
msgbox % f("3,P,H,I`nP,H,3`nH,I,1`nP,I,4")
Avi
quelle
1

Python 311

import sys,random
d=sys.stdin.readlines()
u=[]
r=g=0
m={}
l=d[0].split()[1:]
for a in l:m[a]=g;g+=1
for v in d[1:]:i=v.split();u+=[i];r+=int(i[2])
j=len(l)
y=range(j)
while any(abs(y[m[t]]-y[m[w]])!=int(p) for t,w,p in u):y=random.sample(range(r),j)
o=["."]*r
for a in m:o[y[m[a]]]=a
print "".join(o).strip(".")

Mein erster Code-Golf: D.

(Ich bin mir nicht sicher mit der Zählung, ich poste es einfach online in einer Zeichenanzahl)

Die Idee des Algorithmus ist ziemlich schlecht, aber kurz. Versuchen Sie zufällig alle Positionen für die Symbole, bis sie alle Einschränkungen erfüllen. Die Eingabe erfolgt beispielsweise mit Leerzeichen

3 P H I
P H 3
H I 1
P I 4

Drücken Sie danach STRG + D in der Konsole, um das Lesen zu beenden.

Hier ist der Originalcode, der immer noch ',' als Trennzeichen verwendet.

import sys, random
#data = sys.stdin.readlines()
data = [
"3,P,H,I",
"P,H,3",
"H,I,1",
"P,I,4"
]
container = []
max_range = 0
map = {}
map_counter = 0

line_split = data[0].split(',')[1:]
count = len(line_split) # Number of genes
for symbol in line_split:
    map[symbol] = map_counter
    map_counter += 1

for line in data[1:]:
    line_split = line.split(',')
    container.append(line.split(','))
    max_range += int(line_split[2])

restart = True
while restart == True:
    positions = random.sample(range(max_range), count) # Since this loop will take like forever, but some day it will produce the correct positions
    restart = False
    for symbol1, symbol2, distance in container:
        if abs(positions[map[symbol1]] - positions[map[symbol2]]) != int(distance):
            restart = True
            break

output = ["."] * max_range
for symbol in map:
    output[positions[map[symbol]]] = symbol
print "".join(output).strip(".") # Strip . to make it more pretty
nvidia
quelle
0

dg - 717 579 Bytes

Ein Python kommt an.

import '/sys'
w,o=list,tuple
p=g a b m->
 b in g=>a,b=b,a
 i,l,k=g.index a,w$g,w$g
 l!!(i+m),k!!(i-m)=b,b
 g!!(i+m)=='.'=>yield$o$l
 g!!(i-m)=='.'=>yield$o$k
g=t->
 d=sorted key:(i->snd i)$map((a,b,i)->((a,b),int i))$filter fst$map(i->i.split ',')$t.split '\n'
 (a,b),i=d.pop!
 g=w$('.',)*i*4
 g!!i,g!!(i+i)=a,b
 s=set'$o g
 while d=>
  d.sort key:((k,v)->set k&(set$fst$w s))
  n,(a,b),i=set! :+d.pop!
  for r in s=>
   if(a in r and b in r=>i==abs(r.index a-r.index b)=>n.add r)(1=>n.update$p r a b i)
   s = n
 '\n'.join$map(l->(''.join l).strip '.')s
print$g sys.stdin.read!

Beispiele:

$ echo """P,H,3
H,I,1
P,I,4""" | dg dna.dg
P..HI
$ echo """B,Q,4
A,B,10
G,U,13              
Q,U,10
A,G,9
G,Q,3
A,Q,6""" | dg dna.dg
BG..Q.....A...U
rubik
quelle
0
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <malloc.h>

struct Gene
{
    char a1 , a2 ;
    int d ;
};
typedef struct Gene gene ;

struct Set
{
    int appr_id ;
    char CMN_char ;
};
typedef struct Set set ;

gene *stack;
int cp_id1 , cp_id2 , N=0 , cid , *used , n ;
char ucmn_char , *cmp1 , *cmp2 , *base , ep[15] ;                       
set ap_set ;


void randomize(void)
{   int i;
    Set temp;
    for(i=0;i<(n-1);i++)
    {
        temp=stack[i];
        stack[i]=stack[i+1];
        stack[i+1]=temp;
    }

    return;

}
void populate_ep ( char ucmn_char )
{
    int i;
    for ( i=0 ; ep[i] != '\0' ; i ++ );
        ep[ i ] = ucmn_char ;
}

set find_appr ( void )
{
    int i , j ;
    set s ;
    for ( i = 0 ; i < n ; i++ )
    {
        if ( used[ i ] == 1 )
            continue ;
        else
        {
            for ( j = 0 ; ep[ j ] != '\0' ; j++ )
            {
                if ( ep[ j ] == stack[ i ].a1 || ep[ j ] == stack[ i ].a2 )
                {
                    s.appr_id = i ;
                    s.CMN_char = ep[ j ] ;
                    return s ;
                }
            }
        }
    }
}

void destroy ( int id )
{
    used[ id ] = 1 ;
}

int get_center_id ( char a )
{
    int i ;
    for ( i = 0 ; i < N * 2 ; i++ )
        if ( base[ i ] == a )
            return i ;
}

int get_comparer ( void )
{
    int i , j , k ;
    for ( i = 0 ; i < n ; i ++ )
    {
        if ( used[ i ] == 0 )
        for ( j = 0 ; ep[ j ] != '\0' ; j ++ )
            if ( stack[ i ].a1 == ep[ j ])
                for ( k = 0 ; k < 15 ; k ++ )
                    if ( stack[ i ].a2 == ep[ k ] )
                        return i ;
    }
    printf ( "\nWrong set of genes....\n" ) ;
    exit ( 0 ) ;
}

void compare_and_merge ( int cid, int cp_id1, int cp_id2 )
{
    int base_cp_id , i ;
    char temp = ( ucmn_char == stack[ cid ].a1 ) ? stack[ cid ].a2 : stack[ cid ].a1 ;
    for ( i = 0 ; i < N * 2 ; i ++ )
        if ( base[ i ] == temp )
            base_cp_id = i ;
    if ( stack[ cid ].d == ( sqrt ( pow ( ( cp_id1 - base_cp_id ) , 2 ) ) ) )
    {   
        base[ cp_id1 ] = cmp1[ cp_id1 ] ;
        return ;
    }
    else
    {
        base[ cp_id2 ] = cmp2[ cp_id2 ] ;
        return ;
    }
}

void show_stack ( void )
{
    int i ;
    printf ( "The gene sets you entered are: \n" ) ;
    printf ( "____________\n" ) ;
    for ( i = 0 ; i < n ; i ++ )
        if ( used[ i ] == 0 )
            printf ( "%c %c %d\n" , stack[i].a1, stack[i].a2, stack[i].d ) ;
    printf ( "____________\n" ) ;
}

int main ( void )
{
    printf ( "Enter number of gene sets: " ) ;
    scanf ( "%d" , &n ) ;
    stack = ( gene* ) calloc ( n , sizeof ( gene ) ) ;
    used = ( int* ) calloc ( n , sizeof ( int ) ) ;
    int i ;
    N = 0 ;
    for ( i = 0 ; i < n ; i ++ )
    {
        char y[ 2 ] ;
        scanf ( "%s" , y ) ;
        stack[ i ].a1 = y[ 0 ] ;
        scanf ( "%s" , y ) ;
        stack[ i ].a2 = y[ 0 ] ;
        scanf ( "%d" , &stack[ i ].d ) ;
        N += stack[ i ].d ;
        used[ i ] = 0 ;
        fflush ( stdin ) ;
    }   
    randomize();
    show_stack ( ) ;
    int ff ;
    strcpy ( ep , " " ) ;
    cmp1 = ( char* ) calloc ( N * 2 , sizeof ( char ) ) ;
    cmp2 = ( char* ) calloc ( N * 2 , sizeof ( char ) ) ;
    base = ( char* ) calloc ( N * 2 , sizeof ( char ) ) ;
    for ( i = 0 ; i < N * 2 ; i ++ )
        base[ i ] = cmp1[ i ] = cmp2[ i ] = '=' ;
    base[ N ] = stack[ 0 ].a1 ;
    base[ N + stack[ 0 ].d ] = stack[ 0 ].a2 ;
    destroy ( 0 ) ;
    ep[ 0 ] = stack[ 0 ].a1 ;
    ep[ 1 ] = stack[ 0 ].a2 ;
    for ( ff = 0 ; ff < n / 2  ; ff ++ )
    {
        ap_set = find_appr ( ) ;
        cmp1[ get_center_id ( ap_set.CMN_char ) ] = ap_set.CMN_char ;
        cmp2[ get_center_id ( ap_set.CMN_char ) ] = ap_set.CMN_char ;
        ucmn_char = ( stack[ ap_set.appr_id ].a1 == ap_set.CMN_char ) ? stack[ ap_set.appr_id ].a2 : stack[ ap_set.appr_id ].a1;
        cmp1[ cp_id1 = get_center_id ( ap_set.CMN_char ) + stack[ ap_set.appr_id ].d ] = ucmn_char ;
        cmp2[ cp_id2 = get_center_id ( ap_set.CMN_char ) - stack[ ap_set.appr_id ].d ] = ucmn_char ;
        populate_ep ( ucmn_char ) ;
        destroy ( ap_set.appr_id ) ;
        cid = get_comparer ( ) ;
        compare_and_merge ( cid , cp_id1 , cp_id2 ) ;
        destroy ( cid ) ;
    }
    int start , end ;
    for ( i = 0 ; i < N * 2 ; i ++ )
        if ( base[ i ] != '=' )
        {
            start = i ;
            break ;
        }
    for ( i = N * 2 - 1 ; i >= 0 ; i -- )
        if ( base[ i ] != '=' )
        {
            end = i ;
            break ;
        }
        for ( i = start ; i <= end ; i ++ )
            printf( "%c" , base[ i ] ) ;
    printf( "\n\n" ) ;
}
Ankit Kumar
quelle
3
Willkommen bei PPCG! Dies ist Code Golf, also zeigen Sie bitte einige Anstrengungen, um das Problem in der minimalen Menge an Code zu lösen. Zunächst könnten Sie alle unnötigen Leerzeichen entfernen und Variablen-, Struktur- und Funktionsnamen aus einem Buchstaben verwenden. Bitte geben Sie auch die Sprache und die Gesamtanzahl der Bytes oben in Ihrer Antwort an.
Martin Ender