Alright, there’s this one algorithm that I’ve solved before. I’ve always found it to be a rather fun little exercise to work out. It popped into my head recently and I wanted to recollect how the logic of it went, but my Google-fu wasn’t so great. In the end, I didn’t find the algorithm problem statement but I’ve recollected it as best as I could from memory. If you know what the name of this challenge is I’d love to know what it’s called or if I’ve put it back together correctly. Ping me @Adron.So the story goes something like this. There once were some nations with a number of cities in each nation. Every citizen has access to every city and every city has a town center for all the citizens to enjoy. Recently the roads were damaged from a lack of maintenance work, ya know, like in real life. Meanwhile there was a revolution that led to catastrophic war that destroyed all the town centers in the nations. So now none of the cities have reachable town centers or functional working town centers anymore! The citizens of the world are angry at the nations and demand immediate fixes to their roads and town centers, with a priority on the town centers! The leaders have decided that the roads shall be repaired and have hired me (you) to assist!The nation has n cities, we’ll number 1 to n. The cities have two way roads, totalling m roads. A citizen has access to the town center if: their city contains a town center and their city has a road to travel from their city with a town center to another city with a town center.

The following is a map of one great nation of cities with currently impassable roads that must be repaired.

The cost of road repair is croad and to build a town center is ctown center. To start off with, you’re given q queries, where each query consists of a map of the nation and the value of croad and ctown center. For each of the queries the minimum cost of a town center accessible to all the citizens should be printed on a line.

The Input

The first line is an integer, q, denoting the number of queries. The subsequent lines describe the queries in a particular format. Each query is basically formatted like this:

• The first line of each set for a query will have four integers describing the number of cities n, the number of roads, m, and the cost to build a town center ctown center, and the cost to repair a road croad. Each integer is space seperated.
• Each line following that will have two integers describing a road for use between cities ui and vi. Each integer is space seperated.

The Output

Each query should have a result displayed that is the integer denoting the minimum cost of making town centers accessible to all the citizens.

The following example includes three queries (denoted by the first line having a 3). The subsequent queries then have a definition line of [6,4,2,1], [7,6,2,1], and [9,7,3,4] respectively. Then below those query definition lines are the road definitions between the cities, and respectively the town centers.

Sample Input

3
6 4 2 1
1 2
2 3
4 5
5 6
7 6 2 1
1 2
2 3
3 4
2 4
5 6
6 7
9 7 3 4
1 2
1 5
2 4
2 3
3 9
6 8

Alright, this one has a nubmer of elements to resolve. Here’s how I’ve worked through these three samples to get answers. I’ve drawn out the three examples so that there is a visual understanding of where the cities are also.

The first nation described by the section [6 4 2 1] would look something like this based on the road data of [1,2], [2,3], [4,5], and [5,6].

The next nation in section [7,6,2,1] would look like this with the road data of [1,2], [2,3], [3,4], [2,4], [5,6], and [6,7].

The last nation defined as [9,7,3,4] with road data of [1,2], [1,5], [2,4], [2,3], [3,9], and [6,8] looks like this.

Observations and Solutions

Dataset 1

Here’s how I worked these out. In the first example there are n=6 cities, m=4 roads connecting those cities, with the price of building a town center set at ctown center = 2 and the price to repair a road set at croad = 1. To meet the requirement of having access to a town center in every city, I could acheive this through several options, which I can then pick the cheapest from those options.

Rebuild the roads and build one town center in each connected part of the nation. In this scenario that would included 4 roads at 1 cost each, and one town center in each island of the nation at 2 cost each. The total would equal

roads x croad = total

4 x 1 = 4 to rebuild the roads.

cities x ctown center = total

2 x 2 = 4

total croad + total ctown center = combined total.

4 + 4 = 8

The next option would be to possible just rebuild town centers in each city and not rebuild the roads. This is quick to determine the cost of, as it just requires calculating the town center cost.

cities x ctown center = total

6 x 2 = 12

Out of the two solutions, the cheapest is to go with option one, rebuilding the roads and building one town center for access in each of the island segments of the nation.

Dataset 2

Alright, the next data set shows a city of 7 cities, among two islands, and 6 roads connecting those cities. Just a quick look, I’m guessing this one will work out the same as the first one. Working through I could build town centers in each city.

cities x ctown center = total

7 x 2 = 14

But I could also rebuild road [1,2], [2,4], and [2,3] on the left island with a single town center build, which would mean I need one town center and three roads for island one. The second I could build one town center in Tupelo and then rebuild road [5,6] and [6,7]. Total is two town centers and five roads.

Town centers would cost 2 x 2 = 4. The roads would be 5 x 1 = 5, adding 5 and 4 gives a total of 9 to rebuild enough so that all cities can regain access to a town center.

Dataset 3

This third dataset has three island areas. The first has 6 cities with 6 roads. The next island has 2 cities and 1 road, and then final island has one city with no roads. This last city, Solace, just needs a town center built to gain access to a town center.

For the island with two cities will need at least one town center. But with the prices increased let’s take a look to be sure. If I replace one town center, we’ll say in Tupelo, and rebuild the road that would be ctown center of 3 and road cost of 4 giving a total cost of 7. But if I rebuild a town center in San Francisco and Tupelo, that would only be 6. The previous plus this solution gives me three town centers at a cost of 5.

Now considering the last island segment I have 6 cities, and a number of roads that in some cases connect just one city. For the stretch that connects Legoland and York I could rebuild a town center in York, then the road [1,5] and [1,2] which would give Lenia, Legoland, and York direct access to a town center. The total would be 3 + 4 + 4 = 11 for a single town center and two roads. Then looking at things, the cheap scenario would be to rebuild a town center in Odessa and road [3,4] and [3,9] for another 11 total. Overall for this island of cities within the nation I’ll have 4 roads rebuilt with 2 town centers, for a total of 22 cost.

Adding that together for the entire nation of Dataset 3, that’s 22 + 5 + 3, giving a total cost for direct access to town centers of 30 cost.

The question now is, what’s the best algorithm to solve all of this. I’m going to make this algorithm a two parter, because this is such a whopper of a problem to lay out that I’ll give readers a chance

Sample Output

With each of these resolved, the output of the algorithm should print to stdout with the following results.

8
9
30

So…what’s your take on this one. If you build a solution, I’ll add it to my blog post in a few days. Let me know and we’ll sync up on it and talk about what an ideal solution might look like. Ping me @Adron.

Also, with any involvement in coding & hacks I’ll send a Thrashing Code sticker, kudos, and next beer is on me!

https://twitter.com/ThrashingCode/status/958799254901768192

I’ve got a few thoughts and ideas I’m going to write about here. These thoughts will connect the reality of evangelism and advocacy with the often imagined notions of what advocates and evangelists may do in their respective roles.

My History

I’ve spent a number of years working in what is commonly referred to as evangelism and advocacy in the technology industry. Most of it has been focused around software development, development practices, and related topics. In addition to the years I’ve worked around evangelism and advocacy I’ve also done a fair bit of it on my own for my own purposes around community development, conferences, and other related things. The companies I’ve worked with as advocate or evangelist include; Basho, Tier 3 (now Century Link Cloud), Home Depot, and others.

More Context

There tend to be two key groups that these roles end up under: sales or somewhere near engineering. When it is under sales the evangelism word is often associated with the role along with other problematic issues. When the role is within or somewhere near engineering, the role is often found to be more respected and focused. In the end, both titles and roles under either group tend to be found doing similar work.

Reality Versus Perception

But this is where I want to dive into the realistic roles of evangelism and advocacy versus the unrealistic roles I’ve seen posted and asked for. Let’s talk about some of the common things I’ve seen that pose a seriously broken reality and are red flags. I’ll break these out to perceptions and then realities in the following. Toward the end, don’t worry, I’ll provide some solutions in case you are trying to hire this type of professional.

Traveling

Perception: I often see descriptions where 50% travel is expected (or more), along with a host of other things like “must be able to write node.js, go, python and contribute to open source project and… and… and…”. To compound matters I often see where these roles need to communicate between departments and act as some mythical type of glue so that engineering can somehow get information from the customers that advocates or evangelists talk to. This is, to put it nicely, a truly odd notion when matched to travel, contributions, and a host of other requirements.

Reality: The reality is this is a pick one scenario. If you want someone to travel and speak 50% of the time the other 50% of the time isn’t going to be writing node.js, go, python and contributing to open source and doing technical meetings and leading groups or something. It’s going to be 50% travel, 20% planning, probably 20% resting and recuperating, and then maybe 10% doing something technical like coding or reading up on the latest technologies. The hard reality is these are not gentle task switches, but brash, hard, brutal, brain shattering task switches that nobody ever accomplishes them efficiently in any way. The fact is people people will actively or simply be forced to drop the ball when the perception is force pushed onto the reality of what will or can be done.

Scott Hanselman said it really well.

Remember that NOT answering an email is always an option. Dropping the ball is sometimes appropriate, especially for your mental health.

— Scott Hanselman (@shanselman) April 7, 2017

Do it. Drop the ball today.

— Scott Hanselman (@shanselman) April 7, 2017

Solution: If you want someone to travel, don’t expect them to keep up with technology. If you want someone to keep up with technology, don’t expect them to travel an excessive amount. Traveling 10–20% of the time is somewhat reasonable when combined with expectations of technical blog writing, coding, contributions, and other involvement. Maintaining a reputable brand for one’s self (i.e. ensuring people trust your code, contributions, and writing) is extremely important. Keeping the travel, code, contributions, and related efforts balanced appropriately with realistic expectations is the only way to maintain a solid self brand and reputation.

Writing

Perception: Publishing written articles via blogs and other mediums is by no means an easy thing to do. It takes a ton of work to write truly good, effective, and useful blog entries. Most people don’t even want to write things outside of the things they have to. Expecting an advocate to evangelize via blog posts and written word, with expectations around numerous blog posts as if it takes no effort is dangerous and sets an extremely bad precedent. but there it is, often in job descriptions and sometimes even with absurd requirements like; “write 4–6 blog entries per month on programming topics deep diving into X”.

Reality: There is no way anybody is going to deliver 4–6 blog entries while travelling, coding, contributing, and more. That’s just complete, utter, nonsense that is completely out of touch with reality. If you’re looking for a developer advocate or technical evangelist don’t put such notions in the post, it’s a massive red flag that says, “unrealistic expectations, stay away”. In all seriousness, if an advocate or evangelist writes a solid blog entry with code, repository, and other elements that actually work, they’d be lucky to get 1–2 blog entries of this level per month mixed with all the other things to stay relevant. To summarize, blog entries are a ridiculous amount of work, editing, and effort to do well.

Solution: Want to read and see the rhythm of really well done articles and tech material, give the Codeship or Digital Ocean blogs a read. The best thing is to have writing as a peripheral element that can be used in multiple ways. Write documentation, have someone mold that into a useful blog entry. Then flip it around and make blog entries into documentation. Whatever the case make it so that there is multiple people working to fold ideas and thoughts into blog material. Individuals slammed with all the blogging almost never works out, and if it appears to work out, it’s probably decimating other important activities.

Speaking

Perception: We’ll line you up with plenty of speaking opportunities (says super hip and awesome company) and then you just show up and use your personality to present the technology we build! It’ll be super easy!

Reality: Oh hell no! Don’t sign up advocates and evangelists to speak. Otherwise you don’t have an advocate or evangelist, you have some mutant shill infomercial salesperson (I mean, unless I suppose you want a sham wow)! Hire a salesperson, or infomercial spokesperson if you need that, don’t conflate a technical advocate for this role! That’s not going to build honest, high integrity, positive reputation or brand recognition for the company or the individual. This is a lose lose practice to presenting at conferences, meetups, and related events.

Solution: Advocates, or evangelists need to be actively involved in determining where they travel, where they speak, and what element and aspects of the technology they’re advocating at those presentations. Provide options, suggestions, or even ideas but don’t force these, offer a path for them to determine these efforts. This provides the most effective, authentic, best brand, high integrity, solid, reliable, trustworthy, and most excellent presentations among these roles!

Other Solutions

There are certain other things that come up when I’m a contributor on projects with regard to advocates and evangelists. It boils down to a really simple focal point, are they working on, building samples, contributing to projects, and generally helping me get done what I’m trying to build? Whenever I see Google, AWS, Microsoft, HashiCorp, New Relic, other open source projects, companies, or other organizations’ advocates I immediately pay attention when they’re building or working on projects that reflect what is getting done and needs to be done in industry. In the future I intend to research and put together a list of effective practices around these roles from two perspectives; that of the evangelist or advocate and that of the community member working with the evangelist or advocate.

Until later, cheers, and good luck hiring evangelist and advocates! It’s a challenge!

I’ve been practicing up on some algorithms with Go per my Resolutions for 2018 item “Write More Code, Build Patterns, Algorithms”. Here’s a few of the ones I took a quick review of, from the algorithm perspective.

The first algorithm I took a dive into is a big sum problem. Part of the reason is I wanted a refresher on how Go deals with various integer data types. Easier to set it to memory if I play around with the data types versus just simply reading up on the specifics.

Big Sum!

Imagine being given an array of integers of size N. The task is to get the sum of the elements of the array and print each sum out. The added caveat is that each of the integers may be large.

Input & Sample Input

