Quine Solution

//
//  main.m
//  Quine
//

#import <Foundation/Foundation.h>

BOOL allowUndefinedRepeatBehavior = NO;
BOOL allowRepeatToCycleAndPrintItself = NO;

typedef enum : NSUInteger {
    PRINT,
    REPEAT,
} PrintOrRepeat;

@interface Line : NSObject
@property (readwrite,assign) PrintOrRepeat printOrRepeat;
@property (readwrite,assign) int arg1;
@property (readwrite,assign) int arg2;
@end

@interface ExecutionState : NSObject
@property (readwrite,assign) int totalNumberOfLines;
@property (readwrite,retain) NSMutableArray* lines;
@property (readwrite,retain) NSMutableArray* outputAlreadyWritten;
@property (readwrite, assign) int currentIndexOfExecution;
@property (readwrite, assign) BOOL isPrinting;
@property (readwrite, assign) int ifIsPrintingPrintUntilWhatLine;
@end



@implementation Line

-(NSString*) description {
    if (self.printOrRepeat == PRINT) {
        return [NSString stringWithFormat:@"PRINT %d", self.arg1];
    } else {
        return [NSString stringWithFormat:@"REPEAT %d %d", self.arg1, self.arg2];
    }
}
+(Line*) lineZero {
    Line* r = [[Line alloc] init];
    r.printOrRepeat = PRINT;
    r.arg1 = 0;
    r.arg2 = 0;
    return r;
}
-(Line*) nextLineLineIndex:(int)x ofTotal:(NSUInteger) y carry:(BOOL*) carry {
    *carry = NO;
    Line* r = [[Line alloc] init];
    r.printOrRepeat = self.printOrRepeat;
    r.arg1 = self.arg1;
    r.arg2 = self.arg2;
    if (r.printOrRepeat == PRINT) {
        r.arg1 = r.arg1+1;
        if (r.arg1 > y /*- x - 1*/) {
            r.printOrRepeat = REPEAT;
            r.arg1 = 0;
            r.arg2 = 0;
        }
    } else {
        r.arg1 = r.arg1 + 1;
        if (r.arg1 > y) {
            r.arg1 = 0;
            r.arg2 = r.arg2 + 1;
            if (r.arg2 > y) {
                *carry = YES;
                return [Line lineZero];
            }
        }
    }
    return r;
}
-(BOOL) equals:(Line*) rhs {
    if (self.printOrRepeat != rhs.printOrRepeat) {
        return NO;
    }
    if (self.printOrRepeat == PRINT) {
        return self.arg1 == rhs.arg1;
    } else {
        return self.arg1 == rhs.arg1 && self.arg2 == rhs.arg2;
    }

}

@end

@implementation ExecutionState

