# 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.
– user45941
Apr 23 '16 at 1:28
• Changed it to allow omitting N from input. 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
• 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. – Nic Apr 23 '16 at 4:14 • Obligatory Unicode is not an encoding response. Apr 23 '16 at 4:15 • For Pyth, it is still 12 bytes using your algorithm... One does not simply outgolf Dennis. Apr 23 '16 at 6:47 • Oh, it's 11 bytes now. 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. Apr 23 '16 at 7:28 • @Dennis Thanks, but I still cannot outgolf you :D 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))  # GolfScript, 5 - 10% = 4.5 bytes Port of the CJam answer - reduce by symdiff, sort. {^}*$
`

Try it online!