Planet Scheme

September 20, 2019

Programming Praxis

What Comes Next?

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.

by programmingpraxis at September 20, 2019 09:00 AM

September 17, 2019

Programming Praxis

Getopt

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.

by programmingpraxis at September 17, 2019 09:00 AM

September 10, 2019

Programming Praxis

Alchemical Reduction

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.

by programmingpraxis at September 10, 2019 09:00 AM

September 06, 2019

Programming Praxis

Semi-Primes

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.

by programmingpraxis at September 06, 2019 09:00 AM

September 03, 2019

Programming Praxis

Date Conversion

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.

by programmingpraxis at September 03, 2019 09:00 AM

August 30, 2019

Programming Praxis

Numbers With 3 Divisors

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.

by programmingpraxis at August 30, 2019 09:00 AM

August 27, 2019

Programming Praxis

Powers Of 3

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.

by programmingpraxis at August 27, 2019 09:00 AM

August 23, 2019

Programming Praxis

Sexy Primes

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.

by programmingpraxis at August 23, 2019 09:00 AM

August 20, 2019

Programming Praxis

Sum Distinct Items

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.

by programmingpraxis at August 20, 2019 09:00 AM

August 16, 2019

Programming Praxis

Last Man Standing

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.

by programmingpraxis at August 16, 2019 09:00 AM

August 13, 2019

Programming Praxis

Round To 5

Every morning when I drive to work the highway signs display commute information: 7 minutes to Manchester Road, 11 minutes to Olive Blvd, speed ahead 55 mph. That’s little comfort when I’m sitting still on the highway. The “speed ahead” calculation is always rounded to the nearest 5 mph; the Department of Transportation takes a bunch of speed readings from sensors buried in the pavement and averages them.

Your task is to take a list of speed readings and average them to the nearest 5 mph. 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.

by programmingpraxis at August 13, 2019 09:09 AM

August 09, 2019

Programming Praxis

A Triangular Sequence

Consider the triangle:

1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
...

When the triangle is flattened, it produces the sequence (1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 …).

Your task is to write a program to generate the flattened sequence, and a second program to calculate the nth item in the sequence. 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.

by programmingpraxis at August 09, 2019 09:00 AM

August 06, 2019

Programming Praxis

Program Cross-Referencing

I’ve been writing a lot of Awk code at work lately; Awk is an acceptable language where I work, Scheme is not. One of my Awk programs got big enough that I needed a cross-referencer, so I pulled out the one on the next page from my dusty archives. It’s thirty years old, and still works! I was amazed. Though I guess I’ll have to update the list of keywords, because Gawk, which we use where I work, has many more keywords than Awk did thirty years ago.

Your task is to write a cross-referencer for your favorite language. 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.

by programmingpraxis at August 06, 2019 09:00 AM

August 02, 2019

Programming Praxis

Friday Fun

I wish I thought of this:

I came up with a single pass O(n) sort algorithm I call StalinSort. You iterate down the list of elements checking if they’re in order. Any element which is out of order is eliminated. At the end you have a sorted list.

Your task is to implement StalinSort. 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.

by programmingpraxis at August 02, 2019 09:00 AM

July 30, 2019

Programming Praxis

CsvSplit

There was a question the other day on Reddit or Stack Overflow or someplace about handling CSV files with awk. We’ve done that in a previous exercise, but today I decided to handle CSV files in a different way. Specifically, I wrote an awk function csvsplit that works the same way as awk’s built-in split function except that it handles CSV strings instead of splitting on a regular expression:

n = csvsplit(str,arr)

Csvsplit takes a string and an array, deletes any current contents of the array, splits the string into fields using the normal CSV rules, stores the fields in arr[1] .. arr[n], and returns n. The splitting rules are: every comma splits a field, except that double-quotes around a field protect commas inside the field, and double-quotes may appear in a quoted field by doubling them (two successive double-quotes).

Your task is to write a csvsplit function 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.

by programmingpraxis at July 30, 2019 09:00 AM