+(ExecutionState*) freshExecutionStateOfScriptLength:(int) length {
    ExecutionState* es = [[ExecutionState alloc] init];
    es.totalNumberOfLines = length;
    es.lines = [NSMutableArray array];
    es.outputAlreadyWritten = [NSMutableArray array];
    es.currentIndexOfExecution = 0;
    es.isPrinting = NO;
    es.ifIsPrintingPrintUntilWhatLine = 0;
    return es;
}
-(ExecutionState*) copy {
    ExecutionState* es = [[ExecutionState alloc] init];
    es.totalNumberOfLines = self.totalNumberOfLines;
    es.lines = [NSMutableArray arrayWithArray:self.lines];
    es.outputAlreadyWritten = [NSMutableArray arrayWithArray:self.outputAlreadyWritten];
    es.currentIndexOfExecution = self.currentIndexOfExecution;
    es.isPrinting = self.isPrinting;
    es.ifIsPrintingPrintUntilWhatLine = self.ifIsPrintingPrintUntilWhatLine;
    return es;
}
-(BOOL) cannotBecomeQuine {
    if (self.outputAlreadyWritten.count > self.totalNumberOfLines) {
        return YES;
    }
    for (int i = 0; i < self.lines.count && i<self.outputAlreadyWritten.count; i++) {
        if (![[self.lines objectAtIndex:i] equals:[self.outputAlreadyWritten objectAtIndex:i]]) {
            return YES;
        }
    }
    return NO;
}
-(BOOL) applyLine:(Line*) line {

    [self.lines addObject:line];
    int currentLineNumber = (int)self.lines.count-1;
    if (self.isPrinting) {
        [self.outputAlreadyWritten addObject:line];
        self.isPrinting = self.ifIsPrintingPrintUntilWhatLine > currentLineNumber;

    } else {
        if (line.printOrRepeat == PRINT) {
            if (line.arg1 == 0) {

            } else {
                self.isPrinting = YES;
                self.ifIsPrintingPrintUntilWhatLine = currentLineNumber + line.arg1;
            }

        } else {
            int firstOutputLineToPrint = (int)self.outputAlreadyWritten.count - line.arg2;
            int lastOutputLineToPrint = firstOutputLineToPrint + line.arg1 - 1;
            if (!allowRepeatToCycleAndPrintItself && lastOutputLineToPrint >= self.outputAlreadyWritten.count) {
                return YES;
            }
            if (firstOutputLineToPrint < 0) {
                if (allowUndefinedRepeatBehavior) {
                    return NO;
                } else {
                    return YES;
                }

            }
            for (int i =firstOutputLineToPrint; i<=lastOutputLineToPrint; i++) {
                [self.outputAlreadyWritten addObject:[self.outputAlreadyWritten objectAtIndex:i]];
            }

        }
    }
    return NO;
}
-(ExecutionState*) quineFromInitialSegmentWithCommand:(Line*) line {
    ExecutionState* es = [self copy];
    BOOL error = [es applyLine:line];
    if (error) {
        return nil;
    }
    if ([es cannotBecomeQuine]) {
        return nil;
    }
    return [es quineFromInitialSegment];
}
-(BOOL) isOutputEqualToInput {
    if (self.outputAlreadyWritten.count != self.lines.count) {
        return NO;
    }
    for (int i = 0; i<self.lines.count; i++) {
        if (![(Line*)([self.outputAlreadyWritten objectAtIndex:i]) equals: (Line*)([self.lines objectAtIndex:i])]) {
            return NO;
        }
    }
    return YES;
}
-(ExecutionState*) quineFromInitialSegment {

    if (self.lines.count == self.totalNumberOfLines) {
        if (!self.isPrinting && [self isOutputEqualToInput]) {
            NSLog(@"%@\n\n",self);
            return nil;
        } else {
            return nil;
        }
    }

    if (self.isPrinting && self.outputAlreadyWritten.count > self.lines.count) {
        Line* nextCommand = [self.outputAlreadyWritten objectAtIndex:self.lines.count];
        return [self quineFromInitialSegmentWithCommand:nextCommand];
    }
    if (self.isPrinting && self.outputAlreadyWritten.count < self.lines.count) {
        Line* nextCommand = [self.lines objectAtIndexedSubscript:self.outputAlreadyWritten.count];
        return [self quineFromInitialSegmentWithCommand:nextCommand];
    }

    int indexOfNextCommand = (int)self.lines.count;
    int minimumPrintArg1 = 0;
    int maximumPrintArg1 = MIN(self.totalNumberOfLines - indexOfNextCommand - 1, self.totalNumberOfLines -  (int)self.outputAlreadyWritten.count);
    if (self.isPrinting) {
        maximumPrintArg1 = self.totalNumberOfLines;
    }
    for (int arg1 = minimumPrintArg1; arg1 <= maximumPrintArg1; arg1++) {
        Line* nextCommand = [[Line alloc] init];
        nextCommand.printOrRepeat = PRINT;
        nextCommand.arg1 = arg1;
        ExecutionState* es = [self quineFromInitialSegmentWithCommand:nextCommand];
        if (es) {
            return es;
        }
    }
    int minimumRepeatArg1 = 0;
    int maxumumRepeatArg1 = self.totalNumberOfLines -  (int)self.outputAlreadyWritten.count ;
    if (self.isPrinting) {
        maxumumRepeatArg1 = self.totalNumberOfLines;
    }
    for (int arg1 = minimumRepeatArg1; arg1 <= maxumumRepeatArg1; arg1++) {
        int minimumRepeatArg2;
        int maximumRepeatArg2;
        if (self.isPrinting) {
            maximumRepeatArg2 = self.totalNumberOfLines;
            minimumRepeatArg2 = 1;
        } else {
            minimumRepeatArg2 = 1;
            if (allowUndefinedRepeatBehavior) {
                maximumRepeatArg2 = self.totalNumberOfLines -  (int)self.outputAlreadyWritten.count;
            } else {
                maximumRepeatArg2 = self.totalNumberOfLines;
            }
        }


        for(int arg2 = minimumRepeatArg2; arg2 <= maximumRepeatArg2; arg2++) {
            Line* nextCommand = [[Line alloc] init];
            nextCommand.printOrRepeat = REPEAT;
            nextCommand.arg1 = arg1;
            nextCommand.arg2 = arg2;
            ExecutionState* es = [self quineFromInitialSegmentWithCommand:nextCommand];
            if (es) {
                return es;
            }
        }
    }
    return nil;
}




+(ExecutionState*) quineOfLength:(int) length {
    NSLog(@"Checking quines of length %d",length);
    ExecutionState* s = [ExecutionState freshExecutionStateOfScriptLength:length];
    return [s quineFromInitialSegment];
}
+(ExecutionState*) iterateQuineLength {
    int length = 1;
    while (YES) {
        ExecutionState* s = [ExecutionState quineOfLength:length];
        if (s) {
            return s;
        }
        length++;

    }
}
-(NSString*) description {

    NSMutableString* o = [NSMutableString stringWithFormat:@"Script of length %d:\n",(int)self.totalNumberOfLines];
    for (int i = 0; i< self.lines.count; i++) {
        [o appendString:[[self.lines objectAtIndex:i] description]];
        [o appendString:@"\n"];
    }


    return o;
}
@end


int main(int argc, const char * argv[]) {
    @autoreleasepool {

        [ExecutionState iterateQuineLength];
    }
    return 0;
}