The first line of the input consists of an integer N. The next line contains N space-seperated integers in the array. Sample input would look something like this.

3
1230983459 90232478345 2349432014

or

6
982734503 2938563459 100032400 9202345873 701346892 2345010900

Output & Sample Output

Print a single value equal to the sum of the elements in the array.

Sample output for the first example input.

93812893818

Sample output for the second example input.

16270034027

The Solution

Alright. Down to the task. The first thing I’ll need is to setup getting the input into the application, a little standard input. For that I’ll need to use the standard Go “fmt” library. In my main.go file I go ahead and create the start of the code.

package main

import (
    "fmt"
)

Next I’ll write up the input for the index count, which is the first value passed in.

func main() {
    var arraySizeCount int64

    _, err := fmt.Scanf("%d", &arraySizeCount)
}

Now that I know the size of the array of data I’ll be scraping up, I’ll setup the array to put that data in. I’ll add the next line of code just below the previous additions.

data := make([]int64, arraySizeCount)

With data now setup as the array I’ll need, I can step through the data that is retreived from input and put values in the array.

for i := range data {
    _, err = fmt.Scanf("%d", &data[i])
}

Next I’ll need a variable for the total sum of the values in the array. I’ll create that and then also step through the range of values in the array, adding them while I go.

var totalSum int64 = 0

for _, v := range data {
    totalSum += v
}

The final step involves an error catch, I’ll print out the error, then display the value of the sum. That solves the algorithm in a short bit of code.

if err != nil {
    fmt.Print(err)
}

fmt.Printf("%d\n", totalSum)

All of the code together only amounts to 29 lines of code. One additional thing I could do, that might make it more readable is to break out the input phase and output phase of the function. The code currently looks like this.

package main

import (
    "fmt"
)

func main() {
    var arraySizeCount int64

    _, err := fmt.Scanf("%d", &arraySizeCount)

    data := make([]int64, arraySizeCount)

    for i := range data {
        _, err = fmt.Scanf("%d", &data[i])
    }

    var totalSum int64 = 0

    for _, v := range data {
        totalSum += v
    }

    if err != nil {
        fmt.Print(err)
    }

    fmt.Printf("%d\n", totalSum)
}

A Refactoring?

As I start to refactor this code, as I mentioned, the existing code is only 29 lines of code. But I’m going to break it out into two functions; I’ll call one SumTotal and one DataRead. My SumTotal function will take a list of 64 bit integer data types and return a single total 64 bit integer.

func SumTotal(list []int64) int64 {
    var totalSum int64 = 0

    for _, v := range list {
        totalSum += v
    }

    return totalSum
}

The DataRead function will have a 64 integer paramter and an error result. The function definition will look like func DataRead() ([]int64, error) {}. The function itself I’ll have take in and get the input and also have it build the array. I get to work on that and pull the functionality out of the existing 29 lines of code into the function, which I end up with a function that looks like this.

func DataRead() ([]int64, error) {
    var length int64

    _, err := fmt.Scanf("%d", &length)
    if err != nil {
        return nil, err
    }

    data := make([]int64, length)

    for i := range data {
        _, err := fmt.Scanf("%d", &data[i])
        if err != nil {
            return nil, err
        }
    }

    return data, nil
}

Now I just go ahead and wipe out what is in the main function of the code and replace it with the few lines to call the respective input, and lass it to the respective processor and finalize that by printing out the results.

func main() {
    data, err := DataRead()
    if err != nil {
        fmt.Print(err)
    }

    fmt.Printf("%d\n", SumTotal(data))
}

Now the whole file of code looks like this, which leaves one with a few questions.

package main

import (
    "fmt"
)

func main() {
    data, err := DataRead()
    if err != nil {
        fmt.Print(err)
    }

    fmt.Printf("%d\n", SumTotal(data))
}

func SumTotal(list []int64) int64 {
    var totalSum int64 = 0

    for _, v := range list {
        totalSum += v
    }

    return totalSum
}

func DataRead() ([]int64, error) {
    var length int64

    _, err := fmt.Scanf("%d", &length)
    if err != nil {
        return nil, err
    }

    data := make([]int64, length)

    for i := range data {
        _, err := fmt.Scanf("%d", &data[i])
        if err != nil {
            return nil, err
        }
    }

    return data, nil
}

Both of the solutions work and provide the desired result. However, one is refactored into input and output functions, with the main function minimized. In this particular situation does it even matter? One might say it’s good to practice refactoring, but in the end did the refactored solution end up better in some way? I could argue that the latter is easier to read. I could say that the first solution was easier to read, since it was so much shorter. The argument could fall either way, but in the end it’s a quick, simple, introductory algorithm and some simple refactoring.

