May 11, 2021

Today’s exercise comes from one of those online code exercises, via Stack Overflow:

There is a machine that can fix all potholes along a road 3 units in length. A unit of road will be represented by a period in a string. For example, “…” is one section of road 3 units in length. Potholes are marked with an “X” in the road, and also count as 1 unit of length. The task is to take a road of length N and fix all potholes with the fewest possible sections repaired by the machine.

The city where I live needs one of those machines.

Here are some examples:

.X.          1
.X...X       2
XXX.XXXX     3
.X.XX.XX.X   3

Your task is to write a program that takes a string representing a road and returns the smallest number of fixes that will remove all the potholes. 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

4 Responses to “Potholes”

  1. Iulia said

    potholes = go 0
    go n (‘X’:rest) = go (n+1) (drop 2 rest)
    go n (_:rest) = go n rest
    go n [] = n

  2. chaw said

    My first solution was almost identical to the one by
    @programmingpraxis so I omit it here and instead include, mostly for
    chuckles, a “one-liner” using that often-used and -misused hammer,
    regular expressions, in particular as implemented in the irregex

    (import (scheme base)
            (scheme write)
            (chibi irregex))
    (define samples ; ((input . output) ...)
      '((".X." . 1)
        (".X...X" . 2)
        ("XXX.XXXX" . 3)
        (".X.XX.XX.X" . 3)
        ("" . 0)
        (".........." . 0)
        (".........X" . 1)))
    (define (pothole-filling-sections/re str)
      (length (irregex-extract '(seq "X" (** 0 2 any)) str)))
    (display (equal? (map cdr samples)
                     (map pothole-filling-sections/re (map car samples))))

  3. r. clayton said

    A solution in Racket.

  4. Daniel said

    Here’s a solution in C.

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int main(int argc, char* argv[]) {
      if (argc != 2) return EXIT_FAILURE;
      int count = 0;
      int n = strlen(argv[1]);
      for (int i = 0; i < n; ++i) {
        if (argv[1][i] == 'X') {
          i += 2;
      printf("%d\n", count);
      return EXIT_SUCCESS;

    Example usage:

    $ ./a.out .X.
    $ ./a.out .X...X
    $ ./a.out XXX.XXXX
    $ ./a.out .X.XX.XX.X

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: