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

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.

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

• You should make the N input optional - many languages would just read and discard/ignore it because it can be inferred from the rows. – Mego Apr 23 '16 at 1:28
• Changed it to allow omitting N from input. – Filip Haglund Apr 23 '16 at 1:30
• More generally, I think you should adapt your I/O format to be more flexible by letting languages do input and output in their native list types. See Things to avoid when writing challenges. – xnor Apr 23 '16 at 1:30
• This strikes me as a chameleon challenge. Once you solve the puzzle, you find that it's really about cancelling duplicates. – xnor Apr 23 '16 at 4:13
• – Alex A. Apr 23 '16 at 5:38

# 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


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

• Damn, this is impressive. Also, obligatory "but this is eight bytes in Unicode" comment-- wait, you linked the codepage this time! Never mind. – Fund Monica's Lawsuit Apr 23 '16 at 4:14
• Obligatory Unicode is not an encoding response. – Dennis Apr 23 '16 at 4:15
• For Pyth, it is still 12 bytes using your algorithm... One does not simply outgolf Dennis. – Leaky Nun Apr 23 '16 at 6:47
• Oh, it's 11 bytes now. – Leaky Nun Apr 23 '16 at 6:50

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

# Pyth, 131211 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!

• If you take a flat list as input (I guess that's allowed), you can shorten your 12-byte solution to 9 bytes. – Dennis Apr 23 '16 at 7:28
• @Dennis Thanks, but I still cannot outgolf you :D – Leaky Nun Apr 23 '16 at 8:24

# Julia, 19.8 bytes

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


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

## 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))
`