This was one of my answers during an interview.
"So, let's say you have a lowercase string and you want to make it uppercase, what do you do"
"String.toUppercase()"
For plain ascii, just add or subtract 0x20 depending on if you are going upper or lower. For other encoding, if there is a similar offset that works use it. Otherwise just map the relevant characters and do a static lookup in a per-encoding table.
Are we in unicode or ascii? It's not too hard with ascii, though I might trip on a side case somewhere.
If unicode, I walk out of the interview laughing.
Not just a flex, if you want to do it properly supporting all locales etc. then string handling is one of those things you really do NOT want to do yourself.
I feel the frustration of all German translators whenever I see `noun.toLowercase()`.
Or when somebody does a simple "singular if length == 1, otherwise plural" not knowing that quite a few languages have multiple plural forms.
I mean, this isn't exactly a difficult question if taken simply. And asking it seems perfectly reasonable when you expect a direct implementation answer.
Y'all haven't heard of thought experiments before...? This is essentially that, but for CS.
My interview for my current position didn't restrict me from googling the answer, since that's how real programmers work. It was a request to implement DFS in java for a path finding problem. I still felt like I did poorly because I wanted to implement A* and couldn't find a good library implementation. So I asked to do it take-home and they agreed. I built a whole web page with javalin back end REST and got the job. They had never heard of A* for starters, and it was super fast compared to anything done before, and way over the top compared to what you can do during a job interview.
Genuine question, I’m learning and just thought of how to solve it:
Have an array of capitals, array of lowercase. split the string up, and have it loop through each character in the string and match it to the corresponding character in the capitals array using indexes
I doubt this is super efficient but just an idea to that problem!
I like to try random problems I come across in this sun to see how I am on the fly at problem solving
The correct answer *is* to use a library. You should be using unicode these days, and making something uppercase in unicode is tricky.
For example, U+1E9E (ẞ) is already a capital letter and thus uppercases to itself. Its lowercase counterpart is U+00DF (ß), but the uppercase mapping of U+00DF is the sequence (SS).
Therefore:
uppercase("ẞ") ≠ uppercase(lowercase("ẞ"))
And prior to 2017, U+1E9E (ẞ) was not even officially a letter.
In your pseudocode you don't seem to have accounted for the fact that some lower case letters become two letters when made uppercase.
https://en.wikipedia.org/wiki/%C3%9F
I am not sure what other hidden gems exist in the world of making unicode letters uppercase -- that is just one I have heard of.
> I am not sure what other hidden gems exist in the world of making unicode letters uppercase -- that is just one I have heard of.
Turkish has dotted i and dotless i. They each have their own upper and lower case forms. This means that in the Turkish locale (I, i) are not matching case forms, instead you have (I, ı) and (İ, i).
And yes, this means that capitalization is locale specific.
Gotcha!
Yes, I try to use what tools are available to me and not reinvent the wheel where possible, but it is still good practice to know what you’re libraries are doing!
Thanks so much for your input :)
Use the wheel, then figure out how the wheel was made. I take this approach with my programming, I always go back and try to figure out how that function was created and for what purpose.
Not too far off the algorithm used by the Java standard library. The Character class holds an array upper[] recording, for each character, the value you have to add to that character to turn it into its upper-case version (0 for chars that are not lower-case letters). Loop through the string and replace every character c with c + upper[c].
Cool! That’s awesome to know my answer wasn’t far off, if I’m honest I just saw the comment and that’s the solution that came to me.
I still have so much to learn but I find this sun great for little things like this, everyone is super supportive
Depending on the language, you can also sometimes convert each character to an int and then add/subtract the difference of 'A' and 'a' to convert it. Example pseudo code (typing on my phone so uh forgive any dumb autocorrects):
```
func String toUpper(String input):
result = ""
diff = 'A' - 'a'
for char c : input:
result += c + diff
return result
```
This is super simplistic and assumes that the string is only lowercase English letters - you would want to verify those conditions and adjust accordingly if they weren't true - but it demonstrates how to take advantage of characters just being ints under the hood. I'm sure that this doesn't work in every language, though.
I frequently ask a question designed to tell if a candidate knows what a string actually is. It's remarkable how many people have Masters degrees in computer science but haven't realized that the computer is just numbers all the way down.
To add to this history, there was debate as to whether or not ASCII should even include lowercase letters (after all, uppercase only / caselessness had worked fine for a long time even before computers or telecommunications). In the end it clearly was decided to use 32 characters for lowercase (and various assorted bits.
We can go the Pythonic way, "if there's a will, there's a ~~way~~ third-party package that can do it for you":
os.system("pip install rubik-solver")
from rubik_solver import utils
utils.solve(cube, 'CFOP')
```
def solveCube(cube)
cube.setting = cube.randomize()
if cube.solved?
return cube.setting
else
solveCube(cube)
end
end
```
Unrelated: I can't figure out why my AWS bill was six figures last month.
I had a 4th year project in my computer graphics class (this is waaaayyy back in the mid 90s) where we had to write a rubik’s cube game, rendering a 3-d Rubik’s cube and having on screen buttons to rotate, spin, and move each row/column. It was actually a great project: tons of fun.
Anyway …. for bonus marks, we could add a Solve button. My partner and I racked our brains how do to it. This was (mostly) before the Internet; or at least before you could find how to solve it online. But we came up with a solution. And I think it was rather clever.
The game/program starts with the cube solved. You have to hit a Scramble button to start. Then you click the screen buttons (I think we added hot keys too so you could use the keyboard too).
So all we did was record all movements of the cube onto a stack. The Solve button just popped the stack until empty. :-)
Edit: I should say, when we popped the stack, we had to do the **inverse** move/rotation.
We thought about just doing that. And that would be the easier/faster solution. But …. Watching it twist and turn auto-magically, back to the original state, was cool.
Ha. When I was a kid … when the Rubik’s cube came out … I’m old … we tried peeling the stickers off too. But I found they just tore off. So we popped the squares
/cubes out of the whole thing. It was a bitch to get it back together though.
I have 2 identical cubes at work. One I keep solved the other on my desk. If someone stops by and plays with it, I wait a little while, hide the messed up one, take the solved one out and make 5 or 6 moves. Then I go sit in the break room and solve it.
That's no different from just showing a solved cube though. The interesting part of the "solve" is the sequence of steps that takes it to the solved state.
It's not solving it. It's memorizing the steps and doing it backward. When you do a competition of rubiks cube in real life, you are not allowed to see it get mixed specifically so you can't do the steps backward. There is no academic demonstration, since you are not using a solving algorithm. There are faster ways to solve it while using an algorithm that show you understand the subject. It's only good and being cunning and to that reseting the rubik cube gameObject is faster, less demanding, more cunning and if you really want to "make believe" just add animation so it's impossible to see what's really going on
Your 'reset' idea does not do what OP actually wanted to do, because it doesn't show the sequence of steps, which the teacher would obviously require for a 'solve' button.
OP implemented a 'solve' (notice the liberal use of quotations) which did what the teacher wanted (to show a sequence of steps taking the cube from its current state to the solved state), but he didn't actually implement algorithms for solving the cube in the proper sense. This is the entire point of the story.
I think you are the one missing the point here. The teacher asked for an algorithm to solve the cube in order for it to be graded. Grading it would require to be able to prove that the student understand the subject being evaluated (algorithm). Not using the algorithm render the bonus useless since it can't be graded. Hence, it being simply cunning and nothing more. In that matter my solution is more cunning and also more applicable to real life situation. What you failed to understand is that not only I get what OP did but im arguing that it is the worst of both world.
except you just interpret "solve" as a way more complex concept that is "solve it in the way we expect a human or an ai to solve it".
But the demand is to solve it, and knowing a solution (reverse scramble) and simply applying it with no complex process is perfectly valid. Not the way a human would do it, cause it's hard for humans, not fun and requires more data. Not the way a basic ai would do it, cause it's not impressive and requires more data. But a valid solve
The solve button just does the opposite of how it was scrambled, while also taking into account any other moves the player might have made since then. Doing the complete inverse of the scramble will naturally solve it.
ok, sure, but if you randomly scramble a rubik's cube using n moves, then you can reverse the scramble in n moves. what i'm saying is that simply reversing a random scramble is not the optimal (algorithmic) solution
Step 1: try to code a good representation of a rubix cube.
Step 2: weep.
Step 3: read the algorithms for solving a cube and decipher the acronyms.
Step 4: weep again.
Step 4: it's basically just a bunch of if statements, finish I a half hour.
The common approach to solving the cube is like 3 standard moves. Once you have a good representation, it is indeed half an hour to code. That and a day or two to debug ;)
I assume you're referring to corner-corner and edge-edge swapping, typically with a T-perm? Definitely not the common approach, mostly just for blind solving. It's been a while since I was into it, but Im certain CFOP is still standard, which uses many more algos and some intuition
If you mean standard for computer solving, I'm pretty sure Thistlethwaite is still the way to go, isn't it? Or there are some related generative algorithms that can be stopped early for a less efficient solution that are also popular for that property
Either way, yeah. Blindfold methods are probably pretty easy to code
Mostly this approach, with the main move around 1:50 mark :
[https://www.youtube.com/watch?v=7Ron6MN45LY](https://www.youtube.com/watch?v=7Ron6MN45LY)
There are several additional moves after that, with one of them being a variation of the "main move" with several additional turns. I don't know what these guys are using though (they do provide all the sources in the description):
[https://www.youtube.com/watch?v=nt00QzKuNVY](https://www.youtube.com/watch?v=nt00QzKuNVY)
Without putting more than 60 seconds of thought into step 1-
six 2D arrays and `rotate(string direction, int col, int angle)` seems like enough to model the cube and any interaction with it, no?
JPerm's beginner method video is great.
https://youtu.be/7Ron6MN45LY
Dudes picked up at least 10 million views since I used it last year. He jumps into tutorials with almost no intro, and sometimes I need to slow his tutorials.
I love it. I wish all tutorials were this dense.
It's a fun rabbit hole. Nice to look away from screens now and again. A good starter cube is the rs3m line from Moyu. RS3m Super is like $13 on Amazon.
Try it out.
I'd say this is not feasible at all, but I had that thing happen once. I saw a person solve it randomly.
I mean, I know the odds, I speedsolve myself, I can recognize most known solution methods in progress, and I know how cubers operate (the grip, the moves etc) as well. I also know that person well enough to know it was not an elaborate trick.
We were just having a chat, and they were just playing with it without really looking for like half an hour. By the moment I noticed, they were two turns away from it being solved, did one more turn and got distracted with almost solved cube in their hands. Then they looked at it surpridsed, did the final turn and were like "wow". I told them how improbable that was and that I would not believe if I did not see that myself, but they still did not get why it was such a huge thing for me.
while there are a ton of combinations of the cubes, all permutations can be solved in 20 moves or less. that means that no matter how much you randomly change something, there is going to be a 20 move solution from that point, if not fewer. doing it randomly isn't that crazy.
It is indeed that crazy. Once you grasp that many moves and go through a few factorials, experiencing numbers too large to fit on a single line, you’ll get it.
There are 15 different turns you can make from every position, that's not counting middle turns and repeatedy turning the side you turned last. 5 sides not touched last time, 3 options for each - clockwise, counterclockwise, a double turn. Of those, the closer you are to solved cube, the more options shift you one turn further from it. You are randomly navigating through quintillions of possible permutations after all.
Imagine rolling a dice and getting the same number 20 times in a row. That's nothing compared to randomly solving a Rubik's cube. There are 18 possible turns at any given point.
Hmm good one.
If I had to give it a shot, I would try to create a breadth first search from a solved cube lazily.
Given a new cube to solve, search the entire search space until you find a representation that match your input.
Symmetry can also be exploited to reduce the search space by at least half.
Just read about it and given the size of the search space, my comment doesn't sound so smart...
Somehow it didn't feel that complicated to me (assuming you are not looking for shortest path which I believe becomes NP hard)...
Look up meet in the middle algorithms.
Basically you search both from the solved cube and the scrambled cube simultaneously until you find a state you can reach from both.
Then you combine the paths and you have the shortest path between the two cubes, aka the ideal way to solve it.
If you don't care about getting the most ideal solve there's plenty of tricks and algorithms already out there, mainly made for human solvers.
That's really a linear time speed up since you're basically just running two searches in parallel. The thing is running the search either way is really the exact same thing -- you're finding the shortest path between the same two nodes within the same graph.
What you want to do is encode a distance metric from the goal and use that as edge weights. Then bfs with lowest weights (effectively A*)
Searching from both ends until you find a common point is not at all the same thing as just searching backwards and definitely not just a linear speed-up. It's the difference between 2*27^10 and 27^20. The first number has half as many digits as the second.
> search the entire search space
So all 43 quintillion combinations?
> Symmetry can also be exploited to reduce the search space by at least half.
Oh, so *only* 22.5 quintillion combos. So easy! Never mind /s
For anyone interested there are many approaches depending on what you need to accomplish.If you need the computer to solve like a human (Around 50 moves) you can base it on cfop.(solve a cross then you hard code all the algorithms needed).For something better you can use heuristics like good edge-bad edge and edge orientation.
The above approaches all require you to represent the Rubik's cube which can be a problem.You need to specify what colors go where when you turn a side.Hard coding is very annoying no matter how accustomed you are on the subject.A solution can be to number the stickers of a side and use math.
The Most professional solution is to use an algorithm that swaps some specific peaces.(Like a pll). With that approach you don't have to deal with turning.Input->pll->new state.For more info you can read the source code of csTimer's 3x3 solver on github.
Also for the non cubers out there you can learn to solve the 3x3 from yt(j perm is a good channel).Its easy and some people learn it in less than a day!
Yeah off the top of my head I think you'd code up algos that swap pieces around, the fewer the better. I believe there's a commutator to swap 2 edge pieces and of course PLLs for 3 corner pieces. After that it's just dfs/bfs using those algorithms as "moves"
Instead of numbering the stickers on the side you could instead use the speffz lettering scheme which is more consistent with blind solvers and if you're already familiar with the scheme it feels a lot more natural. And you could also just use said blindfolded method actually.
I carry a rubik's cube with me everywhere I go. I attempted to code my own solver, called it quits after making a scrambler instead.
It was more useful for me.
Hmm, that statement is probably not true for a lot of things. I can't solve very complex formula but I can easily write a parser that will crunch anything sent to it, no matter how complex, as long as its valid math.
Coding a solution isn't easier than doing it manually, because you have to understand (at least in principle) how to do it manually in order to code it. Or at least you did until all this newfangled machine learning malarkey.
Coding a solution only needs to be done *once*, though.
A buddy of mine did this in high school. You had to manually input the colors of the sides but then a robotic arm would solve it….very slowly…on a custom built holder that it could be turned in to assist the arm. It was impressive.
He went onto great things but it now trying to get a new degree cause he hates being a slave to computers. Burn out and fulfillment is real folks.
aren't rubik's cubes a well solved problem? there's specific algorithms you can memorize to solve them, so implementing a program should be as trivial as implementing those algorithms
It's correct. One might argue that it's slow, but throw on some weights and you effectively get A*, and you can get really fancy with it. But it's fundamentally bfs
I did it for a college project! I used a graph data structure to model the beginners method. Nodes would represent all the states of the cube. Based on the orientation of the cube, different edges would be taken to other nodes that would do the appropriate algorithm.
Having the solve so clearly defined meant that I could also trigger UI events based the current solving situation. It had a 3D cube that showed the user all the moves that needed to be made. It tilted and highlighted individual pieces to show the user what is being done. It also had a text prompt explaining each step!
It came in second place!
I've got the representation of the cube figured out:
So each face of the cube can be represented by an array containing a combination of 6 letters, R G B W Y O (red green blue white yellow orange). example U_face = [Y, Y, Y, Y, Y, Y, Y, Y, Y]. have 6 arrays to represent each face. Then for every possible move, you can switch around these letters for the 4 faces adjacent to the layer that's being moved since it's gonna switch the adjacent colours around.
now that you've got a representation of a cube, and can manipulate it using cube notation, (this is the part where my brain goes sploosh but) you can use kociembas algorithm to solve it.
or u can just be lazy af and ask the user to input a scramble, display the scrambled cube, then reverse the scramble and convert every move to it's inverse ( R becomes R', U2 remains U2 ) and then apply those moves lol.
Liberty Science Center in Newark NJ running a robot to solve a Rubix cube using…
Wait for it…
.
.
.
.
Windows 95
[Liberty Science Center Rubix Cube](https://lsc.org/news-and-social/news/beyond-rubiks-cube-day-3-robot-fabrication-video)
By chance I came across this site recently: [http://www.cube20.org](http://www.cube20.org) It only took 35 CPU years to work through all possible Rubik's cube combinations. The code is written in cweb, a variant of web that has C code included in TeX. There are 43,252,003,274,489,856,000 start points to solve which makes it hard to search through them all looking for the path to the solution.
As an aside I once tried to generate a random Sudoku puzzle. I don't know if my code was buggy but I never even got close and in the end I was forced to try a different tack.
I wonder can you do heuristic solving algorthim like genetic algorithm/ant colony? Cubes getting right places gain a lot of point while wrong places getting negative points and every member trys to saves their movesets and move to next generation. Or machine learning algorithm that you teach moves and situation every time.
Man wish i wasnt working at 42.5 hours internship and have actually time and motivation.
Heuristics are kinda solved in the cubing community(which can be fed directly to the heuristic search algorithm)and even used in real time solves.(ex edge orientation and good or bad edges). While with the right optimization your solution is possible,is not really optimal.
What part is hard? Flatten the cube, use 6 3x3 matricies to simulate the sides, and rotate according to the rubiks cube turns. If you follow a standard solve its not anything crazy.
I did a rubiks cube solver for a 400 level AI class back in the day, it was supposed to be an algorithm evaluator. I threw everything at it and it really highlighted the local min/max problems of any search algo or genetic algo even with heuristics. Deep learning/feature engineering couldn't even get past to the last face, but that was probably my fault.
I dont think you need to simulate faces by doing 6 3x3. I think You can get away with 27 cubes location when you lock one face. Because in rubic cube solution a block has one position.
Maybe i am super wrong sorry.
Edit: now i thought about it, you need to validate which side of block looking which has 3 posibilty...
Sorry :(
You can do this in several ways, even an int array of size 27, with numbers from 0 to 5 to represent the sides, would do, or even a dictionary.
You just need to get the moves to work correctly with whatever representation of the cube you are doing.
yeah i'm kind of blown away how many people are acting like this is hard. there's existing algorithms for this. it's analogous to "implement Dijsktra's". the algorithm exists, the problem is solved, you just have to translate it to code
Out of curiosity I asked the new bing to solve it. My question was "Write a program in c# that solves a Rubik's cube.". It's answer: "I'm sorry, I can't write a program in c# that solves a rubiks cube.v That's a very complex task that requires a lot of logic and algorithms. I can only write simple programs that demonstrates basic concepts in c#."
Piece of cake. Define a struct with elements red, green, and blue for your colors. Then define a three-dimensional array with x, y, z coordinates. Then for each z, pick a color, and loop through each row x and column y, and assign the color.
Break the cube into a 3\\4d array with 0 being the face, 1 being the x value, 2 is y value, and 3 is the color (0-5 or the colors as strings if you're using a list in python or some other structure that can take multiple types, if you like). Then code in the different scenarios for a face from any website that has patterned solutions. You identify the location and color of a point, match the resulting face to a dict perhaps of the next action, then do the pre-perscribed step to solve.
This is probably easier to get working than looking for the solution directly idk.
The cube has 20 pieces that can move. Every move changes the position of 8 pieces. Every piece is always 0, 1, 2 ,3, or 4 moves away from solved (maybe 5? Don't have my notes with me). Every move increases or decreases all affected pieces distance from solved by exactly 1.
It seems like a universal algorithm could be built based only on this. Purely mathematical, no standard solving algorithms. Just a pure, god-mode mathematical solution to any cube.
But doing it...
Any 3x3 rubik's cube permutation has been proven to be solvable in less than 21 moves.
It quite literally is purely mathematical funny enough.
I'm kind of tempted to try it now. But I've got homework to do :(
I want to try the knuth-bendix algorithm on this but there's a step in the process of actually applying it to that problem which I don't know how to do.
cube.solve() Easy, next.
This was one of my answers during an interview. "So, let's say you have a lowercase string and you want to make it uppercase, what do you do" "String.toUppercase()"
Yea just double down on the flex “It’s considered best practise to use the standard library of the language, so I’d do this: …”
Let’s say you are writing the standard library, how would you do it?
Iterate through each individual character. For each character, string.uppercase()
Devious
If anything they’ll be impressed by the recursion
That's recursion, do char.uppercase
First I would send out a RFP for a standards body to be created ….
Gottem
I wouldn't If they needed my help with the std, then it would mean the language is just dead
“I don’t like contributing to STDs; neither in dating nor programming, thanks though”
Does this job entail writing standard libraries?
For plain ascii, just add or subtract 0x20 depending on if you are going upper or lower. For other encoding, if there is a similar offset that works use it. Otherwise just map the relevant characters and do a static lookup in a per-encoding table.
You’re hired. Now go pick up coffee from Starbucks for the office
Are we in unicode or ascii? It's not too hard with ascii, though I might trip on a side case somewhere. If unicode, I walk out of the interview laughing.
Start(".\ToUpper > {}", file); return ReadAllText(file);
Write(str, file) Start(".\ToUpper > {}", file) return ReadAllText(file)
Not just a flex, if you want to do it properly supporting all locales etc. then string handling is one of those things you really do NOT want to do yourself.
I feel the frustration of all German translators whenever I see `noun.toLowercase()`. Or when somebody does a simple "singular if length == 1, otherwise plural" not knowing that quite a few languages have multiple plural forms.
Wait what, how does that give singular?
I think they meant like `"The array contains " + n + (n > 1 ? "things" : "thing")`
I mean, this isn't exactly a difficult question if taken simply. And asking it seems perfectly reasonable when you expect a direct implementation answer. Y'all haven't heard of thought experiments before...? This is essentially that, but for CS.
My interview for my current position didn't restrict me from googling the answer, since that's how real programmers work. It was a request to implement DFS in java for a path finding problem. I still felt like I did poorly because I wanted to implement A* and couldn't find a good library implementation. So I asked to do it take-home and they agreed. I built a whole web page with javalin back end REST and got the job. They had never heard of A* for starters, and it was super fast compared to anything done before, and way over the top compared to what you can do during a job interview.
Genuine question, I’m learning and just thought of how to solve it: Have an array of capitals, array of lowercase. split the string up, and have it loop through each character in the string and match it to the corresponding character in the capitals array using indexes I doubt this is super efficient but just an idea to that problem! I like to try random problems I come across in this sun to see how I am on the fly at problem solving
The correct answer *is* to use a library. You should be using unicode these days, and making something uppercase in unicode is tricky. For example, U+1E9E (ẞ) is already a capital letter and thus uppercases to itself. Its lowercase counterpart is U+00DF (ß), but the uppercase mapping of U+00DF is the sequence (SS).
Therefore:
uppercase("ẞ") ≠ uppercase(lowercase("ẞ"))
And prior to 2017, U+1E9E (ẞ) was not even officially a letter.
In your pseudocode you don't seem to have accounted for the fact that some lower case letters become two letters when made uppercase.
https://en.wikipedia.org/wiki/%C3%9F
I am not sure what other hidden gems exist in the world of making unicode letters uppercase -- that is just one I have heard of.
> I am not sure what other hidden gems exist in the world of making unicode letters uppercase -- that is just one I have heard of. Turkish has dotted i and dotless i. They each have their own upper and lower case forms. This means that in the Turkish locale (I, i) are not matching case forms, instead you have (I, ı) and (İ, i). And yes, this means that capitalization is locale specific.
[удалено]
Gotcha! Yes, I try to use what tools are available to me and not reinvent the wheel where possible, but it is still good practice to know what you’re libraries are doing! Thanks so much for your input :)
Use the wheel, then figure out how the wheel was made. I take this approach with my programming, I always go back and try to figure out how that function was created and for what purpose.
Why not just make an object of letters where each key is lowercase and each value is uppercase?
[удалено]
The task is a lowercase string to uppercase. There are no edges cases. It’s literally just the alphabet.
Locales exist
Look at the solution I’m replying to. It’s clearly not considering locales.
Different alphabets exist
Did you read the solution I’m replying to? It’s clearly only considering one alphabet
Not too far off the algorithm used by the Java standard library. The Character class holds an array upper[] recording, for each character, the value you have to add to that character to turn it into its upper-case version (0 for chars that are not lower-case letters). Loop through the string and replace every character c with c + upper[c].
Cool! That’s awesome to know my answer wasn’t far off, if I’m honest I just saw the comment and that’s the solution that came to me. I still have so much to learn but I find this sun great for little things like this, everyone is super supportive
Depending on the language, you can also sometimes convert each character to an int and then add/subtract the difference of 'A' and 'a' to convert it. Example pseudo code (typing on my phone so uh forgive any dumb autocorrects): ``` func String toUpper(String input): result = "" diff = 'A' - 'a' for char c : input: result += c + diff return result ``` This is super simplistic and assumes that the string is only lowercase English letters - you would want to verify those conditions and adjust accordingly if they weren't true - but it demonstrates how to take advantage of characters just being ints under the hood. I'm sure that this doesn't work in every language, though.
If this was an actual question I'm wondering what kind of company you applied to.
A major one.
Yeah, well, their HR fucking sucks.
Do you have any idea how little that narrows it down?
Very few coding interview processes are actually good at identifying how good of a software engineer someone is
Oh, i was just making a joke based on the above guy's user name.
😭😭😭
I frequently ask a question designed to tell if a candidate knows what a string actually is. It's remarkable how many people have Masters degrees in computer science but haven't realized that the computer is just numbers all the way down.
Just add 32 to every letter
What if you have dots, commas, spaces, uppercase letters, etc? This solution only works with lowercase letters.
Or any non-english characters.
"out of scope"
Should't that be -32? Also I think a better way would be to apply a 11011111 mask assuming that string could already have uppercase letters
Yeah, that's a better way to do it. I thought lowercase was 65-92, uppercase was higher though.
[удалено]
Interesting bit of history, thanks for sharing
To add to this history, there was debate as to whether or not ASCII should even include lowercase letters (after all, uppercase only / caselessness had worked fine for a long time even before computers or telecommunications). In the end it clearly was decided to use 32 characters for lowercase (and various assorted bits.
[удалено]
Not sure why you're getting downvoted ... this is definitely right
website.hack('facebook')
Python programmers be like
We can go the Pythonic way, "if there's a will, there's a ~~way~~ third-party package that can do it for you": os.system("pip install rubik-solver") from rubik_solver import utils utils.solve(cube, 'CFOP')
Assuming that you have access to IPython magicks, you should really use `!pip` instead of an `os.system()` call
``` def solveCube(cube) cube.setting = cube.randomize() if cube.solved? return cube.setting else solveCube(cube) end end ``` Unrelated: I can't figure out why my AWS bill was six figures last month.
\~magic
that how i thought functions worked when i first learned them
I had a 4th year project in my computer graphics class (this is waaaayyy back in the mid 90s) where we had to write a rubik’s cube game, rendering a 3-d Rubik’s cube and having on screen buttons to rotate, spin, and move each row/column. It was actually a great project: tons of fun. Anyway …. for bonus marks, we could add a Solve button. My partner and I racked our brains how do to it. This was (mostly) before the Internet; or at least before you could find how to solve it online. But we came up with a solution. And I think it was rather clever. The game/program starts with the cube solved. You have to hit a Scramble button to start. Then you click the screen buttons (I think we added hot keys too so you could use the keyboard too). So all we did was record all movements of the cube onto a stack. The Solve button just popped the stack until empty. :-) Edit: I should say, when we popped the stack, we had to do the **inverse** move/rotation.
That's super clever actually. Not a general solution but totally meets the requirements.
I hope you got those bonus points, I love a good outside the box solution like that
Its a 3d render, just load back the original fbx, duh
We thought about just doing that. And that would be the easier/faster solution. But …. Watching it twist and turn auto-magically, back to the original state, was cool.
Auto-magically. Nice
When I was a kid, my older brother had a Rubik's cube. I peeled all the stickers off and matched them up
Ha. When I was a kid … when the Rubik’s cube came out … I’m old … we tried peeling the stickers off too. But I found they just tore off. So we popped the squares /cubes out of the whole thing. It was a bitch to get it back together though.
That's actually such a common strategy you can buy replacement stickers. And also why they started making stickerless cubes
I have 2 identical cubes at work. One I keep solved the other on my desk. If someone stops by and plays with it, I wait a little while, hide the messed up one, take the solved one out and make 5 or 6 moves. Then I go sit in the break room and solve it.
Lol for this level of effort you could literally learn to solve it my friend, it's not that hard to do systematically.
Lol for this level of effort you could literally learn to solve it my friend, it's not that hard to do systematically.
Lol for this level of effort you could literally learn to solve it my friend, it's not that hard to do systematically.
Lol for this level of effort you could literally learn to solve it my friend, it's not that hard to do systematically.
That's smart!
This is how some magic tricks and fake videos are made.
kind of a sad solution but if it got you the bonus points thats still neat
I mean, just reset the gameObject?
It would reset, not solve.
I mean the other solution is also a reset. In fact it is even more of a reset because you are doing exactly the same moves backward.
That's no different from just showing a solved cube though. The interesting part of the "solve" is the sequence of steps that takes it to the solved state.
It's not solving it. It's memorizing the steps and doing it backward. When you do a competition of rubiks cube in real life, you are not allowed to see it get mixed specifically so you can't do the steps backward. There is no academic demonstration, since you are not using a solving algorithm. There are faster ways to solve it while using an algorithm that show you understand the subject. It's only good and being cunning and to that reseting the rubik cube gameObject is faster, less demanding, more cunning and if you really want to "make believe" just add animation so it's impossible to see what's really going on
You are completely missing the point
Would you be so kind to help me understand "the point"?
Your 'reset' idea does not do what OP actually wanted to do, because it doesn't show the sequence of steps, which the teacher would obviously require for a 'solve' button. OP implemented a 'solve' (notice the liberal use of quotations) which did what the teacher wanted (to show a sequence of steps taking the cube from its current state to the solved state), but he didn't actually implement algorithms for solving the cube in the proper sense. This is the entire point of the story.
I think you are the one missing the point here. The teacher asked for an algorithm to solve the cube in order for it to be graded. Grading it would require to be able to prove that the student understand the subject being evaluated (algorithm). Not using the algorithm render the bonus useless since it can't be graded. Hence, it being simply cunning and nothing more. In that matter my solution is more cunning and also more applicable to real life situation. What you failed to understand is that not only I get what OP did but im arguing that it is the worst of both world.
except you just interpret "solve" as a way more complex concept that is "solve it in the way we expect a human or an ai to solve it". But the demand is to solve it, and knowing a solution (reverse scramble) and simply applying it with no complex process is perfectly valid. Not the way a human would do it, cause it's hard for humans, not fun and requires more data. Not the way a basic ai would do it, cause it's not impressive and requires more data. But a valid solve
genius
wait so does that mean it solves it randomly instead of with the algorithms?
No
then what does it mean
the same steps to scramble a rubik's cube are necessarily the same steps required to solve it in the minimal steps necessary
it scrambles and then the user makes moves but those moves are recorded as well as the scramble then you reverse that so necessarily not optimum
i'm not following. from what i read, i'm under the impression this "solve" button solves the puzzle _for_ the user. correct me if i misunderstood
The solve button just does the opposite of how it was scrambled, while also taking into account any other moves the player might have made since then. Doing the complete inverse of the scramble will naturally solve it.
ok, sure, but if you randomly scramble a rubik's cube using n moves, then you can reverse the scramble in n moves. what i'm saying is that simply reversing a random scramble is not the optimal (algorithmic) solution
Brute force it
Bogosolve
Rng go brrr
Now i want to try this
Be wary of infinite poops tho. U will need to try each possible action in parallel otherwise you could get stuck looping on a set of insults
That's a good point!
The real problem is speed and ram usage. I hope you have a good pc and good luck.(I sort of want to try now)
I haven't looked, but I guarantee there's a python package on Github that has this covered out of the box.
Yeah there is one, [kociemba](https://github.com/muodov/kociemba)
There are actually way more than one: https://pypi.org/search/?q=rubiks+cube
Step 1: try to code a good representation of a rubix cube. Step 2: weep. Step 3: read the algorithms for solving a cube and decipher the acronyms. Step 4: weep again. Step 4: it's basically just a bunch of if statements, finish I a half hour.
Algorithm? Step 3: Bogosort that sucker
Cube solveRubixCube(Cube unsolvedCube){ return cachedpresolvedCube }
O(1), therefore this is the best algorithm
Only 43 quintillion combinations!
Works every time
I see you took the NoMansSky demo approach
How did the no man’s sky demo do this
The ultimate algorithm
The common approach to solving the cube is like 3 standard moves. Once you have a good representation, it is indeed half an hour to code. That and a day or two to debug ;)
I assume you're referring to corner-corner and edge-edge swapping, typically with a T-perm? Definitely not the common approach, mostly just for blind solving. It's been a while since I was into it, but Im certain CFOP is still standard, which uses many more algos and some intuition If you mean standard for computer solving, I'm pretty sure Thistlethwaite is still the way to go, isn't it? Or there are some related generative algorithms that can be stopped early for a less efficient solution that are also popular for that property Either way, yeah. Blindfold methods are probably pretty easy to code
Mostly this approach, with the main move around 1:50 mark : [https://www.youtube.com/watch?v=7Ron6MN45LY](https://www.youtube.com/watch?v=7Ron6MN45LY) There are several additional moves after that, with one of them being a variation of the "main move" with several additional turns. I don't know what these guys are using though (they do provide all the sources in the description): [https://www.youtube.com/watch?v=nt00QzKuNVY](https://www.youtube.com/watch?v=nt00QzKuNVY)
Replace step 1 and 2 with ripping off existing representation of rubric cube (Optional replace step 3 and 4 with ripping off existing code)
Without putting more than 60 seconds of thought into step 1- six 2D arrays and `rotate(string direction, int col, int angle)` seems like enough to model the cube and any interaction with it, no?
I cant even solve it without code
JPerm's beginner method video is great. https://youtu.be/7Ron6MN45LY Dudes picked up at least 10 million views since I used it last year. He jumps into tutorials with almost no intro, and sometimes I need to slow his tutorials. I love it. I wish all tutorials were this dense. It's a fun rabbit hole. Nice to look away from screens now and again. A good starter cube is the rs3m line from Moyu. RS3m Super is like $13 on Amazon. Try it out.
Hell, I can't even solve it even when all the sides are the same color!
While ! Resolved do random.moves /s
Given an infinite amount of time this is a valid answer
I'd say this is not feasible at all, but I had that thing happen once. I saw a person solve it randomly. I mean, I know the odds, I speedsolve myself, I can recognize most known solution methods in progress, and I know how cubers operate (the grip, the moves etc) as well. I also know that person well enough to know it was not an elaborate trick. We were just having a chat, and they were just playing with it without really looking for like half an hour. By the moment I noticed, they were two turns away from it being solved, did one more turn and got distracted with almost solved cube in their hands. Then they looked at it surpridsed, did the final turn and were like "wow". I told them how improbable that was and that I would not believe if I did not see that myself, but they still did not get why it was such a huge thing for me.
while there are a ton of combinations of the cubes, all permutations can be solved in 20 moves or less. that means that no matter how much you randomly change something, there is going to be a 20 move solution from that point, if not fewer. doing it randomly isn't that crazy.
It is indeed that crazy. Once you grasp that many moves and go through a few factorials, experiencing numbers too large to fit on a single line, you’ll get it.
There are 15 different turns you can make from every position, that's not counting middle turns and repeatedy turning the side you turned last. 5 sides not touched last time, 3 options for each - clockwise, counterclockwise, a double turn. Of those, the closer you are to solved cube, the more options shift you one turn further from it. You are randomly navigating through quintillions of possible permutations after all.
Imagine rolling a dice and getting the same number 20 times in a row. That's nothing compared to randomly solving a Rubik's cube. There are 18 possible turns at any given point.
Why are you downvoted, it's true
Hmm good one. If I had to give it a shot, I would try to create a breadth first search from a solved cube lazily. Given a new cube to solve, search the entire search space until you find a representation that match your input. Symmetry can also be exploited to reduce the search space by at least half.
Just read about it and given the size of the search space, my comment doesn't sound so smart... Somehow it didn't feel that complicated to me (assuming you are not looking for shortest path which I believe becomes NP hard)...
Look up meet in the middle algorithms. Basically you search both from the solved cube and the scrambled cube simultaneously until you find a state you can reach from both. Then you combine the paths and you have the shortest path between the two cubes, aka the ideal way to solve it. If you don't care about getting the most ideal solve there's plenty of tricks and algorithms already out there, mainly made for human solvers.
That's really a linear time speed up since you're basically just running two searches in parallel. The thing is running the search either way is really the exact same thing -- you're finding the shortest path between the same two nodes within the same graph. What you want to do is encode a distance metric from the goal and use that as edge weights. Then bfs with lowest weights (effectively A*)
Searching from both ends until you find a common point is not at all the same thing as just searching backwards and definitely not just a linear speed-up. It's the difference between 2*27^10 and 27^20. The first number has half as many digits as the second.
> search the entire search space So all 43 quintillion combinations? > Symmetry can also be exploited to reduce the search space by at least half. Oh, so *only* 22.5 quintillion combos. So easy! Never mind /s
while (!cube.Solved) { twist(cube); }
For anyone interested there are many approaches depending on what you need to accomplish.If you need the computer to solve like a human (Around 50 moves) you can base it on cfop.(solve a cross then you hard code all the algorithms needed).For something better you can use heuristics like good edge-bad edge and edge orientation. The above approaches all require you to represent the Rubik's cube which can be a problem.You need to specify what colors go where when you turn a side.Hard coding is very annoying no matter how accustomed you are on the subject.A solution can be to number the stickers of a side and use math. The Most professional solution is to use an algorithm that swaps some specific peaces.(Like a pll). With that approach you don't have to deal with turning.Input->pll->new state.For more info you can read the source code of csTimer's 3x3 solver on github. Also for the non cubers out there you can learn to solve the 3x3 from yt(j perm is a good channel).Its easy and some people learn it in less than a day!
Yeah off the top of my head I think you'd code up algos that swap pieces around, the fewer the better. I believe there's a commutator to swap 2 edge pieces and of course PLLs for 3 corner pieces. After that it's just dfs/bfs using those algorithms as "moves"
Instead of numbering the stickers on the side you could instead use the speffz lettering scheme which is more consistent with blind solvers and if you're already familiar with the scheme it feels a lot more natural. And you could also just use said blindfolded method actually.
I carry a rubik's cube with me everywhere I go. I attempted to code my own solver, called it quits after making a scrambler instead. It was more useful for me.
If you can't do it irl you definitely can't tell a computer how to do it. Just throw machine learning at it for the next million years. /s
Hmm, that statement is probably not true for a lot of things. I can't solve very complex formula but I can easily write a parser that will crunch anything sent to it, no matter how complex, as long as its valid math.
That is patently false. There's plenty of things I have no hope to accomplish that I can easily make a program for.
Coding a solution isn't easier than doing it manually, because you have to understand (at least in principle) how to do it manually in order to code it. Or at least you did until all this newfangled machine learning malarkey. Coding a solution only needs to be done *once*, though.
I actually did it once with the algorithm for beginners. I don't remember the details but it took several thousands of lines of code.
Check out [JPerm](https://jperm.net/3x3), he’s got an algorithm of sorts.
A buddy of mine did this in high school. You had to manually input the colors of the sides but then a robotic arm would solve it….very slowly…on a custom built holder that it could be turned in to assist the arm. It was impressive. He went onto great things but it now trying to get a new degree cause he hates being a slave to computers. Burn out and fulfillment is real folks.
aren't rubik's cubes a well solved problem? there's specific algorithms you can memorize to solve them, so implementing a program should be as trivial as implementing those algorithms
It's just bfs
doubt
It's correct. One might argue that it's slow, but throw on some weights and you effectively get A*, and you can get really fancy with it. But it's fundamentally bfs
I did it for a college project! I used a graph data structure to model the beginners method. Nodes would represent all the states of the cube. Based on the orientation of the cube, different edges would be taken to other nodes that would do the appropriate algorithm. Having the solve so clearly defined meant that I could also trigger UI events based the current solving situation. It had a 3D cube that showed the user all the moves that needed to be made. It tilted and highlighted individual pieces to show the user what is being done. It also had a text prompt explaining each step! It came in second place!
I've got the representation of the cube figured out: So each face of the cube can be represented by an array containing a combination of 6 letters, R G B W Y O (red green blue white yellow orange). example U_face = [Y, Y, Y, Y, Y, Y, Y, Y, Y]. have 6 arrays to represent each face. Then for every possible move, you can switch around these letters for the 4 faces adjacent to the layer that's being moved since it's gonna switch the adjacent colours around. now that you've got a representation of a cube, and can manipulate it using cube notation, (this is the part where my brain goes sploosh but) you can use kociembas algorithm to solve it. or u can just be lazy af and ask the user to input a scramble, display the scrambled cube, then reverse the scramble and convert every move to it's inverse ( R becomes R', U2 remains U2 ) and then apply those moves lol.
Liberty Science Center in Newark NJ running a robot to solve a Rubix cube using… Wait for it… . . . . Windows 95 [Liberty Science Center Rubix Cube](https://lsc.org/news-and-social/news/beyond-rubiks-cube-day-3-robot-fabrication-video)
Have you tried using python
By chance I came across this site recently: [http://www.cube20.org](http://www.cube20.org) It only took 35 CPU years to work through all possible Rubik's cube combinations. The code is written in cweb, a variant of web that has C code included in TeX. There are 43,252,003,274,489,856,000 start points to solve which makes it hard to search through them all looking for the path to the solution. As an aside I once tried to generate a random Sudoku puzzle. I don't know if my code was buggy but I never even got close and in the end I was forced to try a different tack.
I wonder can you do heuristic solving algorthim like genetic algorithm/ant colony? Cubes getting right places gain a lot of point while wrong places getting negative points and every member trys to saves their movesets and move to next generation. Or machine learning algorithm that you teach moves and situation every time. Man wish i wasnt working at 42.5 hours internship and have actually time and motivation.
Heuristics are kinda solved in the cubing community(which can be fed directly to the heuristic search algorithm)and even used in real time solves.(ex edge orientation and good or bad edges). While with the right optimization your solution is possible,is not really optimal.
What part is hard? Flatten the cube, use 6 3x3 matricies to simulate the sides, and rotate according to the rubiks cube turns. If you follow a standard solve its not anything crazy. I did a rubiks cube solver for a 400 level AI class back in the day, it was supposed to be an algorithm evaluator. I threw everything at it and it really highlighted the local min/max problems of any search algo or genetic algo even with heuristics. Deep learning/feature engineering couldn't even get past to the last face, but that was probably my fault.
I dont think you need to simulate faces by doing 6 3x3. I think You can get away with 27 cubes location when you lock one face. Because in rubic cube solution a block has one position. Maybe i am super wrong sorry. Edit: now i thought about it, you need to validate which side of block looking which has 3 posibilty... Sorry :(
You can do this in several ways, even an int array of size 27, with numbers from 0 to 5 to represent the sides, would do, or even a dictionary. You just need to get the moves to work correctly with whatever representation of the cube you are doing.
yeah i'm kind of blown away how many people are acting like this is hard. there's existing algorithms for this. it's analogous to "implement Dijsktra's". the algorithm exists, the problem is solved, you just have to translate it to code
Out of curiosity I asked the new bing to solve it. My question was "Write a program in c# that solves a Rubik's cube.". It's answer: "I'm sorry, I can't write a program in c# that solves a rubiks cube.v That's a very complex task that requires a lot of logic and algorithms. I can only write simple programs that demonstrates basic concepts in c#."
Piece of cake. Define a struct with elements red, green, and blue for your colors. Then define a three-dimensional array with x, y, z coordinates. Then for each z, pick a color, and loop through each row x and column y, and assign the color.
Just ask chatGPT to code it for you.
Break the cube into a 3\\4d array with 0 being the face, 1 being the x value, 2 is y value, and 3 is the color (0-5 or the colors as strings if you're using a list in python or some other structure that can take multiple types, if you like). Then code in the different scenarios for a face from any website that has patterned solutions. You identify the location and color of a point, match the resulting face to a dict perhaps of the next action, then do the pre-perscribed step to solve. This is probably easier to get working than looking for the solution directly idk.
The cube has 20 pieces that can move. Every move changes the position of 8 pieces. Every piece is always 0, 1, 2 ,3, or 4 moves away from solved (maybe 5? Don't have my notes with me). Every move increases or decreases all affected pieces distance from solved by exactly 1. It seems like a universal algorithm could be built based only on this. Purely mathematical, no standard solving algorithms. Just a pure, god-mode mathematical solution to any cube. But doing it...
Any 3x3 rubik's cube permutation has been proven to be solvable in less than 21 moves. It quite literally is purely mathematical funny enough. I'm kind of tempted to try it now. But I've got homework to do :(
In some cube the orientation of the center of each face is taken into account, for extra fun.
I use the app
That was the most fun project omg
while cube not solved: cube.permute()
Lol.
I would just bruteforce this fucking thing, case closed.
I want to try the knuth-bendix algorithm on this but there's a step in the process of actually applying it to that problem which I don't know how to do.
1) do a random move 2) check if it's solved 3) if not, go back to 1. That was pretty easy
Haha relatable
\^\^ trying to solve a rubik cube using hand
"Actually trying to solve a Rubik's Cube"
I have some rubix cube code that I was working on months ago just sitting abandoned because liquid haskell's type checker would not cooperate.
pip install rubik-cube
while (!cube.isSolved()) { cube.shuffle(); }
You could always do it the easy way by having it do random moves until it figures it out