title: Why isn't it ending?

text:
# Question
Title: Why isn't it ending?
Your task: To write a program that should obviously terminate, but it never (to the extent of a computer crash) does. Make it look like it should perform a simple task: adding numbers, printing something,... But it just gets caught in an infinite loop.

Try to make your program very clear and simple, while it actually will get stuck in an unforeseen loop. Voters: judge the answers on how "underhanded" they are!

This is a popularity contest: Be creative!

# Answer
## Javascript

```
var x=prompt('Enter a value under 100');
while (x != 100) {
  x=x+1;
}
console.log('End!');

```

> prompt() returns a string and the loop appends the character '1', it will never be equal to 100.
> 182 votes

# Answer
## C

Just a basic example program that illustrates the three different kinds of while-loops in C.

```
int main() {

    int x = 0;

    // Multi-statement while loops are of the form "while (condition) do { ... }" and
    // are used to execute multiple statements per loop; this is the most common form
    while (x < 10) do {
        x++;
    }

    // x is now 10

    // Null-statement while loops are of the form "while (condition) ;" and are used
    // when the expression's side effect (here, decrementing x) is all that is needed
    while (x-- > 0)
        ; // null statement

    // x is now -1

    // Single-statement while loops are of the form "while (condition) statement;"
    // and are used as a shorthand form when only a single statement is needed
    while (x > -10)
        x--;

    // x is now -10

    return 0;
}

```

> While loops don't have a "do" before the opening curly brace. This actually creates a do-while loop inside of the (x \< 10) loop that's terminated by the following "null statement" while loop. Since x is incremented inside of the loop and then decremented in the do-while loop's condition, the inner loop never terminates, and so neither does the outer loop. The "single-statement" loop at the end is never reached.
> If you're still confused, look here (externally hosted because codegolf.SE doesn't like code blocks in spoilers).
> 87 votes

# Answer
# JavaScript

```
var a = true;
(function() {
  while(!a){}
  alert("infinite");
  var a = true;
})();

```

> Variable hoisting: JavaScript will actually grab my second definition of `var a = true;`, declare it at the top of the function as `var a;`, and modify my assignment to `a = true;` meaning `a` will be undefined at the time it enters the while loop.
> 84 votes

# Answer
# C#

```
class Program
{
    // Expected output:
    // 20l
    // 402
    // 804
    // l608
    // 32l6
    // game over man

    static void Main()
    {
        var x = 20l;
        while (x != 6432)
        {
            Console.WriteLine(x);
            x *= 2;
        }
        Console.WriteLine("game over man");
    }
}

```

> The number literal in the first line of the function is not a '201', but a '20' with a lowercase 'L' (**long** datatype) suffix. The number will overflow pretty quickly without ever hitting 6432, but the program will keep going unless overflow checking was switched on in the build options.
> Sensibly, Visual Studio 2013 (and probably other versions too) gives you a warning for this code, recommending that you use 'L' instead of 'l'.
> 49 votes

# Answer
## C

How about precision ?

```
int main(void)
{
    double x = 0;
    while(x != 10) x += 0.1;
    return 0;
}

```

> Imagine you have to store a range of integer numbers \<0;3\> in computer memory. There are only 4 integer numbers in this range (0,1,2,3). It's enough to use 2 bits to store that in memory. Now imagine you have to store a range of floating point numbers \<0;3\>. The problem is there is an infinite number of floating point numbers in this range. How to store infinite number of numbers ? It is impossible. We can only store finite number of numbers. This is why some numbers like 0.1 are actually different. In case of 0.1 it is 0.100000000000000006. It is highly recommended to not use == or != in conditions as far as you use floating point numbers.
> 39 votes

# Answer
# HTML / JavaScript

Imagine you have an input box in your page:

```
<input onfocus="if (this.value === '') alert('Input is empty!');">

```

And now you want to type something in it... Try in Chrome: http://jsfiddle.net/jZp4X/.

> Standard browser dialog box called with `alert` function is modal, so when it's displayed it takes the focus out of the text box, but when it is dismissed the text box receives the focus back.
> 33 votes

# Answer
# C++

```
#include <iostream>
#include <cstddef>

int main() {
    size_t sum = 0;
    for (size_t i = 10; i >= 0; --i) {
         sum += i;
    }
    std::cout << sum << std::endl;
    return 0;
}

```

> The condition `i >=0` is always true because size\_t is unsigned.
> 32 votes

# Answer
**bash**

*(There was a request for no loops or recursion)*

```
#!/bin/bash

# Demo arrays

foo=("Can I have an array?")

echo $foo

echo ${foo[0]}

foo[2] = `yes`

echo $foo

echo ${foo[2]}

```

> Instead of assigning the string 'yes' to foo\[2\], this calls the system command `yes`, which fills up foo\[2\] with a never ending amount of "yes\n".
> 29 votes

# Answer
# C

Letter "x" was lost in a file. A program was written to find it:

```
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
  FILE* fp = fopen("desert_file", "r");
  char letter;
  char missing_letter = argv[1][0];

  int found = 0;
  printf("Searching file for missing letter %c...\n", missing_letter);
  while( (letter = fgetc(fp)) != EOF ) {
    if (letter == missing_letter) found = 1;
  }
  printf("Whole file searched.\n");
  fclose(fp);
  if (found) {
    printf("Hurray, letter lost in the file is finally found!\n");
  } else {
    printf("Haven't found missing letter...\n");
  }
}

```

It was compiled and to ran and it finally shout:

```
Hurray, letter lost in the file is finally found!

```

For many years letters have been rescued this way until the new guy came and optimized the code. He was familiar with datatypes and knew that it's better to use unsigned than signed for non-negative values as it has wider range and gives some protection against overflows. So he **changed int into unsigned int**. He also knew ascii well enough to know that they always have non-negative value. So he also **changed char into unsigned char**. He compiled the code and went home proud of the good job he did. The program looked like this:

```
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
  FILE* fp = fopen("desert_file", "r");
  unsigned char letter;
  unsigned char missing_letter = argv[1][0];

  unsigned int found = 0;
  printf("Searching file for missing letter %c...\n", missing_letter);
  while( (letter = fgetc(fp)) != EOF ) {
    if (letter == missing_letter) found = 1;
  }
  printf("Whole file searched.\n");
  fclose(fp);
  if (found) {
    printf("Hurray, letter lost in the file is finally found!\n");
  } else {
    printf("Haven't found missing letter...\n");
  }
}

```

He came back to a havoc on the next day. Letter "a" was missing and even though it was supposed to be in the "desert\_file" containing "abc" the program was searching for it forever printing out only:

```
Searching file for missing letter a...

```

They sacked the guy and rolled back to previous version remembering that one should never optimize datatypes in working code.

But what is the lesson they should have learnt here?

> First of all, if you take a look at the ascii table you'll notice that there is no EOF. That's because EOF is not a character but a special value returned from fgetc(), which can either return character extended to int or -1 denoting end of file.
> As long as we are using signed char everything works well - char equal to 50 is extended by fgetc() into int equal to 50 as well. Then we transform it back to char and still have 50. Same happens for -1 or any other output coming from fgetc().
> But look what happens when we use unsigned char. We start with a char in fgetc() extend it to int and then want to have an unsigned char. The only problem is that we can't preserve -1 in unsigned char. Program is storing it as 255 which no longer equal to EOF.
> **Caveat**
> If you take a look at section 3.1.2.5 Types in copy of ANSI C documentation you'll find out that whether char is signed or not depends solely on implementation. So the guy probably shouldn't be sacked as he found a very tricky bug lurking in the code. It could come out when changing the compiler or moving to different architecture. I wonder who would be fired if the bug came out in such a case ;)

PS. Program was built around the bug mentioned in PC Assembly Language by Paul A. Carter
> 28 votes

# Answer
# Regex

With appropriate input, the following regex can cause most backtracking regex engine to go into backtracking hell:

```
^\w+(\s*\w+)*$

```

Simple input such as `"Programming Puzzles and Code Golf Stack Exchange - Mozilla Firefox"` or `"AVerySimpleInputWhichContainsAnInsignificantSentence."` (both strings quoted for clarity) is enough to keep most backtracking regex engines running for a long time.

> Since `(\s*\w+)*` allows for the expansion `\w+\w+\w+`...`\w+`, which means the regex engine will basically try out all possible ways to split up a string of *word characters*. This is the source of the backtracking hell.
> It can easily be fixed by changing `\s*` to `\s+`, then `(\s+\w+)*` can only be expanded to `\s+\w+\s+\w+`...`\s+\w+`.
> 21 votes

# Answer
# **JavaScript**

```
function thiswillLoop(){
var mynumber = 40;
while(mynumber == 40){
mynumber = 050;
}
return "test";
}
thiswillLoop();

```

> 050 is an octal constant in Javascript, and it happens to have the decimal value of 40.
> 20 votes

# Answer
# Haskell

```
head $ reverse $ (repeat '!') ++ "olleH"

```

Well, think of it! It would be the same as `head $ "Hello" ++ (repeat '!')`, i.e should just return `'H'`.

> In haskell lists are recursive structures, with first element being the topmost. To append to a list, you have to unroll all those elements, place your appendix, and put the lifted elements back. That wouldn't work on an infinite list. Similarly, reversing an infinite list won't magically give you your `"Hello"` back. It will just hang forever.
> 18 votes

# Answer
# Java under Windows

```
public class DoesntStop
{
    public static void main(String[]a) throws InterruptedException, IOException
    {
        ProcessBuilder p = new ProcessBuilder("cmd.exe","/c","dir");
        p.directory(new File("C:\\windows\\winsxs"));
        Process P = p.start();
        P.waitFor();
    }
}

```

> Program relies on a jammed standard output stream from the commandline to get stuck. The WinSXS directory under windows has multiple thousands of files with long names so it is almost guaranteed to clog stdout, and the `waitFor` can't return so the program is deadlocked
> 16 votes

# Answer
# To compare apples and oranges... in C

I'm impressed that there is no piece of code here using a `goto`... (You know: *Goto is evil!*)

```
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main()
{
    char *oranges = "2";
    long int apples;

next_harvest:

    apples = random() % 3;

    printf("%ld apples comp. %s oranges ...\n", apples, oranges);

    if( apples != (long int)oranges )
    {
        sleep(1);
        goto next_harvest;
    }

    return 0;
}

```

The sleep is just for being able to read it. Press ^C if you don't have an endless amount of time to wait for something that never happens ;-)
> 15 votes

# Answer
# C, with certain optimizing compilers

This program increments an integer variable until it overflows.

```
#include <stdio.h>
#include <stdint.h>
int main()
{
    int32_t x = 0;
    while(x + 1 > x)
        x++;
    printf("Got overflow!\n");
    return 0;
}

```

> Signed integer overflow is undefined behaviour. Usually in practice it wraps, when optimizations are turned off. With optimizations on, compilers can and do decide that `x + 1 > x` is always true.
> 12 votes

# Answer
# C++

```
int main()
{
  int x = 1;
  //why doesn't this code terminate??/
  x = 0;
  while(x) {} //no-op/
  return 0;
}

```

The weird commenting style is the trick. Hint: trigraphs.
> 11 votes

# Answer
## Java

I particular love this side effect of the autoboxing optimization:

```
class BoxingFun {
  public static void main( String[] args) {
    Integer max;
    Integer i;

    max = 100;
    for( i = 1; i != max; i++ ) {
      System.out.println("Not endless");
    }
    max = 200;
    for( i = 1; i != max; i++ ) {
      System.out.println("Endless");
    }
  }
}

```

> Because of autoboxing, `Integer` objects behave almost like plain `int`s here, with one exception: The `i != max` in the `for` loops compares the *references* (identity) of the `Integer` objects, not their value (equality). For values up to 100 this surprisingly "works" nevertheless because of an optimization in the JVM: Java preallocates `Integer` objects for the "most common values" and reuses them when autoboxing. So for values up to 100 we have identity \<==\> equality.
> 11 votes

# Answer
# Ruby/C

```
#include <stdio.h>
#ifdef llama
def int(*args)
end
def main(arg)
  yield
end
void = nil
#endif
#define do {
#define end }
int main(void) {
  int x = 10;
  while(x-=1) do
    printf("%i\n",x);
  end
    return 0;
}

```

This works correctly in C, counting down from 9 to 1 in STDOUT. When run in Ruby, it does not terminate, because

> 0 is not a false value in Ruby.
> 8 votes

# Answer
# JavaScript

```
// This multiplies the elements in the inner lists and sums the results.
function sum_of_products(var items)
{
        var total = 0;
        for(var i = 0; i < items.length; i++) {
                var subitems = items[i];
                var subtotal = 1;
                for(var i = 0; i < subitems.length; i++) {
                        subtotal *= subitems[i];
                }
                total += subtotal;
        }
        return total;
}

// Should return 1*2 + 3*4*5 + 6*7*8*9 + 10*11 = 3196
sum_of_products([[1, 2], [3, 4, 5], [6, 7, 8, 9], [10, 11]]);

```

> Both loops use the same loop variable, so depending on the input, the inner loop can keep the outer loop from ever finishing.
> 7 votes

# Answer
## C

This should print a code table for all ASCII characters, from 0 to 255. A `char` is large enough to iterate over them.

```
#include <stdio.h>

int main(){
    char i;
    for(i = 0; i < 256; i++){
        printf("%3d 0x%2x: %c\n", i, i, i);
    }
    return 0;
}

```

> All chars are less than 256. 255++ gives 0 due to overflow, so the condition `i < 256` always hold. Some compilers warn about it, some don't.
> 7 votes

# Answer
# C++

How about the classical C++-programmer's trap?

```
int main()
{
   bool keepGoing = false;

   do {
       std::cout << "Hello, world!\n";
   } while( keepGoing = true );

   return 0;
}

```
> 6 votes

# Answer
# Java:

```
public class LoopBugThing{
   public static void main(String[] args)
   {
      int i = 0;
      while(i < 10)
      {
         //do stuff here
         i = i++;
      }
      System.out.println("Done!");
   }
}

```

> The "i = i++" is a pretty common beginner mistake and can be surprisingly hard to find
> 6 votes

# Answer
# Python

```
a = True
m = 0
while a:
    m = m + 1
    print(m)
    if m == 10:
        exit

```

> it should be `exit()` and not `exit`. As I understand it, `exit()` is the command to exit the python interpreter. In this case the call is to the representation of the function and not to the function see: exit-discussion. Alternatively `break` would be a better choice.
> 6 votes

# Answer
# Haskell

Some code to time the computation of a given value of the Ackermann function. For very low values it usually terminates. On my machine very low values means something like 3 5 or smaller with compiled code and `-O`. In ghci low values means something like 3 3.

The `'` symbol seems to mess up syntax highlighting, not sure why. In some places they are needed so can't remove all of them.

Edit- changed language.

```
{-# LANGUAGE NamedFieldPuns #-}
import Control.Concurrent.STM
import Control.Concurrent
import Data.Time.Clock.POSIX

data D = D { time :: !POSIXTime
           , m :: !Integer
           , n :: !Integer
           , res :: !(Maybe Integer)
           } deriving Show

startvalue = D 0 3 8 Nothing

-- increment time in D. I belive lensen make code like
-- this prettier, but opted out.
inctime t t' (d@D{time}) = d {time = time + t' - t }

-- Counting time
countTime :: TVar D -> POSIXTime -> IO ()
countTime var t = do
    t' <- getPOSIXTime
    atomically $ modifyTVar' var (inctime t t')
    countTime var t'

-- Ackermann function
ack m n
    | m == 0    = n + 1
    | n == 0    = ack (m - 1) 1
    | otherwise = ack (m - 1) (ack m (n - 1))

-- Ackerman function lifted to the D data type and strict
ack' (d@D{m, n}) = let a = ack m n
                   in seq a (d { res = Just a })

-- fork a counting time thread, run the computation
-- and finally print the result.
main = do
    d <- atomically (newTVar startvalue)
    forkIO (getPOSIXTime >>= countTime d)
    atomically $ modifyTVar' d ack'
    (atomically $ readTVar d) >>= print

```

> This causes a livelock. The counting thread repeatedly causes the Ackermann computation to roll back since they touch the same TVar.
> 5 votes

# Answer
## C++

A bit of random ?

```
class Randomizer
{
   private:
   int max;

   public:
   Randomizer(int m)
   {
      max = m;
      srand(time(NULL));
   }

   int rand()
   {
      return (rand() % max);
   }
};

int main()
{
  Randomizer r(42);
  for (int i = 0; i < 100; i++)
  {
     i += r.rand();
  }
  return (0);
}

```

> Doesn't call the function `rand` but instead call recursively the `Randomizer::rand` function.
> 5 votes

# Answer
# Java -- No loops or recursion

I just started learning regular expressions and wrote my first program to test if my string matches a regular expression.

Unfortunately, the program does not produce any result. It holds up the terminal. Please help in finding the problem. I have not made any use of loops, there is no recursion involved. I am completely baffled.

```
import java.util.regex.*;

public class LearnRegex {
     public static void main(String[] args) {
         Pattern p = Pattern.compile("(x.|x.y?)+");
         String s = new String(new char[343]).replace("\0", "x");
         if (p.matcher(s).matches())
             System.out.println("Match successful!");
     }
}

```

## What have I done wrong? Why doesn't my program end? Please help!

Ideone link here.

> This is a stupid example of catastrophic backtracking. The complexity is O(2n/2). While the program might not run indefinitely, it'd probably outlive both living and non-living *objects* around and *not-so-around*.
> 5 votes

# Answer
# C

You should only need one of the two loops, but which one you need depends on your compiler.

```
main()
{
        int i, a[10];

        i = 0;
        while (i <= 10) {
            i++;
            a[i] = 10 - i;
            printf("i = %d\n", i);
        }

        /* Now do it in reverse */

        i = 10;
        while (i >= 0) {
            i--;
            a[i] = 10 - i;
            printf("i = %d\n", i);
        }

}

```

> A simple bounds overrun that resets *i* to a non-terminating value. Compilers can differ on whether they allocate *i* above or below *a* on the stack, so I've included overruns in both directions.
> 5 votes

# Answer
# C / C++

C++ just allows the easy inline variable declarations used here, but it's just as easy to make this mistake in plain old C...

```
#include <stdio.h>

int main(void)
{
    int numbers[] = {2, 4, 8};

    /* Cube each item in the numbers array */
    for(int i = 0; i < 3; i++) {
      for(int j = 0; j < 3; i++) {
        numbers[j] *= numbers[j];
      }
    }

    /* Print them out */
    for(int i = 0; i < 3; i++) {
      printf("%d\n", numbers[i]);
    }

    return 0;
}

```

> In the inner loop, 'j' is compared but never incremented. (The 'i++' should actually be 'j++'). This is not so much a sneaky trick but more of an actual error I've made in the past ;) Something to watch out for.
> 5 votes

# Answer
## C#

The following is a simple class performing an arithmetic operation (summation) on a large input array using a background thread. A sample program is included.

However, even though it is quite straightforward, it never terminates. Note that there is no sleight of hand (character lookalikes, hidden/missing semicolons, trigraphs ;-), etc.)

```
using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

class Program
{
    static void Main()
    {
        var summer = new BackgroundSummer(Enumerable.Range(1, 1234567));
        Console.WriteLine(summer.WaitAndGetResult());
    }
}

public class BackgroundSummer
{
    private IEnumerable<int> numbers;
    private long sum;
    private bool finished;

    public BackgroundSummer(IEnumerable<int> numbers)
    {
        this.numbers = numbers;
        new Thread(ComputingThread).Start();
    }

    public long WaitAndGetResult()
    {
        while (!finished) { /* wait until result available */ }
        return sum;
    }

    private void ComputingThread()
    {
        foreach(var num in numbers)
        {
            sum += num;
        }
        finished = true;
    }
}

```

> This is an example of a real-world nasty bug which might appear in your code as well. Per the .NET memory model and C# specification, a loop such as the one in `WaitAndGetResult` might never terminate unless you specify the variable as volatile, because it is modified by another thread. See this StackOverflow question for details. The bug is dependent on the .NET implementation, so it might or might not affect you. But usually, running a release build on an x64 processor seems to display the problem. (I tried it with *“csc.exe /o+ /debug- infinite.cs”*.)
> 4 votes

# Answer
Javascript

```
var а = 0;
a = 1;
while(а<10){
    a++;
}

```

> The variables used in 1st and 3rd line are different from the ones used in 2nd and 3rd line.
> One uses  (U+0061) while the other uses  (U+0430)
> 4 votes

# Answer
## Javascript

This once bit me years ago:

```
function outerloop(){
  for(i=0;i<10;i++){
    innerloop();
  }
}
function innerloop(){
  for(i=0;i<5;i++){
    console.log(i)
  }
}
outerloop();

```

