I finally finished!!!!!! In the process, I realized why I hate division so much. Took me 2 hours.(I started it last night)

# Hopscotch Programming Puzzles

**BuildASnowman**#22

That is really cool! And pretty genius, too. Now - there are two thing I see that you could change to make it better. The first one is that once you know it's not a prime (when prime=false), you no longer have to test any other numbers. So, under that prime=false, you can add 'break;', which simply ends the for loop.

The other one is that you don't actually have to test ever number up to your variable 'number'. Let's say our number is 30. Remember: Every factor has to have a pair, and the smallest possible factor is 2, so what's the largest possible factor? Can you extend this into a general statement about the largest factor of any given number?

And you only have to test every number up to it's largest possible factor.

**t1_hopscotch**#23

## This is a great point!

The largest possible factor is the number divided by 2.

However, I think you only have to check up to the square root of the number if you work out pairs of factors as you go (For example, if you find that the number is divisible by 3, you know that `number/3`

will also be a factor.)

And woah @FreshGuppy thatās awesome

**t1_hopscotch**#24

Hmm another challenge that Iād thought about for a while was:

# A line of 2048

In the game, there are 4 numbers in each row or column.

```
Here is an example row (0 represents an empty tile):
0 2 4 4
```

Can you work out the output after a line (row or column) has been swiped in a direction? (up/down, left/right ā you can choose which direction.)

```
For example, if I swiped right from the previous example, I would get:
0 0 2 8
```

More examples with swiping a row to the right:

```
2 2 4 4 -> 0 0 4 8
4 0 2 8 -> 0 4 2 8
```

## Some information for if you haven't played the game before

You can play an online version of the game here:

https://gabrielecirulli.github.io/2048/

- All numbers are powers of 2 (from 2 onwards)
- When tiles of the same number collide, they add up to make a new tile

**t1_hopscotch**#25

## Some background information

This is a bit sneaky because for forever Iāve been genuinely curious if thereās a better way to make 2048 work since i first thought about it!! So Iām disguising this as a challenge here Iām really sure there are more ways to make it work. And Iām sure others can come up with it

Once you have one line, you basically will have the whole game!

## information from my attempt

This was my attempt at explaining the ideas I had:

http://forum.gethopscotch.com/t/uber-impressive-work-by-t1-hopscotch-its-2048/1761/10?u=t1_hopscotch

But recently I was thinking about how you could use clones in Hopscotch to make arrays, and possibly how it could be made a lot more easily in Hopscotch right now! If I hadnāt had to copy code manually, it probably would have been made 16 times faster I really bet that it could be done a lot better I donāt think there were clones when I started on it, but clones could help a lot

Anyway, I also know Valgo tried 2048 too ā we were discussing it here:

http://forum.gethopscotch.com/t/valgos-general-topic/20408/647

**MR.GAM3R**#26

Is there a set formula for solving it? (EDIT: sorry, I didnāt fully understand the puzzle yet. You can ignore my question )

**hnu**#28

Hereās a simple problem for all you guys to do:

Create a chess AI.

This problem can also be a competition, pitting the best chess AIās against each other.

**BuildASnowman**#29

Primality proving is one of my favorite things. Ever.

Hereās a challenge: Implement a Sieve of Eratosthenes. This is where you have a list of the numbers (like the picture on wikipedia), and you just go through and eliminate all multiples of 2, 3, 4, 5ā¦ etc until you are left with only primes.

For those a little more determined: Although @t1_hopscotchās suggestion is fast (For those who know big-O, it runs in O(Sqrt(n)), it isnāt the fastest. The second fastest algorithm out there is AKS, which was actually discovered accidentally. (The big O of this algorithm is actually quite interesting, Iāll expand if someone wants me to).

My challenge is to implement AKS in Hopscotch. It may seem daunting, but it really isnāt. If someone is stuck or needs a little help, Iāve just made about 10 lines of pseudocode that would implement the algorithm. Just really read about it, donāt be thrown off by the math.

I also have a very difficult challenge for anyone ready to get their hands dirty. You know how I said AKS is the second fastest primality algorithm? Well, the fastest is a thing called Elliptic Curve Primality Tests. Itās what most math based languages use, because it runs *super* fast. There are two main ECPTs, GoldwasserāKilian and AtkināMorain. They rely on properties of elliptic curves, which are equations of the form y^2=x^3+ax+b. If anyone actually implements this, I will be in awe. I think it would be fair to say you will have won Hopscotch. Iām about to public a paper on elliptic curves and Iām not even sure I could do it xD But, even if you try, thatās still a feat in my book. And Iāll be there every step of the way if you have questions. I love this stuff.

In fact, if any of you know languages outside of Hopscotch, try implementing these algorithms in them too. Making something in Python first always helps me make it in Hopscotch.

**JonnyGamer**#31

Ooh! Primality tests! I have discovered a primaliy test myself (although quite by accident) with the use of polygons.

First, create any n-gon youād like. Start at a point, and draw a line from that point to the next point closest to it. Then, do that again in the same direction, but instead of going to the next point, go to the next one, 2 points over. Then 3, then 4, and 5. This eventually creates a pattern.

(Sorry if this seemed confusing, Iāll add a picture below and a better explanation)

```
ā¢ (a)
ā¢ (e) ā¢ (b)
ā¢ (d) ā¢ (c)
```

So you draw a line from A to B, B to D, D to B, B to A, A to A, and it repeats itself

So as I draw lines from point to point, it increases by increments of 1. For any n-gon where ānā is divisible by 2, the line pattern weāve made is rotationally symmetrical (180 to 180).

For any n-gon where ānā is prime, the line pattern we made is not symmetrical whatsoever (Now you might be saying, "Ah, but what happens when you have an n-gin where ānā is odd? I have a proof for this, too)

For any n-gon where ānā is odd, the line pattern we made is not symmetrical, but some points that the line travels through get reused, whereas prime n-gons do not. Hereās a picture to help understanding:

I think this has to do with mods, but I havenāt learned them yet. So I have no idea. But I think this is extremely cool, but probably not the best for finding vastly huge prime numbers. Iāll try to figure out a way to represent it (Iāll probably have to do it in different bases, Iām not sure yet) without having to draw out each polygon

Anyways, Iām really excited on this subject

**BuildASnowman**#32

That is actually amazing. God, thatās incredible. Playing around with shapes and numbers, thatās how you find amazing things like this. Keep at it, youāre a natural.

I think I know how this works, and how you can represent it without the shapes. But let me do some math

**BuildASnowman**#33

Ok. Iāve got it. And itās beautiful. Itās a lot deeper than I expected. You hit on something really cool. I know you havenāt learned in depth about modulo, but do you know what it means? Like do you understand what I mean when I say a clock is related to modulo?

**JonnyGamer**#34

Awesome! Iām glad that this will end up being used! Simple things in math can lead to huge breakthroughs, that why I love math so much

Yeah, I semi understand what module is, since you said a clock, that would mean 11 + 4 = 3; and 12 = 0

Or for a 3 sectioned module, 2 + 2 = 1; 3 = 0

I have played around with this a tiny bit, but I know that there is a much larger section of math about this that I have yet to learn

**BuildASnowman**#35

Ok, so hereās a proof that if you get multiple hits on one vertex, it isnāt prime (that isnāt the whole thing - we also have to prove that if you donāt get multiple hits it is prime. But this a fairly large portion of the claim that Iām sure can be adapted to prove the whole thing). So, instead of labing the vertices of your n-gon with letters, label them with numbers 1-n.

The numbers of the vertices we hit at each stage are:

1 mod n (which is just 1)

1+2 mod n

1+2+3 mod n

ā¦

We need the mod n because, letās say we have a pentagon, 1+2+3 = 6, and a pentagon only has 5 vertices, so it loops back around to 1.

Now, recall that 1+2+3+4ā¦n = (n(n+1))/2. So we can write the vertices that get hit in the form:

(1(2))/2 mod n

(2(3))/2 mod n

(3(4))/2 mod n

ā¦

Now, lets say two of these are equal (i.e, the line hits the point twice), at step u and v. That means that

[ (u(u+1))/2 = (v(v+1))/2 ] mod n

When two things are āequal mod nā, that means that the right side of the equation mod n is equal to the left side of the equation mod n.

Do the multiplication and shove everything to one side and you get:

[u^2+u-v^2-v=0] mod n

Now remember when something is equal to 0 mod n, it means that thing divides n.

Factor it and you get:

[(u+v)(u-v) + (u-v) = 0] mod n

A little manipulation can then show:

[(u+v+1)(u-v)=0] mod n

Since the product of those two expressions in the parentheses divide n, both of them separately divide n. Specifically, u-v divides n, and u-v is an integer. So, n is not prime because an integer divides it.

QED.

**BuildASnowman**#36

I also have a proof of the whole thing, but it requires a little more math. I can show it to you if you want, but in the mean time Iāll try to simplify it. Also, something cool to note is that your system works for every number except powers of 2, for reasons Iām still trying to decipher.

**JonnyGamer**#37

Ooh! Thatās a lot of math!

But I didnāt understand half of it, so does it eventually work?

This is really fascinating!

**t1_hopscotch**#38

Oooh I donāt know if thereās a set formula out there actually. How I approached it was I coded individual calculations for a whole bunch of cases. It was basically checking for empty tiles, and checking if tiles next to each other were equal. There are probably better ways of doing it!

Thatās a really cool problem!

It would be interesting to even just implement chess in Hopscotch that lets you make only valid moves (e.g. knight can only land in L shape, king can only move 1 square in any direction, bishop can only move diagonally)

And woah that was awesome

And definitely, this was basically why i made this topic! (You should check out Programming Puzzles & Code Golf Stack Exchange too. I was considering bringing a few puzzles inspired by the ones on there.) I sort of put the focus on Hopscotch specifically because it brings up really interesting creative constraints (like doing functions and recursion)

**JonnyGamer**#40

āintegral calculus, higher dimensional objects, elliptic curves, abstract algebra and the Riemann Hypothesisā

Youāre 2 years younger than me and know all of this stuff!?

Iām gonna be homeschooled this year and Iām really excited since I will learn all these things

Do you recommend anything I could use to learn these topics?

_{ I found a Calculus series on 3Blue1Brown YouTube channel that I shall binge watch very shortly}

Iām having trouble finding places on the internet that feature the incredibleness of math, but Iām sure there are loads of places that I am completely oblivious to

**BuildASnowman**#41

I learned it in a very terrible way. But that terrible way worked for me so perhaps it will work for you.

Everyone always says Khan Academy or a structured course like it, but I canāt bear those videos. I lose interest almost immediately. So what I did, is I found math.stackexchange.com, and just browsed through questions. Sort by new, top voted, bounty, look at certain tags, etc. At the beginning I understood none of it. But it just became a habit to browse through the questions and look at how pretty and complex the math was. Occasionally I would learn something, but usually how I learned things is if I thought something was cool and wanted to learn about it, I would just spend hours on google and wiki trying to get a grasp of what it even meant, not necessarily how I can practically apply it. Wikipedia and wolfram mathworld are good resources for that. If after researching it I still didnāt understand it, I would just ask a question on the math stackexchange asking for the intuitive ideas behind it. Thats probably the most important part - ask questions on the math stackexchange. Thatās how I learned a lot.

Thatās also a main thing, donāt look to practically apply anything at first. Took my 2 years between when I knew what contour integration was and when I did my first integral. Just get an idea of the ideas behind the math. And thatās how I learned, and I think thatās the best way to learn. Unstructured, not in a classroom, just you, the internet, and whatever you want to learn about.

Later, when you start getting into topics past college and grad school math, you will have to start reading books and papers on arxiv to get those ideas, but the concept is the same.

And good luck. Took me a lot of trial and error to get where I am today. You have a very naturally talented mathematical brain, moreso than I do. I would be lying if I said it took discipline and hard work to get to where I am today, but it certainly took time. So be patient. You are already above your classes, you are in no rush. Find tidbits, piece them together, and see what you come up with. *Play with it.* Have fun with it. Thatās what math is about.