110 - Meta-Loopless Sorts

[aram90]

Yeah, it worked!
Tarasich

[eugeneyche]

I've been working on this problem for some time, and I compared line for line for someone's post of 1 - 4 cases.

Can someone help me figure out what's wrong with my algorithm?

Code: Select all

#include <iostream>
#include <algorithm>
using namespace std;

int n;
char vars [8];

void tab(int n);
void insert_var(int i);

int main() {
    bool first = true;
    while (cin >> n) {
        if (!first) { cout << endl; }
        cout << "program sort(input,output);" << endl; 
        cout << "var" << endl;
        for (int i = 0; i < n; i++) {
            if (i > 0) {
                cout << ",";
            }
            vars[i] = 'a' + i;
            cout << vars[i];
        }
        cout << " : integer;" << endl;
        cout << "begin" << endl;
        tab(1);
        cout << "readln(";
        for (int i = 0; i < n; i++) {
            if (i > 0) {
                cout << ",";
            }
            cout << vars[i];
        }
        cout << ");" << endl;
        insert_var(1);
        cout << "end." << endl;
        first = false;
    }
}

void tab(int n) {
    for (int i = 0; i < n; i++) {
        cout << "  ";
    }
}

void insert_var(int i) {
    if (i == n) {
        tab(i);
        cout << "writeln(";
        for (int i = 0; i < n; i++) {
            if (i > 0) cout << ",";
            cout << vars[i];
        }
        cout << ")" << endl;
        return;
    }
    for (int j = i; j > 0; j--) {
        tab(i);
        if (j < i) {
            cout << "else ";
        }
        if (j > 0) { 
            cout << "if " << vars[j - 1] << " < " << vars[j] << " then" << endl;
        }
        int tmp_vars [n];
        copy(vars, vars + n, tmp_vars);
        insert_var(i + 1);
        copy(tmp_vars, tmp_vars + n, vars);
        int tmp = vars[j];
        vars[j] = vars[j - 1];
        vars[j - 1] = tmp;
    }
    tab(i);
    cout << "else" << endl;
    insert_var(i + 1);
}

Input

Code: Select all

1

2

3

4

Output

Code: Select all

program sort(input,output);
var
a : integer;
begin
  readln(a);
  writeln(a)
end.

program sort(input,output);
var
a,b : integer;
begin
  readln(a,b);
  if a < b then
    writeln(a,b)
  else
    writeln(b,a)
end.

program sort(input,output);
var
a,b,c : integer;
begin
  readln(a,b,c);
  if a < b then
    if b < c then
      writeln(a,b,c)
    else if a < c then
      writeln(a,c,b)
    else
      writeln(c,a,b)
  else
    if a < c then
      writeln(b,a,c)
    else if b < c then
      writeln(b,c,a)
    else
      writeln(c,b,a)
end.

program sort(input,output);
var
a,b,c,d : integer;
begin
  readln(a,b,c,d);
  if a < b then
    if b < c then
      if c < d then
        writeln(a,b,c,d)
      else if b < d then
        writeln(a,b,d,c)
      else if a < d then
        writeln(a,d,b,c)
      else
        writeln(d,a,b,c)
    else if a < c then
      if b < d then
        writeln(a,c,b,d)
      else if c < d then
        writeln(a,c,d,b)
      else if a < d then
        writeln(a,d,c,b)
      else
        writeln(d,a,c,b)
    else
      if b < d then
        writeln(c,a,b,d)
      else if a < d then
        writeln(c,a,d,b)
      else if c < d then
        writeln(c,d,a,b)
      else
        writeln(d,c,a,b)
  else
    if a < c then
      if c < d then
        writeln(b,a,c,d)
      else if a < d then
        writeln(b,a,d,c)
      else if b < d then
        writeln(b,d,a,c)
      else
        writeln(d,b,a,c)
    else if b < c then
      if a < d then
        writeln(b,c,a,d)
      else if c < d then
        writeln(b,c,d,a)
      else if b < d then
        writeln(b,d,c,a)
      else
        writeln(d,b,c,a)
    else
      if a < d then
        writeln(c,b,a,d)
      else if b < d then
        writeln(c,b,d,a)
      else if c < d then
        writeln(c,d,b,a)
      else
        writeln(d,c,b,a)
end.

Additionally, my n=8 case does not compile with FPC, with the following output:

Code: Select all

code.pas(3914,17) Fatal: Procedure too complex, it requires too many registers
Fatal: Compilation aborted
Error: /usr/bin/ppcx64 returned an error exitcode (normal if you did not specify a source file to be compiled)

But I don't think that's a problem with the algorithm.

[brianfry713]

Check out http://www.uvatoolkit.com/problemssolve.php