The navigation bar for a winning entry now has a "_Original C_" link
(between the ✅ and the Inventory on the right hand side) so that one
may easily view the original C code that was submitted for IOCCC judging.
Ran `make www timestamp` to perform the above.
764 lines
30 KiB
HTML
764 lines
30 KiB
HTML
<!DOCTYPE html>
|
||
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
|
||
<!-- START: two lines up starts content from: inc/top.default.html -->
|
||
|
||
<!-- END: this line ends content from: inc/top.default.html -->
|
||
<!-- START: this line starts content from: inc/head.default.html -->
|
||
|
||
<head>
|
||
<link rel="stylesheet" href="../../ioccc.css">
|
||
<link href="https://fonts.googleapis.com/css2?family=Outfit:wght@100..900&display=swap" rel="stylesheet">
|
||
<meta charset="utf-8">
|
||
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes">
|
||
<title>2018/vokes - Most connected</title>
|
||
<link rel="icon" type="image/x-icon" href="../../favicon.ico">
|
||
<meta name="description" content="2018 IOCCC entry vokes - Most connected">
|
||
<meta name="keywords" content="IOCCC, 2018, IOCCC 2018, IOCCC entry, vokes, Most connected">
|
||
</head>
|
||
|
||
<!-- !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! -->
|
||
<!-- !!! DO NOT MODIFY THIS FILE - This file is generated by a tool !!! -->
|
||
<!-- !!! DO NOT MODIFY THIS FILE - This file is generated by a tool !!! -->
|
||
<!-- !!! DO NOT MODIFY THIS FILE - This file is generated by a tool !!! -->
|
||
<!-- !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! -->
|
||
|
||
<!-- END: this line ends content from: inc/head.default.html -->
|
||
|
||
<!-- -->
|
||
<!-- This web page was formed via the tool: bin/readme2index.sh -->
|
||
<!-- The content of main section of this web page came from: 2018/vokes/README.md -->
|
||
<!-- -->
|
||
|
||
<!-- !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! -->
|
||
<!-- !!! Do not modify this web page, instead modify the file: 2018/vokes/README.md !!! -->
|
||
<!-- !!! Do not modify this web page, instead modify the file: 2018/vokes/README.md !!! -->
|
||
<!-- !!! Do not modify this web page, instead modify the file: 2018/vokes/README.md !!! -->
|
||
<!-- !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! -->
|
||
|
||
<!-- Markdown content was converted into HTML via the tool: bin/md2html.sh -->
|
||
|
||
<!-- START: this line starts content from: inc/body.default.html -->
|
||
|
||
<body>
|
||
|
||
<!-- END: this line ends content from: inc/body.default.html -->
|
||
<!-- START: this line starts content from: inc/topbar.default.html -->
|
||
|
||
<div class="theader">
|
||
<nav class="topbar">
|
||
<div class="container">
|
||
<div class="logo">
|
||
<a href="../../index.html" class="logo-link">
|
||
IOCCC
|
||
</a>
|
||
</div>
|
||
|
||
<div class="topbar-items">
|
||
<div class="item">
|
||
<span class="item-header">
|
||
Entries
|
||
</span>
|
||
|
||
<div class="sub-item">
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../years.html" class="sub-item-link">
|
||
Winning entries
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../authors.html" class="sub-item-link">
|
||
Winning authors
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../location.html" class="sub-item-link">
|
||
Location of authors
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../bugs.html" class="sub-item-link">
|
||
Bugs and (mis)features
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../faq.html#fix_an_entry" class="sub-item-link">
|
||
Fixing entries
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../faq.html#fix_author" class="sub-item-link">
|
||
Updating author info
|
||
</a>
|
||
</div>
|
||
|
||
</div>
|
||
</div>
|
||
|
||
<div class="item">
|
||
<span class="item-header">
|
||
Status
|
||
</span>
|
||
|
||
<div class="sub-item">
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../news.html" class="sub-item-link">
|
||
News
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../status.html" class="sub-item-link">
|
||
Contest status
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../next/rules.html" class="sub-item-link">
|
||
IOCCC rules
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../next/guidelines.html" class="sub-item-link">
|
||
IOCCC guidelines
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../markdown.html" class="sub-item-link">
|
||
Markdown guidelines
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../SECURITY.html" class="sub-item-link">
|
||
Security policy
|
||
</a>
|
||
</div>
|
||
|
||
</div>
|
||
</div>
|
||
|
||
<div class="item">
|
||
<span class="item-header">
|
||
FAQ
|
||
</span>
|
||
|
||
<div class="sub-item">
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../faq.html" class="sub-item-link">
|
||
Frequently asked questions
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../quick-start.html#enter" class="sub-item-link">
|
||
Enter the IOCCC
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../faq.html#compiling" class="sub-item-link">
|
||
Compiling entries
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../faq.html#running_entries" class="sub-item-link">
|
||
Running entries
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../faq.html#help" class="sub-item-link">
|
||
How to help
|
||
</a>
|
||
</div>
|
||
|
||
</div>
|
||
</div>
|
||
|
||
<div class="item">
|
||
<span class="item-header">
|
||
About
|
||
</span>
|
||
|
||
<div class="sub-item">
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../index.html" class="sub-item-link">
|
||
Home page
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../social.html" class="sub-item-link">
|
||
IOCCC social media
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../about.html" class="sub-item-link">
|
||
About the IOCCC
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../judges.html" class="sub-item-link">
|
||
The judges
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../thanks-for-help.html" class="sub-item-link">
|
||
Thanks for the help
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../contact.html" class="sub-item-link">
|
||
Contact us
|
||
</a>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
</nav>
|
||
|
||
<div class="header-mobile-menu">
|
||
<noscript>
|
||
<a href="../../nojs-menu.html" class="topbar-js-label">
|
||
Please Enable JavaScript
|
||
</a>
|
||
</noscript>
|
||
|
||
<button id="header-open-menu-button" class="topbar-mobile-menu">
|
||
<img
|
||
src="../../png/hamburger-icon-open.png"
|
||
alt="hamburger style menu icon - open state"
|
||
width=48
|
||
height=48>
|
||
</button>
|
||
|
||
<button id="header-close-menu-button" class="hide-content">
|
||
<img
|
||
src="../../png/hamburger-icon-closed.png"
|
||
alt="hamburger style menu icon - closed state"
|
||
width=48
|
||
height=48>
|
||
</button>
|
||
|
||
<div id="mobile-menu-panel" class="hide-content">
|
||
<div class="mobile-menu-container">
|
||
|
||
<div class="mobile-menu-wrapper">
|
||
<div class="mobile-menu-item">
|
||
Entries
|
||
</div>
|
||
<div class="mobile-submenu-wrapper">
|
||
|
||
<a class="mobile-submenu-item" href="../../years.html">
|
||
Winning entries
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../authors.html">
|
||
Winning authors
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../location.html">
|
||
Location of authors
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../bugs.html">
|
||
Bugs and (mis)features
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../faq.html#fix_an_entry">
|
||
Fixing entries
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../faq.html#fix_author">
|
||
Updating author info
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../thanks-for-help.html">
|
||
Thanks for the help
|
||
</a>
|
||
|
||
</div>
|
||
</div>
|
||
|
||
<div class="mobile-menu-wrapper">
|
||
|
||
<div class="mobile-menu-item">
|
||
Status
|
||
</div>
|
||
<div class="mobile-submenu-wrapper">
|
||
|
||
<a class="mobile-submenu-item" href="../../news.html">
|
||
News
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../status.html">
|
||
Contest status
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../next/rules.html">
|
||
IOCCC rules
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../next/guidelines.html">
|
||
IOCCC guidelines
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../markdown.html">
|
||
Markdown guidelines
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../SECURITY.html">
|
||
Security policy
|
||
</a>
|
||
|
||
</div>
|
||
</div>
|
||
|
||
<div class="mobile-menu-wrapper">
|
||
<div class="mobile-menu-item">
|
||
FAQ
|
||
</div>
|
||
<div class="mobile-submenu-wrapper">
|
||
|
||
<a class="mobile-submenu-item" href="../../faq.html">
|
||
Frequently asked questions
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../quick-start.html#enter">
|
||
Enter the IOCCC
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../faq.html#compiling">
|
||
Compiling entries
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../faq.html#running_entries">
|
||
Running entries
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../faq.html#help">
|
||
How to help
|
||
</a>
|
||
|
||
</div>
|
||
</div>
|
||
|
||
<div class="mobile-menu-wrapper">
|
||
<div class="mobile-menu-item">
|
||
About
|
||
</div>
|
||
<div class="mobile-submenu-wrapper">
|
||
|
||
<a class="mobile-submenu-item" href="../../index.html">
|
||
Home page
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../social.html">
|
||
IOCCC social media
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../about.html">
|
||
About the IOCCC
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../judges.html">
|
||
The judges
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../contact.html">
|
||
Contact us
|
||
</a>
|
||
|
||
</div>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<script>
|
||
var headerOpenMenuButton = document.getElementById("header-open-menu-button");
|
||
var headerCloseMenuButton = document.getElementById("header-close-menu-button");
|
||
var mobileMenuPanel = document.getElementById("mobile-menu-panel");
|
||
|
||
headerOpenMenuButton.addEventListener("click", () => {
|
||
headerOpenMenuButton.classList.remove("topbar-mobile-menu");
|
||
headerOpenMenuButton.classList.add("hide-content");
|
||
|
||
headerCloseMenuButton.classList.remove("hide-content");
|
||
headerCloseMenuButton.classList.add("topbar-mobile-menu");
|
||
|
||
mobileMenuPanel.classList.remove("hide-content");
|
||
mobileMenuPanel.classList.add("topbar-mobile-panel");
|
||
});
|
||
|
||
headerCloseMenuButton.addEventListener("click", () => {
|
||
headerCloseMenuButton.classList.remove("topbar-mobile-menu");
|
||
headerCloseMenuButton.classList.add("hide-content");
|
||
|
||
mobileMenuPanel.classList.add("hide-content");
|
||
mobileMenuPanel.classList.remove("topbar-mobile-panel");
|
||
|
||
headerOpenMenuButton.classList.add("topbar-mobile-menu");
|
||
headerOpenMenuButton.classList.remove("hide-content");
|
||
});
|
||
</script>
|
||
|
||
<!-- END: this line ends content from: inc/topbar.default.html -->
|
||
<!-- START: this line starts content from: inc/header.default.html -->
|
||
|
||
<div class="header">
|
||
<a href="../../2011/zucker/index.html">
|
||
<img src="../../png/ioccc.png"
|
||
alt="IOCCC image by Matt Zucker"
|
||
width=300
|
||
height=110>
|
||
</a>
|
||
<h1>The International Obfuscated C Code Contest</h1>
|
||
<h2>2018/vokes - Most connected</h2>
|
||
<h3>Computing strongly connected graph components</h3>
|
||
</div>
|
||
|
||
<!-- END: this line ends content from: inc/header.default.html -->
|
||
<!-- START: this line starts content from: inc/navbar.mid.html -->
|
||
|
||
<div class="navbar">
|
||
<a class="Left" href="../poikola/index.html">← 2018/poikola</a>
|
||
<a class="Left" href="../index.html">↑ 2018 ↑</a>
|
||
<a class="Left" href="../yang/index.html">2018/yang →</a>
|
||
<a class="Right" href="https://github.com/ioccc-src/winner/blob/master/2018/vokes/prog.c">C code</a>
|
||
<a class="Right" href="https://github.com/ioccc-src/winner/blob/master/2018/vokes/Makefile">Makefile</a>
|
||
<a class="Right" href="#inventory">Inventory</a>
|
||
<a class="Right" href="https://github.com/ioccc-src/winner/blob/master/2018/vokes/prog.orig.c">Original C</a>
|
||
<a class="Right" href="https://validator.w3.org/nu/?doc=https%3A%2F%2Fwww.ioccc.org%2F2018%2Fvokes%2Findex.html">✓</a>
|
||
</div>
|
||
|
||
<!-- END: this line ends content from: inc/navbar.mid.html -->
|
||
<!-- START: this line starts content from: inc/before-content.default.html -->
|
||
|
||
<div class="content" id="content">
|
||
|
||
<!-- END: this line ends content from: inc/before-content.default.html -->
|
||
<!-- START: this line starts content for HTML phase 20 by: bin/output-index-author.sh via bin/md2html.sh -->
|
||
|
||
<!-- START: this line starts content generated by: bin/output-index-author.sh -->
|
||
|
||
<h2 id="author">Author:</h2>
|
||
<ul>
|
||
<li>Name: <a href="../../authors.html#Scott_Vokes">Scott Vokes</a><br>
|
||
Location: <a href="../../location.html#US">US</a> - <em>United States of America</em> (<em>United States</em>)</li>
|
||
</ul>
|
||
|
||
<!-- END: next line ends content generated by: bin/output-index-author.sh -->
|
||
|
||
<!-- END: this line ends content for HTML phase 20 by: bin/output-index-author.sh via bin/md2html.sh -->
|
||
<!-- START: this line starts content for HTML phase 21 by: bin/pandoc-wrapper.sh via bin/md2html.sh -->
|
||
|
||
<!-- BEFORE: 1st line of markdown file: 2018/vokes/README.md -->
|
||
<h2 id="to-build">To build:</h2>
|
||
<pre><code> make</code></pre>
|
||
<h3 id="bugs-and-misfeatures">Bugs and (Mis)features:</h3>
|
||
<p>The current status of this entry is:</p>
|
||
<blockquote>
|
||
<p><strong>STATUS: INABIAF - please DO NOT fix</strong></p>
|
||
</blockquote>
|
||
<p>For more detailed information see <a href="../../bugs.html#2018_vokes">2018/vokes in bugs.html</a>.</p>
|
||
<h2 id="to-use">To use:</h2>
|
||
<pre><code> ./prog < file.txt</code></pre>
|
||
<h2 id="try">Try:</h2>
|
||
<pre><code> ./try.sh</code></pre>
|
||
<h2 id="judges-remarks">Judges’ remarks:</h2>
|
||
<p>What this program does is not witchcraft and there are no spectres, but you
|
||
might have a meltdown trying to work it all out (look at the source code to
|
||
understand this better).</p>
|
||
<p>This entry is designed to mislead in many ways. However, if you find yourself
|
||
wanting to know the possibilities for navigating a graph, you will get the
|
||
answer you seek with no hocus pocus.</p>
|
||
<h2 id="authors-remarks">Author’s remarks:</h2>
|
||
<h3 id="introduction">Introduction:</h3>
|
||
<p>This program reads a directed graph (as lines with integer node IDs),
|
||
and prints the graph’s nodes in reverse-topologically sorted order,
|
||
grouped into strongly connected components. Given a set of nodes
|
||
representing targets and edges representing dependencies between them,
|
||
it produces a build order with any dependency cycles gathered.</p>
|
||
<p>For example, the following input, provided as <a href="example-1.txt">example-1.txt</a>:</p>
|
||
<pre><code> 0 4 8
|
||
1 0
|
||
2 1 3
|
||
3 2
|
||
4 1
|
||
5 4 6
|
||
6 5 2
|
||
7 3 6 7</code></pre>
|
||
<p>would be interpreted as:</p>
|
||
<pre><code> 0 -> 4, 8
|
||
1 -> 0
|
||
2 -> 1, 3
|
||
3 -> 2
|
||
4 -> 1
|
||
5 -> 4, 6
|
||
6 -> 5, 2
|
||
7 -> 3, 6, 7</code></pre>
|
||
<p>So, node 0 has edges to / depends on nodes 4 and 8, node 1 depends on
|
||
node 0, and so on. Then, it groups the graph’s nodes into
|
||
strongly connected components and prints them in reverse-topologically
|
||
sorted order:</p>
|
||
<pre><code> 0: 8
|
||
1: 0 1 4
|
||
2: 2 3
|
||
3: 5 6
|
||
4: 7</code></pre>
|
||
<p>It uses <a href="https://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm">Tarjan’s strongly connected components
|
||
algorithm</a>
|
||
for the grouping and reverse-topological sorting, along with a bonus hidden
|
||
implementation of counting sort, which sorts each group.</p>
|
||
<p>For other details about the input format, see <a href="#issues-and-limitations">Issues and
|
||
Limitations</a>.</p>
|
||
<h3 id="building">Building:</h3>
|
||
<p>To build:</p>
|
||
<pre><code> ${CC} -o prog prog.c -std=c11 -O3 -Wall -Wextra -pedantic -Wno-missing-prototypes</code></pre>
|
||
<p><code>-Wno-missing-prototypes</code> is necessary because there aren’t any
|
||
prototypes. (They would put the program well over the size limit.)</p>
|
||
<p>Note: The program can also be built with <code>-std=c99</code> or <code>-std=c89</code>.</p>
|
||
<p>If building with <code>-Weverything</code>, then <code>-Wno-strict-prototypes</code>
|
||
may also be necessary – the function pointer declarations for
|
||
<code>_</code> and <code>B</code> may get warnings otherwise, for reasons described
|
||
next in <a href="#obfuscations">Obfuscations</a>.</p>
|
||
<h3 id="obfuscations">Obfuscations:</h3>
|
||
<ul>
|
||
<li><p>This entry uses functions that have a variable number of arguments,
|
||
but despite what the rules say, there is no need to be careful about
|
||
<code>va_list</code> implementation differences. :) . There are several
|
||
references to a function pointer, <code>_</code>, but it’s called with different
|
||
numbers of arguments in different places. (In particular, look at
|
||
<code>spell</code>.) Because the function pointer declaration has an empty list
|
||
of parameters, the argument count and types are unconstrained. <code>_</code> is
|
||
set to different functions in several places, but it is always called
|
||
with appropriate argument(s) for its possible current functions. This
|
||
is allowed by the standard – The section on
|
||
<code>F</code>,<code>I</code>,<code>N</code>,<code>D</code>,<code>M</code>,<code>Y</code>,<code>C</code>,<code>L</code>,<code>U</code>,<code>E</code> has further details.</p></li>
|
||
<li><p>It uses <code>_</code> in three different scopes: as a <code>goto</code> label (function
|
||
scope), as an <code>enum</code> name, and a <code>_</code> function pointer (which is required
|
||
to have file scope, since it starts with <code>_</code>). There are also other
|
||
<code>_</code>s: it appears in a string, obscured by a hexadecimal escape sequence
|
||
(<code>\x5f</code>), and the cauldron is supported by a giant underscore.
|
||
(Does this program qualify for Best One Liner?)</p></li>
|
||
<li><p>Most of the variables are not only global, but used for unrelated
|
||
purposes at different times, so just renaming them while studying the
|
||
program should make it even more confusing. The few variables local to
|
||
functions have their names reused for different things in other
|
||
functions.</p></li>
|
||
<li><p>There is an enum early on that defines several single-letter identifiers:
|
||
<code>F</code>,<code>I</code>,<code>N</code>,<code>D</code>,<code>M</code>,<code>Y</code>,<code>C</code>,<code>L</code>,<code>U</code>,<code>E</code>. These are used for array offsets,
|
||
both individually and in combination. The first several values are also a
|
||
clue: ISO/IEC 9899:1999 chapter 6.7.5.3 verse 14 describes how function
|
||
declarators with an empty parameter list behave. (As does 3.5.4.3 for ANSI C,
|
||
which explains the <code>0x3543</code> that appears soon after.)</p></li>
|
||
<li><p>Several parts of the program’s state are stashed in otherwise unused
|
||
offsets of the node arrays. These locations are accessed in multiple
|
||
ways, such as using <code>I[p]</code> (where <code>I == 7</code>) as well as <code>p[F+L]</code> (6+1),
|
||
or <code>b[M-N]</code> (14-5) and <code>U[b]</code> (where <code>U == 9</code>).</p></li>
|
||
<li><p>The other identifiers are misleading, punny, or both. <code>spectre</code> does
|
||
not exploit CVE-2017-5753 or CVE-2017-5715, for example – it just fits
|
||
the witch theme. <code>cast</code> doesn’t cast, <code>hex</code> has nothing to do with
|
||
hexadecimal, <code>bubble</code> is not bubble sort, there is no undefined
|
||
behavior in <code>nasal_demons</code>, and <code>main()</code> has absolutely nothing to do
|
||
with a hand.</p></li>
|
||
<li><p>For well-formed input, how the program determines when to exit is a
|
||
bit obscure. <code>main()</code> ends with a <code>goto</code> leading back to an earlier <code>_</code>
|
||
label, so it just loops forever, and <code>exit</code> only appears in code paths
|
||
related to error-handling. It looks like <code>cast</code> calls <code>meltdown</code> with
|
||
its second argument set to 0, which would call <code>exit</code>, but running in
|
||
<code>gdb(1)</code> with a breakpoint on <code>cast</code> reveals that it isn’t being called…</p></li>
|
||
<li><p>Instead of using <code>isdigit(3)</code>, the program checks the numeric value of
|
||
each <code>char</code>, and literals that would suggest comparing against e.g. <code>'0'</code>
|
||
are specified in octal in one place, and produced by arithmetic using
|
||
the <code>enum</code> elsewhere.</p></li>
|
||
<li><p>Common conventions are subverted: <code>i</code> is not a loop index, <code>argv</code> and
|
||
<code>argc</code>’s names are swapped.</p></li>
|
||
<li><p><code>NULL</code> does not appear in the program. Instead, <code>argc[argv]</code> (which is
|
||
required to be a NULL pointer) is saved and passed to where its value
|
||
is needed.</p></li>
|
||
<li><p>Oh, and the program is squashed into the shape of a bubbling cauldron,
|
||
on top of a giant underscore, so there’s that.</p></li>
|
||
</ul>
|
||
<h3 id="issues-and-limitations">Issues and Limitations:</h3>
|
||
<ul>
|
||
<li><p>Despite appearances, it does not handle numbers in hex, or provide
|
||
a <code>curses(3)</code>-based interface.</p></li>
|
||
<li><p>The expected input format is zero or more lines of space-separated
|
||
integers. If other characters appear in the input, it will either
|
||
reject the input entirely and exit with a non-zero status, or skip
|
||
number(s) adjacent to the non-digit characters, depending on where the
|
||
characters appear. Tabs and multiple consecutive spaces are handled
|
||
correctly, however.</p></li>
|
||
<li><p>Individual lines of input longer than <code>0x3543 - 1</code> bytes will be
|
||
split and processed as if they were multiple lines of input, which can
|
||
produce incorrect results. This magic number’s significance is
|
||
described earlier.</p></li>
|
||
<li><p>The algorithm expects its input to represent a fully connected graph.
|
||
While the output is otherwise topologically sorted, if there are nodes
|
||
completely unconnected to the rest of the graph (with or without
|
||
self-cycles), they will be output as soon as they are processed –
|
||
this means that, when there are disconnected nodes, reordering the
|
||
input lines can produce different output. Addressing this by adding
|
||
another pass is would put the program over the size limit.</p></li>
|
||
<li><p>While the node IDs don’t need to be consecutive or start at 0, the
|
||
implementation doesn’t have special handling for sparse graphs. If you
|
||
give it a graph with nodes numbered 0 and 2147483647, it will attempt
|
||
to allocate sufficient memory (potentially around 32 GB) for the
|
||
entire range of graph nodes, even if those are the only ones. If
|
||
memory allocation returns NULL, it will gracefully exit, otherwise it
|
||
will succeed, eventually, perhaps after a great deal of swapping.</p></li>
|
||
<li><p>Node IDs >= 2147483648 will cause the program to print an error
|
||
message and exit with a non-zero status. This shrinks the code that
|
||
detects overflowing the array size by a bit.</p></li>
|
||
<li><p>A very large group of nodes in a cycle can cause a stack overflow.
|
||
This typically takes over 100,000 nodes, and depends on the order the
|
||
nodes are visited. Addressing this would put the program over the size
|
||
limit.</p></li>
|
||
<li><p>The implementation depends on the characters <code>'0'</code>, <code>'1'</code>, … <code>'9'</code> having
|
||
the values <code>48</code> through <code>57</code>, rather than using <code>isdigit(3)</code>. As noted above,
|
||
this program has nothing to do with a hand.</p></li>
|
||
</ul>
|
||
<!--
|
||
|
||
Copyright © 1984-2024 by Landon Curt Noll. All Rights Reserved.
|
||
|
||
You are free to share and adapt this file under the terms of this license:
|
||
|
||
Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0)
|
||
|
||
For more information, see:
|
||
|
||
https://creativecommons.org/licenses/by-sa/4.0/
|
||
|
||
-->
|
||
<!-- AFTER: last line of markdown file: 2018/vokes/README.md -->
|
||
|
||
<!-- END: this line ends content for HTML phase 21 by: bin/pandoc-wrapper.sh via bin/md2html.sh -->
|
||
<!-- START: this line starts content for HTML phase 22 by: bin/output-index-inventory.sh via bin/md2html.sh -->
|
||
|
||
<!-- START: this line starts content generated by: bin/output-index-inventory.sh -->
|
||
|
||
<div id="inventory">
|
||
<h1 id="inventory-for-2018vokes">Inventory for 2018/vokes</h1>
|
||
</div>
|
||
<h2 id="primary-files">Primary files</h2>
|
||
<ul>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2018/vokes/prog.c">prog.c</a> - entry source code</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2018/vokes/Makefile">Makefile</a> - entry Makefile</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2018/vokes/prog.orig.c">prog.orig.c</a> - original source code</li>
|
||
<li><a href="example-1.txt">example-1.txt</a> - sample input</li>
|
||
<li><a href="example-2.txt">example-2.txt</a> - sample input</li>
|
||
<li><a href="example-tab.txt">example-tab.txt</a> - sample input</li>
|
||
<li><a href="ioccc.txt">ioccc.txt</a> - sample input</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2018/vokes/try.sh">try.sh</a> - script to try entry</li>
|
||
</ul>
|
||
<h2 id="secondary-files">Secondary files</h2>
|
||
<ul>
|
||
<li><a href="2018_vokes.tar.bz2">2018_vokes.tar.bz2</a> - download entry tarball</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2018/vokes/README.md">README.md</a> - markdown source for this web page</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2018/vokes/.entry.json">.entry.json</a> - entry summary and manifest in JSON</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2018/vokes/.gitignore">.gitignore</a> - list of files that should not be committed under git</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2018/vokes/.path">.path</a> - directory path from top level directory</li>
|
||
<li><a href="index.html">index.html</a> - this web page</li>
|
||
</ul>
|
||
<hr style="width:10%;text-align:left;margin-left:0">
|
||
<h4>
|
||
Jump to: <a href="#">top</a>
|
||
</h4>
|
||
|
||
<!-- END: next line ends content generated by: bin/output-index-inventory.sh -->
|
||
|
||
<!-- END: this line ends content for HTML phase 22 by: bin/output-index-inventory.sh via bin/md2html.sh -->
|
||
<!-- START: this line starts content from: inc/after-content.default.html -->
|
||
|
||
</div>
|
||
|
||
<!-- END: this line ends content from: inc/after-content.default.html -->
|
||
<!-- START: this line starts content from: inc/footer.inventory.html -->
|
||
|
||
<!--
|
||
|
||
Copyright © 1984-2025 by Landon Curt Noll. All Rights Reserved.
|
||
|
||
You are free to share and adapt this file under the terms of this license:
|
||
|
||
Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0)
|
||
|
||
For more information, see:
|
||
|
||
https://creativecommons.org/licenses/by-sa/4.0/
|
||
|
||
-->
|
||
|
||
<div class="footer">
|
||
|
||
<div id="copyright"><h3>Copyright © 1984-2025 by Landon Curt Noll:
|
||
<a href="https://creativecommons.org/faq/#what-does-some-rights-reserved-mean"
|
||
target="_blank"
|
||
rel="license noopener noreferrer">Some Rights Reserved</a></h3>
|
||
<p>
|
||
This work is <b>licensed by Landon Curt Noll</b> under
|
||
<b><a href="https://creativecommons.org/licenses/by-sa/4.0/?ref=chooser-v1"
|
||
target="_blank"
|
||
rel="license noopener noreferrer"
|
||
style="display:inline-block;">CC BY-SA 4.0</a></b>.
|
||
<img style="height:22px!important;margin-left:3px;vertical-align:text-bottom;"
|
||
src="../../png/cc.png"
|
||
alt="cc inside circle symbol">
|
||
<img style="height:22px!important;margin-left:3px;vertical-align:text-bottom;"
|
||
src="../../png/by.png"
|
||
alt="person inside circle symbol">
|
||
<img style="height:22px!important;margin-left:3px;vertical-align:text-bottom;"
|
||
src="../../png/sa.png"
|
||
alt="arrow looping back on itself inside circle symbol"><br>
|
||
You should <b>carefully review</b> the
|
||
<b><a href="https://creativecommons.org/licenses/by-sa/4.0/legalcode.en"
|
||
target="_blank"
|
||
rel="license noopener noreferrer">CC BY-SA 4.0 LEGAL CODE</a></b>
|
||
before using the licensed material.<br>
|
||
You may wish to review the
|
||
<b><a href="../../license.html"
|
||
target="_blank"
|
||
rel="license noopener noreferrer">highlights of some of the key features and terms</a></b>
|
||
of <b>CC BY-SA 4.0</b>.<br>
|
||
</p>
|
||
</div>
|
||
|
||
<div id="coda"><h3>Coda</h3>
|
||
<p>
|
||
<a href="https://validator.w3.org/nu/?doc=https%3A%2F%2Fwww.ioccc.org%2F2018%2Fvokes%2Findex.html" rel="nofollow">Nu HTML check this web page</a><br>
|
||
<a href="#top">Jump to top</a> <a href="#content">Jump to Content</a> <a href="#inventory">Jump to Inventory</a><br>
|
||
</p>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<!-- END: this line ends content from: inc/footer.inventory.html -->
|
||
<!-- START: this line starts content from: inc/bottom.default.html -->
|
||
|
||
</body>
|
||
</html>
|
||
|
||
<!-- END: this line ends content from: inc/bottom.default.html -->
|