TextFile2.txt

/*
Our local radio station is running a show where the songs are ordered in a very specific way.  The last word of the title of one song must match the first word of the title of the next song - for example, "Silent Running" could be followed by "Running to Stand Still".  No song may be played more than once.

Given a list of songs and a starting song, find the longest chain of songs that begins with that song, and the last word of each song title matches the first word of the next one.  Write a function that returns the longest such chain. If multiple equivalent chains exist, return any of them.

Example:
songs1 = [
    "Down By the River",
    "River of Dreams",
    "Take me to the River",
    "Dreams",
    "Blues Hand Me Down",
    "Forever Young",
    "American Dreams",
    "All My Love",
    "Cantaloop",
    "Take it All",
    "Love is Forever",
    "Young American",
    "Every Breath You Take",
]
song1_1 = "Every Breath You Take"
chaining(songs1, song1_1) => ['Every Breath You Take', 'Take it All', 'All My Love', 'Love is Forever', 'Forever Young', 'Young American', 'American Dreams', 'Dreams']

Additional Input:
song1_2 = "Dreams"
song1_3 = "Blues Hand Me Down"
song1_4 = "Cantaloop"

songs2 = [
    "Bye Bye Love",
    "Nothing at All",
    "Money for Nothing",
    "Love Me Do",
    "Do You Feel Like We Do",
    "Bye Bye Bye",
    "Do You Believe in Magic",
    "Bye Bye Baby",
    "Baby Ride Easy",
    "Easy Money",
    "All Right Now",
]
song2_1 = "Bye Bye Bye"
song2_2 = "Bye Bye Love"

songs3 = [
    "Love Me Do",
    "Do You Believe In Magic",
    "Magic You Do",
    "Magic Man",
    "Man In The Mirror"
]
song3_1 = "Love Me Do"

All Test Cases:
chaining(songs1, song1_1) => ['Every Breath You Take', 'Take it All', 'All My Love', 'Love is Forever', 'Forever Young', 'Young American', 'American Dreams', 'Dreams']
chaining(songs1, song1_2) => ['Dreams']
chaining(songs1, song1_3) => ['Blues Hand Me Down', 'Down By the River', 'River of Dreams', 'Dreams']
chaining(songs1, song1_4) => ['Cantaloop']
chaining(songs2, song2_1) => ['Bye Bye Bye', 'Bye Bye Baby', 'Baby Ride Easy', 'Easy Money', 'Money for Nothing', 'Nothing at All', 'All Right Now']
chaining(songs2, song2_2) => ['Bye Bye Love', 'Love Me Do', 'Do You Feel Like We Do', 'Do You Believe in Magic']
chaining(songs3, song3_1) => ['Love Me Do', 'Do You Believe in Magic', 'Magic Man', 'Man In The Mirror']

Complexity Variable:
n = number of songs in the input
*/
const songs1 = [
  'Down By the River',
  'River of Dreams',
  'Take me to the River',
  'Dreams',
  'Blues Hand Me Down',
  'Forever Young',
  'Forever and Ever',
  'American Dreams',
  'All My Love',
  'Cantaloop',
  'Take it All',
  'Love is Forever',
  'Young American',
  'Every Breath You Take'
];
const song1_1 = 'Every Breath You Take';
const song1_2 = 'Dreams';
const song1_3 = 'Blues Hand Me Down';
const song1_4 = 'Cantaloop';

const songs2 = [
  'Bye Bye Love',
  'Nothing at All',
  'Money for Nothing',
  'Love Me Do',
  'Do You Feel Like We Do',
  'Bye Bye Bye',
  'Do You Believe in Magic',
  'Bye Bye Baby',
  'Baby Ride Easy',
  'Easy Money',
  'All Right Now'
];
const song2_1 = 'Bye Bye Bye';
const song2_2 = 'Bye Bye Love';

const songs3 = [
  'Love Me Do',
  'Do You Believe In Magic',
  'Magic You Do',
  'Magic Man',
  'Man In The Mirror'
];
const song3_1 = 'Love Me Do';

function  getSongFirstAndLastNode (songTitle) {
  let words = songTitle.split(' ');
  return { first : words[0], last : words[words.length-1], song:songTitle, connections:[], visited:false };
}

function deepCopy (o){
    return JSON.parse(JSON.stringify(o));
}

function toString(ob) {
    return JSON.stringify(ob, null, 2);
}

function  getSongWordsNodes (songTitles) {
  let songsFirstAndLast = [];
  songTitles.forEach ((currentElement)=>{
    let songFirstAndLast = getSongFirstAndLastNode (currentElement);
    songsFirstAndLast.push(songFirstAndLast);
  });
 return(songsFirstAndLast);  
}

// function walkTree(nodes, index, output, prefix) {
//     if(nodes[index].visited) {return false;}
//     nodes[index].visited = true;
//     let nodeCopy = deepCopy(nodes);
//     let wentDeeper = false;
//     prefix = prefix + "\n" +nodes[index].song; 
//     console.log(prefix);

//     nodes[index].connections.forEach((nextIndex)=>{
//         if(nodes[nextIndex].visited) {return false;}
//         walkTree(nodeCopy, nextIndex, output, prefix);
//         wentDeeper = true;
//     });
// //    console.log(nodes[index].song);
//     if(!wentDeeper){
//         console.log("*****");
//         output.push(prefix);
//     }
//     return output;
// }    

function walkTree(nodes, index, output, accumulator) {
    if(nodes[index].visited) {return false;}
    nodes[index].visited = true;
    let nodeCopy = deepCopy(nodes);
    let wentDeeper = false;
    let accumulator2 = [...accumulator];
    accumulator2.push(nodes[index].song);
 //   console.log(toString(accumulator2));

    nodes[index].connections.forEach((nextIndex)=>{
        if(nodes[nextIndex].visited) {return false;}
        walkTree(nodeCopy, nextIndex, output, accumulator2);
        wentDeeper = true;
    });
//    console.log(nodes[index].song);
    if(!wentDeeper){
//        console.log("*****");
        output.push(accumulator2);
    }
    return output;
} 

function getLongestPlaylist(songs, startingSong){
    console.log("songs "+ toString(songs));
    console.log("start "+ toString(startingSong));
    
    let songNodes = getSongWordsNodes (songs);
    let start = -1;
    getSongFirstAndLastNode (startingSong); 
    (node) => node.song == startingSong;
    
    start = songNodes.findIndex( (node) => node.song === startingSong);
    if( start == -1){
        // not found
    }
//    console.log("start "+ start);

    songNodes.forEach((node, i)=>{
        songNodes.forEach((second, j)=>{
            if(i == j){return;}
            if(node.last == second.first){
                node.connections.push(j);
            }
        })
    });
//    console.log(toString(songNodes));

    let playlists = walkTree(songNodes, start, [], []);    
    console.log(toString(playlists));
    let longestPlaylistIndex = 0;
    let longestPlaylist = -1;
    
    playlists.forEach((songs, index)=>{
        if(longestPlaylist < songs.length){
            longestPlaylistIndex = index;
            longestPlaylist = songs.length;
        }
    });
    console.log(`the longest playlist is number ${longestPlaylistIndex+1} at ${longestPlaylist} songs long:`);
    console.log("--------------");
    console.log(playlists[longestPlaylistIndex]);
    console.log("--------------\n");
    
}

console.log("songlists for songs1, starting with "+song1_1+"\n");
getLongestPlaylist(songs1, song1_1);

console.log("songlists for songs1, starting with "+song1_2+"\n");
getLongestPlaylist(songs1, song1_2);

console.log("songlists for songs1, starting with "+song1_3+"\n");
getLongestPlaylist(songs1, song1_3);

console.log("songlists for songs2, starting with "+song2_1+"\n");
getLongestPlaylist(songs2, song2_1);

console.log("songlists for songs2, starting with "+song2_2+"\n");
getLongestPlaylist(songs2, song2_2);

console.log("songlists for songs3, starting with "+song3_1+"\n");
getLongestPlaylist(songs3, song3_1);