# hopscotch (151 solves, 436 points)
## Description
Keith wants to play hopscotch, but in order to make things interesting, he decides to use a random number generator to decide the number of squares n to draw for a round of
hopscotch. He then creates a hopscotch board on the floor by randomly creating a sequence of ones (one square) and twos (two squares) such that the sum of all the numbers in the
sequence is n. Given 1 <= n <= 1000, find the number of valid hopscotch boards (mod 10000) he can create.

Sample Input: 5 Sample Output: 8

``nc hopscotch.hsc.tf 1337``
## Solution
This one killed me. I **WAY** overthought this problem. I first had to lookup how tf a hopscotch board works because the description didn't make sense to me (bc im stupid or smth idk)

After figuring out what I was supposed to do, I handwrote the example problem representing boards as sequences of numbers either being 1 or 2.

Example below:
1 2 1 1 1 2 1 2
1 1 2 1 1 2 2 1
1 1 1 2 1 1 2 2
1 1 1 1 2
I did this for a few more numbers until I noticed some rules:

1. For any number there will always be a base pattern of all 1's (pretty obvious)

2. The next starting pattern could be found by adding in a 2, then filling the remaining space with 1's

3. Each starting pattern could be rotated round to find more patterns

4. The number of rotations for a starting pattern is equal to it's length
I though I had all the rules figured out to make my script, so I wrote python to match the behavoir explained above. It worked... kinda. As soon as I got to a number larger than 9,
I was getting incorrect board counts. This was because I forgot a key rule:


I messed around with determining how I could find the number of possible boards of a sequence of a given length and found myself drowning in messy and over-complicated code.
Then it hit me... PERMUTATIONS! What I was trying to find was a way to find the number of permutations there were for a sequence of 1's and 2's. This is an algorithm that has
already been made before, so why re-invent the wheel. I pulled out an old math textbook and found the formula for permutations of a multiset, my saving grace:


I implemented the formula in python and got my final script:

from pwn import *
import math

def findBoards(n):
total = 0
max2 = n // 2
for twoCount in range(max2 + 1):
oneCount = n - 2 * twoCount
length = oneCount + twoCount
perm = math.factorial(length) // (math.factorial(oneCount) * math.factorial(twoCount))
total += perm
return total

io = process(['nc', 'hopscotch.hsc.tf', '1337'])
while True:
data = io.recvuntil(':').decode()
except EOFError:
n = int(re.search("(\d{1,})\n", data).group(0))
print("[RECIEVE]: " + str(n))
answer = int(findBoards(n) % 10000)
print("[SEND]: " + str(answer))

## Flag

Original writeup (https://github.com/BASHing-thru-challenges/HSCTF-2021-Writeups/tree/main/algo/hopscotch).