A General Post About the More Math-ey Levels

2

Knowing where to find resources that are useful to you and how much research you really need is key.

Example: from problem to research to algorithm development

I had been stuck on the level Prime Pathing, and I needed an efficient way to determine if large numbers are prime. So, I googled “prime number algorithm,” and the first result was a link to “Primality Test” on Wikipedia. I scanned through the page, and there was plenty of extra info I didn’t need. However, this paragraph caught my eye:

A good way to speed up these methods (and all the others mentioned below) is to pre-compute and store a list of all primes up to a certain bound, say all primes up to 200. (Such a list can be computed with the Sieve of Eratosthenes or by an algorithm that tests each incremental m against all known primes < √m). Then, before testing n for primality with a serious method, n can first be checked for divisibility by any prime from the list. If it is divisible by any of those numbers then it is composite, and any further tests can be skipped.

I kept reading and looking up everything until I understood enough to start coding the algorithm.
I settled with an algorithm using a Sieve of Eratosthenes to make a predefined list of primes that I can use to quickly check for primality among numbers.
I even read up a little bit on Fermat’s Primality Test, but I decided not to implement that because it seemed more complicated than what I decided to go with.
(I had no clue what a Sieve of Eratosthenes or a Fermat’s Primality Test was before I started doing this level)

The next step for me was just writing the algorithm in a way that I can understand:

# Sieve of Eratosthenes
# define a function that returns a list of all prime numbers up to a given limit:
    # make an empty list that will store composite numbers (dubbed composites)
    # make an empty list that will store prime numbers (dubbed primes)
    
    # for each number in the range of limit, going up by 1 on each iteration:
        # if this number is found in the composites list:
            # skip to the next number (continue)
        
        # else:
            # this number is prime, so add it to the primes list
            
            # then, for each multiple of this prime number:
                # add that multiple to the composites list if it's not there already
    
    # return the list of primes

# define a list of prime numbers using the Sieve of Eratosthenes which will be used for a faster primality test

# Primality Test
# define a function that tests if a given number is prime
# use a globally defined list of primes to test the given number against to increase efficiency
...

I would have used sets instead of lists, but sets aren’t implemented in CodeCombat.

Then, I changed that pseudocode into Python.

Summary
For complicated problems that I can’t think of a solution for off the top of my head:

  1. Most of my time is probably spent researching and understanding the problem;
  2. Then, a moderate amount of time is spent writing the pseudocode that I can easily understand and check the logic of;
  3. And, finally, the least of my time is spent writing the actual code.

(End of example)
A different approach

Looking for helpful posts in old threads

Using your “What In Carnation” example, I searched and found this thread (I’m not a subscriber, so I don’t have access to this level). In the thread, I see two kinds of replies:

  • The replies from people trying to “hack it out” are from people that don’t completely understand what the level is really asking for. You can scan through their posts, but there’s usually nothing useful to help you.

  • The other type of replies comes from people who know what’s going on in the code, who know what the level is about. These are the posts that you should read through if you need help.

Here’s a shining example of a post from that same thread that fits the second category of replies:

Posts like these are the ones you really want to prioritize to read first.

Yes, the gap in skill required going from Cloudrip Mountain to Kelvintaph Glacier is really big.

There’s more of an emphasis towards doing your own research during the levels of Kelvintaph Glacier.

I recommend you to learn what vectors are and what they are used for before you program with them, just to avoid any shortsighted mistakes. Personally, I didn’t even know what vectors were until I learned about them in my third semester of calculus! Vectors can be a surprisingly simple concept to grasp, but their usefulness really shines in physics and advanced calculus.

Parametric equations along with trigonometry can be useful to learn, primarily for those flower-drawing levels.

Not all programs are going to be math-y. Some problems focus more on logic. There are a few levels in Kelvintaph Glacier that are complex logic problems with minimal math, such as Gridmancer Redux.

Some math resources:

Use a search engine/Wikipedia if you need a quick reference for an algorithm, whether it is math or logic.
Use StackOverflow if you have a question about implementing something in code (be mindful that all code might not work in CodeCombat due to incomplete transpiler features).

If you want more math-y levels:

Archived Problems - Project Euler (You’ll probably want to program these outside of CodeCombat)

5 Likes