Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

You are required to find how many triangles are unique out of given triangles. For each triangle you are given three integers a,b,c , the sides of a triangle.

A triangle is said to be unique if there is no other triangle with same set of sides.

Note : It is always possible to form triangle with given sides.

INPUT:

First line contains n, the number of triangles. Each of next n lines contain three integers a,b,c (sides of a triangle).

Output:

print single integer, the number of unique triangles.

Constraints:

1 <= n <= 10^5
1 <= a,b,c <= 10^15

Sample Input

5
7 6 5
5 7 6
8 2 9
2 3 4
2 4 3

Sample Ouput

1

Explanation

only triangle with sides 8, 2, 9 is unique
share|improve this question
2  
I don't really understand what you mean by no other triangle with the same set of sides. I think it would be helpful if you provided a few example input -> output pairs. –  Gareth Feb 3 at 12:43
    
@ Gareth See the updated question –  Dangling_pointer Feb 3 at 12:48
    
is the input of 1 triangle restricted to one line or can you ask for side a,b,c in turns? side a: 1 -> side b: 3 -> side c: 5 –  Teun Pronk Feb 3 at 13:10
1  
Why do you complicate the task by having first number telling you the number of lines? This unnecessarily complicates the programs in most languages. Can we just assume we have the triangles, without the count at the beginning? –  Tomas Feb 3 at 13:42
    
Agree with Gareth. This challenge is not specified clearly. –  Tomas Feb 3 at 13:45

11 Answers 11

up vote 7 down vote accepted

GolfScript, 22 characters

n%{~]$}%:^{]^\/,3<},,(

Includes the first line into the list of triangles but subtracts one from the result later. Run online.

Commented code

n%            # Split input into lines
{             # For each line
  ~]          # Evaluate the content and put into array
  $           # Sort the array (aka sides)
}%
:^            # Assign to variable ^
{             # Filter list of triangles
  ]           # Make array from triangle
  ^\/         # Count number of occurences in ^ by splitting
  ,3<         # and testing if number of parts is less than 3 (i.e. 
              # triangle occurse only once
},
,(            # Count distinct lines and subtract 1 (for first line)
share|improve this answer

k [22 chars]

{+/1=#:'={x@<x}'x:1_x}

Example

input:(5;7 6 5;5 7 6; 8 2 9;2 3 4;2 4 3)
input
5
7 6 5
5 7 6
8 2 9
2 3 4
2 4 3

Output

{+/1=#:'={x@<x}'x:1_x}[input]
1

Example

input:(3;1 2 3;4 5 6;7 8 9)
input
3
1 2 3
4 5 6
7 8 9

Output

{+/1=#:'={x@<x}'x:1_x}[input]
3
share|improve this answer

Bash and coreutils (87,98,95,93)

Assumes input file is called "f",

sed 1d f|while read n;do echo `echo $n |tr ' ' '\n'|sort|tr '\n' ' '`;done|sort|uniq -u|wc -l

Reads line by line, sorts each line separately, then sorts all the lines. Finally the unique lines are filtered and counted. Also works for strings.

EDIT: As Yimin Rong pointed out, the first line containing the number of triangles is now handled (by removing it :) ).

share|improve this answer
    
I don't think it handles the first line correctly. I get 2 as the answer for the sample input with this script. –  Yimin Rong Feb 3 at 16:07
    
You're totally right. I missed the fact that there is a first line stating the number of triangles... –  camelthemammel Feb 3 at 16:21
    
Cool, we came out with the same character counts but with completely different approaches! –  Yimin Rong Feb 3 at 17:07
    
I managed to shave 3 off by using "|" to pipe into the while loop instead of using "<" :) –  camelthemammel Feb 3 at 17:14

APL, 18 chars/bytes*

{+/1=+/∘.(≡⍦)⍨1↓⍵}

Dialect is Nars2000. Following the lead in the K answer, this code is a function that accepts a list of vectors, first the number of lines (which is ignored) and then the triangles. Let me know if this is not ok.

Exploded view

{             1↓⍵}   drop the first element of the list (the number of lines)
       ∘.(  )⍨       for each possible pair of vectors (triangles) from the list,
          ≡⍦         compare them as multisets: check whether they are the same triangle
     +/              sum each row: for each triangle, count how many others are the same
   1=                find out which ones are unique
 +/                  and count them

Example

      {+/1=+/∘.(≡⍦)⍨1↓⍵} 5(7 6 5)(5 7 6)(8 2 9)(2 3 4)(2 4 3)
1
      {+/1=+/∘.(≡⍦)⍨1↓⍵} 6(7 6 5)(5 7 6)(8 2 9)(2 3 4)(2 4 3)(2 4 6)
2

⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
*: APL can be written in its own (legacy) single-byte charset that maps APL symbols to the upper 128 byte values. Therefore, for the purpose of scoring, a program of N chars that only uses ASCII characters and APL symbols can be considered to be N bytes long.

share|improve this answer

GolfScript (24 chars)

~](;3/{$}%:^1/{^\/,2=},,

Online demo

This relies on the triangle sides being GolfScript literals of the same type (and hence sortable): it would work equally well with strings.

share|improve this answer
    
+1 for almost the same solution at almost the same time. –  Howard Feb 3 at 13:40

C#: 250c

(compiled to exe; assumes "line" means from stdin, so ran as type trianglesfile | counttri.exe)

using System;using System.Linq;class P{static void Main(){int n=int.Parse(Console.ReadLine());var a=new string[n];while(--n>=0)a[n]=string.Join(":",Console.ReadLine().Split(' ').OrderBy(x=>x));Console.Write(a.GroupBy(s=>s).Count(g=>g.Count()==1));}}

Ungolfed:

using System;
using System.Linq;

class P
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());            // reads line from stdin; converts to int without validation
        var a = new string[n];

        while (--n >= 0) 
            a[n] = string.Join(":",                       // re-stringfy the following:
                               Console.ReadLine()         //  - read the next line
                                      .Split(' ')         //  - splits by space to form an array of sides
                                      .OrderBy(x => x)    //  - sorts by default comparison 
                   );

        Console.Write(
            a.GroupBy(s => s)                             // group on the sorted, stringified value
             .Count(g => g.Count() == 1)                  // count the number of groups which have 1 member
        );
    }
}

