Rosetta Stone Challenge: Cartographie des gènes

11

L'objectif d'un Rosetta Stone Challenge est d'écrire des solutions dans autant de langues que possible. Montrez votre multilinguisme de programmation!

Le défi

Votre défi est de mettre en œuvre un programme qui cartographiera certains gènes en utilisant des fréquences de croisement, dans autant de langages de programmation que possible . Vous êtes autorisé à utiliser n'importe quelle sorte de fonction de bibliothèque standard de votre langue, car il s'agit principalement d'une vitrine de langue.

Qu'est-ce que la «cartographie génétique»?

La cartographie des gènes est le processus de localisation de la position relative des gènes sur les chromosomes. Cela se fait en mesurant la fréquence de croisement de paires de gènes, égale au pourcentage de descendants dans lesquels cette paire n'est pas héritée ensemble. La distance est mesurée en unités de carte avec une unité de carte égale à un pour cent de franchissement. Par exemple, si les gènes C & D ont une fréquence de croisement de 11%, alors le gène C est à une distance de 11 unités de carte du gène D.

La cartographie des gènes est effectuée avec plusieurs paires de gènes pour déterminer leur ordre relatif. Par exemple, les données (A,B,12) (D,B,7) (A,D,5) (D,H,2) (H,B,9)produisent la carte suivante:

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

Vous avez peut-être remarqué qu'il B......D.H..As'agit également d'une carte valide. Cela est vrai, car il n'est pas possible de distinguer les opposés miroirs. Votre programme peut choisir lequel produire. Bien que l'entrée ne puisse pas inclure toutes les paires possibles, il y aura toujours suffisamment d'informations pour reconstruire la carte entière (il n'y aura donc jamais plus de 2 sorties valides). De plus, les chiffres fonctionneront toujours (contrairement à la biologie réelle), ce qui signifie que vous n'aurez pas de trucs comme (A,B,3) (B,C,4) (A,C,13).

Contribution

L'entrée commencera par un nombre nsuivi d'une liste de gènes (lettres majuscules). Il y aura alors des ntriplets de données. Chaque ensemble consistera en une paire de gènes et leur croisement sur la fréquence (distance).

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

L'entrée n'est pas définie de manière rigide, car différentes langues peuvent avoir des restrictions sur ce qui est faisable. Par exemple, vous pouvez remplacer les délimiteurs par autre chose que des virgules et des sauts de ligne. Le formatage des entrées dépend en grande partie de vous.

Production

La sortie sera une restitution de la carte des gènes. Il sera composé des gènes (lettres majuscules) espacés par des périodes telles que les distances soient représentées avec précision. Voici les sorties des exemples ci-dessus.

P..HI  *or*  IH..P

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

Ce n'est pas non plus une exigence complètement rigide. Par exemple, vous pouvez utiliser autre chose que des points, comme des virgules ou des espaces.

Le critère de gain objectif

En ce qui concerne un critère de gain objectif, le voici: chaque langue est une compétition distincte pour savoir qui peut écrire la plus courte inscription, mais le gagnant général serait la personne qui remporte le plus de ces sous-compétitions. Cela signifie qu'une personne qui répond dans de nombreuses langues rares peut bénéficier d'un avantage. Le code-golf est surtout un bris d'égalité lorsqu'il y a plus d'une solution dans une langue: la personne avec le programme le plus court obtient un crédit pour cette langue.

Règles, restrictions et notes

Votre programme peut être écrit dans n'importe quelle langue qui existait avant le 20 décembre 2013. Je devrai également compter sur la communauté pour valider certaines réponses écrites dans certaines des langues les plus rares / ésotériques, car il est peu probable que je puisse tester leur.


Classement actuel

Cette section sera périodiquement mise à jour pour montrer le nombre de langues et qui mène dans chacune.

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

Classements des utilisateurs actuels

  1. Avi (1): AutoHotkey (632)
  2. rubik (1): dj (579)
PhiNotPi
la source
Faut-il inclure du code pour lire l'entrée? Ou devrions-nous simplement supposer que l'entrée est passée comme premier argument de la fonction?
Chaussure
@Jefffrey Je suppose que l'un ou l'autre va bien.
PhiNotPi
.. le classement? :-)
Avi
1
Quelles sont les limites d'entrée? Pas tellement n, mais surtout les limites de la fréquence de passage (distance). Pouvons-nous supposer qu'il sera toujours, disons, inférieur à 1000?
rubik
@PhiNotPi: pouvez-vous fournir quelques cas de test supplémentaires? J'ai presque fini le mien et j'aimerais le tester davantage.
rubik

Réponses:

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,".")
}

Le code peut être raccourci en renommant tous les vars en 1 caractère. Il devrait alors être d'environ 610 caractères.

Cas de test

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
la source
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(".")

Mon premier code-golf: D

(Je ne suis pas sûr du décompte, je le poste simplement en ligne dans un décompte de caractères)

L'idée de l'algorithme est assez mauvaise, mais elle est courte. Essayez au hasard toutes les positions des symboles jusqu'à ce qu'elles satisfassent à toutes les contraintes. L'entrée est avec un espace par exemple

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

Appuyez ensuite sur CTRL + D dans la console pour terminer la lecture.

Voici le code d'origine qui utilise toujours «,» comme délimiteur.

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
la source
0

dg - 717 579 octets

Un Python arrive.

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!

Exemples:

$ 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
la source
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
la source
3
Bienvenue chez PPCG! Il s'agit de golf de code, veuillez donc faire un effort pour résoudre le problème avec un minimum de code. Pour commencer, vous pouvez supprimer tous les espaces inutiles et utiliser des noms de variables, de structures et de fonctions à lettre unique. Veuillez également inclure la langue et le nombre total d'octets en haut de votre réponse.
Martin Ender