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.

Advertisements

Pages: 1 2

Round To 5

August 13, 2019

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.

Pages: 1 2

A Triangular Sequence

August 9, 2019

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.

Pages: 1 2

Program Cross-Referencing

August 6, 2019

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.

Pages: 1 2

Friday Fun

August 2, 2019

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.

Pages: 1 2

CsvSplit

July 30, 2019

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.

Pages: 1 2

Twin Primes

July 26, 2019

According to number theory:

m is the base of a twin-prime pair (m, m+2) if and only if 4((m−1)! + 1) == –m (mod m (m+2)).

Your task is to write a program that implements the criterion given above, then calculate the twin primes less than a thousand. 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

Homework

July 23, 2019

Today’s exercise comes from somebody’s homework assignment:

Write a program that fills a 50-element array with random numbers from 1 to 10. Print the array. Calculate and print the sum of the random numbers in the array. Calculate and print the number of times that a particular number appears in the array.

Your task is to complete the homework problem described above. 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

Interactive Diff

July 12, 2019

[ There will be no exercises next week, as my daughter is visiting from out-of-town and I will be spending time with her. ]

One of my favorite books is The Unix Programming Environment by Brian Kernighan and Rob Pike, which I have recently been re-reading; the spine of my copy broke long ago, so I must be careful turning the pages, and I wrap the book in a rubber band every time I put it back on my shelf. It is an excellent introduction to Unix, still relevant today even though it was published in 1984. The recent exercise Remind was inspired by a program in Section 4.4, and today’s exercise is a rewrite of the program in Section 6.8.

NAME

    idiff -- interactive diff

USAGE

    idiff file1 file2 -- interactively merge file differences

DESCRIPTION

    idiff takes two files file1 and file2, diffs them, and presents
    the difference to the user interactively. At each difference,
    the user may accept the text from file1 by responding <, or     accept the text from file2 by responding >, or edit the difference
    by responding e (in which case whatever the user saves from the
    editor is entered into the output file), or execute a command
    by typing !cmd, in which case the user must then respond when
    the prompt is repeated. The assembled output with the selected
    differences is placed in file idiff.out.

EXAMPLE

    $ cat file1
    This is
    a test
    of
    your
    skill
    and comprehension.
    $ cat file2
    This is
    not a test
    of
    our
    ability.
    $ diff file1 file2
    2c2
    < a test     ---     > not a test
    4,6d4,5
    < your
    < skill
    < and comprehension.     ---     > our
    > ability.
    $ idiff file1 file2
    2c2
    < a test     ---     > not a test
    ? >
    4,6c4,5
    < your
    < skill
    < and comprehension.     ---     > our
    > ability.
    ? <
    $ cat idiff.out
    This is
    not a test
    of
    your
    skill
    and comprehension.

[ WordPress is determined not to render less-than and greater-than signs properly. Look at https://ideone.com/nI9CNB if you can’t make sense of what you see. ]

Your task is to write idiff. 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

Doubled Letters

July 9, 2019

We have a fun little exercise on a lazy summer Tuesday:

Given a list of words, remove from the list those words that have two adjacent identical letters. For instance, given “Now is the time for all good men to come to the aid of their country” the program should remove the words “all” and “good”.

Your task is to write a program to remove words with doubled letters from a list of words. 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