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

Yay!! edX started… wait, What?!?

So the edX Python course started 14 hours late…

Anyways, I’m going through it, and one of the first main loop concepts talks about while loops… And the 3rd programming exercise on while loops says that they provide the variable end, use a while loop to calculate the sum of all the integers leading up to end (meaning, if end = 6, we expect 21 [1 + 2 + 3 + 4 + 5 + 6])…

Well, of course I already know a better way to do this… I just blogged about this particular thing a few days ago when talking about Project Euler #1 so I went to use that answer, and of course, it didn’t like it (it was looking for a while statement), so I cheated and wrote:

while True:
    break;

print(end * (end + 1) / 2)

which solved it…

I posted on the site as well that I was disappointed with that particular exercise, as I would think that MIT would actually have an exercise that taught you the proper way to solve the problem (meaning there are lots of good valid reasons to use a while statement, as the prior exercises had done, I felt that they shouldn’t use one that had a better solution than the one they wanted)…

But hey… onwords and upwards!

Home Sweet Home – Motley Crue
Never B Flat, Sometimes B Sharp, Always B Natural

edX, CodeWars, and CriticalRoleRenamer

So, I was supposed to be starting a Python course through edX, but apparently it’s starting late (was supposed to start about 12 hours ago, so I was going to give my first thoughts after reading the syllabus and such, but alas)… so that sounds like something I’ll have to do in the future…

Yesterday I started with CodeWars and completed 11 exercises (codewars calls them Katas), although 2 of them were simple parts of the sign up process. I’m going to try to do at least 2-3 a week, when not focusing on my own projects.

Speaking of my own projects, over the weekend, I wrote my first Python program for personal use. As I’ve stated before, I’m a gamer, and I’ve been trying to watch this show called Critical Role, which involves a group of voice actors playing Dungeons & Dragons. It’s actually a good show to see the game in action… But I don’t have 3 hours an episode to sit their and watch… but what I do have is that time when I’m walking, and driving to work, etc…

So I used a program called ClipGrab and downloaded the episodes from YouTube, and converted them to mp3 files, and then put them on my phone, so that my podcast player (Pocket Casts) would see them. Now I can listen (as admittedly, there isn’t a great need to ‘watch’ the program) while I’m exercising, or driving, etc. Plus Pocket Cast lets me increase the speed and jumps sound pauses (silence in the conversation), so that 3 hour episode only takes me about 2 hours…

But I digress…

When being downloaded and converted, the youtube naming convention (which admittedly is probably just the name the uploader used) isn’t the most consistent, or friendly, especially when you have things like Plex or Kodi for media serving content… so I wrote a python program that grabbed the episode number and title from the file name, and renamed the file… Taking it from, for example, “Enter Vasselheim – Critical Role RPG Show: Episode 16.mp3” to “Critical Role – S01E16 – Enter Vasselheim.mp3”, which is a common naming convention. The neat thing was, by using regex (again, another thing I’m learning), I was able to grab the title, and then episode number, but with code, helped normalize them… because sometimes they used a pipe (|) instead of a hyphen to separate, sometimes they had the colon after show, and sometimes not, and sometimes they had the show title uppercased… But I was able to rename the whole thing (which literally took less than a second of time to run) so that the episode title was standard Capital Case, and based on thetvdb.com, had the season numbers properly meshed out…

While its a simple program, all in all, i’m rather proud of it… My next step will be using it for other shows I listen to! You can see it in its current form on my GitHub page!

Rocky Mountain Way – Joe Walsh
Never B Flat, Sometimes B Sharp, Always B Natural

Project Euler #1

So I’ve been threatening to do this basically since day 1…

To aid in my programming learning, I’m doing various programming puzzles… via Project Euler, Exercism.io, Coding Bat and others…

But I think another part of the learning process is explaining things, or sometimes at least why I did what I did…

So I want to discuss my solutions… Instead of boring you here with code, I’ll link my GitHub Gist, as well as my JSFiddle solutions.

First of all, the problem:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

Now, first, the key word here is under. But we’ll get to that in a second.

At first, this looks like it can be solved with a simple loop, and really, for this exact problem, it can be, with little concern about cost. However, what if this was changed to 1 million, or 10 million, or 100 million…

Well, on most modern-day computers, looping through 1 to 1,000,000 takes about 2 seconds… 1 to 10,000,000 takes about 20 seconds… while 1 to 100,000,000 takes over 3 minutes… while 2 seconds is not horrendous, 20 seconds is bad, and 200 seconds is down right insufferable – at least from today’s web standards…

The solution for this is simple, and usually overlooked… Its taking a simple equation 3 times and your done.

Wait, what?!

All this is looking for is the sum of all multiples of 3 under 1000 (so 3+6+9+12…+996+999) and the sum of all multiples of 5 under 1000 (important to note since 1000 is divisible by 5, if we use it, we’ll get the wrong result) (so 5+10+15+20…+990+995). Now, if you remember your high school math, there was this equation that allows you to get the sum off all the consecutive integers that made up a number… so, for example, the sum of the consecutive integers for 10 is 1+2+3+4+5+6+7+8+9+10=55. The formula is n(n+1)/2… or 10(11)/2 >> 110/2 = 55. So having that, all we have to do is realize that the sum of 3+6+9+12 (quick example) = 30 is the same as (1+2+3+4)*3 >> 10 * 3…

Now, if that’s the case, then the sum of consecutive multiples of three would be 3 * ((n/3)(n/3+1) / 2), or in this case, we know that 999 is the last, and 333 is 1/3 of that, so 3 * 333 * 334 / 2 = 166833, and the same would be true of for 5 (5 * 199 * 200 / 2 = 99500). So we would think, at first glance, that our answer is 266333. However, we’d be wrong!

Wait, what?!

Well, we forgot one thing. In using this equation, every multiple of 15 (3×5) is being added in twice… once for the 3 side of it, and once for the five side of it… so all we have to do is subtract out one of them… so 15 * 66 * 67 / 2 = 33165… Now, if we take 166833 + 99500 - 33165 = 233168, which would be the exact same value our loop gives us…

So if we did this to get the results for 100,000,000 instead of 1000, we’d get our solution in under 1/100th of a second, vs 3 1/3 minutes, and at way fewer CPU cycles, which could be very important for some algorithms you write!

So that is my first foray into Project Euler, and the programming puzzles!

Young and Innocent -Elefante
Never B Flat, Sometimes B Sharp, Always B Natural

PyCharm… and my regex learning…

So I installed PyCharm today… I know I’m a VIM user, and I could use vim to write my python code very easily, but I’ve learned, both from past experience (i.e. an older job where I wrote PHP via VIM) and my current experience (i.e. my current job where I write Javascript/HTML 5 via VisualStudio) that there are some features that an IDE provides that are incredibly useful.

For me, 2 of the most useful features are the debugger (being able to see my python results immediately, and having clues about bad pythonic form) and being able to jump around based on a function (meaning if i’m making a function call, in the code, I can highlight the function call itself, click a key, and jump to the definition of the function… very useful!

I’m sure there are lots of different ways VIM can do things as well, but so far, I’m happy with PyCharm and will continue to use it!

On a different note, I’m working on learning regex. Regex is one of those things that have popped up since I took programming in college, and has really only been something seen as very minor in the peripheral view of coding… But i’m realizing its usefulness more and more, so I started working on it…

My first big breakthrough was on my gaming program i’m working on… Of course, when making a RPG Game manager, you are going to need dice rolled, and I know that python has the randint function to simply give me a single random die roll, but I wanted to be able to handle all kinds of die situations… one of them was for rolling stats for an NPC… so I would pass in ‘6@4d6!1’ into the die roll parser… (which basically means roll 4d6, drop the lowest result, and do that 6 times – giving me all 6 individual results)

In my javascript version, I was using this complex set of ifs to loop through each character in the string, to determine if there was an @ symbol, etc… Then I learned about grouping in regex, and was able to use ‘(\d*)@*(\d+)[Dd](\d+)([\+\-\*/!\^]*)(\d*)’ to group everything I needed in 1 statement… now I had groups that had the values I needed instead of trying to parse individual characters from the string…

I’ve seen the light!

Whole Lotta Love – Led Zepplin
Never B Flat, Sometimes B Sharp, Always B Natural

How I installed Ubuntu-Mate 16.04.1

The post is a walkthrough on how I installed Ubuntu-Mate 16.04.1… It wasn’t a very difficult process, but for those who are new to Linux, it may prove useful to you…

First, I downloaded the .iso image from Ubuntu Mate. I downloaded the 64-bit version, but I’m also using it on my Raspberry Pi 2, so I’ve downloaded it for that as well… I download it via torrent, to not suck up the paid for bandwidth by Ubuntu, plus I leave it available for a few days seeding to help the community… I followed the instructions here to create a microSD card to install with… (or on in the case of the Raspberry Pi)…

For the computer installations, I just plugged it in to my USB drive, and booted my computer up, and once in the graphical environment, I chose to Install Ubuntu-Mate…

Now, before I get into the nitty-gritty of the install choices and selections, let me tell you about my PC. I am currently using a Dell Inspiron 530 (Built in June 2008 – so a ‘Vista’ Machine that is 8 years old). It’s an Intel Core 2 Quad (Q6600) @ 2.4Ghz, with 8GB of Ram (max I can install). I added to it a Gigabit ethernet card, as well as an nVidia GeForce GTX650 video card. I also installed 2 Crucial 240GB SSDs that I use as my root and home folders. There is also an external USB BluRay drive. I will eventually build a new PC, but this works well for now!

But I digress…

In the install process, I selected to Download Updates, and to Install 3rd Party software by default. I then set up my hard drives by selected Something Else, and then configured my first SSD (sda) with 2 partitions, sda1 which is an 8GB swap partitions, and then the rest of that drive as an XFS partition (sda2) that mounts as the root (/) folder. I made the second drive an single XFS partition (sdb1) that mounts as the home folder (/home). I then set the boot loader to sda. I note this, because I swap these every new install (which basically means, when I install 16.10 in a few months, I will make sdb the swap and root partitions, and sda the home partition.) I do this to alleviate wear and tear on a single drive, as I do way more writing data to the home drive, than I do to the root partition.

Next, I select New York as my time zone, and English as my keyboard and language options. I then name my computer (musicalcoder), my username (chris), my password (password… just kidding) and then wait for the system to finish setting up my computer. After that, I reboot.

The first thing I do after rebooting is to update the video drivers. This is highly important for me, as I’m using a SEIKI 39″ 4K TV as my monitor, and it sets at 3840×2160, and the fonts are almost illegible until the nVidia driver is installed. After the driver install and reboot, my monitor looks beautiful! I do this, so that I have 4 distinct portions of my screen, and with Ubuntu-Mate, I’m able to use Ctrl-Alt-NumPad 1/3/7/9 to automatically move a window to the four quadrants of the screen, ‘maximized’ for that size (meaning each window is 1280×1024)

After that, I do my customizing! When Welcome comes up after my reboot, I turn on the Subscribe to Updates, so my Software Boutique always has the latest available! I set my background (which I’ll describe in a new post someday), and change my preferences to use Mutiny (which is a take on Ubuntu), since I have such a large monitor, that is ‘widescreen’, I like having the ‘task bar/icon bar’ on the left side of the screen. I then run my updates and get the latest versions of all my internal software.

That’s basically it. I’ll keep a ‘My Linux Rig’ post updated with everything I install, software-wise, but this is the actual installation of Ubuntu-Mate.

Thanks for stopping by and spending a moment of your precious time reading my musings, I do greatly appreciate it! I hope you find it useful! Leave any comments if you have questions about why I do what I do, or suggestions of what you would do differently!

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

My Linux Rig… Master Edition!

One of the blogs I follow is My Linux Rig, and one of the things I’ve wanted to do was write down (for future reference) my linux set up, mainly so that I know, in future update installs (16.10 and beyond) how my computer is configured…

I’m currently using Ubuntu-Mate 16.04.1. You can read about how I installed said Linux Distro in my How I installed Ubuntu-Mate 16.04.1 post.

I am using the following software… (this is what I install that differs from the default installation) [I’m breaking this down into 2 sections… The first section are the normal repository programs I installed (which I will create a script to install for future reinstalls)] {Last Updated 11/25/2016}
Ubuntu Mate Repository (uses apt install)

  • ttf-mscorefonts-installer
  • vim
  • python3
  • python-pip
  • git
  • hplip-gui

3rd Party (either by DownLoading directly, using the Software Boutique, or adding a PPA to install)

  • Chrome (SB)
  • PyCharm (DL)
  • Clipgrab (PPA)

My goal here is as I add more software, I’ll create new posts explaining what I installed and why I chose it, and then updating this list. I’ll also add any tools/scripts I create here as well (and up to my git location (either github or my own hosted gitlab)) so that I’ll eventually simply have 1 place that has all of the software I use and scripts I run, so that should I ever update or change computers/distros, I know what I have installed!

Also…

I noticed I had been closing my posts with Until Next Time… and I was fine with that, until I noticed that John Somnez (simpleprogrammer.com) did the same, and I realized that is where I had gotten it from… Not that I mind doing that, and I’m sure he wouldn’t mind if I did the same (although maybe he would… I didn’t ask) but I figured I wanted to come up with my own… Also, I had realized that I had started to title my posts with a lyrics or a song title, but decided to not do that, as I wanted the post title to mean more to new visitors (as well as analytics and such for future concerns), so I decided that I’ll close my posts with a song title!!!

We Said Hello Goodbye – Phil Collins

Never B Flat, Sometimes B Sharp, Always B Natural