previndexinfonext

code guessing, round #16 (completed)

started at ; stage 2 at ; ended at

specification

your challenge this time around is to invert a binary tree. submissions can be written in javascript, haskell, d, apl, standard ml, pony, vim, or any language by chris pressey.

here's a binary tree:

    Λ
   / \
  Λ   \
 / \   \
w   a   Λ
       / \
      Λ   t
     / \
    t   z

they're in season, so these trees are ripe with juicy lowercase latin letters on all the leaves. your job will be to invert the tree, a classic interview problem:

      Λ
     / \
    /   Λ
   /   / \
  Λ   a   w
 / \
t   Λ
   / \
  z   t

see how it's, like, flipped? you just have to exchange the left and right branches at every depth.

your program may take and return strings in any of the following formats:

you don't have to take the same format that you return. you may also return ASCII art, subject to only the following conditions, and not any other conditions (wink wink ( ;) ) (see what I mean? (you only have to do what it says (nothing else)))):

API time:

results

  1. 👑 LyricLy +4 -1 = 3
    1. MathR (was GNU Radio Shows)
    2. razetime
    3. HelloBoi
    4. Olive (was IFcoltransG)
    5. Palaiologos
    6. IFcoltransG (was Olive)
    7. GNU Radio Shows (was MathR)
    8. SoundOfSpouting
  2. Olive +5 -3 = 2
    1. GNU Radio Shows
    2. LyricLy (was razetime)
    3. IFcoltransG (was LyricLy)
    4. HelloBoi
    5. razetime (was IFcoltransG)
    6. Palaiologos
    7. MathR
    8. SoundOfSpouting
  3. SoundOfSpouting +5 -3 = 2
    1. Olive (was GNU Radio Shows)
    2. razetime
    3. LyricLy
    4. HelloBoi
    5. IFcoltransG
    6. Palaiologos
    7. MathR (was Olive)
    8. GNU Radio Shows (was MathR)
  4. IFcoltransG +3 -1 = 2
    1. razetime
    2. SoundOfSpouting (was LyricLy)
    3. HelloBoi
    4. MathR (was Palaiologos)
    5. Olive
    6. LyricLy (was MathR)
    7. Palaiologos (was SoundOfSpouting)
  5. Palaiologos +3 -3 = 0
    1. MathR (was GNU Radio Shows)
    2. razetime
    3. SoundOfSpouting (was LyricLy)
    4. HelloBoi
    5. LyricLy (was IFcoltransG)
    6. Olive
    7. IFcoltransG (was MathR)
    8. GNU Radio Shows (was SoundOfSpouting)
  6. GNU Radio Shows +1 -1 = 0
    1. razetime
    2. SoundOfSpouting (was LyricLy)
    3. Palaiologos (was HelloBoi)
    4. Olive (was IFcoltransG)
    5. IFcoltransG (was Palaiologos)
    6. MathR (was Olive)
    7. HelloBoi (was MathR)
    8. LyricLy (was SoundOfSpouting)
  7. MathR +1 -1 = 0
    1. razetime (was GNU Radio Shows)
    2. IFcoltransG (was razetime)
    3. GNU Radio Shows (was LyricLy)
    4. Palaiologos (was HelloBoi)
    5. HelloBoi (was IFcoltransG)
    6. Olive (was Palaiologos)
    7. LyricLy (was Olive)
    8. SoundOfSpouting
  8. razetime +2 -5 = -3
    1. MathR (was GNU Radio Shows)
    2. SoundOfSpouting (was LyricLy)
    3. HelloBoi
    4. Palaiologos (was IFcoltransG)
    5. IFcoltransG (was Palaiologos)
    6. Olive
    7. GNU Radio Shows (was MathR)
    8. LyricLy (was SoundOfSpouting)
  9. HelloBoi +0 -6 = -6
    1. MathR (was GNU Radio Shows)
    2. LyricLy (was razetime)
    3. Palaiologos (was LyricLy)
    4. Olive (was IFcoltransG)
    5. SoundOfSpouting (was Palaiologos)
    6. razetime (was Olive)
    7. IFcoltransG (was MathR)
    8. GNU Radio Shows (was SoundOfSpouting)

