652 - Eight

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang »

Hi,

Can you describe how you do it by IDA*? Mine gets a TLE... even though it should be faster than BFS. Is there a way to "prune" the search like in A* where you don't repeat states?

Thanks.

Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil »

hello. my approach with IDA* was following:

Code: Select all

1. calculate the minimum moves required (MIN) to reach the goal-state, using the "manhattan" heuristic.
2. starting searching with S as the initial state
3. for a state S
     let N = number of moves from the starting state to reach S
         M = number of minimum moves required to reach goal-state from S (using the "manhattan" heuristic, again)
  3.1. if N > MIN then goto step 4.
  3.2. if N + M > MIN then goto step 4.
  3.3. consider the states that can be reached from S using one move, and see if that state has already been reached. if not then expand the search.
4. if the solution was not found in 3.3, then increase MIN and continue with step 3.
but of course, before all this, check if the puzzle is at all solvable. (you can have a look at the link given by LittleJohn).

hope i was clear enough, and hope this helps.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

652 It's OK again!

Post by Observer »

..
Last edited by Observer on Sat Dec 13, 2003 5:20 pm, edited 2 times in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

Latest news! See this page:

http://acm.uva.es/cgi-bin/OnlineJudge?ProblemStat:652

Now, ZERO submission is accepted. I reckon that there must be some flaws in the new judging data. Admins please have a look into it. Thank you.

Or, has the output requirement changed..?? :-?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

You know what? The adminz realize the problem and they're rejudging all the submissions again!! Everything's back to normal~~

Now you can really ignore this topic lu~~~ :lol:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 652 - Eight

Post by plamplam »

Beware this problem contains unnecessary blanks in between inputs. Be sure to handle them properly. I used something like while gets() and checked for a valid character, if so then break and continue to the next case.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

tzupengwang
New poster
Posts: 36
Joined: Fri Dec 02, 2011 1:30 pm
Location: Kaohsiung, Taiwan

Re: 652 - Eight

Post by tzupengwang »

Can anyone help?
I applied the A* algorithm but got TLE. I've seen someone AC with pure BFS, which should be much slower.
Can anyone give me suggestions to speed up my program, or is there some tricky parts in the I/O?

thanks!!

Code: Select all

/*652*/
#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define MAXN 5000000

typedef vector<int> vi;
typedef vector<char> vc;
typedef pair<int,vi> ii;
typedef pair<ii,vc> iii;
vi in;
vi anss;
int factor[10]={1,1,2,6,24,120,720,5040,40320,362880};
int manhatton[10][10];
int h[MAXN];
bool vis[MAXN];
int dis[MAXN];

priority_queue<iii,vector<iii>,greater<iii> >pq;

int abs(int k)
{
    if (k>0)return k;
    else return -k;
}
void MANHATTON()
{
    for (int i=0;i<3;i++)
    {
        for (int j=0;j<3;j++)
        {
            for (int k=0;k<3;k++)
            {
                for (int l=0;l<3;l++)
                {
                    manhatton[i*3+j+1][k*3+l+1]=manhatton[k*3+l+1][i*3+j+1]=abs(i-k)+abs(j-l);
                }
            }
        }
    }
}
int hash(vi s)
{
    int ret=0;
    for (int i=0;i<9;i++)
    {
    //printf("1\n");
        int temp=0;
        for (int j=i+1;j<9;j++)
        {
            if (s[i]>s[j])temp++;
        }
        ret+=temp*factor[8-i];
    }
    return ret;
}
int tot_MANHATTON(vi s)
{
    int ret=0;
    for (int i=0;i<9;i++)
    {
        if (s[i]==9)continue;
        ret+=manhatton[i+1][s[i]];
    }
    return ret;
}
vc Astar()
{
    while (!pq.empty())pq.pop();
    //int count=0;

    memset(vis,false,sizeof vis);

    int ind=hash(in);
    dis[ind]=0;
    h[ind]=tot_MANHATTON(in);
    vc nn;
    pq.push(iii(ii(h[ind],in),nn));
    vis[ind]=true;
    while (!pq.empty())
    {
        //count++;
        //if (count>50)break;

        iii front=pq.top();
        pq.pop();
        vi str=front.first.second;
        vc ansstr=front.second;
        int now=hash(str);
        if (now==hash(anss))return ansstr;
        int nine;
        for (int i=0;i<9;i++)
        {
            if (str[i]==9)nine=i;
        }
        if (nine>2)
        {
            swap(str[nine],str[nine-3]);
            ansstr.push_back('u');
            int index=hash(str);
            if (vis[index]==false)
            {
                vis[index]=true;
                dis[index]=dis[now]+1;
                h[index]=tot_MANHATTON(str);
                pq.push(iii(ii(h[index]+dis[index],str),ansstr));
            }
            ansstr.pop_back();
            swap(str[nine],str[nine-3]);
        }
        if (nine<6)
        {
            swap(str[nine],str[nine+3]);
            ansstr.push_back('d');
            int index=hash(str);
            if (vis[index]==false)
            {
                vis[index]=true;
                dis[index]=dis[now]+1;
                h[index]=tot_MANHATTON(str);
                pq.push(iii(ii(h[index]+dis[index],str),ansstr));
            }
            ansstr.pop_back();
            swap(str[nine],str[nine+3]);
        }
        if (nine%3!=0)
        {
            swap(str[nine],str[nine-1]);
            ansstr.push_back('l');
            int index=hash(str);
            if (vis[index]==false)
            {
                vis[index]=true;
                dis[index]=dis[now]+1;
                h[index]=tot_MANHATTON(str);
                pq.push(iii(ii(h[index]+dis[index],str),ansstr));
            }
            ansstr.pop_back();
            swap(str[nine],str[nine-1]);
        }
        if (nine%3!=2)
        {
            swap(str[nine],str[nine+1]);
            ansstr.push_back('r');
            int index=hash(str);
            if (vis[index]==false)
            {
                vis[index]=true;
                dis[index]=dis[now]+1;
                h[index]=tot_MANHATTON(str);
                pq.push(iii(ii(h[index]+dis[index],str),ansstr));
            }
            ansstr.pop_back();
            swap(str[nine],str[nine+1]);
        }
    }
}
bool unsolvable()
{
    int k=0;
    for (int i=0;i<9;i++)
    {
        if (in[i]==9)continue;
        for (int j=i+1;j<9;j++)
        {
            if (in[j]==9)continue;
            if (in[i]>in[j])k++;
        }
    }
    if (k%2==1)return true;
    return false;
}
int main()
{
    //freopen("in.txt","r",stdin);

    for (int i=0;i<9;i++)anss.push_back(i+1);
    MANHATTON();
    int amm;
    bool first=true;
    scanf("%d",&amm);
    while (amm--)
    {

        in.clear();
        char s[5];
        for (int i=0;i<9;i++)
        {
            scanf("%s",s);
            if (s[0]=='x')in.push_back(9);
            else in.push_back(s[0]-'0');
        }

        if (unsolvable())
        {
            puts("unsolvable");
            first=false;
            continue;
        }
        vc ans=Astar();
        if (first)first=false;
        else puts("");
        for (int i=0;i<ans.size();i++)
            printf("%c",ans[i]);
        puts("");
    }
    return 0;
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 652 - Eight

Post by brianfry713 »

I got AC in 1.228 sec using BFS. Precompute all reachable states from the solution, store them into a map with the reverse path taken.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 6 (600-699)”