Programming Forums > Application Development > Software Design and Algorithms

Sane · Oct 7th, 2008, 3:22 PM

Attached to this post is the test data for Eliminanagram.

Eliminanagram (Beginner)

The nice thing about this problem is there are many different ways to solve it.

Since the problem requires use of basic counting techniques and manipulating strings, the problem is fairly open to different approaches. Some approaches are easier than others, but all are just as correct.

Here is one approach, directly derived from the problem.

You are given the definition of an Eliminanagram, and all you need to do is apply the logic to test if the two words satisfy the definition.

That process will look something like:

- Take the first letter in the first word
- Look for it somewhere else in the first or second word
- If it can't be found, then the word is not an eliminangram
- If it can be found, then delete both occurrences and repeat
- If there are still letters left over in the second word then repeat this process again taking the first letter from the second word
- If no letters remain, then the word is an eliminanagram

This will get you full points. But we are doing a lot more work than we need to, and can make various observations to turn this into a very simple task:

Observation #1:

isEliminanagram?( a, b ) <==> isEliminanagram?( a+b, "" )

What does that mean? If a and b are an eliminanagram, then the combined string a+b with the empty string "" must be an eliminanagram.

Why? From our definition, it doesn't matter what word we pick the duplicates from. So moving letters to and from each word is okay. Therefore, moving the entire second word to the first word must also be okay.

Observation #2:

If any letter occurs an odd number of times, then it can not be fully eliminated.

Why? From our definition, any letter can only be eliminated by matching it with the same letter elsewhere. So letters can only be eliminated in duplicate pairs.

Thus, for any letter there must be a total of 2*k occurrences of that letter, for some positive integer k, or else the letter can not be eliminated.

Note that a number of the form x=2*k, means x is an even number. In other words, x mod 2 == 0.

Conclusion:

From these two observations, we obtain the following algorithm:

- Combine the input into a single string (By Observation 1)
- Make sure that each letter appears an even number of times
- The above is satisfied if and only if the two words are eliminanagrams (By Observation 2)

Interestingly enough, the two people who used this algorithm got perfect. The others had longer solutions derived from the definition, so they missed a couple cases for not handling the tiny nuances of the implementation. I think this clearly demonstrates the benefit of breaking down problems into something simpler to solve.

Freaky Chris's perfect solution in Python:

 Python Syntax (Toggle Plain Text) 
inFile = open("elimi.in", "r")
outFile = open("elimi.out", "w")
words = ""
 
for lines in inFile:
    words += lines
 
for letters in words:
    if letters != '\n':
        if (words.count(letters) % 2) == 0:
            z = 1
        else:
            z = 0
            break       
 
if z == 1:
    outFile.write("Yes\n")
else:
    outFile.write("No\n")
 
inFile.close()
outFile.close()
inFile = open("elimi.in", "r")
outFile = open("elimi.out", "w")
words = ""

for lines in inFile:
    words += lines

for letters in words:
    if letters != '\n':
        if (words.count(letters) % 2) == 0:
            z = 1
        else:
            z = 0
            break       

if z == 1:
    outFile.write("Yes\n")
else:
    outFile.write("No\n")

inFile.close()
outFile.close()

Arla's perfect solution in Java:

 Java Syntax (Toggle Plain Text) 
package eliminagram;
 
import java.io.*;
 
public class Eliminagram {
 
	public static boolean eliminanagram(String input)
	{
		//First check the length of the input, if it's not divisible by two it can't possibly be an eliminanagram
		if ((input.length() % 2) != 0)
			return false;
		//Java defaults each value in a new array to 0
		int[] alphabet = new int[26];
		int value;
		for (char c: input.toCharArray())
		{
			value = c - 97;
			if (value >= 0 & value <27)
				alphabet[value]++;
			else
				//If any values are outside of the expected range, return false
				return false;
		}
		//Now we have made a count of all the values, simply check each is divisible by 2
		for (int i: alphabet)
			if ((i % 2)!=0) return false;
		//If we've got to here, ever letter is divisible by 2, therefore this is an eliminanagram, return true;
		return true;
	}
 
