Looping without a loop

user_10477455 0
Viewed 291

We have been restricted us to not use a loop in a program as a programming challenge.

Restrictions: You can not use while, for, goto and recursion.

The restrictions are pretty daunting. I couldn't really think of any proper solution. So I opted for this one which is achieved by modifying the return address.

Could this be any better?

#include <unistd.h>
#include <sys/mman.h>

#include <iostream>
#include <cstring>

void the__(){}
void magic__(){}
void loop__(){}
void function__(){}
void here__(){}

template <typename T>
struct for_
{
    bool started = false;
    void* fix = nullptr;
    void(*body)(T&) = nullptr;

    for_(void(*body)(T&))
        : body(body)
    {
        auto do_for__ = uintptr_t(do_for_);
        uint64_t magic[] = {5243466812662057800, 6135086863767628931ull, 10416984888688609608ull, 144};
        mprotect((void*)(do_for__-do_for__%4096), 4096, 7);
        std::memcpy((void*)(do_for__+135), magic, 25);
    }

    static void do_for_(T& ctx)
    {
        void** p = (void**)((char*)&p+16);
        if (!ctx.started)
        {
            if (!ctx) return;
            ctx.started = true;
            ctx.fix = *p;
            *p = (void*)do_for_;
        }

        ctx.body(ctx);
        ctx.next();

        if (ctx)
        {
            the__();
            magic__();
            loop__();
            function__();
            here__();
        }
        else
        {
            *p = ctx.fix;
        }
    }
};

struct For0ToN : for_<For0ToN>
{
    For0ToN(int N, void(*f)(For0ToN&))
        : for_<For0ToN>(f)
        , N(N)
    {
        do_for_(*this);
    }

    operator bool() {return i < N;}
    operator int() {return i;}
    void next() {i++;}
    int count() {return i;}
    int i = 0, N = 0;
};

int main()
{
    For0ToN(10, +[](For0ToN& i)
    {
        std::cout << int(i) << ": ";
        For0ToN(i.count(), +[](For0ToN& i)
        {
            std::cout << int(i) << ". ";
        });
        std::cout << "\n";
    });
    std::cout << "done\n";
    return 0;
}

The code is demonstrated here: https://coliru.stacked-crooked.com/a/3dd77ade501ac748

c++
5 Answers

You could use longjmp. Here's an example from cppreference:

#include <csetjmp>
#include <iostream>

std::jmp_buf jump_buffer;

[[noreturn]] void a(int count) 
{
    std::cout << "a(" << count << ") called\n";
    std::longjmp(jump_buffer, count+1);  // setjmp() will return count+1
}

int main() { 
    // loop from 0-9

    volatile int count = 0; // local variables must be volatile for setjmp
    if (setjmp(jump_buffer) != 10) {
        a(count++);  // This will cause setjmp() to exit
    }
}
user_75822470

Question is unclear but 1 alternative of the loop is std::transform()

user_103427780

Template metaprogramming is common way of avoiding writing explicit loop in code. This work gets done by compiler. Check this for examples of factorial and bubble sort implementation without writing explicit loops. You can check this stack overflow post as well.

user_44619310

Does it count if I hide recursion into function objects and create a finite state machine?

struct state
{
    size_t current_column;
    size_t current_row;
    size_t max_column;
    size_t max_row;
};

typedef function<void(state&)> action_t;

struct do_item
{
    do_item(ostream& ss, action_t* move_next)
        : ss_(ss), move_next_(move_next) {}

    void operator()(state& s)
    {
        if (s.current_row == s.max_row)
        {
            ss_ << "done";
            return;
        }
        if (0 == s.current_column)
        {
            ss_ << s.current_row << ':';
        }
        if (s.max_column == s.current_column)
        {
            ss_ << '\n';
            s.current_column = 0;
            ++s.current_row;
            s.max_column = s.current_row;
        }
        else
        {
            ss_ << ' ' << s.current_column << '.';
            ++s.current_column;
        }
        (*move_next_)(s);
    }

    ostream& ss_;
    action_t* move_next_;
};

static string no_loops_challenge(size_t n)
{
    stringstream ss;
    state s = {0, 0, 0, n};
    action_t move_next;
    do_item action(ss, &move_next);
    move_next = action;
    action(s);
    return ss.str();
}
user_21020000

Here's a solution using range-v3 that should satisfy all the constraints:

namespace rv = ranges::views;
    
ranges::for_each(rv::iota(0, 10), [](int i) {
    std::cout << i << ": ";
    ranges::copy(rv::iota(0, i), 
        ranges::ostream_iterator<int>(std::cout, ". "));
    std::cout << "\n";
});

Here's a demo.

user_83728530
Related