entries

you can download all the entries

entry #1

written by GNU Radio Shows
submitted at
2 likes

guesses
comments 0

post a comment


golf.js ASCII text
1
2
v=a=>a.length-1?[v(a[1]),v(a[0])]:a
entry=s=>JSON.stringify(v(JSON.parse(s)))

entry #2

written by razetime
submitted at
5 likes

guesses
comments 0

post a comment


index.html ASCII text
index.mjs Unicode text, UTF-16, little-endian text
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
/*
* Usage:
* import * as CodeGuessing16 from path/to/index.mjs
* CodeGuessing16.entry(args)
*/

//export { entry }

var BRANCH = 'Λ'

class BinaryTreeNode {
  constructor() {
    this.left = null;
    this.right = null;
  }
}

function zip(l1, l2) {
  return l1.map(function(k, i) {
    return [k, l2[i]]
  })
}

function fromPrefix(input) {
  stack = []
  for(var i = input.length-1; i >= 0; i--) {
    if(input[i] == '`') {
      var node = new BinaryTreeNode()
      node.right = stack.pop()
      node.left = stack.pop()
      stack.push(node)
    } else {
      stack.push(input[i])
    }
  }
  return stack.pop()
}

function fromPostfix(input) {
  stack = []
  for(var i = 0; i < input.length; i++) {
    if(input[i] == ',') {
      var node = new BinaryTreeNode()
      node.left = stack.pop()
      node.right = stack.pop()
      stack.push(node)
    } else {
      stack.push(input[i])
    }
  }
  return stack.pop()
}

function fromNestedHelper(tree) {
  var node = new BinaryTreeNode()
  if(!Array.isArray(tree))
    return tree
  node.right = fromNestedHelper(tree[0])
  node.left = fromNestedHelper(tree[1])
  return node
}

function fromNested(input) {
  var tree = eval(input)
  return fromNestedHelper(tree)
}

function fromASCIIHelper(grid, row, col) {
  if(grid[row][col] !== BRANCH) {
    return grid[row][col]
  }
  var node = new BinaryTreeNode()
  var leftR = row + 1
  var leftC = col + 1
  while(grid[leftR][leftC] == '\\') {
    leftR += 1
    leftC += 1
  }
  console.log(leftR, leftC, grid[leftR][leftC])
  node.left = fromASCIIHelper(grid, leftR, leftC)
  var rightR = row + 1
  var rightC = col - 1
  while(grid[rightR][rightC] == '/') {
    rightR += 1
    rightC -= 1
  }
  node.right = fromASCIIHelper(grid, rightR, rightC)
  return node
}

function fromASCII(input) {
  var grid = input.split("\n")
  console.log(grid)
  var col = grid[0].indexOf("Λ")

  console.log(col)
  return fromASCIIHelper(grid, 0,  col)
}

function toPrefix(tree) {
  if(tree instanceof BinaryTreeNode) {
    //console.log('happening', tree.left, tree.right)
    return '`' + toPrefix(tree.left) + toPrefix(tree.right)
  }
  return tree
}

function toPostfix(tree) {
  if(tree instanceof BinaryTreeNode) {
    return toPrefix(tree.left) + toPrefix(tree.right) + ','
  }
  return tree
}

function toNested(tree) {
  if(tree instanceof BinaryTreeNode)
    return "[" + toNested(tree.left) + ", " + toNested(tree.right) + "]"
  return "'" + tree + "'"
}

function depth(tree) {
  if(tree instanceof BinaryTreeNode)
    return 1 + Math.max(depth(tree.left), depth(tree.right))
  return 0
}



function toASCII(tree) {
  var dep = depth(tree)
  var dim = Math.pow(2, dep+2)
  var grid = []
  for(var i = 0; i < dim - 1; i++)
    grid.push(Array(dim).fill(' '))

  function helper(tree, depth, row, col) {
    if(tree instanceof BinaryTreeNode) {
      grid[row][col] = BRANCH;
      var len = Math.floor(Math.pow(2, depth+1)-1)
      for(var i = 1; i <= len; i++) {
        grid[row+i][col+i] = '\\'
        grid[row+i][col-i] = '/'
      }
      helper(tree.right, depth - 1, row+len+1, col+len+1)
      helper(tree.left, depth - 1, row+len+1, col-(len+1))
    } else {
      grid[row][col] = tree
    }
  }
  helper(tree, dep-1, 0, grid[0].length/2)
  // for(i of grid) {
  //   console.log(i.join(""))
  // }
  return grid.map(function(line) {
    return line.join("")
  }).join("\n")
}

function graphical(tree, canvasID, scale) {
  var cnv = document.getElementById(canvasID)
  var ctx = cnv.getContext("2d")
  ctx.font = scale + 'px serif'
  ctx.textAlign = 'center'
  ctx.textBaseline = 'middle'
  var dep = depth(tree)
  function helper(tree, depth, x, y) {
    if(tree instanceof BinaryTreeNode) {
      var len = Math.floor(scale*Math.pow(2, depth+1)-1)
      ctx.beginPath()
      // console.log(x,y)
      ctx.moveTo(x,y)
      ctx.lineTo(x-len, y+len)
      ctx.moveTo(x+len, y+len)
      ctx.lineTo(x,y)
      ctx.stroke()
      ctx.closePath()
      // console.log(tree)
      helper(tree.right, depth-1, x+len, y+len)
      helper(tree.left, depth-1, x-len, y+len)
    } else {
      ctx.beginPath()
      ctx.arc(x, y, scale, 0, 2 * Math.PI)
      ctx.fillStyle = "white"
      ctx.fill()
      ctx.stroke()
      ctx.closePath()
      ctx.fillStyle = "black"
      ctx.fillText(tree, x, y)
    }
  }
  helper(tree, dep, cnv.width/2, 0)
}

function entry(input, inputType = 'nestedArray', outputType = 'nestedArray', canvasID = "tree", scale = 10) {
  var inputTypes = {
    'prefix': fromPrefix,
    'postfix': fromPostfix,
    'nestedArray': fromNested,
    'ASCIIArt': fromASCII
  }
  var tree = inputTypes[inputType](input)
  var outputTypes = {
    'prefix': toPrefix,
    'postfix': toPostfix,
    'nestedArray': toNested,
    'ASCIIArt': toASCII
  }
  if(outputType == 'graphical') {
    graphical(tree, canvasID, scale)
    return undefined
  }
  return outputTypes[outputType](tree)
}

entry #3

written by LyricLy
submitted at
1 like

guesses
comments 0

post a comment


invert.hs ASCII text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
-- // Code by SoundOfSpouting#6980 (UID: 151149148639330304)

data Tree = Leaf Char | Node Tree Tree

instance Read Tree where
  readsPrec _ ('`':xs) = do
    (x, ys) <- reads xs
    (y, zs) <- reads ys
    return (Node x y, zs)
  readsPrec _ (x:xs) = [(Leaf x, xs)]

instance Show Tree where
  show (Leaf x) = [x]
  show (Node x y) = '`' : show x ++ show y

invert (Node x y) = Node (invert y) (invert x)
invert x = x

entry = show . invert . read

entry #4

written by HelloBoi
submitted at
1 like

guesses
comments 0

post a comment


test.js ASCII text
1
2
3
4
5
6
7
8
9
let a=k=>Array.isArray(k)?[a(k[1]),a(k[0])]:k;
						function entry(o) {
					// XXX security error
					return JSON.stringify(a(eval(o)));}
function japh() {
	console.log("2022-04-27 check DMs");
}

console.log(entry("[['w', 'a'], [['t', 'z'], 't']]"));

entry #5

written by IFcoltransG
submitted at
3 likes

guesses
comments 0

post a comment


