Re: The Perl 6 Coding Contest 2012

[BrowserUk]

Has an expanded explanation of the following phrase(s) been forthcoming anywhere?:

Two crossings can never be placed vertically adjacent to each other. (This is equivalent to saying that the wires never split or merge, they only permute.)

[moritz]

I'm pretty sure it means that you can't cross the wires (0, 1) and (1, 2) at once, just (0, 1) and (2, 3):

# allowed:
0 _  _ 1
   \/
1 _/\_ 0

2 _  _ 3
   \/
3 _/\_ 2


# disallowed, ambiguous:
0 _  _ 1
   \/
1 _/\_ 0
   \/
2 _/\ _ 3

[BrowserUk]

Hm. To me, that was clearly not an option.

My doubt centers around this:

0 _      _ 3
   \    /   
1 _ \  / _ 4
   \ \/ /   
2 __\/\/__ 2
    /\/\    
3 _/ /\ \_ 0
    /  \    
4 _/    \_ 1

The crossovers between: the 0 & 3 wires; and the 1 & 4 wires are "vertically adjacent". Ie. As close together vertically as two crossovers can be. It also means that the striaght through 2 wire has a large break which cannot be filled, leaving its continuity unclear.

Both of these things can be addressed like this:

0 ___    ___ 3
     \  /
1 _   \/   _ 4
   \  /\  /
2 __\/__\/__ 2
    /\  /\
3 _/  \/  \_ 0
      /\    
4 ___/  \___ 1

This makes for a much clearer diagram, but that means that all the crossovers are 'on the wire lines' rather than between them. It also may be seen to contravene the "It is considered elegant not to make the grid wider than it has to be." rule.

So maybe it would need to be something like:

0 _____  _____ 3
       \/  
1 _    /\    _ 4
   \  /  \  /
2 __\/____\/__ 2
    /\    /\
3 _/  \  /  \_ 0
       \/
4 _____/\_____ 1

But that still leaves some crossovers occurring on wire lines rather than between them. So maybe:

0 _____  _____ 3
       \/  
1 ___  /\  ___ 4
     \/  \/  
2 __ /\__/\___ 2
    /  \/  \
3 _/   /\   \_ 0
      /  \
4 ___/    \___ 1

The 2 line sucks and it destroys the natural symmetry, but it more clearly complies with the rules -- except perhaps the no wider than necessary. Unless it is necessary to be that wide in order to comply with the other rules :)

It is an interesting programming problem, but it would suck to implement a brilliant solution, only to be failed because the problem description was ambiguous.

Science is about questioning the status quo. Questioning authority

[moritz]

0 _      _ 3
   \    /   
1 _ \  / _ 4
   \ \/ /   
2 __\/\/__ 2
    /\/\    
3 _/ /\ \_ 0
    /  \    
4 _/    \_ 1

That's not an option. Crossing have to be pairwise, I.e if 0 crosses over to 1, 1 must also cross over to 0. So you have to wire it as

0 _____  _____ 3
       \/    
1 ___  /\  ___ 4
     \/  \/  
2 _  /\  /\  _ 2
   \/  \/  \/
3 _/\  /\  /\_ 0
     \/  \/  
4 ___/\__/\___ 1

Think of it as physical wires, and all you can do is to exchange two adjacent wires.

I'll point masak to this thread so he can object if I wrote something wrong.

[masak]

Yep, moritz has it right.

Think of it like this. The fundamental operation is "exchange wires N and N+1". This is depicted graphically with a single crossing between two adjacent wires. You're allowed to put several of these fundamental operations in the same column, provided no two operations in the same column act on the same wire.

[BrowserUk]

Ignoring questions of optimality, is this legal? (If not, which rule(s) does it violate?)

0 _____  _____ 3
       \/       
1 ___  /\    _ 4
     \/  \/\/   
2 _  /\  /\/\_ 2
   \/  \/ /\    
3 _/\__/\/  \_ 0
        /\      
4 _____/  \___ 1