optimizing moves in a queue/stack (sorting TV channels)

[Ponch]

I know I'm going to loose more time than I'll win by discussing this, but just for the curiosity...

I'm sorting the channels on a relative's TV (he's in hospital so I have a few days to do that  hopefully he'll appreciate). We've all done that 30 times in our lives (on VCRs and others), you move them like mad until you're done or the remote's batteries are dead.

I was wondering if there was a method to do as few moves as possible.

Normally, I'd start with the channel I want to place in #1 and go fetch it and place it there, that is...unless I see an obvious best move. That's where logic becomes vague and I stop thinking.

An "obvious best move" would be this kind of thing; if 1-2-3-4-5 has to become 2-3-4-5-1, moving 1 to the end is the best move (instead of moving 2 to 1, 3 to 2 etc) but you have to see it and that was a really obvious one.

Are there methods to do that in a sensible way ? I'm talking about 85 channels I'm moving to front from a list of 175. Google doesn't seem to be my friend.

[jaclaz]

Maybe you want to quickly check "Sorting Algorithms":

http://en.wikipedia.org/wiki/Sorting_algorithm

 

The actual commands you have available on that TV set may make one way simpler than another.

 

The algorithm that should be the one with less moves (on randome data) should be selection sort:

http://www.sorting-algorithms.com/

http://www.sorting-algorithms.com/selection-sort

 

Your simplified example of 2-3-4-5-1 is more pertaining to LIS:

http://en.wikipedia.org/wiki/Longest_increasing_subsequence

 

The minimum number of moves to order a list with n elements containing a LIS of m is n-m (but this only tells you the minimum number of moves needed, not which ones are needed).

 

jaclaz

[Glenn9999]

Sorting algorithms are where you want to look, especially sorting networks.  The problem you'll run into is that most sorts are based on exchanges more than reorders, due to the nature of computer memory.  Which means in a lot of cases, like you described, you'll be exchanging a lot of numbers.  Now if you construct the data as a linked list, you can perform a replacement like you described, but can be a little tricky to code a sort against.  If you can do it (and I'll have to look at my source, I kind of remember doing something like this, but not sure), you'll need to do your normal sort algorithm, saving the data from it (i.e. a sequence of instructions like "exchange position 5 with 1"), then parsing that data and constructing an optimal path for sorting the data which requires the fewest moves.

 

I'll look and see if I can find something like that in my stuff.

[Ponch]

I'll read most of that (I studied physics few years long time ago but my brain's sharpness is very far from what it was at the time).

The actual commands you have available on that TV set may make one way simpler than another.

The fact I have to navigate through the channel's list to go "fetch" them is a factor. I can "page up/page down" 10 channels at a time in that purpose.

[jaclaz]

 

The fact I have to navigate through the channel's list to go "fetch" them is a factor. I can "page up/page down" 10 channels at a time in that purpose.

