Coding challenge

[H@L0_F00]

Lets get a new challenge going. Anybody?

[oda777]

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 .

[oda777]

.

[stingwray]

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

[oda777]

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.....

[lukeh53]

could we get a new challenge please. i think that i could finally participate

[stingwray]

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.

[bbq]

#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();
}

[Emeryth]

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);
    }
}

[stingwray]

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?

[Emeryth]

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());

[stingwray]

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.

[Zimmer]

Here this hasn't been active so if now one is going to be declared a winner.

How about for the next challenge a crack me....

Language: ANY

Winner: Hardest to find password

[doug_h]

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.

[doug_h]

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])

[Zimmer]

Stingray declare a winner already! So we can get a new challenge going

[Zimmer]

Double post delete

[Zimmer]

Stingwray are you going to declare a winner? Can I start a new challenge? Is anyone still interested in this? Is this dead?

[kchap91]

I am interested, but it does seem to be dead :(

[cooper]

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.

[%_%]

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;
    }
}

[Zimmer]

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 :))

[Deveant]

This challange has already been done... in this topic...

Winner was Steve8x with: Steve8x http://hak5.org/forums/index.php?s=&sh...ost&p=94604

[Zimmer]

I knew it was done before I just wanted to get this active again :).

[corcrash]

I'm interested in getting this challenge up again, to! So if there are more ppl who would like to do it, I'm in for sure! :D