Learning to Code: Week 7 – Project Euler

6/23/16

Using our collaborative approach to learning, you’ll be introduced to Javascript, the programming language of the internet! This is a great opportunity to experience a collaborative, hands-on approach to learning.

By the end of the evening you’ll understand the basics of Javascript, have written a bunch of Javascript yourself and be equipped with resources to continue learning beyond our workshop.

  • The workshop ended up being horrible and I learned nothing new. Here is example of something we worked through arbitrarily in a group: https://github.com/greatersum/intro-to-programming-using-javascript-koans/blob/master/koans/AboutNumbers.js
  • We’d just change “FILL_ME_IN” to make the code work, but I didn’t see the point at all. This was supposed to be an introduction class, but nothing was explained. Just two hours of math/coding problems. If you were unfamiliar with coding at all your head would’ve exploded. No basics were covered and we never actually wrote a single line of JS. Just a lot of 1 + 1 = ?
  • You can see the actually exercises they used here: https://github.com/greatersum/intro-to-programming-using-javascript-koans/blob/master/koans/AboutNumbers.js
  • I looked up Javascript Koans and they seem to be a common thing, but I personally didn’t see how it served as an introduction to JS unless you were already really proficient in another language. But if you were good in another language you wouldn’t need to do these Koan exercises anyway!

6/24/16

Shawn linked me this article on Twitter.

I found this part really interesting:

Call your shot. Before you run code, predict out loud exactly what will happen.

6/25/16

6/26/16

  • Worked a little more on the BASIC FORMATTING challenge.
  • Decided to scrap trying to read the input as a text file as C doesn’t make it very easy to do it as a file with line breaks and I kept getting Segmentation Faults (but I could get it to read the file and print it out, THEN it would break).
  • I just put the input string directly into the problem itself now and will work from there. I am not sure how to get the first characters up to the letter V to be deleted and then work from there…
  • This is as far as I got. It can print out the input properly but then it segmentation faults.
  • https://gist.github.com/anonymous/25d1ed63c5d0875330737bd24899c6d3

6/27/16

  • Only got a chance to read more of Grokking Algorithms chapter 7.
  • Dijkstra’s algorithm in python and how to do negative weighted graphs using the Bellman-Ford algorithm.

6/28/16

First day of experimenting with doing coding work first thing in the morning before work. 😴

CS50 Section Videos:

  • Dynamic Memory Allocation
    • Hard to wrap my head around this concept. How do people keep track of this?
    • Memory must be freed at the end.
    • Never free memory twice.
  • Structures
    • This is really cool.
    • They need a semicolon at the end
    • Is this similar to linked lists in the Python examples I’ve seen?
  • Defining Custom Types
    • aka Typedef
    • Can rename types like instead of char* call it string to make it easier.
    • You can also define structs INSIDE of typedef!
  • Recursion
    • Another video again. This one talked about the Base Case and Recursive case finally. I found that out in the Algorithm book and knowing that you need a base case to stop a recursive call really helped visualize how to use recursive functions.
    • The Collatz Conjecture is talked about. The code I came up with wasn’t as elegant as theirs. Didn’t think of not using a step counter!)
  • Call Stack
    • Frame for the most recently called stack is always on the top.
    • When a new function is called it is pushed onto the stack.
    • The functions below the top one are paused.
    • Once a function is finished it is popped off the stack.
    • It reminds me a lot of the cup pyramid speed people that take a stack of cups and build them up and then collapse them.

image17

  • At work I decided to dive into some Project Euler problems and just do them by hand written out. I will code them up later today if I get a chance.

Project Euler

Project Euler Problem 3 asks for the largest prime factor of the number 600851475143. We consider first a function to find all the prime factors of any number. A simple way, not necessarily the best way, but sufficient for this task and for many others, works in two steps: first remove factors of 2 while the number is even, then perform trial division by the odd numbers starting from 3 until the factorization is complete.

    • Just dividing by odds numbers is a lot easier than calling a function to find the next prime number and using that. Not sure if it’s faster though…

6/29/16

CS50 Problem Set 4 Videos

  • File I/O
  • Valgrind
    • Program to check for memory leaks and errors.
  • Have been contemplating getting a coding coach/tutor/mentor person. https://www.codementor.io/ looks like an interesting site to try. Maybe someone to talk to live once a week and get feedback on code I’ve written in terms of better practices/techniques.

Problem Set 4

  • BMP, GIF, JPEG, and PNG file formats.
    • How many different colors does each format support?
    • Which of the formats supports animation?
    • What’s the difference between lossy and lossless compression?
    • Which of these formats is lossy-compressed?
  • Article: http://cdn.cs50.net/2015/fall/psets/4/garfinkel.pdf
    • What happens, technically speaking, when a file is deleted on a FAT file system?
    • What can someone like you do to ensure (with high probability) that files you delete cannot be recovered?
  • Whodunit

Project Euler Problem 1

  • Worked on coding up problem 1 and 2. For problem 1 I wasn’t getting the expected answer and this was my code.

  • I ran the debugger and it instantly became clear why. (1 should be i, duh). After that it still wasn’t correct and I realized I didn’t quite read the problem correctly. It should only calculate values BELOW 1000 not including it.
  • Also sum = sum + i can be rewritten as sum += i.
  • Click here for final code for problem 1

  • Solution = 233168
  • Learned about the conditional operator or ternary operator in C. I saw it on Stack Overflow and it made no sense so I looked up the answer on…Stack Overflow of course.
    • http://stackoverflow.com/questions/795286/what-does-do-in-c
    • This is commonly referred to as the conditional operator, and when used like this:
      • condition ? result_if_true : result_if_false
    • … if the condition evaluates to true, the expression evaluates to result_if_true, otherwise it evaluates to result_if_false.
    • This is pretty cool and much shorter to write!

Project Euler Problem 2

  • Ran into a couple of issues coding this one up. First I was thinking about it incorrectly to start with. It was fibonacci numbers up to 4 million not up to the 4 millionth fibonacci number (which would be massive).
  • After I fixed that I ran into another issue where my program should’ve worked, but just hung completely.
  • I ran the debugger and everything seemed to sum okay when rolling through a few iterations of the loop.
  • I thought that maybe my data types weren’t big enough and changed my ints to long longs and tried again, but it still hangs (that wasn’t the issue at all).
    • It works for 10 steps through the loop.
    • At 100 steps the CPU on the IDE goes to max and just hangs.
    • Not sure what I can do here at all.
  • Using this calculator the numbers cross 4mil after the 34th one. So I set my loop to only check up to that number and it worked!
  • How would I overcome my program hanging in the future though? Need something with more memory or just need more time to wait? Could it be because my function was recursive and the stack just got super full?
  • Click here for final code for Problem 2
  • Solution = 4613732

 

Project Euler Problem 3

  • I just came to the realization that attempting to write a function that can calculate the next prime number from any given number would be…well to say the least “really complex.” I don’t know a way to write it that wouldn’t use straight up brute force, but doing a little googling I do see there are algorithms that do it faster.
  • https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes (the animation here is pretty sweet)
  • Most likely for this problem I will stick the to the “divide by odds” strategy and not mess with that higher level math problem solving. Maybe someone wrote a library that does this already?
  • I did find this solution to finding the next prime number which makes perfect sense, but is brute force checking. http://stackoverflow.com/questions/27303306/finding-next-prime-number-of-x-in-c
  • I may try to use it and see what happens.