Yep, as an example there are a few sets in which (while in the "menu/setup) you can go to a channel (by using the arrow up/arrow down buttons on the remote) and while you are on it you can input directly the number to be assigned to it an press "OK" or "Enter".

 

But here there is a "fork", some will exchange the "current" channel with the one that was on the channel number before (if any) AND keep focus where you are, some will do the same exchange BUT "jump" to the newly entered channel number, some will instead "insert" the current channel at the position you gave (thus shifting all other following ones), etc.

With a 5 channel "random" initial situation of 2 3 5 1 4 when you go to the 4th entry and input 1 as channel to be assigned you can have:

a. 1 3 5 2 4 (and "remain" on the 4th entry, i.e. now  the 2)

b. 1 3 5 2 4 (but get to first entry, i.e. now the 1)

c. 1 2 3 5 4 (and "remain" on the 4th entry, i.e. now  the 5)

d. 1 2 3 5 4 (but get to first entry, i.e. now the 1)

 

jaclaz

[Ponch]

I'll probably do that tomorrow night.

I'm not familiar at all with any of those methods to find out the "Longest Increasing Subsequence".

The existing sequence is this (those should get from 1 to 85);

7,8,9,1,2,49,16,139,140,141,142,143,74,18,81,90,68,69,70,92,14,61,120,3,11,4,5,17,12,13,76,72,73,116,117,10,45,170,44,55,85,121,122,128,82,34,83,59,136,75,151,80,169,84,172,161,35,52,43,164,56,53,54,37,38,71,123,134,138,165,152,15,166,79,167,163,133,36,40,126,144,88,67,517,518

 

I'm sure lots of people here could do that in 3 copy/paste.

[Ponch]

  I tried, I tried. I got dropbox and TurboC (Im on Win7 here), I tried to compile the C bit on that page I linked. It says there is an error (warning). There seems to be a typo on line 30; that "%d" seems to be coming from nowhere but I don't know what it should be replaced with.

#include <stdio.h>#include <stdlib.h> struct node {	int val, len;	struct node *next;}; void lis(int *v, int len){	int i;	struct node *p, *n = calloc(len, sizeof *n);	for (i = 0; i < len; i++)		n[i].val = v[i]; 	for (i = len; i--; ) {		// find longest chain that can follow n[i]		for (p = n + i; p++ < n + len; ) {			if (p->val > n[i].val && p->len >= n[i].len) {				n[i].next = p;				n[i].len = p->len + 1;			}		}	} 	// find longest chain	for (i = 0, p = n; i < len; i++)		if (n[i].len > p->len) p = n + i; 	do printf(" %d", p->val); while ((p = p->next));	putchar('\n'); 	free(n);} int main(void){	int x[] = { 3, 2, 6, 4, 5, 1 };	int y[] = { 7,8,9,1,2,49,16,139,140,141,142,143,74,18,81,90,68,69,70,92,14,61,120,3,11,4,5,17,12,13,76,72,73,116,117,10,45,170,44,55,85,121,122,128,82,34,83,59,136,75,151,80,169,84,172,161,35,52,43,164,56,53,54,37,38,71,123,134,138,165,152,15,166,79,167,163,133,36,40,126,144,88,67,517,518}; 	lis(x, sizeof(x) / sizeof(int));	lis(y, sizeof(y) / sizeof(int));	return 0;}

[jaclaz]

Well, if it's OK for you in Excel, see if the attached fits.

The LIS should be 7 and is made of 37, 38, 71, 123, 134, 138,165.

jaclaz

Ponch_TV.zip

Edited July 10, 2014 by jaclaz

[Ponch]

Thanks. But 7 is not the answer I'm looking for.

LIS does not need to be contiguous (see your links).

I can already see a example of 17;

7, 8, 9, 16,18, 44,55,82, 83; 84, 123, 134, 138, 165, 166, 517, 518

there is most probably more.

Edited July 10, 2014 by Ponch

[jaclaz]

You are right.

Those are contiguous sequences only , my bad

I am pretty sure there must be a way to find also non contiguous sequences.

jaclaz

[Ponch]

I am pretty sure there must be a way to find also non contiguous sequences.

Yes, I listed 37 !

You know what... I think any method will be flawed anyway. The fact I'm ignoring more than half the channels will make the pseudo optimization irrelevant.

If I get it right, the idea is to keep channels that are in the LIS and move the other ones around, which makes sense if you have a place for all channels, but here i'll have more channels to move "out" than channels I want to move forward. Even if ignoring the last 2. (I have digital HD channels, then digital channels for which a part is redondant and a part is crypted, then radios most of which are crypted or for which I don' care then I have analog channels which are all but 2 redondant.

Wish me patience.

[Ponch]

Well, man, man, man.. what a PITA this was. Jaclaz, to take your example in post #5, the situation I faced was not even in your possibilities. The engeneers of Sharp had an other philosphy. In fact moving a channel downwards would come to your "d" example but moving a channel up would just leave an empty slot ! The logic of the TV is that it places the element you select in the place you select and after asking for confirmation, it shifts the channel that was previously there one place up (and on and on). But when you move up, the leaving place is not taken!

For instance if I wanted to switch 1 and 3, If I selected "3" and place it in 1, it would ask me "this place is already taken, do you want top move the channel that's there?" ..Yes please! it would put 3 in 1st place, shift "1" in 2 and shift "2" in 3 (that is free) and stop there. Good !

But if I tried the same thing by selecting "1" and move it to 3,  I'd end up (after confirmation I want to free place 3) with nothing in 1, "2" in 2, old "1" in 3, and old 3 in 4 and so on! Which obviously shifts ALL my channels list with no way of getting them back down! And that got me mad from the 1st minute.   It took me hours!

Still mad after a night of sleep. I'm going to have a coffee now.

[Ponch]

Well, man, man, man.. what a PITA this was. Jaclaz, to take your example in post #5, the situation I faced was not even in your possibilities. The engineers at Sharp had an other philosophy. In fact moving a channel downwards would come to your "d" example but moving a channel up would just leave an empty slot ! The logic of the TV is that it places the element you select in the place you select and after asking for confirmation, it shifts the channel that was previously there one place up (and on and on). But when you move up, the leaving place is not taken!

For instance if I wanted to switch 1 and 3, If I selected "3" and place it in 1, it would ask me "this place is already taken, do you want top move the channel that's there?" ..Yes please! it would put 3 in 1st place, shift "1" in 2 and shift "2" in 3 (that is free) and stop there. Good !

But if I tried the same thing by selecting "1" and move it to 3,  I'd end up (after confirmation I want to free place 3) with nothing in 1, "2" in 2, old "1" in 3, and old 3 in 4 and so on! Which obviously shifts ALL my channels list with no way of getting them back down! And that got me mad from the 1st minute.   It took me hours!

Still mad after a night of sleep. I'm going to have a coffee now.

[jaclaz]

Well, man, man, man.. what a PITA this was. Jaclaz, to take your example in post #5, the situation I faced was not even in your possibilities. The engeneers of Sharp had an other philosphy. In fact moving a channel downwards would come to your "d" example but moving a channel up would just leave an empty slot ! The logic of the TV is that it places the element you select in the place you select and after asking for confirmation, it shifts the channel that was previously there one place up (and on and on). But when you move up, the leaving place is not taken!

Yep, notwithstanding my (our ) total failure at finding a valid "strategy", it would have been anyway most probably made vain by the specific implementation of the "shifting" on that TV.

 

The funny (or actually sad) thing is that most probably your set is one of the "new" ones (meaning something manufactured in the last 5 years or so) that are not anymore "TV sets", but (usually Linux based) computers so, if they provided an access to the actual database where the channels are stored it would have been like a 5 minutes job.

 

http://en.wikipedia.org/wiki/Sharp_Aquos

 

Unlike LG and Samsung (for which there are alternative Linux versions) I beleve noone cared to "hack" the SHARPs.

 

jaclaz