zzun.net

프로그래밍 언어 / 2003년 1학기 / 한상영 교수님

[입력파일 예시]
A := B + C
B := 3
C := 5
PRINT D
PRINT A
B := 8
PRINT A
RESET
PRINT A

[calculator.scm]
(define inport (open-input-file "calculator.in"))
(define outport (open-output-file "calculator.out"))

(define a ''undef) (define a-rec 0)
(define b ''undef) (define b-rec 0)
(define c ''undef) (define c-rec 0)
(define d ''undef) (define d-rec 0)
(define e ''undef) (define e-rec 0)
(define env (the-environment))

(define adjust (lambda (x)
       (let ((next (read x)))
               (if (eof-object? next) '()
                       (if (list? next) (cons next (adjust x))
                               (if (eqv? next '+) (cons '+ (adjust x))
                                       (if (eqv? next '-) (cons '- (adjust x))
                                               (if (eqv? next '*) (cons '* (adjust x))
                                                       (cons next (adjust x))))))))))

(define zzun-eval (lambda (x)
       (if (list? x)
               (if (> (length x) 4)
                       (if (eqv? (fourth x) '*)
                               (zzun-eval (cons (first x) (cons (second x) (cons (list (third x) (fourth x) (fifth x)) (list-tail x 5)))))
                               (zzun-eval (cons (zzun-eval (list-head x 3)) (list-tail x 3))))
                       (if (= (length x) 4)
                               (zzun-eval (list (first x) (second x) (list (third x) (fourth x))))
                               (if (= (length x) 3)
                                       (let
                                               ((fff (zzun-eval (first x))) (ttt (zzun-eval (third x))))
                                               (if (or (eqv? fff 'undef) (eqv? ttt 'undef))
                                                       'undef
                                                       (apply (eval (second x) ()) (list fff ttt))))
                                       (if (= (length x) 2)
                                               (eval x env)
                                               (if (= (length x) 1)
                                                       (zzun-eval (first x)))))))
               (if (symbol? x)
                       (if        (or
                                       (and (eqv? x 'a) (= a-rec 1))
                                       (and (eqv? x 'b) (= b-rec 1))
                                       (and (eqv? x 'c) (= c-rec 1))
                                       (and (eqv? x 'd) (= d-rec 1))
                                       (and (eqv? x 'e) (= e-rec 1))
                               ) 'undef
                               (begin        
                                       (if (eqv? x 'a)
                                               (set! a-rec 1)
                                               (if (eqv? x 'b)
                                                       (set! b-rec 1)
                                                       (if (eqv? x 'c)
                                                               (set! c-rec 1)
                                                               (if (eqv? x 'd)
                                                                       (set! d-rec 1)
                                                                       (if (eqv? e 'a)
                                                                               (set! e-rec 1))))))
                                       (zzun-eval (eval x env))))                                
                       x))))

(let loop ((cur-token (read inport)))
       (if (eof-object? cur-token) #f
               (begin
                       (if (eqv? cur-token 'PRINT)
                               (begin
                                       (display (zzun-eval (read inport)) outport)
                                       (set! a-rec 0) (set! b-rec 0) (set! c-rec 0) (set! d-rec 0) (set! e-rec 0)
                                       (display #\newline outport)))
                       (if (eqv? cur-token 'RESET)
                               (begin
                                       (set! a ''undef)
                                       (set! b ''undef)
                                       (set! c ''undef)
                                       (set! d ''undef)
                                       (set! e ''undef)))
                       (if (eqv? cur-token 'a)
                               (if (eqv? ':= (read inport))
                                       (begin
                                               (read-char inport)
                                               (set! a (adjust (string->input-port (read-line inport)))))))
                       (if (eqv? cur-token 'b)
                               (if (eqv? ':= (read inport))
                                       (begin
                                               (read-char inport)
                                               (set! b (adjust (string->input-port (read-line inport)))))))
                       (if (eqv? cur-token 'c)
                               (if (eqv? ':= (read inport))
                                       (begin
                                               (read-char inport)
                                               (set! c (adjust (string->input-port (read-line inport)))))))
                       (if (eqv? cur-token 'd)
                               (if (eqv? ':= (read inport))
                                       (begin
                                               (read-char inport)
                                               (set! d (adjust (string->input-port (read-line inport)))))))
                       (if (eqv? cur-token 'e)
                               (if (eqv? ':= (read inport))
                                       (begin
                                               (read-char inport)
                                               (set! e (adjust (string->input-port (read-line inport)))))))
                       (loop (read inport)))))

(close-output-port outport)
(close-input-port inport)

'IT > 소스코드' 카테고리의 다른 글

[C] fork(), exec(), and wait()  (0) 2003.10.16
[C] Binary Search Tree  (0) 2003.10.11
[MIT Scheme] Calculator  (0) 2003.07.10
[Java] Soma Cube  (0) 2003.07.10
[C++] 3-dimension 63-Puzzle  (1) 2003.07.10
[C++] Booth's Algorithm Simulator  (0) 2003.07.10

Comment +0

프로그래밍 언어 / 2003년 1학기 / 한상영 교수님

[설명]
임의의 블럭들의 모양을 입력으로 받은 다음
그 블럭들을 이용해 3*3*3의 큐브를 만들 수 있는
distinct한 모든 해를 구하는 프로그램.
Soma Cube라고 널리 알려진 문제.

[cube.java]
/************************************************************ http://zzun.net ******************************************************/

import java.io.*;

class Piece                                                                // a class of each piece
{
       public Piece(char s)
       {
               ptn = new int[2][27*24/2];                // patterns will save here
               symbol = s;                                                // symbol of pattern
               count = new int[2];                                                // # of patterns (two groups)
       }

       public void setBase(int base)                        // setting the base pattern
       {
               String temp = "";
               for (int i=0; i<27; i++)
                       if ( ((base >> i) % 2) == 1 )        // determine the piece's shape
                       {
                               temp += (char)i;
                               size++;
                       }
               
               basePtn = new int[size][3];
               for (int i=0; i<size; i++)
               {
                       basePtn[i][0] = temp.charAt(i)%3 - temp.charAt(0)%3;                        // saving the base pattern as if it starts at first cell
                       basePtn[i][2] = temp.charAt(i)/9 - temp.charAt(0)/9;
                       basePtn[i][1] = (temp.charAt(i) - basePtn[i][2]*9) / 3 - (temp.charAt(0) - basePtn[0][2]*9) / 3;
               }
       }

       private void push(int type, int s)                        // add a pattern by type
       {
               ptn[type][count[type]] = s;
               count[type]++;                                                // act like stack
       }

       public void generate(int i)                        // generate i-th pattern
       {
               int[][] next = rotate(i);                // read a rotated pattern
               int[] xyz = new int[3];
               int pushing;

               for (int j=0; j<27; j++)                // through all positions in cube
               {
                       pushing = 0;

                       xyz[0] = j % 3;
                       xyz[2] = j / 9;
                       xyz[1] = (j - xyz[2]*9) / 3;        // calculate coordinates

                       int[] temp = new int[3];
                       int newCoord;

                       big:
                       for (int k=0; k<size; k++)
                       {
                               for (int l=0; l<3; l++)
                               {
                                       newCoord = next[k][l] + xyz[l];                // moving the rotated piece
                                       if (newCoord < 0 || newCoord > 2)                // if rotated piece has illegal cube, then break, try another position
                                       {
                                               pushing = 0;
                                               break big;
                                       }
                                       else
                                                temp[l] = (char)newCoord;
                               }
                               pushing |= (1 << (temp[0] + temp[1]*3 + temp[2]*9));                // save the current rotated pattern
                       }

                       boolean exist = false;                // already exist
                       if (pushing != 0)                        // legal rotating
                       {
                               int type = (pushing>>13)%2;                                        // if a ptn have cube no.13 TYPE 1, if not TYPE 0. every ptn is distinguishable by this rule.
                               for (int k=count[type]-1; k>=0; k--)
                                       if (ptn[type][k] == pushing)                        // check whether the same pattern exists already or not
                                               exist = true;
                               if (!exist)
                                       push(type, pushing);                                                        // if the pattern is unique, push it.
                       }
               }

               return;
       }

       private int[][] rotate(int idx)                                        // return a rotated piece (=pattern) by idx
       {
               int[][] rtn = new int[size][3];

               for (int i=0; i<size; i++)
                       for (int j=0; j<3; j++)
                               rtn[i][Math.abs(rotate[idx][j])-1] = basePtn[i][j] * ((rotate[idx][j] > 0) ? 1 : (-1));        // now rotating

               return rtn;
       }

       public int size = 0;
       public char symbol;
       public int count[];
       public int[][] ptn;                                // possible patterns
       private int[][] basePtn;                // base pattern
       private static int[][] rotate = { {1,2,3}, {1,-2,-3}, {1,3,-2}, {1,-3,2}, {-1,2,-3}, {-1,-2,3}, {-1,3,2}, {-1,-3,-2},
                                                                         {2,1,-3}, {2,-1,3}, {2,3,1}, {2,-3,-1}, {-2,1,3}, {-2,-1,-3}, {-2,3,-1}, {-2,-3,1},
                                                                         {3,1,2}, {3,-1,-2}, {3,2,-1}, {3,-2,1}, {-3,1,-2}, {-3,-1,2}, {-3,2,1}, {-3,-2,-1}
                                                                       };                // the rotating patterns {3,-2,1} means x->z, y->-y, z->x
}

public class cube
{
       public static String inputFileName;
       public static String outputFileName = "cube.out";
       public static Piece[] p;
       public static int[] answer;
       public static int status = 0;
       public static BufferedReader fin;                        // input stream
       public static PrintWriter fout;                                // output stream
       public static boolean typeCheck;

       public static void initialize() throws IOException                        // initialize for a search
       {
               String buffer;
               int pos;
               char sym;
               for (int i=0; i<p.length; i++)
               {
                       buffer = fin.readLine();
                       sym = buffer.charAt(0);                                // check the symbol of the piece
                       p[i] = new Piece(sym);                                // make an object presenting the piece

                       pos = 0;                                                        // initial pattern
                       for (int j=0; j<27; j++)
                               if (buffer.charAt(j+2) == sym)
                                       pos |= (1 << j);
                       p[i].setBase(pos);                                                // set a base pattern

                       if (i==0)
                               p[i].generate(0);                        // if it is the first piece
                       else                                                        // otherwise
                               for (int j=0; j<24; j++)
                                       p[i].generate(j);
               }

               return;
       }

       public static void search(int type, int idx) throws IOException
       {
               int temp;
               
               for (int i=0; i<p[idx].count[type]; i++)
               {
                       temp = p[idx].ptn[type][i];                                                                // get a pattern of current piece

                       if ((status & temp) == 0)
                       {
                               status |= temp;
                               answer[idx] = temp;

                               if (idx == p.length - 1)                                                        // if the pushed piece is the last piece
                                       prodAns();                                                                                // We Find One! Produce the Answer!
                               else
                               {
                                       if (typeCheck)                                                                        // if any above piece has the 13-cube,
                                               search(0, idx+1);                                                        // find next piece in type 0
                                       else                                                                                        // if not
                                       {
                                               typeCheck = true;                                                        // set typeCheck
                                               search(1, idx+1);                                                        // find next piece in type 1
                                               typeCheck = false;                                                        // unset
                                               search(0, idx+1);                                                        // and find remaining in type 0
                                       }
                               }

                               status &= ~temp;                                // unpush the piece
                       }
               }
               
               return;
       }

       private static void prodAns() throws IOException                        // output the answer
       {
               char[] out = new char[27];
               for (int i=0; i<27; i++)
                       for (int j=0; j<p.length; j++)
                               if ( ((answer[j] >> i) % 2) == 1 )
                               {
                                       out[i] = p[j].symbol;
                                       break;
                               }

               fout.println(out);
       }

       public static void main(String[] args) throws IOException
       {
               if (args.length!=1 || args[0] == null)
               {
                       System.out.println("ERROR : please enter the input file name as an argument");
                       System.exit(0);
               }
               else
                       inputFileName = args[0];
               fin = new BufferedReader(new FileReader(inputFileName));
               int number = Integer.parseInt(fin.readLine());                                // # of pieces
               p = new Piece[number];
               answer = new int[number];
               System.out.println("Initializing...");
               initialize();
               fin.close();

               fout = new PrintWriter(new FileOutputStream(outputFileName));
               System.out.println("Searching...");
               typeCheck = true;
               search(1, 0);                                                // find as the first piece in type 1
               typeCheck = false;
               search(0, 0);                                                // in type 2
               
               fout.close();

               System.out.println("Finished!");
               return;
       }
}

'IT > 소스코드' 카테고리의 다른 글

[C] Binary Search Tree  (0) 2003.10.11
[MIT Scheme] Calculator  (0) 2003.07.10
[Java] Soma Cube  (0) 2003.07.10
[C++] 3-dimension 63-Puzzle  (1) 2003.07.10
[C++] Booth's Algorithm Simulator  (0) 2003.07.10
[MIPS Assembly] MAXMIN  (0) 2003.07.10

Comment +0

프로그래밍 언어 / 2003년 1학기 / 한상영 교수님

[설명]
2차원에서의 15-puzzle을 3차원으로 확장한 개념.
임의의 퍼즐 배치를 입력으로 받아
Optimal Solution(최소move)을 구함.
Cell을 움직이거나, 움직임의 sequence를 입력받아 움직일 수 있음.

[puzzle.cpp]
#include <iostream.h>
#include <fstream.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#define WIDTH 4

short CELL[WIDTH][WIDTH][WIDTH];
short* CELL_S = &(CELL[0][0][0]);                // the 1-dimension alias of the 3-dimension array CELL
short MD[WIDTH*WIDTH*WIDTH][WIDTH*WIDTH*WIDTH];                        // save All possible MD values.
short ANS[1000] = {0};                                        // the optimal solution of minimum moving sequence
int bound;

bool read_input(char* filename)                        // at first, load input file (ex. from puzzle.in)
{
       ifstream in (filename);
       
       char buf;
       int current_cell = 0;
       int counter = 0;

       while (in.get(buf))
       {
               if (buf>='0' && buf<='9')
               {
                       current_cell = current_cell*10 + (buf - '0');
               }
               else if (buf == '$')
                       current_cell = 64;
               else
               {
                       if (current_cell > 64)
                       {
                               cout << "ERROR : Wrong input file." << endl;
                               return false;
                       }
                       else if (current_cell > 0)
                       {
                               CELL_S[counter] = current_cell;                        // save it in to the array
                               counter++;
                               current_cell = 0;
                       }
               }                                
       }

       in.close();

       int inv_count = 0;                        // Check whether this problem can be solved or not

       for (int i=1; i<WIDTH*WIDTH*WIDTH; i++)
       {
               if (CELL_S[i-1]>CELL_S[i])
                       inv_count++;
       }

       if (inv_count%2 == 0)
       {
               cout << "Impossible to solve!" << endl;
               return false;
       }

       return true;
}

void set_md()                                // compute Manhattan Distance of all possible pair of cells
{
       int i_x, i_y, i_z, j_x, j_y, j_z;

   for (int i=0; i<WIDTH*WIDTH*WIDTH; i++)
       {
               i_x = i % WIDTH;
               i_z = i / (WIDTH*WIDTH);
               i_y = (i - i_z*WIDTH*WIDTH) / WIDTH;
               for (int j=0; j<WIDTH*WIDTH*WIDTH; j++)
               {
                       j_x = j % WIDTH;
                       j_z = j / (WIDTH*WIDTH);
                       j_y = (j - j_z*WIDTH*WIDTH) / WIDTH;
                       
                       MD[i][j] = abs(i_x - j_x) + abs(i_y - j_y) + abs(i_z - j_z);                // |x1-x2| + |y1-y2| + |z1-z2|
               }
       }

       return;
}

int cur_MD()                                // return current sum of MDs
{
       int md = 0;

       for (int i=0; i<WIDTH*WIDTH*WIDTH; i++)
       {
               if (CELL_S[i] == 64)
                       continue;
               md += MD[i][CELL_S[i]-1];
       }

       return md;
}

bool move_to(int dir)                // move to dir
{
       int x, y, z, idx;                                // find the empty cell
       for (idx=0; idx<WIDTH*WIDTH*WIDTH; idx++)
               if (CELL_S[idx]==64) break;
       x = idx % WIDTH;
       z = idx / (WIDTH*WIDTH);
       y = (idx - z*WIDTH*WIDTH) / WIDTH;

       switch (dir)
       {
       case 1 :                                                // move up
               if (y != 0)
               {
                       CELL[z][y][x] = CELL[z][y-1][x];
                       CELL[z][y-1][x] = 64;
               }
               else
                       return false;                        // impossible to move
               break;

       case 2 :                                                // move down
               if (y != 3)
               {
                       CELL[z][y][x] = CELL[z][y+1][x];
                       CELL[z][y+1][x] = 64;
               }
               else                        
                       return false;
               break;
       
       case 3 :                                                // move left
               if (x != 0)
               {
                       CELL[z][y][x] = CELL[z][y][x-1];
                       CELL[z][y][x-1] = 64;
               }
               else
           return false;
               break;
       
       case 4 :                                                // move right
               if (x != 3)
               {
                       CELL[z][y][x] = CELL[z][y][x+1];
                       CELL[z][y][x+1] = 64;                        
               }
               else
           return false;
               break;

       case 5 :                                                // move forward
               if (z != 0)
               {
                       CELL[z][y][x] = CELL[z-1][y][x];
                       CELL[z-1][y][x] = 64;
               }
               else
           return false;        
               break;

       case 6 :                                                // move backward
               if (z != 3)
               {
                       CELL[z][y][x] = CELL[z+1][y][x];
                       CELL[z+1][y][x] = 64;                        
               }
               else
                       return false;
               break;
       
       default :
               return false;
       }

       return true;                                        // success to move
}

bool IDA(int depth, short prev)                // searching algorithm
{
       depth++;
       short opp;

       for (int i=1; i<=6; i++)
       {
               opp = (i%2 == 0) ? i-1 : i+1;                // the opposite side of moving direction.
               if (prev != opp && move_to(i))
               {
                       if (cur_MD()+depth<=bound)
                       {
                               if (depth == bound || IDA(depth, i))                // recursive call
                               {
                                       move_to(opp);                        // move back
                                       ANS[depth] = i;                        // save the answer
                                       return true;
                               }
                       }
                       move_to(opp);                        // move back
               }
       }

       return false;
}

void print_cur()                                        // print out the current status
{
       for (int i=0; i<WIDTH; i++)
       {
               for (int j=0; j<WIDTH; j++)
               {
                       for (int k=0; k<WIDTH; k++)
                       {
                               if (CELL[j][i][k] == 64)
                                       printf("  $");
                               else
                   printf("%3d", CELL[j][i][k]);
                       }
                       printf(" | ");
               }
               printf("\n");
       }
       return;
}

void search()                                                // find the optimal solution
{
       bound = cur_MD();                                // lower bound of moves in optimal solution

       if (bound != 0)
       {
               cout << "Lower Bound = " << bound << endl << "Now Searching..." << endl;

               cout << "Trying " << bound << endl;

       while(!IDA(0, -1))                        // searching start
               {
                       bound += 2;                                // if the solution wasn't found, try with bound+2 as the lower bound
                       cout << "Trying " << bound << endl;
               }

               cout << "Success!" << endl;
       }

       return;
}

int main(int argc, char* argv[])
{
       char *input_file, *output_file;//, *cmd;

       /*if (argc != 2)                                                // check the arguments
       {
               printf("ERROR : Please enter the input file name as an argument.\n");
               return 1;
       }*/

       input_file = "puzzle.in";//argv[1];

       if (!read_input(input_file))                // read the input file and save it into the array
               return 1;

       char cmd[20];
       //cmd = new char[20];

       set_md();                                                        // set the MD values

       print_cur();

       printf("$>");
       cin.getline(cmd, sizeof(cmd));                                // ready to accept a command

       while (strcmp("quit", cmd))
       {
               if (strlen(cmd)==1 && cmd[0] >= '1' && cmd[0] <= '6')                        // moving command
               {
                       if(!move_to((int)(cmd[0] - '0')))
                               cout << "Illegal Move!" << endl;                        // fail to move
                       else
                               print_cur();                                                                // success to move
               }
               else if (!strncmp("in ", cmd, 3))                        // read a sequence from a file
               {
                       char buf;
                       input_file = cmd + 3;
                       ifstream in(input_file);
                       cout << "Moving... : ";
                       while(in.get(buf))
                       {
                               if (buf >= '1' && buf <= '6')
                               {
                                       cout << buf;
                                       if(!move_to((int)(buf - '0')))
                                       {
                                               cout << " Illegal Move!" << endl;
                                               goto exit;
                                       }
                               }
                       }

                       exit :
                       in.close();
                       cout << endl;
                       print_cur();
               }
               else if (!strncmp("out ", cmd, 4))                        // solve the puzzle, and put out the optimal sequence of moves
               {
                       output_file = cmd + 4;
           search();
                       cout << "Optimal solution : " << bound << " moves." << endl;
                       ofstream out(output_file);
                       for (int i=1; ANS[i] != 0; i++)                        // ANS re-initialization for next solving
                       {
                               out << ANS[i];
                               ANS[i] = 0;
                               if (i%10 == 0)
                                       out << endl;
                       }
                       out.close();

                       print_cur();
               }
               else
                       printf("Wrong Command.\n");

               printf("$>");
               cin.getline(cmd, sizeof(cmd));
       }

       return 0;
}

'IT > 소스코드' 카테고리의 다른 글

[MIT Scheme] Calculator  (0) 2003.07.10
[Java] Soma Cube  (0) 2003.07.10
[C++] 3-dimension 63-Puzzle  (1) 2003.07.10
[C++] Booth's Algorithm Simulator  (0) 2003.07.10
[MIPS Assembly] MAXMIN  (0) 2003.07.10
[MIPS Assembly] WriteBackwards  (0) 2003.07.10

Comment +1

  • zzun 2004.07.11 02:06 신고

    슬라이딩 퍼즐은 기본적으로 state들로 볼 수 있다.
    15-puzzle의 경우엔 총 16!개의 state가 존재하고
    그 state들이 서로 얽히고 &#49445;히도록 transition이 존재한다.

    초기의 생각은 그런 state들을 그룹지어서..
    각 transition에게 특성을 부여하는거였는데..
    워낙 광범위하고, 정의하기가 어려워서 포기했다.
    그러던 중 IDA* 알고리즘을 발견하게 됐고,
    트리 형태로 구현하는 방법을 생각하게 됐다.

    16!개의 state로 생각하지 말고...
    현재의 state를 root로 두고...
    모든 state는 child를 4개(4방향으로 움직일 수 있음, 실제론 3개-왔던방향으로 돌아가는건 의미없으므로)씩 갖고 있는 node라고 생각하면...
    무한히 뻗어나갈 수 있는 트리를 생각할 수 있다.

    이렇게 되면 transition은 아주 일반적인 것이 되므로..
    각 node를 특성화 시키는게 필요한데
    가장 간단한것이 node마다 어떤 숫자를 부여하는 것이다.
    GOAL state로 부터 얼마나 떨어져있나 하는 숫자.

    이때 쓴것은 Manhattan Distance 라고...
    간단히 말해 |x1-x2| + |y1-y2| 를 구하는 것이다.
    현재 15개의 cell에 대해 MD들을 다 합하면(empty cell 제외)
    일정한 값이 되고 이 값이 각 state를 구분짓는 기준이 된다.
    또한, 현재 state의 MD의 합은 곧 optimal solution의 move수의 lower bound가 된다.
    (한번의 move에 반드시 하나의 cell이 empty cell과 바뀌므로)

    이제 tree를 타고 내려가면서 검색을 시작한다.
    tree라고 해서 직접 구현하는것이 아니라
    recursive function을 통해 간단히 구현한다.
    empty cell이 이동 가능한 지점들을 차례로 방문하면서
    만약 그 지점으로 이동했을경우 MD+depth가 구해놓은 lower bound보다 작거나 같다면 제대로 찾아온 것이므로 검색을 계속한다(recursive call).
    크다면 잘못 온것이므로 false를 return하면서 이동한것을 원래대로 복귀시킨다.

    이렇게 검색을 하다가 MD = 0 이 되고 현재 node의 tree depth가 lower bound랑 같다면 해를 구한 것이 된다. 이 때는 true를 return하면서 구했던 solution을 저장한다.

    만약 lower bound에 해당하는 모든 solution을 검색했으나 딱 떨어지는 solution이 없을 경우엔 lower bound를 2만큼 증가시켜 다시 검색을 시도한다.
    (bound를 1 증가시키는건 의미가 없다.)

    이번 숙제는 3차원 63-puzzle 이였는데
    간단한 확장으로 어렵지 않게 구현이 가능하다.


티스토리 툴바