dev.to staff

Posted on Dec 12, 2019

Daily Challenge #136 - The Deaf Rats of Hamelin

#challenge

Story

The Pied Piper has been enlisted to play his magical tune and coax all the rats out of town.

But some of the rats are deaf and are going the wrong way!

How many deaf rats are there?

Legend

P = The Pied Piper
O~ = Rat going left
~O = Rat going right

Example

ex1 ~O~O~O~O P has 0 deaf rats
ex2 P O~ O~ ~O O~ has 1 deaf rat
ex3 ~O~O~O~OP~O~OO~ has 2 deaf rats

This challenge comes from dinglemouse on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Top comments (8)

Nick Holmes • Dec 13 '19

Thanks for the feedback. With a little inspiration from Avalander's Scala solution, I've got it what I had in mind in the first place.

let deafRats (s:string)=
    let rec inner s piper deaf =
        match s with
        | [] -> deaf
        | 'P' :: tail -> inner tail 1 deaf
        | 'O' :: '~' :: tail -> inner tail piper (deaf + 1 - piper)
        | '~' :: 'O' :: tail -> inner tail piper (deaf + piper)
        | _ :: tail -> inner tail piper deaf

    inner [for c in s -> c] 0 0

Avalander • Dec 13 '19

Nice math trick with the piper, hadn't thought of that!

Nick Holmes • Dec 12 '19 • Edited

Done very quickly, but works.

let deafRats s=
    let rec inner s (piper, deaf) =
        if s = "" then
            deaf
        else
            match s.[0..1] with
            | x when x.[0] = 'P' -> inner s.[1..] (1, deaf)
            | "O~" -> inner s.[2..] (piper, deaf + (1-piper))
            | "~O" -> inner s.[2..] (piper, deaf + piper)
            | _ -> inner s.[1..] (piper, deaf)

    inner s (0, 0)

Avalander • Dec 13 '19 • Edited

Slightly over-engineered solution in Scala.

object Hamelin {
  trait Character
  case object Piper extends Character
  case object Left extends Character
  case object Right extends Character

  type Town = Seq[Character]

  def of (raw: String): Town = {
    @tailrec
    def iter (chars: Seq[Char], result: Town = List()): Town =
      chars match {
        case Nil              => result
        case 'P' :: xs        => iter(xs, result :+ Piper)
        case 'O' :: '~' :: xs => iter(xs, result :+ Left)
        case '~' :: 'O' :: xs => iter(xs, result :+ Right)
        case _ :: xs          => iter(xs, result)
      }
    iter(raw.toList)
  }

  def countDeafRats (town: Town): Int = {
    val (result, _) = town.foldLeft((0, false)) {
      case ((x, _), Piper)     => (x, true)
      case ((x, false), Left)  => (x + 1, false)
      case ((x, true), Right)  => (x + 1, true)
      case (x, _)              => x
    }
    result
  }

  val solve = countDeafRats _ compose of _
}

And the tests:

class HamelinTest extends FunSuite {
  trait Input {
    val raw1 = "~O~O~O~O P"
    val raw2 = "P O~ O~ ~O O~"
    val raw3 = "~O~O~O~OP~O~OO~"
  }

  trait Parsed {
    val parsed1 = List(Right, Right, Right, Right, Piper)
    val parsed2 = List(Piper, Left, Left, Right, Left)
    val parsed3 = List(Right, Right, Right, Right, Piper, Right, Right, Left)
  }

  test("of") {
    new Input with Parsed {
      assert(of(raw1) == parsed1)
      assert(of(raw2) == parsed2)
      assert(of(raw3) == parsed3)
    }
  }

  test("countDeafRats") {
    new Parsed {
      assert(countDeafRats(parsed1) == 0)
      assert(countDeafRats(parsed2) == 1)
      assert(countDeafRats(parsed3) == 2)
    }
  }

  test("solve") {
    new Input {
      assert(solve(raw1) == 0)
      assert(solve(raw2) == 1)
      assert(solve(raw3) == 2)
    }
  }
}

Sabin Pandelovitch • Dec 13 '19

Using javascript

const examples = [
  "~O~O~O~O P",
  "P O~ O~ ~O O~",
  "~O~O~O~OP~O~OO~",
  "O~ O~~OPO~~O O~"
];

const putSpaces = item => item.replace(/(.{2})/g, "$1 ");
const getDeafRats = example => {
  const [leftPad, rightPad] = example.replace(/\s+/g, "").split("P");

  return (
    (putSpaces(leftPad).match(/O~/g) || []).length +
    (putSpaces(rightPad).match(/~O/g) || []).length
  );
};

const totalDeafRats = examples.reduce(
  (total, result) => total + getDeafRats(result),
  0
);
console.log("Total", totalDeafRats);
console.log("For each example", examples.map(getDeafRats));

CodeSandbox example

Simon Landry • Dec 13 '19

Using Ruby and Regex

def count_deaf_rats(input)
  deaf_count = 0
  while input =~ /~O|O~/
    if input =~ /~O\s*P|P\s*O~/
      input = input.gsub(/~O\s*P|P\s*O~/, 'P')
    end

    if input =~ /O~\s*P|P\s*~O/
      input = input.gsub(/O~\s*P|P\s*~O/, 'P')
      deaf_count += 1
    end
  end

  deaf_count
end

examples = [
  '~O~O~O~O P',
  'P O~ O~ ~O O~',
  '~O~O~O~OP~O~OO~'
]

examples.each_with_index do |ex, idx|
  puts "ex#{idx + 1} #{ex} has #{count_deaf_rats(ex)} deaf rats"
end

Output:

ex1 ~O~O~O~O P has 0 deaf rats
ex2 P O~ O~ ~O O~ has 1 deaf rats
ex3 ~O~O~O~OP~O~OO~ has 2 deaf rats

Thibaut Patel • Dec 16 '19

Here is my javascript walkthrough, I've used repl.it for the first time and it felt like a great use case.

Let me know if the video helps you!

erezwanderman • Dec 13 '19

deaf = town => [...town].filter((x, i, a) => x === 'O' && ((a[i + 1] ==='~' && i < a.indexOf('P')) || (a[i - 1] ==='~' && i > a.indexOf('P')))).length

DEV Community

Daily Challenge #136 - The Deaf Rats of Hamelin

Top comments (8)

Read next

AIM Weekly for 04Nov2024

Some Free API for Front-end Projects </>

End to End Data Engineering OTP Pipeline Project

Building a Regex Engine in Go: Introducing MatchGo