In an effort to make these weekly, I present a new programming challenge.

The challenge this week is to compress some text using a prefix code. Prefix codes associate each letter with a given bit string, such that no encoded bitstring is the prefix of any other. These bit strings are then concatenated into one long integer which is separated into bytes for ease of reading. These bytes can be represented as hex values as well. The provided prefix encoding is as follows:

Challenge

Your program should accept a lowercase string (including the ~ character), and should output the formatted compressed bit string in binary and hex. Your final byte should be 0 padded so that it has 8 bits as required. For your convenience, here is the above table in a text file for easy read-in.

Example

Here is an example:

$> tildes ~comp
10010100 10010010 01011010 10111001 00000010 11000100 00110000 10100000
94 92 5A B9 02 C4 30 A0

Bonuses

1. Print the data compression ratio for a given compression, assuming the original input was encoded in 8 bit ASCII (one byte per character).
   2. Output the ASCII string corresponding to the encoded byte string in addition to the above outputs.
2. @onyxleopard points out that many bytes won't actually be valid ASCII. Instead, do as they suggested and treat each byte as an ordinal value and print it as if encoded as UTF-8.
3. An input prefixed by 'D' should be interpreted as an already compressed string using this encoding, and should be decompressed (by inverting the above procedure).

Previous Challenges (I am aware of prior existing ones, but it is hard to collect them as they were irregular. Thus I list last week's challenge as 'Week 1')
Week 1

Its been a while since we did one of these, which is a shame.

Create a program that takes is an input of the type: "d6 + 3" or "2d20 - 5", and return a valid roll.
The result should display both the actual rolls as well as the final result. The program should accept any valid roll of the type 'xdx'
Bonuses:

• Multiplication "d6 * 3"
• Division "d12 / 6"
• Polish notation "4d6 * (5d4 - 3)"

As a side note, it would be really cool if weekly programming challenges became a thing

Previous challenges

It's time for another coding challenge!

This challenge isn't mine, it's this challenge (year 5, season 3, challenge 3) by ČVUT FIKS.

The task is to design a network communication protocol. You're sending large amount of bits over the network. The problem is that network is not perfect and the message sometimes arrives corrupted. Design a network protocol, that will guarantee that the decoded message will be exactly same as the message that was encoded.

MESSAGE => (encoding) => message corrupted => (decoding) => MESSAGE

Corruption

Transmitting the message might corrupt it and introduce errors. Each error in a message (there might be more than one error in a single message) will flip all following bits of the message.

Example:

011101 => 011|010

(| is place where an error occured).

There might be more than one error in a message, but there are some rules:

• Minimum distance between two errors in a single message is k

• Number of bits between two errors is always odd number

According to these rules, describe a communication protocol, that will encode a message, and later decode message with errors.

Bonus

• Guarantee your protocol will work always - even when errors are as common as possible

• Try to make the protocol as short as possible.

Hello everyone! It has been a while since last programming challenge, it's time for another one!

This week's goal would be to build your own interpreter.

Interpreter is program that receives input and executes it. For example Python is interpreted language, meaning you are actually writing instructions for the interpreter, which does the magic.

Probably the easiest interpereter to write is Brainfuck interpreter. If someone here doesn't know, Brainfuck is programming language, which contains following instructions: ,.<>[]-+. Other characters are ignored. It has memory in form of array of integers. At the start, pointer that points to one specific memory cell points to cell 0. We can use < to move pointer to left (decrement) and > to move pointer to right (increment). . can be used to print value of cell the pointer is currently pointing to (ascii). , can be used to read one character from stdin and write it to memory. [ is beggining of loop and ] is end of loop. Loops can be nested. Loop is terminated when we reach ] character and current value in memory is equal to 0. - can be used to decrement value in memory by 1 and + can be used to increment value in memory by 1. Here's Hello World:

++++++++++[>+++++++>++++++++++>+++>+<<<<
-]>++.>+.+++++++..+++.>++.<<++++++++++++
+++.>.+++.------.--------.>+.>.

People with nothing to do today can attemp to make an interpreter for the Taxi programming language.

You can even make your own language! There are no limits for this challenge.

Preface

Conceptual models in programming are essential for being able to reason about problems. We see this through code all the time, with implementation details hidden away behind abstractions like functions and objects so that we can ignore the cumbersome details and focus only on the details that matter. Without these abstractions and conceptual models, we might find ourselves overwhelmed by the size and complexity of the problem we’re facing. Of these conceptual models, one of the most easily neglected is that of data and object structure.

Data Types Galore

Possibly one of the most overwhelming aspects of conceptualizing data and object structure is the sheer breadth of data types available. Depending on the programming language you’re working with, you may find that you have more than several dozens of object classes already defined as part of the language’s core; primitives like booleans, ints, unsigned ints, floats, doubles, longs, strings, chars, and possibly others; arrays that can contain any of the objects or primitives, and even other arrays; and several other data structures like queues, vectors, and mixed-type collections, among others.

With so many types of data, it’s incredibly easy to lose track in a sea of type declarations and find yourself confused and unsure of where to go.

Tree’s Company

Let’s start by trying to make these data types a little less overwhelming. Rather than thinking strictly of types, let’s classify them. We can group all data types into one of three basic classifications:

1. Objects, which contain key/value pairs. For example, an object property that stores a string.
2. Arrays, which contain some arbitrary number of values.
3. Primitives, which contain nothing. They’re simply a “flat” data value.

We can also make a couple of additional notes. First, arrays and objects are very similar; both contain references to internal data, but the way that data is referenced differs. In particular, objects have named keys while arrays have numeric, zero-indexed keys. In a sense, arrays are a special case of objects where the keys are more strictly typed. From this, we can condense the classifications of objects and arrays into the more general “container” classification.

With that in mind, we now have the following classifications:

1. Containers.
2. Primitives.

We can now generally state that containers may contain other containers and primitives, and primitives may not contain anything. In other words, all data structures are a composition of containers and/or primitives, where containers may accept containers and/or primitives and primitives may not accept anything. More experienced programmers should notice something very familiar about this description--we’re basically describing a tree structure! Primitive types and empty containers act as the leaves in a tree, whereas objects and arrays act as the nodes.

Trees Help You Breathe

Okay, great. So what’s the big deal, anyway? We’ve now traded a bunch of concrete data types that we can actually think about and abstracted them away into this nebulous mess of containers and primitives. What do we get out of this?

A common mistake many programmers make is planning their data types out from the very beginning. Rather than planning out an abstraction for their data and object architecture, it’s easy to immediately find yourself focusing too much on the concrete implementation details.

Imagine, for example, modeling a user account for an online payment system. A common feature to include is the ability to store payment information for auto-pay, and payment methods typically take the form of some combination of credit/debit cards and bank accounts. If we focus on implementation details from the beginning, then we may find ourselves with something like this in a first iteration:

UserAccount: {
    username: String,
    password: String,
    payment_methods: PaymentMethod[]
}

PaymentMethod: {
    account_name: String,
    account_type: Enum,
    account_holder: String,
    number: String,
    routing_number: String?,
    cvv: String?,
    expiration_date: DateString?
}

We then find ourselves realizing that PaymentMethod is an unnecessary mess of optional values and needing to refactor it. Odds are we would break it off immediately into separate account types and make a note that they both implement some interface. We may also find that, as a result, remodeling the PaymentMethod could result in the need to remodel the UserAccount. For more deeply nested data structures, a single change deeper within the structure could result in those changes cascading all the way to the top-level object. If we have multiple objects, then these changes could propagate to them as well. And what if we decide a type needs to be changed, like deciding that our expiration date needs to be some sort of date object? Or what if we decide that we want to modify our property names? We’re then stuck having to update these definitions as we go along. What if we decide that we don't want an interface for different payment method types after all and instead want separate collections for each type? Then including the interface consideration will have proven to be a waste of time. The end result is that before we’ve even touched a single line of code, we’ve already found ourselves stuck with a bunch of technical debt, and we’re only in our initial planning stages!

To alleviate these kinds of problems, it’s far better to just ignore the implementation details. By doing so, we may find ourselves with something like this:

UserAccount: {
    Username,
    Password,
    PaymentMethods
}

PaymentMethods: // TODO: Decide on this container’s structure.

CardAccount: {
    AccountName,
    CardHolder,
    CardNumber,
    CVV,
    ExpirationDate,
    CardType
}

BankAccount: {
    AccountName,
    AccountNumber,
    RoutingNumber,
    AccountType
}

A few important notes about what we’ve just done here:

1. We don’t specify any concrete data types.
2. All fields within our models have the capacity to be either containers or primitives.
3. We’re able to defer a model’s structural definition without affecting the pace of our planning.
4. Any changes to a particular field type will automatically propagate in our structural definitions, making it trivial to create a definition like ExpirationDate: String and later change it to ExpirationDate: DateObject.
5. The amount of information we need to think about is reduced down to the very bare minimum.
6. By deferring the definition of the PaymentMethods structure, we find ourselves more inclined to focus on the more concrete payment method definitions from the very beginning, rather than trying to force them to be compatible through an interface.
7. We focused only on data representation, ensuring that representation and implementation are both separate and can be handled differently if needed.

SOLIDifying Our Conceptual Model

In object-oriented programming (OOP), there’s a generally recommended set of principles to follow, represented by the acronym “SOLID”:

• Single responsibility.
• Open/closed.
• Liskov substitution.
• Interface segregation.
• Dependency inversion.

These “SOLID” principles were defined to help resolve common, recurring design problems and anti-patterns in OOP.

Of particular note for us is the last one, the “dependency inversion” principle. The idea behind this principle is that implementation details should depend on abstractions, not the other way around. Our new conceptual model obeys the dependency inversion principle by prioritizing a focus on abstractions while leaving implementation details to the future class definitions that are based on our abstractions. By doing so, we limit the elements involved in our planning and problem-solving stages to only what is necessary.

Final Thoughts

The consequences of such a conceptual model extend well beyond simply planning out data and object structures. For example, if implemented as an actual programming or language construct, you could make the parsing of your data fairly simple. By implementing an object parser that performs reflection on some passed object, you can extract all of the publicly accessible object properties of the target object and the data contained therein. Thus, if your language doesn’t have a built-in JSON encoding function and no library yet exists, you could recursively traverse your data structure to generate the appropriate JSON with very little effort.

Many of the most fundamental programming concepts, like data structures ultimately being nothing more than trees at their most abstract representation, are things we tend to take for granted and think very little about. By making ourselves conscious of these fundamental concepts, however, we can more effectively take advantage of them.

Additionally, successful programmers typically solve a programming problem before they’ve ever written a single line of code. Whether or not they’re conscious of it, the tools they use to solve these problems effectively consist largely of the myriad conceptual models they’ve collected and developed over time, and the experience they’ve accumulated to determine which conceptual models need to be utilized to solve a particular problem.

Even when you have a solid grasp of your programming fundamentals, you should always revisit them every now and then. Sometimes there are details that you may have missed or just couldn’t fully appreciate when you learned about them. This is something that I’m continually reminded of as I continue on in my own career growth, and I hope that I can continue passing these lessons on to others.

As always, I'm absolutely open to feedback and questions!

Previous challenges

Hi, it's been very long time from last Programming Challenge, and I'd like to revive the tradition.

The point of programming challenge is to create your own solution, and if you're bored, even program it in your favourite programming language. Today's challenge isn't mine. It was created by ČVUT FIKS (year 5, season 2, challenge #4).

You need to transport plans for your quantum computer through Totalitatia. The problem is, that Totalitatia's government would love to have the plans. And they know you're going to transport the computer through the country. You'll receive number N, which denotes number of cities on the map. Then, you'll get M paths, each going from one city to another. Each path has k traffic controls. They're not that much effective, but the less of them you have to pass, the better. Find path from city A to city B, so the maximum number of traffic controls between any two cities is minimal. City A is always the first one (0) and city B is always the last one (N-1).

Input format:

N
M
A1 B1 K1
A2 B2 K2
...

On the first two lines, you'll get numbers N (number of cities) and M (number of paths). Than, on next M lines, you'll get definition of a path. The definition looks like 1 2 6, where 1 is id of first city and 2 is id of second city (delimited by a space). You can go from city 1 to city 2, or from city 2 to city 1. The third number (6) is number of traffic controls.

Output format:

Single number, which denotes maximum number of traffic controls encountered on one path.

Hint: This means, that path that goes via roads with numbers of traffic controls 4 4 4 is better than path via roads with numbers of traffic controls 1 5 1. First example would have output 4, the second one would have output 5.

Example:

IN:

4
5
0 1 3
0 2 2
1 2 1
1 3 4
2 3 5

OUT:

4

Solution: The optimal path is either 0 2 1 3 or 0 1 3.

Bonus

• Describe time complexity of your algorithm.
• If multiple optimal paths exist, find the shortest one.
• Does your algorithm work without changing the core logic, if the source city and the target city is not known beforehand (it changes on each input)?
• Do you use special collection to speed up minimum value search?

Hints

Special collection to speed up algorithm

It's been over a week since the last programming challenge and the previous one was a bit more difficult, so let's do something easier and more accessible to newer programmers in particular. Write a function that takes two strings as input and returns true if they're anagrams of each other, or false if they're not.

Extra credit tasks:

• Don't consider the strings anagrams if they're the same barring punctuation.
• Write an efficient implementation (in terms of time and/or space complexity).
• Minimize your use of built-in functions and methods to bare essentials.
• Write the worst--but still working--implementation that you can conceive of.

Preface

Recently I briefly touched on the subject of cyclomatic complexity. This is an important concept for any programmer to understand and think about as they write their code. In order to provide a more solid understanding of the subject, however, I feel that I need to address the topic more thoroughly with a more practical example.

What is cyclomatic complexity?

The concept of "cyclomatic complexity" is simple: the more conditional branching and looping in your code, the more complex--and therefore the more difficult to maintain--that code is. We can visualize this complexity by drawing a diagram that illustrates the flow of logic in our program. For example, let's take the following toy example of a user login attempt:

<?php

$login_data = getLoginCredentialsFromInput();

$login_succeeded = false;
$error = '';
if(usernameExists($login_data['username'])) {
    $user = getUser($login_data['username']);
    
    if(!isDeleted($user)) {
        if(!isBanned($user)) {
            if(!loginRateLimitReached($user)) {
                if(passwordMatches($user, $login_data['password'])) {
                    loginUser($user);
                    $login_succeeded = true;
                } else {
                    $error = getBadPasswordError();
                    logBadLoginAttempt();
                }
            } else {
                $error = getLoginRateLimitError($user);
            }
        } else {
            $error = getUserBannedError($user);
        }
    } else {
        $error = getUserDeletedError($user);
    }
} else {
    $error = getBadUsernameError($login_data['username']);
}

if($login_succeeded) {
    sendSuccessResponse();
} else {
    sendErrorResponse($error);
}

?>

A diagram for this logic might look something like this:

+-----------------+
|                 |
|  Program Start  |
|                 |
+--------+--------+
         |
         |
         v
+--------+--------+    +-----------------+
|                 |    |                 |
|    Username     +--->+    Set Error    +--+
|    Exists?      | No |                 |  |
|                 |    +-----------------+  |
+--------+--------+                         |
         |                                  |
     Yes |                                  |
         v                                  |
+--------+--------+    +-----------------+  |
|                 |    |                 |  |
|  User Deleted?  +--->+    Set Error    +->+
|                 | Yes|                 |  |
+--------+--------+    +-----------------+  |
         |                                  |
      No |                                  |
         v                                  |
+--------+--------+    +-----------------+  |
|                 |    |                 |  |
|  User Banned?   +--->+    Set Error    +->+
|                 | Yes|                 |  |
+--------+--------+    +-----------------+  |
         |                                  |
      No |                                  |
         v                                  |
+--------+--------+    +-----------------+  |
|                 |    |                 |  |
|   Login Rate    +--->+    Set Error    +->+
| Limit Reached?  | Yes|                 |  |
|                 |    +-----------------+  |
+--------+--------+                         |
         |                                  |
      No |                                  |
         v                                  |
+--------+--------+    +-----------------+  |
|                 |    |                 |  |
|Password Matches?+--->+    Set Error    +->+
|                 | No |                 |  |
+--------+--------+    +-----------------+  |
         |                                  |
     Yes |                                  |
         v                                  |
+--------+--------+    +----------+         |
|                 |    |          |         |
|   Login User    +--->+ Converge +<--------+
|                 |    |          |
+-----------------+    +---+------+
                           |
                           |
         +-----------------+
         |
         v
+--------+--------+
|                 |
|   Succeeded?    +-------------+
|                 | No          |
+--------+--------+             |
         |                      |
     Yes |                      |
         v                      v
+--------+--------+    +--------+--------+
|                 |    |                 |
|  Send Success   |    |   Send Error    |
|    Message      |    |    Message      |
|                 |    |                 |
+-----------------+    +-----------------+

It's important to note that between nodes in this directed graph, you can find certain enclosed regions being formed. Specifically, each conditional branch that converges back into the main line of execution generates an additional region. The number of these distinct enclosed regions is directly proportional to the level of cyclomatic complexity of the system--that is, more regions means more complicated code.

Clocking out early.

There's an important piece of information I noted when describing the above example:

. . . each conditional branch that converges back into the main line of execution generates an additional region.

The above example is made complex largely due to an attempt to create a single exit point at the end of the program logic, causing these conditional branches to converge and thus generate the additional enclosed regions within our diagram.

But what if we stopped trying to converge back into the main line of execution? What if, instead, we decided to interrupt the program execution as soon as we encountered an error? Our code might look something like this:

<?php

$login_data = getLoginCredentialsFromInput();

if(!usernameExists($login_data['username'])) {
    sendErrorResponse(getBadUsernameError($login_data['username']));
    return;
}

$user = getUser($login_data['username']);
if(isDeleted($user)) {
    sendErrorResponse(getUserDeletedError($user));
    return;
}

if(isBanned($user)) {
    sendErrorResponse(getUserBannedError($user));
    return;
}

if(loginRateLimitReached($user)) {
    logBadLoginAttempt($user);
    sendErrorResponse(getLoginRateLimitError($user));
    return;
}

if(!passwordMatches($user, $login_data['password'])) {
    logBadLoginAttempt($user);
    sendErrorResponse(getBadPasswordError());
    return;
}

loginUser($user);
sendSuccessResponse();

?>

Before we've even constructed a diagram for this logic, we can already see just how much simpler this logic is. We don't need to traverse a tree of if statements to determine which error message has priority to be sent out, we don't need to attempt to follow indentation levels, and our behavior on success is right at the very end and at the lowest level of indentation, where it's easily and obviously located at a glance.

Now, however, let's verify this reduction in complexity by examining the associated diagram:

+-----------------+
|                 |
|  Program Start  |
|                 |
+--------+--------+
         |
         |
         v
+--------+--------+    +-----------------+
|                 |    |                 |
|    Username     +--->+   Send Error    |
|    Exists?      | No |    Message      |
|                 |    |                 |
+--------+--------+    +-----------------+
         |
     Yes |
         v
+--------+--------+    +-----------------+
|                 |    |                 |
|  User Deleted?  +--->+   Send Error    |
|                 | Yes|    Message      |
+--------+--------+    |                 |
         |             +-----------------+
      No |
         v
+--------+--------+    +-----------------+
|                 |    |                 |
|  User Banned?   +--->+   Send Error    |
|                 | Yes|    Message      |
+--------+--------+    |                 |
         |             +-----------------+
      No |
         v
+--------+--------+    +-----------------+
|                 |    |                 |
|   Login Rate    +--->+   Send Error    |
| Limit Reached?  | Yes|    Message      |
|                 |    |                 |
+--------+--------+    +-----------------+
         |
      No |
         v
+--------+--------+    +-----------------+
|                 |    |                 |
|Password Matches?+--->+   Send Error    |
|                 | No |    Message      |
+--------+--------+    |                 |
         |             +-----------------+
     Yes |
         v
+--------+--------+
|                 |
|   Login User    |
|                 |
+--------+--------+
         |
         |
         v
+--------+--------+
|                 |
|  Send Success   |
|    Message      |
|                 |
+-----------------+

Something should immediately stand out here: there are no enclosed regions in this diagram! Furthermore, even our new diagram is much simpler to follow than the old one was.

Reality is rarely simple.

The above is a really forgiving example. It has no loops, and loops are going to create enclosed regions that can't be broken apart so easily; it has no conditional branches that are so tightly coupled with the main path of execution that they can't be broken up; and the scope of functionality and side effects are minimal. Sometimes you can't break those regions up. So what do we do when we inevitably encounter these cases?

High cyclomatic complexity in your program as a whole is inevitable for sufficiently large projects, especially in a production environment, and your efforts to reduce it can only go so far. In fact, I don't recommend trying to remove all or even most instances of cyclomatic complexity at all--instead, you should just be keeping the concept in mind to determine whether or not a function, method, class, module, or other component of your system is accumulating technical debt and therefore in need of refactoring.

At this point, astute readers might ask, "How does refactoring help if the cyclomatic complexity doesn't actually go away?", and this is a valid concern. The answer to that is simple, however: we're hiding complexity behind abstractions.

To test this, let's forget about cyclomatic complexity for a moment and instead focus on simplifying the refactored version of our toy example using abstraction:

<?php

function handleLoginAttempt($login_data) {
    if(!usernameExists($login_data['username'])) {
        sendErrorResponse(getBadUsernameError($login_data['username']));
        return;
    }

    $user = getUser($login_data['username']);
    if(isDeleted($user)) {
        sendErrorResponse(getUserDeletedError($user));
        return;
    }

    if(isBanned($user)) {
        sendErrorResponse(getUserBannedError($user));
        return;
    }

    if(loginRateLimitReached($user)) {
        logBadLoginAttempt($user);
        sendErrorResponse(getLoginRateLimitError($user));
        return;
    }

    if(!passwordMatches($user, $login_data['password'])) {
        logBadLoginAttempt($user);
        sendErrorResponse(getBadPasswordError());
        return;
    }

    loginUser($user);
    sendSuccessResponse();
}

$login_data = getLoginCredentialsFromInput();

handleLoginAttempt($login_data);

?>

The code above is functionally identical to our refactored example from earlier, but has an additional abstraction via a function. Now we can diagram this higher-level abstraction as follows:

+-----------------+
|                 |
|  Program Start  |
|                 |
+--------+--------+
         |
         |
         v
+--------+--------+
|                 |
|  Attempt Login  |
|                 |
+-----------------+

This is, of course, a pretty extreme example, but this is how we handle thinking about complex program logic. We abstract it down to the barest basics so that we can visualize, in its simplest form, what the program is supposed to do. We don't actually care about the implementation unless we're digging into that specific part of the system, because otherwise we would be so bogged down by the details that we wouldn't be able to reason about what our program is supposed to do.

Likewise, we can use these abstractions to hide away the cyclomatic complexity underlying different components of our software. This keeps everything clean and clutter-free in our head. And the more we do to keep our smaller components simple and easy to think about, the easier the larger components are to deal with, no matter how much cyclomatic complexity all of those components share as a collective.

Final Thoughts

Cyclomatic complexity isn't a bad thing to have in your code. The concept itself is only intended to be used as one of many tools to assess when your code is accumulating too much technical debt. It's a warning sign that you may need to change something, nothing more. But it's an incredibly useful tool to have available to you and you should get comfortable using it.

As a general rule of thumb, you can usually just take a glance at your code and assess whether or not there's too much cyclomatic complexity in a component by looking for either of the following:

• Too many loops and/or conditional statements nested within each other, i.e. you have a lot of indentation.
• Many loops in the same function/method.

It's not a perfect rule of thumb, but it's useful for at least 90% of your development needs, and there will inevitably be cases where you will prefer to accept some greater cyclomatic complexity because there is some benefit that makes it a better trade-off. Making that judgment is up to you as a developer.

As always, I'm more than willing to listen to feedback and answer any questions!

Preface

Software security is one of those subjects that often gets overlooked, both in academia and in professional projects, unless you're specifically working with some existing security-related element (e.g. you're taking a course on security basics, or updating your password hashing algorithm). As a result, we frequently see stories of rather catastrophic data leaks from otherwise reputable businesses, leaks which should have been entirely preventable with even the most basic of safeguards in place.

With that in mind, I thought I would switch things up and discuss something security-related this time.

Background

It's commonplace for complex software systems to avoid unnecessarily large expenses, especially in terms of technical debt and the capital involved in the initial development costs of building entire systems for e.g. geolocation or financial transactions. Instead of reinventing the wheel and effectively building a parallel business, we instead integrate with existing third-party systems, typically by using an API.

The problem, however, is that sometimes these third-party systems process requests over a long period of time, potentially on the order of minutes, hours, days, or even longer. If, for example, you have users who want to purchase something using your online platform, then it's not a particularly good idea to having potentially thousands of open connections to that third-party system all sitting there waiting multiple business days for funds to clear. That would just be stupid. So, how do we handle this in a way that isn't incredibly stupid?

There are two commonly accepted methods to avoid having to wait around:

1. We can periodically contact the third-party system and ask for the current status of a request, or
2. We can give the third-party system a way to contact us and let us know when they're finished with a request.

Both of these methods work, but obviously there will be a potentially significant delay in #1 between when a request finishes and when we know that it has finished (with a maximum delay of the wait time between status updates), whereas in #2 that delay is practically non-existent. Using #1 is also incredibly inefficient due to the number of wasted status update requests, whereas #2 allows us to avoid that kind of waste. Clearly #2 seems like the ideal option.

