DEV Community

dev.to staff
dev.to staff

Posted on

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)

Collapse
 
nickholmesde profile image
Nick Holmes •

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
Enter fullscreen mode Exit fullscreen mode
Thread Thread
 
avalander profile image
Avalander •

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

Collapse
 
nickholmesde profile image
Nick Holmes • • Edited

Done very quickly, but works.

F#

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)
Enter fullscreen mode Exit fullscreen mode
Collapse
 
sabbin profile image
Sabin Pandelovitch •

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

Collapse
 
avalander profile image
Avalander • • 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) } } }
Collapse
 
hyftar profile image
Simon Landry •

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
Collapse
 
thibpat profile image
Thibaut Patel •

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!

Collapse
 
erezwanderman profile image
erezwanderman •

JS

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