## 10073 - Constrained Exchange Sort

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

Moderator: Board moderators

dh3014
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:

### 10073 - Constrained Exchange Sort

May anybody provide the correct answer for following test data?:

2
LKJIHGFEDCBA
KLJIHGFEDCBA

My output is:
Permutation #1

Permutation #2
HGABEHGECIKGJDBCIFGJDACIFKJDABIFKJDABCF

I want to know if my output sequence is the shortest.

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
Is there some trick to this ? My attempts at a scoring function and some recursive look ahead dont seem to work very well.......

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

### 10073 pls explain

The letter 'L' at location l1 can be swapped with the letter at location l2 provided l1 ~ l2 = di and floor((l1 - 1) / di + 1) = floor((l2 - 1) / di + 1)for i = 1 | 2 | 3, where (d1, d2, d3, d4) = (1, 3, 6, 12).
what does the "~" symbol mean?

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

### 10073 Constrained Exchange Sort

The memory limit for this problem is tight (~16 MB), so I don't think hashing is possible here. Instead, I believe A* is the only way to conquer this problem.

Now the problem is: how can I set up a good heuristic function? I have absolutely no idea. Can anyone give me some hints? Thanks in advance.

P.S. My own function, which deals with mis-put letters, gives me TLE all the time.

P.S.2. This "sorting method" looks like a variant of 15-puzzles....
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I haven't solved this yet, but my idea on this is a 'man in the middle' approach (I don't know if that is the official name for it). This kind of approach kan be used for problems in which both the start and the target state are known (Rubick's Cube, Fifteen puzzle, Solitair, etc.). The idea is to simultaniously expand state-space from the start state (using regular moves) and from the target state (using backward moves) until you find a state that is in both expansions.

Say the problem has a fanning factor of 3 (every state leads on avg. to 3 new states) and you have a storage capacity of about a milion states, you can only go to about 13 moves deep before you run out of storage. But if you simultaniously expand from both sides, you can go about 12 moves deep for every side for a total of 24 or 25 moves within the same storage.

Of course the success of this approach leans heavily on the implementation details: the way you encode the states and store them, checking if you already visited a particular state, etc.

But again, I haven't solved this problem yet, so I'm not sure if this approach is feasible in this situation. I know of a Rubic's Cube solver that uses about 10Megs of memory taking only seconds to solve any scrambled cube using this approach.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Thanks joey (though I don't know how to implement it Bidirectional A*/BFS? Let me think about it....)

I tried to use some sort of Manhattan distance as my heuristic function. Still, TLE..... Any help plz???
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Hmm. Forget it. Tried to implement it, but its definitly too slow...

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Here some things that might interest you:
I know from my program, that there is at least one test case where you need 35 moves, but you will never need more than 38 for cases of the judge input.
I had to use a lot of tricks to avoid TLE in this problem, like I have stored the result of all permutations that are reachable from "AB...L" in at most 13 steps. My solution is definitely not nice, so perhaps someone with a better runtime can give better hints.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Thanks for your hint! Now I'm able to get Accepted in ~4 sec. Thx a lot !!!

(Btw: I've spent >1 hr on a stupid bug - forgetting to put things in my stack which checks if a state is repeated.... )
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am
The problem can be interpreded as a three-dimensional version of the 15 Puzzle.

Code: Select all

``````    A---D
/|  /|
B---E |
/| G/|-J
C---F |/
| H-|-K
|/  |/
I---``````
Possible exchanges are nothing but movements of letters to the (empty) "L" field. Using an IDA* search with the manhattan heuristics for the 15 Puzzle, my solution got AC in ~7 seconds without precalculating permutations. I basically re-used the solution from 10181, added the third dimension and changed the grid limits.

Adding a heuristics enhancement analogous to the 15-Puzzle's "Last Move" reduced runtime to ~3 seconds.
Last edited by Christian Schuster on Tue Feb 22, 2005 1:46 pm, edited 1 time in total.

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am
Ermmm... "0:00.1000" seems to be a quite strange time.

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh
after more than 3 years you are being informed that ~ means difference, so l1 ~ l2 is equivalent to abs(l1-l2)
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

New poster
Posts: 16
Joined: Mon Jun 26, 2006 9:33 am
Contact:

### something to clarify

Referring to the problem statement, the 3rd constraint on the swapping procedure:

"... can be swapped with the letter at location l2 provided l1 ~ l2 = di "

I am not sure of what the symbol ~ suppose to mean. Checked the wikipedia, it just says that it is a shorthand to say that there is a binary relation between l1 and l2. But why would l1~l2 be equated to di?

On a sidenote, are there any more problems on the UVa site that requires by A* or IDA*? I am solving all problems of this class in one go as I've learnt this algorithm recently. So far I've tried the 8-puzzle, 15-puzzle and knights in FEN.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
I am not sure of what the symbol ~ suppose to mean
Absolute difference of the two numbers. (link)
On a sidenote, are there any more problems on the UVa site that requires by A* or IDA*?
Try these problems: