Skip to content

Instantly share code, notes, and snippets.

@sudhackar

sudhackar/given.dot

Last active September 8, 2018 12:12
Show Gist options
  • Save sudhackar/42b7c23ac301c59050e93536ef90b937 to your computer and use it in GitHub Desktop.
Save sudhackar/42b7c23ac301c59050e93536ef90b937 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
given.dot
strict digraph "" {
graph [ordering="out"];
null[label=""];
C -> G;
C -> H;
G -> M;
G -> N;
F -> S;
F -> U;
H -> null;
H -> W;
J -> Z;
J -> A;
L -> P;
L -> Y;
O -> J;
O -> K;
P -> O;
P -> E;
S -> L;
T -> F;
T -> V;
W -> X;
W -> I;
Z -> C;
Z -> D;
}
Display the source blob
Display the rendered blob
Raw
given.svg
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Raw
solve.py
debug = False
def the_process(stored, inp, size, fs):
if debug:
print '\t' * fs + \
"the_process({}, {}, {})".format(stored, "".join(inp), size)
idx = 0
global thstr
idx = stored.index(inp[0])
if idx:
the_process(stored[:idx], inp[1:], idx, fs + 1)
if size - 1 != idx:
the_process(stored[1 + idx:1 + idx + size - idx - 1],
inp[idx + 1:], size - idx - 1, fs + 1)
thstr.append(inp[0])
def rev_process(stored, inp, size, fs):
if debug:
print '\t' * fs + \
"rev_process({}, {}, {})".format(stored, "".join(inp), size)
if not size:
return
global thstr
mp = {stored[i]: i for i in xrange(len(stored))}
idx = mp[inp[-1]]
thstr.append(inp[-1])
if size == 1:
return
try:
less_part = max(
loc for loc,
val in enumerate(inp) if mp[val] < idx) + 1
except ValueError:
less_part = 0
rev_process(stored[:idx], inp[:less_part], less_part, fs + 1)
if less_part != size - 1:
rev_process(stored[idx + 1:], inp[less_part:-1],
size - less_part - 1, fs + 1)
if __name__ == "__main__":
thstr = []
stored = "MGNCHXWIZDJAOKPELYSFUTV"
input1 = "TFSLPOJZCGMNHWXIDAKEYUV"
target = "MNGHCWZIJDXOPKLESUVTFYA"
print "sample input : " + input1
the_process(stored, input1, 23, 0)
output1 = "".join(thstr)
print "sample output : " + output1
thstr = []
rev_process(stored, output1, 23, 0)
input1_rev = "".join(thstr)
assert input1 == input1_rev
thstr = []
print "target output : " + target
rev_process(stored, target, 23, 0)
target_rev = "".join(thstr)
print "target input : " + target_rev
thstr = []
the_process(stored, target_rev, 23, 0)
target_out = "".join(thstr)
assert target_out == target
Raw
target.dot
strict digraph "" {
graph [ordering="out"];
A -> X;
X -> C;
C -> G;
G -> M;
G -> N;
C -> H;
X -> D;
D -> I;
I -> W;
I -> Z;
D -> J;
A -> Y;
Y -> E;
E -> K;
E -> L;
K -> O;
K -> P;
Y -> F;
F -> S;
F -> T;
T -> U;
T -> V;
}
Display the source blob
Display the rendered blob
Raw
target.svg
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<!-- Generated by graphviz version 2.40.1 (20161225.0304)
-->
<!-- Pages: 1 -->
<svg width="602pt" height="332pt"
viewBox="0.00 0.00 602.00 332.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 328)">
<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-328 598,-328 598,4 -4,4"/>
<!-- A -->
<g id="node1" class="node">
<title>A</title>
<ellipse fill="none" stroke="#000000" cx="315" cy="-306" rx="27" ry="18"/>
<text text-anchor="middle" x="315" y="-302.3" font-family="Times,serif" font-size="14.00" fill="#000000">A</text>
</g>
<!-- X -->
<g id="node2" class="node">
<title>X</title>
<ellipse fill="none" stroke="#000000" cx="207" cy="-234" rx="27" ry="18"/>
<text text-anchor="middle" x="207" y="-230.3" font-family="Times,serif" font-size="14.00" fill="#000000">X</text>
</g>
<!-- A&#45;&gt;X -->
<g id="edge1" class="edge">
<title>A&#45;&gt;X</title>
<path fill="none" stroke="#000000" d="M295.6918,-293.1278C278.6445,-281.763 253.5981,-265.0654 234.4656,-252.3104"/>
<polygon fill="#000000" stroke="#000000" points="236.4031,-249.3956 226.1411,-246.7607 232.5201,-255.2199 236.4031,-249.3956"/>
</g>
<!-- Y -->
<g id="node13" class="node">
<title>Y</title>
<ellipse fill="none" stroke="#000000" cx="351" cy="-234" rx="27" ry="18"/>
<text text-anchor="middle" x="351" y="-230.3" font-family="Times,serif" font-size="14.00" fill="#000000">Y</text>
</g>
<!-- A&#45;&gt;Y -->
<g id="edge12" class="edge">
<title>A&#45;&gt;Y</title>
<path fill="none" stroke="#000000" d="M323.7146,-288.5708C327.9597,-280.0807 333.1536,-269.6929 337.8663,-260.2674"/>
<polygon fill="#000000" stroke="#000000" points="341.024,-261.7782 342.3657,-251.2687 334.763,-258.6477 341.024,-261.7782"/>
</g>
<!-- C -->
<g id="node3" class="node">
<title>C</title>
<ellipse fill="none" stroke="#000000" cx="99" cy="-162" rx="27" ry="18"/>
<text text-anchor="middle" x="99" y="-158.3" font-family="Times,serif" font-size="14.00" fill="#000000">C</text>
</g>
<!-- X&#45;&gt;C -->
<g id="edge2" class="edge">
<title>X&#45;&gt;C</title>
<path fill="none" stroke="#000000" d="M187.6918,-221.1278C170.6445,-209.763 145.5981,-193.0654 126.4656,-180.3104"/>
<polygon fill="#000000" stroke="#000000" points="128.4031,-177.3956 118.1411,-174.7607 124.5201,-183.2199 128.4031,-177.3956"/>
</g>
<!-- D -->
<g id="node8" class="node">
<title>D</title>
<ellipse fill="none" stroke="#000000" cx="207" cy="-162" rx="27" ry="18"/>
<text text-anchor="middle" x="207" y="-158.3" font-family="Times,serif" font-size="14.00" fill="#000000">D</text>
</g>
<!-- X&#45;&gt;D -->
<g id="edge7" class="edge">
<title>X&#45;&gt;D</title>
<path fill="none" stroke="#000000" d="M207,-215.8314C207,-208.131 207,-198.9743 207,-190.4166"/>
<polygon fill="#000000" stroke="#000000" points="210.5001,-190.4132 207,-180.4133 203.5001,-190.4133 210.5001,-190.4132"/>
</g>
<!-- G -->
<g id="node4" class="node">
<title>G</title>
<ellipse fill="none" stroke="#000000" cx="27" cy="-90" rx="27" ry="18"/>
<text text-anchor="middle" x="27" y="-86.3" font-family="Times,serif" font-size="14.00" fill="#000000">G</text>
</g>
<!-- C&#45;&gt;G -->
<g id="edge3" class="edge">
<title>C&#45;&gt;G</title>
<path fill="none" stroke="#000000" d="M83.7307,-146.7307C73.803,-136.803 60.6847,-123.6847 49.5637,-112.5637"/>
<polygon fill="#000000" stroke="#000000" points="51.7933,-109.8436 42.2473,-105.2473 46.8436,-114.7933 51.7933,-109.8436"/>
</g>
<!-- H -->
<g id="node7" class="node">
<title>H</title>
<ellipse fill="none" stroke="#000000" cx="99" cy="-90" rx="27" ry="18"/>
<text text-anchor="middle" x="99" y="-86.3" font-family="Times,serif" font-size="14.00" fill="#000000">H</text>
</g>
<!-- C&#45;&gt;H -->
<g id="edge6" class="edge">
<title>C&#45;&gt;H</title>
<path fill="none" stroke="#000000" d="M99,-143.8314C99,-136.131 99,-126.9743 99,-118.4166"/>
<polygon fill="#000000" stroke="#000000" points="102.5001,-118.4132 99,-108.4133 95.5001,-118.4133 102.5001,-118.4132"/>
</g>
<!-- M -->
<g id="node5" class="node">
<title>M</title>
<ellipse fill="none" stroke="#000000" cx="27" cy="-18" rx="27" ry="18"/>
<text text-anchor="middle" x="27" y="-14.3" font-family="Times,serif" font-size="14.00" fill="#000000">M</text>
</g>
<!-- G&#45;&gt;M -->
<g id="edge4" class="edge">
<title>G&#45;&gt;M</title>
<path fill="none" stroke="#000000" d="M27,-71.8314C27,-64.131 27,-54.9743 27,-46.4166"/>
<polygon fill="#000000" stroke="#000000" points="30.5001,-46.4132 27,-36.4133 23.5001,-46.4133 30.5001,-46.4132"/>
</g>
<!-- N -->
<g id="node6" class="node">
<title>N</title>
<ellipse fill="none" stroke="#000000" cx="99" cy="-18" rx="27" ry="18"/>
<text text-anchor="middle" x="99" y="-14.3" font-family="Times,serif" font-size="14.00" fill="#000000">N</text>
</g>
<!-- G&#45;&gt;N -->
<g id="edge5" class="edge">
<title>G&#45;&gt;N</title>
<path fill="none" stroke="#000000" d="M42.2693,-74.7307C52.197,-64.803 65.3153,-51.6847 76.4363,-40.5637"/>
<polygon fill="#000000" stroke="#000000" points="79.1564,-42.7933 83.7527,-33.2473 74.2067,-37.8436 79.1564,-42.7933"/>
</g>
<!-- I -->
<g id="node9" class="node">
<title>I</title>
<ellipse fill="none" stroke="#000000" cx="171" cy="-90" rx="27" ry="18"/>
<text text-anchor="middle" x="171" y="-86.3" font-family="Times,serif" font-size="14.00" fill="#000000">I</text>
</g>
<!-- D&#45;&gt;I -->
<g id="edge8" class="edge">
<title>D&#45;&gt;I</title>
<path fill="none" stroke="#000000" d="M198.2854,-144.5708C194.0403,-136.0807 188.8464,-125.6929 184.1337,-116.2674"/>
<polygon fill="#000000" stroke="#000000" points="187.237,-114.6477 179.6343,-107.2687 180.976,-117.7782 187.237,-114.6477"/>
</g>
<!-- J -->
<g id="node12" class="node">
<title>J</title>
<ellipse fill="none" stroke="#000000" cx="243" cy="-90" rx="27" ry="18"/>
<text text-anchor="middle" x="243" y="-86.3" font-family="Times,serif" font-size="14.00" fill="#000000">J</text>
</g>
<!-- D&#45;&gt;J -->
<g id="edge11" class="edge">
<title>D&#45;&gt;J</title>
<path fill="none" stroke="#000000" d="M215.7146,-144.5708C219.9597,-136.0807 225.1536,-125.6929 229.8663,-116.2674"/>
<polygon fill="#000000" stroke="#000000" points="233.024,-117.7782 234.3657,-107.2687 226.763,-114.6477 233.024,-117.7782"/>
</g>
<!-- W -->
<g id="node10" class="node">
<title>W</title>
<ellipse fill="none" stroke="#000000" cx="171" cy="-18" rx="27" ry="18"/>
<text text-anchor="middle" x="171" y="-14.3" font-family="Times,serif" font-size="14.00" fill="#000000">W</text>
</g>
<!-- I&#45;&gt;W -->
<g id="edge9" class="edge">
<title>I&#45;&gt;W</title>
<path fill="none" stroke="#000000" d="M171,-71.8314C171,-64.131 171,-54.9743 171,-46.4166"/>
<polygon fill="#000000" stroke="#000000" points="174.5001,-46.4132 171,-36.4133 167.5001,-46.4133 174.5001,-46.4132"/>
</g>
<!-- Z -->
<g id="node11" class="node">
<title>Z</title>
<ellipse fill="none" stroke="#000000" cx="243" cy="-18" rx="27" ry="18"/>
<text text-anchor="middle" x="243" y="-14.3" font-family="Times,serif" font-size="14.00" fill="#000000">Z</text>
</g>
<!-- I&#45;&gt;Z -->
<g id="edge10" class="edge">
<title>I&#45;&gt;Z</title>
<path fill="none" stroke="#000000" d="M186.2693,-74.7307C196.197,-64.803 209.3153,-51.6847 220.4363,-40.5637"/>
<polygon fill="#000000" stroke="#000000" points="223.1564,-42.7933 227.7527,-33.2473 218.2067,-37.8436 223.1564,-42.7933"/>
</g>
<!-- E -->
<g id="node14" class="node">
<title>E</title>
<ellipse fill="none" stroke="#000000" cx="351" cy="-162" rx="27" ry="18"/>
<text text-anchor="middle" x="351" y="-158.3" font-family="Times,serif" font-size="14.00" fill="#000000">E</text>
</g>
<!-- Y&#45;&gt;E -->
<g id="edge13" class="edge">
<title>Y&#45;&gt;E</title>
<path fill="none" stroke="#000000" d="M351,-215.8314C351,-208.131 351,-198.9743 351,-190.4166"/>
<polygon fill="#000000" stroke="#000000" points="354.5001,-190.4132 351,-180.4133 347.5001,-190.4133 354.5001,-190.4132"/>
</g>
<!-- F -->
<g id="node19" class="node">
<title>F</title>
<ellipse fill="none" stroke="#000000" cx="459" cy="-162" rx="27" ry="18"/>
<text text-anchor="middle" x="459" y="-158.3" font-family="Times,serif" font-size="14.00" fill="#000000">F</text>
</g>
<!-- Y&#45;&gt;F -->
<g id="edge18" class="edge">
<title>Y&#45;&gt;F</title>
<path fill="none" stroke="#000000" d="M370.3082,-221.1278C387.3555,-209.763 412.4019,-193.0654 431.5344,-180.3104"/>
<polygon fill="#000000" stroke="#000000" points="433.4799,-183.2199 439.8589,-174.7607 429.5969,-177.3956 433.4799,-183.2199"/>
</g>
<!-- K -->
<g id="node15" class="node">
<title>K</title>
<ellipse fill="none" stroke="#000000" cx="315" cy="-90" rx="27" ry="18"/>
<text text-anchor="middle" x="315" y="-86.3" font-family="Times,serif" font-size="14.00" fill="#000000">K</text>
</g>
<!-- E&#45;&gt;K -->
<g id="edge14" class="edge">
<title>E&#45;&gt;K</title>
<path fill="none" stroke="#000000" d="M342.2854,-144.5708C338.0403,-136.0807 332.8464,-125.6929 328.1337,-116.2674"/>
<polygon fill="#000000" stroke="#000000" points="331.237,-114.6477 323.6343,-107.2687 324.976,-117.7782 331.237,-114.6477"/>
</g>
<!-- L -->
<g id="node16" class="node">
<title>L</title>
<ellipse fill="none" stroke="#000000" cx="387" cy="-90" rx="27" ry="18"/>
<text text-anchor="middle" x="387" y="-86.3" font-family="Times,serif" font-size="14.00" fill="#000000">L</text>
</g>
<!-- E&#45;&gt;L -->
<g id="edge15" class="edge">
<title>E&#45;&gt;L</title>
<path fill="none" stroke="#000000" d="M359.7146,-144.5708C363.9597,-136.0807 369.1536,-125.6929 373.8663,-116.2674"/>
<polygon fill="#000000" stroke="#000000" points="377.024,-117.7782 378.3657,-107.2687 370.763,-114.6477 377.024,-117.7782"/>
</g>
<!-- O -->
<g id="node17" class="node">
<title>O</title>
<ellipse fill="none" stroke="#000000" cx="315" cy="-18" rx="27" ry="18"/>
<text text-anchor="middle" x="315" y="-14.3" font-family="Times,serif" font-size="14.00" fill="#000000">O</text>
</g>
<!-- K&#45;&gt;O -->
<g id="edge16" class="edge">
<title>K&#45;&gt;O</title>
<path fill="none" stroke="#000000" d="M315,-71.8314C315,-64.131 315,-54.9743 315,-46.4166"/>
<polygon fill="#000000" stroke="#000000" points="318.5001,-46.4132 315,-36.4133 311.5001,-46.4133 318.5001,-46.4132"/>
</g>
<!-- P -->
<g id="node18" class="node">
<title>P</title>
<ellipse fill="none" stroke="#000000" cx="387" cy="-18" rx="27" ry="18"/>
<text text-anchor="middle" x="387" y="-14.3" font-family="Times,serif" font-size="14.00" fill="#000000">P</text>
</g>
<!-- K&#45;&gt;P -->
<g id="edge17" class="edge">
<title>K&#45;&gt;P</title>
<path fill="none" stroke="#000000" d="M330.2693,-74.7307C340.197,-64.803 353.3153,-51.6847 364.4363,-40.5637"/>
<polygon fill="#000000" stroke="#000000" points="367.1564,-42.7933 371.7527,-33.2473 362.2067,-37.8436 367.1564,-42.7933"/>
</g>
<!-- S -->
<g id="node20" class="node">
<title>S</title>
<ellipse fill="none" stroke="#000000" cx="459" cy="-90" rx="27" ry="18"/>
<text text-anchor="middle" x="459" y="-86.3" font-family="Times,serif" font-size="14.00" fill="#000000">S</text>
</g>
<!-- F&#45;&gt;S -->
<g id="edge19" class="edge">
<title>F&#45;&gt;S</title>
<path fill="none" stroke="#000000" d="M459,-143.8314C459,-136.131 459,-126.9743 459,-118.4166"/>
<polygon fill="#000000" stroke="#000000" points="462.5001,-118.4132 459,-108.4133 455.5001,-118.4133 462.5001,-118.4132"/>
</g>
<!-- T -->
<g id="node21" class="node">
<title>T</title>
<ellipse fill="none" stroke="#000000" cx="531" cy="-90" rx="27" ry="18"/>
<text text-anchor="middle" x="531" y="-86.3" font-family="Times,serif" font-size="14.00" fill="#000000">T</text>
</g>
<!-- F&#45;&gt;T -->
<g id="edge20" class="edge">
<title>F&#45;&gt;T</title>
<path fill="none" stroke="#000000" d="M474.2693,-146.7307C484.197,-136.803 497.3153,-123.6847 508.4363,-112.5637"/>
<polygon fill="#000000" stroke="#000000" points="511.1564,-114.7933 515.7527,-105.2473 506.2067,-109.8436 511.1564,-114.7933"/>
</g>
<!-- U -->
<g id="node22" class="node">
<title>U</title>
<ellipse fill="none" stroke="#000000" cx="495" cy="-18" rx="27" ry="18"/>
<text text-anchor="middle" x="495" y="-14.3" font-family="Times,serif" font-size="14.00" fill="#000000">U</text>
</g>
<!-- T&#45;&gt;U -->
<g id="edge21" class="edge">
<title>T&#45;&gt;U</title>
<path fill="none" stroke="#000000" d="M522.2854,-72.5708C518.0403,-64.0807 512.8464,-53.6929 508.1337,-44.2674"/>
<polygon fill="#000000" stroke="#000000" points="511.237,-42.6477 503.6343,-35.2687 504.976,-45.7782 511.237,-42.6477"/>
</g>
<!-- V -->
<g id="node23" class="node">
<title>V</title>
<ellipse fill="none" stroke="#000000" cx="567" cy="-18" rx="27" ry="18"/>
<text text-anchor="middle" x="567" y="-14.3" font-family="Times,serif" font-size="14.00" fill="#000000">V</text>
</g>
<!-- T&#45;&gt;V -->
<g id="edge22" class="edge">
<title>T&#45;&gt;V</title>
<path fill="none" stroke="#000000" d="M539.7146,-72.5708C543.9597,-64.0807 549.1536,-53.6929 553.8663,-44.2674"/>
<polygon fill="#000000" stroke="#000000" points="557.024,-45.7782 558.3657,-35.2687 550.763,-42.6477 557.024,-45.7782"/>
</g>
</g>
</svg>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment