Pachebel Canon Challenge

I used to volunteer at the Dobama Theater in Cleveland Heights for props under Mary Walsh from 1991-1995 starting at the show Hunting Cockroaches starring Diane Bradley.  What an incredible experience!  I did some lights then finally some acting for the Children’s Festival as an FBI agent.  I had to do a stage entrance by tumbling; I ripped open my pants and almost forgot my lines, but got thru it with flying colors.  The show ended with Pachebel’s Canon, which I had never heard before.  It was beautiful so I asked Mary what it was and I think she said “Taco Bell’s Cannon”.

Well, that chord progression stuck with me and well it should!  It’s stuck with many since its creation in the early 1600’s, about the time of Sir Isaac Newton!  Now, given that I am learning guitar, I thought that I’d learn it, but in every key.  Here is the chart.

pachelbel

The top line in the key of C is the easiest.  But every new line introduces you to a new chord.  Some are barre chords.  But most importantly, the new chord is “exactly the same but different” and you will be amazed at the patterns that you see develop as you learn each line.  For example the F chord on the guitar is just a barred E chord.  Duh, it’s obvious now, but until I started making my way thru the challenge, I didn’t see it.  And the revelations continued for me.

I was expecting that the overall Pachelbel sound would be conserved across keys.  It generally is, but each key has it’s own characteristic sound.  Try it!

You might think that the Pachebel chord transition would map out on the circle of fifths in some beautiful way.  It does orbit near the root, but it doubles back and there are discontinuities that Pythagorus would disapprove of.  No sexy geometry here.

1111111111Go figure.

 

Gemstones

HackerRank says this is easy, and it is.

The Challenge

John has discovered various rocks. Each rock is composed of various elements, and each element is represented by a lower-case Latin letter from ‘a’ to ‘z’. An element can be present multiple times in a rock. An element is called a gem-element if it occurs at least once in each of the rocks.

Given the list of rocks with their compositions, display the number of gem-elements that exist in those rocks.

Input Format

The first line consists of an integer, , the number of rocks.
Each of the next lines contains a rock’s composition. Each composition consists of lower-case letters of English alphabet.

Constraints

Each composition consists of only lower-case Latin letters (‘a’-‘z’).
length of each composition

Output Format

Print the number of gem-elements that are common in these rocks. If there are none, print 0.

Sample Input

3
abcdde
baccd
eeabg

Sample Output

2

Explanation

Only “a” and “b” are the two kinds of gem-elements, since these are the only characters that occur in every rock’s composition.

My Solution

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T=scanner.nextInt();
        Set<Character> allCs = new HashSet<>();
        List<Set> sets = new ArrayList<>(); 
        for (int t=0; t<T; t++) {
            char[] cs = scanner.next().toCharArray();
            Set<Character> set = new HashSet<Character>();
            for (char c : cs) {
                set.add(c);
                allCs.add(c);
            }
            sets.add(set);
        }
        int total=0;
        for (char c : allCs) {
            boolean gem = true;
            for (Set set : sets) {
                if (!set.contains(c)) {
                    gem = false;
                    break;
                }
            }
            if (gem) {
                total++;
            }
        }
        System.out.println(total);
    }
}

Love Letter Mystery

This one is so simple that actually typing it slowed me down.

The Challenge

James found a love letter his friend Harry has written for his girlfriend. James is a prankster, so he decides to meddle with the letter. He changes all the words in the letter into palindromes.

To do this, he follows two rules:

1. He can reduce the value of a letter, e.g. he can change d to c, but he cannot change c to d.
2. In order to form a palindrome, if he has to repeatedly reduce the value of a letter, he can do it until the letter becomes a. Once a letter has been changed to a, it can no longer be changed.

Each reduction in the value of any letter is counted as a single operation. Find the minimum number of operations required to convert a given string into a palindrome.

Input Format

The first line contains an integer , i.e., the number of test cases.
The next lines will contain a string each. The strings do not contain any spaces.

Constraints

length of string
All characters are lower case English letters.

Output Format

A single line containing the number of minimum operations corresponding to each test case.

Sample Input

4
abc
abcba
abcd
cba

Sample Output

2
0
4
2

Explanation

1. For the first test case, abc -> abb -> aba.
2. For the second test case, abcba is already a palindromic string.
3. For the third test case, abcd -> abcc -> abcb -> abca = abca -> abba.
4. For the fourth test case, cba -> bba -> aba.

My solution

import java.io.*;
import java.util.*;

public class Solution {

    static class TestCase {
        
        private final char[] cs;
        
        TestCase(Scanner scanner) {
            cs = scanner.next().toCharArray();            
        }
        
        int solve() {
            int start = 0; 
            int stop = cs.length-1;
            int total = 0;
            while (start < stop-1) {
                total += Math.abs(cs[stop]-cs[start]);
                start++;
                stop--;
            }
            if (stop != start) {
                total += Math.abs(cs[stop]-cs[start]);
            }
            return total;
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int t = 0; t < T; t++) {
            System.out.println(new TestCase(scanner).solve());
        }
    }
}

