Faces from a mesh: Difference between revisions

From Rosetta Code
Content added Content deleted
(Added 11l)
(→‎{{header|Haskell}}: added solution)
Line 305: Line 305:
H => Invalid edge format
H => Invalid edge format
</pre>
</pre>

=={{header|Haskell}}==
<lang haskell>import Data.List (find, delete, (\\))
import Control.Applicative ((<|>))

------------------------------------------------------------

newtype Perimeter a = Perimeter [a]
deriving Show

instance Eq a => Eq (Perimeter a) where
Perimeter p1 == Perimeter p2 =
null (p1 \\ p2)
&& ((p1 `elem` zipWith const (iterate rotate p2) p1)
|| Perimeter p1 == Perimeter (reverse p2))

rotate lst = zipWith const (tail (cycle lst)) lst

toEdges :: Ord a => Perimeter a -> Maybe (Edges a)
toEdges (Perimeter ps)
| allDifferent ps = Just . Edges $ zipWith ord ps (tail (cycle ps))
| otherwise = Nothing
where
ord a b = if a < b then (a, b) else (b, a)

allDifferent [] = True
allDifferent (x:xs) = all (x /=) xs && allDifferent xs

------------------------------------------------------------

newtype Edges a = Edges [(a, a)]
deriving Show

instance Eq a => Eq (Edges a) where
e1 == e2 = toPerimeter e1 == toPerimeter e2

toPerimeter :: Eq a => Edges a -> Maybe (Perimeter a)
toPerimeter (Edges ((a, b):es)) = Perimeter . (a :) <$> go b es
where
go x rs
| x == a = return []
| otherwise = do
p <- find ((x ==) . fst) rs <|> find ((x ==) . snd) rs
let next = if fst p == x then snd p else fst p
(x :) <$> go next (delete p rs)</lang>

First task.

<pre>λ> Perimeter [8,1,3] == Perimeter [1,3,8]
True

λ> Perimeter [8,1,3] == Perimeter [1,8,3]
True

λ> Perimeter [18,8,14,10,12,17,19] == Perimeter [8,14,10,12,17,19,18]
True

λ> Perimeter [18,8,14,10,12,17,19] == Perimeter [8,14,10,12,17,19]
False

λ> Perimeter [18,8,14,10,12,17,19] == Perimeter [8,14,10,12,17,18,19]
False</pre>

Second task
<pre>λ> toPerimeter (Edges [(1,11),(7,11),(1,7)])
Just (Perimeter [1,11,7])

λ> toPerimeter (Edges [(11,23),(1,17),(17,23),(1,11)])
Just (Perimeter [11,23,17,1])

λ> toPerimeter (Edges [(8,14),(17,19),(10,12),(10,14),(12,17),(8,18),(18,19)])
Just (Perimeter [8,14,10,12,17,19,18])

λ> toPerimeter (Edges [(1,3),(9,11),(3,11),(1,11)])
Nothing</pre>


=={{header|J}}==
=={{header|J}}==

Revision as of 03:24, 18 November 2021

Task
Faces from a mesh
You are encouraged to solve this task according to the task description, using any language you may know.

A mesh defining a surface has uniquely numbered vertices, and named, simple-polygonal faces described usually by an ordered list of edge numbers going around the face,


For example: External image of two faces
Rough textual version without edges: 


      1         
                        17
 7   A
             B

       11                     
                  23
  • A is the triangle (1, 11, 7), or equally (7, 11, 1), going anti-clockwise, or

any of all the rotations of those ordered vertices. 

      1         
                        
 7   A
            

       11
  • B is the four-sided face (1, 17, 23, 11), or equally (23, 17, 1, 11) or any

of their rotations. 

1         
                  17

       B

 11                     
            23

Let's call the above the perimeter format as it traces around the perimeter.

A second format

A separate algorithm returns polygonal faces consisting of a face name and an unordered set of edge definitions for each face.

  • A single edge is described by the vertex numbers at its two ends, always in

ascending order.

  • All edges for the face are given, but in an undefined order.

For example face A could be described by the edges (1, 11), (7, 11), and (1, 7) (The order of each vertex number in an edge is ascending, but the order in which the edges are stated is arbitrary).

Similarly face B could be described by the edges (11, 23), (1, 17), (17, 23), and (1, 11) in arbitrary order of the edges.

Let's call this second format the edge format.


Task

1. Write a routine to check if two perimeter formatted faces have the same perimeter. Use it to check if the following pairs of perimeters are the same: 

 Q: (8, 1, 3)
 R: (1, 3, 8)

 U: (18, 8, 14, 10, 12, 17, 19)
 V: (8, 14, 10, 12, 17, 19, 18)

2. Write a routine and use it to transform the following faces from edge to perimeter format. 

 E: {(1, 11), (7, 11), (1, 7)}
 F: {(11, 23), (1, 17), (17, 23), (1, 11)}
 G: {(8, 14), (17, 19), (10, 12), (10, 14), (12, 17), (8, 18), (18, 19)}
 H: {(1, 3), (9, 11), (3, 11), (1, 11)}

Show your output here.

11l

Translation of: Python

<lang 11l>F perim_equal(p1, =p2) 

  I p1.len != p2.len | Set(p1) != Set(p2)
     R 0B
  I any((0 .< p1.len).map(n -> @p2 == (@p1[n ..] [+] @p1[0 .< n])))
     R 1B
  p2 = reversed(p2)
  R any((0 .< p1.len).map(n -> @p2 == (@p1[n ..] [+] @p1[0 .< n])))

F edge_to_periphery(e) 

  V edges = sorted(e)
  [Int] p
  I !edges.empty
     p = [edges[0][0], edges[0][1]]
     edges.pop(0)
  V last = I !p.empty {p.last} E -1
  L !edges.empty
     L(ij) edges
        V (i, j) = ij
        I i == last
           p.append(j)
           last = j
           edges.pop(L.index)
           L.break
        E I j == last
           p.append(i)
           last = i
           edges.pop(L.index)
           L.break
     L.was_no_break
        R ‘>>>Error! Invalid edge format<<<’
  R String(p[0 .< (len)-1])

print(‘Perimeter format equality checks:’) L(eq_check) [(‘Q’, [8, 1, 3], 

             ‘R’, [1, 3, 8]),
            (‘U’, [18, 8, 14, 10, 12, 17, 19],
             ‘V’, [8, 14, 10, 12, 17, 19, 18])]
  V (n1, p1, n2, p2) = eq_check
  V eq = I perim_equal(p1, p2) {‘==’} E ‘!=’
  print(‘  ’n1‘ ’eq‘ ’n2)

print("\nEdge to perimeter format translations:") V edge_d = [‘E’ = [(1, 11), (7, 11), (1, 7)], 

           ‘F’ = [(11, 23), (1, 17), (17, 23), (1, 11)],
           ‘G’ = [(8, 14), (17, 19), (10, 12), (10, 14), (12, 17), (8, 18), (18, 19)],
           ‘H’ = [(1, 3), (9, 11), (3, 11), (1, 11)]]

L(name, edges) edge_d 

  print(‘  ’name‘: ’edges"\n     -> "edge_to_periphery(edges))</lang>
Output:
Perimeter format equality checks:
  Q == R
  U == V

Edge to perimeter format translations:
  E: [(1, 11), (7, 11), (1, 7)]
     -> [1, 7, 11]
  F: [(11, 23), (1, 17), (17, 23), (1, 11)]
     -> [1, 11, 23, 17]
  G: [(8, 14), (17, 19), (10, 12), (10, 14), (12, 17), (8, 18), (18, 19)]
     -> [8, 14, 10, 12, 17, 19, 18]
  H: [(1, 3), (9, 11), (3, 11), (1, 11)]
     -> >>>Error! Invalid edge format<<<

Go

<lang go>package main

import ( 

   "fmt"
   "sort"

)

// Check a slice contains a value. func contains(s []int, f int) bool { 

   for _, e := range s {
       if e == f {
           return true
       }
   }
   return false

}

// Assumes s1, s2 are of same length. func sliceEqual(s1, s2 []int) bool { 

   for i := 0; i < len(s1); i++ {
       if s1[i] != s2[i] {
           return false
       }
   }
   return true

}

// Reverses slice in place. func reverse(s []int) { 

   for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
       s[i], s[j] = s[j], s[i]
   }

}

// Check two perimeters are equal. func perimEqual(p1, p2 []int) bool { 

   le := len(p1)
   if le != len(p2) {
       return false
   }
   for _, p := range p1 {
       if !contains(p2, p) {
           return false
       }
   }
   // use copy to avoid mutating 'p1'
   c := make([]int, le)
   copy(c, p1)
   for r := 0; r < 2; r++ {
       for i := 0; i < le; i++ {
           if sliceEqual(c, p2) {
               return true
           }
           // do circular shift to right
           t := c[le-1]
           copy(c[1:], c[0:le-1])
           c[0] = t
       }
       // now process in opposite direction
       reverse(c)
   }
   return false

}

type edge [2]int

// Translates a face to perimeter format. func faceToPerim(face []edge) []int { 

   // use copy to avoid mutating 'face'
   le := len(face)
   if le == 0 {
       return nil
   }
   edges := make([]edge, le)
   for i := 0; i < le; i++ {
       // check edge pairs are in correct order
       if face[i][1] <= face[i][0] {
           return nil
       }
       edges[i] = face[i]
   }
   // sort edges in ascending order
   sort.Slice(edges, func(i, j int) bool {
       if edges[i][0] != edges[j][0] {
           return edges[i][0] < edges[j][0]
       }
       return edges[i][1] < edges[j][1]
   })
   var perim []int
   first, last := edges[0][0], edges[0][1]
   perim = append(perim, first, last)
   // remove first edge
   copy(edges, edges[1:])
   edges = edges[0 : le-1]
   le--

outer: 

   for le > 0 {
       for i, e := range edges {
           found := false
           if e[0] == last {
               perim = append(perim, e[1])
               last, found = e[1], true
           } else if e[1] == last {
               perim = append(perim, e[0])
               last, found = e[0], true
           }
           if found {
               // remove i'th edge
               copy(edges[i:], edges[i+1:])
               edges = edges[0 : le-1]
               le--
               if last == first {
                   if le == 0 {
                       break outer
                   } else {
                       return nil
                   }
               }
               continue outer
           }
       }
   }
   return perim[0 : len(perim)-1]

}

func main() { 

   fmt.Println("Perimeter format equality checks:")
   areEqual := perimEqual([]int{8, 1, 3}, []int{1, 3, 8})
   fmt.Printf("  Q == R is %t\n", areEqual)
   areEqual = perimEqual([]int{18, 8, 14, 10, 12, 17, 19}, []int{8, 14, 10, 12, 17, 19, 18})
   fmt.Printf("  U == V is %t\n", areEqual)
   e := []edge{{7, 11}, {1, 11}, {1, 7}}
   f := []edge{{11, 23}, {1, 17}, {17, 23}, {1, 11}}
   g := []edge{{8, 14}, {17, 19}, {10, 12}, {10, 14}, {12, 17}, {8, 18}, {18, 19}}
   h := []edge{{1, 3}, {9, 11}, {3, 11}, {1, 11}}
   fmt.Println("\nEdge to perimeter format translations:")
   for i, face := range [][]edge{e, f, g, h} {
       perim := faceToPerim(face)
       if perim == nil {
           fmt.Printf("  %c => Invalid edge format\n", i + 'E')
       } else {
           fmt.Printf("  %c => %v\n", i + 'E', perim)
       }
   }

}</lang>

Output:
Perimeter format equality checks:
  Q == R is true
  U == V is true

Edge to perimeter format translations:
  E => [1 7 11]
  F => [1 11 23 17]
  G => [8 14 10 12 17 19 18]
  H => Invalid edge format

Haskell

<lang haskell>import Data.List (find, delete, (\\)) import Control.Applicative ((<|>))

newtype Perimeter a = Perimeter [a] 

 deriving Show

instance Eq a => Eq (Perimeter a) where 

 Perimeter p1 == Perimeter p2 =
   null (p1 \\ p2)
   && ((p1 `elem` zipWith const (iterate rotate p2) p1)
       || Perimeter p1 == Perimeter (reverse p2))

rotate lst = zipWith const (tail (cycle lst)) lst

toEdges :: Ord a => Perimeter a -> Maybe (Edges a) toEdges (Perimeter ps) 

 | allDifferent ps = Just . Edges $ zipWith ord ps (tail (cycle ps))
 | otherwise = Nothing
 where
   ord a b = if a < b then (a, b) else (b, a)

allDifferent [] = True allDifferent (x:xs) = all (x /=) xs && allDifferent xs

newtype Edges a = Edges [(a, a)] 

 deriving Show

instance Eq a => Eq (Edges a) where 

 e1 == e2 = toPerimeter e1 == toPerimeter e2

toPerimeter :: Eq a => Edges a -> Maybe (Perimeter a) toPerimeter (Edges ((a, b):es)) = Perimeter . (a :) <$> go b es 

 where
   go x rs
     | x == a = return []
     | otherwise = do
         p <- find ((x ==) . fst) rs <|> find ((x ==) . snd) rs
         let next = if fst p == x then snd p else fst p
         (x :) <$> go next (delete p rs)</lang>

First task. 

λ> Perimeter [8,1,3] == Perimeter [1,3,8]
True

λ> Perimeter [8,1,3] == Perimeter [1,8,3]
True

λ> Perimeter [18,8,14,10,12,17,19] == Perimeter [8,14,10,12,17,19,18]
True

λ> Perimeter [18,8,14,10,12,17,19] == Perimeter [8,14,10,12,17,19]
False

λ> Perimeter [18,8,14,10,12,17,19] == Perimeter [8,14,10,12,17,18,19]
False

Second task 

λ> toPerimeter (Edges [(1,11),(7,11),(1,7)])
Just (Perimeter [1,11,7])

λ> toPerimeter (Edges [(11,23),(1,17),(17,23),(1,11)])
Just (Perimeter [11,23,17,1])

λ> toPerimeter (Edges [(8,14),(17,19),(10,12),(10,14),(12,17),(8,18),(18,19)])
Just (Perimeter [8,14,10,12,17,19,18])

λ> toPerimeter (Edges [(1,3),(9,11),(3,11),(1,11)])
Nothing

J

First task: 

   NB. construct a list of all rotations of one of the faces
   NB. including all rotations of the reversed list.
   NB. Find out if the other face is a member of this list.

   NB. ,&:rotations -> append, but first enlist the rotations.


   rotations=. |."0 1~ i.@#
   reverse=: |.
   same_perimeter=: e. (,&:rotations reverse)

   (3, 1, 8)same_perimeter(8, 1, 3)
1

   (18, 8, 14, 10, 12, 17, 19)same_perimeter(8, 14, 10, 12, 17, 19, 18)
1

Secondly: <lang J> edge_to_node=: 3 :0 

assert. 2 = #/.~ , y [ 'expect each node to appear twice'
oel=. 1 2 {. y
Y=. }. y
while. # Y do.
 i =. <. -: 1 i.~ , Y (e."1) {: oel
 assert. 0 < # i [ 'isolated edge detected'
 oel =. oel , i { Y
 Y =. i ({. , (}.~ >:)~) Y
end.
~. , oel

) </lang> 

   boxdraw_j_ 0

   ]TESTS=: ([: < _2 ]\ ".);._2'{}'-.~0 :0
{(1, 11), (7, 11), (1, 7)}
{(11, 23), (1, 17), (17, 23), (1, 11)}
{(8, 14), (17, 19), (10, 12), (10, 14), (12, 17), (8, 18), (18, 19)}
{(1, 3), (9, 11), (3, 11), (1, 11)}
)
┌────┬─────┬─────┬────┐
│1 11│11 23│ 8 14│1  3│
│7 11│ 1 17│17 19│9 11│
│1  7│17 23│10 12│3 11│
│    │ 1 11│10 14│1 11│
│    │     │12 17│    │
│    │     │ 8 18│    │
│    │     │18 19│    │
└────┴─────┴─────┴────┘



   edge_to_node ::('failure'"_)&.> TESTS
┌──────┬──────────┬───────────────────┬───────┐
│1 11 7│11 23 17 1│8 14 10 12 17 19 18│failure│
└──────┴──────────┴───────────────────┴───────┘


   edge_to_node _1 {:: TESTS
|assertion failure: edge_to_node
|       2=#/.~,y['expect each node to appear twice'

Julia

<lang julia>iseq(f, g) = any(n -> f == circshift(g, n), 1:length(g))

function toface(evec) 

   try
       ret, edges = collect(evec[1]), copy(evec[2:end])
       while !isempty(edges)
           i = findfirst(x -> ret[end] == x[1] || ret[end] == x[2], edges)
           push!(ret, ret[end] == edges[i][1] ? edges[i][2] : edges[i][1])
           deleteat!(edges, i)
       end
       return ret[1:end-1]
   catch
       println("Invalid edges vector: $evec")
       exit(1)
   end

end

const faces1 = [ 

   [[8, 1, 3], [1, 3, 8]],
   [[18, 8, 14, 10, 12, 17, 19], [8, 14, 10, 12, 17, 19, 18]]

]

const faces2 = [ 

   [(1, 11), (7, 11), (1, 7)], [(11, 23), (1, 17), (17, 23), (1, 11)],
   [(8, 14), (17, 19), (10, 12), (10, 14), (12, 17), (8, 18), (18, 19)],
   [(1, 3), (9, 11), (3, 11), (1, 11)]

]

for faces in faces1 

   println("Faces are ", iseq(faces[1], faces[2]) ? "" : "not ", "equivalent.")

end

for face in faces2 

   println(toface(face))

end

</lang>

Output:
Faces are equivalent.
Faces are equivalent.
[1, 11, 7]
[11, 23, 17, 1]
[8, 14, 10, 12, 17, 19, 18]
Invalid edges vector: Tuple{Int64,Int64}[(1, 3), (9, 11), (3, 11), (1, 11)]

Nim

<lang Nim>import algorithm, strutils

type 

 Perimeter = seq[int]
 Face = tuple[name: char; perimeter: Perimeter]
 Edge = tuple[first, last: int]

const None = -1 # No point.

  1. ---------------------------------------------------------------------------------------------------

func isSame(p1, p2: Perimeter): bool = 

 ## Return "true" if "p1" and "p2" represent the same face.

 if p1.len != p2.len: return false

 for p in p1:
   if p notin p2: return false

 var start = p2.find(p1[0])
 if p1 == p2[start..^1] & p2[0..<start]:
   return true

 let p3 = reversed(p2)
 start = p3.find(p1[0])
 if p1 == p3[start..^1] & p3[0..<start]:
   return true
  1. ---------------------------------------------------------------------------------------------------

func `$`(perimeter: Perimeter): string = 

 ## Convert a perimeter to a string.
 '(' & perimeter.join(", ") & ')'

func `$`(face: Face): string = 

 ## Convert a perimeter formatted face to a string.
 face.name & $face.perimeter
  1. ---------------------------------------------------------------------------------------------------

func toPerimeter(edges: seq[Edge]): Perimeter = 

 ## Convert a list of edges to perimeter representation.
 ## Return an empty perimeter if the list of edges doesn’t represent a face.

 var edges = edges
 let firstEdge = edges.pop()       # First edge taken in account.
 var nextPoint = firstEdge.first   # Next point to search in remaining edges.
 result.add(nextpoint)

 while edges.len > 0:
   # Search an edge.
   var idx = None
   for i, e in edges:
     if e.first == nextPoint or e.last == nextPoint:
       idx = i
       nextPoint = if nextpoint == e.first: e.last else: e.first
       break
   if idx == None:
     return @[]      # No edge found containing "newPoint".

   # Add next point to perimeter and remove the edge.
   result.add(nextPoint)
   edges.del(idx)

 # Check that last added point is the expected one.
 if nextPoint != firstEdge.last:
   return @[]
  1. ———————————————————————————————————————————————————————————————————————————————————————————————————

when isMainModule: 

 # List of pairs of perimeter formatted faces to compare.
 const FP = [(('P', @[8, 1, 3]), ('R', @[1, 3, 8])),
             (('U', @[18, 8, 14, 10, 12, 17, 19]), ('V', @[8, 14, 10, 12, 17, 19, 18]))]

 echo "Perimeter comparison:"
 for (p1, p2) in FP:
   echo p1, if isSame(p1[1], p2[1]): " is same as " else: "is not same as", p2

 # List of edge formatted faces.
 const FE = {'E': @[(1, 11), (7, 11), (1, 7)],
             'F': @[(11, 23), (1, 17), (17, 23), (1, 11)],
             'G': @[(8, 14), (17, 19), (10, 12), (10, 14), (12, 17), (8, 18), (18, 19)],
             'H': @[(1, 3), (9, 11), (3, 11), (1, 11)]}

 echo ""
 echo "Conversion from edge to perimeter format:"
 for (faceName, edges) in FE:
   let perimeter = edges.toPerimeter()
   echo faceName, ": ", if perimeter.len == 0: "Invalid edge list" else: $perimeter</lang>
Output:
Perimeter comparison:
P(8, 1, 3) is same as R(1, 3, 8)
U(18, 8, 14, 10, 12, 17, 19) is same as V(8, 14, 10, 12, 17, 19, 18)

Conversion from edge to perimeter format:
E: (1, 11, 7)
F: (1, 17, 23, 11)
G: (18, 8, 14, 10, 12, 17, 19)
H: Invalid edge list

Perl

Translation of: Raku

<lang perl>use strict; use warnings; use feature 'say'; use Set::Scalar; use Set::Bag; use Storable qw(dclone);

sub show { my($pts) = @_; my $p='( '; $p .= '(' . join(' ',@$_) . ') ' for @$pts; $p.')' }

sub check_equivalence { 

   my($a, $b) = @_;
   Set::Scalar->new(@$a) == Set::Scalar->new(@$b)

}

sub edge_to_periphery { 

   my $a = dclone \@_;

   my $bag_a = Set::Bag->new;
   for my $p (@$a) {
       $bag_a->insert( @$p[0] => 1);
       $bag_a->insert( @$p[1] => 1);
   }
   2 != @$bag_a{$_} and return 0 for keys %$bag_a;

   my $b = shift @$a;
   while ($#{$a} > 0) {
       for my $k (0..$#{$a}) {
           my $v = @$a[$k];
           if (@$v[0] == @$b[-1]) {
               push @$b, @$v[1];
               splice(@$a,$k,1);
               last
           } elsif (@$v[1] == @$b[-1]) {
               push @$b, @$v[0];
               splice(@$a,$k,1);
               last
           }
       }
   }
   @$b;

}

say 'Perimeter format equality checks:'; for ([[8, 1, 3], [1, 3, 8]], 

    [[18, 8, 14, 10, 12, 17, 19], [8, 14, 10, 12, 17, 19, 18]]) {
   my($a, $b) = @$_;
   say '(' . join(', ', @$a) . ')  equivalent to  (' . join(', ', @$b) . ')? ',
       check_equivalence($a, $b) ? 'True' : 'False';

}

say "\nEdge to perimeter format translations:"; for ([[1, 11], [7, 11], [1, 7]], 

    [[11, 23], [1, 17], [17, 23], [1, 11]],
    [[8, 14], [17, 19], [10, 12], [10, 14], [12, 17], [8, 18], [18, 19]],
    [[1, 3], [9, 11], [3, 11], [1, 11]]) {
   say show($_) . '  ==>  (' .  (join ' ', edge_to_periphery(@$_) or 'Invalid edge format') . ')'

}</lang>

Output:
Perimeter format equality checks:
(8, 1, 3)  equivalent to  (1, 3, 8)? True
(18, 8, 14, 10, 12, 17, 19)  equivalent to  (8, 14, 10, 12, 17, 19, 18)? True

Edge to perimeter format translations:
( (1 11) (7 11) (1 7) )  ==>  (1 11 7)
( (11 23) (1 17) (17 23) (1 11) )  ==>  (11 23 17 1)
( (8 14) (17 19) (10 12) (10 14) (12 17) (8 18) (18 19) )  ==>  (8 14 10 12 17 19 18)
( (1 3) (9 11) (3 11) (1 11) )  ==>  Invalid edge format

Phix

<lang Phix>function perequiv(sequence a, b) -- Works by aligning and rotating in one step, so theoretically much faster on massive sets. -- (ahem, faster than multiple rotates, index-only loops would obviously be even faster...) 

   bool res = (length(a)==length(b))
   if res and length(a)>0 then
       integer k = find(a[1],b)
       if k=0 then
           res = false
       else
           -- align with a (ie make b[1]==a[1], by
           -- rotating b k places in one operation)
           b = b[k..$]&b[1..k-1]
           if a!=b then
               -- eg {8,3,4,5} <=> {8,5,4,3}, ie
               -- rotate *and* keep in alignment.
               b[2..$] = reverse(b[2..$])
               res = (a==b)
           end if
       end if
   end if

-- return res 

   return {"false","true"}[res+1]

end function

function edge2peri(sequence edges) 

   sequence was = edges, res = {}
   string error = ""
   integer lnk = 0
   if length(edges)<2 then
       error = "too short"
   else

-- edges = sort(edges) -- (see note below) 

       res = edges[1]
       edges = edges[2..$]
       lnk = res[2]
       while length(edges) and error="" do
           bool found = false
           for i=1 to length(edges) do
               integer k = find(lnk,edges[i])
               if k then
                   lnk = edges[i][3-k]
                   edges[i..i] = {}
                   if edges={} then
                       if lnk!=res[1] then error = "oh dear" end if
                   else
                       if find(lnk,res) then error = "oops" end if
                       res &= lnk
                   end if
                   found = true
                   exit
               end if
           end for
           if not found then error = "bad link" exit end if
       end while
   end if
   if length(error) then res = {error,res,lnk,edges,was} end if
   return res

end function

constant ptests = {{{8, 1, 3}, {1, 3, 8}}, 

                  {{18, 8, 14, 10, 12, 17, 19}, {8, 14, 10, 12, 17, 19, 18}},
                   -- (check our results below against Go etc)
                  {{1,11,7},{1,7,11}},
                  {{11,23,17,1},{1,11,23,17}}}

for i=1 to length(ptests) do 

   sequence {p,q} = ptests[i]
   printf(1,"%v equivalent to %v: %s\n",{p,q,perequiv(p,q)})

end for

constant etests = {{{1, 11}, {7, 11}, {1, 7}}, 

                  {{11, 23}, {1, 17}, {17, 23}, {1, 11}},
                  {{8, 14}, {17, 19}, {10, 12}, {10, 14}, {12, 17}, {8, 18}, {18, 19}},
                  {{1, 3}, {9, 11}, {3, 11}, {1, 11}}}

for i=1 to length(etests) do 

   printf(1,"%v\n",{edge2peri(etests[i])})

end for</lang>

Output:

(second part matches Julia/Perl: un-comment that sort above to match Go/Python/zkl) 

{8,1,3} equivalent to {1,3,8}: true
{18,8,14,10,12,17,19} equivalent to {8,14,10,12,17,19,18}: true
{1,11,7} equivalent to {1,7,11}: true
{11,23,17,1} equivalent to {1,11,23,17}: true
{1,11,7}
{11,23,17,1}
{8,14,10,12,17,19,18}
{"bad link",{1,3,11,9},9,{{1,11}},{{1,3},{9,11},{3,11},{1,11}}}

Python

<lang python>def perim_equal(p1, p2): 

   # Cheap tests first
   if len(p1) != len(p2) or set(p1) != set(p2):
       return False
   if any(p2 == (p1[n:] + p1[:n]) for n in range(len(p1))):
       return True
   p2 = p2[::-1] # not inplace
   return any(p2 == (p1[n:] + p1[:n]) for n in range(len(p1)))

def edge_to_periphery(e): 

   edges = sorted(e)
   p = list(edges.pop(0)) if edges else []
   last = p[-1] if p else None
   while edges:
       for n, (i, j) in enumerate(edges):
           if i == last:
               p.append(j)
               last = j
               edges.pop(n)
               break
           elif j == last:
               p.append(i)
               last = i
               edges.pop(n)
               break
       else:
           #raise ValueError(f'Invalid edge format: {e}')
           return ">>>Error! Invalid edge format<<<"
   return p[:-1]

if __name__ == '__main__': 

   print('Perimeter format equality checks:')
   for eq_check in [
           { 'Q': (8, 1, 3),
             'R': (1, 3, 8)},
           { 'U': (18, 8, 14, 10, 12, 17, 19),
             'V': (8, 14, 10, 12, 17, 19, 18)} ]:
       (n1, p1), (n2, p2) = eq_check.items()
       eq = '==' if perim_equal(p1, p2) else '!='
       print(' ', n1, eq, n2)

   print('\nEdge to perimeter format translations:')
   edge_d = {
    'E': {(1, 11), (7, 11), (1, 7)},
    'F': {(11, 23), (1, 17), (17, 23), (1, 11)},
    'G': {(8, 14), (17, 19), (10, 12), (10, 14), (12, 17), (8, 18), (18, 19)},
    'H': {(1, 3), (9, 11), (3, 11), (1, 11)}
           }
   for name, edges in edge_d.items():
       print(f"  {name}: {edges}\n     -> {edge_to_periphery(edges)}")</lang>
Output:
Perimeter format equality checks:
  Q == R
  U == V

Edge to perimeter format translations:
  E: {(7, 11), (1, 11), (1, 7)}
     -> [1, 7, 11]
  F: {(11, 23), (1, 11), (1, 17), (17, 23)}
     -> [1, 11, 23, 17]
  G: {(8, 14), (17, 19), (10, 12), (10, 14), (12, 17), (8, 18), (18, 19)}
     -> [8, 14, 10, 12, 17, 19, 18]
  H: {(1, 11), (9, 11), (1, 3), (3, 11)}
     -> >>>Error! Invalid edge format<<<

Raku

(formerly Perl 6)

Works with: Rakudo version 2019.11

<lang perl6>sub check-equivalence ($a, $b) { so $a.Bag eqv $b.Bag }

sub edge-to-periphery (@a is copy) { 

   return Nil unless @a.List.Bag.values.all == 2;
   my @b = @a.shift.flat;
   while @a > 1 {
       for @a.kv -> $k, $v {
           if $v[0] == @b.tail {
               @b.push: $v[1];
               @a.splice($k,1);
               last
           }
           elsif $v[1] == @b.tail {
               @b.push: $v[0];
               @a.splice($k,1);
               last
           }
       }
   }
   @b

}

say 'Perimeter format equality checks:';

for (8, 1, 3), (1, 3, 8), 

   (18, 8, 14, 10, 12, 17, 19), (8, 14, 10, 12, 17, 19, 18)
 -> $a, $b {
    say "({$a.join: ', '})  equivalent to  ({$b.join: ', '})? ",
        check-equivalence($a, $b)

}

say "\nEdge to perimeter format translations:";

for ((1, 11), (7, 11), (1, 7)), 

   ((11, 23), (1, 17), (17, 23), (1, 11)),
   ((8, 14), (17, 19), (10, 12), (10, 14), (12, 17), (8, 18), (18, 19)),
   ((1, 3), (9, 11), (3, 11), (1, 11))
 {
   .gist.print;
   say "  ==>  ({.&edge-to-periphery || 'Invalid edge format'})";

}</lang>

Output:
Perimeter format equality checks:
(8, 1, 3)  equivalent to  (1, 3, 8)? True
(18, 8, 14, 10, 12, 17, 19)  equivalent to  (8, 14, 10, 12, 17, 19, 18)? True

Edge to perimeter format translations:
((1 11) (7 11) (1 7))  ==>  (1 11 7)
((11 23) (1 17) (17 23) (1 11))  ==>  (11 23 17 1)
((8 14) (17 19) (10 12) (10 14) (12 17) (8 18) (18 19))  ==>  (8 14 10 12 17 19 18)
((1 3) (9 11) (3 11) (1 11))  ==>  (Invalid edge format)

Wren

Translation of: Go
Library: Wren-sort
Library: Wren-fmt

<lang ecmascript>import "/sort" for Sort import "/fmt" for Fmt

// Assumes s1, s2 are of same length. var sliceEqual = Fn.new { |s1, s2| 

   for (i in 0...s1.count) {
       if (s1[i] != s2[i]) return false
   }
   return true

}

// Check two perimeters are equal. var perimEqual = Fn.new { |p1, p2| 

   var le = p1.count
   if (le != p2.count) return false
   for (p in p1) {
       if (!p2.contains(p)) return false
   }
   // use copy to avoid mutating 'p1'
   var c = p1.toList
   for (r in 0..1) {
       for (i in 0...le) {
           if (sliceEqual.call(c, p2)) return true
           // do circular shift to right
           var t = c[-1]
           for (i in le-2..0) c[i+1] = c[i]
           c[0] = t
       }
       // now process in opposite direction
       Sort.reverse(c) // reverses 'c' in place
   }
   return false

}

var faceToPerim = Fn.new { |face| 

   // use copy to avoid mutating 'face'
   var le = face.count
   if (le == 0) return []
   var edges = List.filled(le, null)
   for (i in 0...le) {
       // check edge pairs are in correct order
       if (face[i][1] <= face[i][0]) return []
       edges[i] = [face[i][0], face[i][1]]
   }
   // sort edges in ascending order
   var cmp = Fn.new { |e1, e2|
       if (e1[0] != e2[0]) {
           return (e1[0] - e2[0]).sign
       }
       return (e1[1] - e2[1]).sign
   }
   Sort.insertion(edges, cmp)
   var first = edges[0][0]
   var last  = edges[0][1]
   var perim = [first, last]
   // remove first edge
   edges.removeAt(0)
   le = le - 1
   while (le > 0) {
       var i = 0
       var outer = false
       var cont = false
       for (e in edges) {
           var found = false
           if (e[0] == last) {
               perim.add(e[1])
               last = e[1]
               found = true
           } else if (e[1] == last) {
               perim.add(e[0])
               last = e[0]  
               found = true
           }
           if (found) {
               // remove i'th edge
               edges.removeAt(i)
               le = le - 1
               if (last == first) {
                   if (le == 0) {
                       outer = true
                       break
                   } else {
                       return []
                   }
               }
               cont = true
               break
           }
           i = i + 1
       }
       if (outer && !cont) break
   }
   return perim[0..-2]

}

