← Catalogo
NWCK
PyJS

Distances in Trees

Phylogeny

Pagina originale su rosalind.info

Descrizione

Il formato Newick rappresenta un albero filogenetico come stringa annidata di parentesi (es. "(dog,cat);" rappresenta un albero con radice non nominata e due foglie, dog e cat, collegate direttamente alla radice). La distanza tra due nodi in un albero è il numero di archi sull'unico cammino che li collega (poiché un albero non ha cicli, questo cammino è sempre unico).

Given

Una collezione di n (n ≤ 40) alberi in formato Newick (senza lunghezze di ramo), ciascuno con al massimo 200 nodi; ogni albero Tk è seguito da una coppia di nodi xk e yk in Tk.

Return

Una collezione di n interi positivi, in cui il k-esimo intero rappresenta la distanza tra xk e yk in Tk.

Sample Dataset

(cat)dog;
dog cat

(dog,cat);
dog cat

Sample Output

1 2

La mia esecuzione

08/24/2026 11:24:47

Input · dataset.txt

(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((Zosterops_epops)Vipera_rutilans)Varanus_decor)Trionyx_fulvus)Trionyx_caucasicus)Tringa_picta)Trachemys_atriceps)Thecla_nigrolineatus)Tetrao_tatarica)Sus_melanostictus)Sericinus_fuscus)Seokia_jaculus)Selenocosmia_ampullatus)Scolopax_ocellatus)Sceloporus_helena)Rosalia_alpina)Rhynchaspis_dauricus)Rhinolophus_leucotus)Remiz_kingii)Regulus_ruficollis)Recurvirostra_mystacinus)Pyxicephalus_alpina)Pogona_australis)Pleurodeles_japonica)Platemys_irregularis)Phyllopneuste_tatarica)Phrynocephalus_meles)Phasianus_aspera)Perdix_carnivorus)Pelomedusa_pictus)Pelodiscus_clypeata)Otocoris_modestus)Osteopilus_mykiss)Ortigometra_schneideri)Ophisops_schreibersi)Net_olivacea)Natriciteres_americanus)Mylopharyngodon_colombianus)Mustela_fasciolata)Monticola_timidus)Monticola_lineatus)Mogera_iguana)Megophrys_lobatus)Mabuya_scripta)Lobipes_means)Litoria_colombianus)Larus_parvus)Lagenorhynchus_guttata)Homopholis_sinensis)Homalopsis_calamita)Holaspis_arenarius)Himantopus_leucorodia)Heterodon_schneideri)Gyps_ibera)Gerrhosaurus_porphyrio)Gecarcinus_striatus)Eutamias_strepera)Eutamias_arizonensis)Euspiza_fernandi)Eunectes_pallasii)Elseya_minutus)Dipus_subglobosa)Cygnus_nyroca)Cuora_uluguruensis)Corvus_mexicanum)Corallus_rubida)Clemmys_guineti)Citharacanthus_nigrolineatus)Chrysemys_salamandra)Cervus_regius)Ceratophrys_clypeata)Cardiocranius_chrysargos)Capreolus_middendorffi)Capra_modestus)Canis_teguixin)Canis_sanguinolentus)Canis_cancerides)Candoia_longipes)Calidris_verrucosus)Bronchocela_dione)Bradypodion_sauromates)Balaena_mysticetus)Atrophaneura_melleri)Archispirostreptus_rutila)Anthropoidae_carnifex)Anodonta_indica)Anas_mehelyi)Alcedo_cenchria)Aix_maculatum);
Heterodon_schneideri Selenocosmia_ampullatus

(((Acanthis_dubia,((((((((Ameiva_angustirostris,(((Aphonopelma_calligaster,Gonocephalus_stimsoni),Latastia_erythropus),((Callipogon_tinctorius,Hydrosaurus_leschenaultii),Pyrgilauda_melleri))),Gyps_zonata),Physignathus_campestris),(Sorex_garmani,Spermophilus_ferrumequinum)),Pusa_cachinans),Net_indica),Norops_wislizeni),Cynops_hipposideros)),Equus_jaculus),Acanthoceros_pygmeus,(((((((((((Alaus_Jankowskii,(Pseudemys_zonata,Sorex_aureola)),(Mogera_maihensis,Parus_flammea)),(Enhydra_scripta,(Himantopus_musicus,Moschus_taezanowskyi))),Limnaeus_geniculata),Heterodon_quinquestriatus),((((Aplopeltura_uluguruensis,Castor_martensi),Tadarida_cinerea),(Laudakia_compactus,Porphyrio_tricolor)),Ursus_equestris)),((((((((Alcedo_subcinctus,Lamprophis_reticulatus),Rhacodactylus_labiatus),Anthropoides_himalayanus),Hydrosaurus_auratus),((((((((((Allactaga_capra,(Balaenoptera_mystacinus,(Dryobates_trigonopodus,Gavia_amboinensis))),Cinclus_sibilans),((((Anthropoides_grossmani,(Platalea_guttata,Psammophis_dactylisonans)),Kinosternon_percnopterus),Ciconia_nupta),Nucifraga_catenifer)),(Rhabdophis_medici,Scolopendra_femoralis)),((((((Argynnis_aegyptia,Norops_dispar),((Bos_cingulata,Odonthurus_personata),(Chlidonias_timidus,Phrynosoma_erythrogastra))),(Bradypodion_longicollis,Plethodon_ulikovskii)),(Coenobita_pygmaeus,Psalmopoeus_cranwelli)),Egretta_calvus),Cygnopsis_ferina)),Falco_monorhis),(Apalone_barbata,((Leptopelis_horridum,Passer_glacialis),Plegadis_vanellus))),((Anas_medici,Spalerosophis_eremita),Saiga_nippon)),Pterinochilus_dendrophila),Ingerophrynus_piscator)),(Bufo_pyromelana,Turdus_ibis)),(Chrysemys_teniotis,Desnana_musicus)),Dafila_minor)),Hottentotta_obsoleta),((Athene_flava,((Milvus_maldivarum,Tylototriton_mutabilis),Tamias_dives)),(((Citharacanthus_glacialis,Eschrichtius_azureus),Ophisops_versicolor),Tadarida_caesius))),Grammostola_fuellebornii),(Opheodrys_hungaricus,(Tadorna_milii,Tylototriton_fasciolata))));
Plegadis_vanellus Limnaeus_geniculata

(((((((((((((((Acanthoscurria_eremita,Teratolepis_alpina),Apodora_pusilla),(Homopholis_subniger,Nipponia_mugodjaricus)),Ctenotus_karelini),((Hydrosaurus_dorsalis,Otis_Anas),Notophthalmus_guentheri)),Sericinus_macqueni),(Rosalia_barbata,Sus_mykiss)),(Notophthalmus_miliaris,(Remiz_chinensis,Ruticilla_caesius))),(Ciconia_wumuzusume,Panthera_caeruleus)),(Chondropython_similis,(Cynops_auriculatus,Grammostola_oxycephalum))),Cygnus_pictus),Aplopeltura_nigrolineatus),Phrynosoma_cyanea),Nemachilus_longicollis),(((((Agama_jubata,Epipedobates_orientalis),Saiga_anatina),Litoria_ferrumequinum),(((Colaeus_subglobosa,(Iomachus_strepera,Oxyura_moschata)),Ingerophrynus_maritimus),(Lyrurus_tetrix,Pelodytes_sauromates))),Citellus_jaculus),(((((((((((((((((Alpes_variabilis,(((((Casarca_leucorodia,Chrysopelea_tentaculatum),Tylototriton_citreola),sibiricus_apus),Mustela_geyri),(Grus_hilarii,Kassina_spaldingi))),(Chrysemys_avicularia,Pareas_albicilla)),(((((Archispirostreptus_marmorata,Otocoris_jaspidea),(Epipedobates_ferrumequinum,Nhandu_platyrhinos)),Euspiza_dulkeitiana),(Callipogon_xanthocheilus,(Gongylophis_cliffordii,Haliaetus_schneideri))),Budytes_carinatus)),Plegadis_cingulata),((Buthus_olivacea,Phrynohyas_leucoryphus),Sphenurus_apus)),((Morelia_schneideri,Tetrao_pusilla),Salvelinus_vertebralis)),(((((((Crotaphytus_moschata,Gecarcinus_rusticolus),Philothamnus_cristata),Tylototriton_savignii),(Mogera_multituberculatus,Nucifraga_hendricksoni)),Gambelia_novaeguineae),Hottentotta_nigropalmatus),(Macrorhamphus_govinda,Prunella_Bernicla))),Ctenosaura_reticulatus),Gyps_rufinus),Recurvirostra_not),(((((Buthacus_glutinosus,Holaspis_flavirufa),Tryngites_tolai),Osteopilus_striatus),(Limosa_pica,Pogona_rosmarus)),(Chondropython_bukhunensis,Rufibrenta_taczanowskius))),Eirenis_tridactylum),Cypselus_merganser),Oxyura_guangxiensis),Anolis_ibis),(Ameiva_serpentina,Archispirostreptus_moschata)),Gypaetus_carbonaria));
Ctenotus_karelini Archispirostreptus_marmorata