reverse.js ASCII text, with very long lines (321)
1
2
3
const entry=input=>input?input.replace(/[`, \[\]"']/g,match=>({',':'`','`':',',' ':'','[':']',']':'[','"':"'","'":'"'}[match])).split("").reverse().join("").replace(/([\]'"])`/g,(_,match)=>`${match},${input.match(/ /)?'':' '}`):" "

for(const test of['',"[['w', 'a'], [['t', 'z'], 't']]","['a', 'a']]","[['w','a'],[['t','z'],'t']]","['i','i']]",'[["w", "a"], [["t", "z"], "t"]]','["v", "v"]]','[["w","a"],[["t","z"],"t"]]','["i","i"]]','``wa``tzt','`ll',`wa,tz,t,,`,`oo,`]){if(test!==entry(entry(test))||test===entry(test)){throw'assertion error '+test}}

entry #6

written by Palaiologos
submitted at
3 likes

guesses
comments 0

post a comment


main ASCII text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
           :%s/\^A/\="\<C-A>"/g|%s/\^X/\="\<C-X>"/g|%s/\^R/\="\<C-R>"/g|%s/\^M/\n/g|06
           0f-ly$@"



_c:        _s1-gg0mh`h/_t^Mnjmt`h/_p^Mnjmp`h/_o^Mnjmo`h/_i^Mnjmi`h/_s2^Mnf-ly$@"njmt_j
           _s2-`h/_a^Mnjma`h/_c^Mnf:mc`h/_f^Mnf_mf`h/_b^Mnf_mb`pyl`c/_\V^R"^Mf-ly2tX@"
            z_>-`twmt`p mpyl`c/_\V^R"^Mf-ly2tX@"Xs_<-`tbmt`p mpyl`c/_\V^R"^Mf-ly2tX@"X
           _f:_0x:-`p% mpyl`c/_\V^R"^Mf-ly2tX@"Xa_nx:-`p mpyl`c/_\V^R"^Mf-ly2tX@"Xmpyl
           _b:_0x:-`p mpyl`c/_\V^R"^Mf-ly2tX@"Xm_nx:-`p% mpyl`c/_\V^R"^Mf-ly2tX@"Xly2t
           _+-`t^A`p mpyl`c/_\V^R"^Mf-ly2tX@"Xo_--`t^X`p mpyl`c/_\V^R"^Mf-ly2tX@"X_/--
           _]-`tyt `b/\(^R"\|n\)x^Mf-ly2tX@"Xd_[-`tyt `f/\(^R"\|n\)x^Mf-ly2tX@"X^$0x:-
           _v.$7yy_.-`tyw`a/_\(^R"\|uuu\)^Mellyl`op$mo`p mpyl`c/_\V^R"^Mf-ly2tX@"Xelly
           _$`p mpy`pyl`a_,-`iy  mi`a/ ^R"_^MT_ye`tvt p`p mpyl`c/_\V^R"^Mf-ly2tX@"X_#- 
_o:


_i:
``wa``tzt^M

_t:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

_a:
___0 .___1 .___2 .___3 .___4 .___5 .___6 .___7 .___8 .___9 .__10 ^M_11 .__12 .__13 .__14 .__15 ._
__16 .__17 .__18 .__19 .__20 .__21 .__22 .__23 .__24 .__25 .__26 .__27 .__28 .__29 .__30 .__31 ._
__32  __33 !__34 "__35 #__36 $__37 %__38 &__39 '__40 (__41 )__42 *__43 +__44 ,__45 -__46 .__47 /_
__48 0__49 1__50 2__51 3__52 4__53 5__54 6__55 7__56 8__57 9__58 :__59 ;__60 <__61 =__62 >__63 ?_
__64 @__65 A__66 B__67 C__68 D__69 E__70 F__71 G__72 H__73 I__74 J__75 K__76 L__77 M__78 N__79 O_
__80 P__81 Q__82 R__83 S__84 T__85 U__86 V__87 W__88 X__89 Y__90 Z__91 [__92 \__93 ]__94 ^__95 __
__96 `__97 a__98 b__99 c_100 d_101 e_102 f_103 g_104 h_105 i_106 j_107 k_108 l_109 m_110 n_111 o_
_112 p_113 q_114 r_115 s_116 t_117 u_118 v_119 w_120 x_121 y_122 z_123 {_124 |_125 }_126 ~_127 ._
_uuu .

_p:
>>----------[++++++++++>,----------]<[[>+>+<<-]>[-<+>]>>+++++++[>++++++++++++++<-]>--[-<<->>]<+<[
[-]<<.>>>-<]>[+++[>+++++++++++<-]>.[-]<]<<<[-]<]#
main.hint ASCII text
1
2
3
4
5
6
7
8
9
how to use:
- put your tree in place of ``wa``tzt or keep it intact to see a demo
- open `vim` and type `:e main` or run `vim main`
- type gg2yy@"
- wait until the program finishes, it will display an inverted tree

details: takes input in prefix form, outputs in postfix form.
requirements: a decently modern version of vim
acknowledgements: xoreaxeax (Christopher Domas)

entry #7

written by Olive
submitted at
1 like

guesses
comments 0

post a comment


binary_tree.js ASCII text, with CRLF, CR, LF line terminators
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
function fucker ( s)

{

    this . t=[ ];

    this . c=s;

    this . p=0;};


fucker  . prototype . run = function ( i)

{

    var s="";

    while ( 1)

    {

        if ( ! this . c) return s

        var c=this . c . substring( 0);

        this . c=this . c . substring( this . c . length, 1);

        if ( c . charCodeAt( 0)==053)

        {

       this . t[ this . p] ++;

       if ( ! this . t[ this . p])

       {

        this . t[ this . p]=1;};}

        else if ( c . charCodeAt( 0)==054)

        {

       i+=String . fromCharCode( 0);

       this . t[ this . p]=i . charCodeAt( 0);

       i=i . substring( i . length, 1);

       this . i=i;}

        else if ( c . charCodeAt( 0)==055)

        {

       this . t[ this . p] --;}

        else if ( c . charCodeAt( 0)==056)

        {

       //console.log("awa!! " + this . t[ this . p]);

       s+=String . fromCharCode( this . t[ this . p]);}

        else if ( c . charCodeAt( 0)==074)

        {

       this . p --;}

        else if ( c . charCodeAt( 0)==076)

        {

       this . p ++;}

        else if ( c . charCodeAt( 0)==91)

        {

       while ( this . t[ this . p])

       {

        var c = new fucker( );

        Object . assign( c, this);

        let x = c . run( i);

        s+= x;

        this . p = c . p;

        i = c . i;};

       var c = new fucker( );

       Object . assign( c, JSON . parse( JSON . stringify( this)));

       c . run( i);

       this . c = c . c;}

        else

        {

       return s};};};



function entry ( i)

{

    return new fucker( "+->,[>,]<[>+++++++++++[-<---->]+<[>++++++++++[-<++++>]<.[-]]>[+++++[->++++++++++++++++<]>.[-]<]<<]") . run( i);};

entry #8

written by MathR
submitted at
4 likes

guesses
comments 0

post a comment


cg Unicode text, UTF-8 text
1
2
3
4
main = a & eof.
a = b | c.
b = "`" & a → A & a → B & return '`' + B + A.
c = "a"|"b"|"c"|"d"|"e"|"f"|"g"|"h"|"i"|"j"|"k"|"l"|"m"|"n"|"o"|"p"|"q"|"r"|"s"|"t"|"u"|"v"|"w"|"x"|"y"|"z".

entry #9

written by SoundOfSpouting
submitted at
4 likes

guesses
comments 0

post a comment


street.pony ASCII text
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
// Code by SoundOfSpouting#6980 (UID: 151149148639330304)

class Bit is HasEq[Bit]
	let a: Bool val
	new val create(a': Bool) =>
		a = a'
	new val from_unsigned_integer[A: UnsignedInteger[A] val](n: UnsignedInteger[A]) =>
		a = n != A.min_value()
	fun val to_unsigned_integer[A: UnsignedInteger[A] val](): A =>
		let one = A.max_value() / A.max_value()
		let zero = one - one
		if a then one else zero end
	fun eq(bit: Bit box^): Bool =>
		a == bit.a

class Byte is HasEq[Byte]
	let data: (Bit val, Bit val, Bit val, Bit val, Bit val, Bit val, Bit val, Bit val)
	new val create(a: Bit val, b: Bit val, c: Bit val, d: Bit val, e: Bit val, f: Bit val, g: Bit val, h: Bit val) =>
		data = (a, b, c, d, e, f, g, h)
	new val from_unsigned_integer[A: UnsignedInteger[A] val](n: UnsignedInteger[A]) =>
		let one = A.max_value() / A.max_value()
		let two = one + one
		let three = two + one
		let four = two * two
		let five = four + one
		let six = five + one
		let seven = six + one
		data = (
			Bit.from_unsigned_integer[A](n.shr(three).mod(two)),
			Bit.from_unsigned_integer[A](n.shr(one).mod(two)),
			Bit.from_unsigned_integer[A](n.shr(four).mod(two)),
			Bit.from_unsigned_integer[A](n.shr(five).mod(two)),
			Bit.from_unsigned_integer[A](n.shr(two).mod(two)),
			Bit.from_unsigned_integer[A](n.shr(six).mod(two)),
			Bit.from_unsigned_integer[A](n.shr(seven).mod(two)),
			Bit.from_unsigned_integer[A](n.mod(two))
		)
	fun to_unsigned_integer[A: UnsignedInteger[A] val](): A =>
		let one = A.max_value() / A.max_value()
		(let a, let b, let c, let d, let e, let f, let g, let h) = data
		g.to_unsigned_integer[A]().shl(one)
			.add(f.to_unsigned_integer[A]()).shl(one)
			.add(d.to_unsigned_integer[A]()).shl(one)
			.add(c.to_unsigned_integer[A]()).shl(one)
			.add(a.to_unsigned_integer[A]()).shl(one)
			.add(e.to_unsigned_integer[A]()).shl(one)
			.add(b.to_unsigned_integer[A]()).shl(one)
			.add(h.to_unsigned_integer[A]())
	fun eq(byte: Byte box^): Bool =>
		(data._1 == byte.data._1) and
		(data._2 == byte.data._2) and
		(data._3 == byte.data._3) and
		(data._4 == byte.data._4) and
		(data._5 == byte.data._5) and
		(data._6 == byte.data._6) and
		(data._7 == byte.data._7) and
		(data._8 == byte.data._8)

type StackNodeOptional[A] is (StackNode[A] | None)

class Stack[A]
	var _left: StackNodeOptional[A] = None
	var _right: StackNodeOptional[A] = None
	fun ref pushL(value: A) =>
		let prevLeft = _left = StackNode[A](None, _left, consume value)
		match prevLeft | let node: StackNode[A] => node.left = _left end
		if _right is None then _right = _left end
	fun ref pushR(value: A) =>
		let prevRight = _right = StackNode[A](_right, None, consume value)
		match prevRight | let node: StackNode[A] => node.right = _right end
		if _left is None then _left = _right end
	fun ref popL(): A ? =>
		if _right is _left then _right = None end
		let leftNode = _left as StackNode[A]
		_left = leftNode.right
		leftNode.value
	fun ref popR(): A ? =>
		if _left is _right then _left = None end
		let rightNode = _right as StackNode[A]
		_right = rightNode.left
		rightNode.value
	fun peekL(): this->A ? =>
		(_left as this->StackNode[A]).value
	fun peekR(): this->A ? =>
		(_right as this->StackNode[A]).value

class StackNode[A]
	var left: StackNodeOptional[A]
	var right: StackNodeOptional[A]
	let value: A
	new create(left': StackNodeOptional[A], right': StackNodeOptional[A], value': A) =>
		left = left'
		right = right'
		value = consume value'

type TreeNode[A: HasEq[A] val] is (TreeBranchNode[A] | TreeLeafNode[A])

class Tree[A: HasEq[A] val]
	let head: TreeNode[A]
	new iso parsePostfix(delimeter: A, input: Array[A] val) ? =>
		let stack: Stack[TreeNode[A]] ref = Stack[TreeNode[A]]
		for value in input.values() do
			if value == delimeter then
				let right: TreeNode[A] = stack.popR()?
				let left : TreeNode[A] = stack.popR()?
				stack.pushR(TreeBranchNode[A](left, right))
			else stack.pushR(TreeLeafNode[A](value)) end
		end
		head = stack.peekR()?
		head
	fun ref invert() =>
		try (head as TreeBranchNode[A]).invert() end
	fun serializePrefix(delimeter: A): Iterator[A] =>
		head.serializePrefix(delimeter)

class TreeBranchNode[A: HasEq[A] val]
	var left: TreeNode[A]
	var right: TreeNode[A]
	new create(left': TreeNode[A], right': TreeNode[A]) =>
		left = left'
		right = right'
	fun ref invert() =>
		left = right = left
		try (left as TreeBranchNode[A] ref).invert() end
		try (right as TreeBranchNode[A] ref).invert() end
	fun serializePrefix(delimeter: A): Iterator[A] =>
		let stack: Stack[Iterator[A]] ref = Stack[Iterator[A]]
		stack.pushR(SingletonIterator[A](delimeter))
		stack.pushR(left.serializePrefix(delimeter))
		stack.pushR(right.serializePrefix(delimeter))
		ConcatIterators[A](stack)

class TreeLeafNode[A: HasEq[A] val]
	let value: A
	new create(value': A) =>
		value = consume value'
	fun serializePrefix(delimeter: A): Iterator[A] =>
		SingletonIterator[A](value)

primitive IteratorToArray[A: Any val]
	fun apply(a: Iterator[A]): Array[A] =>
		Array[A].>concat(a)

trait Map[A: Any val, B: Any val]
	fun apply(a: A): B

primitive UnsignedIntegerToByte[A: UnsignedInteger[A] val] is Map[A, Byte val]
	fun apply(a: A): Byte val =>
		Byte.from_unsigned_integer[A](a)

primitive ByteToUnsignedInteger[A: UnsignedInteger[A] val] is Map[Byte val, A]
	fun apply(b: Byte val): A =>
		b.to_unsigned_integer[A]()

primitive IdentityMap[A: Any val] is Map[A, A]
	fun apply(a: A): A =>
		a

class MapIterator[A: Any val, B: Any val] is Iterator[B]
	let itr: Iterator[A]
	let map: Map[A, B] val
	new create(itr': Iterator[A], map': Map[A, B] val) =>
		itr = consume itr'
		map = consume map'
	fun ref has_next(): Bool =>
		itr.has_next()
	fun ref next(): B ? =>
		map(itr.next()?)

primitive MapArray[A: Any val, B: Any val]
	fun apply(a: Array[A] val, map: Map[A, B] val): Array[B] =>
		IteratorToArray[B](MapIterator[A, B](a.values(), map))

class ConcatIterators[A] is Iterator[A]
	let stack: Stack[Iterator[A]]
	new create(stack': Stack[Iterator[A]]) =>
		stack = stack'
	fun ref has_next(): Bool =>
		try
			let itr = stack.peekL()?
			if itr.has_next() then true
			else
				stack.popL()?
				has_next()
			end
		else false end
	fun ref next(): A ? =>
		stack.peekL()?.next()?

class SingletonIterator[A] is Iterator[A]
	let value: A
	var unused: Bool = true
	new create(value': A) =>
		value = consume value'
	fun ref has_next(): Bool =>
		unused
	fun ref next(): A =>
		unused = false
		value

class Main
	fun entry(input: String): String =>
		try
			let tree = Tree[Byte val].parsePostfix(Byte.from_unsigned_integer[U8](','), recover val IteratorToArray[Byte val](MapIterator[U8, Byte val](input.values(), UnsignedIntegerToByte[U8])) end)?
			tree.invert()
			String.from_array(recover val IteratorToArray[U8](MapIterator[Byte val, U8]((consume tree).serializePrefix(Byte.from_unsigned_integer[U8]('`')), ByteToUnsignedInteger[U8])) end)
		else input end