System.print("Perimeter format equality checks:") var areEqual = perimEqual.call([8, 1, 3], [1, 3, 8]) System.print(" Q == R is %(areEqual)") areEqual = perimEqual.call([18, 8, 14, 10, 12, 17, 19], [8, 14, 10, 12, 17, 19, 18]) System.print(" U == V is %(areEqual)") var e = [[7, 11], [1, 11], [1, 7]] var f = [[11, 23], [1, 17], [17, 23], [1, 11]] var g = [[8, 14], [17, 19], [10, 12], [10, 14], [12, 17], [8, 18], [18, 19]] var h = [[1, 3], [9, 11], [3, 11], [1, 11]] System.print("\nEdge to perimeter format translations:") var i = 0 for (face in [e, f, g, h]) { 

   var perim = faceToPerim.call(face)
   if (perim.isEmpty) {
       Fmt.print("  $c => Invalid edge format", i + 69) // 'E' is ASCII 69
   } else {
       Fmt.print("  $c => $n", i + 69, perim)
   }

}</lang>

Output:
Perimeter format equality checks:
  Q == R is true
  U == V is true

Edge to perimeter format translations:
  E => [1, 7, 11]
  E => [1, 11, 23, 17]
  E => [8, 14, 10, 12, 17, 19, 18]
  E => Invalid edge format

zkl

Translation of: Python

<lang zkl>fcn perimSame(p1, p2){ 

  if(p1.len() != p2.len()) return(False);
  False == p1.filter1('wrap(p){ (not p2.holds(p)) })

}

fcn edge_to_periphery(faces){ 

  edges:=faces.copy().sort(fcn(a,b){ if(a[0]!=b[0]) a[0]<b[0] else a[1]<b[1] });
  p,last := ( if(edges) edges.pop(0).copy() else T ), ( p and p[-1] or Void );
  while(edges){
     foreach i,j in (edges){
        if     (i==last){ p.append( last=j ); edges.del(__iWalker.idx); break; }
        else if(j==last){ p.append( last=i ); edges.del(__iWalker.idx); break; }
     }
     fallthrough{ return(">>>Error! Invalid edge format<<<") }
  }
  p[0,-1]	// last element not part of result

}</lang> <lang zkl>println("Perimeter format equality checks:"); ps:=T( T( T(8,1,3), T(1,3,8) ), 

      T( T(18, 8, 14, 10, 12, 17, 19), T(8, 14, 10, 12, 17, 19, 18) ) );

foreach p1,p2 in (ps) 

  { println(pp(p1), "  equivalent to  ", pp(p2), "? ", perimSame(p1,p2)) }

println("\nEdge to perimeter format translations:"); edge_d:=T( 

       T(T( 1, 11), T( 7, 11), T( 1,  7) ),
       T(T(11, 23), T( 1, 17), T(17, 23), T( 1, 11) ),
       T(T( 8, 14), T(17, 19), T(10, 12), T(10, 14), T(12, 17), T(8, 18), T(18, 19) ),
       T(T( 1,  3), T( 9, 11), T( 3, 11), T( 1, 11) ),
       );

foreach edges in (edge_d) 

  { println(ppp(edges), "  --> ", edge_to_periphery(edges)) }

fcn pp(a){ a.concat(", ","(",")") } fcn ppp(edges){ pp(edges.apply(pp)) }</lang>

Output:
Perimeter format equality checks:
(8, 1, 3)  equivalent to  (1, 3, 8)? True
(18, 8, 14, 10, 12, 17, 19)  equivalent to  (8, 14, 10, 12, 17, 19, 18)? True

Edge to perimeter format translations:
((1 11), (7 11), (1 7))  --> L(1,7,11)
((11 23), (1 17), (17 23), (1 11))  --> L(1,11,23,17)
((8 14), (17 19), (10 12), (10 14), (12 17), (8 18), (18 19))  --> L(8,14,10,12,17,19,18)
((1 3), (9 11), (3 11), (1 11))  --> >>>Error! Invalid edge format<<<
Retrieved from "https://rosettacode.org/wiki/Faces_from_a_mesh?oldid=296557"