While working on a project I ran into an interesting problem that I thought the ATers might enjoy solving (and hopefully someone does, because this problem is stumping my project ).

The setup:

1.) Start with a list A. A has some items, some of which are identical, some of which are unique. A has at least 1000 items.
2.) List B starts as an identical copy of list A, with each item in A corresponding to its same-placement item in B.
3.) A few items are removed from list B, and a few new items are added. As items are removed from B the item it corresponded to in A no longer has a corresponding item, even if there still is an item in B that has the same value. As items are added to B the new items never get a corresponding item in A.

The Solution:

We need to write two programs, G and P, that create and use a code or function Z, and be able to follow these steps:

1.) P is given A and B.
2.) P is ran and returns Z.
3.) G is given Z and the placement of an item in A.
4.) G is ran and returns true if there is a corresponding item, false if there isn't. If it returns true, it also returns the placement of the corresponding item in B.

The Problem

What are G and P such that Z is as short as possible?

Example

For this example A will only have 5 items, instead of at least 1000. This is just to show as an example.
We start with list A, its corresponding item placement in list B, and list B:

A————Corresponding———-B
cat———-1—————————-cat
dog———2—————————-dog
dog———3—————————-dog
mouse—–4—————————-mouse
cat———-5—————————-cat

Next, some items are removed from B.

A————Corresponding———-B
cat———-null————————-cat
dog———1—————————-dog
dog———2—————————-dog
mouse—–null————————-mouse
cat———-3—————————-cat

Next, some items are added to B.

A————Corresponding———-B
cat———-null————————-dog
dog———1—————————-snake
dog———3—————————-dog
mouse—–null————————-cat
cat———-4—————————-bird

*P is given A and B.
*P creates Z.
*G is given Z and the number 3 (the placement of the 2nd dog in list A)
*G should return true and 3.
If G were given 4, it should return false.

In case you are wondering, here is why I need to know this:
One of my projects is a game that runs off a list (A). There is a save code feature that marks your progression in the game by indicating which items in the list A you have explored/changed. As I continue to work on the game I make minor changes to A, adding some new areas and removing ones that are not so good. When I make an update to the game the list is slightly different (list B). Because of this, sometimes old save codes will not work since the items it pointed to have shifted in the new list. What I am trying do is make a save code converter that will take an old code and update the list pointers to their new locations in the new list (B). Because I do quiet a few updates on the game it is possible that someone will create a save code when the game is on version 3, and come back to the game when it is on version 9. This means their code needs to be transformed 6 times. This is why I want the code transformation function/code (z) for each version to the next to be as small as possible, so my project doesn't reach the JSON size limit of 2.5 MB.

Ill start this off the most obvious solution:

Z starts as a variable with no value. P goes through each item in A. If the item has a corresponding item in B it will add the placement number and a ‘;’ to Z, otherwise it will just add ‘;’. G can then go through Z, adding each value inbetween the ‘;’s to a new a list. When it is given the placement of the item in A it looks up the item with the same placement in the new list. If the looked up item's length is greater than 0 it has a corresponding item in B, which is at the placement of the looked up item.

In the example I posted Z would look like:


This works, but Z would be very large when A and B have thousands of items.

Actually, it turns out this doesn't work, as I don't know how P would be able to find the corresponding values in B since there could be values in B with identical values. Perhaps because there could be identical values in A and B it is impossible to do this?

Does this work? https://scratch.mit.edu/projects/270440307/
It should as long as you aren't making thousands of changes each time. The first items of each list are the version number.

When a item is removed from B, it is noted in a update code(Z?), eg:

1 Cat
2 1 Dog
3 2 Dog
4 Mouse
5 3 Cat

Update code: 1-3-

When items are added to B, they are noted in the update code too:
1 Dog
2 Snake
2 3 Dog
3 4 Cat
5 Bird

Update code: 2+5+
The value can be gotten from be for added items, get item 2 from B and insert it at 2, get item 5 from B and insert it at 5. You can get rid of the need for this if you only add items to the end. Then you would just have to add any missing values from the end of B.

The removal and addition of items can be combined in one update code:
1 Cat
2 1 Dog
2 Snake
3 Dog
4 Mouse
5 4 Cat
5 Bird

Update code: 1-2+4-5+

imfh wrote:

Does this work? https://scratch.mit.edu/projects/270440307/
It should as long as you aren't making thousands of changes each time. The first items of each list are the version number.

When a item is removed from B, it is noted in a update code(Z?), eg:

1 Cat
2 1 Dog
3 2 Dog
4 Mouse
5 3 Cat

Update code: 1-3-

When items are added to B, they are noted in the update code too:
1 Dog
2 Snake
2 3 Dog
3 4 Cat
5 Bird

Update code: 2+5+
The value can be gotten from be for added items, get item 2 from B and insert it at 2, get item 5 from B and insert it at 5. You can get rid of the need for this if you only add items to the end. Then you would just have to add any missing values from the end of B.

The removal and addition of items can be combined in one update code:
1 Cat
2 1 Dog
2 Snake
3 Dog
4 Mouse
5 4 Cat
5 Bird

Update code: 1-2+4-5+

Oh wow, this is a great solution! The one downside is that I won't be able to make edits to the list in my offline text editor anymore (which means no ctrl+f to find items quickly), but this will make save code updating easy and possible! Thanks

Glad it works!

You can update it in a text editor, just do it like this:

To delete Dog and add Bird to the end:
Cat
Dog
Mouse

Cat
-
Mouse
+
Bird

Anything replaced by - will be deleted in the save code any anything preceded by a + will be added.

When you run Create Update from B, it will remove the - and + and create the Update Code.
You will then have to either remove the + and - by hand in the text editor or export the list.

imfh wrote:

Glad it works!

You can update it in a text editor, just do it like this:

To delete Dog and add Bird to the end:
Cat
Dog
Mouse

Cat
-
Mouse
+
Bird

Anything replaced by - will be deleted in the save code any anything preceded by a + will be added.

When you run Create Update from B, it will remove the - and + and create the Update Code.
You will then have to either remove the + and - by hand in the text editor or export the list.

Ah yes, that should work. Clever, yet again!