Перейти к содержимому

Фото
- - - - -

Хотите задачку


  • Вы не можете создать новую тему
  • Please log in to reply
15 ответов в этой теме

#1 ННБ

ННБ
  • Пользователь
  • 1 664 сообщений

Отправлено 04 Май 2005 - 13:21

Описание

Magic Squares

Following the success of the magic cube, Mr. Rubik invented its planar version, called magic squares. This is a sheet composed of 8 equal-sized squares (see Figure 3).




1                                    2 3                                    4
8                                    7 6                                    5
Figure 3: Initial configuration




In this task we consider the version where each square has a different colour. Colours are denoted by the first 8 positive integers (see Figure 3). A sheet configuration is given by the sequence of colours obtained by reading the colours of the squares starting at the upper left corner and going in clockwise direction. For instance, the configuration of Figure 3 is given by the sequence
(1,2,3,4,5,6,7,8). This configuration is the initial configuration.


Three basic transformations, identified by the letters 'A', 'B' and 'C', can be applied to a sheet:


'A': exchange the top and bottom row,


'B': single right circular shifting of the rectangle,


'C': single clockwise rotation of the middle four squares.


All configurations are available using the three basic transformations.






Figure 4: Basic transformations




The effects of the basic transformations are described in Figure 4. Numbers outside the squares denote square positions. If a square in position p contains number i, it means that after applying the transformation, the square whose position was i before the transformation moves to position p.

You are to write a program that computes a sequence of basic transformations that transforms the initial configuration of Figure 3 to a specific target configuration (Subtask A). Two extra points will be given for the solution if the length of the transformation sequence does not exceed 300 (Subtask B).


Input Data

The file INPUT.TXT contains 8 positive integers in the first line, the description of the target configuration.

Output Data

On the first line of file OUTPUT.TXT your program must write the length L of the transformation sequence. On the following L lines it must write the sequence of identifiers of basic transformations, one letter in the first position of each line.


Tool

MTOOL.EXE is a program in the task directory that lets you play with the magic squares. By executing "mtool input.txt output.txt" you can experiment with the target configuration and the sequence of transformations.


Example Input and Output




INPUT.TXT OUTPUT.TXT

2  6  8  4  5  7  3  1 7
B C A B C C B


Figure 5: Example Input and Output

Навскидку решив обойтись без эвристической функции, так как ее написание потребовало бы больше времени, написал решение за два часа
вот мой резалт

// squares.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <string.h>
#define DEEPLEVEL 25
#define OPTIMIZELEVEL 2


int iData[8];   //digit data
static int iTarget[8];
 
static char cSolution[25];
static char *pz;
FILE *fli,*flout;


int iMutationConst(char cType, int iDataArr [], int iDeepLevel);
bool bCheckMutation (int iDataArr[]);
void vOptimizeS ();


int main(int argc, char *argv[])
{
	int iData [8] = {1,2,3,4,5,6,7,8};//initial Configuration
	int len; //lenght of Solution
	pz = cSolution; // pointer to solution string
	
	/// Parameters Control
	if (argc <3){
  printf ("Two parameters required. \n");
  exit(1);

	}
	
	// Loading Target Array and control input data
	fli=fopen(argv[1],"r");
	

	for (int i=0; i<8; i++)
  if(fscanf (fli," %d",&iTarget[i])==EOF){
  	printf ("Incorrect parameter. \n");
  	exit(1);
  }

	
	//If the target configuration the same ad initial
	if (bCheckMutation(iData)){
  printf ("Target the same as beginning. \n");
  exit(1);
	}
	
	// beginning
	if (iMutationConst('A', iData , 1)==1){
  
  
	}else
	if (iMutationConst('B', iData , 1)==1){
  
  
  
	}else
	if (iMutationConst('C', iData , 1)==1){
  
	}
	
	//Optimize solution
	for (int i=0; i<OPTIMIZELEVEL; i++)
  vOptimizeS();
	

	len =strlen(cSolution);
	
	//Print out solution into file
	flout = fopen(argv[2],"w");
	fprintf (flout,"%d",len);
	while (len>=0){
  	fprintf (flout,"%c\n",cSolution[len]);
  	len--;
	}
	fclose(fli);
	fclose(flout);
	
	
	return 0;

}

int iMutationConst(char cType, int iDataArr [], int iDeepLevel){
	int iD [8], iDt[8];//Array for data which sqves in recursive operations
	
	if (cType=='A'){
  //A movement
  iD[0]= iDataArr[7];
  iD[1]= iDataArr[6];
  iD[2]= iDataArr[5];
  iD[3]= iDataArr[4];
  iD[4]= iDataArr[3];
  iD[5]= iDataArr[2];
  iD[6]= iDataArr[1];
  iD[7]= iDataArr[0];
  
	
	}
	else if (cType=='B'){
  // B Movement
  iD[0]= iDataArr[3];
  iD[1]= iDataArr[0];
  iD[2]= iDataArr[1];
  iD[3]= iDataArr[2];
  iD[4]= iDataArr[5];
  iD[5]= iDataArr[6];
  iD[6]= iDataArr[7];
  iD[7]= iDataArr[4];
  

  
   
	
	}
	else {
  // C Movement
  iD[0]= iDataArr[0];
  iD[1]= iDataArr[6];
  iD[2]= iDataArr[1];
  iD[3]= iDataArr[3];
  iD[4]= iDataArr[4];
  iD[5]= iDataArr[2];
  iD[6]= iDataArr[5];
  iD[7]= iDataArr[7];
  
	}
	// Save data for back turns
	for (int i=0; i<8;i++)
   iDt[i]= iD[i];

	
	
	//Check if finish configuration considered
	if (bCheckMutation (iD)) {
  
   *pz=cType;
   pz++;
  return 1;
	}
	else if (iDeepLevel >= DEEPLEVEL)
  return 0;
	else {
  iDeepLevel++;
  if (cType != 'A') // exclude AA transformation
  	if (iMutationConst('A', iD , iDeepLevel)==1){//recursive operation for next mutation
    
     *pz=cType; //if target considered save turn
     pz++;
    return 1;
  	}
  	else
    for (int i=0; i<8;i++)//Turn back
    	iD[i]= iDt[i];
  	
  	

  if (iMutationConst('B', iD , iDeepLevel)==1){//recursive operation for next mutation
    
    *pz=cType; //if target considered save turn
    pz++;
    return 1;
  	}
  else
    for (int i=0; i<8;i++)
    	iD[i]= iDt[i];
  if (iMutationConst('C', iD , iDeepLevel)==1){//recursive operation for next mutation
    
    *pz=cType; //if target considered save turn
    pz++;
    return 1;
  	}
  else
    for (int i=0; i<8;i++)
    	iD[i]= iDt[i];

  return 0; 
	}
	
	
}
bool bCheckMutation (int iDataArr[]){
	

	if ((iDataArr[0]==iTarget[0]) && (iDataArr[1]==iTarget[1]) && (iDataArr[2]==iTarget[2]) && (iDataArr[3]==iTarget[3]) && (iDataArr[4]==iTarget[4]) && (iDataArr[5]==iTarget[5]) && (iDataArr[6]==iTarget[6]) && (iDataArr[7]==iTarget[7]))
  return true;
	else
  return false;

}

void vOptimizeS(){
	///Optimize function removes ABA to B and BBBB mutations
	char cTemp [25];
	char *pAT;
	int len;

	pAT = cTemp;
	len =strlen(cSolution);
	len--;
	while (len>=0){
  if ((cSolution[len]=='A') && (cSolution[len-1]=='B') && (cSolution[len-2]=='A'))
  {
  	*pAT='B';
  	pAT++;
  	len-=3;
  }
  else if ((cSolution[len]=='B') && (cSolution[len-1]=='B') && (cSolution[len-2]=='B')&& (cSolution[len-3]=='B'))
  {
  	len-=4;
  }
  else
  {
  	*pAT=cSolution[len];
  	pAT++;
  	len--;
  }
	}
	*pAT=0;

	for (int i=0; i<(int)strlen(cTemp); i++)
  cSolution[i]=cTemp[i];
  	
	cSolution[strlen(cTemp)]=0;
	
	
}

Немного кривоват но все работает
При желании код можно оптимизировать но лень и не в этом была цель

Сообщение изменено: Ничего не боится (04 Май 2005 - 13:25 )

  • 0

#2 Zero

Zero

    TRUST NO ONE

  • Постоялец
  • 9 116 сообщений
  • Откуда:Таллин

Отправлено 04 Май 2005 - 16:32

Можешь, плиз в двух словах по-русски? Я английский знаю (технический) очень хорошо, но лень...
  • 0
Моя Родина - СССР! Пролетарии всех стран, соединяйтесь!
-----------------------------------------------------------------------
Ясность - одна из форм полного тумана. Форумчане, давайте жить дружно!

#3 PPL

PPL
  • Пользователь
  • 45 сообщений

Отправлено 04 Май 2005 - 18:13

hah esli znaesh' to chego sprashivaesh' perevesti "umnik"? Ili chitat' ne umeesh'? :P
  • 0

#4 libricon

libricon
  • Постоялец
  • 572 сообщений
  • Откуда:Маарду

Отправлено 04 Май 2005 - 18:44

мне тоже чето читать лень. сформулирируй задание по-русски
  • 0
Пингвин птица гордая, пока не пнешь, не полетит!!!

#5 V^v

V^v
  • Пользователь
  • 316 сообщений

Отправлено 04 Май 2005 - 20:51

бррр, ненавижу алгоритмические задачки...
  • 0
int main(void)

#6 ННБ

ННБ
  • Пользователь
  • 1 664 сообщений

Отправлено 04 Май 2005 - 21:32

В общем тема такая
есть 8 квадратов разных цветов у нас они помечены цифрами
расположены в два ряда вот так
1 2 3 4
8 7 6 5

к ним можно применять три базовые трансформации А В и С

А меняет верхнюю и нижнюю строки

было

1234
8765
стало

8765
1234

В правый сдвиг обеих строк
было
1234
8765

стало

4123
5876

и С
вращаетпо часовой 4 средних квадрата

было
1234
8765

стало

1724
8635

Задача написать прогу которая на входе принимает файл конфигурации и на выходе выдает решение как из исходной конфигурации получить желаемую пользуясь только 3мя видами трансформации.
Грубо говоря так.




Добавлено в [mergetime]1115235047[/mergetime]
Академическая алгоритмическая задачка в чистом виде

Добавлено в [mergetime]1115235137[/mergetime]
Мое решение хоть и грубое и в лоб
но решает все и в принципе быстрее чем при использовании эвристических функций, так как пространчтво решений в данном случае не велико.
К тому же время затраченное на написание эвристической функции ббыло бы больше чем написаное как есть.
Скорость быстрая меньше секунды.
  • 0

#7 Zero

Zero

    TRUST NO ONE

  • Постоялец
  • 9 116 сообщений
  • Откуда:Таллин

Отправлено 04 Май 2005 - 21:54

PPL, Такой умный? А тебе лень было мою просьбу ВНИМАТЕЛЬНО прочитать? Что я написал? Читать лень, хоть и могу. Будьте спокйнее и внимательнее, народ.
Умник.
  • 0
Моя Родина - СССР! Пролетарии всех стран, соединяйтесь!
-----------------------------------------------------------------------
Ясность - одна из форм полного тумана. Форумчане, давайте жить дружно!

#8 heybuddy

heybuddy
  • Пользователь
  • 110 сообщений

Отправлено 04 Май 2005 - 22:02

афтар темы-ГЕНИЙ ;)
  • 0

#9 ННБ

ННБ
  • Пользователь
  • 1 664 сообщений

Отправлено 04 Май 2005 - 22:10

V^v, я их наоборот люблю
Ибо там можно хоть творчески помыслить.
А то основные велосипеды уже давно изобретены при написании типовых проектов.
Мои любимые вещи это всякие такие штуки.
  • 0

#10 PPL

PPL
  • Пользователь
  • 45 сообщений

Отправлено 05 Май 2005 - 00:55

Zero
Ну так по-русски тебе все равно придется "читать",а если знаешь английский "очень хорошо" ,то не должно быть предпочтения русского. Your logic is flawed dude ;)

Сообщение изменено: PPL (05 Май 2005 - 00:56 )

  • 0

#11 spamrobot

spamrobot
  • Новобранец
  • 7 сообщений

Отправлено 05 Май 2005 - 08:50

Вот моя программа. Находит самый короткий (а значит оптимальный) ответ. Задача кстати простая, 20 минут.
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

ifstream fi("INPUT.TXT");
ofstream fo("OUTPUT.TXT");



//permutations
int p[3][8]={{8,7,6,5,4,3,2,1},{4,1,2,3,6,7,8,5},{1,7,2,4,5,3,6,8}};

struct Entry{
	int a[8];
	int from;
};

char inqueue[87654321/8+1];

vector<Entry> v;


void print(){
	vector <char> res;
	int cur=v.size()-1;
	while(v[cur].from>-1){
  if (v[cur].a[0]==v[v[cur].from].a[7]) res.push_back('A');
  if (v[cur].a[0]==v[v[cur].from].a[3]) res.push_back('B');
  if (v[cur].a[0]==v[v[cur].from].a[0]) res.push_back('C');
  cur=v[cur].from;
	}
	fo<<res.size()<<'\n';
	for (int i=res.size()-1;i>=0;i--){
  fo<<res[i]<<'\n';
	}
}


int power[]={1,2,4,8,16,32,64,128};

int main(){
	Entry newEntry;
	for (int i=0;i<8;i++) {
  newEntry.a[i]=i+1;
	}

	int temp;
	int finish=0;
	for (int j=0;j<4;j++) {
    	fi>>temp;
    	finish=finish*10+temp;
	}
	finish*=10000;
	fi>>temp;finish+=temp*1000;
	fi>>temp;finish+=temp*100;
	fi>>temp;finish+=temp*10;
	fi>>temp;finish+=temp*1;
	if (finish==12345678){
  fo<<"0\n\n";
  return 0;
	}

	newEntry.from=-1;
	v.push_back(newEntry);
	inqueue[12345678/8]|=power[12345678%8];

	int cur=0;
	while(cur<v.size()){
  newEntry.from=cur;
  for (int j=0;j<3;j++){
  	for (int i=0;i<8;i++) 
    newEntry.a[i]=v[cur].a[p[j][i]-1];

  	int t=0;

  	for (int k=0;k<8;k++)t=t*10+newEntry.a[k];

      if ((inqueue[t/8]&power[t%8])!=power[t%8]){
      	inqueue[t/8]|=power[t%8];
      	v.push_back(newEntry);
      }
      if (t==finish) {
      	print();
      	return 0;
      }
  }
  cur++;
	}
	return 0;
}

  • 0

#12 tomatensaft

tomatensaft

    Samurai Jack

  • Пользователь
  • 449 сообщений
  • Откуда:Tallinn

Отправлено 05 Май 2005 - 10:13

Zero
Ну так по-русски тебе все равно придется "читать",а если знаешь английский "очень хорошо" ,то не должно быть предпочтения русского. Your logic is flawed dude ;)

Просмотреть сообщение


А с какой целью ты пытаешься доказать это? :rolleyes:
  • 0
"This is all I want'd t' say 'bout dat..." © Forest Gump

#13 Zero

Zero

    TRUST NO ONE

  • Постоялец
  • 9 116 сообщений
  • Откуда:Таллин

Отправлено 05 Май 2005 - 14:33

PPL, я не понял, почему РУССКОМУ человеку должго быть удобнее читать по-английски. Division by Zero, dude.
  • 0
Моя Родина - СССР! Пролетарии всех стран, соединяйтесь!
-----------------------------------------------------------------------
Ясность - одна из форм полного тумана. Форумчане, давайте жить дружно!

#14 spamrobot

spamrobot
  • Новобранец
  • 7 сообщений

Отправлено 12 Май 2005 - 16:21

Тема получилась с офигенной смысловой нагрузкой...
  • 0

#15 Solmyr

Solmyr
  • Пользователь
  • 32 сообщений

Отправлено 12 Май 2005 - 17:12

получилось вот такое[java] :rolleyes:
у меня решает все за пару секунд
import java.io.*;

public class mut{
static int a[]   = new int[8];
static int i[]   = {1,2,3,4,5,6,7,8};
static int m[][] = {
	{8,7,6,5,4,3,2,1},
	{4,1,2,3,6,7,8,5},
	{1,7,2,4,5,3,6,8}};
	
static java.util.Random rand = new java.util.Random();
	
public static void transform(char c){
	int ob[] = new int[8];
	for(int i = 0; i < 8; i++)ob[i] = a[i];
	switch(c){
  case 'A':
  	for(int i = 0; i < 8; i++)a[i] = ob[m[0][i]-1];
  	System.out.println("A");
  	break;
    
  case 'B':
  	for(int i = 0; i < 8; i++)a[i] = ob[m[1][i]-1];
  	System.out.println("B");
  	break;
  	
  case 'C':
  	for(int i = 0; i < 8; i++)a[i] = ob[m[2][i]-1];
  	System.out.println("C");
	}
}
	
public static void getData() throws IOException{
	BufferedReader READ = new BufferedReader(new FileReader("res.txt"));
	String reading;
	for(int i = 0;i < 8;i++){
	reading = READ.readLine();
  a[i] = Integer.parseInt(reading);
	}
	READ.close();
}

public static void main(String[] args) throws IOException{
	getData();
	for(int i = 0;i < 8; i++)System.out.print(a[i]);
	System.out.println();
	while((a[0]!=i[0])||(a[1]!=i[1])||(a[2]!=i[2])||(a[3]!=i[3])||
	(a[4]!=i[4])||(a[5]!=i[5])||(a[6]!=i[6])||(a[7]!=i[7])){
  
  if((a[0]==8)&&(a[1]==7)&&(a[2]==6)&&(a[3]==5)&&
  (a[4]==4)&&(a[5]==3)&&(a[6]==2)&&(a[7]==1)){
  	transform('A');break;}
  
  if(rand.nextInt(2)==0)transform('B');
  else transform('C');
	}
	for(int i = 0;i < 8; i++)System.out.print(a[i]);
	System.out.println();
}
}

  • 0

#16 spamrobot

spamrobot
  • Новобранец
  • 7 сообщений

Отправлено 12 Май 2005 - 17:38

Solmyr, рокенрольное решение :) А если поставить дополнительное условие: ответом должна быть наикратчайшая последовательность, причем если таких несколько, то надо вывести первую из них, если б они были отсортированы по алфавиту (как в словаре)?

Сообщение изменено: spamrobot (12 Май 2005 - 17:38 )

  • 0