Method #2 is what we call a webhook.

May I see your ID?

The problem with webhooks is that when you're implementing one, it's far too easy to forget that you need to restrict access to it. After all, that third-party system isn't a user, right? They're not a human. They can't just give us a username and password like we want them to. They don't understand the specific requirements for our individual, custom-designed system.

But what happens if some malicious actor figures out what the webhook endpoint is? Let's say that all we do is log webhook requests somewhere in a non-capped file or database table/collection. Barring all other possible attack vectors, we suddenly find ourselves susceptible to that malicious actor sending us thousands, possibly millions of fraudulent data payloads in a small amount of time thanks to a botnet, and now our server's I/O utilization is spiking and the entire system is grinding to a halt--we're experiencing a DDoS!

We don't want just anyone to be able to talk to our webhook. We want to make sure that anyone who does is verified and trusted. But since we can't require a username and password, since we can't guarantee that the third-party system will even know how to make use of them, what can we do?

The answer is to use some form of token-based authentication--we generate a unique token, kind of like an ID card, and we attach it to our webhook endpoint (e.g. https://example.com/my_webhook/{unique_token}). We can then check that token for validity every time someone touches our webhook, ensuring that only someone we trust can get in.

Class is in Session

Just as there are two commonly accepted models for how to handle receiving updates from third-party systems, there are also two common models for how to assign a webhook to those systems:

1. Hard-coding the webhook in your account settings, or
2. Passing a webhook as part of request payload.

Model #1 is, in my experience, the most common of the two. In this model, our authentication token is typically directly linked to some user or user-like object in our system. This token is intended to be persisted and reused indefinitely, only scrapped in the event of a breach or a termination of integration with the service that uses it. Unfortunately, if the token is present within the URL, it's possible for your token to be viewed in plaintext in your logs.

In model #2, it's perfectly feasible to mirror the behavior of model #1 by simply passing the same webhook endpoint with the same token in every new request; however, there is a far better solution. We can, instead, generate a brand new token for each new request to the third-party system, and each new token can be associated with the request itself on our own system. Rather than only validating the token itself, we then validate that the token and the request it's supposed to be associated with are both valid. This ensures that even in the event of a breach, a leaked authentication token's extent of damage is limited only to the domain of the request it's associated with! In addition, we can automatically expire these tokens after receiving a certain number of requests, ensuring that a DDoS using a single valid token and request payload isn't possible. As with model #1, however, we still run into problems of token exposure if the token is present in the URL.

Model #2 treats each individual authentication token not as a session for an entire third-party system, but as a session for a single request on that system. These per-request session tokens require greater effort to implement, but are inherently safer due to the increased granularity of our authentication and our flexibility in allowing ourselves to expire the tokens at will.

Final Thoughts

Security is hard. Even with per-request session tokens, webhooks still aren't as secure as we might like them to be. Some systems allow us to define tokens that will be inserted into the request payload, but more often than not you'll find that only a webhook URL is possible to specify. Ideally we would stuff those tokens right into the POST request payload for all of our third-party systems so they would never be so easily exposed in plaintext in log files, but legacy systems tend to be slow to catch up and newer systems often don't have developers with the security background to consider it.

Still, as far as securing webhooks goes, having some sort of cryptographically secure authentication token is far better than leaving the door wide open for any script kiddie having a bad day to waltz right in and set the whole place on fire. If you're integrating with any third-party system, your job isn't to make it impossible for them to get their hands on a key, but to make it really difficult and to make sure you don't leave any gasoline lying around in case they do.

Hi everyone, it's been 12 days since last programming challenge. So here's another one. The task is to make an algorithm that'll count how long would it take to fill system of lakes with water.

It's raining in the forest. The forest is full of lakes, which are close to each other. Every lake is below the previous one (so 1st lake is higher than 2nd lake, which is higher than 3rd lake). Lakes are empty at the beginning, and they're filling at rate of 1l/h. Once a lake is full, all water that'd normally fall into the lake will flow to the next lake.

For example, you have lakes A, B, and C. Lake A can hold 1 l of water, lake B can hold 3 l of water and lake C can hold 5 l of water. How long would it take to fill all the lakes?
After one hour, the lakes would be: A (1/1), B (1/3), C(1/5). After two hours, the lakes would be: A(1/1), B(3/3), C(2/5) (because this hour, B received 2l/h - 1l/h from the rain and 1l/h from lake A). After three hours, the lakes would be: A(1/1), B(3/3), C(5/5). So the answer is 3. Please note, that the answer can be any rational number. For example if lake C could hold only 4l instead of 5, the answer would be 2.66666....

Hour 0:

\            /
  ----(A)----
                       \                /
                        \              /
                         \            /
                          ----(B)----
                                             \           /
                                              \         /
                                               \       /
                                               |       |
                                               |       |
                                                --(C)--

Hour 1:

\============/
  ----(A)----
                       \                /
                        \              /
                         \============/
                          ----(B)----
                                             \           /
                                              \         /
                                               \       /
                                               |       |
                                               |=======|
                                                --(C)--

Hour 2:

            ==============
\============/           |
  ----(A)----            |
                       \================/
                        \==============/
                         \============/
                          ----(B)----
                                             \           /
                                              \         /
                                               \       /
                                               |=======|
                                               |=======|
                                                --(C)--

Hour 3:

            ==============
\============/           |
  ----(A)----            |             ========
                       \================/       |
                        \==============/        |
                         \============/         |
                          ----(B)----           |
                                             \===========/
                                              \=========/
                                               \=======/
                                               |=======|
                                               |=======|
                                                --(C)--

Good luck everyone! Tell me if you need clarification or a hint. I already have a solution, but it sometimes doesn't work, so I'm really interested in seeing yours :-)

