Rating:

# 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

1

```

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:

``2's DONT HAVE TO BE GROUPED!!!``

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:

```python3

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'])

io.recvline()

while True:

try:

data = io.recvuntil(':').decode()

print(data)

except EOFError:

print(io.recvline().decode())

quit()

n = int(re.search("(\d{1,})\n", data).group(0))

print("[RECIEVE]: " + str(n))

answer = int(findBoards(n) % 10000)

io.sendline(str(answer))

print("[SEND]: " + str(answer))

```

## Flag

``flag{wh4t_d0_y0U_w4nt_th3_fla5_t0_b3?_'wHaTeVeR_yOu_wAnT'}``

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