Jump to content

Coding challenge


snakey
 Share

Recommended Posts

  • Replies 237
  • Created
  • Last Reply

Top Posters In This Topic

Top Posters In This Topic

Posted Images

before we do i will post my version of my challenge .

input=gets.chomp.downcase
puts input.tr('a-z', 'b-za')

this is a small little code in ruby , .tr is short for translate which is a useful method that i have only seen in ruby and Perl .

Link to comment
Share on other sites

.

Link to comment
Share on other sites

before we do i will post my version of my challenge .

input=gets.chomp.downcase
puts input.tr('a-z', 'b-za')

this is a small little code in ruby , .tr is short for translate which is a useful method that i have only seen in ruby and Perl .

Nice use of the translate method, although not a very full featured program! :P

Link to comment
Share on other sites

Nice use of the translate method, although not a very full featured program! :P

lol very true, i had a full program for it but i was lazy when posting..... :rolleyes:

Link to comment
Share on other sites

  • 2 weeks later...

Nice simple one, but one I have just had to solve.

Challenge: Find the power set of an input set.

Examples: Input Set = {1,2,3}, Power Set = {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

Points for execution time, code simplicity, code readability and extra features (like working on any object not just integers).

Implement in your favorite language.

Link to comment
Share on other sites

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <iterator>

typedef std::set<int> set_type;
typedef std::set<set_type> powerset_type;

powerset_type powerset(set_type const& set)
{
  typedef set_type::const_iterator set_iter;
  typedef std::vector<set_iter> vec;
  typedef vec::iterator vec_iter;

  struct local
  {
    static int dereference(set_iter v) { return *v; }
  };


  powerset_type result;
  
  vec elements;
  do
  {
    set_type tmp;    
    
    std::transform(elements.begin(), elements.end(),std::inserter(tmp, tmp.end()),local::dereference);
    result.insert(tmp);
    if (!elements.empty() && ++elements.back() == set.end())
    {
      elements.pop_back();
    }
    else
    {
      set_iter iter;
      if (elements.empty())
      {
        iter = set.begin();
      }
      else
      {
        iter = elements.back();
        ++iter;
      }
      for (; iter != set.end(); ++iter)
      {
        elements.push_back(iter);
      }
    }
  } while (!elements.empty());

  return result;
}

int main()
{
  int values[4] = { 2, 3, 5, 7 };
  set_type test_set(values, values+4);

  powerset_type test_powerset = powerset(test_set);

  for (powerset_type::iterator iter = test_powerset.begin();
       iter != test_powerset.end();
       ++iter)
  {
    std::cout << "{ ";
    char const* prefix = "";
    for (set_type::iterator iter2 = iter->begin(); iter2 != iter->end(); ++iter2)
    {
      std::cout << prefix << *iter2;
      prefix = ", ";
    }
    std::cout << " }\n";
    
  }
  getchar();
}

Link to comment
Share on other sites

Here is my solution in Java.

The returned power set is sorted and can contain any type of objects (of course all of the objects must be of the same type) as long as they implement the Comparable interface (e.g. all basic data types).

As an example, the program creates a power set of command line parameters.

import java.util.Collections;
import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

public class Main {

    public static TreeSet makePowerSet(Comparable[] elements) {
        TreeSet powerSet = new TreeSet(new Comparator<Set>() {

            public int compare(Set o1, Set o2) {
                TreeSet tmp1 = new TreeSet(o1);
                TreeSet tmp2 = new TreeSet(o2);
                if (o1 == Collections.EMPTY_SET) {
                    return -1;
                }
                if (tmp1.size() < tmp2.size()) {
                    return -1;
                }
                if (tmp1.size() > tmp2.size()) {
                    return 1;
                }
                while (tmp1.size() > 0 && tmp2.size() > 0) {
                    Comparable cmp1 = (Comparable) tmp1.pollFirst();
                    Comparable cmp2 = (Comparable) tmp2.pollFirst();
                    if (cmp1.compareTo(cmp2) < 0) {
                        return -1;
                    }
                    if (cmp1.compareTo(cmp2) > 0) {
                        return 1;
                    }
                }
                return 0;
            }
        });
        powerSet.add(Collections.EMPTY_SET);
        for (int i = 0; i < elements.length; i++) {
            Object o = elements[i];
            for (int k = 0; k < elements.length; k++) {
                TreeSet set = new TreeSet();
                    set.add(o);
                for (int j = k; j < elements.length; j++) {
                    Object p = elements[j];
                        set.add(p);
                    TreeSet copy = new TreeSet(set);
                    powerSet.add(copy);
                }
            }
        }
        return powerSet;
    }

    public static void main(String[] args) {
        TreeSet powerSet = makePowerSet(args);
        System.out.println(powerSet);
    }
}

Link to comment
Share on other sites

Did you test your code Emeryth?

Comparable cmp1 = (Comparable) tmp1.pollFirst();
Comparable cmp2 = (Comparable) tmp2.pollFirst();

Doesn't compile as the method pollFirst() doesn't exist. TreeSet JavaDoc

So I changed it to first() making the assumption that's what you meant. However it doesn't not halt now so never returning an answer.

What JVM are you working with?

Link to comment
Share on other sites

Oh that's the joy of Java. The pollFirst() method was introduced in 1.6 :P

For compatibility you can replace it with:

Comparable cmp1 = (Comparable) tmp1.first();
Comparable cmp2 = (Comparable) tmp2.first();
tmp1.remove(tmp1.first());
tmp2.remove(tmp2.first());

Link to comment
Share on other sites

Strange, I am running 1.6, I thought for a moment I wasn't because I had been working with 1.5 for my previous project, because SWT doesn't support 64-bit JVMs on OS X and Apple don't support Java as 32-bit any more. Plus one developer in the group owned a Core Duo MacBook Pro which isn't 64-bit.

I shall have to look into this further.

EDIT: found the problem, I'm using NetBeans at the moment as Eclipse has finally lost all love that I had for it and I hadn't set it up to use 1.6, all works fine now.

public static <T extends Comparable<? super T>> Set<Set<T>> findPowerSet(
            Set<T> set) {
        // Create a result set to hold the result and add the empty set.
        Set<Set<T>> result = new HashSet<Set<T>>();
        result.add(new HashSet<T>());

        // Foreach item in the input set.
        for (T item : set) {
            // Create a set to hold generated sets this iteration.
            Set<Set<T>> iterationresult = new HashSet<Set<T>>() {};

            // Foreach set in the current result.
            for (Set<T> rset : result) {
                // Copy that set, add the current item to it and place the
                // result in the iteration result set.
                Set<T> copyitem = (Set<T>) ((HashSet<T>) rset).clone();
                copyitem.add(item);
                iterationresult.add(copyitem);
            }

            // Add all of the iteration results to the result set.
            result.addAll(iterationresult);
        }

        // Return the result set.
        return result;
}

Nice little algorithm, want to try and improve it still, but at the moment not sure where to start.

Link to comment
Share on other sites

  • 1 month later...
Nice simple one, but one I have just had to solve.

Challenge: Find the power set of an input set.

Examples: Input Set = {1,2,3}, Power Set = {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

Points for execution time, code simplicity, code readability and extra features (like working on any object not just integers).

Implement in your favorite language.

Here's my submission.

def PowerSet(base):
	power_set = []
	b = len(base)
	map(lambda g: power_set.append(map(lambda x: base[x],
		filter(lambda x: g[x], range(0, b)))),
		map(lambda value: map(lambda x: (value >> x) & 1, range(b - 1, -1, -1)),
		map(lambda value: value ^ (value / 2), range(0, 2**b))))
	return power_set

print PowerSet([1,2,3])

This definitely won't win for readability but it's the shortest I could come up with.

Link to comment
Share on other sites

Here's a simpler more readable version of my previous submission. It's also commented.

def PowerSet(base):
	#What size of gray_code set should we make?
	bits = len(base)
	power_set = []

	#Generate the gray_code
	gray_code = map(lambda x: x ^ (x / 2), range(0, 2 ** bits))

	for gcode in gray_code:
		#Calculate binary of gray_code
		binary = map(lambda x: (gcode >> x) & 1, range(bits-1, -1, -1))
		#Calculate the indexes of the 1's
		working_set = filter(lambda x: binary[x], range(0, bits))
		#Add the values from the base that coorespond to the 1 indexes
		working_set = map(lambda x: base[x], working_set)
		#Add working_set to power_set
		power_set.append(working_set)
	return power_set

print PowerSet([1,2,3])

Link to comment
Share on other sites

  • 2 weeks later...

My entry into the fray:

#include <stdio.h>

static show(int *set, char *prefix) {
    char buffer[100];
    while (*set >= 0) {
        sprintf(buffer,"%s%d",prefix,*set);
        printf("%s ",buffer);
        set++;
        show(set, buffer);
    }
}

int main(void) {
    int inputSet [5] = { 1,2,3,4,-1 };
    show(inputSet,"");
    return 0;
}

Place some values in inputSet and end it with a negative.

Link to comment
Share on other sites

My solution in java

public class PowerSet
{

    public static void main(String[] args)
    {
        Object[] set = {1,2,3};//change to whatever variable type
        LinkedHashSet myPowerSet = powerset(set);
        System.out.println(myPowerSet.toString());
    }

    /**
     * Returns the power set from the given set by using a binary counter
     * Example: S = {a,b,c}
     * P(S) = {[], [c], [b], [b, c], [a], [a, c], [a, b], [a, b, c]}
     * @param set Obect[]
     * @return LinkedHashSet
     */
    private static LinkedHashSet powerset(Object[] set)
    {
        //create the empty power set
        LinkedHashSet power = new LinkedHashSet();

        //get the number of elements in the set
        int elements = set.length;

        //the number of members of a power set is 2^n
        int powerElements = (int) Math.pow(2, elements);

        for (int i = 0; i < powerElements; i++) {
            String binary = binaryValue(i, elements);
            LinkedHashSet innerSet = new LinkedHashSet();
            for (int j = 0; j < binary.length(); j++) {
                if (binary.charAt(j) == '1') {
                    innerSet.add(set[j]);
                }
            }
            power.add(innerSet);
        }

        return power;
    }

    /**
     * Converts the given integer to a String representing a binary number
     * with the specified number of digits
     * For example when using 4 digits the binary 1 is 0001
     * @param binary int
     * @param digits int
     * @return String
     */
    private static String binaryValue(int binary, int digits)
    {
        String temp = Integer.toBinaryString(binary);
        int foundDigits = temp.length();
        String returner = temp;
        for (int i = foundDigits; i < digits; i++) {
            returner = "0" + returner;
        }
        return returner;
    }
}

Link to comment
Share on other sites

  • 1 month later...

Here I got a challenge:

An alarm clock.

-Able to set time by well time like 12:55

- Military time = bonus points

-Clean well commented code N00b undertandable

-Bonus for mp3 support

-Bonus for mp3 slowly getting louder

-Bonus playlist support

-Other Bonuses I'll decide (if anyone does this challenge :))

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.

×
×
  • Create New...