Store Page
TIS-100
All Discussions Screenshots Artwork Broadcasts Videos News Guides Reviews

TIS-100

Store Page
View Stats:
Global Achievements
TIS-100 > General Discussions > Topic Details
jonbrave 27 Dec, 2017 @ 12:19pm
Sorting/Stacks
I think it's time now I reached out... :steamsad:

I have done 24 of the first 25, optimizing as I go. Stuck on "Sequence Sorter".

Done half the second 25 so far, stuck on "Sequence Merger" & "Sequence Mode Calculator". (It's got to the point where I'm looking at "Character Terminal" and thinking: I reckon I can do this without using the stacks at all...)

Do you see a theme? :) These all have 2 stacks, and involve sorting.

Please don't tell me about sort algoritms. I know those perfectly well. It's a different matter squeezing them into about 12 braindead bytes.

I have thought long about these. I see various possibilities: removing things as you go, inserting things as you go, picking out the lowest/highest, keeping things sorted, ...

It seems to me, they all involve some kind of repeatedly moving items from one stack to the other, and back again, doing something as you go. And there just ain't enough darn room in those boxes to do all that, also signalling as you go and putting stack terminators on and what-not.

So I think I ought to reach out now, for my sanity!

Of course I really don't just want to be told how to do them, or to look at a solution. I'd appreciate some tips about how I should be using these two LIFOs, 'coz I think I'm just not getting it....
Last edited by jonbrave; 27 Dec, 2017 @ 12:25pm
< >
Showing 1-15 of 34 comments
Edwin 27 Dec, 2017 @ 3:06pm 
Those are the seriously tricky ones. Keep at it though. The moment when you get it right is what you play Zachtronics games for. I remember tinkering on the sequence sorter and getting it, only to get fouled by the zero length sequence. And then trying to find the space to hack that in. Glorious game. :-)
#1
jonbrave 28 Dec, 2017 @ 1:05am 
I'll keep at it, and may well come post fragments from my proposed solutions to see if I'm doing it right. But from what you say, am I right that I do need to "fit in" something along the lines of a loop which transfers numbers from one stack to another and then back again in preparation for the next "run"?
#2
Edwin 28 Dec, 2017 @ 2:49am 
That's the idea. Usually hinted by having a node sitting right between two stack memory nodes.
#3
cake>pie 30 Dec, 2017 @ 2:24am 
Originally posted by Edwin:
the zero length sequence.
Thanks for the heads up!
(I just got to this level, man it's going to be tricky!)
#4
jonbrave 30 Dec, 2017 @ 2:29am 
@cake>pie
I'm OK on using a 0 terminator on the stacks. But wait till you try to squeeze everything into one box :(
#5
cake>pie 30 Dec, 2017 @ 2:39am 
I know, I already ran out of lines trying to do selection sort >_<;
#6
jonbrave 30 Dec, 2017 @ 2:48am 
@cake
Good, maybe we can help each other, because as I wrote above I can do them all except the ones which involve 2 stacks/sorting.

You have 1 or more boxes connecting one stack to the other. The requirements are slightly different for a box connecting to a stack versus a box in the middle of a pipeline. But essentially it seems to me we need:

1. A loop transferring all numbers in one direction.
2. A loop transferring all numbers back in the opposite direction.
3. Some logic for passing the numbers out of the loop, manipulating them, and passing them back into the loop.

All in one box. Plus, depending where it is, some kind of "signaller" node for knowing when to start/stop (e.g. you mustn't start transferring the numbers before one stack has had all of them pushed to it).

By the time I try to set just this up --- let alone the actual logic for passing numbers in/out of the loop to do insertions/deletions/swaps/whatever you decide to do --- I run out of space, and my brain aches... :(

You?
Last edited by jonbrave; 30 Dec, 2017 @ 2:50am
#7
cake>pie 30 Dec, 2017 @ 6:09am 
Requirements analysis sounds about right, my thoughts exactly there.

Feels like the layout already forces three of the nodes into pretty much fixed roles:
- ingest input
- signalling middleman / dumb pipe
- pass numbers out of / back into loop

My coding approach is a bit different, so I start with inititialization and start signal, and then most of the sorting logic. I run out of space before I can properly handle the stop case, and send a completion signal >_<;

But yeah, that's where my brain goes nope and I have to switch to playing something else for a bit.
#8
jonbrave 30 Dec, 2017 @ 6:53am 
@cake
If you feel like putting up a screenshot of any of your efforts, I'd be interested to take a look?

Like you said, I'm trying to play something else for a while atm.... :)
#9
cake>pie 31 Dec, 2017 @ 12:15pm 
Just solved it with 8 nodes / 95 lines -- should be obvious which node went unused. Did not use stack terminators. An inelegant solution that I can't exactly say I'm proud of, will likely come back to this at some point to try to improve it. But it'll do for now.
#10
jonbrave 31 Dec, 2017 @ 12:24pm 
Damn! :(

Umm, "Did not use stack terminators". Oh! Then I think that must mean you're not using the stacks like I thought we have to. You're not shuffling things from one to the other? You're talking about the "sort" one that's about #23 of the first 25, right?
#11
cake>pie 31 Dec, 2017 @ 12:44pm 
I am shuffling things between stacks. Just without terminators.
And yes, I'm talking about Sequence Sorter.
Last edited by cake>pie; 31 Dec, 2017 @ 6:35pm
#12
jonbrave 31 Dec, 2017 @ 12:49pm 
If you are moving things between stacks, but you don't have a terminator, how do you known when the stack is empty? Unless you can afford to block?? Or, you're not going through every one on the stack? I don't think I'm getting how to use the stacks then.

All without telling me the answer, of course! :)
#13
Edwin 31 Dec, 2017 @ 2:07pm 
I imagine he counts the number of values in the sequence.
#14
cake>pie 31 Dec, 2017 @ 6:35pm 
Yup, dumb counters counting out an O(n^2) algorithm. I also do have one node that blocks on read and will start reading numbers off the stack while it is still being written to.
If you think carefully about these statements it should be possible to narrow down what I did.
#15
< >
Showing 1-15 of 34 comments
Per page: 1530 50

TIS-100 > General Discussions > Topic Details
Date Posted: 27 Dec, 2017 @ 12:19pm
Posts: 34

Discussions Rules and Guidelines