[Dogstopper]

Welcome to the second function challenge! It is similar to the last one, but since it's New Years, I decided to shake it up a little bit. There are three problems, each progressing in difficulty. If you can, try all three. Thanks to mostyfriedman for the first two challenges!

*Note* This competition is always going to be available, but will be unpinned by January 15th.

---

Easy problem:

Given a set of integers represented as an array, print all the possible subsets of the set.
Example:
Input: {1, 2, 3}
Output:
[1, 2, 3]
[1, 2]
[1, 3]
[1]
[2, 3]
[2]
[3]
[]


Medium problem:

Given a string of characters, your job is to find a permutation of the string such that it is a palindrome, if more than one palindrome can be found, return the smallest one lexicographically. If no palindromes can be constructed, return "NOT FOUND".

examples:

Input:
"ABBAC"

Output:
"ABCBA"

Input:
"AB"

Output:
"NOT FOUND"

Hard Problem:

Document Distance

This is an easy problem if implemented a certain way compared to other potential ways. There are efficient methods and non-efficient methods of doing this. I have two documents attached - lewis.txt and Tom Sawyer.txt. Try to compare the Document Distance of these two files in the most efficient method possible.

You can find the methodology and information on Document Distance here:
http://www.andrew.cm...stance/lab.html

This process should take no longer than a minute or two to calculate.

Text files:
 lewis.txt (1007.29K)
Number of downloads: 105
 Tom Sawyer.txt (390.07K)
Number of downloads: 105

Good Luck!

_{If you have any ideas or suggestions for future challenges, feel free to PM me with it.}

This post has been edited by Dogstopper: 31 December 2010 - 08:13 PM

[Raynes]

(ns ctwo.core
  (:use [clojure.contrib.combinatorics :only [permutations subsets]]))