> The trick here is that when one uses `for( i=0 ...`, the variable `i` is created in the *global scope* (even if they're in separate functions), so it gets overwritten every time by the inner loop. This is an easy pitfall for those coming from C++ or PHP. The fix is to use `var` to declare the variable in local scope (`for (var i...`)
> 4 votes

# Answer
**PowerShell**

```
$i = 1

do {
    $i++
} until( $i > 10 )

```

> The `>` is not the greater-than operator (which is `-gt`); it is the redirection operator. Since nothing is returned, PowerShell evaluates the expression as false and continues.
> 4 votes

# Answer
It is a GUI program that will show an empty frame titled `Hello, world!` and hide the frame in 1 second.

```
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.JFrame;
import javax.swing.SwingUtilities;
import javax.swing.Timer;

public class Main {
    public static void main(String[] args) {
        SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                // Create a frame titled "Hello, world!".
                final JFrame frame = new JFrame("Hello, world!");
                frame.setVisible(true);

                // After 1 second...
                Timer timer = new Timer(1000, new ActionListener() {
                    @Override
                    public void actionPerformed(ActionEvent e) {
                        // Hide the frame.
                        frame.setVisible(false);
                    }
                });
                timer.setRepeats(false);
                timer.start();
            }
        });
    }
}

```

> The frame is hidden, but it is not disposed, so the virtual machine would not terminate. Reference: http://docs.oracle.com/javase/7/docs/api/java/awt/doc-files/AWTThreadIssues.html#Autoshutdown
> 3 votes

# Answer
## C

```
int main(void) {
  float x = 0;
  while(x != 1) x+=0.1;
}

```

lots of nooses for a C developer....
> 3 votes

# Answer
# C

This was tested on a 64 bit machine with gcc using the compiler flag `-fomit-frame-pointer`.

```
int main() {
    long x = (long)main;
    asm("sub %0,%%rsp"::"i"(sizeof(x)));
}

```

> This makes the return address the address of main. Which makes an infinite loop. The assembly line is needed to not run out of stack.
> 3 votes

# Answer
# Java

Spawns a thread that will sleep for 1 second. The program should effectively sleep for a second while waiting for that thread to quit, and then end.

```
import java.lang.*;

class A {
    static boolean done;
    public static void main(String args[]) {
        done = false;
        new Thread() {
            public void run() {
            try {
                Thread.sleep(1000); // dummy work load
            } catch (Exception e) {
                done = true;
            }
            done = true;
            }
        }.start();
        while (!done);
        System.out.println("bye");
    }
}

```

Why it doesn't end
> 3 votes

# Answer
# JavaScript

```
while(true)
    if(NaN == NaN)
        break;
    else
        console.log("Batman");

```

> A funny property of the global `NaN` (Not a Number) object in JavaScript is that it is not equal to itsself. To test if a number is NaN one must use `isNaN()`. It's also amusing that `typeof(NaN)` returns `"number"`.
> 3 votes

# Answer
## C

This prints numbers from 0 to 9. Or at least it should...

```
#include <stdio.h>

int main() {
    int i;
    char line[12]; // "Iteration: x"

    for(i = 0; i < 10; i++) {
        sprintf(line, "Iteration: %d", i);
        puts(line);
    }

    return 0;
}

```

> This is a classic off-by-one error triggering a stack overflow. The string is indeed 12 characters long, but the programmer forgot about the NULL terminator inserted by sprintf! On GCC, local variables are pushed to the stack in declaration order. Other compilers may order the variables differently. Since the stack grows backwards, this means `i` is after `line` in memory. The null byte overwrites the least significant byte of `i`. At the end of the block, `i` is always `0`. `i` is incremented and it loops forever with `i = 1`.
> 3 votes

# Answer
## C

```
int main(void)
{
        float count = 0;
        while(count < 33554432L)
        {
                count++;
        }
        return 0;
}

```

> Floating-point numbers have limited precision. Under IEEE 754 floating-point math, a single-precision float only has 24 bits of precision: the largest integer that can be represented exactly is 16,777,216. 16777216 + 1 = 16777216.
> 2 votes

# Answer
## C#

Perhaps too obvious, but

```
class Program
{
    static void Main()
    {
        int x = 0;
        while (x * x != 1000)
            x++;
        System.Console.WriteLine("Square root of 1000 is " + x);
    }
}

```

> The square root of 1000 is not an integer, so it will never find it. It's just going to loop forever, assuming overflows aren't checked (the default is unchecked). So like I said, perhaps too obvious. But when I first saw it, I was pretty sure it was going to terminate - 1000 *looks* as though it should have an integer square root - to me, anyway.
> 2 votes

# Answer
**Postscript**

*hello.ps*:

```
/hello
{
    (Hello, world\n) print
    quit
}
dup 2 3 index cvx put def

hello

```

This prints "Hello, world" forever. To try it with ghostscript:

```
gs -sDEVICE=nullpage hello.ps

```

> `dup 2 3 index cvx put` replaces the procedure's call to `quit` with a recursive call to procedure *hello*. Since postscript does tail call optimization, this runs forever without overflowing the stack.
> 2 votes

# Answer
## TeX (Plain): Typesetting *The Song That Never Ends*

Compile with `pdftex`. It is not obfuscated (besides, well, being written in TeX) and actually *does* end, as `pdftex` stops after somewhat about 2.6 million pages...

```
\font\bigrm=cmr12 at 14pt
\centerline{\bigrm The Song That Never Ends}
\bigskip
\def\songthatneverend{
\noindent This is the song that never ends.\hfil\break
Yes, it goes on and on my friends.\hfil\break
Some people started singing it not knowing what it was,\hfil\break
and they'll continue singing it forever just because\smallskip

\expandafter\songthatneverend}
\songthatneverend
\bye

```
> 2 votes

# Answer
# Ruby

```
if p
  //misses
  raise 'Unreachable'
end

while p //nonsense, Kernel#p always returns nil, which is falsey, so this will immediately terminate.
  puts 'Looping'
end

puts 'Done looping'

```
> 2 votes

# Answer
### Batch

This loops forever outputting `Hello.`

```
@echo off
for /l %%a in (0,0,1) do echo Hello.

```

> The for loop tries to count from `0` to `0` incrementing by `1` \- `(0,0,1)`. So it never reaches zero.

Or if you want to cause the prompt to crash.

```
@echo off
for /l %%a in (0,1,1) do call %%%%a
:1
echo END

```

--

```
h:\uprof>end.bat
******  B A T C H   R E C U R S I O N  exceeds STACK limits ******
Recursion Count=477, Stack Usage=90 percent
******       B A T C H   PROCESSING IS   A B O R T E D      ******

```
> 1 votes

# Answer
# Javascript

Here's a typical beginner's programming exercise.

> Continually repeat a sequence of 1..*n1*, until you've output a total of *n2* numbers. For example, looping through 1..3 where the total quantity is 10 would produce this:
>
> 1 2 3 1 2 3 1 2 3 1

Below is a solution that uses a currying function. It's simple, elegant, and will hang your browser :-)

```
function output(msg) {
    $('<span></span>').text(msg).appendTo($('#output'));
}

function loopThroughSequence(max) {
    i = 0;
    return function() {
        if(i >= max) {
            i = 0;
        }
        return ++i;
    }
}

var getNextInSequence = loopThroughSequence(3);
for(var i = 0; i < 10; ++i) {
    output(' ' + getNextInSequence());
}

```

> Note that loopThroughSequence forgets to declare i in scope. (It needed to preceed 'i' with the 'var' keyword.) Instead, it uses the i value declared below it in the for loop, and continually resets it back to zero.
> 1 votes

# Answer
**C++**

```
#include<fstream.h>
int main()
{
 char ch[80];
 ifstream fin("evil.txt");
 while(fin)
 {
  fin.get(ch,50); //read by lines
  cout<<ch;
 } //nothing wrong, right? wrong.
 return 0;
}

```

evil.txt contains following data :

```
hello.
I am awesome.

```

> fin.get() leaves a '\n' in input stream. The rest is Elementary, my dear.
> 1 votes

# Answer
How about this...

```
#include<stdio.h>

void main(){
while((10*5/3)!=(10/3*5))
printf("In a loop\n");
}

```

Mathematically (10/3)\*5==(10\*5)/3;
> 1 votes

# Answer
**Whitespace**

(actual working code follows)

> Readable version:
>
> ```
> FSSSSSTTFFSFSSSSSTTFF
> ```
> Where `F` is linefeed, `S` is space and `T` is tab
> 1 votes

# Answer
## Haskell

This is just a simple program to illustrate return statements. Since the return statement ends the function, it doesn't run anything after it.

```
sayHello :: IO String
sayHello = do
    return "Hello!"
    sayHello

main = do
    hello <- sayHello
    putStrLn hello

```

> Return statements don't end functions, unlike in other languages.
> 1 votes

# Answer
**C**

```
int main(void) {
  int x;
  while(x<=10) x+=1;
}

```

from my experience this thing loops indefinitely only after 4 years of stable production at 3AM on a Saturday and once it loops for first time no system reboot can make it go away and within 15 minutes it happens to all high availability servers, dumping the entire production stack offline for a day.
> 0 votes

# Answer
**Java**

```
public class Main {
    public static void main(String[] args) {
        try{
        double i=1.0/0.0;
            while(i==i+1){  //weired condition should never be true
                System.out.println("This should never be printed");
            }
        }catch (ArithmeticException e){
            System.out.println("Caught divide by 0 exception");

        }
    }
}

```
> 0 votes

# Answer
## Ruby

This is a super efficient piece of code that simulates a dice.

```
def almost_dice
  rand(7) # will output a number between 0 and 6.
end

#I want a dice that outputs a number between 1 and 6, so I have no other choice, right?
def proper_dice
  d = almost_dice
  while d = 0
    d = almost_dice #Eventually, I'll get d != 0
  end
  return d
end

puts proper_dice

```

> In ruby what could look like a test : `d = 0` is actually an assignment. Since the assignement always succeed, then the test always returns true, hence the infinite loop
> 0 votes

# Answer
## C#

Let's take a page from this answer: https://codegolf.stackexchange.com/a/24376/16729 but do the computation on a background thread in the class constructor!

```
class BackgroundSummer
{
  static int sum;
  static BackgroundSummer()
  {
    // Let's compute the sum on another thread!
    var thread = new System.Threading.Thread(ComputeSum);
    thread.Start();
    thread.Join();
  }

  static void ComputeSum()
  { /* omitted: compute the sum here */ }

  static void Main()
  { }
}

```

An explanation of why this runs forever is here: http://ericlippert.com/2013/01/31/the-no-lock-deadlock/
> 0 votes

# Answer
# Scala

```
var break = false
for(i <- Stream.from(0) if !break) {
  break = i >= 10
}
println("Well done!")

```

> Infinite streams will continue to be evaluated even if break is true.

Or the second one.

```
var g = 6
def counter: Int = {
  g -= 2
  g
}
def test() = {
  val t = ListBuffer('s','t','a','r','t',' ','e','m','p','t','y')
  var i = t mkString // returns "start empty"
  var l = ListBuffer[Int]()
  while(i != "42") i = (l += counter) mkString // returns "42 after two iterations"
  s"$i should equal 42"
}
println(test())

```

> mkString captures the second argument as a separator, here s"$i should equal 42". So the value of $i is never "42" but goes indefinitely.
> 0 votes

# Answer
**wxpython**

"Hello World" example that fails to exit.

```
import sys
import time
import wx
from wx.lib.pubsub import setupkwargs
from wx.lib.pubsub import pub

class LoggerWindow(wx.Frame):
    def __init__(self):
        wx.Frame.__init__(self, None, title="Logger")
        self._log = wx.TextCtrl(self, style=wx.TE_MULTILINE)
        pub.subscribe(self.OnLogMessage, "LOG_MESSAGE")

    def OnLogMessage(self, msg):
        self._log.AppendText(msg)

class GUI(wx.Frame):
    def __init__(self):
        wx.Frame.__init__(self, None, title="Demo GUI - Hello World")
        self._logger = LoggerWindow()
        pub.sendMessage("LOG_MESSAGE", msg="GUI Starting")

        # Set up the Hello World message
        self._display = wx.TextCtrl(self, -1, size=(400,20), style=wx.TE_MULTILINE)
        self._display.AppendText("Hello World!")

        # Show it for a while
        self.Show()
        time.sleep(10)

        # Done
        self.Destroy()

App = wx.App()
Gui = GUI()
App.MainLoop()

```

> The log window, while not showing, keeps existing, so the "GUI" window disappears but the app keeps running. I had intended for this to be another example of "not using a loop", but obviously I am using a loop!
> 0 votes

# Answer
## Python

```
def sum(first, add=[]):
    add.append(first)
    sum = 0
    for el in add:
        sum+= el
    print sum
    return add

if __name__ == '__main__':
    #init
    add = sum(1)
    for el in add:
        sum(el)

```

this will loop forever due to the fact that expressions in default arguments are calculated when the function is defined, not when it’s called. So the list will grow until the user terminate the script.
> 0 votes

# Answer
## Java

```
public class Looper {
    public static final int END = Integer.MAX_VALUE;
    public static final int START = END - 100;

    public static void main(String[] args) {
        int count = 0;
        for (int i = START; i <= END; i++)
            count++;
        System.out.println(count);
    }
}

```

This program was blatantly copied from Bloch and Gafter's Java Puzzlers.

> The expression `i <= Integer.MAX_VALUE` is a tautology, at least if `i` is an `int`. By definition, no integer can be greater than `Integer.MAX_VALUE`.
> 0 votes

# Answer
## Tcl

```
set i 1
while $i<=10 {
    puts $i
    incr i
}

```

> I forgot to brace my expression, so `$i` will only be substituted once, when `while` is called
> 0 votes

# Answer
# **JAVASCRIPT**

found this while doing my project

```
function weirdCode(){
  var myarray= ["test",123,false];
  var myarray2 = myarray;
  myarray2[2] = !myarray2[2];
  while(myarray.toString() == myarray2.toString()){
    console.log("shouldn't myarray[2] == false? but it is "+myarray[2]+". but i only edit myarray2, which is "+myarray2[2]);
  }
  console.log("this will never called");
}
weirdCode();

```

> at line "var myarray2 = myarray;" it should be "var myarray2 = myarray.slice()", cause it will be referring the var to myarray, like sharing a var
> 0 votes

# Answer
## JAVASCRIPT

```
 var x = 1; while(x != 0) x -= 0.1;

```

> x = 1;
> x - 0.1 = 0.9;
> x - 0.1 = 0.8;
> x - 0.1 = 0.7000000000000001
> *WHAT!!!!!*

Now more about it
> 0 votes

# Answer
## Java, equal but not?

```
import java.util.HashMap;
import java.util.Map;

public class Endless {
    static class A {
        public A(int a) {
            b = a;
        }

        int b;
        @Override
        public boolean equals(Object obj) {
            return obj != null && (obj instanceof A) && ((A)obj).b == b;
        }
    }

    public static void main(String args[]) {
        Map<A,String> map = new HashMap<A, String>();
        A a = new A(1);
        A sameA = new A(1);

        System.out.println("a is sameA?" + a.equals( sameA ));

        map.put(a, "look ma, no hands!");

        while (!map.containsKey(sameA)){
            //we never get here, do we?
        }
        System.out.println("Done!");
    }
}

```
> 0 votes

# Answer
How about a fork bomb?

```
:(){ :|: &};:

```
> 0 votes

# Answer
**C**

This one works..

```
#include<stdio.h>

void main(){
double a=10;
float b=10;
while(a/3!=b/3)
printf("Infinite loop");
}

```
> 0 votes

# Answer
# In Ruby:

```
x = "a"

while ! x.equal?("aaaaaaaa")
   x += "a"
end

```

> In Ruby, the `.equal?` method checks for object equality, not value equlity. "aaaaaaaa" is a unique object, and thus has a different object ID than x. Because of this the statement will never be true.

Another one:

```
a = b = "a"

while a == b
    b << "a"
end

```

> Here `a` and `b` gets the reference to the same object. The `<<` method actually changes the value at the location where the object is referencing, and does not create a new object as most other methods does. Since both `a` and `b` references the same location, the values will always be the same.
> 0 votes

# Answer
## Powershell

I feel like counting from one to a hundred. Don't you?

```
$i = 1;
for($i -lt 100;$i++){$i}

```

...Wait a minute, that's way more than a hundred printing out...

...

...

This should be fairly simple to figure out, and I found it amusing, at least.
> 0 votes

# Answer
# C

```
#include <stdio.h>

int count_bits(unsigned int field)
    {
    unsigned int a = 1;
    int count = 0;

    while (1)
        {
        switch (a)
            {
            case 1 << 31: /* MAX_UINT32 */
                {
                break;
                }
            default:
                {
                if (field & a) count++;
                a <<= 1;
                }
            }
        };
    return count;
    }

int main(int argc, char *argv[])
    {
    printf("%d\n", count_bits(0xdeadbeef));
    return 0;
    }

```

> In C and C++ `case` is a jump target. The `break` breaks the `switch`, but not the `while`. Substituting `break;` with `return count;` will work.
> 0 votes

# Answer
# Java, with OpenCV

(just a snippet)

```
VideoCapture camera = new VideoCapture(0);
Mat frame = new Mat();
while(frame.get(1, 1)[0]<200)camera.read(frame);

```

Java OpenCV stores pixel values from 0 to 1, not 0 to 255.
> 0 votes

# Answer
# Lua

Totaly boring, but I thought it was still interesting:

```
-- Example of stack overflow using recursion
-- Function foo: this function will call itself forever: foo(foo(foo(foo(foo...
function foo() -- Our recursive function
    return foo() -- Our recursive call, this will cause the stack to overflow
end
pcall(foo) -- pcall will call foo in protected mode, catching stack overflows.
print("Stackoverflow! Avoid infinite recursion!") -- Use infinite recursion wisely

```

## How does it work?

I dont have a clue. I think its optimized to something like:

```
call main
exit
label foo:
jmp foo
label main:
push foo
call pcall
push "Stackoverflow! Avoid infinite recursion!"
call print

```

Notes:

* This is not assembly or lua bytecode or anthing
* Exponential recursion *will* result in a stack overflow: `foo(foo())`. I think this is because this will `call foo` before it will `jmp foo`?
* Can someone please make a C function and try it out with that? I would love to know if it will result in a overflow or not. (I am guessing it will, but you never know...)
> 0 votes

# Answer
C++'s rules can be pesky some times

```
a.cpp:
#include "Shape.h" // includes class Shape, with virtual functions on it

int callback(int value, Shape* s)
{
    // aggregates areas
    return value + s->getArea();
}

// Some boring work... we don't even call this function
int aggrigateAreas(Shape* begin, Shape* end)
{
    int rval = 0;
    for (Shape* iter = begin; iter != end; iter++)
        rval = callback(rval, iter);
    return rval;
}

b.cpp:
#include "Shape.h"

int callback(Shape* s)
{
    // aggrigate perimieters
    return s->getPerimiter();
}

// doSomethingImportant will actually do something for us
int doSomethingImportant(Shape* s)
{
    return callback(s); // this was more complicated in real life
}

main.cpp
#include "Shape.h"
#include <iostream>
int doSomethingImportant(Shape* s);

int main() {
    Square s(1); // square with side length 1
    std::cout << doSomethingImportant(&s); // should print 4, right?
    return 0;
}

```

Sadly, C/C++ is rather unfriendly if you have two functions in different translation units with different names. They call it a ODR violation (One Definition Rule) and it's Undefined Behavior. As it so happens, if the linker is not being kind to you today, your call to `callback` in `doSomethingImportant` can end up calling the `callback` in a.cpp. This is bad enough, but they also don't have the same signatures. `s` may get some garbage value, such as something which causes the virtual function lookup of `getArea`() to return the address just before `main`, creating an infinite loop when called. It even gets a few broken opcodes *just* right to maladjust the stack back to its initials stack height, so you don't even get a sane stack overflow.

Is this against the rules of code golf? Maybe. I am trying to claim a win by getting very unlucky with a compiler's handling of undefined behavior. Technically that's outside of the spec of the language.

However, the scars I put into my cubicle walls that day, dug deep with my fingers as I screamed in agony remain. Dug over the course of that *whole* 12 hour work day, with the debugger taunting me as I went (*You're {bleep}ing kidding me! Why did the debugger put me back in a.cpp again! I commented out all calls to that file wholesale! Maybe I should recompile the world again*)... that has to qualify as "underhanded" somehow, right? Please?

*I will not forget to open the anonymous namespace to store my callbacks*

*I will not forget to open the anonymous namespace to store my callbacks*

*I will not forget to open the anonymous namespace to store my callbacks*
> 0 votes

# Answer
## c++

A simple program, to show how operator overloading works:

EDIT: this is inspired by BF

```
#include <iostream>
class ops
{
public:
    int val=1;
    ops operator * (ops rhs){val++; return *this;}
    ops operator & (ops rhs){val-=3; return *this;}
};
int main() {
    ops a;
    while (a.val>0)
    {
        a=a**&a; //call operator* twice and operator& once, net effect of subtracting 1
        std::cout<<a.val;
    }
    return 0;
}

```

> This calls operator\* once and operator& zero times. \*&a is the same as a, because of pointers.
> 0 votes

# Answer
**c#**

```
    public void MemoryEfficientCountTo256()
    {
        for (byte i = 0; i <= 255; i++)
        {
            Console.WriteLine(i);
        }
    }

```

This is from a stackoverflow question. A byte can never be 256, so adding one takes it back to 0
> 0 votes

# Answer
## C#

```
   for (; ; )
    {
        try
        {
            string text = "SomeText";
            System.IO.File.WriteAllText(@"c:\Pathwith?.txt", text);

            break;
        }
        catch { }
    }

```
> -2 votes

# Answer
# C++ - Lame

Yay I is pro C++ I learnt `for` loop real quik now lets make cool program that print 1 to 10 cuz I am awesome and totaly did not chose C++ just cuz C doesnt allow `for` loop.

```
#include <stdio.h> // 2 lazy 4 std::cout

int main()
{
    int i = 1;
    for (i < 10; i++;)
    {
        printf("%d\n", i);
    }
}

```

No why I is pro C++ why U dont work I learn `for` syntax well :(

upvote `@fuandon` instead, he gave me the idea. This is my second one anyway...
> -2 votes

---
Tags: popularity-contest, underhanded
---


title: Order 40 sticks

text:
# Question
Title: Order 40 sticks
We have 40 sticks of same widths but different heights. How many arrangements are there possible to put them next to each other so that when we look from right we see 10 sticks and when we look from left we again see exactly 10 sticks?

For example such an ordering is:

Black sticks are hidden, red sticks are the ones you can see when you look from left, the blue sticks are the ones you can see when you look from right and purple one(i.e. the longest one) is the one that can be see seen from both sides.

As test cases:

* If we had 3 sticks number of orderings to see 2 from left and 2 from right is 2
* If we had 5 sticks number of orderings to see 3 from left and 3 from right is 6
* If we had 10 sticks number of orderings to see 4 from left and 4 from right is 90720

# Answer
# PARI/GP, 80

```
f(n,v)=abs(sum(k=1,n-1,binomial(n-1,k)*stirling(k,v-1,1)*stirling(n-k-1,v-1,1)))

```

The number of visible sticks is also called Skyscraper Numbers, after the pencil/grid game. This code is based on (only slightly altered) the formula from OEIS A218531. I don't know much PARI, but I really don't think there's much to golf out here.

Test cases are all shown at ideone.com. The result for `f(40,10)` is:

```
192999500979320621703647808413866514749680

```
> 8 votes

# Answer
# Python 3, 259 bytes

Not very happy with this.

```
import itertools as i
x=input().split()
y,k=x
y=int(y)
c=0
x=list(i.permutations(list(range(1,y+1))))
for s in x:
 t=d=0;l=s[::-1]
 for i in range(y):
  if max(s[:i+1])==s[i]:t+=1
 for i in range(y):
  if max(l[:i+1])==l[i]:d+=1
 if t==d==int(k):c+=1
print(c)

```

Example input and output:

```
10 4
90720

```

It generates all the possible combinations of the provided range, and then loops through them, checking each number in them to see if it equal to the maximum of the previous numbers. It then does the same backwards, and if the count forwards (t) = the count backwards (d) = the given view number (k) it's a valid one. It adds this to a counter (c) and prints that at the end.
> 1 votes

# Answer
## R, 104

```
function(N,K)sum(sapply(combinat::permn(N),function(x)(z=function(i)sum(cummax(i)==i)==K)(x)&z(rev(x))))

```

De-golfed a little:

```
    function(N,K) {
      all_perm <- combinat::permn(N)
      can_see_K_from_left <- function(i)sum(cummax(i) == i) == K
      can_see_K_from_both <- function(x)can_see_K_from_left(x) &
                                        can_see_K_from_left(rev(x))
      return(sum(sapply(all_perm, can_see_K_from_both)))
    }

```
> 0 votes

# Answer
# Pyth - 38 36 bytes

Basically a port of the R answer. Pretty slow, can't even complete `10, 4` online.

```
AGHQLlfqhS<bhT@bTUGlf!-,yTy_TH.pr1hG

```

The only things Pyth doesn't have are cummax and the `==` over vectors, but those only took a few bytes to implement.

Explanation and further golfing coming soon.

Try it here online.
> 0 votes

---
Tags: code-golf, combinatorics, permutations
---


title: Magic Sequences of length n

text:
# Question
Title: Magic Sequences of length n
A magic sequence is a sequence of non-negative integers `x[0..n-1]` such that there are exactly `x[i]` instances of `i`

For instance, 6,2,1,0,0,0,1,0,0,0 is a magic sequence since there are 6 0's, 2 1’s, and so on.

Write a function which when given n, outputs all magic sequences of length n

---

The program that can produce the correct output for the highest value of n within 10 seconds win. (All programs are welcome, though)

For example, Alice's program can deal with upto n=15 within 10 seconds while Bob's can deal with upto n=20 within the same time. Bob wins.

Platform: Linux 2.7GHz @ 4 CPUs

# Answer
> 21 votes
# Python, n≈108

```
def magic_sequences(n):
    if n==4:
        return (1, 2, 1, 0),(2, 0, 2, 0)
    elif n==5:
        return (2, 1, 2, 0, 0),
    elif n>=7:
        return (n-4,2,1)+(0,)*(n-7)+(1,0,0,0),
    else:
        return ()

```

This uses the fact, which I'll prove, that the only Magic sequences of length `n` are:

* `[1, 2, 1, 0]` and `[2, 0, 2, 0]` for `n=4`
* `[2, 1, 2, 0, 0]` for `n=5`
* `[n-4, 2, 1, 0, 0, ..., 0, 0, 1, 0, 0, 0]` for `n>=7`

So, for `n>=7`, one only needs to return a huge tuple. I can do this for up to roughly `n=10^8` on my laptop, which is likely limited by memory; any more and it freezes up. (Thanks to trichoplax for the idea of using tuples rather than lists.) Or, if one can instead print a dictionary of nonzero entries, `{0:n-4, 1:2, 2:1, (n-4):1}`, one can do this for ginormous `n`.

I prove the uniqueness for `n>=7`; the other ones can be checked by brute force or casework.

The sum of the entries of `l` is the total count of all numbers of the list, which is its length `n`. The list has `l[0]` zeroes, and so `n-l[0]` nonzero entries. But by definition `l[0]` must be nonzero or we get a contradiction, and each of the other nonzero entries is at least 1. This already accounts for a sum of `l[0] + (n-l[0]-1)*1 = n-1` out of the overall sum of `n`. So not counting `l[0]`, there can be at most one 2 and no entry bigger than 2.

But that means the only nonzero entries are `l[0], l[1], l[2], and l[l[0]]`, whose values are at most `l[0]` and a permutation of `1,1,2`, which gives a maximum sum of `l[0]+4`. Since this sum is `n`, which is at least 7, we have `l[0]>=3`, and so `l[l[0]]=1`. Now, there's at least one `1`, which means `l[1]>=1`, but if `l[1]==1` that's another `1`, so `l[1]>=2`, which implies `l[1]` is the lone `2`. This gives `l[2]=1`, and all the remaining entries are `0`, so `l[0]=n-4`, which completes the solution.

# Answer
> 4 votes
# Python 3, n≈40

```
def plausible_suffix(l,N):
    if sum(l)>N:
        return False

    pairs = [(N-1-i,l[i]) for i in range(len(l))]

    if sum(i*x for i,x in pairs)>N:
        return False

    num_remaining = N - len(l)

    for index, desired_count in pairs:
        count = l.count(index)
        more_needed = desired_count - count
        if more_needed<0:
            return False
        num_remaining -= more_needed
        if num_remaining<0:
            return False
    return True

plausible_func = plausible_suffix

def generate_magic(N):
    l=[0]
    while l:
        extend = False
        if plausible_func(l,N):
            if len(l)==N:
                yield l[::-1]
            else:
                extend = True
        if extend:
            l.append(0)
        else:
            while l[-1]>=N-2:
                l.pop(-1)
                if not l:raise StopIteration
            l[-1]+=1

n=40 #test parameter

if n>0:
    for x in generate_magic(n):
        print(n,x)

```

Does a breadth-first search of possible lists, filling in entries from right to left, stopping the search at a suffix if it isn't plausible, which can happen if:

* The sum of the entries in the suffix exceeds `n` (the sum for the whole list must be `n`)
* The weighted sum of `i*l[i]` in the suffix exceeds `n` (the sum for the whole list must be `n`)
* Any number appears in the suffix more times that the suffix says it should
* The number of remaining unfilled spots is too small to account for all numbers that need to appear more times.

I had original tested prefixes left to right, but that went more slowly.

The outputs up to `n=30` are:

```
4 [1, 2, 1, 0]
4 [2, 0, 2, 0]
5 [2, 1, 2, 0, 0]
7 [3, 2, 1, 1, 0, 0, 0]
8 [4, 2, 1, 0, 1, 0, 0, 0]
9 [5, 2, 1, 0, 0, 1, 0, 0, 0]
10 [6, 2, 1, 0, 0, 0, 1, 0, 0, 0]
11 [7, 2, 1, 0, 0, 0, 0, 1, 0, 0, 0]
12 [8, 2, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0]
13 [9, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
14 [10, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
15 [11, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
16 [12, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
17 [13, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
18 [14, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
19 [15, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
20 [16, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
21 [17, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
22 [18, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
23 [19, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
24 [20, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
25 [21, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
26 [22, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
27 [23, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
28 [24, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
29 [25, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
30 [26, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]

```

Except for the first three lists `[1, 2, 1, 0], [2, 0, 2, 0], [2, 1, 2, 0, 0]`, there is exactly one list of each length `n>6`, and it has the form `[n-4, 2, 1, ..., 0, 0, 1, 0, 0, 0]`. This pattern persists up to at least `n=50`. I suspect it holds forever, in which case it's trivial to output a huge number of these. Even if not, a mathematical understanding on the possible solutions would greatly speed up a search.

# Answer
> 0 votes
# Pyth - 15 bytes

Uses brute force by all possible sequences of len `n` and then filters.

```
f.A.eq/TkYT^UQQ

```

Full explanation coming soon.

Try it here online.

# Answer
> 0 votes
# K, 26 bytes

```
{f@&{x~(+/x=)'!#x}'f:!x#x}

```

Like Maltysen's approach, brute force. The heart of the program is a predicate which tests whether a given vector is "magic":

```
{x~(+/x=)'!#x}

```

Build an iota vector as long as the input vector (`!#x`), count the occurrences of each digit (`(+/x=)'`) and compare the result with the input vector (`x~`). If there's a match, you have a magic sequence.

Unfortunately, this first stab seems to be pretty slow. Testing using Kona on my laptop it takes about 12 seconds to handle n=7. I need to give this a bit more thought.

---
Tags: number, fastest-code, sequence
---


title: aBOTcalypse Now

text:
# Question
Title: aBOTcalypse Now
# aBOTcalypse

Design a bot to compete in a King-of-the-Hill challenge! Here's a replay of a default bot game.

The board is 2D, like a side-scrolling video game (but without any scrolling).

A valid bot must accept a multiline string representation of the region of the board it can see, and output a move for the bot.

### Mechanics

This is a survival game. The apocalypse has come, and only bots (and an endless supply of rocks stored in hammerspace) remain. Each bot is given a random starting location, at elevation 0. In a given move, a bot can rest, move, throw a rock, or drop a rock. Bots can share space with stationary rocks, but a bot that collides with another bot or a meteor is killed, as is a bot hit by a thrown rock.

* Gravity: bots and rocks must rest on top of the floor of the board or on top of another rock; resting on something else (air, a meteor, a bot, etc.) leaves one "unsupported". Unsupported bots or rocks will fall until they are supported; a fall of greater than one space will kill a bot, and a bot underneath a falling rock or bot is also killed. This means that trying to move or drop up will only work if the bot is currently sharing a space with a rock (otherwise the bot/rock will fall back down 1 space). A space can become "unsupported" if the rock beneath it falls **or is destroyed by a meteor or projectile**.
* Meteors: Each turn a meteor enters the board from the top. A meteor has a velocity of magnitude 2, with a random angle chosen uniformly in the range \[-180,0\], and a random starting x position. Meteors fall in a straight line along the given trajectory until they hit something, at which point they disappear. Note that rounding in a meteor's movement is towards 0 (as per python's `int()`).
* Projectiles: A bot can choose to throw a rock any distance up to its elevation. A thrown rock moves in a straight line until it hits something (all in one turn, unlike a meteor; thrown rocks don't appear on the board), at a slope of `- elevation / max distance`. **Note that thrown rocks begin their trajectory at x +- 1 square.** For example, if a bot is at an elevation of 5, and throws left a distance of 1, the rock will begin at `(x-1,5)` and end at `(x-2,0)`. Collision is only checked in steps of `dx=1`, and `dy` is rounded towards 0 (as per python's `int()`).

### Input

Each bot can see a square 20 pixels in each direction (Chebyshev distance = 20), up to the boundaries of the board. There are 8 different characters in each input string:

* `'#'` (board boundary)
* `'.'` (air)
* `'@`' (meteor)
* `'&'` (rock)
* `'e'`/`'s'` (an enemy bot, or itself)
* `'E'`/`'S'` (an enemy bot, or itself, sharing a space with a rock)

Here's an example input (line breaks will be `\n`):

```
..............................#
..............................#
..............................#
..............................#
..............................#
..............................#
..............................#
..............................#
..............................#
..............................#
..............................#
..............................#
..............................#
..............@...............#
.....................E........#
.....................&........#
.....................&........#
.....................&........#
.....................&........#
...........@.........&........#
....................s&........#
###############################

```

### Output

There are four actions that a bot can take each turn.

* `rest` (literally sit and do nothing)
* `move <direction>` moves the bot one space in any of the four directions, `up`, `down`, `left`, or `right`. Movement causes the bot to fall if the new space is not supported by the floor or a rock (`fall > 1 = bot.kill()`).
* `drop <direction>` places ("drops") a rock in the indicated direction. Dropping a rock up (i.e., placing a rock in the square `[bot_x, bot_y+1]`) or to the side causes it to fall until supported (possibly falling onto the bot during `drop up`). `drop down` places a rock in the same position as the bot, if there is not a rock there already.
* `throw <direction> <distance>` throws a rock as per the "projectiles" mechanics above, with the indicated max distance. Max distance is irrelevant for throwing upward or downward - the projectile collides with the square below (for `down`), or attempts to collide with the square above (for `up`) and then with the bot's square if it doesn't hit anything (killing the bot).

A bot in the contest must output a scalar string with its action upon receiving the input string.

### Interface

A bot must consist of a single program which can be called via a python 2 `subprocess`. Any commands should be indicated, and will be saved in a file called `command.txt`; before a game begins, the controller will execute each command in `command.txt`, in order, and then the final command will be used to pass input to the bot from then on.

A bot may have a single storage file called `storage.txt` in its folder; the "Default Thrower" bot shows an example implementation, using json to save its state during various turns. In addition, feel free to include debugging output in a write-only `errlog.txt`, which I'll pass along in case your bot fails during a run. I'll make sure to run several tests with each bot, to try and find any errors beforehand.

### Scoring

A bot's total score is equal to the number of turns it survives, accumulated over X games of maximum length Y. At the moment, `X,Y = 10, 500`; if bots are lasting a long time, I'll increase Y, and if they are lasting a short time, I'll increase X.

Controller code is found in controller.py; many thanks to @Nathan Merrill for his DDOS koth from which I adapted the Communicator code.

# Answer
> 1 votes
# Python 2, Edgebot

Edgebot wants to hide in a corner and build a tower. They'll run to one end, build up a bit, then start dropping rocks to build a wall. Edgebot does not like visitors, and will throw rocks at anyone who gets too close to their tower. If it all goes horribly wrong and edgebot crashes, it'll drop a rock on its own head

```
import sys
from random import randint
class edgebot():

    def playtime(self,board):
        try:
            self.max_height = 5
            board = board.splitlines()

            #find edgebot
            for y in xrange(0,len(board)):
                row = board[y]
                symbol = 's' if row.count('s') else 'S'
                x = row.find(symbol)
                if x >= 0:
                    self.height = 20 - y
                    break

            ground = board[len(board)-2]
            floor = board[len(board)-1]
            nasty_person = 'e' if ground.count('e') else 'E'
            bad_x = ground.find(nasty_person)
            side = ground.find('#')
            if abs(side - x) ==1:
                self.end_found = 1
            else:
                self.end_found = 0

            if side - x == -1:
                self.direction = 'right'
            else:
                self.direction = 'left'

            #Bad edgebot! No climbing out of the game!
            if floor[x] != '#':
                if board[self.height-1][x] == '&':
                    dist = randint(3,self.height)
                    return 'throw ' + self.direction + ' ' + `dist`
                elif symbol =='S':
                    return 'drop up'
                else:
                    return 'move down'

            #Edgebot will go through you to find a corner. You have been warned.
            elif abs(x - bad_x) <=2:
                if x - bad_x >0:
                    return 'throw left 1'
                else:
                    return 'throw right 1'

            #edgebot wants to hide in a corner
            elif self.end_found ==0:
                if side == -1:
                    return 'move right'#edgebot is right-handed
                elif side - x < -1:
                    return 'move left'
                elif side - x > 1:
                    return 'move right'

            #Too close! Throw rocks at it!
            elif self.height+1>= abs(x-bad_x) and abs(x-bad_x) >=3:
                distance = abs(x - bad_x) - 2
                if distance < 1:
                    return 'throw ' + self.direction + ' 1'
                else:
                    return 'throw ' + self.direction + ' ' +`distance - 1`
                self.max_height += 2 #people came close, edgebot needs to be higher up!

            #edgebot wants a home in the corner
            elif self.height <self.max_height :
                if symbol =='S':
                    return 'move up'
                else:
                    return 'drop down'

            #edgebot wants a wall. edgebot has, at best, a limited understanding of architecture
            elif bad_x < 3 or self.height+1<abs(x-bad_x):
                if self.direction == 'right' and row[x+1] == '&':
                    self.max_height += 2
                    return 'drop down'
                elif self.direction == 'left' and row[x-1] == '&':
                    self.max_height += 2
                    return 'move down'
                else:
                    return 'drop ' + self.direction

            else:
                return 'drop down' #Not sure? Hide under a rock!
        except:
            return 'drop up' #All gone horribly wrong? Squish.

print edgebot().playtime(sys.argv[1])

```

Sorry for all the edits, didn't run enough test cases before submitting. There's a small problem in that the little guy will try to climb off the top of the board given enough time, but hopefully that won't be an issue in most matches. Edgebot should now just throw rocks random distances once it's climbed high enough

Last edit for now. Edgebot will now throw rocks at anyone close enough between it and the wall. No sense it taking itself out by running through someone

---
Tags: game, king-of-the-hill
---


title: A Basic Pyth-like Syntax Checker

text:
# Question
Title: A Basic Pyth-like Syntax Checker
Pyth is a golfing language based on Python. It uses prefix notation, with each command having a different arity (number of arguments it accepts).

Your task is to write a syntax checker for a (non-existent) Pyth-like language, Pith.

## Pith's syntax

Pith only has 8 single-char commands:

```
01234()"

```

`01234` each have arity of the corresponding number, and hence expect that many arguments after it. For example,

```
400010

```

is a correct Pith program because `4` is followed by four arguments `0` `0` `0` and `10`, the last of which is a `1` followed by the single argument `0`. To visualise this, we can look at the following tree:

```
      R
      |
      4
      |
-------------
|   |   |   |
0   0   0   1
            |
            0

```

where `R` is the root node. An alternative way to think about this is that each number refers to the number of children the corresponding node has in the tree above.

Here's another valid Pith program, with more than one base command:

```
210010

```

corresponding to

```
           R
           |
     -------------
     |           |
     2           1
     |           |
 ---------       0
 |       |
 1       0
 |
 0

```

On the other hand,

```
3120102100

```

is *not* a correct Pith program because the initial `3` only has two arguments, which we can see by looking at the tree below:

```
                R
                |
                3
                |
     ------------------------ ??
     |          |
     1          2
     |          |
     2        ------
     |        |    |
   ------     1    0
   |    |     |
   0    1     0
        |
        0

```

Next `(` starts an unbounded, and `)` ends an unbounded. An unbounded takes any number of arguments (greedily), and counts as a single argument to any parent command. Any unboundeds still open by the end of the program are automatically closed. A `)` command is not an error if no unboundeds are open — it just does nothing.\*

For instance, the Pith program

```
)31(0)0(201000100

```

corresponds to the tree

```
            R
            |
            3
            |
    ------------------------------
    |       |                    |
    1       0                    (
    |                            |
    (              -----------------------------
    |              |      |      |      |      |
    0              2      0      0      1      0
                   |                    |
                -------                 0
                |     |
                0     1
                      |
                      0

```

Empty unboundeds are okay, so `()` is a valid Pith program.

An invalid Pith program with an unbounded is

```
12(010

```

since the `2` only receives one argument (the unbounded).

Finally, `"` starts and ends a string, which is always 0 arity and counts as a single argument, e.g.

```
2"010""44)()4"

```

which is just a `2` being passed two string arguments `"010"` and `"44)()4"`. Like unboundeds, strings may also be empty, and any unclosed strings by the end of the program are automatically closed.

<sup>\*This part is different from the original Pyth which actually *does* do something in a case like `1)`, ending the 1-arity and raising an error.</sup>

## Input/output

Input will be a single non-empty string consisting of only the characters `01234()"`. You may optionally assume that an additional trailing newline is always present. You may write a function or a full program for this challenge.

You should output a truthy value if the input is syntactically valid Pith, or a falsy value otherwise. The truthy and falsy values must be fixed, so you can't output `1` for one valid program and `2` for another.

## Scoring

This is code-golf, so the code in the fewest bytes wins.

## Test cases

Truthy:

```
0
)
(
"
()
""
10
400010
210010
("")00
3"""""
(0)))0)1)0
2(2(2(0)0)0)0
2"010""44)()4"
)31(0)0(201000100
())2)1))0"3())"))
3("4321("301(0)21100"4")"123"00)40"121"31000""01010

```

Falsy:

```
1
1(310
(1)0)
12(010
4"00010"
3120102100
20(2((0)(0)))
2(2(2(0)0)0)01)
4(0102)00)00000
2"00"("00"2(""))

```

# Answer
> 12 votes
# CJam, 65 bytes

```
q'"/La+2%{0s*}:Z~_,:L')*+{L{4{)_Z+s/Z}/L{'(\Z')++/Z}/}*')-}2*0s-!

```

*Gosh, I wish CJam had Regex, this could have been completed in less than 50 bytes then*

The main idea is to keep reducing stuff to `0` i.e. `10` to `0`, `200` to `0` and so on. Once that is done, we reduce all matched brackets to `0`, i.e. `()` to `0`, `(0)` to `0`, `(00)` to `0` and so on. The we repeat the cycle `L` times, where `L` is the input length.

The input string initially goes through extra processing where we adjust for unmatched `"` and add lots of `)` to compensate for unmatched `(`

This ensures that after all the iterations, we should only have `0` (and no-op `)`) left in the string.

*Update - fixed a bug where top level `)` no-op are considered harmful*

**Code expansion**

```
q'"/La+2%{0s*}:Z~_,:L')*      "Part 1 - Preprocessing";
q'"/                          "Read the input and split it on quote";
    La+                       "Add an extra empty array to the split array to compensate";
                              "for unmatched ending quote";
        2%                    "Take every other splitted part, ignoring the contents";
                              "of the strings in the code";
          {0s*}:Z~            "Join the parts by string 0. Also create a function Z";
                              "that does that for future use. We are now done with";
                              "reducing "XYZ" to 0 ";
                  _,:L        "Store the length of the remaining code in L";
                      ')*     "Append L ) to the string to compensate for unmatched (";

{L{4{)_Z+s/Z}/L{'(\Z')++/Z}/}*')-}2*   "Part 2 - the reducing loop";
 L{                         }*         "Run the reduction logic L times";
   4{)_Z+s/Z}/                         "Part 2a - reducing arities";
   4{       }/                         "Run the iteration for 0, 1, 2 and 3";
     )_                                "Increment the iteration number and make a copy";
       Z+s                             "Get that many 0 and append it to the number";
          /Z                           "Split the code onto this number and convert it";
                                       "to 0. This successfully reduces 10, 200, ";
                                       "3000 and 4000 to 0";
              L{'(\Z')++/Z}/           "Part 2b - reducing groups";
              L{          }/           "Run the iteration for 0 through L - 1";
                '(\Z')++               "Get the string '(<iteration number of 0>)'";
                        /Z             "split on it and join by 0. This successfully";
                                       "reduces (), (0), (00) and so on .. to 0";
                              ')-      "After running the part 2 loop L times, all";
                                       "reducible arities and brackets should be reduced";
                                       "except for cases like '30)00' where the no-op )";
                                       "breaks the flow. So we remove ) from the code";
                                       "and run Part 2 L times again";

0s-!                          "Now, if the code was valid, we should only have 0 in the";
                              "remaining code. If not, the code was invalid";

```

Try it online here or run the whole suite

# Answer
> 12 votes
# Regex, PCRE flavor, 83 bytes

```
^(?3)*\)*$(()((?(2)|\)*)(\((?1)*(\)|$)|0|"[^"]*.?|(1|(2|(3|4(?3))(?3))(?3))(?3))))?

```

Try it here.

# Regex, PCRE flavor, 85 bytes

```
^((?(3)|\)*)(?>\((?2)*(()(?1))?(\)|$)|0|"[^"]*.?|(1|(2|(3|4(?1))(?1))(?1))(?1)))*\)*$

```

Try it here.

Used some ideas in this dan1111's answer.

Some explanations about `(?2)*(()(?1))?`.

# Answer
> 5 votes
# 80386 Assembler, 97 bytes

Hex dump:

```
0000000: 8b54 2404 5589 e531 c96a ff8a 022c 303c  .T$.U..1.j...,0<
0000010: f275 04f6 d530 c084 ed75 263c f875 0141  .u...0...u&<.u.A
0000020: 3cf9 750f 84c9 7419 4958 3c00 7c03 50eb  <.u...t.IX<.|.P.
0000030: 2430 c084 c075 0958 483c ff7f 0140 ebf3  $0...u.XH<...@..
0000040: 5042 8a02 84c0 75c5 4a84 edb0 2275 be84  PB....u.J..."u..
0000050: c9b0 2975 b85a 31c0 39e5 7501 4089 ec5d  ..)u.Z1.9.u.@..]
0000060: c3                                       .

```

This runs through the input once, pushing numbers greater than zero onto the stack and decrementing them when a zero is processed. Unboundeds are processed as a -1.

Function prototype (in C) (function returns 0 if invalid and 1 if valid):

```
int __cdecl test(char *in);

```

Equivalent assembly (NASM):

```
bits 32
; get input pointer into edx
mov edx, [esp+4]                ; 8B 54 24 04

; save ebp; set ebp = esp
push ebp                        ; 55
mov ebp, esp                    ; 89 E5

; clear ecx
xor ecx, ecx                    ; 31 C9

; push base -1
push byte(-1)                   ; 6A FF

; get top char
mov al, [edx]                   ; 8A 02

    sub al, 0x30                ; 2C 30

    ; if al == quote
    cmp al, 0xF2                ; 3C F2
    jne $+6                     ; 75 04
        ; set ch (in quote?) to opposite
        not ch                  ; F6 D5
        ; set value to 0
        xor al, al              ; 30 C0

    ; if in quote, continue
    test ch, ch                 ; 84 ED
    jnz $+40                    ; 75 26

    cmp al, 0xF8                ; 3C F8
    jne $+3                     ; 75 01
        ; increment cl=depth
        inc ecx                 ; 41

    cmp al, 0xF9                ; 3C F9
    jne $+17                    ; 75 0F
        ; check depth = 0
        test cl, cl             ; 84 C9
        jz $+27                 ; 74 19
        ; decrement cl=depth
        dec ecx                 ; 49
        ; pop and check -1
        pop eax                 ; 58
        cmp al, 0               ; 3C 00
        jl $+5                  ; 7C 03
            push eax            ; 50
            jmp $+38            ; EB 24
        xor al, al              ; 30 C0

    test al, al                 ; 84 C0
    jnz $+11                    ; 75 09
        pop eax                 ; 58
        dec eax                 ; 48
        cmp al, -1              ; 3C FF
        jg $+3                  ; 7F 01
            inc eax             ; 40
        jmp $-11                ; EB F3
    push eax                    ; 50

    inc edx                     ; 42
    mov al, [edx]               ; 8A 02
    test al, al                 ; 84 C0
    jnz $-57                    ; 75 C5

    dec edx                     ; 4A

    ; in quote?
    test ch, ch                 ; 84 ED
    mov al, 0x22                ; B0 22
    jnz $-64                    ; 75 BE

    ; depth not zero?
    test cl, cl                 ; 84 C9
    mov al, 0x29                ; B0 29
    jnz $-70                    ; 75 B8

; pop base -1
pop edx                         ; 5A

; set return value based on ebp/esp comparison
xor eax, eax                    ; 31 C0
cmp ebp, esp                    ; 39 E5
jne $+3                         ; 75 01
inc eax                         ; 40
; restore esp
mov esp, ebp                    ; 89 EC
; restore ebp
pop ebp                         ; 5D
; return
ret                             ; C3

```

The following code in C can be used with GCC on a POSIX system to test:

```
#include <sys/mman.h>
#include <stdio.h>
#include <string.h>

int main(){
    char code[] = {
        0x8b, 0x54, 0x24, 0x04, 0x55, 0x89, 0xe5, 0x31, 0xc9, 0x6a, 0xff,
        0x8a, 0x02, 0x2c, 0x30, 0x3c, 0xf2, 0x75, 0x04, 0xf6, 0xd5, 0x30,
        0xc0, 0x84, 0xed, 0x75, 0x26, 0x3c, 0xf8, 0x75, 0x01, 0x41, 0x3c,
        0xf9, 0x75, 0x0f, 0x84, 0xc9, 0x74, 0x19, 0x49, 0x58, 0x3c, 0x00,
        0x7c, 0x03, 0x50, 0xeb, 0x24, 0x30, 0xc0, 0x84, 0xc0, 0x75, 0x09,
        0x58, 0x48, 0x3c, 0xff, 0x7f, 0x01, 0x40, 0xeb, 0xf3, 0x50, 0x42,
        0x8a, 0x02, 0x84, 0xc0, 0x75, 0xc5, 0x4a, 0x84, 0xed, 0xb0, 0x22,
        0x75, 0xbe, 0x84, 0xc9, 0xb0, 0x29, 0x75, 0xb8, 0x5a, 0x31, 0xc0,
        0x39, 0xe5, 0x75, 0x01, 0x40, 0x89, 0xec, 0x5d, 0xc3,
    };
    void *mem = mmap(0, sizeof(code), PROT_WRITE|PROT_EXEC, MAP_ANON|MAP_PRIVATE, -1, 0);
    memcpy(mem, code, sizeof(code));
    int __cdecl (*test)(char *) = (int __cdecl (*)(char *)) mem;

    #define TRY(s) printf(s ": %d\n", test(s))

    printf("Truthy tests:\n");
    TRY("0");
    TRY(")");
    TRY("(");
    TRY("\"");
    TRY("()");
    TRY("\"\"");
    TRY("10");
    TRY("400010");
    TRY("210010");
    TRY("(\"\")00");
    TRY("3\"\"\"\"\"");
    TRY("(0)))0)1)0");
    TRY("2(2(2(0)0)0)0");
    TRY("2\"010\"\"44)()4\"");
    TRY(")31(0)0(201000100");
    TRY("())2)1))0\"3())\"))");
    TRY("3(\"4321(\"301(0)21100\"4\")\"123\"00)40\"121\"31000\"\"01010");

    printf("\nFalsy tests:\n");
    TRY("1");
    TRY("1(310");
    TRY("(1)0)");
    TRY("12(010");
    TRY("4\"00010\"");
    TRY("3120102100");
    TRY("20(2((0)(0)))");
    TRY("2(2(2(0)0)0)01)");
    TRY("4(0102)00)00000");
    TRY("2\"00\"(\"00\"2(\"\"))");

    munmap(mem, sizeof(code));
    return 0;
}

```

# Answer
> 4 votes
# lex, 182 bytes (157 w/ fixed-size stack)

These programs require the input to be a single new-line terminated string of valid characters.

```
%%
 int n=0,s=0,*t=0;
[0-4] n+=*yytext-48-!!n;
\( (t=realloc(t,(s+1)*sizeof n))[s++]=n-!!n;n=0;
\) if(s&&n)exit(1);s&&(n=t[--s]);
\"[^"]*.? n-=!!n;
\n while(s)t[--s]&&n++;exit(!!n);

```

The above program will segfault if it runs out of memory, which could theoretically happen if you give it enough `(`. But since a segfault counts as failure, I'm taking that as "falsey", although the problem description doesn't say what to do if resources don't suffice.

I cut it down 157 bytes by just using a fixed-size stack, but that seemed like cheating.

```
%%
 int n=0,s=0,t[9999];
[0-4] n+=*yytext-48-!!n;
\( t[s++]=n-!!n;n=0;
\) if(s&&n)exit(1);s&&(n=t[--s]);
\"[^"]*.? n-=!!n;
\n while(s)t[--s]&&n++;exit(!!n);

```

To compile:

```
flex -o pith.c pith.l    # pith.l is the above file
c99 -o pith pith.c -lfl

```

Test:

```
while IFS= read -r test; do
  printf %-78s "$test"
  if ./pith <<<"$test"; then echo "OK"; else echo "NO"; fi
done <<EOT
0
)
(
"
()
""
10
400010
210010
("")00
3"""""
2(2(2(0)0)0)0
2"010""44)()4"
)31(0)0(201000100
3("4321("301(0)21100"4")"123"00)40"121"31000""01010
1
1(310
12(010
4"00010"
3120102100
20(2((0)(0)))
2(2(2(0)0)0)01)
4(0102)00)00000
2"00"("00"2(""))
EOT

```

Test output:

```
0                                                                             OK
)                                                                             OK
(                                                                             OK
"                                                                             OK
()                                                                            OK
""                                                                            OK
10                                                                            OK
400010                                                                        OK
210010                                                                        OK
("")00                                                                        OK
3"""""                                                                        OK
2(2(2(0)0)0)0                                                                 OK
2"010""44)()4"                                                                OK
)31(0)0(201000100                                                             OK
3("4321("301(0)21100"4")"123"00)40"121"31000""01010                           OK
1                                                                             NO
1(310                                                                         NO
12(010                                                                        NO
4"00010"                                                                      NO
3120102100                                                                    NO
20(2((0)(0)))                                                                 NO
2(2(2(0)0)0)01)                                                               NO
4(0102)00)00000                                                               NO
2"00"("00"2(""))                                                              NO

```

# Answer
> 3 votes
# Python 2, 353 bytes

The parse function steps through the tokens one at a time and builds a tree of the program structure. Invalid programs trigger an exception which causes a zero (Falsy) to be printed, otherwise successful parsing results in a one.

```
def h(f,k=0):
 b=[]
 if k:
  while f:b+=[h(f)]
  return b
 q=f.pop(0)
 if q==')':return[]
 elif q=='"':
  while f:
   q+=f.pop(0)
   if q[-1]=='"':break
 elif q=='(':
  while f:
   if f and f[0]==')':f.pop(0);break
   b+=h(f)
 else:
  for i in range(int(q)):b+=h(f)
  assert len(b)==int(q)
 return[[q,b]]
try:h(list(raw_input()));r=1
except:r=0
print r

```

The output of the tests showing the parser output:

```
------------------------------------------------------------
True: 0
    0

------------------------------------------------------------
True: )

------------------------------------------------------------
True: (
    (

------------------------------------------------------------
True: "
    "

------------------------------------------------------------
True: ()
    (

------------------------------------------------------------
True: ""
    ""

------------------------------------------------------------
True: 10
    1
        0

------------------------------------------------------------
True: 400010
    4
        0
        0
        0
        1
            0

------------------------------------------------------------
True: 210010
    2
        1
            0
        0
    1
        0

------------------------------------------------------------
True: ("")00
    (
        ""
    0
    0

------------------------------------------------------------
True: 3"""""
    3
        ""
        ""
        "

------------------------------------------------------------
True: 2(2(2(0)0)0)0
    2
        (
            2
                (
                    2
                        (
                            0
                        0
                0
        0

------------------------------------------------------------
True: 2"010""44)()4"
    2
        "010"
        "44)()4"

------------------------------------------------------------
True: )31(0)0(201000100
    3
        1
            (
                0
        0
        (
            2
                0
                1
                    0
            0
            0
            1
                0
            0

------------------------------------------------------------
True: 3("4321("301(0)21100"4")"123"00)40"121"31000""01010
    3
        (
            "4321("
            3
                0
                1
                    (
                        0
                2
                    1
                        1
                            0
                    0
            "4"
        "123"
        0
    0
    4
        0
        "121"
        3
            1
                0
            0
            0
        ""
    0
    1
        0
    1
        0

------------------------------------------------------------
False: 1
0
------------------------------------------------------------
False: 1(310
0
------------------------------------------------------------
False: 12(010
0
------------------------------------------------------------
False: 4"00010"
0
------------------------------------------------------------
False: 3120102100
0
------------------------------------------------------------
False: 20(2((0)(0)))
0
------------------------------------------------------------
False: 2(2(2(0)0)0)01)
0
------------------------------------------------------------
False: 4(0102)00)00000
0
------------------------------------------------------------
False: 2"00"("00"2(""))
0

```

The code before the minifier:

```
def parse(tokens, first=False):
    toklist = []
    if first:
        while tokens :
            toklist += [parse(tokens)]
        return toklist
    tok = tokens.pop(0)
    if tok == ')' :
        return []
    elif tok == '"':
        while tokens:
            tok += tokens.pop(0)
            if tok[-1] == '"' :
                break
    elif tok == '(':
        while tokens:
            if tokens and tokens[0] == ')' :
                tokens.pop(0);
                break
            toklist += parse(tokens)
    else:
        for i in range(int(tok)) :
            toklist += parse(tokens)
        assert len(toklist) == int(tok)
    return [[tok, toklist]]

try :
    parse(list(raw_input()));
    r = 1
except :
    r = 0
print r

```

# Answer
> 1 votes
# Javascript (ES6), ~~289~~ ~~288~~ ~~285~~ ~~282~~ ~~278~~ ~~244~~ ~~241~~ 230 bytes

```
c=prompt(k="0"),j=c[l="length"];if((c.match(/"/g)||[])[l]%2)c+='"';c=c[R="replace"](/".*?"/g,k);c+=")".repeat(j);while(j--)c=c[R](/\(0*\)/,k)[R](/10/g,k)[R](/200/g,k)[R](/3000/g,k)[R](/40000/g,k);alert(!c[R](/0/g,"")[R](/\)/g,""))

```

# Answer
> 1 votes
# Pip, ~~88~~ 72 bytes

Idea taken from Optimizer's CJam. My original stab at the problem with a recursive descent parser was... rather longer.

```
Qpz:,5.iX,5AL'(.0X,#p.')p^:'"Fj,#pIj%2p@j:0p:Jpp.:')X#pL#ppR:z0!pRM')Rz0

```

Formatted, with explanation:

```
Qp                Query user for p
z:                Store the following list in z:
  ,5 . 0X,5         For x in range(5), concatenate x zeros to it
  AL                (append list)
  '(. 0X,#p .')     For x in range(len(p)), concatenate x zeros inside parens
p^: '"            Split p on " and assign result back to p
Fi,#p             Loop over the indices of the resulting list:
 Ii%2               If index is odd:
  p@i:0               Replace that item with 0
p: Jp             Concatenate the results and assign back to p
p.: ')X#p         Append len(p) closing parens to p
L#p               Loop len(p) times:
 pR:z0              Replace every occurrence in p of items of z with 0
! pRM')Rz0        Remove ) from result and replace z with 0 one more time; then
                  take logical negation, which will be true iff string is empty OR
                  consists only of zeros

```

Interesting tricks:

* Many operators work item-wise on lists and ranges. So `0X,5`, for example, is `0 X [0 1 2 3 4] == ["" "0" "00" "000" "0000"]`.
* As of a few days ago, the ternary `R`eplace operator can take a list for any of its arguments: `"abracadabra" R ["br" "ca"] 'b` gives `ababdaba`, for example. I make good use of this feature with `z` here.
* Falsy values in Pip include the empty string `""`, empty list `[]`, and any scalar that is zero. Thus, `0` is false, but also `0.0` and `"0000000"`. This feature is inconvenient sometimes (to test whether a string is empty, one must test its length because `"0"` is false too), but for this problem it's perfect.

---
Tags: code-golf, string, decision-problem, syntax
---


title: Undirect a Graph

text:
# Question
Title: Undirect a Graph
# Introduction

In this challenge, you are given a directed graph with self-loops, and your task is to convert it to an undirected graph without self-loops.

# Input

Your input is a directed graph with vertex set `{0, 1, ..., n-1}` for some natural number `n ≥ 0` (or `{1, 2, ..., n}` if you use 1-based indexing). The graph is given as a length-`n` list `L` where `L[i]` is a list of the out-neighbors of vertex `i`. For example, the list `[[0,1],[0],[1,0,3],[]]` represents the graph

```
.-.
| v
'-0<--2-->3
  ^   |
  |   |
  v   |
  1<--'

```

Note that the neighbor lists are not necessarily ordered, but they are guaranteed to be duplicate-free.

# Output

Your output is another graph in the same format as the input, obtained from it as follows.

1. Delete all self-loops.
2. For each remaining edge `u -> v`, add the reversed edge `v -> u` if it's not already present.

As with the input, the neighbor lists of the output graph may be unordered, but they cannot contain duplicates. For the above graph, a correct output would be `[[1,2],[0,2],[0,1,3],[2]]`, which represents the graph

```
0<->2<->3
^   ^
|   |
v   |
1<--'

```

# Rules

You can use 0-based or 1-based indexing in the graphs. Both functions and full programs are acceptable. The lowest byte count wins, and standard loopholes are disallowed.

# Test Cases

These test cases use 0-based indexing; increment each number in the 1-based case. These neighbor lists are sorted in ascending order, but it is not required.

```
[] -> []
[[0]] -> [[]]
[[],[0,1]] -> [[1],[0]]
[[0,1],[]] -> [[1],[0]]
[[0,1],[0],[1,0,3],[]] -> [[1,2],[0,2],[0,1,3],[2]]
[[3],[],[5],[3],[1,3],[4]] -> [[3],[4],[5],[0,4],[1,3,5],[2,4]]
[[0,1],[6],[],[3],[3],[1],[4,2]] -> [[1],[0,5,6],[6],[4],[3,6],[1],[1,2,4]]
[[6],[0,5,1],[5,4],[3,5],[4],[5,6],[0,3]] -> [[1,6],[0,5],[4,5],[5,6],[2],[1,2,3,6],[0,3,5]]
[[1,0],[5,1],[5],[1],[5,7],[7,1],[],[1]] -> [[1],[0,3,5,7],[5],[1],[5,7],[1,2,4,7],[],[1,4,5]]
[[2,8,0,9],[5,2,3,4],[0,2],[3,7,4],[8,1,2],[5,1,9,2],[6,9],[6,5,2,9,0],[9,1,2,0],[3,9]] -> [[2,7,8,9],[2,3,4,5,8],[0,1,4,5,7,8],[1,4,7,9],[1,2,3,8],[1,2,7,9],[7,9],[0,2,3,5,6,9],[0,1,2,4,9],[0,3,5,6,7,8]]

```

# Answer
> 5 votes
# Pyth, ~~17~~ 16 bytes

```
.e-.|f}k@QTUQbkQ

```

Try it online: Demonstration or Test Suite

### Explanation

```
                   implicit: Q = input
.e             Q   enumerated mapping of Q (k index, b out-neighbors):
     f     UQ         filter [0, 1, ..., len(Q)-1] for elements T, which satisfy:
      }k@QT              k in Q[T]
                      # this are the in-neighbors
   .|        b        setwise union with b
  -           k       remove k

```

# Answer
> 5 votes
# CJam, ~~43~~ ~~40~~ ~~35~~ ~~34~~ 33 bytes

*2 bytes saved by Sp3000.*

This started out as a really elegant solution and then grew increasingly hideous as I tried patching up some holes I overlooked. I'm not sure yet if the original idea is still salvageable, but I'll try my best...

```
q~_,,\ff{&W+0=)}_z..-{_,{;(},+}%`

```

Test it here. Alternatively, run the entire test harness.

I'll add an explanation once I'm sure the patient is dead.

# Answer
> 3 votes
# Python 2, 107 bytes

Still trying to figure out if I can golf this more, but for now, this is the best I can do.

```
def u(g):e=enumerate;o=[set(_)-{i}for i,_ in e(g)];[o[j].add(i)for i,_ in e(o)for j in _];print map(list,o)

```

I use sets to prevent duplicates; also, unlike `list.remove(i)`, `{S}-{i}` doesn't throw an error if `i` is not in `S`.

# Answer
> 3 votes
# Ruby, 78 bytes

Finally some use for ruby's set operators (`[1,2]&[2]==[2]` and `[3,4,5]-[4]==[3,5]`).

```
->k{n=k.size;n.times{|i|n.times{|j|(k[j]&[i])[0]&&k[i]=(k[i]<<j).uniq-[i]}};k}

```

ideone, including all test cases, which it passes.

# Answer
> 2 votes
# CJam, 26 bytes

```
l~_,,:T.-_T\ff&Tf.e&.|:e_p

```

Not very short...

### Explanation

```
l~                           e# Read the input.
  _,,:T                      e# Get the graph size and store in T.
       .-                    e# Remove self-loops from the original input.
         _T\ff&              e# Check if each vertex is in each list, and
                             e# return truthy if yes, or empty list if no.
               Tf.e&         e# Convert truthy to vertex numbers.
                    .|       e# Merge with the original graph.
                      :e_    e# Remove empty lists.
                         p   e# Format and print.

```

# Answer
> 1 votes
# JavaScript(ES6), 96 ~~110~~

Creating adjacency sets from adjacency list, that helps avoiding duplicates. Ad last it rebuilds the lists starting from the sets.

```
//Golfed
U=l=>
  l.map((m,n)=>m.map(a=>a-n?s[n][a]=s[a][n]=1:0),s=l.map(m=>[]))
  &&s.map(a=>[~~k for(k in a)])

// Ungolfed

undirect=(adList)=>(
  adSets=adList.map(_ => []),
  adList.forEach((curAdList,curNode)=>{
    curAdList.forEach(adNode=>{
      if (adNode!=curNode) {
        adSets[curNode][adNode]=1,
        adSets[adNode][curNode]=1
      }
    })
  }),
  adSets.map(adSet=>[~~k for(k in adSet)])
)

// Test
out=s=>OUT.innerHTML+=s+'\n'

test=[
 [ [], [] ]
,[ [[0]], [[]] ]
,[ [[],[0,1]] , [[1],[0]] ]
,[ [[0,1],[]] , [[1],[0]] ]

,[ [[0,1],[0],[1,0,3],[]] , [[1,2],[0,2],[0,1,3],[2]] ]
,[ [[3],[],[5],[3],[1,3],[4]] , [[3],[4],[5],[0,4],[1,3,5],[2,4]] ]
,[ [[0,1],[6],[],[3],[3],[1],[4,2]] , [[1],[0,5,6],[6],[4],[3,6],[1],[1,2,4]] ]
,[
   [[6],[0,5,1],[5,4],[3,5],[4],[5,6],[0,3]] ,
   [[1,6],[0,5],[4,5],[5,6],[2],[1,2,3,6],[0,3,5]]
 ]
,[
  [[1,0],[5,1],[5],[1],[5,7],[7,1],[],[1]] ,
  [[1],[0,3,5,7],[5],[1],[5,7],[1,2,4,7],[],[1,4,5]]
 ]

,[
  [[2,8,0,9],[5,2,3,4],[0,2],[3,7,4],[8,1,2],[5,1,9,2],[6,9],[6,5,2,9,0],[9,1,2,0],[3,9]] ,
  [[2,7,8,9],[2,3,4,5,8],[0,1,4,5,7,8],[1,4,7,9],[1,2,3,8],[1,2,7,9],[7,9],[0,2,3,5,6,9],  [0,1,2,4,9],[0,3,5,6,7,8]]
 ]
]

show=l=>'['+l.map(a=>'['+a+']').join(',')+']'

test.forEach(t => (
  r = U(t[0]),
  ck = show(r) == show(t[1]),
  out('Test ' + (ck ? 'OK: ':'FAIL: ') + show(t[0])+' -> ' +
      '\nResult: ' + show(r) +
      '\nCheck : ' + show(t[1]) + '\n\n')
) )
```

```
<pre id=OUT></pre>
```

# Answer
> 0 votes
# Java, 150

```
a->{int i=0,j,k=a.size();for(;i<k;a.get(i).remove((Object)i++))for(j=k;j-->0;)if(a.get(j).contains(i)&!a.get(i).contains(j))a.get(i).add(j);return a;}

```

Expanded, runnable code:

```
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.Function
public class C {
    static Function<List<List<Integer>>, List<List<Integer>>> f = a -> {
        int i = 0, j, k = a.size();
        for (; i < k; a.get(i).remove((Object) i++)) {
            for (j = k; j-- > 0;) {
                if (a.get(j).contains(i) & !a.get(i).contains(j)) {
                    a.get(i).add(j);
                }
            }
        }
        return a;
    };
    public static void main(String[] args) {
        System.out.println(f.apply(new ArrayList(Arrays.asList(
                new ArrayList(Arrays.asList(0, 1)),
                new ArrayList(Arrays.asList(1)),
                new ArrayList(Arrays.asList(1, 0, 3)),
                new ArrayList(Arrays.asList()))
        )));
    }
}

```

# Answer
> 0 votes
# Mathematica, ~~84~~ ~~66~~ 64 bytes

Using 1-based indexing.

```
MapIndexed[Union[#,First/@l~Position~Tr@#2]~Complement~#2&,l=#]&

```

# Answer
> 0 votes
# Groovy - 87

```
u={g->g.eachWithIndex{n,i->g[i]=n-i;g[i].each{g[it]<<i}};g.each{it=it.sort().unique()}}

```

Full script to run tests:

```
u={g->g.eachWithIndex{n,i->g[i]=n-i;g[i].each{g[it]<<i}};g.each{it=it.sort().unique()}}
assert u([]) == []
assert u([[0]]) == [[]]
assert u([[],[0,1]]) == [[1],[0]]
assert u([[0,1],[]]) == [[1],[0]]
assert u([[0,1],[0],[1,0,3],[]]) == [[1,2],[0,2],[0,1,3],[2]]
assert u([[3],[],[5],[3],[1,3],[4]]) == [[3],[4],[5],[0,4],[1,3,5],[2,4]]
assert u([[0,1],[6],[],[3],[3],[1],[4,2]]) == [[1],[0,5,6],[6],[4],[3,6],[1],[1,2,4]]
assert u([[6],[0,5,1],[5,4],[3,5],[4],[5,6],[0,3]]) == [[1,6],[0,5],[4,5],[5,6],[2],[1,2,3,6],[0,3,5]]
assert u([[1,0],[5,1],[5],[1],[5,7],[7,1],[],[1]]) == [[1],[0,3,5,7],[5],[1],[5,7],[1,2,4,7],[],[1,4,5]]
assert u([[2,8,0,9],[5,2,3,4],[0,2],[3,7,4],[8,1,2],[5,1,9,2],[6,9],[6,5,2,9,0],[9,1,2,0],[3,9]]) == [[2,7,8,9],[2,3,4,5,8],[0,1,4,5,7,8],[1,4,7,9],[1,2,3,8],[1,2,7,9],[7,9],[0,2,3,5,6,9],[0,1,2,4,9],[0,3,5,6,7,8]]

```

# Answer
> 0 votes
# Python 3, 127 bytes

```
l=list;g=l(map(set,eval(input())))
for i in range(len(g)):
    for j in g[i]:g[j]=g[j]^g[j]&{j}|{i}
print(l(map(l,g)))

```

Try online

Not my best attempt...

---
Tags: code-golf, array, graph-theory
---