(((Acanthis_calamita,(Hadogenes_hemilasius,Mochlus_kopsteini)),Holodactylus_dendrophila),Acanthis_leucotus,(((((((((((((((((((((((((((((((((((Allactaga_indicus,(Chelydra_lesueurii,Enhudra_solitaria)),(Bos_fischeri,Hysterocrates_scalaris)),Ingerophrynus_gratiosa),(Motacilla_leucorodia,Netta_leucogeranus)),Aphonopelma_orientalis),Desnana_rufodorsata),Limnaeus_lopatini),(Marmota_glaucescens,Tylototriton_similis)),Pagophila_argali),Emberiza_truncatus),Parnassius_coloratovillosum),Caiman_albirostris),Teratoscincus_galeatus),Enhydra_schrencki),Mabuya_avosetta),Pyrrhocorax_melanostictus),(((((Anas_flammea,Anolis_galactonotus),((Balaenoptera_nasicus,Middendorffinaia_collybitus),Rissa_himalayensis)),(((Anolis_caesius,((((Bombus_pedo,Cervus_chukar),Pseudorca_coloratovillosum),Tetrao_mykiss),(Leptopelis_argentatus,Tupinambus_mexicanum))),Phylloscopus_deminutus),((Gekko_tigris,Iguana_cristatellus),Uroplatus_crucigera))),Citellus_dennysii),(((Balaena_ameiva,(Pelusios_Jankowskii,Sterna_duplus)),Bradypodion_lobatus),Rosalia_dives))),Cyclagras_melanostictus),Cuculus_piceus),Sericinus_smaragdina),(((((Chlamydosaurus_ibis,Homopholis_angustirostris),Heterodon_temminckii),Cuora_papuana),Pelomedusa_veredus),Spermophilus_fluviatilis)),(((((Bombyx_notaeus,Procellaria_anatina),Camptoloma_grandis),(Leptobrachium_hypoleucos,Paraphysa_infrafrenata)),Tadarida_leucogeranus),Furcifer_anser)),(Chamaeleo_mycterizans,Xenophrys_caeruleus)),(Cardiocranius_moschiferus,(((Gambelia_ferruginea,Phalacrocorax_peregusna),Gekko_longicollis),((Gerrhosaurus_ignicapillus,Querquedula_caelebs),Rangifer_alba)))),((Cottus_wumuzusume,Rufibrenta_felderi),Dipus_percnopterus)),(Limnaeus_melanoleucus,Panthera_schneideri)),(Dendrobates_stejnegeri,Xenophrys_crispus)),(Archispirostreptus_pholeter,((Phyllopneuste_floridana,(Physignathus_paradoxus,Totanus_fimbriatus)),Poephagus_torquata))),Marmota_alpina),(Porphyrio_kazanakowi,Tropidurus_venulosa)),Mustela_cranwelli),Casarca_duplex),((Eudrornias_penelope,Ovis_septentrionalis),Leiocephalus_helvetica)),Coregonus_armata),Chrysemys_trigonopodus));
Acanthis_leucotus Chelydra_lesueurii

(((((Acanthogonatus_ferruginea,Gyps_maldivarum),Mabuya_cinclus),Tadarida_boschas),((Philomachus_paradisi,Phrynocephalus_constricticollis),Tetraogallus_fuliginosus)),((((((((((((Acanthoscurria_noctua,(((((((Alectoris_rosea,Totanus_getula),((Anolis_truncatus,(Eulabeia_uluguruensis,(Siniperca_hendersoni,Ziphius_bonasus))),Eschrichtius_septentrionalis)),Diomedea_carbonaria),(Certhia_hassanica,Rhodostethia_dorsalis)),Eunectes_galeatus),Pratincola_erythronota),Rufibrenta_heudei)),Gonyosoma_temminskii),(((Almo_equestris,Chettussia_papuana),(((((Bufo_kurilensis,(Middendorffinaia_sepsoides,Tamias_subruficollis)),Notophthalmus_musculus),Dyscophus_leucocephala),Fulica_atthis),Coleonyx_angulifer)),Oedura_vertebralis)),(Kaloula_catenifer,(Lepidobatrachus_subrubrum,(Parabuthus_stellatum,Rhynchophis_varius)))),Philothamnus_glacialis),(((Certhia_deserti,Thymallus_eximia),Pratincola_multituberculatus),Philomachus_himalayensis)),Pituophis_caucasicus),Megaloperdix_rubicola),((Eucratoscelus_bicoloratum,Scaphiophryne_turtor),Leptopelis_carinatus)),Rhinolophus_sibirica),Dahurinaia_apollo),Odobenus_bengalensis),((((((((Acipenser_ferruginea,((Buteo_breitensteini,Gavia_guttifer),Rhamphiophis_grupus)),(((Aegialifes_angustirostris,(Brachyramphus_tetrax,((Cardiocranius_emilia,Dendrobates_situla),Salvelinus_galericulata))),Haliaeetus_schreibersi),Gypaetus_squaterola)),((Hyla_schreibersi,Oenanthe_canus),(Leptopelis_semipalmatus,Sturnus_kingii))),(Parus_belliana,Sphenops_scalaris)),(((((((Buteo_zonata,Fulica_geniculata),Homalopsis_oxycephalum),(Enhydris_diffidens,Salvelinus_mandarina)),Phalacrocorax_torquata),Pratincola_chinensis),(Neophron_moschata,Tupinambus_saxatilis)),Capra_olivacea)),(Nemorhaedus_quinquestriatus,Zosterops_glutinosus)),Dendrobates_heterolepidotus),(Hottentotta_glutinosus,Lutra_rutilans)));
Capra_olivacea Hyla_schreibersi

((((((((((Abantias_monilis,(Dahurinaia_rhymnus,Syrrhaptes_aeruginosus)),((Calotes_himalayensis,(Lanius_grunniens,Leiurus_chrysaetos)),crecca_dulkeitiana)),((Ambystoma_regius,(((Ardea_melleri,((((Dyscophus_ulikovskii,Oedura_ion),Pleurodeles_bairdi),Lycaenopsis_pardalis),Sitta_gregaria)),Varanus_blakistoni),((Bos_hosii,Upupa_cliffordii),Salamandra_aestivus))),Lagenorhynchus_nigrolineatus)),(((Cottus_celer,Otis_nigropalmatus),Heterodon_murinus),Pelusios_lesueurii)),Arenaria_acanthinura),Sericinus_borealis),Lagenorhynchus_ciliatus),(Chelus_uncia,Fregilegus_peregusna)),Kinixys_barbatus),Actitis_barroni,(((((Actitis_teguixin,Phelsuma_japonica),Onychodactylus_subruficollis),(Amphiuma_cocincinus,(((Candoia_coelestis,(Lepus_zenobia,Zosterops_caudicinctus)),(((Clemmys_trigonopodus,Geochelone_ochropus),Mesoplodon_armata),Querquedula_sibilans)),Pyrrhocorax_maldivarum))),((((((Almo_fulvus,(((Lycodon_carnifex,Pelusios_eximia),Phelsuma_torquatus),Phrynomerus_barbata)),(((((((((((((((((Alopex_microlepis,Lamprophis_ovata),(Rissa_molurus,Streptopelia_rapax)),(((((((Chrysopelea_deserti,(Tadorna_penelope,Teratoscincus_hendricksoni)),Pelomedusa_macrops),Recurvirostra_limosa),Thecla_doctus),Picus_longicollis),Megaptera_olivacea),Litoria_lutra)),Pelecanus_elegans),Kaloula_nasuta),Camptoloma_caesius),Rhacodactylus_lagopus),(Totanus_albirostris,Tylototriton_maculata)),Uromastyx_subcinctus),Hydrochelidon_rostratus),((((Cottus_livia,Sturnus_diadema),Eublepharis_subniger),Coturnix_saiga),Squaterola_schreibersi)),((((Chelodina_olivacea,Haliaeetus_sp),((Crocodylus_squaterola,Pseudorca_cristata),Passer_corone)),Eirenis_davidiana),(Coturnix_campestris,Morelia_salvator))),Dipus_paradoxus),(Arenaria_taxus,Sphenurus_onocrotalus)),Notophthalmus_sp),Leiolepis_sebae),(((Dipus_peregusna,Leiolepis_amethistina),Synthliboramphus_vittatus),Falco_kopsteini))),(Nipponia_leucopsis,Siniperca_pulcher)),Brachyramphus_chamaeleontinus),Caiman_arvensis),Minipterus_jaspidea)),(Megaptera_buccata,Podoces_clypeata)));
Phrynomerus_barbata Nipponia_leucopsis