(defn find-palindrome [s]
  (if-let [result (first (filter #(= % (reverse %)) (permutations s)))]
    (apply str result)
    "NOT FOUND!"))

(defn find-subsets [coll]
  (doseq [sub (subsets coll)]
    (prn sub))) ; use prn because we want the collection printed all pretty-like.

My just-for-fun Clojure implementations of the first two problems.

First and foremost, I'm using a library in contrib for the hard parts. You never specified whether or not reader need to implement the relevant operations themselves. If this library wasn't in contrib, I wouldn't have bothered. Contrib libraries can sometimes make it into Clojure itself, thus what I used could be core functions in the future. Nonetheless, it's very apparent that I cheated and that it is easy to cheat. If you want to avoid these types of solutions, you might need to clarify. Before Adam gets his hands on it.

[mostyfriedman]

Here's my solution for the first 2 problems, I will post the third one later

Spoiler

recursive solution

public static void subsets(int [] arr, int i, Stack<Integer> sub)
{
        if(i >= arr.length)
        {
            System.out.println(sub);
            return;
        }
        
        sub.push(arr[i]);
        subsets(arr, i+1, sub);
        sub.pop();
        subsets(arr, i+1, sub);
}

public static void main(String[]args)
{
    subsets(new int[]{1, 2, 3}, 0, new Stack<Integer>());
}

Iterative one with some bit fiddling

public static void subsets(int [] arr)
{
        ArrayList<Integer> sub = new ArrayList<Integer>();
        int n = 1 << arr.length;
        int bits = 0;
        for(int i = 0; i < n; i++)
        {
            if((i & i-1) == 0 && i > 0)
                bits++;
                
            for(int j = 0; j < bits; j++)
            {
                if((i & 1 << j) != 0)
                {
                    sub.add(arr[j]);
                }
            }
            System.out.println(sub);
            sub.clear();
        }
}

2nd problem, the algorithm assumes the input will be all capital letters.

public static String makePalindrome(String baseString)
{
        int countOdd = 0;
        int [] alpha = new int[26];
        for(int i = 0; i < baseString.length(); i++)
        {
            alpha[baseString.charAt(i)-'A']++;
        }
        char odd = '\u0000';
        for(int i = 0; i < alpha.length; i++)
        {
                if(alpha[i]%2 != 0)
                {
                    odd = (char)(i+'A');
                    countOdd++;
                }
        }
        if(countOdd > 1)
            return "NOT FOUND";
        
        String prefix = "";
        String suffix = "";
        for(int i = 0; i < alpha.length; i++)
        {
            for(int j = 0; j < alpha[i]/2; j++)
            {
                prefix += (char)('A'+i);
                suffix = ((char)('A'+i))+suffix;
            }
        }
        return prefix+odd+suffix;
}

This post has been edited by mostyfriedman: 01 January 2011 - 01:51 PM

[KYA]

Problem 3:

Spoiler

/**
 *
 * @author Knowles
 */

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

public class Main {

	private Scanner in;
	private HashMap<String, Long> fileOneStorage;
    private HashMap<String, Long> fileTwoStorage;
    private Vector<Long> fileOneVect;
    private Vector<Long> fileTwoVect;

    private final String fileOneName = "lewis.txt";
    private final String fileTwoName = "Tom Sawyer.txt";

    public Main() {
        //let's do this sequentially

        fileOneVect = new Vector<Long>();
        fileTwoVect = new Vector<Long>();
        //Lewis
    	try{
    		in = new Scanner(new File(fileOneName)).useDelimiter("\\W");
    		fileOneStorage = new HashMap<String, Long>();
    	}
    	catch(Exception e){
    		e.printStackTrace();
            in.close();
    	}
    	while(in.hasNext()){
    		String temp = in.next().toLowerCase();
    		if(temp.length() > 0){
    			if(fileOneStorage.containsKey(temp)){
    				long frequency = fileOneStorage.get(temp);
    				frequency++;
    				fileOneStorage.put(temp, frequency);
    			}
    			else{
    				fileOneStorage.put(temp, 0L);
    			}
    		}
    	}
        
        in.close();
        
        //Tom Sawyer
        try{
    		in = new Scanner(new File(fileTwoName)).useDelimiter("\\W");
    		fileTwoStorage = new HashMap<String, Long>();
    	}
    	catch(Exception e){
    		e.printStackTrace();
    	}

        while(in.hasNext()){
    		String temp = in.next().toLowerCase();
    		if(temp.length() > 0){
    			if(fileTwoStorage.containsKey(temp)){
    				long frequency = fileTwoStorage.get(temp);
    				frequency++;
    				fileTwoStorage.put(temp, frequency);
    			}
    			else{
    				fileTwoStorage.put(temp, 0L);
    			}
    		}
    	}
        //get intersection of the list
        for(String key: fileOneStorage.keySet()){
            if(fileTwoStorage.containsKey(key)){
                fileOneVect.add(fileOneStorage.get(key));
                fileTwoVect.add(fileTwoStorage.get(key));
            }
        }
        //quick verification
        System.out.println(fileOneVect.size() + " "  + fileTwoVect.size());
        Double normOne = 0d, normTwo = 0d, dotProduct = 0d, finalAns = 0d;
        Long p1, p2;
        if(fileOneVect.size() != 0){
            //awesome, math!
            for(int i = 0; i < fileOneVect.size(); i++){
                p1 = fileOneVect.get(i);
                p2 = fileTwoVect.get(i);
                normOne += Math.pow(p1, 2);
                normTwo += Math.pow(p2, 2);
                dotProduct += p1*p2;
            }
            normOne = Math.sqrt(normOne);
            normTwo = Math.sqrt(normTwo);

            //debug
            System.out.println("Normal of text one: " + normOne);
            System.out.println("Normal of text two: " + normTwo);
            System.out.println("Dot product: " + dotProduct);

            finalAns = Math.acos(dotProduct/(normOne*normTwo));
        }
        else{
            //dotproduct is zero in the event of no similar letters
            //acos(0) = pi/2 ~=1.57
            finalAns = Math.acos(0);
        }
        
        System.out.println("Document Distance is: " + finalAns);
    }

    public static void main(String[] args){
    	new Main();
    }
}

Output for test case given:

Quote

3327 3327
Normal of text one: 22171.96184373408
Normal of text two: 6892.604152278005
Dot product: 1.31035689E8
Document Distance is: 0.5405285106498728

Also ran it for identical documents and documents without any common words, got the correct answer of zero and pi/2 [~1.57] respectfully.

I'd probably make it prettier/a little more clean [like methods, heh] for an under 100 LOC solution.

O(n)

[Dogstopper]

Raynes, on 01 January 2011 - 01:31 PM, said:

First and foremost, I'm using a library in contrib for the hard parts. You never specified whether or not reader need to implement the relevant operations themselves. If this library wasn't in contrib, I wouldn't have bothered. Contrib libraries can sometimes make it into Clojure itself, thus what I used could be core functions in the future. Nonetheless, it's very apparent that I cheated and that it is easy to cheat. If you want to avoid these types of solutions, you might need to clarify. Before Adam gets his hands on it.

NO CHEATING! There. I said it.

I did say simply said to find a good implementation. Whether permutations are done through and external library or not. However, to be able to effectively judge whether or not it is fast or not (Big O), we have to know what the implementation looks like!

@KYA, Nice use of HashMaps! It reduced the efficiency from O(n²) to O(n)

This post has been edited by Dogstopper: 01 January 2011 - 04:24 PM

[cfoley]

Here's my code for problem 2:

Spoiler

		public static String findPalindrome(String originalString) {

		final String notFound = "Not Found";
		final char[] chars = originalString.toCharArray();
		final char[] start = new char[chars.length / 2];
		final char[] end = new char[start.length];
		int centerIndex = -1;
		
		Arrays.sort(chars);
		
		int i = 0;
		for(int s = 0, e = end.length - 1; i < chars.length - 1;) {
			if (chars[i] != chars[(i+1)%chars.length]) {
				if (centerIndex != -1) return notFound;
				centerIndex = i++;
			} else {
				start[s++] = chars[i++];
				end[e--] = chars[i++];
			}
		}
		
		if (i == chars.length - 1) {
			if (centerIndex != -1) return notFound;
			centerIndex = i;
		}
		
		StringBuffer all = new StringBuffer(chars.length);
		all.append(start);
		if (centerIndex != -1) all.append(chars[centerIndex]);
		all.append(end);
		return all.toString();
		
	}

This post has been edited by cfoley: 02 January 2011 - 07:33 AM

[skaoth]

code for #3

Spoiler

/*
 * DocumentDistance.java
 * 
 * Copyright (c) 2011 skaoth. All rights reserved.
 * 
 * This software/library is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License,
 * or version 3 of the License.
 * 
 * This software/library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE
 * 
 * See the GNU Lesser General Public License for more details.
 * http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html
 * http://www.gnu.org/licenses/lgpl.html
 */

package net.skaoth.dic_test;

import java.io.InputStream;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
 *
 * @author skaoth
 */
public class DocumentDistance {

	private Map<String, Integer> file1Freq = new HashMap<String, Integer>();
	private Map<String, Integer> file2Freq = new HashMap<String, Integer>();
	private InputStream sawyerFile = null;
	private InputStream lewisFile = null;

	public DocumentDistance() {
		sawyerFile = getClass().getResourceAsStream("/Tom Sawyer.txt");
		lewisFile = getClass().getResourceAsStream("/lewis.txt");

		long start, stop;
		start = System.currentTimeMillis();
		getDistance();
		stop = System.currentTimeMillis();
		System.out.println("Distance calc took " + (stop - start) + "]ms");
	}

	private void getDistance() {
		file1Freq = getWordFrequencyFromFile(sawyerFile);
		file2Freq = getWordFrequencyFromFile(lewisFile);

		// perform the union of the 2 files
		file1Freq.keySet().retainAll(file2Freq.keySet());//getSharedWords();
		//file2Freq.keySet().retainAll(file1Freq.keySet());
		calculateDistance();
	}

	private void calculateDistance() {
		double dot = 0;
		double m1 = 0, m2 = 0, p1, p2;

		for(String key : file1Freq.keySet()) {
			p1 = file1Freq.get(key);
			p2 = file2Freq.get(key);

			m1 += Math.pow(p1, 2);
			m2 += Math.pow(p2, 2);
			dot += p1 * p2;
		}
		m1 = Math.sqrt(m1);
		m2 = Math.sqrt(m2);
		double ans = Math.acos(dot / (m1*m2));

		System.out.println("dot product: " + dot);
		System.out.println("distance: " + ans);
	}

	private Map<String, Integer> getWordFrequencyFromFile(InputStream is) {
		// read the words from the input stream and tally up
		// the word frequency
		Map<String, Integer> freq = new HashMap<String, Integer>();
		String word;
		Scanner s = new Scanner(is).useDelimiter("\\W");

		while(s.hasNext()) {
			word = s.next().toLowerCase();
			if(word.isEmpty()) { continue; }
			if(freq.containsKey(word)) {
				int count = freq.get(word);
				freq.put(word, count + 1);
			} else {
				freq.put(word, 1);
			}
		}

		return freq;
	}

	public static void main(String args[]) {
		new DocumentDistance();
	}
}

This post has been edited by skaoth: 01 January 2011 - 11:01 PM

[Raynes]

Here is my Clojure solution for 3.

Spoiler

(defn get-file-freq [f]
  (-> f slurp .toLowerCase (.split "\\W") frequencies))

(defn document-distance []
  (let [sawyer (get-file-freq "Tom Sawyer.txt")
        lewis (get-file-freq "lewis.txt")
        lv (map val (filter (comp sawyer key) lewis))
        sv (map val (filter (comp lewis key) sawyer))]
    (if (= 0 (count sv))
      (Math/acos 0)
      (do
        (let [[saw-norm lew-norm dot]
              (reduce (fn [[x y z] [no nt d]] [(+ x no) (+ y nt) (+ z d)])
                      (map (fn [x y]
                             [(Math/pow x 2)
                              (Math/pow y 2)
                              (* (double x) y)])
                           lv sv))]
          (println "Count:" (count lv) (count sv))
          (Math/acos (/ dot (* (Math/sqrt saw-norm) (Math/sqrt lew-norm)))))))))

And here is my output:

Quote

user=> (document-distance)
Count: 3257 3257
0.22798180494943945

I'm weirded out. I've scrutinized every character of KYA's code and my own code and I am almost absolutely certain that what we're doing is exactly the same. I'm just doing it in a functional way. Nonetheless, we're getting different outputs. I've tested my code against several different files including the test case (whose output I've documented above) and it appears to work just fine.

He noted that his frequency vector count was 3327, but when I ran his code on my machine against the exact same files, it gave me different output and said that the count was 3256. My code's count is 3257. What is up with this? What is the real correct answer here?

Note that I'm not saying that KYA's code is wrong. It's just as likely that my code is wrong. I've sat here for an hour trying to figure out if *I* did something wrong, but comparing our code, I'm pretty sure mine is solid enough.

Anyways, just a bizarre situation. Nonetheless, this is (once again) a just-for-fun solution because I have fun doing these challenges and it gives people a chance to compare Java to Clojure. Enjoy! :>

This post has been edited by Raynes: 02 January 2011 - 12:28 PM

[Dogstopper]

File lewis.txt : 15996 lines, 182355 words, 8530 distinct words
File Tom Sawyer.txt : 10272 lines, 73844 words, 7400 distinct words
The distance between the documents is: 0.565878 (radians)

That's the official program's output (the MIT solution). Unfortunately, it counts things like O'neil as to words - O and neil. However, as long as it is consistent, I would think it would be ok. KYA got really close to the correct answer.

Raynes, the prompt states:

Quote

A word is a sequence of letters [a..zA..Z] that might include digits [0..9] and the undescore character. All delimiters are thrown away and not kept as part of the word. Here are examples of words:

abcd
abcd12
abc_
a12cd
15111
We'll treat all upper-case letters as if they are lower-case, so that "CMU" and "cmu" are the same word.

That means that mine is potentially incorrect because I forgot about the last part...shoot.

This post has been edited by Dogstopper: 02 January 2011 - 05:36 AM

[cfoley]

I fixed a bug in my code.

[Raynes]

Oh goody, so we were both wrong at some level? It was just bizarre. It feels like the only reason my output was different from KYA's is because of that single word difference in count. Somehow, I'm getting one extra word. I actually tested that theory by just removing a random word from both frequency vectors and got almost the exact same results as he did. Thus, either he or I are doing something magical and getting a frequency vector that is one element too large.

In any case, yes, it is consistent. I've tested it with several duplicate and non-duplicate files and it appears to give sensible distance measures on all of them.

Cheers!

EDIT: I read the header of that page as well. I actually originally did a little filtering to make sure it was only underscores, spaces, letters, and digits, but I removed that after I got weird results in order to compare them with KYA's.

EDIT2: I fixed the code tags in my previous post. I'm surprised nobody mentioned that I screwed those up.

This post has been edited by Raynes: 02 January 2011 - 12:29 PM

[KYA]

Quote

File lewis.txt : 15996 lines, 182355 words, 8530 distinct words
File Tom Sawyer.txt : 10272 lines, 73844 words, 7400 distinct words
The distance between the documents is: 0.565878 (radians)

That explains my difference:

8539 7400 distinct words for lewis and sawyer respectfully.

[skaoth]

@Raynes
Are you checking to make sure you are not counting empty strings. I found the samething to be happening. In this case the empty string was happening so frequently that it screwed up the document distance function

[Raynes]

skaoth, on 03 January 2011 - 03:26 AM, said:

@Raynes
Are you checking to make sure you are not counting empty strings. I found the samething to be happening. In this case the empty string was happening so frequently that it screwed up the document distance function

That was it! Deadly easy to fix too.

Here is the amended code:

Spoiler

(defn get-file-freq [f]
  (-> f slurp .toLowerCase (.split "\\W") (->> (filter seq) frequencies)))

(defn document-distance [file1 file2]
  (let [d1 (get-file-freq file1)
        d2 (get-file-freq file2)
        lv (map val (filter (comp d1 key) d2))
        sv (map val (filter (comp d2 key) d1))]
    (if (= 0 (count sv))
      (Math/acos 0)
      (do
        (let [[d1-norm d2-norm dot]
              (reduce (fn [[x y z] [no nt d]] [(+ x no) (+ y nt) (+ z d)])
                      (map (fn [x y]
                             [(Math/pow x 2)
                              (Math/pow y 2)
                              (* (double x) y)])
                           lv sv))]
          (println "Count:" (count lv) (count sv))
          (Math/acos (/ dot (* (Math/sqrt d1-norm) (Math/sqrt d2-norm)))))))))

I also generalized it a bit so that it can be called on any two documents rather than hardcode the file names.

Here is the output:

Quote

user=> (document-distance "Tom Sawyer.txt" "lewis.txt")
Count: 3256 3256
0.5410870400062462

[Dogstopper]

Raynes, can you even WRITE Java code?