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

3 Responses to “Potholes”

  1. Iulia said

    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

    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

    A solution in Racket.

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 )

Google photo

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

Twitter picture

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

Facebook photo

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

Connecting to %s

%d bloggers like this: