Potholes

May 11, 2021

It is wrong to predefine the three-unit lengths of road where the pothole fixing machine can set up. Our solution scans until it finds a pothole, fixes that pothole plus any potholes in the next two units of road, then begins rescanning at the third subsequent unit of road:

(define (potholes str)
  (let ((len (string-length str)))
    (let loop ((i 0) (fixes 0))
      (cond ((<= len i) fixes)
            ((char=? (string-ref str i) #\X)
              (loop (+ i 3) (+ fixes 1)))
            (else (loop (+ i 1) fixes))))))
> (potholes ".X.")
1
> (potholes ".X...X")
2
> (potholes "XXX.XXXX")
3
> (potholes ".X.XX.XX.X")

You can run the program at https://ideone.com/XueE9y.

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