What Comes Next?

September 20, 2019

This is a Microsoft interview question:

What is the next number in the sequence: 8, 13, 17, 22, 24, 26, 29, 31, 35, …?

Your task is to solve the puzzle. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

Getopt

September 17, 2019

As I have said previously on this blog, I’m not allowed to write Scheme code at work; it would never make it past code review. But I can write shell scripts, and Awk is a natural language to use in shell scripts, so lately I have been writing a lot of Awk programs.

I recently had occasion to write an Awk program that took command-line arguments, so naturally I googled “getopt.awk” and found an implementation in the Gnu Awk manual. But that version of getopt was very C-like and not at all Awk-ish, so I decided to write my own. My getopt function extracts command-line arguments into an associative array OPTS that has the flag as its key and the value associated with the flag as its value; the value is null if the flag has no associated value. The getopt function takes two arguments — a string defining the available flags, in the same format as the C getopt function, and a string containing a message to be printed on error — and returns the number of arguments found.

Your task is to write a getopt function for your favorite langauge; if your language already provides command-line argument handling, write a version for Awk. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Alchemical Reduction

September 10, 2019

Today’s exercise is from the 2018 Advent of Code, Day 5:

You’ve managed to sneak in to the prototype suit manufacturing lab. The Elves are making decent progress, but are still struggling with the suit’s size reduction capabilities.

While the very latest in 1518 alchemical technology might have solved their problem eventually, you can do better. You scan the chemical composition of the suit’s material and discover that it is formed by extremely long polymers (one of which is available as your puzzle input).

The polymer is formed by smaller units which, when triggered, react with each other such that two adjacent units of the same type and opposite polarity are destroyed. Units’ types are represented by letters; units’ polarity is represented by capitalization. For instance, r and R are units with the same type but opposite polarity, whereas r and s are entirely different types and do not react.

For example:

– In aA, a and A react, leaving nothing behind.

– In abBA, bB destroys itself, leaving aA. As above, this then destroys itself, leaving nothing.

– In abAB, no two adjacent units are of the same type, and so nothing happens.

– In aabAAB, even though aa and AA are of the same type, their polarities match, and so nothing happens.

Now, consider a larger example, dabAcCaCBAcCcaDA:

dabAcCaCBAcCcaDA  The first 'cC' is removed.
dabAaCBAcCcaDA    This creates 'Aa', which is removed.
dabCBAcCcaDA      Either 'cC' or 'Cc' are removed (the result is the same).
dabCBAcaDA        No further actions can be taken.

After all possible reactions, the resulting polymer contains 10 units.

How many units remain after fully reacting the polymer you scanned?

Your task is to write a program that solves the alchemical reduction. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Semi-Primes

September 6, 2019

We have on several occasions seen functions for generating the primes less than n. Sometimes, what you want instead of primes are semi-primes, numbers which are the product of two primes. For instance, the six semi-primes less than 25 are 2×3=6, 2×5=10, 2×7=14, 3×5=15, 3×7=21 and 2×11=22.

Your task is to write a function that makes a list of the semi-primes less than n; use it to discover the number of semi-primes less than 10,000. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Date Conversion

September 3, 2019

Where I work, the accounting department does a survey of its vendors once a year, or every three years, or something, I’m not sure of the details. All of the vendors send CSV files with multiple rows, from a few rows to several hundred; each row contains 3 dates. Different vendors send dates in different formats: 9/3/19, 9-3-19, 09/03/2019, 3-SEP-19, “September 3, 2019” (quoted to protect the embedded comma), and even 09/03/2019T14:37:26.8493 (because every ten-thousandth of a second matters). That variety of formats caused problems for the accounting department, so they asked for help in reformatting the dates. Here is some sample data:

John,Smith,9/3/19,9-3-19,09/03/19,100
Sally,Jackson,3-SEP-19,"September 3, 2019",09/03/2019T14:37:26.8493,200

Your task is to write a program to convert dates from a variety of formats to the standard MM/DD/YYYY format. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Numbers With 3 Divisors

August 30, 2019

I saw this question on Stack Overflow a few days ago; it’s a well-known problem in number theory:

For a given number n, how many numbers less than n have exactly 3 divisors?

Your task is to write a program that counts the numbers less than n that have exactly 3 divisors, and use it to find the result when n is one billion. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Powers Of 3

August 27, 2019

This problem appeared on a beginning-programmers discussion list:

How can I determine if a number n is a power of 3?

Your task is to write a program to determine if a number is a power of 3. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Sexy Primes

August 23, 2019

A sexy prime is a prime number p for which p + 6 is also prime. Such primes are called sexy because the Latin word for six is sex.

Your task is to write a program that counts the sexy primes between one billion and two billion. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Sum Distinct Items

August 20, 2019

We have an interview question today:

In a list of integers, find the sum of the integers that appear only once. For instance, in the list [4 2 3 1 7 4 2 7 1 7 5], the integers 1, 2, 4 and 7 appear more than once, so they are excluded from the sum, and the correct anser is 3 + 5 = 8.

Your task is to write a program to find the sum of the distinct integers in a list. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Last Man Standing

August 16, 2019

Today’s exercise is a fun task for a lazy summer Friday:

Given a circular array X of positive integers and a starting index k of the array, delete the element at k and jump X[k] steps in the circular array. Repeat until only a single element remains. Find the last remaining element.

For example, with array 6 2 3 1 4 7 5 and k = 3, the last man standing is 3, computed as shown below, with the item to be deleted at each step marked with brackets and the list rotated at each step to bring the new head of the list to the front:

6 2 3 [1] 4 7 5
4 [7] 5 6 2 3
5 6 [2] 3 4
3 4 [5] 6
6 3 [4]
[6] 3
3

Your task is to write a program to find the last remaining element. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2