Two Strings

HackerRank has a “moderate” challenge called Two Strings.  It must be a mistake because it is trivial.  Thanks for the easy points!

The Challenge:

You are given two strings, S1 and S2. Find if there is a substring that appears in both S1 and S2.

 

Input Format

Several test cases will be given to you in a single file. The first line of the input will contain a single integer , the number of test cases.

Then there will be descriptions of the test cases. Each description contains two lines. The first line contains the string and the second line contains the string .

 

Output Format

For each test case, display YES (in a newline), if there is a common substring. Otherwise, display NO.

Constraints

All the strings contain only lowercase Latin letters.

Sample Input

2
hello
world
hi
world

Sample Output

YES
NO

Explanation

 

For the 1^st test case, the letter o is common between both strings, hence the answer YES. (Furthermore, the letter l is also common, but you only need to find one common substring.)
For the 2^nd test case, hi and world do not have a common substring, hence the answer NO.

My solution:

import java.io.*;
import java.util.*;

public class Solution {

    static class TestCase {

        char[] cs1,cs2;

        public TestCase(Scanner scanner) {
            cs1 = scanner.next().toCharArray();
            cs2 = scanner.next().toCharArray();
        }

        public String hasCommonCharacter() {
            Set<Character> set = new HashSet<>();
            for (char c :cs1) {
                set.add(c);
            }
            for (char c :cs2) {
                if (set.contains(c)) return "YES";
            }
            return "NO";
        }
    }

    public static void main(String[] args) {
        
        Scanner scanner = new Scanner(System.in);
        int T=scanner.nextInt();
        for (int t=0; t<T; t++) {
            System.out.println(new TestCase(scanner).hasCommonCharacter());
        }
    }
}

Palindrome Index

HackerRank has a challenge that is categorized as easy, but there is a twist that hung me up for a little while.  This test case was my bottleneck:

hgygsvlfwcwnswtuhmyaljkqlqjjqlqkjlaymhutwsnwcflvsgygh should return 8

So it’s not so trivial that it isn’t fun to try.

Here is the challenge:

Given a string, S, of lowercase letters, determine the index of the character whose removal will make S a palindrome. If is already a palindrome or no such character exists, then print -1. There will always be a valid solution, and any correct answer is acceptable. For example, if S=“bcbc”, we can either remove ‘b’ at index 0 or ‘c’ at index 3.

 

Input Format

The first line contains an integer,T , denoting the number of test cases.
Each line of the subsequent lines (where 0<=i<T) describes a test case in the form of a single string, Si.

 

Constraints

• All characters are lowercase English letters.
• 1 <=T<=20
• 1<=|S| <=10^5 + 5

 

Output Format

Print an integer denoting the zero-indexed position of the character that makes not a palindrome; if is already a palindrome or no such character exists, print .

 

Sample Input

3
aaab
baa
aaa

Sample Output

3
0
-1

Explanation

Test Case 1: “aaab”
Removing ‘b’ at index results in a palindrome, so we print on a new line.

Test Case 2: “baa”
Removing ‘b’ at index results in a palindrome, so we print on a new line.

Test Case 3: “aaa”
This string is already a palindrome, so we print ; however, , , and are also all acceptable answers, as the string will still be a palindrome if any one of the characters at those indices are removed.

Here is my solution:

import java.io.*;
import java.util.*;

public class Solution {
    static class TestCase {      
        final char[] cs;
        public TestCase(Scanner scanner) {
            String cand = scanner.next();
            cs=cand.toCharArray();
        }
        public int calc() {
            int beg=0,end=cs.length-1,retval=-1;
            while(beg < end+1) {
                //System.out.println("Comparing indices beg:end="+beg+":"+end);
                if (cs[beg] != cs[end]) {
                    //System.out.println("Fixing: "+cs[beg]+"!="+cs[end]);
                    if (retval != -1) {
                        return -1; // too many mismatches
                    } 
                    // mismatch - which one to remove?
                    if (cs[beg] == cs[end-1] && cs[beg+1] == cs[end-2]) {
                            //System.out.println("Removing end "+end);
                            retval = end;
                            end--;
                        
                    }
                    else if (cs[beg+1] == cs[end] &&cs[beg+2] == cs[end-1]) {
                            retval = beg;
                            //System.out.println("Removing beg "+beg);
                            beg++;
                    }
                    else {
                        //System.out.println("Can't fix ");
                        return -1;
                    }
                }
                beg++;
                end--;
            }
            if (cs[beg] != cs[end]) {
                return beg;
            }
            return retval;
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T=scanner.nextInt();
        for (int t=0; t<T; t++) {
            System.out.println(new TestCase(scanner).calc());
        }
    }
}