Potholes

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

Posted by programmingpraxis
Filed in Exercises
4 Comments »

4 Responses to “Potholes”

  1. Iulia said
    May 11, 2021 at 3:53 PM

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

  2. chaw said
    May 11, 2021 at 4:01 PM

    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
    library.

    (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))))
(newline)

  3. r. clayton said
    June 5, 2021 at 5:20 AM

    A solution in Racket.

  4. Daniel said
    June 21, 2021 at 8:27 PM

    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') {
      ++count;
      i += 2;
    }
  }
  printf("%d\n", count);
  return EXIT_SUCCESS;
}

    Example usage:

    $ ./a.out .X.
1

$ ./a.out .X...X
2

$ ./a.out XXX.XXXX
3

$ ./a.out .X.XX.XX.X
3

Leave a comment