Preface

Different projects have different use cases that can ultimately result in common solutions not suiting your particular needs. Today I'm going to diverging a bit from my more abstract, generalized topics on code quality and instead focus on a specific project structure example that I encountered.

Background

For a while now, I've found myself being continually frustrated with the state of my project configuration management. I had a single configuration file that would contain all of the configuration options for the various tools I've been using--database, API credentials, etc.--and I kept running into the problem of wanting to test these tools locally while not inadvertently committing and pushing sensitive credentials upstream. For me, part of my security process is ensuring that sensitive access credentials never make it into the repository and to limit access to these credentials to only people who need to be able to access them.

Monolithic Files Cause Monolithic Pain

The first thing I realized was that having a single monolithic configuration file was just terrible practice. There are going to be common configuration options that I want to have in there with default values, such as local database configuration pointing to a database instance running on the same VM as the application. These should always be in the repo, otherwise any dev who spins up an instance of the VM will need to manually tread documentation and copy-paste the missing options into the configuration. This would be incredibly time-consuming, inefficient, and stupid.

I also use different tools which have different configuration options associated with them. Having to dig through a single file containing configuration options for all of these tools to find the ones I need to modify is cumbersome at best. On top of that, having those common configuration options living in the same place that sensitive access credentials do is just asking for a rogue git commit -A to violate the aforementioned security protocol.

Same Problem, Different Structure

My first approach to resolving this problem was breaking the configuration out into separate files, one for each distinct tool. In each file, a "skeleton" config was generated, i.e. each option was given a default empty value. The main config would then only contain config options that are common and shared across the application. To avoid having the sensitive credentials leaked, I then created rules in the .gitignore to exclude these files.

This is where I ran into problem #2. I learned that this just doesn't work. You can either have a file in your repo and have all changes to that file tracked, have the file in your repo and make a local-only change to prevent changes from being tracked, or leave the file out of the repo completely. In my use case, I wanted to be able to leave the file in the repo, treat it as ignored by everyone, and only commit changes to that file when there was a new configuration option I wanted added to it. Git doesn't support this use case whatsoever.

This problem turned out to be really common, but the solution suggested is to have two separate versions of your configuration--one for dev, and one for production--and to have a flag to switch between the two. Given the breaking up of my configuration, I would then need twice as many files to do this, and given my security practices, this would violate the no-upstream rule for sensitive credentials. Worse still, if I had several different kinds of environments with different configuration--local dev, staging, beta, production--then for m such environments and n configuration files, I would need to maintain n*m separate files for configuration alone. Finally, I would need to remember to include a prefix or postfix to each file name any time I needed to retrieve values from a new config file, which is itself an error-prone requirement. Overall, there would be a substantial increase in technical debt. In other words, this approach would not only not help, it would make matters worse!

Borrowing From Linux

After a lot of thought, an idea occurred to me: within Linux systems, there's an /etc/skel/ directory that contains common files that are copied into a new user's home directory when that user is created, e.g. .bashrc and .profile. You can make changes to these files and have them propagate to new users, or you can modify your own personal copy and leave all other new users unaffected. This sounds exactly like the kind of behavior I want to emulate!

Following their example, I took my $APPHOME/config/ directory and placed a skel/ subdirectory inside, which then contained all of the config files with the empty default values within. My .gitignore then looked something like this:

$APPHOME/config/*
!$APPHOME/config/main.php
!$APPHOME/config/skel/
!$APPHOME/config/skel/*
# This last one might not be necessary, but I don't care enough to test it without.

Finally, on deploying my local environment, I simply include a snippet in my script that enters the new skel/ directory and copies any files inside into config/, as long as it doesn't already exist:

cd $APPHOME/config/skel/
for filename in *; do
    if [ ! -f "$APPHOME/config/$filename" ]; then
        cp "$filename" "$APPHOME/config/$filename"
    fi
done

(Note: production environments have a slightly different deployment procedure, as local copies of these config files are saved within a shared directory for all releases to point to via symlink.)

All of these changes ensure that only config/main.php and the files contained within config/skel/ are whitelisted, while all others are ignored, i.e. our local copies that get stored within config/ won't be inadvertently committed and pushed upstream!

Final Thoughts

Common solutions to problems are typically common for a good reason. They're tested, proven, and predictable. But sometimes you find yourself running into cases where the common, well-accepted solution to the problem doesn't work for you. Standards exist to solve a certain class of problems, and sometimes your problem is just different enough for it to matter and for those standards to not apply. Standards are created to address most cases, but edge cases will always exist. In other words, standards are guidelines, not concrete rules.

Sometimes you need to stop thinking about the problem in terms of the standard approach to solving it, and instead break it down into its most abstract, basic form and look for parallels in other solved problems for inspiration. Odds are the problem you're trying to solve isn't as novel as you think it is, and that someone has probably already solved a similar problem before. Parallels, in my experience, are usually a pretty good indicator that you're on the right track.

More importantly, there's a delicate line to tread between needing to use a different approach to solving an edge case problem you have, and needing to restructure your project to eliminate the edge case and allow the standard solution to work. Being able to decide which is more appropriate can have long-lasting repercussions on your ability to manage technical debt.

Preface

Occasionally I feel the need to touch on the subject of code quality, particularly because of the importance of its impact on technical debt, especially as I continue to encounter the effects of technical debt in my own work and do my best to manage it. It's a subject that is unfortunately not emphasized nearly enough in academia.

Background

As a refresher, technical debt is the long-term cost of the design decisions in your code. These costs can manifest in different ways, such as greater difficulty in understanding what your code is doing or making non-breaking changes to it. More generally, these costs manifest as additional time and resources being spent to make some kind of change.

Sometimes these costs aren't things you think to consider. One such consideration is how difficult it might be to upgrade a specific technology in your stack. For example, what if you've built a back-end system that integrates with AWS and you suddenly need to upgrade your SDK? In a small project this might be easy, but what if you've built a system that you've been maintaining for years and it relies heavily on AWS integrations? If the method names, namespaces, argument orders, or anything else has changed between versions, then suddenly you'll need to update every single reference to an AWS-related tool in your code to reflect those changes. In larger software projects, this could be a daunting and incredibly expensive task, spanning potentially weeks or even months of work and testing.

That is, unless you keep those references to a minimum.

A Toy Example

This is where "wrapping" your external libraries comes into play. The concept of "wrapping" basically means to create some other function or object that takes care of operating the functions or object methods that you really want to target. One example might look like this:

<?php

class ImportedClass {
    public function methodThatMightBecomeModified($arg1, $arg2) {
        // Do something.
    }
}

class ImportedClassWrapper {
    private $class_instance = null;

    private function getInstance() {
        if(is_null($this->class_instance)) {
            $this->class_instance = new ImportedClass();
        }

        return $this->class_instance;
    }

    public function wrappedMethod($arg1, $arg2) {
        return $this->getInstance()->methodThatMightBecomeModified($arg1, $arg2);
    }
}

?>

Updating Tools Doesn't Have to Suck

Imagine that our ImportedClass has some important new features that we need to make use of that are only available in the most recent version, and we're several versions behind. The problem, of course, is that there were a lot of changes that ended up being made between our current version and the new version. For example, ImportedClass is now called NewImportedClass. On top of that, methodThatMightBecomeModified is now called methodThatWasModified, and the argument order ended up getting switched around!

Now imagine that we were directly calling new ImportedClass() in many different places in our code, as well as directly invoking methodThatMightBecomeModified:

<?php

$imported_class_instance = new ImportedClass();
$imported_class_instance->methodThatMightBeModified($val1, $val2);

?>

For every single instance in our code, we need to perform a replacement. There is a linear or--in terms of Big-O notation--a complexity of O(n) to make these replacements. If we assume that we only ever used this one method, and we used it 100 times, then there are 100 instances of new ImportClass() to update and another 100 instances of the method invocation, equaling 200 lines of code to change. Furthermore, we need to remember each of the replacements that need to be made and carefully avoid making any errors in the process. This is clearly non-ideal.

Now imagine that we chose instead to use the wrapper object:

<?php

$imported_class_wrapper = new ImportedClassWrapper();
$imported_class_wrapper->wrappedMethod($val1, $val2);

?>

Our updates are now limited only to the wrapper class:

<?php

class ImportedClassWrapper {
    private $class_instance = null;

    private function getInstance() {
        if(is_null($this->class_instance)) {
            $this->class_instance = new NewImportedClass();
        }

        return $this->class_instance;
    }

    public function wrappedMethod($arg1, $arg2) {
        return $this->getInstance()->methodThatWasModified($arg2, $arg1);
    }
}

?>

Rather than making changes to 200 lines of code, we've now made changes to only 2. What was once an O(n) complexity change has now turned into an O(1) complexity change to make this upgrade. Not bad for a few extra lines of code!

A Practical Example

Toy problems are all well and good, but how does this translate to reality?

Well, I ran into such a problem myself once. Running MongoDB with PHP requires the use of an external driver, and this driver provides an object representing a MongoDB ObjectId. I needed to perform a migration from one hosting provider over to a new cloud hosting provider, with the application and database services, which were originally hosted on the same physical machine, hosted on separate servers. For security reasons, this required an upgrade to a newer version of MongoDB, which in turn required an upgrade to a newer version of the driver.

This upgrade resulted in many of the calls to new MongoId() failing, because the old version of the driver would accept empty strings and other invalid ID strings and default to generating a new ObjectId, whereas the new version of the driver treated invalid ID strings as failing errors. And there were many, many cases where invalid strings were being passed into the constructor.

Even after spending hours replacing the (literally) several dozen instances of the constructor calls, there were still some places in the code where invalid strings managed to get passed in. This made for a very costly upgrade.

The bugs were easy to fix after the initial replacements, though. After wrapping new MongoId() inside of a wrapper function, a few additional conditional statements inside of the new function resolved the bugs without having to dig around the rest of the code base.

Final Thoughts

This is one of those lessons that you don't fully appreciate until you've experienced the technical debt of an unwrapped external library first-hand. Code quality is an active effort, but a worthwhile one. It requires you to be willing to throw away potentially hours or even days of work when you realize that something needs to change, because you're thinking about how to keep yourself from banging your head against a wall later down the line instead of thinking only about how to finish up your current task.

"Work smarter, not harder" means putting in some hard work upfront to keep your technical debt under control.

That's all for now, and remember: don't be fools, wrap your external tools.

The programming challenges have kind of come to a grinding halt recently. I think it's time to get another challenge started!

Given a grid of symbols, representing a simple binary state of "filled" or "unfilled", determine whether or not a square is present on the grid. Squares must be 2x2 in size or larger, must be completely solid (i.e. all symbols in the NxN space are "filled"), and must not be directly adjacent to any other filled spaces.

Example, where 0 is "empty" and 1 is "filled":

000000
011100
011100
011100
000010

// Returns true.

000000
011100
011100
011110
000000

// Returns false.

000000
011100
010100
011100
000000

// Returns false.

For those who want a greater challenge, try any of the following:

1. Get a count of all squares.
2. Detect squares that are touching (but not as a rectangle).
3. Detect other specific shapes like triangles or circles (you will need to be creative).
4. If doing (1) and (3), count shapes separately based on type.
5. Detect shapes within unfilled space as well (a checkerboard pattern is a great use case).

Preface

In a previous topic, I'd covered the subject of a few small lessons regarding code quality. Especially important was the impact on technical debt, which can bog down developer productivity, and the need to pay down on that debt. Today I would like to touch on a practical example that I'd encountered in a production environment.

Background

Before we can discuss the refactor itself, it's important to be on the same page regarding the technologies being used. In my case, I work with PHP utilizing a proprietary back-end framework and MongoDB as our database.

PHP is a server-side scripting language. Like many scripting languages, it's loosely typed. This has some benefits and drawbacks.

MongoDB is a document-oriented database. By default it's schema-less, allowing you to make any changes at will without an update to schema. This can blend pretty well with the loose typing of PHP. Each document is represented using a JSON-like structure and is stored in something called a "collection". For those of you accustomed to using relational database, a "collection" is analogous to a table, each document is a row, and each field in the document is a column. A typical query in the MongoDB shell would look something like this:

db.users.findOne({
    username: "Emerald_Knight"
});

The framework itself has some framework-specific objects that are held in global references. This makes them easily accessible, but naturally littering your code with a bunch of globals is both error-prone and an eyesore.

Unexpected Spaghetti

In my code base are a number of different objects that are designed to handle basic CRUD-like operations on their associated database entries. Some of these objects hold references to other objects, so naturally there is some data validation that occurs to ensure that the references are both valid and authorized. Pretty typical stuff.

What I noticed, however, is that the collection names for these database entries were littered throughout my code. This isn't necessarily a bad thing, except there were some use cases that came to mind: what if it turned out that my naming for one or more of these collections wasn't ideal? What if I wanted to change a collection name for the sake of easier management on the database end? What if I have a tendency to forget the name of a database collection and constantly have to look it up? What if I make a typo of all things? On top of that, the framework's database object was stored in a global variable.

These seemingly minor sources of technical debt end up adding up over time and could cause some serious problems in the worst case. I've had breaking bugs make their way passed QA in the past, after all.

Exchanging Spaghetti for Some Light Lasagna

The problem could be characterized simply: there were scoping problems and too many references to what were essentially magic strings. The solution, then, was to move the database object reference from global to local scope within the application code and to eliminate the problem of magic strings. Additionally, it's a good idea to avoid polluting the namespace with an over-reliance on constants, and using those constants for database calls can also become unsightly and difficult to follow as those constants could end up being generally disconnected from the objects they're associated with.

There turned out to be a nice, object-oriented, very PHP-like solution to this problem: a so-called "magic method" named "__call". This method is invoked whenever an "inaccessible" method is called on the object. Using this method, a database command executed on a non-database object could pass the command to the database object itself. If this logic were placed within an abstract class, the collection could then be specified simply as a configuration option in the inheriting class.

This is what such a solution could look like:

<?php

abstract class MyBaseObject {

    protected $db = null;
    protected $collection_name = null;

    public function __construct() {
        global $db;
        
        $this->db = $db;
    }

    public function __call($method_name, $args) {
        if(method_exists($this->db, $method_name)) {
            return $this->executeDatabaseCommand($method_name, $args);
        }

        throw new Exception(__CLASS__ . ': Method "' . $method_name . '" does not exist.');
    }

    public function executeDatabaseCommand($command, $args) {
        $collection = $this->collection_name;
        $db_collection = $this->db->$collection;

        return call_user_func_array(array($db_collection, $command), $args);
    }
}

class UserManager extends MyBaseObject {
    protected $collection_name = 'users';

    public function __construct() {
        parent::__construct();
    }
}

$user_manager = new UserManager();
$my_user = $user_manager->findOne(array('username'=>'Emerald_Knight'));

?>

This solution utilizes a single parent object which transforms a global database object reference into a local one, eliminating the scope issue. The collection name is specified as a class property of the inheriting object and only used in a single place in the parent object, eliminating the magic string and namespace polluting issues. Any time you perform queries on users, you do so by using the UserManager class, which guarantees that you will always know that your queries are being performed on the objects that you intend. And finally, if the collection name for an object class ever needs to be updated, it's a simple matter of modifying the single instance of the class property $collection_name, rather than tracking down some disconnected constant.

Limitations

This, of course, doesn't solve all of the existing problems. After all, executing the database queries for one object directly from another is still pretty bad practice, violating the principle of separation of concerns. Instead, those queries should generally be encapsulated within object methods and the objects themselves given primary responsibility in handling associated data. It's also incredibly easy to inadvertently override a database method, e.g. defining a findOne() method on UserManager, so there's still some mindfulness required on the part of the programmer.

Still, given the previous alternative, this is a pretty major improvement, especially for an initial refactor.

Final Thoughts

As always, technical debt is both necessary and inevitable. After all, in exchange for not taking the excess time and considering structuring my code this way in the beginning, I had greater initial velocity to get the project off of the ground. What's important is continually reviewing your code as you're building on top of it so that you can identify bottlenecks as they begin to strain your efficiency, and getting those bottlenecks out of the way.

In other words, even though technical debt is often necessary and is certainly inevitable, it's important to pay down on some of that debt once it starts getting expensive!

It's time for another programming challenge!

Given a list of coordinate pairs on a 2D plane that describe the vertices of a polygon, determine whether the polygon is concave or convex.

Since a polygon could potentially be any shape if we don't specify which vertices connect to which, we'll assume that the coordinates are given in strict order such that adjacent coordinates in the list are connected. Specifically, if we call the list V[1, n] and say that V[i] <-> V[j] means "vertex i and vertex j are connected", then for each arbitrary V[i] we have V[i-1] <-> V[i] <-> V[i+1]. Moreover, since V[1] and V[n] are at the ends of the list, V[1] <-> V[n] holds (i.e. the list "wraps around").

Finally, for simplicity we can assume that all coordinates are unique, that all polygon descriptions generate valid polygons with 3 or more non-overlapping sides, and that, yes, we're working with coordinates that exist in the set of real numbers only. Don't over-complicate it :)

For those who want an even greater challenge, extend this out to work with 3D space!

It's been nearly a week, so it's time for another programming challenge!

This time, let's create a calculator that accepts reverse Polish notation (RPN), also known as postfix notation.

For a bit of background, RPN is where you take your two operands in an expression and place the operator after them. For example, the expression 3 + 5 would be written as 3 5 +. A more complicated expression like (5 - 3) x 8 would be written as 5 3 - 8 x, or 8 5 3 - x.

All your program has to do is accept a valid RPN string and apply the operations in the correct order to produce the expected result.

Another week, another challenge!

This time, assume you're given a grid where each . represents an empty space and each # represents a "wall". We'll call any contiguous space of .s a "region". You can also think of a grid with no walls the "base" region. The walls may subdivide the base region into any number of isolated sub-regions of any shape or size.

Write a program that will, given a grid description, compute the total number of isolated regions.

For example, the following grid has 5 isolated regions:

....#....#
....#.###.
....#.#.#.
#...#..#..
.#..#...#.

It looks like it's been over a week and a half since our last coding challenge, so let's get one going. This challenge is a relatively simple one, but it's complex enough that you can take a variety of different approaches to it.

As the title suggests, write a program that accepts an arbitrary number of arrays, in whatever form or manner you see fit (if you want to e.g. parse a potentially massive CSV file, then go nuts!), and returns a single array containing all of the elements of the other arrays in sorted order. That's it!

Bonus points for creative, efficient, or generalized solutions!

Let's do something a little more challenging this time.

Given an MxN grid of arbitrary size, and given a random starting place on that grid and a list of points to visit, find the shortest path such that you visit all of them. Path lengths will be computed using taxicab distances rather than strict coordinate distance calculations.

There are no restrictions on expected input this time. Output should be the total distance traveled between points.

Example

Assume that we use the character # to denote a spot on the grid, the character @ to denote your starting point, and the character * to denote a place on the grid that you're required to visit. One such grid may look something like this:

######
######
**####
#*####
#*#*##
#@####
######

In this case, let's say that the bottom-left point on the grid is point (0, 0) and we're starting on point (1, 1). One valid solution would be to move to point (3, 2), then (1, 2), then (1, 3), then (1, 4), and finally (0, 4). The shortest path available is thus 8. Note that it's not enough just to visit the next nearest point on the grid!

Another programming mini-challenge for you. It's been a month since the first one and that seemed to be rather successful. (I appreciate that there are other challenges on here but trying to sync with them seems tricky!)

A reminder:
I'm certain that many of you might find these pretty straight forward, but I still think there's merit in sharing different approaches to simple problems, including weird-and-wonderful ones.

KnightBot

Info

You will be writing a small part of a Chess program, specifically focusing on the Knight, on an 8 x 8 board.

Input

The top-left square of the board will have index 0, and the bottom-right square will have index 63.

• The first input is the starting square of the knight.
• The second input is the requested finishing square of the knight.
• The third input is the number of maximum moves allowed.

Output

The expected outcome is either True or False, determined by whether or not the Knight can reach the requested finishing square within the number of allowed moves when stating on the starting square.

e.g. The expected output for the input 16, 21, 4 is True since the Knight can move 16->33->27->21, which is 3 moves.

Extensions

Some additional ideas for extending this challenge...

1. Instead of an 8x8, what if the board was nxn?
2. Instead of "within x moves", what if it was "with exactly x moves?"
3. Instead of a traditional Knight's move (2 long, 1 short), what if it was n long and m short?
4. What if the board was infinite?
5. What if the board looped back around when crossing the edges? (e.g. the square to the right of 7 is 0)

Hi,

There's a certain site which hosts media files and has a player that depends on a lot of third-party resources to play, while browsers have native support for those file types. Those 3rd-party resources are often blocked by ad blockers and I have no desire to white-list them. I would like to extract the direct link to the media file and make it playable on my custom web page.

The link to the media file is present in the page source of each page, always on the same line. It's not anchored in HTML but present in the JavaScript for the player, like so:

    $(document).ready(function(){
      $("#jquery_jplayer_1").jPlayer({
        ready: function () {
          $(this).jPlayer("setMedia", {
            [ext]: "https://[domain]/[filename.ext]"
          });
        },

In this example it's on line #5. [ext] = the file extension.

I want to build the following:

• A web page with a form with a single input field meant to receive links from that specific file host
• [Something] that extracts the file link from the source of the host's page
• Present the linked file as playable in an embedded native player

So far I've managed to create a form with an input box and a submit button, but it doesn't do anything yet. What is the best way to build the actual functionality? I know HTML/CSS. I have some rudimentary understanding of JavaScript/jQuery and Python3, so those would be my preferred tools.

For those worried about piracy: The files in question are not copyrighted and I'm not looking to make copies. I just want to make them playable. This is for personal use.

Thank you for reading this far. Any and all advice is welcome!

I thought it could be fun to discuss problems that we've encountered in our programming or programming-related work and have never found a solution for. I figure that at worst we can have a lot of fun venting about and scratching our heads at things that just don't make any sense to anyone, and at best we might be able to help each other find answers and, more importantly, some closure.

TLDR: What programming language would be useful for taking info in an excel file and producing a text file (that is organized and arranged in a particular way) containing that info? Which would be useful for this problem but also helpful in general? And also, are there any recommended online courses where I could learn it?

I have no real experience coding or anything but have always wanted to learn. Recently at work we've encountered a problem. My boss had created a matlab program in order to take text/numbers from an excel document and transfer them to a text file, but in an organized way.

Say you have something you call "Pancakes" and the cell next to it has the number "3", as in there are three pancakes. I want to be able to create a text file that would read something like this:

NUMBER OF PANCAKES

• Pancakes: 3

We recently have changed around the format of the excel document for a different item, for example "French Toast". I've tried to mess with matlab briefly but was unable to change the program to compensate, and I no longer easily have access to matlab.

I'm seeing this as an opportunity to learn some programming and also fix some stuff at work. So what programming language would be useful for fixing this problem? Which would be useful for this problem, but also helpful in general? And also, are there any recommended online courses where I could learn it?

Thanks for any help, I appreciate it.

Background

There's been some talk on ~ before, and it seems like there are quite a few people who are either interested in, learning, or working in game development, so I thought this could be a fun programming challenge.

This one is fairly open-ended: make a game in 1 hour. Any game, any engine, don't worry about art or sound or anything.

Doing is the best way to learn. Most people's first project is something overly ambitious, and when they find that it's more difficult than they thought, they can get discouraged, or even give up entirely. This is why the 1 hour limit is important: it forces you to finish something, even if it's small. When you're done, you can come out of it saying you made a game, and you learned from it.

Chances are the game might not be fun, look bad, be buggy, etc. But don't worry about that, everyone's game will have problems, and if you do create something really fun or innovative, congratulations, you have a prototype that you can expand on later!

"Rules"

Like I said before, these "rules" are pretty simple: make a game in (approximately) 1 hour. You can use any tools you want. If you use external assets (art, sound), it's probably best you use something you have the rights to (see resources). If you're completely new to game development/programming, your goal could even be to finish a tutorial.

If you're the kind of person who tends to get carried away with these things, you might want to post a comment saying you're starting, then another one once you've finished your game.

Please share your finished game, I'm sure everyone would love to try them! If your game is web-based, it can be hosted for free on Github Pages or Itch.io. If downloadable, it can be hosted for free on Google Drive, Mega, Dropbox, Itch.io, etc.

Resources

Engines

If you're a beginner, a good engine to start with is LÖVE. It's very simple, and uses Lua, which is very easy to learn.

If you're familiar with another language, you could use a library to make it in that language. Some examples:

C++: SFML, SDL, Allegro

Javascript: kontra, Phaser, pixi.js

Python: pygame

Rust: Piston, ggez, Amethyst

If you want something more complex, consider Godot, Unity, or Unreal.

You can also try something visual like Construct, Clickteam Fusion, or GDevelop

Art

For such a short time constraint, I'd suggest you use your own "programmer art": just use some basic shapes. Your primary focus should be gameplay.

If you think you have time to find something, try looking on OpenGameArt.

Sound

You can make simple sound effects very quickly with sfxr (or in this case, a web port of sfxr called jsfxr).

I've seen the programming challenges on ~comp as well as quite a few users who are interested in getting started with programming. I thought it would be interesting to post some 'mini-challenges' that all could have a go at. I'm certain that many of you might find these pretty straight forward, but I still think there's merit in sharing different approaches to simple problems, including weird-and-wonderful ones.

This is my first post and I'm a maths-guy who dabbles in programming, so I'm not promising anything mind-blowing. If these gain any sort of traction I'll post some more.

Starting of with...

TicTacToeBot

Info

You will be writing code for a programme that will check to see if a player has won a game of tic-tac-toe.

Input

The input will be 9 characters that denote the situation of each square on the grid.

• 'X' represents the X-player has moved on that square.
• 'O' represents the O-player has moved on that square.
• '#' represents that this square is empty.

Example:

|O| |X|
|X|X|O|    The input for this grid will be O#XXXOO##
|O| | |

Output

The expected output is the character representing the winning player, or "#" if the game is not won.

(e.g. The expected output for the example above is '#' since no player has won)

Pretty standard:

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

The twist: come up with the most creative or unusual way to solve this in your language of choice.

I just realized that I completely glossed over this week's programming challenge. For this week, let's do something more flexible: write a program that accepts a file as input--either through a file name/path or through standard input--and perform any form of analysis you want on its contents. That's it!

For instance, you could count the occurrences of each word and find the most common ones, or you could determine the average sentence length, or the average unique words per sentence. You could even perform an analysis on changes in words and sentence structure over time (could be useful for e.g. poetry where metre may play an important role). You can stick with simple numbers or dive right into the grittiest forms of textual analysis currently available. You could output raw text or even a graphical representation. You could even do a bit of everything!

How simple or complex your solution ends up being is completely up to you, but I encourage you to challenge yourself by e.g. learning a new language or about different textual analysis techniques, or by focusing on code quality rather than complexity, or even by taking a completely different approach to the problem than you ordinarily would. There are a lot of learning opportunities available here.

It's that time of week again! For this week's programming challenge, I thought I would focus on data structures.

Goal: Construct a binary tree data structure. It may handle any data type you choose, but you must handle sorting correctly. You must also provide a print function that prints each value in the tree on a new line, and the values must be printed in strictly increasing order.

If you're unfamiliar with this data structure, it's a structure that starts with a single "root" node, and this root can have a left child, right child, both, or neither. Each of these child nodes is exactly the same as the root node, except the root has no parent. This branching structure is why it's called a tree. Furthermore, left descendants always have values smaller than the parent, and right descendants always have larger values.

This problem is based on the Project Euler problem here.

Goal: Given some input describing a triangle of numbers, find the path starting from the top-most row of the triangle and ending at the bottom-most row of the triangle that contains the largest sum of all of the numbers along the path. You may only move downward and you must select an adjacent position to move to. Efficiency is not a requirement for completion.

Constraints:

• The first line of input for a triangle will be a single integer telling you how many rows the triangle will have.
• Each following line of input will be the next row of the number triangle, starting at the first row.
• For each line describing the number triangle, the individual numbers will be separated by a single space.

Note: The constraints above are to keep hard-coded triangles out of submitted solutions while also ensuring that all languages can equally handle this problem without annoying workarounds for lower-level languages. The consistency also makes it easier for beginners to review and understand someone else's code, and makes it easier to receive help if you get stuck. They're not necessarily required, but are highly encouraged.

Example input:

4
1
3 2
4 5 6
7 8 9 10

Corresponding triangle:

   1
  3 2
 4 5 6
7 8 9 10

Expected result: 19 (1 + 2 + 6 + 10)

Extra Credit: As noted on the Project Euler page, you can solve this using a brute force method, but it's incredibly inefficient. Specifically, a brute force solution would be O(2ⁿ) time (exponential). There exists a solution that can be solved in O(n²) time (quadratic). Find this solution.

What are some of your favorite videos that explain deep topics in depth?

I've recently been on a 3blue1brown binge (youtube) and am looking for more videos of that ilk. Doesn't have to be a series or a consistent uploader, one off videos are sometimes the best. Just thought I'd ask ~comp if there's anything in particular that comes to mind.

This is in part inspired by the video posted by /u/Deimos in the Technical Goals section of Tildes, titled Simplicity Matters

By coding headphones I mean with active noise cancellation, to be focused on your work. However I'd like to have it more universal since i do play videogames in my freetime, so with a microphone would be best - Or should i have 2 sets for both activities?

Something below 100€ would be nice (naive yes, but I aint got much).

I looked at the Mixcder e7 on Amazon, which looked promising. Thoughts?

This is an adapted version of Talking Clock from /r/DailyProgrammer.

The point of this thread is to post your code for solving the task. Other will comment with feedback and new ideas. Post what language (and version, if relevant) your code is written in.

Task description

Your task is to translate a 24-hour formatted time to words.

Input description

An hour between 00 and 23 followed by a colon followed by a minute between 0 and 59.

Output description

The time expressed in words, in 12-hour format followed by "am" or "pm".

Sample input

00:00
01:30
12:05
14:01

Sample output

It's twelve am
It's one thirty am
It's twelve oh five pm
It's two oh one pm