bored game | Python Fiddle

__author__ = 'ershamay'
import unittest
import math

class unique_element:
    def __init__(self,value,occurrences):
        self.value = value
        self.occurrences = occurrences

def perm_unique(elements):
    eset=set(elements)
    listunique = [unique_element(i,elements.count(i)) for i in eset]
    u=len(elements)
    return perm_unique_helper(listunique,[0]*u,u-1)

def perm_unique_helper(listunique,result_list,d):
    if d < 0:
        yield tuple(result_list)
    else:
        for i in listunique:
            if i.occurrences > 0:
                result_list[d]=i.value
                i.occurrences-=2
                for g in perm_unique_helper(listunique,result_list,d-1):
                    yield g
                i.occurrences+=1

def answer(number_of_moves, board_size):
    # Min board size is 2
    if board_size < 2:
        return 0

# Need to have at least as many moves as needed to make it to the final square
    if number_of_moves < board_size - 1:
        return 0

# Number of each type of move to start with.
    # Always start with the simple case of enough R moves to get to the final square, then stay there
    L = 0
    R = board_size - 1
    S = number_of_moves - board_size + 1

total = 0

count = math.ceil((number_of_moves-board_size+1)/2) + 1
    i = 0
    while True:
        s = S - 2*i
        r = R + i
        l = L + i

# This sequence and all its permutations will get from start to finish.
        # However, some permutations are not valid as they go off the board.
        # Trim out all the S's because they don't advance the game at all
        winning_sequence = [0] * s + [1] * r + [-1] * l

# Check each permutation to see if it's valid or not
        for sequence in perm_unique(winning_sequence):
            filtered_sequence = list(filter(lambda a: a != 0, sequence))

if sequence[0] == -1:
                continue

position = 1
            for p in filtered_sequence:
                position += p
                # if the position ever goes < 1, or > the board_size it's an invalid sequence
                if position < 1 or position > board_size:
                    #print("Failed: %s" % (sequence,))
                    break

# If we've made it all the way to the last position without falling off it's a win!
            if position == board_size:
                #print("Success: %s" % (sequence,))
                total += 1

i += 1
        if s < 2:
            break

return total % 123454321

class TestBoardMoves(unittest.TestCase):
    def test_first(self):
        self.assertEqual(1, answer(1,2))
    def test_second(self):
        self.assertEqual(4, answer(3,2))
    def test_third(self):
        self.assertEqual(3, answer(3,3))
    def test_fourth(self):
        self.assertEqual(8, answer(4,3))
    def test_fifth(self):
        self.assertEqual(8, answer(6,3))
    def test_sixth(self):
        self.assertEqual(8, answer(999,999))

#print(list(perm_unique(['r','r','l'])))
#print(['R'] * 3 + ['L'] * 1 + ['S'] * 5)

Python Fiddle

Python Cloud IDE