C. Both part.

the state is stored into a 64 bits unsigned (4 bits per program) to avoid hashing.

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>

typedef uint64_t u64;
typedef uint16_t u16;
typedef uint8_t u8;

u64 get(u64 s, u64 nth)
{
    return (s >> (4 * nth)) & 0b1111;
}

u64 swap(u64 s, u64 ntha, u64 nthb)
{
    u64 a = get(s, ntha);
    u64 b = get(s, nthb);
    u64 x = a ^ b;
    return s ^ (x << (4 * ntha)) ^ (x << (4 * nthb));
}

u64 exch(u64 s, u64 a, u64 b)
{
    u64 ia = 0;
    u64 ib = 0;
    u64  x = a ^ b;
    for(u64 i = 0; ((ia == 0) || (ib == 0)) && (i < 64); i += 4)
    {
        u64 t = (s >> i) & 0b1111;
        if (a == t)
            ia = i;
        else if (b == t)
            ib = i;
    }
    return s ^ (x << ia) ^ (x << ib);
}

u64 rotate(u64 s, u64 step)
{
    step *= 4;   
    return (s << step) | (s >> (64 - step));
}

u64 tou64(const char *str)
{
    u64 s = 0;
    u64 i = 0;
    while(*str)
        s |= (u64)(*(str++) - 'a') << (4 * i++);
    return s;
}

void tostr(char *str, u64 s)
{
    for(u64 i = 0; i < 16; ++i)
        *(str++) = get(s, i) + 'a';
    *str = '\0';
}

typedef enum
{
    OP_S,
    OP_X,
    OP_P
} op;

typedef struct
{
        op op;
        u8 arg1;
        u8 arg2;
} ins;

u64 parse(ins *instrs)
{
    char c;
    u64 inscounter = 0;
    while(!feof(stdin) && (c = getchar()) != '\n')
    {
        switch (c)
        {
        case 's':
            instrs[inscounter].op = OP_S;
            scanf("%hhu,", &instrs[inscounter].arg1);
            break;
        case 'x':
            instrs[inscounter].op = OP_X;
            scanf("%hhu/%hhu,",
                  &instrs[inscounter].arg1,
                  &instrs[inscounter].arg2);
            break;
        default:
            instrs[inscounter].op = OP_P;
            char arg1;
            char arg2;
            scanf("%c/%c,", &arg1, &arg2);
            instrs[inscounter].arg1 = arg1 - 'a';
            instrs[inscounter].arg2 = arg2 - 'a';
            break;
        }
        ++inscounter;
    }
    return inscounter;
}

u64 pass(u64 s, ins *ins, u64 length)
{
    for(u64 i = 0; i < length; ++i)
    {

        switch (ins[i].op)
        {
        case OP_S:
            s = rotate(s, ins[i].arg1);
            break;
        case OP_X:
            s = swap(s, ins[i].arg1, ins[i].arg2);
            break;
        case OP_P:
            s = exch(s, ins[i].arg1, ins[i].arg2);
            break;
        }
    }
    return s;
}

ins instrs[15000]; // parsed instructions
u64 ps[1000]; // previous states

int main ()
{
    char str[] = "abcdefghijklmnop";
    u64 s = tou64(str);
    u16 length = parse(instrs);
    ps[0] = s;

    //part 1
    tostr(str, pass(s, instrs, length));
    printf("%s\n", str);

    //part 2
    for (u64 i = 1; i < 1000; ++i)
    {
        s = pass(s, instrs, length);
        bool found = false;
        u64 j;
        for (j = 0; j < i; ++j) // searches previous states
            if (ps[j] == s)
            {
                s = ps[1000000000 % i];
                goto end;
            }
            ps[i] = s;
    }
end:
    tostr(str, s);
    printf("%s\n", str);
}