The Deaf Rats of Hamelin Challenge in Java

The challenge

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!

Task

How many deaf rats are there?

Legend

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

Examples

  • 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

The solution in Java code

Option 1:

public class DeafRatsOfHamelin {
    public static int countDeafRats(final String town) {
        String t = town.replaceAll(" ","");
        int count = 0;
        for (int i = 0 ; i < t.length() ; i+=2) if (t.charAt(i) == 'O') count++;
        return count;
    }
}

Option 2:

import java.util.stream.IntStream;

public class DeafRatsOfHamelin {
  public static int countDeafRats(final String town) {
    final String s = town.replaceAll("\\s+", "");
    return (int) IntStream.range(0, s.length()).filter(i -> s.charAt(i) == '~' && i%2 > 0).count();
  }
}

Option 3:

public class DeafRatsOfHamelin {
  public static int countDeafRats(final String town) {
    int DeafRats=0;   
    String CompactTown;   
    CompactTown = town.replace(" ","");
    for(int i=0;i<CompactTown.length();i+=2){   
        if(CompactTown.charAt(i) == 'O') DeafRats++;     
    }
    return DeafRats;
  }
}

Test cases to validate our solution

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

class DeafRatsOfHamelinTest {
    @Test
    public void ex1() {
        assertEquals(0, DeafRatsOfHamelin.countDeafRats("~O~O~O~O P"));
    }
    @Test
    public void ex2() {
        assertEquals(1, DeafRatsOfHamelin.countDeafRats("P O~ O~ ~O O~"));
    }
    @Test
    public void ex3() {
        assertEquals(2, DeafRatsOfHamelin.countDeafRats("~O~O~O~OP~O~OO~"));
    }
}

Additional test cases

import org.junit.Test;
import static org.junit.Assert.assertEquals;

public class SolutionTests {
  @Test
  public void ex1() {
    assertEquals(0, DeafRatsOfHamelin.countDeafRats("~O~O~O~O P"));
  }
  
  @Test
  public void ex2() {
    assertEquals(1, DeafRatsOfHamelin.countDeafRats("P O~ O~ ~O O~"));
  }
  
  @Test
  public void ex3() {
    assertEquals(2, DeafRatsOfHamelin.countDeafRats("~O~O~O~OP~O~OO~"));
  }

  @Test
  public void rats() {
    assertEquals(8, DeafRatsOfHamelin.countDeafRats("O~~OO~~OO~~OO~P~OO~~OO~~OO~~O"));
    assertEquals(8, DeafRatsOfHamelin.countDeafRats("O~~OO~~OO~~OO~ P~OO~~OO~~OO~~O"));
    assertEquals(8, DeafRatsOfHamelin.countDeafRats("O~~OO~~OO~~OO~P ~OO~~OO~~OO~~O"));
  }
  
  @Test
  public void highlander() {
    assertEquals(0, DeafRatsOfHamelin.countDeafRats("~OP"));
    assertEquals(0, DeafRatsOfHamelin.countDeafRats("PO~"));
    assertEquals(1, DeafRatsOfHamelin.countDeafRats("O~P"));
    assertEquals(1, DeafRatsOfHamelin.countDeafRats("P~O"));
  }

  @Test
  public void empty() {
    assertEquals(0, DeafRatsOfHamelin.countDeafRats("         P"));
    assertEquals(0, DeafRatsOfHamelin.countDeafRats("P         "));
    assertEquals(0, DeafRatsOfHamelin.countDeafRats("         P      "));
    assertEquals(0, DeafRatsOfHamelin.countDeafRats("P"));
  }

  // ====================================
  
  // Reference implementation for the Random test cases
  private static class DeafRatsOfHamelin {
  
    static int countDeafRats(final String town) {
      String s = "";
      for (int i = 0; i < town.length(); i++) {
        final char c = town.charAt(i);
        if (c == '~') { s += "R"; i ++; }
        else if (c == 'O') { s += "L"; i ++; }
        else if (c == 'P') { s += c; }
      }
      final String s1 = s.substring(0, s.indexOf("P")), s2 = s.substring(s.indexOf("P")+1);
      int deaf = 0;
      // Rats to left of the Piper should be going right
      deaf += s1.replace("R","").length();
      // Rats to right of the Piper should be going left
      deaf += s2.replace("L","").length();
      return deaf;
    }
  
  }
  
  private static String makeRatFacing(final char mostly) {
    final double d = Math.random() * 3;
    if (mostly == 'L') {
      // Mostly facing left
      if (d < 2.5) return "O~";
      if (d < 2.8) return "~O";
    } else {
      // Mostly facing right
      if (d < 2.5) return "~O";
      if (d < 2.8) return "O~";
    }
    return "  ";
  }
  
  private static String makeTown(char piperPos) {
    final int ratsLeft = (int)(Math.random() * 20) + 5;
    final int ratsRight = (int)(Math.random() * 20) + 5;
    String town = "";
    boolean piper = false;
    if (piperPos == 'L') { town += "P"; piper = true; }
    for (int r = 0; r < ratsLeft; r++) {
      town += makeRatFacing(piper ? 'L' : 'R');
    }
    if (piperPos == 'M') { town += "P"; piper = true; }
    for (int r = 0; r < ratsRight; r++) {
      town += makeRatFacing(piper ? 'L' : 'R');
    }
    if (piperPos == 'R') town += "P";
    return town;
  }
  
  @Test
  public void random() {
    for (int r = 1; r <= 200; r++) {
      final int p = (int)(Math.random() * 3);
      final char piper = p == 0 ? 'L' : p == 1 ? 'M' : 'R';
      final String town = makeTown(piper);
      final int expected = DeafRatsOfHamelin.countDeafRats(town);
      System.out.println(String.format("Random test %d : <span style='color:green'>%s</span> has %d deaf rats", r, town, expected));      
      assertEquals(expected, DeafRatsOfHamelin.countDeafRats(town));
    }
  }
}