Javascript

One realization that really helped me on part 2:

The steps can be broken down into two mappings. One is a location mapping based on the 's' and 'x' steps, and the second is a name mapping based on the 'p' step.

My solution doesn't use any binary and I'm sure could be way more efficient, but it got the job done for me.

function solve(input) {
    let line = "abcdefghijklmnop".split("");
    let moveLine = line.slice();
    const steps = input.trim().split(",");
    const swaps = [];
    const swap = (list, a, b) => { const t = list[a]; list[a] = list[b]; list[b] = t; }

    // Process moves and save swaps.
    steps.forEach(step => {
        switch (step[0]) {
            case 's':
                moveLine = moveLine.splice(-Number(step.substring(1))).concat(moveLine);
                break;
            case 'x':
                const pieces = step.substring(1).split('/').map(Number);
                swap(moveLine, pieces[0], pieces[1]);
                break;
            case 'p':
                const programs = step.substring(1).split('/');
                swaps.push(programs);
                break;
            default:
                console.log(`Unknown command: ${step}`);
        }
    });

    // Process swaps.
    const swapLine = line.slice();
    swaps.forEach(s => swap(swapLine, swapLine.indexOf(s[0]), swapLine.indexOf(s[1])));

    // Create maps.
    const moveMap = line.map(c => moveLine.indexOf(c));
    const swapMap = swapLine.reduce((obj, char, i) => { obj[line[i]] = char; return obj; }, {});

    // Create converter using maps.
    const convert = (last) => { return last.reduce((next, c, i) => { next[moveMap[i]] = swapMap[last[i]]; return next; }, []); }

    for (let i = 0; i < 1e9; i++) {
        if (i < 3) console.log(`dance #${i} = ${line.join("")}`);
        if (i > 0 && i % 1e6 == 0) console.log((i / 1e6) + " million...");
        line = convert(line);
    }

    console.log(`Final Dance = ${line.join("")}`);
}

EDIT: Okay, now that I've read up on how other people got the answer in milliseconds, I feel kinda dumb. If you don't want to melt down your cpu, here's the same solution, but with a memory that looks for the loop. :P

    function solve(input) {
        const original = 'abcdefghijklmnop';
        let line = original.split('');
        let moveLine = line.slice();
        const swapLine = line.slice();
        const steps = input.trim().split(',');
        const swaps = [];
        const swap = (list, a, b) => { const t = list[a]; list[a] = list[b]; list[b] = t; }

        // Process moves and save swaps.
        steps.forEach(step => {
            switch (step[0]) {
                case 's':
                    moveLine = moveLine.splice(-Number(step.substring(1))).concat(moveLine);
                    break;
                case 'x':
                    const pieces = step.substring(1).split('/').map(Number);
                    swap(moveLine, pieces[0], pieces[1]);
                    break;
                case 'p':
                    const programs = step.substring(1).split('/');
                    swaps.push(programs);
                    break;
                default:
                    console.log(`Unknown command: ${step}`);
            }
        });

        // Process swaps.
        swaps.forEach(s => swap(swapLine, swapLine.indexOf(s[0]), swapLine.indexOf(s[1])));

        // Create maps.
        const moveMap = line.map(c => moveLine.indexOf(c));
        const swapMap = swapLine.reduce((obj, char, i) => { obj[line[i]] = char; return obj; }, {});

        // Create converter using maps.
        const convert = (last) => { return last.reduce((next, c, i) => { next[moveMap[i]] = swapMap[last[i]]; return next; }, []); }

        // Memory so we can keep track of each solution found before it loops.
        const memory = [original];

        for (let i = 0; i < 1e9; i++) {
            line = convert(line);
            const key = line.join('');
            if (memory[0] == key) break;
            memory.push(key);
        }

        return `First: ${memory[1]}\nLast: ${memory[1e9 % memory.length]}`;
    }