((((Acanthis_vastus,(Babycurus_carolinensis,Haplopelma_indica)),(Capella_venulosa,Laudakia_rostratus)),(((Bos_arvensis,Litoria_pardalis),Gecarcinus_tinctorius),((((Bradypodion_griseus,Lobipes_horridum),((Cottus_reticulatus,Norops_situla),Nyctixalus_quinquetaeniata)),(Mareca_smi

… troncato (54.375 caratteri totali)

Output · run_log.txt

OK
40 15 33 38 7 6 9 25 7 2 13 19 18 11 2 2 15 17 21 20 13 15 10 2 16 10 17 2 2 2 2 32 57 2 21

Esegui nel browser · Pyodide

Mostra il codice sorgente (problem.py)
#http://rosalind.info/problems/nwck/

from collections import defaultdict, deque


def parse_newick(s):
    """Costruisce un albero da una stringa in formato Newick (senza lunghezze di ramo).
    Restituisce la lista di adiacenza (non orientata) e un dizionario nome -> id nodo."""
    s = s.strip()
    s = s.removesuffix(";")
    adiacenza = defaultdict(list)
    nomi = {}
    pos = [0]
    contatore = [0]

    def nuovo_nodo():
        contatore[0] += 1
        return contatore[0]

    def parse_clade():
        nodo = nuovo_nodo()
        if pos[0] < len(s) and s[pos[0]] == "(":
            pos[0] += 1
            while True:
                figlio = parse_clade()
                adiacenza[nodo].append(figlio)
                adiacenza[figlio].append(nodo)
                if s[pos[0]] == ",":
                    pos[0] += 1
                    continue
                elif s[pos[0]] == ")":
                    pos[0] += 1
                    break
        inizio_nome = pos[0]
        while pos[0] < len(s) and s[pos[0]] not in ",()":
            pos[0] += 1
        nome = s[inizio_nome:pos[0]]
        if nome:
            nomi[nome] = nodo
        return nodo

    parse_clade()
    return adiacenza, nomi

def distanza(adiacenza, nomi, x, y):
    partenza = nomi[x]
    arrivo = nomi[y]
    visitati = {partenza: 0}
    coda = deque([partenza])
    while coda:
        corrente = coda.popleft()
        if corrente == arrivo:
            return visitati[corrente]
        for vicino in adiacenza[corrente]:
            if vicino not in visitati:
                visitati[vicino] = visitati[corrente] + 1
                coda.append(vicino)
    return None

def lettura(filename):
    with open(filename) as f:
        righe = [r.strip() for r in f if r.strip() != ""]
    blocchi = []
    for i in range(0, len(righe), 2):
        albero = righe[i]
        x, y = righe[i + 1].split()
        blocchi.append((albero, x, y))
    return blocchi

def main():
    blocchi = lettura("dataset.txt")
    risultati = []
    for albero, x, y in blocchi:
        adiacenza, nomi = parse_newick(albero)
        risultati.append(str(distanza(adiacenza, nomi, x, y)))
    print(" ".join(risultati))

if __name__ == "__main__":
    # execute only if run as a script
    main()

Soluzione JavaScript

Esegui ora, live

Mostra il codice sorgente
// Distances in Trees (Rosalind ID: NWCK) - soluzione JavaScript
// indipendente, non una trascrizione di problem.py: stessa logica
// (parser ricorsivo discendente per il formato Newick senza lunghezze
// di ramo, costruzione della lista di adiacenza, poi BFS per la
// distanza tra due foglie nominate), riscritta in modo idiomatico per
// JS.
//
// Contratto: riceve il contenuto testuale di dataset.txt, restituisce
// l'output testuale (stessa forma dell'output Python).
function parseNewick(sInput) {
  let s = sInput.trim();
  if (s.endsWith(";")) s = s.slice(0, -1);

  const adiacenza = new Map();
  const nomi = new Map();
  const pos = { v: 0 };
  const contatore = { v: 0 };

  function getAdiacenza(nodo) {
    if (!adiacenza.has(nodo)) adiacenza.set(nodo, []);
    return adiacenza.get(nodo);
  }

  function nuovoNodo() {
    contatore.v += 1;
    return contatore.v;
  }

  function parseClade() {
    const nodo = nuovoNodo();
    if (pos.v < s.length && s[pos.v] === "(") {
      pos.v += 1;
      while (true) {
        const figlio = parseClade();
        getAdiacenza(nodo).push(figlio);
        getAdiacenza(figlio).push(nodo);
        if (s[pos.v] === ",") {
          pos.v += 1;
          continue;
        } else if (s[pos.v] === ")") {
          pos.v += 1;
          break;
        }
      }
    }
    const inizioNome = pos.v;
    while (pos.v < s.length && !",()".includes(s[pos.v])) {
      pos.v += 1;
    }
    const nome = s.slice(inizioNome, pos.v);
    if (nome) nomi.set(nome, nodo);
    return nodo;
  }

  parseClade();
  return { adiacenza, nomi };
}

function distanza(adiacenza, nomi, x, y) {
  const partenza = nomi.get(x);
  const arrivo = nomi.get(y);
  const visitati = new Map([[partenza, 0]]);
  const coda = [partenza];
  let head = 0;
  while (head < coda.length) {
    const corrente = coda[head++];
    if (corrente === arrivo) return visitati.get(corrente);
    for (const vicino of adiacenza.get(corrente) ?? []) {
      if (!visitati.has(vicino)) {
        visitati.set(vicino, visitati.get(corrente) + 1);
        coda.push(vicino);
      }
    }
  }
  return null;
}

function lettura(datasetText) {
  const righe = datasetText
    .split("\n")
    .map((r) => r.trim())
    .filter((r) => r !== "");

  const blocchi = [];
  for (let i = 0; i < righe.length; i += 2) {
    const albero = righe[i];
    const [x, y] = righe[i + 1].split(/\s+/);
    blocchi.push([albero, x, y]);
  }
  return blocchi;
}

export default function solve(datasetText) {
  const blocchi = lettura(datasetText);

  if (blocchi.length === 0) {
    throw new Error("Input non valido: nessun blocco albero/coppia trovato");
  }

  const risultati = [];
  for (const [albero, x, y] of blocchi) {
    const { adiacenza, nomi } = parseNewick(albero);
    risultati.push(String(distanza(adiacenza, nomi, x, y)));
  }

  return `${risultati.join(" ")}\n`;
}