	public static void main(String[] args) {
		// Get the input, should be two text strings
		try 
		{
			int inputCount =0;
			String text;
			String allTogether = "";
			BufferedReader in = new BufferedReader(new FileReader("elimi.in"));
			while ((text = in.readLine()) != null)
			{
				inputCount++;
				allTogether+=text;
			}
			if (inputCount!=2)
				System.out.println("Unexpected number of input text strings in input file, program aborting");
			else
			{
				//Now we have enough to check for whether this is an Eliminanagram
				boolean isEliminanagram = eliminanagram(allTogether);
				try
				{
					BufferedWriter out = new BufferedWriter(new FileWriter("elimi.out"));
					if (isEliminanagram)
						out.write("Yes\n");
					else
						out.write("No\n");
					out.close();
				}
				catch (Exception e)
				{
					e.printStackTrace();
				}
			}
			//Now close the input since we are done with it
			in.close();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}
 
}
package eliminagram;

import java.io.*;

public class Eliminagram {

	public static boolean eliminanagram(String input)
	{
		//First check the length of the input, if it's not divisible by two it can't possibly be an eliminanagram
		if ((input.length() % 2) != 0)
			return false;
		//Java defaults each value in a new array to 0
		int[] alphabet = new int[26];
		int value;
		for (char c: input.toCharArray())
		{
			value = c - 97;
			if (value >= 0 & value <27)
				alphabet[value]++;
			else
				//If any values are outside of the expected range, return false
				return false;
		}
		//Now we have made a count of all the values, simply check each is divisible by 2
		for (int i: alphabet)
			if ((i % 2)!=0) return false;
		//If we've got to here, ever letter is divisible by 2, therefore this is an eliminanagram, return true;
		return true;
	}
	
	public static void main(String[] args) {
		// Get the input, should be two text strings
		try 
		{
			int inputCount =0;
			String text;
			String allTogether = "";
			BufferedReader in = new BufferedReader(new FileReader("elimi.in"));
			while ((text = in.readLine()) != null)
			{
				inputCount++;
				allTogether+=text;
			}
			if (inputCount!=2)
				System.out.println("Unexpected number of input text strings in input file, program aborting");
			else
			{
				//Now we have enough to check for whether this is an Eliminanagram
				boolean isEliminanagram = eliminanagram(allTogether);
				try
				{
					BufferedWriter out = new BufferedWriter(new FileWriter("elimi.out"));
					if (isEliminanagram)
						out.write("Yes\n");
					else
						out.write("No\n");
					out.close();
				}
				catch (Exception e)
				{
					e.printStackTrace();
				}
			}
			//Now close the input since we are done with it
			in.close();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}

}

The official solution in Python:

