Rosetta Stone Challenge: mapeo genético

11

El objetivo de Rosetta Stone Challenge es escribir soluciones en tantos idiomas como sea posible. ¡Muestra tu programación multilingüismo!

El reto

Su desafío es implementar un programa que mapee algunos genes usando frecuencias cruzadas, en tantos lenguajes de programación como sea posible . Se le permite usar cualquier tipo de función de biblioteca estándar que tenga su idioma, ya que esto es principalmente un escaparate de idiomas.

¿Qué es el "mapeo genético"?

El mapeo de genes es el proceso de localizar la posición relativa de los genes en los cromosomas. Esto se realiza midiendo la frecuencia de cruce de pares de genes, igual al porcentaje de descendencia en la que el par no se hereda juntos. La distancia se mide en unidades de mapa con una unidad de mapa igual al uno por ciento del cruce. Por ejemplo, si los genes C y D tienen una frecuencia de cruce del 11%, entonces el gen C está a una distancia de 11 unidades de mapa del gen D.

El mapeo de genes se realiza con múltiples pares de genes para determinar su orden relativo. Por ejemplo, los datos (A,B,12) (D,B,7) (A,D,5) (D,H,2) (H,B,9)producen el siguiente mapa:

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

Es posible que haya notado que B......D.H..Atambién es un mapa válido. Esto es cierto, porque no es posible distinguir entre los espejos opuestos. Su programa puede elegir cuál emitir. Aunque la entrada puede no incluir todos los pares posibles, siempre habrá suficiente información para reconstruir todo el mapa (por lo que nunca habrá más de 2 salidas válidas). Además, los números siempre funcionarán (a diferencia de la biología real), lo que significa que no tendrás cosas como estas (A,B,3) (B,C,4) (A,C,13).

Entrada

La entrada comenzará con un número nseguido de una lista de genes (letras mayúsculas). Entonces habrá ntrillizos de datos. Cada conjunto constará de un par de genes y su cruce sobre la frecuencia (distancia).

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

La entrada no está rígidamente definida, porque diferentes idiomas pueden tener restricciones sobre lo que es factible. Por ejemplo, puede cambiar los delimitadores a algo distinto de comas y líneas nuevas. El formato de entrada depende en gran medida de usted.

Salida

La salida será una representación del mapa genético. Consistirá en los genes (letras mayúsculas) espaciados por períodos de modo que las distancias se representen con precisión. Aquí están las salidas para los ejemplos anteriores.

P..HI  *or*  IH..P

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

Esto tampoco es un requisito completamente rígido. Por ejemplo, podría usar algo distinto de puntos, como comas o espacios.

El criterio objetivo ganador

En cuanto a un criterio ganador objetivo, aquí está: cada idioma es una competencia separada en cuanto a quién puede escribir la entrada más corta, pero el ganador general sería la persona que gana la mayoría de estas subcompeticiones. Esto significa que una persona que responde en muchos idiomas poco comunes puede obtener una ventaja. Code-golf es principalmente un factor decisivo para cuando hay más de una solución en un idioma: la persona con el programa más corto obtiene crédito por ese idioma.

Reglas, restricciones y notas

Su programa se puede escribir en cualquier idioma que existiera antes del 20 de diciembre de 2013. También tendré que confiar en la comunidad para validar algunas respuestas escritas en algunos de los idiomas más infrecuentes / esotéricos, ya que es poco probable que pueda probar ellos.


Tabla de clasificación actual

Esta sección se actualizará periódicamente para mostrar la cantidad de idiomas y quién lidera cada uno.

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

Ranking de usuarios actuales

  1. Avi (1): AutoHotkey (632)
  2. rubik (1): dj (579)
PhiNotPi
fuente
¿Deberíamos incluir código para leer la entrada? ¿O deberíamos asumir que la entrada se pasa como primer argumento de la función?
Zapato
@ Jeffrey, supongo que cualquiera de los dos está bien.
PhiNotPi
.. la tabla de clasificación? :-)
Avi
1
¿Cuáles son los límites de entrada? No tanto n, sino principalmente los límites para el cruce sobre la frecuencia (distancia). ¿Podemos suponer que siempre será, digamos, menor que 1000?
rubik
@PhiNotPi: ¿puedes proporcionar un par de casos de prueba más? Casi he terminado el mío y me gustaría probarlo más.
rubik

Respuestas:

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

El código puede acortarse más cambiando el nombre de todos los vars a 1 carácter. Debería tener unos 610 caracteres.

Casos de prueba

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

Mi primer código de golf: D

(No estoy seguro con el conteo, simplemente lo publico en línea en un recuento de caracteres)

La idea del algoritmo es bastante mala, pero es corta. Pruebe al azar todas las posiciones de los símbolos hasta que cumplan con todas las restricciones. La entrada es con espacios en blanco, por ejemplo

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

Presione luego CTRL + D en la consola para finalizar la lectura.

Aquí está el código original que todavía usa ',' como delimitador.

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
fuente
0

dg - 717 579 bytes

Un Python está entrando.

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!

Ejemplos:

$ 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
fuente
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
fuente
3
Bienvenido a PPCG! Este es el código de golf, por lo tanto, muestre algún esfuerzo para resolver el problema en la cantidad mínima de código. Para empezar, podría eliminar todos los espacios en blanco innecesarios y utilizar nombres de variables, estructuras y funciones de una sola letra. Incluya también el idioma y el total de bytes en la parte superior de su respuesta.
Martin Ender