Wireless Keyboard Inteference

Question

Initech are setting up an office of 36 employees in a soul-crushingly efficient square of cubicles, 6 desks long and 6 desks deep. Management has bought wireless keyboards in bulk from a cheap, international wholesaler. IT are quickly discovering that the wireless keyboards only operate on 3 different radio frequencies, and each individual keyboard is hardwired to a particular frequency. When two keyboards on the same frequency are too close to each other, they interfere with each other. The only identifying mark on the keyboards is a unique serial number which gives no clues as to the keyboard's radio frequency. Thankfully there are an equal number of keyboards operating on each frequency.

A keyboard can be defined by the following class.

sealed class WirelessKeyboard
{
    private int frequency;
    private int serialNum;

    public WirelessKeyboard(int frequency, int serialNum)
    {
        this.frequency = frequency;
        this.serialNum = serialNum;
    }

    public bool InteferesWith(WirelessKeyboard other)
    {
        return this.frequency == other.frequency;
    }

    public int getSerialNum()
    {
        return serialNum;
    }
}

Your function must accept an array of 36 WirelessKeyboard objects. Each is predefined with a unique serial number and one of the three frequencies (12 keyboards of each frequency). The array is in random order. The only way to determine a keyboard's frequency is to test if it interferes with another keyboard.

Your function must:

• Not modify or extend the WirelessKeyboard class beyond translating it into your programming language of choice.
• Accept an input array of WirelessKeyboard objects.
• Not create or alter any WirelessKeyboard objects. Only those in the input may be used.
• Not use any means (eg. reflection) to read a keyboard's frequency.
• Output a 6x6 array (or equivalent) populated with WirelessKeyboard objects, which:
  • Contains all 36 unique keyboards.
  • InteferesWith(other) must return false for all horizontally and vertically adjacent keyboards.

For the sake of code golf, the WirelessKeyboard class may be aliased as K and code may be written as a function. For example, in C/Java, ungolfed and golfed:

WirelessKeyboard[,] FindMap(WirelessKeyboard[] collection) { ... }

K[,]F(K[]c){ ... }

The shortest code in a week gets the points. Please post your implementation of the WirelessKeyboard class if it differs significantly from the sample above, but do not count it towards your score. The function and any dependant declarations (eg. library imports) count towards your score.

Answer 1

Julia, 97 chars

s(k)=while any([k[j]>k[j-1]||j>6&&k[j]>k[j-6] for j=2:36]);i,j=rand(1:36,2);k[[i,j]]=k[[j,i]];end

Checks if the array is in an acceptable final state state, if not, randomly flips two entries. It's super slow, which I find highly amusing. Does an in place alteration on the input array k. InterferesWith is implemented as >.

As I said, it's really slow. I tested it with more frequencies and smaller boards with 3 frequencies, but it hasn't returned in over 30 mins on the actual problem. I suspect that it won't return overnight, but I'll update if it does. Update: Yes it did finish in less than 12 hours, and yielded an answer that I added to the gist.

Gist with commented code, and includes 3x3 test case that finishes fast: https://gist.github.com/ggggggggg/8679916

Answer 2

Ruby, 108

Here's my WirelessKeyboard class, similar to @gggg I have used a shorter alias for the InterferesWith method.

class K
    attr_reader :freq, :serial
    protected :freq

    def initialize freq, serial
        @freq, @serial = freq, serial
    end

    def interferes_with other
        self.freq == other.freq
    end

    alias :i :interferes_with

    def inspect
        '%3i:%i' % [serial, freq]
    end
end

My actual code:

f=->k{r=k.group_by{|e|e.i(a=k[0])?0:e.i(k.find{|e|!e.i a})?1:2}
(v=0..5).map{|y|v.map{|x|r[(x+y%2)%3].pop}}}

Test run:

keyboards = (0..35).map { |i| K.new(i%3, i) }.shuffle
puts f[keyboards].map { |r| r.map { |c| c.inspect }*' ' }

Result:

 23:2  34:1  33:0   8:2  25:1  24:0
 19:1  12:0  20:2   4:1  21:0  29:2
  2:2  16:1  18:0  35:2   7:1  27:0
 28:1   0:0  17:2  13:1  15:0   5:2
 26:2  22:1   6:0  32:2  10:1   3:0
  1:1  30:0  11:2  31:1   9:0  14:2

Answer 3

PHP 200

<? function O($K){$O=[[],[],[]];foreach($K as$v){foreach($O as&$d){if(!$d||$v->I($d[0])){$d[]=$v;break;}}}$i=6;while($i--){$j=6;while($j--){$v=$j%3+$i%3;$v>2&&$v-=3;echo array_pop($O[$v]);}echo"\n";}}

sample result

10-1 32-2  6-0  1-1 20-2 15-0 
 2-2 24-0 19-1 11-2 30-0 28-1 
18-0 25-1 29-2 21-0  4-1  5-2 
16-1 35-2  3-0 22-1 14-2 12-0 
 8-2  9-0  7-1 17-2 33-0 13-1 
 0-0 31-1 23-2 27-0 34-1 26-2 

testcase+class http://codepad.org/UtjNt7qV

(the class has a __toString to be echoable

Answer 4

C#, 269 bytes

using System.Linq;

WirelessKeyboard[,] FindMap(WirelessKeyboard[] collection)
{
    var list = collection.ToList();
    var map = new WirelessKeyboard[6, 6];
    map[0, 0] = list[0];
    list.Remove(map[0, 0]);
    map[1, 0] = list.First(keyboard => !keyboard.InteferesWith(map[0, 0]));
    list.Remove(map[1, 0]);
    map[2, 0] = list.First(keyboard => !keyboard.InteferesWith(map[0, 0]) && !keyboard.InteferesWith(map[1, 0]));
    list.Remove(map[2, 0]);
    for (int y = 0; y < 6; y++)
    {
        int x = y == 0 ? 3 : 0;
        for (; x < 6; x++)
        {
            map[x, y] = list.First(keyboard => keyboard.InteferesWith(map[(x + y) % 3, 0]));
            list.Remove(map[x, y]);
        }
    }
    return map;
}

The golfed code with InterferesWith defined as I:

using System.Linq;
K[,]F(K[]c)
{
    var l=c.ToList();
    var m=new K[6,6];
    l.Remove(m[0,0]=l[0]);
    l.Remove(m[1,0]=l.First(k=>!k.I(m[0,0])));
    l.Remove(m[2,0]=l.First(k=>!k.I(m[0,0])&&!k.I(m[1,0])));
    for(int x=2;++x<36;){
        l.Remove(m[x%6,x/6]=l.First(k=>k.I(m[(x+x/6)%3,0])));
    }
    return m;
}

It populates the first three cubicles with keyboards with different frequencies, then fills the rest with a diagonal-stripe pattern using the first three as a template:

11-2  13-1  33-0   5-2   7-1  12-0
16-1  15-0  20-2  22-1   0-0  17-2
18-0  35-2  10-1  27-0  32-2  28-1
14-2  31-1   9-0  29-2   4-1   3-0
25-1  30-0   2-2   1-1  21-0  26-2
24-0  23-2  34-1   6-0   8-2  19-1