 Python Syntax (Toggle Plain Text) 
dat = open("elimi.in", "r").read()
text = ''.join(dat.split('\n')[:2])
 
def go(text):
    for l in text:
        if(text.count(l)%2 != 0):
            return "No"
    return "Yes"
 
f = open("elimi.out", "w")
f.write("%s\n"%go(text))
f.close()
dat = open("elimi.in", "r").read()
text = ''.join(dat.split('\n')[:2])

def go(text):
    for l in text:
        if(text.count(l)%2 != 0):
            return "No"
    return "Yes"

f = open("elimi.out", "w")
f.write("%s\n"%go(text))
f.close()

Weird Fishes · Oct 7th, 2008, 4:33 PM

Damn. I just checked my answers and I figured out where I went wrong. After I found a match I reset a for loop variable to one, but then the for loop went again and it bumped it up to 2. So what separated me from perfect was: x = 1; instead of x = 0;

Oh well.

Arla · Oct 7th, 2008, 5:17 PM

Don't ya hate it when that happens...

I had a large piece of code go fairly wrong because it had <= in it instead of <

It was the suck! (using my best l33t speak)

Weird Fishes · Oct 7th, 2008, 5:19 PM

Yeah. One time for robotics, the project wouldn't build because a file needed a newline at the end. Took forever to figure out the problem.

Arla · Oct 7th, 2008, 5:26 PM

Quote:

Originally Posted by Weird Fishes

Yeah. One time for robotics, the project wouldn't build because a file needed a newline at the end. Took forever to figure out the problem.

Eh, better than it compiling but not working the way you expected, those are much tougher, at least without a compile you're not going anywhere, when it compiles but is missing one line, or a break, or something like that and does something totally wrong it's really hard to spot at times.

Weird Fishes · Oct 7th, 2008, 5:31 PM

Quote:

Originally Posted by Arla

Eh, better than it compiling but not working the way you expected, those are much tougher, at least without a compile you're not going anywhere, when it compiles but is missing one line, or a break, or something like that and does something totally wrong it's really hard to spot at times.

Yeah, we (I) get plenty of that there too.

Things like, it won't actuate or it will drive forward unless button a and button b are pressed and...... Just awful.

Freaky Chris · Oct 8th, 2008, 4:55 AM

My first perfect lol, shame its in beginner. And yet i can't even get any form of solution to the other problems, o well.

well done guys

Chris

Sane · Oct 8th, 2008, 11:16 AM

Quote:

Originally Posted by Weird Fishes

Damn. I just checked my answers and I figured out where I went wrong. After I found a match I reset a for loop variable to one, but then the for loop went again and it bumped it up to 2. So what separated me from perfect was: x = 1; instead of x = 0;

Oh well.

Yeah, that happens. I'm surprised the tests even found it. That's a very minor error that only hurts you 1/10th of the time.

The funny part is the one test file it didn't work on was the very first example in the PDF.

(Toggle Plain Text)

mississippi
mamma

If you had tested it on all the examples in the PDF you would have caught it.

Freaky Chris · Oct 8th, 2008, 11:52 AM

Quote:

Originally Posted by Sane

Yeah, that happens. I'm surprised the tests even found it. That's a very minor error that only hurts you 1/10th of the time.

The funny part is the one test file it didn't work on was the very first example in the PDF.

(Toggle Plain Text)

mississippi
mamma

If you had tested it on all the examples in the PDF you would have caught it.

Ouch thats even more of a slap in the face

Weird Fishes · Oct 8th, 2008, 3:51 PM

Oh well.

I thought I did... guess not.

Oct 7th, 2008, 5:17 PM	#3
Arla Professional Programmer Join Date: Mar 2005 Posts: 407 Rep Power: 4	Re: SMAC #4 [09-08] - Eliminanagram (Beginner) Don't ya hate it when that happens... I had a large piece of code go fairly wrong because it had <= in it instead of < It was the suck! (using my best l33t speak)

Oct 7th, 2008, 5:19 PM	#4
Weird Fishes Hobbyist Programmer Join Date: Aug 2008 Location: Ontario Posts: 177 Rep Power: 1	Re: SMAC #4 [09-08] - Eliminanagram (Beginner) Yeah. One time for robotics, the project wouldn't build because a file needed a newline at the end. Took forever to figure out the problem. __________________ What can you put in a bucket full of water to make it lighter?

Oct 8th, 2008, 4:55 AM	#7
Freaky Chris Expert Programmer Join Date: Dec 2007 Location: England Posts: 541 Rep Power: 2	Re: SMAC #4 [09-08] - Eliminanagram (Beginner) My first perfect lol, shame its in beginner. And yet i can't even get any form of solution to the other problems, o well. well done guys Chris __________________ Steven Skiena - Algorithms `,[->+>+<<]>>[-<<+>>]>++++++++[-<++++++++>]<+[-<->]>+<<[[-]+++++++++++++++.[-]>]>>[+++++++++.[-]],` brainf**k -- It's such a pretty language

Oct 8th, 2008, 3:51 PM	#10
Weird Fishes Hobbyist Programmer Join Date: Aug 2008 Location: Ontario Posts: 177 Rep Power: 1	Re: SMAC #4 [09-08] - Eliminanagram (Beginner) Oh well. I thought I did... guess not. __________________ What can you put in a bucket full of water to make it lighter?

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Oct 7th, 2008, 4:33 PM	#2
Weird Fishes Hobbyist Programmer Join Date: Aug 2008 Location: Ontario Posts: 177 Rep Power: 1	Re: SMAC #4 [09-08] - Eliminanagram (Beginner) Damn. I just checked my answers and I figured out where I went wrong. After I found a match I reset a for loop variable to one, but then the for loop went again and it bumped it up to 2. So what separated me from perfect was: x = 1; instead of x = 0; Oh well. __________________ What can you put in a bucket full of water to make it lighter?

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
SMAC #3 [07-08] - Results	Sane	Software Design and Algorithms	4	Aug 6th, 2008 8:23 PM
SMAC #3 [07-08] - Julius Caesar (Beginner)	Sane	Software Design and Algorithms	0	Aug 6th, 2008 11:41 AM
SMAC #2 [06-08] - Swapping Stories (Beginner)	Sane	Software Design and Algorithms	1	Jul 1st, 2008 2:35 PM
SMAC #1 [05-08] - Mobile (Beginner) and "n Reach k" (Junior)	Sane	Software Design and Algorithms	2	Jun 3rd, 2008 9:10 AM
SMAC #1 [05-08] - Results	Sane	Software Design and Algorithms	6	Jun 2nd, 2008 5:56 PM

Programming Forums > Application Development > Software Design and Algorithms

SMAC #4 [09-08] - Eliminanagram (Beginner)