Why isn't it ending? [closed]

Question

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 1

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.

Answer 2

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).

Answer 3

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.

Answer 4

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'.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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".

Answer 9

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

Answer 10

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+.

Answer 11

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.

Answer 12

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.

Answer 13

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

Answer 14

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 ;-)

Answer 15

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.

Answer 16

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.

Answer 17

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 ints 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.

Answer 18

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.

Answer 19

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.

Answer 20

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.

Answer 21

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;
}

Answer 22

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

Answer 23

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.

Answer 24

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.

Answer 25

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.

Answer 26

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(2^n/2). While the program might not run indefinitely, it'd probably outlive both living and non-living objects around and not-so-around.

Answer 27

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.

Answer 28

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.

Answer 29

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”.)

Answer 30

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 a (U+0061) while the other uses а (U+0430)