If you’ve got a quick second, ping me @Adron if you’ve got suggestions, other refactoring, or other thoughts about this algorithm. I’m always open to a critical editorialization.

In the meantime, happy hacking!

References: The repository for this code I’ve written here is available on Github @ algorithms-101-a-big-sum

I thought. I pondered. I added conjecture and reasoning, some oompf, and just went with it. I usually don’t do resolutions. I usually don’t even really do anything for new years except maybe use it as an excuse to watch a good movie and see a fire works show or two. This year I’ve decided I’m going with some resolutions.

• Beer: Live a little, treat yo’ self, and hit up at least two happy hours or other meets with friends and coder/tech/hacker crews per month. The Ballard Happy Hour has been a good one so far, and of course the exceptional Seattle Scalability Group I help organize is pretty epic unto itself. The latter often having free beer post meet up. Both meets are good conversations, great beer, and a great chance to just unwind with smart folk. Goal: Attend two meets per month.
• Communication Improvements: Find a new and more efficient way to increase the throughput of my follow ups with everybody. Whether by email, phone, or whatever it might be. Goal: Increase rate of follow ups by 15%.
• Cell Phone Disruption: Decrease my actual cell phone usage making *phone calls* even further. Regain the privacy, personal time, and focus time that one traditionally had before the time of cell phones invading every corner of existence. How I do this I’m not entirely sure, but I’m betting when I figure it out I’ll blog it. Goal: Make it so that I don’t look at or need my cell phone for anything more than 1 phone call per week on average (vid chat, etc, excluded).
• Write More Code, Build Patterns & Algorithms: I want to review and go back to some of the coding roots that I haven’t hit upon in a long time. It’s odd, when coding day in and day out one tends to not touch upon a lot of the fundamental basics. I want to start writing about and reviewing this again, keep it fresh in mind so it’s always easy to reach into my mind and explain how things work to who may ask. Goal: Write 0.5 blog entry per week on coding algorithms, patterns, or related core coding concepts and skills.
• Reinitiate in Industry: Kick back off and give some dedicated presentations at meet ups and conferences. Goal: Give at least 4–6 talks that are dedicated, focused, mid-level or advanced topics following my standards for speaking, follow up, and improving.
• Make OSS Workable for Me: Get the OSS projects I’ve started in the last 2–3 years into a more workable state, insure others can take them, build, and get running without issue. It’s been a few years since I’ve worked on and helped with any OSS projects that are actually used, it’s a bummer and I’m going to resolve that this year. Goal: Get two projects into a workable state so others can use them and I can use them for their intended purpose and for teaching and blogging purposes.
• Get More Active: Take more bike rides, train trips, and spend more time with friends and family in Portland. Goal 1: Spend at least 3–4 days at Pedalpalooza this year, and take at least 4 trips (1 per quarter at minimum) of about ~2 days each in 2018. Goal 2: Participate in at least 1 group rides per quarter in Seattle.
• Self Health: Take more time for myself, allocate appropriate me time to make sure I can keep my sanity. Goal: Write, ponder, introspect, and watch the world turn more often. Blog on the park, lake, boat, train, or place and moment of writing, pondering, introspecting, and watching the world turn by writing about it.
• Write More: I’ve fallen off from the levels I like to blog and write about things. I like to write to introspect, to learn, and show, share, and teach. I want to return and increase beyond the level in which I wrote previously. Following the medium use of mediums I’ve previously outlined. Goal: See “Self Health” as this goal interlines with that goal.
• Improve Local Communities: Stop getting involved in Internet politics I can’t improve. Get more focused in local politics. Help more people in Seattle, help more people however I can. Help in the fight for better and more housing for all people. Help in the fight for better and more advanced and modern transportation options in Seattle, Portland, and wherever I can. Goal 1: Join Cascade Bicycle Club and the monthly urbanist meets. Goal 2: Keep up with the respective communities ala Bike Portland, The Urbanist, Seattle Transit Blog, Seattle Bike Blog, WA Bikes, and Cascade Bicycle Club.

Now for the bets right? I’ve got 11 goals. Will I meet them all? Will I get 50% of them accomplished? What’s the probability I can knock all of this out? Right now as I write this resolution I’m taking a wild guess of about 93% chance I can knock out all of these goals. Even if each quarter is off kilter a bit, I could recover in a subsequent quarter. Here’s to 2018, actually accomplishing the resolutions, and all that jazz.

Cheers!