Counting triangles

Question

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

Answer 1

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)

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

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 :) ).

Answer 7

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

Answer 8

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.

Answer 9

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

Answer 10

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

Answer 11

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 :)

Answer 12

#include<iostream>
#include<stdio.h>

void unique_check();

typedef struct triangle
{
    int s1, s2, s3;

}t;

t *tp[10];

int no;
void main()
{
    int  i,ch=0;

    do
    {
        int ch;
        printf("Enter the no triangles\n");
        scanf_s("%d", &no);

        for (i = 0; i < no; i++)
        {
            tp[i] = (t *)malloc(sizeof(t));
            printf("Enter the sides of %d triangle ", i);
            scanf_s("%d", &tp[i]->s1);
            scanf_s("%d", &tp[i]->s2);
            scanf_s("%d" ,&tp[i]->s3);
        }

        unique_check();

        printf("Enter the choice\n1 Perform more \n2 End\n");
        scanf_s("%d", &ch);
        system("cls");


    } while (ch!=2);

}


void unique_check()
{
    int i, j, f = 0, count = 0,tri=0;

    for (i = 0; i < no; i++)
    {
        for (j = 0; j < no; j++)
        {
            if (i == j)
                continue;
            else
            {
                if (((tp[i]->s1 == tp[j]->s1) || (tp[i]->s1 == tp[j]->s2) || (tp[i]->s1 == tp[j]->s3)) &&
                    ((tp[i]->s2 == tp[j]->s1) || (tp[i]->s2 == tp[j]->s2) || (tp[i]->s2 == tp[j]->s3)) &&
                    ((tp[i]->s3 == tp[j]->s1) || (tp[i]->s3 == tp[j]->s2) || (tp[i]->s3 == tp[j]->s3)))
                {
                    f = 0;
                    break;
                }

                else
                    f = 1;
            }

        }

        if (f == 1)
            tri++, f = 0;


    }

    printf("No of unique triangle\n%d\n",tri);



}

Answer 13

Husk, ¹² 8 bytes

#εkOmwt¶

Try it online!

-4 bytes from Leo.

Answer 14

Pyth, 17 bytes

This is not a serious participation, because Pyth is much younger than this question. Found the question while researching for another question and had to try it.

JmScd)t.zlfq/JT1J

Try it online: Pyth Compiler/Executor.

Wasted quite a few bytes on parsing the awkward input format.

       .z           read all of input
      t             discard the first line
 m                  map each line d to:
   cd)                 split d by spaces
  S                    and sort     
J                   store the result in J
          f     J   filter J for trianges T, which satisfy the condition:
            /JT        count T in J
           q   1        == 1
         l          length / number of remaining triangles, print

Another 17 byte solution, which uses the .r command (run length encoding).

lfqeT1.rSmScd)t.z