C#: 116c

(via LINQPad, in "C# Statements" mode; assumes "line" means any single line from an arbitrary string s, definition not counted)

string s = @"5
1 2 3
2 1 3
4 5 6
3 1 2
8 7 6";            // <- input not included in overall count

Regex.Split(s,"\r\n").Skip(1).GroupBy(x=>string.Join(":",x.Split(' ').OrderBy(y=>y))).Count(g=>g.Count()==1).Dump();

Ungolfed:

string s = @"5
1 2 3
2 1 3
4 5 6
3 1 2
8 7 6";                                              // literal string definition, not counted

Regex.Split(s, "\r\n")                               // split on regex
     .Skip(1)                                        // who cares about the number of following lines?
     .GroupBy(x => string.Join(":",                  // re-stringify the following:
                               x.Split(' ')          //  - split by space into sides array
                                .OrderBy(y => y)))   //  - sort sides array
     .Count(g => g.Count() == 1)                     // count the number of groups that have 1 member
     .Dump();                                        // Output into LINQPad results pane
share|improve this answer

D - 201, 172, 171, 170 chars

Reads from STDIN only and relies on D 2.x for UFCS (Uniform Function Call Syntax) and assumes the -property compiler flag isn't set.

import std.stdio,std.algorithm,std.conv;void main(){int n=[stdin.readln[0]].to!int;char[][]a;while(n-->0)a~=stdin.readln.dup.sort;a.group.filter!(x=>x[1]<2).count.write;}

Normal indented version:

import std.stdio, std.algorithm, std.conv;

void main()
{
    int n = [ stdin.readln[0] ].to!int;
    char[][] a;

    while( n --> 0 )
        a ~= stdin.readln.dup.sort;

    a.group.filter!( x => x[1] < 2 ).count.write;
}

Input:

F:\Code\Other>rdmd tri.d
5
7 6 5
5 7 6
8 2 9
2 3 4
2 4 3

Output:

1
share|improve this answer

Perl, 53 50 45

perl -nE '$h{"@{[sort split]}"}++}{say-1+grep{!log}values%h'

Input either STDIN or append filename to the line above. "50" -- counting inside ' ' and n.

Another edit:

perl -nE '$h{1,sort split}++}{say-1+grep{!log}values%h'

i.e. 45. As I understand, the trick here is to force list context when evaluating hash index. Then Perl joins this list with $; (cf. with $" in my previous take). Without 1,, sort evaluates in scalar context = undefined behaviour.

share|improve this answer
    
The rules require you to count the cmdline flags you use other than -e/-E, so your total is 39. –  breadbox Feb 3 at 19:49
    
Fixed, but managed to make it 38 ;) –  VadimR Feb 3 at 21:53
    
Nice. Unfortunately, I just realized that this is solving a problem different than the one in the description. Your code is counting the number of triangles after omitting repeated triangles. But the description's test case makes it clear that the problem is to count the number of triangles that are not repeated at all. (For example, your program returns 3 instead of 1 for the given test case.) –  breadbox Feb 3 at 22:09
    
You are certainly right. I updated my answer. Thanks a lot for checking and pointing out. –  VadimR Feb 3 at 22:44

bash — 98 113 characters

I'm sure this isn't the smallest bash solution (assumes i is the input file):

rm -f w;sed 1d i|while read L;do echo $L|xargs -n 1|sort|xargs -n 3 >>w;done;sort <w|uniq -u|wc -l

Explanation:

rm -f w; // delete working file

sed 1d i|while read L; // read each line, skipping the first one

do echo $L|xargs -n 1|sort|xargs -n 3 >>w; // normalize each line by sorting the elements

done; // end of while loop

sort <w|uniq -u|wc -l // sort all the lines, pull out unique ones and count

share|improve this answer

Haskell (116, 99 w/o import)

import Data.List
main=getContents>>=(\x->print((length.(filter((<2).length)).group.(map(sort.words)).tail.lines)x))

If the file input contains the example input, run with:

$ cat input | runghc solution.hs
1
share|improve this answer

Ruby, 55 characters

a=$<.map{|s|s.split.sort}
p a.count{|b|1==a.count(b)}-1

The code is pretty straightforward for golfing standards:

  • first a=$<.map{|s|s.split.sort} reads all lineas from stdin, splits them into arrays, sorts them and stores them in the array a,
  • then a.count{|b|1==a.count(b)} counts how many of those arrays appear only once in a,
  • and the final -1 is just not to count the first line read from stdin :)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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