(25C) 1D Rubik's Cube

[nsg]

This is an implementation of one-dimensional equivalent of Rubiks cube.
The string of 8 digits (colors) can has to be manipulated to produce an initial position. Move consists of the following: any 4 consecutive characters in the string turn 180 degrees in their place (4-substring reverses its order).
For example

12345678 may be transformed into 1(2345)678 --> 1(5432)678 = 15432678 by reversing substring of length 4 starting from second character.

If the input is some permutation of digits 12345678, then only even permutations can be completely sorted.

Here are several challenges:

1. Warm up challenge.

12121212 STO 0
turn into 11112222

12341234 STO 0
turn into 11223344

2. Standard mode.

a) 62783541
b) 87236451
c) 51382764
d) 53847261
e) 64381257

Select one of the initial permutaions a)-e).
Save it to R0
Sort all digits to get 12345678

3. Extra credit.
Extra challenging variant of the puzzle reverses substrings of length 6, rather than 4. This variant allows to sort all permutations, even and odd. To implement this variant modify lines 06 and 23 in the program (they are marked "variant" in the listing). change "06. 6" to "06. 4" and "23. 4" to "23. 6".

Convert 87654321 to 12345678

(there are only 3 substrings of length 6, so at each moment only move 1,2 or 3 are acceptable)

Code:


01. int
02. sto 3
03. 0
04. x>=y
05. gto 48
06. 6        <--- variant: 4
07. rcl 3
08. x>=y
09. gto 48
10. 9
11. x<->y
12. -
13. 10^x
14. .
15. 4
16. +
17. int
18. sto 2
19. sto/ 0
20. rcl 0
21. frac
22. eex
23. 4        <--- variant: 6
24. sto* 0
25. sto/ 2
26. *
27. int
28. sto- 0
29. 0
30. x<->y
31. rcl 1
32. /
33. frac
34. lastx
35. int
36. sto 3
37. rdn
38. +
39. rcl 1
40. *
41. rcl 3
42. x!=0
43. gto 31
44. x<->y
45. sto+ 0
46. rcl 2
47. sto* 0
48. rcl 0
49. gto 00

Initial setting:
f PRGM
FIX 0
10 STO 1
<starting combination of exactly 8 non-zero digits> STO 0
For example: 12121212 STO 0

To make a move: <n> R/S
n=1..5, position of the first character of substring to reverse
Output: updated position.
For example: 3 R/S --> 12212112


Repeat moves until you achieve final position.

[nsg]

(ctd)

This is my first attempt at programming hp 25c (actually it was np 25, but I hope it still applies).

My impression on the experience: I really like the language. int/frac, storage arithmetic, compares of x to y (rather than just to 0) were very useful and allowed to save a lot of steps. But! 49 steps is too damn little. To achieve my goal I had to manage (and downgrade) expectations several times. For example, initially, I wanted to implement different game, but then I realized that I am not even close to be able to fit it in 49 steps, so had to settle for this. Then, originally, I wanted start with initial random permutation (by applying several random moves to 12345678). That also proved to be too much to ask, so now user has to enter initial permutation himself and also check for completion.

There was a nasty surprise: 10^x returns 99999999.60 on 8, 9999999.99 on 7 and 1000000003 on 9, which almost made me retarget the program to HP-33C mode -- there 10^x works as expected. I ended up rounding the result with

Code:


14. .
15. 4
16. +
17. int

and downgraded from 9 digit input (as I originally planned) to 8 digit input, so I do not have to calculate 10^9.