Hopscotch Programming Puzzles

#20

Okay, I will try to do both.

#21

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

My Project

@t1_hopscotch

#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.

#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

#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

#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

#26

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

#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.

#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.

#30

I just learned about that! I researched it yesterday!

#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:

Pictures

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

#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

#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?

#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

#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.

#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.

#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!

#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)

#39

:)

#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