What's the missing column/row? (GCJ 2016-1A rankfile)

Question

There is an N x N square of numbers.

• All columns increase strictly monotonically from top to down
• All rows increase strictly monotonically from left to right
• There is exactly one valid answer for each input.

You are given 2N-1 rows of N numbers representing rows or columns in this square. The task is to find the row that isn't in the input.

Your Task
Write a program or function that outputs the row or column that isn't in the input.

Input

First, you get the number N.
Then follow 2N-1 lines of N space-separated numbers, representing rows or columns of this N x N square. The lines are given in left-to-right or top-down order. There may be multiple equal lines. It is ok to omit the initial N from the input, or modify the input format as you like.

3
1 2 3
2 3 5
3 5 6
2 3 4
1 2 3

Output

Your program or function should output a single line of N numbers; the row or column from the square that was not present in the input. You may change the output format as you please.

3 4 6

This would correspond to one of two squares:

1 2 3     1 2 3
2 3 4     2 3 5
3 5 6     3 4 6

Either way, the output is the same.

Bonus

Your solution should be able to calculate 2 ≤ N ≤ 10 within a minute on a normal computer. If your solution handles the big input, 2 ≤ N ≤ 50, within a minute, you get -10% byte count.

Test cases

2
22 222
2 22
22 222
-> 2 22


3
1 2 3
2 3 5
3 5 6
2 3 4
1 2 3
-> 3 4 6

4
11 14 16 22
3 6 9 11
6 7 11 14
9 11 15 19
10 11 19 22
6 7 10 11
3 6 8 10
-> 8 10 15 16

Note that you can simply change what line in these inputs that is omitted, and reorder them in any way you want, to generate new test cases.

This is a simplified version of Google Code Jam 2016 round 1A problem B: Rank and File. The original Google Code Jam problem, where you can get more test cases (but without answers), is available here: https://code.google.com/codejam/contest/4304486/dashboard#s=p1

Answer 1

CJam, 5 - 10% = 4.5

This is an unnamed function (block) that takes an array of arrays and returns an array:

{:^$}

(With some inspiration from Dennis)

Try it online

And here is the code I actually submitted at GCJ (24 bytes):

li2*({l~}*]$e`{(2%*~}%S*

Try it online

Explanation:

This basically lists the values that appear an odd number of times.

:^    reduce by symmetric difference; pairs of duplicate values "cancel" each other
$     sort the resulting array

Answer 2

Jelly, 3.6 bytes

œ^/Ṣ

The source code is 4 bytes long and qualifies for the -10% bonus. Try it online!

How it works

Since there are 2N rows/columns in total, each number must appear 2N times. Therefore, it suffices to take the numbers that appear in an odd number of the 2N - 1 rows/columns from input.

œ^/Ṣ  Main link. Argument: A (2D list of integers)

  /   Reduce the rows by...
œ^    symmetric multiset difference.
   Ṣ  Sort the result.

Answer 3

JavaScript (ES6), 179 bytes

f=(n,a,p=[],o)=>(p[n-1]?p.every((_,j)=>~(a.map(v=>v+"").indexOf((m=p.map((_,k)=>p.map(r=>r[k]))[j])+""))?1:o=!o&&m):a.map((c,i)=>o=o||f(n,x=a.slice(),p.concat(x.splice(i,1)))))&&o

Explanation

Whew! That took quite a bit of effort to do without any combinatorics built-ins...

Possibly qualifies for the bonus. I haven't tested with n = 50.

The entire function is a recursive permutation function. It takes the size n and input array a, then moves each item individually from a to the current permutation array p. p becomes every permutation of rows.

Once the length of p becomes n, it transposes p to get an array of the columns. It searches these columns for each item in a.

Because a should contain all these columns except one if this is the correct result, output the column in the transposed p which is missing from a if there is only one column missing.

f=(n,a,p=[],o)=>(
  p[n-1]?                                        // once p is a square
    p.every((_,j)=>                              // find each column in the transposed square a,
                                                 //     a is missing a column so one should fail
      ~(a.map(v=>v+"")                           // convert column arrays to strings so we can use indexOf
        .indexOf(                                // search for current column
          (m=p.map((_,k)=>p.map(r=>r[k]))[j])+"" // transpose p to match a
        )
      )?1:o=!o&&m                                // if there is only one column missing from a, o = missing column
    )
  :a.map((c,i)=>                                 // add each row to the permutation
    o=o||                                        // set o to first found result
    f(n,x=a.slice(),p.concat(x.splice(i,1)))     // get next permutation
  )
)&&o                                             // return o

// Test
var testCases = [[
    2, [
      [22,222],
      [2,22],
      [22,222]
    ]
  ], [
    3, [
      [1,2,3],
      [2,3,5],
      [3,5,6],
      [2,3,4],
      [1,2,3]
    ]
  ], [
    4, [
      [11,14,16,22],
      [3,6,9,11],
      [6,7,11,14],
      [9,11,15,19],
      [10,11,19,22],
      [6,7,10,11],
      [3,6,8,10]
    ]
]];
document.write("<pre>"+testCases.map(c=>f(c[0],c[1])).join`\n`);

Answer 4

Pyth, 13 12 11 9 x 0.9 = 8.1 bytes

S{f%/QT2Q

Flattened list as input.

Try it online!

previous 11-byte solution

M-+GH@GHSgF

Uses Dennis' algorithm.

previous 12-byte solution:

S{f%/.nQT2.n

Try it online!

alternative 13 byte solution:

eCf%hT2rS.nQ8

Try it online!

Answer 5

Julia, 19.8 bytes

x->sort(symdiff(x...))

The source code is 22 bytes long and qualifies for the -10% bonus. Try it online!

Answer 6

JavaScript (Firefox 30-57), 62 bytes

(a,s=[])=>[for(b of a)for(c of b)s[c]^=c]&&[for(c of s)if(c)c]

Only works for positive integers. 64 bytes to work with zero too:

(a,s=[])=>[for(b of a)for(c of b)s[c]^=~c]&&[for(c of s)if(c)~c]

101 bytes to work with arbitrary floating-point numbers:

(a,m=new Map)=>[for(b of a)for(c of b)m.set(c,!m.get(c))]&&[for(b of m)if(b[1])b[0]].sort((a,b)=>a-b)

109 bytes to work with strings instead:

(a,m=new Map)=>[for(b of a)for(c of b)m.set(c,!m.get(c))]&&[for(b of m)if(b[1])b[0]].sort((a,b)=>(a>b)-(a<b))