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.

with javascript_semantics
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(deep_copy(edges)) -- (see note below)
        res = deep_copy(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
