Call Me… I mean… Collatz…

So – I was working on a Project Euler problem (#14 specifically), that deals with Collatz numbers. For those that don’t know, a Collatz number is a sequence by which you get a number to 1. If the number is even, you divide by 2, if its odd, you multiply by 3, and add 1, and the number is how many steps it takes to get to 1. So for example, 13, has a Collatz number of 10, as it takes 10 steps to get to 1 ( 13 > (3*13 +1) 40 > 20 > 10 > 5 > (3*5+1) 16 > 8 > 4 > 2 > 1). Naturally, as you get bigger numbers, it takes more steps to calculate the number of steps…

Now, not only do I do this on Project Euler, I also do this on the HackerRank site… Because while the problem is basically the same, they always throw a twist in… Using this example, Project Euler wants to know what number below 1 million has the most steps to get to 1… HackerRank on the other hand will have anywhere from 3 – 15 ‘test’ cases you need to solve, that follow certain rules, and your program only has so much time to run to pass. So for this problem, a single test case will contain anywhere from 1 to 10000 integers, that range anywhere from 1 to 5 million, and the program has 10 seconds to figure out what the maximum collatz sequence is for any given number. As an example, if the number give was 10, you would have to respond with 9 (since the number 9 has the most collatz sequences of any number between 1 and 10), and then if you are given 15, you would have to respond with 9 (since again, it has the most sequences to get to 1 between 1 and 15) and then you are given 20, and have to respond with 19 (technically 18 and 19 both have the same number of steps (22) to get to 1 – however the constraint dictates that if there are multiple ‘max’ paths, take the higher number – thus 19)… So this is what a simple test case of 3 numbers is… now handle 15 test cases, each with a different set of up to 10000 integers, ranging from 1 to 5 million… and do it in 10 seconds…

So that was the task…

So first – we realize we want to use memoization… What’s that you ask? In simple words, its caching calculations so you don’t have to do them again… Using our 13 example from above, what if, when we calculated 13, we stored each step… so that when 13 was done, we knew that 13 takes 10 steps, but we also know that 40 takes 9 steps, and 20 takes 8 steps, and 10 takes 7 steps, and 5 takes 6 steps, and 16 takes 5, 8 takes 4, 4 takes 3, 2 takes 2, and 1 is 1 step. By keeping this cached, we then are able to save lots of steps. For example, if we get to the number 80, we start our function, and step 1 takes us to 40… now instead of doing the other 9 steps, we look in our cache and see that 40 takes 9 steps, so then we can say in 2 steps, that 80 takes 10 steps… So by doing that and storing the values, we can then simply look up a given number and see how many steps it takes once they are all calculated…

So I created a recursive function that checks our cache, and if our number exists, it returned the # of steps, otherwise, it return the number of steps of either the even calculation or the odd calculation, depend on whether the number was even or odd… so I create that, and add the function for reading the input sequence, and let her rip… My little program goes through the first 2 test cases… and then starts to time out… because she is taking longer than 10 seconds to go through all of the thousands of possible numbers… hmm….

So then I think, well since I’m already using memoization, what if I prebuild all of the values from 1 to 5 million, so then all I need to do is simply look up the max value for a given number…

Except building the initial list from 1 to 5 million takes 13 seconds (on my computer)… hmm…

So now its time to start thinking outside the box…

So first, I think, well, if I start at 5 million and work my way down, lots of things will have been created by the time I got to them (as an example, when 5 million process, it process 2.5 million, which in turn processes 1.25 million, which in turn processes 625000, which processes 312500, etc, etc… So I change my prebuild to go from 5 million to 1 down… This actually knocks 2 seconds of my prebuild…

So… more efficiency… I think and realize that at some point building downward, I’ll reach a number that afterwards, every number below it has already been processed… So I add some variables to my Collatz function, and after processing, it tells me that moving downwards, 125001 is the last uncached number… so now, I only have to build down to 125001, thus saving me 125000 function calls, plus all of those recursive function calls…

However, this only knocked about 2 seconds off as well… so I’m sitting here at 8+ seconds… failing my test cases because it still takes, even with the cache build of 8 seconds, 14 seconds to process all 5 million numbers… So now what…

I start timing individual numbers… how long does it take to calc the 3 million? So I run that in quarter million increments to see how much these higher numbers take, and then noticed something… 3.75, 4, 4.25, 4.5, 4.75, and 5 million all return the same maximum… 3732423 at 579 steps. And then the light bulb goes off… If I ‘hardcode’ a list with that value, I don’t need to test any value above 3732423, because that is the max… that will save 1.27 million function calls + all of the additional recursive calls… So I write a function that sees if the value is greater than or equal to my list value, and if so, report the list value, otherwise, do the cacluations…

That one step shaved literally a second of my test time…

So, to make a long store short (too late), I ended up hand calculating (using my function), the top 50 #s… to understand how fast that made the program, when you see that #50 is the number 97, you realize that for all 4999903 numbers above 97 that could be in the list of integers, there are only 50 possible answers for the maximum collatz… which of course, means my program ran in under 1 second for all 10000 entries, no matter what they were…

So there, that is the story of how I didn’t use a function in the normal way, to gain some major efficiency in a program! If you want to see my program, you can see it on my github page here

Call Me – Blondie
My Way – Frank Sinatra
Never B Flat, Sometimes B Sharp, Always B Natural

J.A.C.U.

So – I’m going to name these Program Testing updates (or coding updates) JACU – for Just Another Coding Update… in honor of Blue Thunder’s JAFO… {google it}

As I start participating in any other sites, I’ll be logging information here… I’ve done reddit’s daily programming once or twice, and I might be signing up for stack exchange’s Code Golf soon… but I’ll have to review it as it seems like something I might not be interested in…

But for now… I digress…

So, we’ll just go down the list… Since my last update, here is where I stand…

    HackerRank:

  • I’m in the 4th Percentile in Algorithm’s – Haven’t done any of these since I completed the initial trek – focusing on…
  • Python: 1007.91 points (boosted by doing 1 partial contest), with a rank of 1491… I’ve completed Introduction, Basic Data Types, Strings, Sets, Math, Itertools, & Collections
  • Week of Code #23: I took part, and did some, but it was a bit beyond me… but still placed 2642nd/10494 [or top 25%]… I’ll probably try a few of their simpler contests to get a better feel, then do more of these!
    CodeWars:

  • 6 kyu (still) – although I’m about 90% finished with level 6
  • 91 Honor points
  • Honor Position # 19297 [83%]
    CheckIO.org:

  • Level 6: 177/235
  • Home: 110 pts – 53% completed… The last 2 are moderate and challenging rated, and moderate is re-writing min/max functions… for me, that is a couple of hours spent on this 1 test… so I’ll wait until I feel more comfortable with args. However, I’ve unlocked O’Reilly, Scientific, Elementary, & Electronic Station.
  • Elementary: 60 pts – 50% completed
    CodeEval:

  • I literally just confirmed my account – so I don’t have anything here yet… will start either later today or tomorrow!
    Project Euler:

  • I’ve finished the first 13 puzzles
  • using HackerRank’s ProjectEuler contest, I’m ranked 2925th/43394

So there is my progress since I last checked in with my coding challenges!

Until next time!

Eye of the Tiger – Survivor
Never B Flat, Sometimes B Sharp, Always B Natural

But I digress…

First – much respect to bloggers who blog on a regular basis… its very easy to let life get in the way of your ‘scheduled’ blogging time!

Now, on with the show!

I figured this would be a short topic on ‘What I learned this week’ – or for me, this month!

I seem to be the type of person that needs lists to get things done… so I’ve been researching Bullet Journal as well as following Kara Benz on BohoBerry regarding her Bullet Journal 101.

I ordered my notebook (which should be here tomorrow) and I’ll review the system, once I get it into place! (Which will probably be the rest of the week).

I’m also writing an update post on the various programming exercise sites I’ve been using, and what my status is on each site – just to track and inform!

This feels like a short one today – but I’ll be posting that programming update, so I’m okay with it!

The Show Must Go On – Queen
Never B Flat, Sometimes B Sharp, Always B Natural

So very disappointed…

So, I’ve been using HackerRank quite a bit recently, and as I’ve been delving deeper into the Python ‘domain’, I’ve been getting more and more disappointed by it. Not by python, but by the site and it’s ‘testing problems’.

By that I mean the problem explanations can be somewhat vague or even sparse in the explanation of what they are looking for, and the test cases are for the simplest answer, and while I don’t expect them to cover every test case (especially in the samples), 2 or 3 different ones that cover some of the variants to me are expected, as to me, this site is about the learning process.

And once you do solve it, they don’t do well at explaining why they did what they did, just that they did.

To me, it makes the learning process tedious…

But I digress…

But not really…

Because I was then like, well, its a new week, I’ll jump on edX and work on this weeks lessons for MITs Python course (as discussed here and here), so I log in, and what do I behold?!

Week 4
No new materials out this week. Catch up on your problem sets!

So no luck there either…

Luckily for me, I was listening to my current favorite python podcast Talk Python to Me… more specifically, this podcast about CheckIO.org, a python ‘game’ testing site. I’m liking this a lot as well, and currently, more so than HackerRank.

Tomorrow, I will post a programming update on where I rank on the various sites!

Take It to the Limit – The Eagles
Never B Flat, Sometimes B Sharp, Always B Natural

Prim and Proper…

So HackerRank ‘tricked’ me with an email, and I ended up gettung into their algorithm section before I felt I was ready for it. (Keep in mind, this was not a mean trick, or something dishonest or shady on their part – they just sent an email that said ‘You should try our Algorithm domain’, and like a dummy, I did.)

So to get the first badge under Algorithms, I had to complete something on graph theory (which I haven’t gone over since high school geometry – 30-ish years ago), and in a new language (python)… but I’m nothing if not dedicated, so I take the plunge and give it a try…

Here is the problem I had to work on:

Given a graph which consists of several edges connecting the nodes in it. It is required to find a subgraph of the given graph with the following properties:

  • The subgraph contains all the nodes present in the original graph.
  • The subgraph is of minimum overall weight (sum of all edges) among all such subgraphs.
  • It is also required that there is exactly one, exclusive path between any two nodes of the subgraph.

One specific node is fixed as the starting point of finding the subgraph. Find the total weight of such a subgraph (sum of all edges in the subgraph)

So, given that, I came up with a basic solution… First Solution and the thing about this is that it worked. The catch was for a test case that had 10000 vertices, it took almost 3 minutes to run, so the test case timed out, and it failed me!! 🙁

So, cracking my knuckles, and rising to the challenge, I employed my google-fu and began to track down some more efficient solutions. Since this discussed Prim in the title, I researched Prim and MST’s and came up with this algorithm to do this calculation, and after some more searching found a python version. After reviewing, I noticed that it wasn’t all that different from my solution, just that it used some python imports that I didn’t know about (mainly heapq and using dictionaries from collections) – apparently using the dictionary stuff from collections speeds that process up, and heapq speeds vertex jumping up significantly… my new solution basically did the same thing, but much more efficiently. Thus solving the problem in a few seconds.

What I take from this is that my original solution was right (and it worked, just not as efficient), and the only real changes the new solution made were to use python modules that were basically unknown to me to make what I was doing more efficient.

So all in all, I’m happy with the results.

I got me 3rd Percentile algorithm (which I’ve since increased to the 4th Percentile) – so I’ve got a ways to go in the Algorithms domain. But I’m going back to the python domain to finish it before i wander off into any of the other domains!

Under Pressure – David Bowie & Queen
Never B Flat, Sometimes B Sharp, Always B Natural

Programming Update

So as I stated in an earlier post, I’ve been taking the edX MITx 6.00.1x Intro to Computer Science and Programming w/ Python to aid in brushing up on modern computer science (I last attended school in the early 1990’s). At the moment, I’m just ‘auditing’ the course, but I think I’ll end up paying to get the certificate of verification…

So, during week 2, I made a mistake when turning in one of my assignments… I rushed to get it done, and did it in my IDE (PyCharm) so that I could test my results and such, I just copied my coded answer from PyCharm to the site’s code input… But because I was doing it in PyCharm, and rushing, I turned it in without any comments… shame on me! As I was peer reviewing others code – I felt stupid for rushing something that didn’t need rushed and not even leaving a basic comment… But, hopefully, I turn this into a learning process to slow down and comment…

I think part of it is I’m also using HackerRank and CodeWars and ProjectEuler to practice python with… and of course, none of the answers on these sites involve comments, so I tend to not use them…

I’m a little disappointed with myself regarding this, and I think I need to adjust my style regarding that… But it is a learning experience…

I’m also going to start listing my ‘scores’ with these sites ‘challenge’ sites, as I’ll have a way to measure my progress – and be publicly accountable (to anyone who actually reads)…

So, as of September 9th:

  • HackerRank: I have 375 points, 367 Hackos, and am ranked # 5531
  • CodeWars: I have 50 Honor, am at level 6 kyu (a decreasing scale – so lower is better), and have an Honor Position of # 28252
  • Project Euler: No ‘ranking or scoring’ system, I’ve completed problem #1 (I’ve been spending my time on HackerRank and CodeWars, as well as Reddit’s DailyProgrammer subreddit)
  • Reddit’s Daily Programmer – also non-ranking/scoring. I will be posting my results to my GitHub page. I’ve currently done challenge #281.

So again – I do this so I can update myself and see how I’m progressing!!! I’m going to work towards doing at least one item per week for each site, if not more (I might try at least 1 per day on some of them)…

But for now, that should cover it!

Play That Funky Music – Wild Cherry
Never B Flat, Sometimes B Sharp, Always B Natural

August 2016 Infodump!

So – something I felt wise to incorporate was a monthly update on what has transpired on my blog. Not so much links, as just how many posts, viewership, etc. This is based on Kara Bentz’ Boho Berry blog, which I follow due to her insights on using Bullet Journal. (Which I will blog about in my tools blog upcoming). But she does a monthly Traffic and Income Report (check out her August 2016 report here), and I thought this was a brilliant idea, so I’m stealing it and incorporating it into my blog. As this is a report on month 1, I don’t have any traffic, nor do I advertise or sell anything, so I don’t have any income… But I can still list what my goals were, how I did, and what my next month’s goals are. So here we go!

    To start with, my goals for August were:

  1. 9 blog posts
  2. 4 comments on other blogs

My # of blog posts goal is based on my desire to have 2 blog posts / week avg (104 per year) + 1 monthly update (12 more) + 1 Quarterly update (4 more) + 1 Annual Goal Review (done very near to Jan 1) which should put me at a minimum of 121 posts per year… This goal will help me towards making a meaningful push towards relevance. 9 comes from each Monday & Thursday in the month (which are my target posting days). Since I started the blog in late July (1 post simply announcing the blog), there was no reason to have a monthly review.

My comments on other blogs is based on my desire to help get my name (Musical Coder) out there, so I find other tech blogs, and try to make meaningful comments on them. That will also help links on other sites to get some people to my blog. When I create my tools blog, I will tell you what other blogs I pay attention to and ‘subscribe’ too.

So, now that I’ve stated what my goals were, lets see how I did:

So I can definitely say both goals met!

So with all of that out of the way, it’s time to announce my September goals!

  1. 10 blog posts (9 Mon/Thur posts + 1 monthly update (that would be this one))
  2. 8 comments on other blogs (I’m shooting for 2 a week avg, and once I consistently hit that, I’ll bump to 3 a week)

So there we go… goals to shoot for!

Truckin’ – Greatful Dead
Never B Flat, Sometimes B Sharp, Always B Natural

Really, I can have any() thing?!?

So, I’ve been using HackerRank, working my way up (at this writing, I’ve got 205 points in Python [309 Hackos points] and I’m ranked 10505), and one of the python items I just finished doing is on string validators…

These let you test if a string is just alpha, alphanumeric, just digits, is upper or is lower case…

But I digress…

The point of the exercise was given a string, determine if any of it was each of these (alpha, alphanumeric, digit, upper or lower), and print if each was true or not.

This is where, looking around online, I discovered the python any() command…

I was able to take this:

results = [False, False, False, False, False]
S = input().strip()
for c in S:
    if c.isalnum():
        results[0] = True
    if c.isalpha():
        results[1] = True
    if c.isdigit():
        results[2] = True
    if c.islower():
        results[3] = True
    if c.isupper():
        results[4] = True
print(*results, sep='\n')

which I thought was a decent solution prior to my discovery, into this:

S = input().strip()
print(any(s.isalnum() for s in S))
print(any(s.isalpha() for s in S))
print(any(s.isdigit() for s in S))
print(any(s.islower() for s in S))
print(any(s.isupper() for s in S))

which I thought was pretty useful… I’m liking python more and more every day I use it!

Anyway You Want It – Journey
Never B Flat, Sometimes B Sharp, Always B Natural