

My problem goes something like this. I have a variable of 5 arrays a[5] for storing the 5nodes of a network. The network is randomly formed by the random number generator. I have the time of travel for each paths of the network. All the nodes may not be connected to eachother. The network and the time of travel of each path is as per the user has assigned. Now I have to check the elements of each array and assign the penalty as per the conditions. My main task is to find a network path traveling each node of the network only once such that the node visited is not repeated. Its similar to TSP but the difference is that in TSP has the condition that it is possible to travel from each node to every other node. But for my case the network is pre defined and nodes are not connected to every other nodes in the network.
a) Like if the network stored is 22345 then I find that a[1]=a[2] so I will have to assign the penalty (type 1 )as the network has a path 22 which is not possible as the starting and end of the path is same. At the same time for rest of the paths from node 2 to 3, node 3 to 4, node 4 to 5 I will have to calculate the sum of total time of travel when I finally reach the node 5.
b) Also there is another penalty condition if the path is not a possible path in the network given by user then I will have to assign penaly( type 2) for such kind of condition like if 12435 is a network to be checked. Here I am supposing that all the paths are possible but the path 43 doesn’t exist in the real network provided by the user, So for such cases I will have to calculate the sum of the time of travel for the paths which are possible and also assign the penalty (type 2)
c) There is also a condition that I need the end point of the network as node 5.So in the network generated randomly if the end node is not the node 5 then I will have to assign the penalty (type 3) and at the same time calculated the sum of the rest possible paths. For example the node 35214 here the end node is 4 so I will have to assign the penalty(type 4)
d) Since I am not allowed to visit the same node twice I will have to assign the (penalty type 4) if the network has repeatition of nodes like if the network is 24314. Here the node 4 is occurring twice so I will have to assign the penalty(type 4) and also calculate the sum of the time of travel of the other paths.
Considering all the above penalty conditions I will have to check the network s. I am really not being able to use any logic on how do I start. Need some hint on how do I do it.





Sorry, I see nothing difficult in this problem statement. Or maybe is it just that you never wrote a program ? Or are you asking how to represent the network topology and path costs ?
For a), scan the array and check if two consecutive indexes are the same.
For b), scan the array and check if every pair of indexes are linked in the usersupplied topology (you need some function that will query the topology and tell you if a link exists).
For c), the condition is a[5] != 5.
For d), use a double loop: the outer loop from i=1 to 4, the inner loop for j=i+1 to 5. In the body of the inner loop, test a[i] == a[j].
Accumulating the path costs is also obvious once you have a query function per network link.





