0
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ You should make the N input optional - many languages would just read and discard/ignore it because it can be inferred from the rows. \$\endgroup\$ – Mego Apr 23 '16 at 1:28
  • \$\begingroup\$ Changed it to allow omitting N from input. \$\endgroup\$ – Filip Haglund Apr 23 '16 at 1:30
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – xnor Apr 23 '16 at 1:30
  • 1
    \$\begingroup\$ This strikes me as a chameleon challenge. Once you solve the puzzle, you find that it's really about cancelling duplicates. \$\endgroup\$ – xnor Apr 23 '16 at 4:13
  • 1
    \$\begingroup\$ We also discourage bonuses in code golf \$\endgroup\$ – Alex A. Apr 23 '16 at 5:38
6
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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

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

\$\endgroup\$
1
\$\begingroup\$

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!

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

Julia, 19.8 bytes

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

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

\$\endgroup\$
1
\$\begingroup\$

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))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.