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.
Programming Praxis 
potholes = go 0
where
go n (‘X’:rest) = go (n+1) (drop 2 rest)
go n (_:rest) = go n rest
go n [] = n
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)A solution in Racket.
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: