Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Journey to the Moon JavaScript Solution
function processData(input) {
var temp = input.split('\n')
var [ N, I ] = temp.shift().split(' ').map( Number )
// generate graph
var graph = [] // store in an array of Set [ 0 : [ 0, 1 ], 1 : [ 3, 2 ] ] (to prevent duplicate)
var relationalMap = {} // use to remember the map { 0 : 0, 1 : 0, 2 : 1, 3 : 1 }
for(let i = 0; i < I;i++)
{
var [ ast1, ast2 ] = temp.shift().split(' ').map( Number )
// if both of the ast1 and ast2 found in the different map => group two map
if ( relationalMap.hasOwnProperty( ast1 ) && relationalMap.hasOwnProperty( ast2 ) )
{
// console.log('[both found]', ast1, ast2, relationalMap)
var graphIndex = relationalMap[ ast1 ]
var graphIndex2 = relationalMap[ ast2 ]
// continue if there are already in the graph
if ( graphIndex === graphIndex2 ) continue
// update the set from 2 to 1, and clear set 2
for( let i of graph[ graphIndex2 ] )
{
graph[ graphIndex ].add( i )
relationalMap[ i ] = graphIndex
}
graph[ graphIndex2 ].clear()
}
// if one of ast1 and ast2 found in the map
else if ( relationalMap.hasOwnProperty( ast1 ) || relationalMap.hasOwnProperty( ast2 ) )
{
// console.log('[one found]', ast1, ast2, relationalMap)
let graphIndex = relationalMap[ ast1 ] || relationalMap[ ast2 ]
graph[ graphIndex ].add( ast1 ).add( ast2 )
relationalMap[ ast1 ] = graphIndex
relationalMap[ ast2 ] = graphIndex
}
// if ast1 ast2 not found in the map
else if ( !relationalMap.hasOwnProperty( ast1 ) && !relationalMap.hasOwnProperty( ast2 ) )
{
// console.log('[not found]', ast1, ast2, relationalMap)
let graphSet = new Set()
graphSet.add( ast1 ).add( ast2 )
let graphIndex = ( graph.push( graphSet ) - 1 ) + ''
relationalMap[ ast1 ] = graphIndex
relationalMap[ ast2 ] = graphIndex
}
}
// console.log('[graph]', graph);
// console.log('[relationalMap]', relationalMap)
// denotes the number of permissible ways to choose a pair of astronauts.
var ways = 0;
for( let i = 0;i < graph.length - 1; i++)
{
let waysi = graph[i].size
for( let j = i + 1; j < graph.length; j++ )
{
let waysj = graph[j].size
ways += waysi * waysj
}
}
// and those who is alone in their country
let alone = N - Object.keys( relationalMap ).length
ways += Object.keys(relationalMap).length * ( N - Object.keys(relationalMap).length )
ways += c(alone, 2)
console.log(ways)
}
function c(n, x)
{
let numerator = n
for(let i = n-1;i>(n-x);i--)
{
numerator *= i
}
let denominator = x
for(let i = x - 1 ;i>=2;i--)
{
denominator *= i
}
return numerator/denominator
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.