Note: I see an interesting "resonance" between this question, and Roger Wright's question below: "A Modelling Question;" which I had not read before I made notes today about this "problem space," to post later on CP, when I got home !
For some reason today, while riding the elevators in a shopping mall that has three sets of two publicuse elevators: in one end of the mall; in the other end of the mall; and in the middle of the mall ...
The idea came to me that it would be an interesting programming challenge (of a type I had never taken on before) to create an elevator use optimization solution: note that I have never studied differential equations, and I am not familiar with queue optimzation algorithms, etc.
Here's how I framed the problem:
1. Given #n sets of elevators, where the number in each set can vary from #1 to #n:
a. defining "set" to mean elevators that are adjacent, and that any button press on a floor that requests an elevator to go up, or down: simultaneously shares that request with every other elevator in its set that is not in use currently: i.e., stopped at one floor with the door closed, and no requests pending (that might be an unrealistic constraint ?).
2. Assuming all elevators serve the same the number of floors:
3. Assuming that the following timestamped data, tagged with a unique ID for each elevator, is generated and sent to a central computer:
a. for every elevator the time it starts moving, and what floor it starts moving from.
b. for every elevator the time it stops moving, after being in motion, and the floor it stops on.
c. on every floor of the building, when someone presses an elevator up, or down, button (from outside the elevator) to request service:
d. data tagged by unique elevator ID containing the time of requestservice button press, and the requested direction, up, or down.
e. inside the elevator: when any floor choice button is pressed: data tagged by unique elevator ID containing the time of floorchoice button press, and the destination floor chosen. So any one moment in time you have a complete list of all floors to be stoppedat by elevator #n.
3. when any elevator starts or stops moving is recorded tagged and timestamped as in the above.
So, imagining we have all this incoming timestamped information, and that some, or all, elevators are in use, some moving up, or down, some stopped.
The problem to be solved:
1. given a new request for service, up, or down, on floor #n of elevator #n:
2. and, given the context of pending requests and states of every other elevator in the set of which elevator #n is contained:
The desired result: to dispatch the elevators most efficiently, so they serve the most number of people in the smallest amount of time.
I'm not looking for "answers" by asking the question here: I am just looking for a few "pointers" to direct my initial study of the type of scheduling optimization this particular example represents.
Frankly, I don't have a clue about how to approach this kind of problem right now (no formal computer science courses for me, unfortunately).
Obviously could make this example much more complex by taking into realworld factors like most requests may originate from the groundfloor before based on some pattern (like, in a hotel: most request originate from the ground and/or checkin floor up to and a certain amount of time past, checkin time).
You could consider recording the exact times of elevator #n's door opening and closing, and figure out that if it's a short enough interval that noone could have gotten on or off, so someone hit the closedoor button immediately for whatever reason.
But all that type of complexity I don't want to even consider until I reach some understanding of basic optimization problems.
thanks, Bill
p.s. A difference I think I see between Roger Wright's simulation problem (if I can even begin to interpret it correctly), and the one I've described here is:
There are "unknowns" (see Roger's response here describing his inability to monitor pumpstates in realtime):[^]) in Roger's complex system of pumps, wells, and flows; while, in the problem described here, there are no similar "unknowns:"
For every elevator #n: its current position; whether it is idle stopped on one floor; or moving up or down to some other floor; and, the number of floors it must stop at before reaching the top or bottom floor depending on which way its moving: is known precisely.
"When it comes to atoms, language can be used only as in poetry. The poet, too, is not nearly so concerned with describing facts as with creating images." Niels Bohr





I've thought about this problem (while waiting for elevators!).
A few random comments: The standard algorithms used by existing elevators seem to be nonoptimal; A cluster of floors where an elevator has been requested will slow down multiple elevators making everyone wait unnecessarily. This is because when the first elevator stops at the first floor in the cluster, the remaining elevators will get bogged down by the next floors in the cluster.
It would be more optimal for a single elevator to handle the cluster, while the others continue down with no delays.
It's hard to optimize for the number of people, because there's no way of knowing exactly how many people are on a particular elevator. We can make a guess, however. When an elevator stops at a requested floor, we can assume at least one person got on. But we don't know how many got off.
Using artificial intelligence may optimize the algorithm better than any "blind" approach, that doesn't take historical use patterns into account.
"Microsoft  Adding unnecessary complexity to your work since 1987!"





Hi Alan, thanks for responding. I've been exceptionally busy and thrown offtrack by some hardware problems in the last week, so have not kept up with this thread.
I think about that's a good point about using some for of of AI technique, or even some form statistical analysis (factor analysis).
If you had a three month data set of all the kinds of data I described above, it would seem you could factorout use patterns: such as heavy traffic from all upper floors, or any floors above coffeeshop level, or groundfloors, or checkout floor, down, in the AM hours, etc.
Near checkin time you'd expect groundfloor to checkin floor (if separate) to be heavy, followed by lots of traffic of people going up to their rooms, and so forth.
Similarly, hotels often have special events at noon, or in the evening involving large numbers of people; it's easy to anticipate when heavy elevatoruse periods related to those events may be ?
And, I wonder if the kind of "fuzzy" algorithms developed by Japanese device makers might be useful here ?
I wonder how long it will be before elevator makers put small videocams with a wideangle lens on each elevator, and from the pictures being fed back into a central dispatching system compouter, roughly estimate the size of the crowd waiting on a particular floor ? Maybe it's already being done ?
best, Bill
"When it comes to atoms, language can be used only as in poetry. The poet, too, is not nearly so concerned with describing facts as with creating images." Niels Bohr





Hello,
I'm a complete newbie to the field of cryptographic algorithms themselves, always having relied on thirdparty libraries and code in the past. Now I'm starting to poke around with them by myself I finally managed to throw together some sort of tiny cryptographic library in VB.NET. However, I'm concerned that... quite frankly... it's a bit rubbish. Sorry about the long code block here:
Imports System.Numerics
Public Class BlumBlumShub
Private _x As BigInteger
Private _p As BigInteger
Private _q As BigInteger
Private _m As BigInteger
Private _pow As New BigInteger(2)
Public Function NextNumber() As BigInteger
_x = BigInteger.ModPow(_x, _pow, _m)
Return _x
End Function
Public Sub New(ByVal seed As BigInteger)
_p = BigInteger.Parse("32416190071")
_q = BigInteger.Parse("32416185031")
_x = seed
_m = BigInteger.Multiply(_p, _q)
End Sub
End Class
Public Class RandomBitStream
Private _b As BlumBlumShub
Public Function ReadByte() As Byte
Dim num As Byte = 0
For i = 1 To 8
num += Math.Pow(i, 2) * If(_b.NextNumber().IsEven, 1, 0)
Next
Return num
End Function
Public Sub New(ByVal seed As BigInteger)
_b = New BlumBlumShub(seed)
End Sub
End Class
Public Class BlumXor
Private _bitSrc As RandomBitStream
Private _key As BigInteger
Public Sub Cipher(ByRef message As Byte())
_bitSrc = New RandomBitStream(_key)
For i = 0 To message.Length  1
message(i) = _bitSrc.ReadByte() Xor message(i)
Next
End Sub
Public Function ByteToStr(ByVal inByte As Byte) As String
Return inByte.ToString().PadLeft(3, "0")
End Function
Public Sub New(ByVal keyStr As String)
Dim encoder As New System.Text.ASCIIEncoding()
Dim keyBytes As Byte() = encoder.GetBytes(keyStr)
_key = BigInteger.Parse(String.Join("", Array.ConvertAll(Of Byte, String)(keyBytes, New System.Converter(Of Byte, String)(AddressOf ByteToStr))))
End Sub
End Class
And that is that. Firstly, I think my implementation of the BlumBlumShub PRNG is off, secondly I'm not entirely sure that I should be using the parity of numbers generated to give me random bits and thirdly I'm not so sure about my use of Xor or how I'm generating a seed integer for the PRNG from a string. I welcome the input and criticism of any cryptographers or mathematicians out there, plus anyone else that can see problems with my code.
SixOfTheClock
A programming language is to a programmer what a fine hat is to one who is fond of fancy garden parties. Just don't try wearing any .NET language on your head. Some of them are sharp.
modified 14Sep12 6:30am.





Hi all,
I am trying to write a windows forms program to communicate to a CNCmachine from the 1980ties.
The machine uses a 6802 microprocessor and communicates with a Desktop computer with a DOS program.
The communication is in ASCII characters and is in the following format:
4 spaces and a 3 digit value and a checksum character or 3 spaces and 4 digits and a checksum character.
So a total of 7 characters and a checksum character.
This is a part of the original message(space represented as  and checksum character bold):
853>1370%248>1204'00117887215625522346#2346#1031#
I already tried some things like adding all decimal ASCII values and MOD against all possible values,
like 853 : 32+32+32+32+56+53+51 MOD some value and add 30 or 31 to make sure result is in the range of printable characters,but no luck.
note that 853 and 248 have the same checksum, also 2346 and 1031.
I hope someone recognizes the checksum algorithm or can help me to find out how the checksum character is calculated.
Thanks,
Groover
0200 A9 23
0202 8D 01 80
0205 00
modified 9Sep12 16:14pm.





Easy,
XOR the 7 ascii values together.
" 853>"
32^32^32^32^56^53^51 = 62 ">"
" 248>"
32^32^32^32^50^52^56 = 62 ">"
" 2346#"
32^32^32^50^51^52^54 = 35 "#"
" 1031#"
32^32^32^49^48^51^49 = 35 "#"
" 1370%"
32^32^32^49^51^55^48 = 37 "%"
" 1024'"
32^32^32^49^48^50^52 = 39 "'"
" 00"
32^32^32^32^32^32^48 = 48 "0"
" 11"
32^32^32^32^32^32^49 = 49 "1"
" 7887"
32^32^32^32^55^56^56 = 55 "7"
" 2156"
32^32^32^32^50^49^53 = 54 "6"
" 2552"
32^32^32^32^50^53^53 = 50 "2"
Alan.





Thank you Alan,
I wrote a function in my program and it works perfect.
Groover,
0200 A9 23
0202 8D 01 80
0205 00





I have a group of points that I need to plot on a graph and calculate the line of best fit(Slope and Intercept) in a programming language.
for example
x 0 1 2 3 4
y 40 41 45 41 47
At the moment I am using and have implemented the Least Squares algorithm
here http://en.wikipedia.org/wiki/Least_squares[^]
I was wondering whether anyone knows of a computationally more efficient algorithm with close to the same accuracy and be able to explain how the algorithm works?
Thanks in advance




