All right. I'd like to welcome our next speaker. Matt's going to be speaking to us today about hiding in plain sight disguising HTTPS traffic with domain fronting. Take it away, Matt. Thank you. Hi, my name is Matt. I'm a software developer. Come here my first time at Defcon. Can everyone hear me up the back? I heard there's some sound issues but lots of thumbs in the air. Thanks very much. Cool. So a lot of us have probably heard about domain fronting. It got to a fair bit of attention recently when signal messenger made some noise when I think Google said, hey, we're going to put an end to this. So there was lots of questions about what is it? There was an academic paper floating around which I don't really understand how to read papers like that. So I asked my friend to help me out and he explained it to me and I sort of figured it out. So I thought let's bring it here and explain it in simple terms to maybe people who don't even necessarily know what TLS is or just have rough understanding. So maybe to some people going to a basic level, that way more people can understand. So hopefully we get the right balance. So what is it? I put on my dictionary writer hat and tried to come up with a dictionary definition and it's abusing an implementation detail of shared infrastructure to disguise the true destination of a HTTPS transaction. So there's a few key words in here. Implementation detail is one big one and shared infrastructure is another. And we'll go into why these parts are important later. And HTTPS. As far as I know there's probably not really any other protocols that share different paths to different things within the same place that connections get terminated at. Domain point is not new. It's been around for quite a while. It didn't do an exhaustive search but it has, this is the oldest thing I could find that uses it. It's some kind of proxy that's written in Python and the code of GitHub, the commit message says abstract host substitution. Maybe that's the old name for it. Cool, so let's look at some of the advantages of domain fronting. Sorry, I messed that up. Sorry, users of domain fronting. I mentioned signal messenger. They primarily use that for bypassing censorship. Lantern seems to do the same. I think that's some kind of a VPN. And then there's meek client which is an obfs proxy for Tor. I presume pretty much everybody here has heard of Tor which is usually used for, you guessed it, bypassing censorship. But also for evading detection. So the obfs proxy there's different plug ins for Tor basically that let you pretend you're different types of traffic. All kinds of interesting ones. I wish I could go into them today but that's a huge rabbit warren. And then malware. They'll be bypassing censorship.  That's also corporation saying no you're not going to Facebook at work. And also evading detection. Malware doesn't want to be going to hey you just got hacked.com. So advantages. Why is it useful? Well it can't be detected without breaking TLS. Someone has to actually perform some kind of a man in the middle attack in order to be able to see that you're doing that. So one potential case here would be if I'm running in a corporate network which doesn't want to invade the privacy of their staff by intercepting their TLS communications I won't be able to tell that this is happening. So maybe a piece of malware could use it to evade my firewall from detecting it. It uses existing infrastructure on the server side. So when I've been playing around with this it's mostly CDNs like cloud fronts and not cloud flare anymore. And not Google cloud anymore either. And it's compatible with anything that can be tunneled over HTTPS. So if you can think of a way of tunneling your traffic over HTTPS you could use domain fronting to send that traffic around. And it's very simple and easy. It sounds complicated but once you realize how simple it is you'll just walk away and go cool I'm going to go do that at home it will take you five minutes. Okay where is it not useful? Bypassing censorship where the TLS is man in the middle. So if I break your TLS session I can see you doing this. I said that before. And it's not useful for hiding web traffic in a normal web browser. You can do it in a normal web browser but each web page you go to is going to load things from all kinds of different places. You need to find suitable domains to hide behind and not every website would have domains that match.  So I'll explain what I mean by front domain a bit later when I go into the demo. And the security is void. The reason for that is you need to basically trust a different certificate to where you're actually talking to. Again we'll see more in the demo. So how does it work? Well let's go back to the days of HTTPS 1.0 and obviously when your web browser was doing you're trying to browse to www.mywebsite.com and you do a DNS look up. Your DNS server returns a server address and you connect to that web server and say hey get me the home page and it returns it. The problem here of course is we needed one IP address per domain we were hosting. So if you wanted to host both websites you needed to have two different IP addresses and some of us couldn't do that or and then we obviously want many millions of websites maybe we would run out of IPv4 even faster than we currently are. So they introduced the host header so basically that just changed this sequence diagram slightly but not at all really. It just added this extra piece of information on the second green arrow here where we just specify hey I want to go to website A or website B that way we could share that IP address across both of them. But it's 2018 and we encrypt web traffic what we're supposed to. So you know we this thing called TLS I guess was its original name sorry SSL was its original name and now known as TLS basically just takes HTTP as it was wraps it in a secure layer that validates you know where you're talking to in some cases it can validate you yourself if you decide to do bi-directional authentication. Am I talking to my bank or am I talking to someone that claims to be my bank? It takes care of that for you and it encrypts the traffic between you and the server as we know. And without changing the protocol so as the application developer it doesn't matter if I'm using HTTP or if I'm doing IMAP or POP or whatever you know TLS was designed to just go over the top. However sorry I'm getting ahead of myself here. So TLS handshake is pretty complicated and I don't understand anything but the first two that's happening there. And it's not relevant for domain fronting. Basically what happens here is your TLS handshake your client says hey I want to talk TLS and then the server goes sure I am your bank. Definitely your bank not someone else. And they do some kind of special packet dance and arrive at some encryption keys that they both agree on. And from there everything gets encrypted. So it's a layer it's hidden from me as the application developer but everything from that point is encrypted and as the application developer it just looks like the same protocol that I came up with in this case HTTP. So forget about all that stuff that I don't know. And we pretend it's not there and just focus on the first couple of messages. Now if I'm sitting on a network watching your traffic okay so maybe I'm at your Starbucks Wi-Fi, maybe I'm your ISP, maybe I'm a government, maybe I'm your sysadmin at your company. I can't see what's happening down the bottom here. That part's encrypted obviously. But what I can see is at these first few messages are unencrypted. The client hello actually has a part at the beginning that says hey I want to go to google.com. And the reason for that is because at the beginning when we look back at our HTTP 1.0 versus HTTP 1.1 is I've totally messed this up. I'm sorry. The reason for this is when I say hey I want to talk TLS the server immediately needs to know who it is representing. So if I have website A and website B both on the same server and my client says hey I want to talk TLS I need to send it back a certificate to say hey I'm website A or website B. So that meant TLS had to be extended slightly to identify which server we're talking about. Am I talking to google.com? Am I talking to yahoo.com? So that got it's a SNI extension so I think when did the Xbox 360 come up? That didn't support it. I just know that if you want to support Xbox 360 it doesn't support this. You need to have one AP per. So that's roughly how long ago it got introduced but it wasn't a standard thing. So say I'm on your network I'm sniffing your traffic and I'm watching you use HTTPS. I can see that you're going to google.com because it's sitting there in that very first message that you send in your TCP session to google. So just to recap that the entire contents of the HTTPS session are encrypted which is all that stuff. For web developers maybe early on, certainly early on in my web development career none of this was clear to me like where all this stuff went it just somehow magically arrived and then you got it from dollar post in PHP somewhere. And then what's not encrypted is the domain name of the server we're talking to that's exposed by SNI. So that's how you're even though you're using HTTPS your ISP can see what you're looking at. And the server certificate also isn't encrypted and I can't remember but I think TLS 1.3 is supposed to encrypt the server certificate. Anyone here? No? No. It does. Thanks. Cool. So let's take a look at HTTPS stacks. So with domain fronting what's important about or what makes it work is the implementation of the HTTPS stacks and how they usually get shared across customers say if you're using Amazon Cloud front. So very simple single server stack like let's say I'm when I was 14 I used to run a web server under my desk which was just Apache and it basically it's this first thing on the left. So sorry first thing on the left is a client and then we got the web server which is like Apache and Gen X IAS whatever and that pulls stuff from an origin and that's generic because the origin can be a file system it could be a Rails application it could be a Django application it doesn't matter. This is just to show the separation of concerns. So you see this web server is responsible for HTTP TLS and caching and when you're running one website it's all pretty simple and yet what we like to do usually for performance reasons though is delegate the TLS. So TLS is reasonably heavy on the CPU and perhaps what you're doing in your application might be very heavy on the memory. So we often we split this out and this is often what's happening at somewhere like Cloud front or Google Cloud where they have lots of customers and they want to have a very fast end point with an IP that lots of customers use that just does the job of terminating those TLS connections and getting them to the next link in the chain which is the next web server that goes and then fetches the content. And so when we're delegated this is where I can steal that little NSA graphic I love. So this is how I think Heroku kind of works is that's a shared infrastructure provider. I haven't tried if domain fronting works for Heroku yet. That's probably something I'll do right after this. But you basically you talk to that reverse proxy whose job is hey let's terminate TLS here and then it goes to something else whose job is look at the host header in the request and routed to whichever one the host header matches. So what happens in the CDN networks often is the reverse proxy decides what certificate to send back to the client based on the SNI header that thing you saw in my Wireshark screenshot and then the next link of the chain decides where to send it based on the host header. Which they don't always have to match and in domain fronting they basically we deliberately make sure they don't match. So if we were to make I'm sorry this is way too small to see on the screen but if we were to make a request to www.good.com and say SNI header hey I want the certificate for good.com then I get my TLS session established and then I say okay get me the home page and the host is www.evil.com and what will end up happening is if that reverse proxy that should satisfy the TLS session then the router would look at the host header and go I want to go to evil.com and this seems to be roughly how it works behind the scenes at Amazon. Unfortunately I don't work there I don't know anyone that does. I wish I would love to know why it works there. So I've already ruined that one. And again remembering what we saw in the wire shark I would only see if I'm sniffing that work I would only see the packets going to www.good.com. Why does it work? An anonymous Google software engineer said it worked because of a quirk of our software stack and Google has since done what they can to get rid of domain fronting. So it highly depends on implementation. In order for it to work the shared infrastructure must not check for a mismatch between SNI header and host header. Apparently that's what Cloudflare does to stop it and it kind of makes sense to do that. And also HDP requests must be routed separately to how TLS, the TLS. So both those layers need to be dealt with separately. So to put it together what do we need to actually do? All we need to do is connect like normal to one host and set the host header to another and they've got to be on the same infrastructure that can route between them. So we find evil.com needs to be accessible via the same infrastructure or something innocent looking. And the infrastructure needs to have the right implementation quirks. So let's say there's plenty of websites on a popular CDN like GQueer is on a CDN. And that same CDN I could go and sign up for myself and put my malware command and control server behind that CDN which would allow me to use somebody else's domain who uses that same CDN to go there. I keep giving away the... So finding them there's loads of websites there. If we go to say Alexa top 500 we should be able to just do reverse DNS lookups to Google.com points to this, whatever. This customer is using Akamai. I think Facebook uses Akamai. Also would be another good one to try. And they're easy enough to find and sign up for. So what makes some domains better than others? It depends really what we're trying to do. If we're evading detection like malware we want to have something that looks pretty business as usual. If I'm in a company that sells apples it probably doesn't look very suspicious if I'm going to fruit.com. Or maybe something innocuous. If I've infiltrated a company and I'm trying to ex-filtrate some data and that company is also a marketing company that uploads a lot to YouTube maybe I could hide my stuff through YouTube.com. If I'm in maybe a country that blocks access to sites which is signals problem is they were in a country which was blocking their messenger and they also apparently block websites. They chose an e-commerce website which they thought would have collateral damage. So if that country were to block that site that would negatively impact that company's country as a whole so perhaps be a reason why that wouldn't get blocked. And then maybe you could do a combination of all. You can find something that looks like business as usual. It's innocuous and it's got collateral damage. Probably a really good one to go with. So I've talked a lot and I'm going to keep talking. But instead of boring slides let's fire up this SSH session and I'm going to try and talk and hold the mic at the same time. One second. All right so what we're going to start with is I have a root shell here and I'm going to start off a TCP dump so you can see the traffic that's actually leaving this machine. So this is just an empty EC2 instance in Amazon. So there should be hopefully no other traffic on 443. So this command here for those not familiar with TCP dump, TCP dump takes network traffic that's going through your network card and logs it somewhere. And I'll just briefly go over the arguments here. Minus C4 means stop after I've seen four packets. And so there's three for the TCP handshake and then the fourth packet is our first message from client to server which is our client hello which has the SNI header in it. Minus A means give me ASCII output, show it straight to the terminal. And it's like a performance optimization like don't do a reverse lookup to the IP address. And I, our interface, F0 and then we're looking for TCP port 443. So let's run that and then switch to another screen. And then we're just going to run a curl to pick some delphotos. It's like a lower Mipsum but for pictures. So curl minus S just means shut up, don't do anything except get that and give me the output to standard out. And then we're going to pipe that to MB5 so we can look at okay what was the content I actually saw. So the content I actually saw in this case or the hash of it is C8EAD. So the purpose of this is just basically go get me this web page, make a hash of it so I've got an idea of what I saw. And then let's get another web page. So in this case, protectyourprivacynow.com. And obviously different hash. So these are the two hashes. And then what we're going to do is take a look at when I do a domain fronting which one I get. So hopefully this makes sense. Now just realize I've messed up my TCP dump. Okay, so only the first curl request got shown up. Only the first curl request got dumped here because it stopped after four packets. So you can see right here this is my SNI header that says hey, I'm going to pick some dot photos. And then let's run the TCP dump again and switch to the other screen and run, I'll just run this curl command here so when I'm going to protectyourprivacynow.com you can see on the other side you've got in the same, roughly the same place I'm going to protectyourprivacynow.com. All right, and it's in my history because I'm testing it out. Cool, so basically let's do some domain fronting and turn over to let's get TCP dump running again. Okay, so all we've done here is we're still establishing our TLS connection with protectyourprivacynow.com. So you can see that most of this curl command is just the same as the one above it. The only difference here is we're telling curl with the minus H flag change the host header to pick some dot photos. And so when I run this, the MD5 sum of what came back is actually pick some dot photos but if I go and look at the other side where I've dumped the packets it actually just shows protectyourprivacynow.com. So when I said it was really easy and you can go and do it in five minutes at home, there it is. So there's a few risks here. Obviously one of them is the reliability. When I try going to protectyourprivacynow.com I don't know that they're going to keep it on that same CDN as pick some dot, pick some dot com, sorry pick some dot photos. They could change that at any time and they could point it somewhere else. So a potential solution to that is you could have a list of backup domains. If you were shipping an app that relied on domain fronting maybe you want to have a list of other ones that still work. But a bigger problem is you can't validate that the server is authentic because if you're connecting to protectyourprivacy.com but then really intending to talk to pick some dot photos the server you validated who you're talking to is protectyourprivacy.com not the photo site that you're trying to go to. And also since you're connecting to that place that you don't, you didn't set up yourself they could change that certificate or CA at any time so you can't pin it either which you'd normally be able to do if it was a self-signed cert or whatever. So also the traffic is visible to the infrastructure provider. So say if you had traffic that you needed to hide from Amazon Cloud front for example or it was sensitive. Because you established your connection with site A that infrastructure provided just by default is able to see what you did. It's kind of obvious if you're used to using a CDN but it's not that obvious sometimes when you do these tricks I guess I forget about all these sort of things. Sensitive data could be stolen and malicious payloads could be injected so basically just treat it as an unencrypted connection encrypt and sign all your messages maybe come up with your own way of validating that you're really talking to who you think you're talking to. Cool. So I actually saw a DOS attack happen via domain fronting it was a combination of some not quite configured correct not quite correctly configured infrastructure and domain fronting. So what happened was we had a very there was a very normal web server set up you know you start with one web server you refactor your application and you make it two web servers and then you you know you eventually end up with a cluster of them and then you end up going okay we need a CDN and so it was put behind a CDN and so they mark the CDN IPs as trusted proxies to the web server as you do because obviously TCP connection hits the CDN endpoint and then the CDN makes another connection and then attackers found a nice slow web page and they decided to make thousands of requests to it but they use domain fronting which in the case of the CDN that was being used and for some reason was going between two different IPs so it was going from one CDN endpoint to another and then to the web server which it didn't expect. So basically the connection diagram would look like this. You client way over to the left connects to reverse proxy that's one TCP connection and the reverse proxy then connects to the web server. So normally because the web server can only see the connection from 2, 2, 2, 2 so for those that can't see the IP addresses they're a bit small. So the web server sees the reverse proxies IP address from that actual TCP so the reverse proxy usually adds into the X4 to 4 header hey I'm forwarding it for <IP_ADDRESS> and the web server knows that because the actual TCP connection comes from 2, 2, 2, 2 that it can trust that <IP_ADDRESS> is really who it's talking to. And that's what I just... So in this case what was happening was the user was hitting the front domain, the domain fronting domain that was being hidden behind that added X4 to <IP_ADDRESS> it got forwarded to the other one which added another X4 to 4 header and then passed it up to the web server who didn't really understand that there could be more than one. So that allowed... That basically opened up an IP spoofing vulnerability because the web server was thinking that the user's true IP was in fact the IP of the CDN endpoint. So what we expect to happen usually is that header has one address which is the true IP of the user or at least that's what the web server was expecting and that the web server reads that header and it knows who it's talking to. In actual fact there was two, it didn't understand it and it assumed that the CDN was the real user. It got worse because we had failed to band config it and it ended up banding the whole CDN and taking the side out because it thought the CDN was dossing it. And the root cause misconfiguration would have forgotten look at the full list and because it went through domain fronting which is a way that it wasn't expected to work it invalidated that assumption. So in order to plug that know your infrastructure. X4 to 4 is actually a de facto standard. Your infrastructure provider might do it differently to how you expect. I think cloud flair has a different cf connecting IP or something is completely different and wherever there's a possibility to get proxied multiple times make sure that the chain is trusted. So if you've got a CDN endpoint that maybe hits another one that hits a load balancer that hits another load balancer it needs to be able to draw a line between all those end points and go okay I trust this one which trusts that one and find its way to the true IP. So in that case NGINX is I don't know the other ones unfortunately but it's real IP recursive if you want to Google that and cloud flair's had a connecting IP. So the future of domain fronting I don't think it'll last much longer. Cloud flair has already said they're getting rid of it. It can't be relied upon. It's implementation details which could change. Like I mentioned before Amazon might just suddenly start doing something differently one day. Netlify, beluga all those CDN providers whatever you use they might find a more efficient way of doing it or decide to get rid of it. Different regions of the world might use different infrastructure. I think I noticed this when I was in China I went to apple.com and I was like I wonder where that's going and I had to look it was completely different to the result I was getting from Perth. It was back in my one place and some other CDN elsewhere. So if you were writing something that needs to be used all over the world they might be pointing to different infrastructure. And it's also actively possible sorry it's possible to actively prevent it from working. Which is cloud flair's deliberately doing this by checking for a mismatch between the SNI and host header. Or by using SNI for routing the request if you remember the several layers of where it decides on its final destination. It could just simply use the SNI header. Which I believe was the intent behind HTTP 2. It seems unwanted Amazon and Google have appeared to have responded to pressure against it. Google's already broken it deliberately. Amazon said they will. And cloud for some reason says it's a risk to their customers. It would put our traditional customers at risk. I presume that means people behind corporate firewalls because those corporate firewalls can't necessarily ban malware traffic if it's using the main fronting. So the main fronting may be not that useful for making your own personal HTTPS private. So a couple more suggestions here. TLS 1.3 has explored the possibility of encrypting the SNI component. It didn't make it into the spec because it required an extra round trip in order to, there was actually two proposals. One was an extra round trip to negotiate a key first. The other one I think was based on a static key. I didn't really pay much attention to it. However I did read recently that there was work done on this by cloud flare I think. And this was only in the last couple of days I think that came out. Use a conventional tunnel like a VPN if you set the tunnel up yourself. Tunnel traffic other ways. There's other protocols out there for achieving this. I've seen some pretty obviously old school malware commander control IRC. A friend of mine tried to do IP of a Facebook messenger. That was pretty horrible. HTTP over XNPP.  But I hope you all walk away from here understanding how SNI facilitates sharing infrastructure that uses TLS. Working around that problem of needing one IP per host. How third parties can see where your HTTPS traffic is going without doing a man in the middle attack. How to find domains and actually do domain fronting yourself. And also how to protect yourself from misconfigurations like what I saw before. Where basically the infrastructure just didn't do what was expected. Thanks for having me. Any questions?


And welcome to the evening stream. I am trying out some new things here. As you may have noticed, everything is different. That's because I'm not at home anymore. I'm, well, I'm home. I'm back home in Iceland. So, stream's gonna be a bit different today. We're gonna do the same content, but we'll be doing it from here. Hey little Annie. My number one fan. I hope the audio is okay. I tried fiddling with it a bit, but, you know, we haven't tried it with this setup. So, might take a couple of sessions to get it working, but it sounded okay to me in the recording. And I hope it'll be good for you on the stream as well. My internet connection isn't quite the same as it is back in Sweden, but, and as you can see, I have no green screen here. But, you know, I hope this will be good. The setup is also gonna be different. This is a Windows computer, but due to company policy, I am not allowed to update it to the latest version. So, I can't run VSL2, the Windows Linux subsystem. So, we're gonna be developing Haskell on Windows. And we're gonna be doing it, we're gonna be compiling and running in PowerShell, which is not quite as nice as, you know, regular bash, but yeah, we're gonna make it work. All right, so what we're gonna do is we're gonna check out day 13, like the latest one. We're gonna see if that one actually, like, does it depend on day 11 or day 12? If it does not, then we're gonna write it, right? But if it does, then we're gonna just start off a day, you know, 11 or 12. And, okay, sweet, so it doesn't. All right, so we'll just jump into day 13 then, and then the plan is later to kind of catch up. We're gonna do a marathon or something like that, you know, just four hours doing 11 and 12, and the six hours doing the current days, I don't know. Maybe next weekend, we'll see. Let's see, start with the problem. Admin of code, I think I'm not logged in here. But let me just do that, do, do, do, sign in. Everything pre-filled, but I have a security key. Make sure you have security keys. All right, we're logged in, safety first, you know? So 14, oh, okay, why is the order is all weird? All right, we're not gonna stop because the order is weird. Let's see, shuttle search. All right, your ferry can make it back, can make it safely to a nearby port. Oh no, wait, did the plane crash? Oh shit, spoiler alert, I think the plane crashed. I mean, we don't know, damn, okay. Okay, book another ship, or did it like, did it, did the plane land on different airport or something, I don't know. All right, we're gonna be finding out, but yeah, to me, this is crazy. All right, also guys and gals, let me know on chat, like if the internet is not, like, if there's something wrong with the setup, because I haven't, I spent, you know, 10 days fine-tuning the other one and now starting all over, wait, let me, I have one more light, better, doesn't change anything, I don't think so. But the setup looks good, this is a mic, this is a road video mic NTG and you can connect it through USB to the, so I don't have a sound card, I don't have a fancy mic, I don't have the fancy headphones, but you know, I think if it looks fine to you all, then that's all that matters, right? Let's see, okay, shuttle bus service is available to bring you from the seat port to the airport, to the, each person's ID number also indicates how often the bus leads for the airport. Bus care is called refined based on timestamp, that measures the number of minutes in some fixed reference point in the past, at time stamp zero, every bus time is only departed from the seat port. After that, each bus travels to the airport, then various other locations, and finally returns to the seat port, okay? The time this loop takes for a particular bus is also its ID number, the bus with ID five, departs from the seat port, time spent zero, five, 10, 15, and so on. 11, okay, so I think we're gonna be doing some modulus probably. Okay, if you are there when the bus departs, you can ride that bus to the airport. Wow, it's a lot of input. Okay, we're gonna have to ride a parser. And I hope, I hope we can use parsec or something.  Let's see, two lines. The first line is your estimate of the earliest time spent you could depart on a bus. Second line lists the bus IDs that are, wait, so. Okay, your notes consist of two lines. Oh, okay, we don't have to parse this input. This is the input, all right, I see. First line is your estimate of the earliest time spent you could depart on a bus. Second line lists the bus IDs that are in service according to the shuttle lamp trees, shuttle company, entries that show X must be out of service, so you decide to ignore them. Your save time once you arrive, your goal is to figure out the earliest bus you can take to the airport. It'll be exactly one such bus. Okay, so we start at 9.39. Hi, are we just gonna be figuring out like what the, yeah, yeah, yeah.  It's on my laptop screen, and then I have a big screen over here. I can't see the chat as well. So speak up, use caps, and I can definitely see it. Nah, I'm kidding. I'll just make this thing bigger here. Wait, hold on. Screen is so small. I have to use all my hard earned CS go. CS go? I never played CS go. Well, hard earned CS 1.3 skills to catch that exact pixel where I have to grab it. Caps lock is cruise control for cool. This guy reads bash.org, right? Sorry, I'm drinking skir. It is an Icelandic drink. Oh, and also my camera doesn't focus now because it's too focused on me. This is the shizzle. Let me actually, let me jump out. I'm gonna grab my coffee.  Since I'm no longer at home, I don't have the Moomin cups, but I do have, oh my God, Star Wars cups. Wow, what an epic cup, Maddy. Yeah, I met my dad's place. He's lent me his place for the duration of my quarantine. Actually, he's pretty nice. One last thing, rats swore. Yeah, I mirrored the camera because I'm looking at you and then I'm looking at the stream and then it's so weird to see me non-mirrored. So if you meet me on the street, my hair will look like this, just so you know. All right, one last thing I wanna point out before I start, look at this t-shirt. What is this t-shirt? It's a woolen t-shirt, hand knit by my grandma. Yeah, that is the most Icelandic you can get in a t-shirt, a hand knit woolen t-shirt. And you know, I just got to represent grandma on stream, you know? Anyway, we have the following notes. 7, 13, 59, 31, 19. The earliest bus you can take to the airport. Okay, so we have these and then I think what we're gonna do is that we're gonna take this number, we're gonna apply a modulus to it of all of these and then that's gonna be our answer. We're gonna take a modulus and then we're going to sort by the modulus. Let's see, which is the idea of the earliest bus you can take the airport multiplied by the number of minutes you'll need to wait for that bus. Let's take the input, let's go. And yeah, like I said, it's gonna be crazy. We're running Windows PowerShell. When I become famous, I'm already famous. I haven't told you guys, I got to recognize that the airport from the stream. That means I'm famous, right? Yeah, no, I was like, it was a very big badge of fun. I'm like, wow. And I was wearing like a mask and a wiser and everything, right? This must be what Justin Bieber feels like, you know? Nah, I'm kidding. I'm kidding. Of course, you learned Haskell on Windows. Yeah, so it works. It works pretty good on Windows except if you're writing like a plugin that's fiddling with the time system, I was doing that. And sometimes it would just randomly crash with some crazy memory exception stuff. Yeah, that was crazy stuff. And the problem with Windows, with running Haskell on Windows, it's not so much the Windows part, it's more that, wow. That is brave. That is so brave. Yeah, I'm using, I'm using like the hard, like I don't guide, I just install, I don't know how I installed it. I don't remember. I just remember that I did to get the IDE working.  And then I haven't used this laptop since March because I've just been home. I've had access to my main machine. And around that time, VSL2 came out and just running when, running Haskell on that is so good. That's just, it's the best programming environment, okay? Having VS code on Windows, SSHing, or like it's connecting directly to the Linux machine. Oh, but I'm not allowed to upgrade. Let's say make dear day 13, see? This is the cool thing about the PowerShell I'm using.  Yeah, and Windows, they do like this. Anyway, this is like, what is this PowerShell? It is PowerShell 6. And the nice thing is that like a lot of these make dear and copy and move and all that stuff, they've like defined that as synonyms.   It's like an object-oriented command line scripting language. So there's a lot of cool stuff you can do with it. But you know, I just spent, you know, eight years studying the power of Bash, right? And not just Bash, but you know, all the new GNU utilities, right? I mean, because I'm using Linux, or as I like to call it, GNU slash Linux. And you know, you know all those utilities and you're kind of crippled by not having those. So they kind of define synonyms for everything. So I can write LS, right? Which is a new Linux utility. And it does what the dear.exe command. Oh wait, it's dear, like yeah. So you don't have to, it's easier to swap around. So I recommend it. As development ironed. All right, let's see. Let's see the into day 13. Let's see if touches define. See, but some of the commands are not defined. So yeah. Oh no. New file. Day 13, not HS. Okay, and we're going to say, test input. I'm doing the dash now. I used to do camel case, now I'm doing the dash. You got to mix it up, you know, it's a little things. We got the test input now. Let's say module main where, wow, you see the lag? Get input, it's going to take a file path and it's going to take a extra string. Get input equals lines.read. We're going to fmap. It needs to be IO, fmap lines.read.file. Main IO, main equals. Oh, thanks for the faro, horrible cow. Yeah, yeah, you're right, conco. But yeah, that's, I think like that was the first stream or something. Oh yeah, wow, thanks for the follow. That was the first stream I did. I had, I was like doing fmap over the input and I was like, what is this, what is it going wrong? And I was doing the right thing. I just, I had forgotten to say IO string. Let's say here, we're going to pipe it into print. And are you ready for this? GAC day 13. We can't do this, because this is PowerShell. We have to do semicolon. Wow, we're getting so many followers. Thank you all for the follows. I really appreciate them. Okay, so we do this and see. Okay, so this is going to compile and it's linking day 13.exe. That's so good, right? Wow, so many new followers. I thought I only had like a very limited watch base, but it's a lot of new people, which is nice. Thank you all. So we compile it and then we do measure command. And we have to do like this. We have to do expression and then like this. And then we say day 13. Yeah, we need more Haskell streamers, right? They're all doing something different. Can you even see this? No, my keyboard is over it, right? I'll run it. Let me see. Let me split this. See this? Measure command expression day 13.exe. Okay, this will run it and measure the runtime, but it will also pipe it to out default. So instead of just running time, run the executable, I have to do all this. But you know, it's something.  Yeah, I know, okay, this didn't work. I have to do dot slash. Okay, now you can see that it compiled, but like the first time it runs, it runs super slow. So it takes us 25 milliseconds to take in the thing and print it. Now, do I have, I have text.parsec, sweet. Let me see. Do I have, do I have, do I have autoparsec, import data.atco. I wanna use autoparsec. Autoparsec is what all cool Haskellers use. Apparently it's like super fast and it has decent error messages. Parsec is not as fast, but has better error messages. And then there's something called byte smash, which is like insanely fast, but it doesn't actually do, I don't know, I have never tried these, but the error messages aren't good enough. But it seems like we don't have autoparsec. So let's just use parsec. All right, now we are trying to compile parsec. Parsec package. Do, do, do, do, do, do, do, do. Mega parsec. Oh yeah, that is also. So you have parsec and you have mega parsec. It was like a discussion. Let me, Twitter, I use Twitter a lot. Mainly to connect, oh no, not the private messages. I use them a lot to kind of communicate with other Haskellers. And I am at treat low on Twitter. And I have a lot of stuff, but, oh my God. Oh my God. Yeah, here. So vibe up, say car. I have no, I'm probably, I don't know how to pronounce his name, but he's a legend. And he said, I said, see, Flavio, also a legend. Twitter legend, Twitter Haskell legend. He says, parsec commentators. I thought we were gonna be using parsec. So why about, it's like, adult parsec, life changing. Flavio says, is it better than mega parsec? And then a cool smiley. If you're dealing with buy strings, yes. It also has backtracking by default. And I'm like, the noob, I'm like, what's wrong with parsec? Too big. And I'm like, I didn't get the joke because adult parsec is like an adult, it's like a unit. It's like smaller parsec. Too big. It's funny. It's a funny joke. And, yeah. So an adult parsec is included with the Haskell platform. So it's good stuff. But if you go to mega parsec, versus, yeah.  That's the joke. But, oh, it's meant by Mark, Mark, MRK, KRP. I think it's Kropov. He's also a legend. So many Haskell legends. You know, that's, I like it. Parsec, Vegas is adult parsec. Yeah, so here's like the, you know, so adult parsec is sometimes faster but not that feature rich. Mega parsec is better for like human readable text. So, yeah. So, but I'm using parsec because it's installed. And, yeah, it's easier that way, right? And like, they all look the same. And also we're not, so, I mean, adult parsec is super fast, right? So if you're running like a graph, so I think that's what Flavio is doing. Like he's running, like he's building a GraphQL server called Move in Haskell, right? And there, you know, you have to parse the query, bam, like that. And you need it, you need it fast.  What? What? Wow. I am followed on Twitter. And I'm apparently a legend. But yeah, there's a lot of cool people in the Haskell community. That's why I like about it. They're all super nice. But none of them are streaming. Can you imagine if Simon and Peyton Jones just started streaming live Haskell development? I would watch that. Okay, let's import data.pecsecparsec.byte string and let's go. So, we're looking at parsec. Do, do, do, do. Some people have been looking at their personal stats in Advent of Code. And I think I have those, yeah, stats. A person, where is the personal stats? Eh, am I, does anyone know? Let me see, one. Cause like someone was looking at like how fast they did stuff. And I mean, that's cool. Yeah, I donated money. But it's not about doing it fast, but it's about having fun, right? Oh, leaderboard, personal stats, right? And apparently it starts counting once you open it. So I started at 12, no, 13, what? Okay, so I have zero score because I am, I'm not competing, right? I start way later. I don't see, I thought like you could see, oh, I think this is like from when it was released. Yeah, yeah, yeah. Okay, yeah, yeah, yeah. That makes sense, right? And we start at five, UTC, right? So anyway, let's look at parsec, not that. Let's see. Looking at parsec, we are going to take, text our parsec by string and we're gonna say parse from file, and then we just give it a file path and it returns an IO, parse error or A. So what do we want? Yeah, so we are going to say get input is not gonna be fmap lines, it's actually gonna be, it's going to be, it's gonna be a parse from file. And then here we say parse input, and then it's gonna take in the file path and what are we trying to get? We are trying to get, so it's going to be a parser. So we're gonna write the parse input is going to return us, it's going to return an integer, which is gonna be the ID and it's going to return us a list of maybe ints. And we're gonna say x is nothing, right? Parse input, okay, this is gonna be a parser. Parse input equals, do, do, do, do, do. Okay, now let's, now we're writing a parser. This is what Haskell is good at. Especially parsing combinators, so cool. Let's see. So we're parsing byte strings and we're gonna write a parser. Do, do, do, do, this is the Harris Heller Lo-Fi Christmas playlist, by the way. So it's got a lot of Christmas stuff in it. So let's say char, no, string, string is not what we want. We want char because it's going to give us, it's gonna give us a string. So we're going to say, first, okay, so do. So first line is going to be, we're going to parse, so we're going to parse, we're gonna parse, we're gonna say take while one, I think. I think that's what we do. Eh, do, do, do, do, do, do, do. Delicious skier drink, yes, Timmy. I'm back home now, I can have access to infinite skier. That moment when the skier hits. Good stuff, let me see. Here is the prim, prim, take while, parser, take while one. Apparently take while one is like, that is, okay, that is an adult parser, but they're apparently super fast. If you just take while one, and let's see. Okay, we're going to import. So that's what you're supposed to do. You're supposed to import text.parsec.char, and then import text.parsec.prim. And so here, we are going to parse digits. So let's see. Eh, do, do, do, do, do, do. So we're gonna parse, we're gonna parse digits until we don't get more digits, right? And then, and then we're going to, let me see, um, do, do, do, do, do, do, do, do, do. So this is, yeah, this is gonna be, okay, so end of line, yes. Letter, digit, text, digit, occupant, digit, char. So we're gonna, let me see. What if I do just a, yeah. Parsec.parsec.f for any care of which, yeah, okay. Let me, let me see, because I don't use, I've never used Parsec. Actually, I always, so tokens. Yes, eh, mm-hmm, mm-hmm, mm-hmm, mm-hmm, mm-hmm. So let's see, eh, many, many one, many one digit. Many one digit, do, digs equals many one digit. So here, and then we have to define this crazy function. Yeah, it's overkill, but it's included by default. Yeah, I mean, you're not wrong, eh, but I think I wanna see what happens. Okay, eh, mm-hmm, mm-hmm, mm-hmm, mm-hmm, mm-hmm. So we're gonna parse digits, many one digits. So we're gonna say import data.char, and what you have to do is you have to, so here, we're gonna write a function that says, you know, string to int. And that is going to be taking a string, and it's gonna return some int, as a string to int equals this crazy function. So you have fold l, so you start with zero, and then you say, you take the digit, and you take in the x, right? What is the, like I've said, even earlier, what is the type of fold l again? I always forget. I mean, yeah, we could use free maybe, but that's not cool, right? Yeah, b, so b, a, b. So it's gonna be the current x and then d, and then we're gonna say 10 times x plus two int to digit, no. Digit to int of d. You see how it works? This, like, takes the number, and then every time you add something new, it multiplies the previous one by 10 and then adds it. It's, mm, this is like, this is taken from, I think, the read implementation or something like that, but it's written by Eric Meyer, this way of doing it, but it works. So what if we just say here, return string to int of digs, comma, and then just an empty list? What does this then show us? Day, day loop, maybe int. And why can't I print this? Because, oh, get input, right. Get data, data? No, what is it? Right, so this is gonna be an either, either. Okay, let's see here. Yeah, this is gonna be an either, parse error, or what? It's complaining. Let's see, what, either parse error, okay, right, parse, yeah, either parse error, maybe, but this is not in scope. What? Where's parser error defined? Import, hiding, I mean, I'm importing everything, but it's just this parse error isn't in scope, parse error, text.parsec.error. Okay, yeah, I think I just, because I didn't import text.parsec, I just imported like everything. Yeah, and I don't need this print thing, okay? Nice, let's print it. I think it's gonna give us a parse error because, yeah, I could have used holes, but like the holes tell us what we should put there, but they don't tell us like what we can import. I think it would give us a parse error because like we didn't parse the entire input, and we'll say like incomplete input. No, see, parse it. Okay, now the rest, we are going to do so timetable is going to be sep by, sep by one, parse tt, okay? And then we're gonna say, what was sep by one do? Do, do, do, do. Sep by, sep by one. Takes a parser. Okay, yeah. So sep by one, this is gonna be, it's gonna be here a char, comma. And the, and the, this is gonna be option, option maybe, of do, do, let's see, let's see here. Let's see, parse number is just gonna be, that's going to be, what is it? It's gonna be string to int over many one, dig it. And this is not fine because ambiguous type variables. So parse number is going to be a parser of a four ints. Okay, so this is gonna be parse option maybe, so many one, so digs. So we're gonna say here ID is a parse number. Then we're going to say skip, skip, we're going to say skip, skip, skip many one. No, yeah, skip many one, many one, and then it's gonna be sep a second. Oh, yeah. I mean, I think I got it working, right? Let's go skip many one, and we're gonna use these do, do, do, do, do, do, end of line, end of line. So we skip the line, and then we separate the option maybe of parse number. So if it can't parse a number, it's just gonna give us a maybe. So time, so here, I know we're gonna say it's gonna be ID comma time table. And this is not okay because sep by one returns a maybe, option maybe. Okay, yeah, sorry. That is true. Sep is second. Listen to chat. Let's see. Do, do, do, do, this is a bit slower because this machine isn't quite as powerful, and it doesn't have a graphics card. So like the rendering of the stream is taking a lot of the CPU. Okay, just seven, just 13 comma nothing. It should be doing more, right? Seven, 13, and then it says nothing, and then it stops after it fails once. That's it, that's it. Not what we wanted, right? Okay, then let's do, let's just do it differently, right? So let's just say choice. The choice is gonna be, so it's going to be, so it's gonna be sep by, okay, and then we're gonna have the char, but this, not gonna be parse number, it's gonna be a choice between just fmapped over parse number, or it's going to be, it's going to be char x into pure, pure nothing. And it says I don't need these parentheses. I don't like that I did, I had to do this though. I thought sep by one would not fail. Anyway, now we have the correct rate. All right, now we got the input. Let's, no, no. Doesn't work. What is the type of, type of that? Well, how do you pronounce it? So I think it doesn't, work. Let's see. I think, yeah, so it takes an A. No, I think it doesn't work. Let me, it should work though. And it says, not in scope. I think that should be in scope, right? It's in control.monad, right? Yeah, I need to separate it again like this. What? Oh yeah, this is the wrong symbol. It's not exported. Why are you telling me that it's, I say now we have this operation and it complains, do I need to say nothing before? What if I apply it here? I don't think it works. So it takes in a functor. So I think the issue is that like this char thing happens in the parsec monad, right? And not in the maybe monad. Let's see. This is the same as doing BS and then pure A. But, so A, BS, yeah. But it's complaining that this whole thing, okay, this is a redundant bracket. Good and bad. I think the issue is, see, it's returning a return on maybe, but it's broken in the monad. The thing you're putting goes first. Okay. Oh, that works, cool. See, we have some Haskell experts in chat. It's all about knowing the symbols. Haskell is like math, right? It's just a game of symbols. Yeah, it looks better, right? Just nothing. Let's highlight the symmetry. Wow. That is nice, right? Good stuff, okay. Now we have the input. I think, yeah, complete overkill, but, you know, that's what we're here for. Okay, let's see a, let's see here. Wait, G. Oh, G. So I'm using Wim keep, I think.  Good stuff. Okay, solution one. It's going to take an int and a list of maybes. Okay, and we are going to return an int. Solution one. Okay, let's see here. We're just going to return. We're not going to return anything. So solution one. Okay, okay, so where? So let's get all the ints. Times is going to be cat maybe of, so this is going to take, you know, our ID. Let's say it's shuttle ID should, should is better. And then times. And it's going to be a times, maybe, and there's going to be times, maybe, and we have to import data up, maybe, cat maybes. Okay, and then we have all the ints. Now we, so now we have like a list of ints. Now I want to do, I want to do a, I want, what I want to do is I want to take the, so I have the times I want to take, so we're going to say next departure is going to be a map ID, SID, and this is going to be, this is going to be mod over times.   And then I'm going to sort that in a map. and we are going to take maximum now we're going to take the minimum of next departure we don't have to sort it but i want to see here so i'm going to say trace show id i don't actually need this one um we don't need data list anymore import debug dot trace let's say let's let's say let's say solution one and this doesn't work because we return either parse error so we're going to say fp do parse uh fp a case parse of if it's a left parse error we're just going to say error if it's a p we're going to say error p show otherwise we're just going to say return a res return res what is case parse of yeah if it's left and we're going to return error let's say here now okay yeah and it's a problem here is that i want to return this like this let's see debug dot trace yeah yeah yeah exactly okay uh one three five four nine eight okay so so it says one so so let's see what is a 939 divided by seven it's 134 so 134 times seven yeah i'm using google as a calculator i mean they have a lot of good people working there right so you should trust their results right uh so yeah 104 times seven is 938 and 1938 plus one is indeed a is indeed 939 so this seems legit let's see uh the seven so okay the only spot you can take is bus id 59 it doesn't depart until sunset 944 what why okay uh so uh let's say here trace show id i think i'm doing something wrong right i'm not supposed to take the max i'm supposed to take the minimum maybe so for 59 it's returning the max it's returning that's the maximum the earliest bus you could take is bus id 59 do we need to flip around the modules oh right so so the problem is okay uh bus seven departs at 938 and that just left one minute ago right a bus 59 944 let me see am i i think i might be doing the modulus like this when do we get then yeah yeah no that's of course yeah yeah this is this is wrong okay okay so i also need to include the id's okay let's see so if i say here div let's say div i like this is some modulus problem right but i think i'm i'm thinking something wrong here okay we map this with the times so we do the division and then we're gonna say we'll go sip with what uh next departure time so we take these and we do sip with we're gonna multiply and then i'm gonna say here times and it doesn't like this a next departure time because the time is wrong yeah yeah yeah it meant it means that the bus left one minute ago oh yeah okay yeah yeah yeah so that is true this is so here so this is how long ago they left right so we're gonna do mod mod and then we're gonna do minus and we are going to say oops so yeah so this is how long until the next bus so yeah so it's the difference uh so now we're going to say okay so we found the next departure time minus we found the right one now we're gonna see like which which one is it right so let's see so here we're gonna map over times we're gonna say you know we're gonna say x we're gonna say x comma sid so x minus sid mod sid mod x isn't there can't i like just take the negative modulus isn't that a thing you know i can just do sid mod period negate i think that i think i can do that let's see let's let's remove this here this is this is what i should be able to do right yeah exactly so we take the negative modulus then we get what we were thinking right so and now we then we take the maximum negative modulus it doesn't work i mean we're getting the minus five here where we were getting five earlier so we just negate twice same as doing the minus thing that's what i was thinking like there's a trick with moduluses but like negative moduluses are a bit weird but they work let's see x over to x comma no now we're gonna say wait we have to know the time right so we had to say what's the idea there especially you can take the r per multiplied by the number of minutes you'll need to wait for that bus okay so this is gonna be we're gonna take the negate here twice okay now let's just say uh let's just say let's do our funny thing minimum minimum by and then we do this function and times this is from data.list allows us to specify minimum by uh all right it takes an ordering minimum by uh do i have to do like on here something like that this is from data.function so i could so i i've done this like sort on data.function on on takes in i think uh i think this is yeah compare on that is correct compare on this function oh yeah now we now we so so we say oops next departure time so this is gonna give us 59 yeah 59 next departure time times uh how many times how much do i have to wait that is going to be next departure time uh times so this is gonna be the sid times uh next departure time times the how long do i have to wait that is sid minus sid uh oops oops uh oh my god i'm pushing the keep pressing the wrong button here like this right yeah sid give a next departure time a i'm doing something wrong this is gonna be 59 how long do i have to wait that is going to be i have to wait a next departure time minus sid oh plus the sid and then we take the negative modules mod negate a next departure time 3186 no that's not correct what is this gonna be try to show Heidi do dum dum dum this is minus five oh okay i should just negate this right this should be correct 295 that's that's the one yeah don't need here don't need here always nice to have hland telling you where you need parenthesis or something something double negate does the same thing yes you gotta negate that stuff okay works for our test input do let's see how does it do on the input i think this one is going to be fine let's see input get the puzzle input oh wow so many x's good thing we have a good at parser huh my wrong compile it and put it linking and then we run again 27 milliseconds 4315 let's see is it gonna be correct oh no we got the first one it only took us an hour but we did write a parser and we did a do a double bunch of double negations right talking about my t-shirt and stuff anyway let's continue part two is going to be harder it's usually like that not always so one goal calling for anyone that can find the earliest time so such as the first bus ID departs at that time and each time we're going to wait a minute for example suppose you have the same list of bus IDs as above an x in the schedule means that there are no constraint on what bus IDs must be part of that time the earliest timestamp called t is such that bus ID 70 parts of time t bus 13 types are okay this is gonna be this is like gonna be some chinese remainder theorem oh shit oh it's gonna be some module stuff i remember i did so much modulus stuff back in the day we're gonna have to look up chinese remainder theorem that's how it's gonna be okay so uh ping ping ping okay let's let's figure it out let's let's just start by looking at our input no this is day 10 day 13 uh let's start by looking at our input but yeah does anyone doubt the benefit of a good education instead of iterating through all the things we're like chinese remainder theorem it's gonna take us as long to look up chinese remainder theorem and learn it but it's gonna give us an o of one answer it's gonna be epic so uh here i'm going to say okay this is gonna be this is gonna be i don't know i'm gonna define i mean it's gonna return us on it but we're just gonna yeah let's see so times maybe and then i'm gonna do sip zero and so on with times maybe so it's gonna give us income blah blah blah integer yeah that is true it's gonna be none no i'm so i'm i i'm gonna do int because advent of code usually works within 32 but okay let's say integer i mean all the chinese remainder iterative theorem stuff works with integer let's just say here uh times add a fs dot of head of times and i'm just gonna do it this way because i want to trace show id so we sip uh with zero and now we filter by a is just dot fst why is this wrong now yes because this is an int no this will return uh could match quite a type int fst and then it's complaining that oh this is supposed to be from just a second right read the bottom of the form oh okay geez this is this is bigger than yeah let's do integers uh let's see filter is just no this is gonna be second this is gonna be isn't it couldn't match expected type no i just i just want to see you know if you did the list correct and what is it complaining about now line 36 oh no longer larl want a we don't care about this anymore now let's let's just run it we're gonna be getting a lot of numbers out although a lot of numbers but let's see your mic is fluffy yeah this is like a or extreme wind like i have i have another one that is just like more regular mic but this is for extreme wind and if you know anything about iceland it's good to have a windshield all right a zero one four six seven yes okay now we want to find x such that is so so x is gonna be a modulo of the first number so it's gonna be a modulo seven and it's gonna be the second one it has to be modulo one of 13 has a modulo four of 59 modulo six to 31 modulo seven of 19 chinese remainder theorem okay uh let's actually let's so we have the times here we're gonna say uh we're gonna say x we're gonna say x comma just x just y two x comma y no because we we don't want to adjust we don't want to adjust stuff if the modulo was one then the bus left one minute ago uh yeah but we want it to be zero right oh minus one yeah okay i think that's correct so let's let's negate that that was what we learned earlier right we didn't want we didn't want we wanted to find the the the the negative one right all right so zero so this is gonna be uh we was minus seven minus 13 minus 59 oh wait we're not negating that we're negating this x here the music stopped i forgot to press replay i'm gonna put my favorite one on this i like this one it's called ice cream in winter it's good stuff so minus one minus four minus six minus seven now chinese remainder theorem yeah so we have a one equals mod n one right so this is exactly what we're trying to solve right x should be zero modulus n one and it should be you know minus one modulus 13 so uh that is the n one and i are pair wise coprime you know i think we can assume oh where's the post can you show it to us can you like a link it we could just look at that instead of the wikipedia article right or does it like include a solution if it includes a solution we don't want it let's see i'm clicking it clicking the link ronal Kirby oh no it came up in the chinese remainder yeah i'll look at this a bit later okay it's just crt yeah yeah so this is what we were talking about we want exactly this i like this cat bezu bolts algorithm all right so we have to do gcd euclid extending bezu chinese remainder theorem two equations okay we're doing all of this stuff i mean this is essentially what we're doing right and put that in here uh what no why can't i oh this is not this issue where like i'm using the beta version of chrome but then the links open and yeah exactly if the if these aren't prime numbers they're gonna be not coprime right so exactly we have bezu lights so let me see a solution of the system of congruences is some from i up to k ai one mi and ni one okay there exist integers so what is the mi and one here let ni be n over ni so the big n here is a what is the big end is that the number that's the number of n right and okay so i want to i want to find this here so the result is going to be the sum of uh so the result here so the result sum of what do they call this a well thanks to any root oh the product of all the moduluses you're taking okay yeah oh okay yeah so let's see let's see because i see a big n is gonna be the the product of a map second of times what is big n i think i might have to convert these two integers actually so eight two integer two two integer easy enough uh well let's just map up to integer here so what's what's the what's the big n here just want to see it's gonna be a big number right we're multiplying so many numbers together well that's not the biggest number actually okay so we map you have a big n okay and then so and then we have to do so like i like this post but it's like it's too close to the solution probably too close to the solution because i could just copy the thing you wrote and solve and it would just essentially be solved right but i want to i want to try it try it out a bit more so okay so we yeah extended Euclidean algorithm okay so we have to so this is the x here is going to be the sum so i'm gonna have so go so it's gonna be it's gonna be sip with three right yeah so we're gonna have the sum of sip sip with three sip with three function of the a and the and the n and the and the wait like n first rate uh sum sum of a a y m i n i okay a sip with n m m and then n of a times m times n put it uh list is not supposed to be like this sum of the sip with takes in three lists uh map the the a the ai's are going to be that's the numbers here right ai mod it's going to be this map of second of times i think and then it's gonna be m's m's and n's m is m is map of second of times right let's see i guess i'm getting a bit confused here right so the the so we're trying to find the x exactly so so x should be should be so it should be the so what is the a one that's so the seven yeah so zero mod seven should be n one right and then so yeah the second one should be minus one mod 13 so the n's are so the n's are going to be map first uh so the n's are going to be map first the map second of times the a's are going to be map map first of times so let's say here it's going to be so we found all the a's we know the a's and the n s and we now we have to compute the m's this reducing to solving initial problem k equations to a similar problem with k minus one equation so yeah that's the basal weight uh the basal basal one i don't know how to pronounce the basalt a identity applies and um so we have to have so that you know we have we're fine we're figuring out so the the sis integers m i and n i such that a okay so then we can figure out m one and m two we can compute them by the extended Euclidean algorithm let's see so we have n one so that's going to be n i and the small n i okay so let's see so the m s so gonna be compute a m s and this is going to take in an n i uh so that so the so the big n i where big n i that's going to be big n divided by n i oh i think i need to do it's going to be deal so we have big n i and then we have n i and then we we we have to find the m one and m two so the big m i so this is going to be big m i big m i and these are going to be map compute m s to the n s right uh big m i is going to be undefined so we have n i here now we only need to find these small n i uh okay a so in addition to the greatest the other yeah which are integers x and y such that okay so so a x plus b y so we find x and y so we we compute the gcd so uh so okay so big m i so i have to say because i can't say m i i think that's going to be like it's going to think it's a data constructor all right uh big m i a m i equals a gcd of gcd n i a big n i right but now we are we sure to have the gcd should be one right okay so let's see let's see okay so two moduli then basso's identity yeah let's just look at that basso's identity is of all in let a be there exists with a great common divisor exists integer x and y such at ax plus by is d okay uh we just need to figure this out let's see if a and b are not both zero and one pair of so basso is covered up acute computer all pairs okay this is a bit rough right let's see so we want this to be one so i have to find out such at the greatest common divisor is is um i'm sorry okay uh let's see here let's let's find out basso's identity algorithm applied to the ones we know big big n i and n i okay where okay so and basso's identity algorithm is going to take an integer and another integer and it's going to return a pair of integers basso's identity algorithm um thanks for the follow live nits uh disciple i bet the live nits disciple likes monads huh am i wrong uh if a and b are not both zero and one pair of basso's code has since has been computed dj using the x then all pairs can present in the form x minus and this is a plus but it like i don't know if you guys see this but on my screen like this plus isn't it like it didn't render the didn't render their uh so let's see a so we are trying to compute x and y so this is going to be this is going to be a and b okay um so it says it might be computed using the extended Euclidean algorithm okay modular integers once you remark the pesovet of coefficient is not needed and this does not need to be computed and it's true we only we we only need the big m i right um let's see s t or more exactly the remainder of division of t by n is a multiplicative inverse of a modular oof i have this book but it's in sweden let's see so to adapt so this we return t okay let's see while nu r is not equal to quotient okay let's just let's just translate this algorithm into what's called chrono-kerby i think you use the integer case here not the modular case but it's only talking about integers right let's see the computation stops okay and oof a and b and this is the extended one right okay that's true i am feeling a bit dizzy that's okay um let's see we're trying to implement this bezu's algorithm we have a solution already because chrono-kerby has it in his blog post but we don't want to use that directly you want to work for this right okay uh so now we so we just need to figure out oh here this shouldn't be integral it should be integer so what are we doing so far we are so we're trying to find so x x comma y such that ax plus myy equals one um that's correct right yeah okay so this is gonna be some euclidean stuff okay it's easy to check whether values yeah yeah okay this implies that the solution brings to the immediate progression by testing the values modulo n just go through okay so the product of moduli this method works well for handwritten computation with the problem moduli or something wait let's see a what did we get here what was the big n let's run it again um oops get data uh it's gonna be undefined let's run it in compile i just want to see what the like the product of the moduli is for for the input let's see uh because it's gonna be a huge number right yeah this is a very big number if i'm gonna get some water it's holding on for a second important to stay hydrated right okay now so we're looking at bezuas in the identity so structure solutions example proof generalization history so we're just trying to figure out uh okay if g is the greatest common divisor for two polynomials a b not plus zero there and there are two polynomials u v such that a u plus b v equals g this the other this is results in the case of polynomials is that there's okay and so the output computes g but we if we we want to fix g so it's that g is one euclidean algorithm that's what we were looking at earlier right now and computes in addition to the greatest common divisor g c d of integers a and b also the coefficients of bezuas and tend to g which are the integers acting wise such that oh let's just see here uh hugo is there an implementation of gcd yes nice gcd uh this laptop is so slow i mean it's not slow it's just doing so much right okay but it's in the preload what said it was in the preload right gci so this returns the greatest common divisor of a and b so let's let's right here let's just see you know what is gcd of big and i and just want to see what this is and then the compute m s and then we're gonna say head of m s trace show id of m s let's see yeah it doesn't but all of them return one nice so yeah so that is exactly okay that's what i was trying to figure out i was like wondering oh she do i do i have to do i have to figure out to change it such that the gcd is one but i i don't have to change that right because we have we've defined we've defined big n i as uh yeah yeah yeah so we multiplied everything and then we divided by we divided by uh so the thing is okay because like big n i is uh uh so big n i is equal to you know n one times n two times n k right and these are all coprime so you know big n i uh big n i right okay this is this is thing this is a trick big n i divided by n i like n i will not be a factor in big n i because all of us all of these ends are coprime so like this will be uh so big n i you know uh so the the greatest common divisor here so n i is not going to be a factor in big n i essentially so so we have this gcd a bar a comma b is one so we just have to find the x and y right and then we can use the grid release this um this g gcd okay uh let's see here finally notice okay and then compute y at the end saving memory auxiliary variables following algorithm this is parallel assignments blah blah blah okay so this is equivalent to similarly this will be following the code ends okay so this is this code but then it's saying that there's something else also why is there why why are there oh sorry why are there two codes here proof section yeah so what i'm just wondering here is why why are there two codes one can solve why if we're given ab x gcd ab that's an optimization above the government's only computer s k sequences okay so let's uh let's define this in haskell okay the pseudocode okay gc a so extended gcd um we're gonna write write like this it's gonna take in an integer and an integer and we're not gonna we're gonna just return a pair of integers let's say integer and extended gcd ab equals extended gcd uh prime so uh of zero and then old s gonna be one and then this is gonna be r b and a where extended gcd prime of s old s uh r and old r equals okay so now we're gonna say while r is not equal to zero do okay so we're just gonna say here uh let's see so x so this is going to be the same x extended gcd prime s old s zero old r equals this is the base case if b equals zero if b is not equal to zero uh okay so case so if b equals zero okay so the gcd of a and b will be one so we don't care about that well let's let's just let's let's just return all of them right uh if b equals zero then it's going to be old s comma uh zero comma old r else it's gonna be all right now let's not do it like this because it's always gonna be old s right what do i think programming will be like yeah it's gonna be awkward there are some very very good scientists working on very uh bezu you know very good programming languages for um for actually what am i trying for quantum computers but but uh we're not quite there yet but i think that's how we're gonna do it where bezu equals you know we're gonna have the good uh yeah that's yeah isn't it like probabilistic programming in some sense uh but it's going to be it's gonna be hard quotient the quotient is just div right well yeah i think it's that's just div no quotient let's just write it directly a quotient times our a quotient of a quotient of hold r minus old s times a else a zero and here the quotient is just div right and i think it's just gonna be div okay and extended so if it's zero then we don't care about the s otherwise we do a loop s old s r okay so the quotient is exactly where q equals uh old r div uh r what is this is equal to is it gonna be a loop it's energy it's a d s prime old so it's going to be s is going to be this and r prime uh you know uh this is going to be be r prime and old and it's gonna be r again q is going to be old r div r uh and we don't have to do this so we just have to say r prime is equal to old r minus q times r s prime equals it's gonna be old s minus q times s right once yeah but so the thing is like i i i did my maths right but we i did it all in Icelandic i'm always like what is quotient and divisor i should i should really read learn all of math in english but yeah okay so old s old r minus old s times a l zero uh okay now let's see what this is right this is gonna be big uh well let's see what is it gonna be it's gonna be old s be a old r equals extended gcd of big n i and n i right so the bezo is never gonna be one the gcd this old r will be one right so we're gonna be looking at old s and bazoua t let's see a trace shoe and let's return i think we returned the b i'm just gonna i just want to see like the trace of what it you do so okay uh what the bees are all zero yeah so these bees are all gonna be zero uh so i guess we are looking for this number here minus six so these i mean the old rs they all turn out to be one right that's exactly what we wanted uh so we're only looking at the old s now that is gonna be the big m i now we're only looking for the old s okay yeah it's just i think this is good okay um we're getting negative results so the sum here is negative is the sum here four yeah that looks weird right so uh let's turn this right okay you should be able to check that a times x plus b times y is equal to one yes because this number for the test input is not at all it's not at all uh this here yeah it's not at all this right okay so we should yeah so it shouldn't be zero right let's see so this should be big n i times a uh so what are the s ss and rs here statement uh okay the s and r is these uh to compute the sk sequence which yields the bees by zoe yeah so we want the by zoe confusion x and then compute y at the end let's see let's i think we should write this code instead because there's something there's something wrong with the with the stuff let's see r s and t i'm just gonna i'm a bit confused with the x yeah x y gcd ab yeah exactly so uh so x y the ab so it's a times old s again uh plus n i times b and then we return all this i think we should be returning the b right but it's always zero so that doesn't work i mean yeah this is just so we get minus one let's see something wrong here right yeah let's let's go to the this one there's something going on here that we're not quite getting this one seems good right okay uh so we the extended ab so okay so we initialize it by it's going to be old r r and then it's going to be old s s and then it's going to be old t t and then we are going to we're going to say so the old r is going to be so it's going to be r r prime s s prime t t prime so we're going to initialize this so old r r is going to be a and b this is going to be old s is going to be one and this is going to be zero and t is going to be zero and one what is it complaining about here okay a extended g so while r is equal to zero so okay if r is zero old r uh zero uh old s uh s old t t okay so this should be old s old t and so the quotients by the gcd the basal so we're actually we're cackling the basal coefficients right so we want the oh sorry about that old s old t and then old r we don't care about the s and t's we don't care about this okay now we are going to apply a t and t prime okay so q is old r divided by r all right s so so yeah we've already done the also r is going to be old r minus q times r r prime uh s prime is going to be old s minus q times s and t prime is going to be old t minus q times t that's in here okay yeah now it actually does something a times b a plus by x equal to one which is exactly what we want so we want to return the b here but now we get minus four three four three one four zero are we sure that we want this to be negative are we sure we want to be negating these axes let's see oh we just get the same except to negate it we want to be returning the e bs right uh let's see two two this is not the right answer right we want one ten sixty eight seven eight one okay so big n i times old s plus n i times b is equal to one and uh and then we found x and y such that let's see we had it here right okay a s and t do we want to return the s and t all right let's see let's go back to the china's remainder theorem let's see okay now let's go back here and let's see here and there exists integers m i and n i such that m i n i plus m e n e m e n i is equal to one so this is big big big n i times old s we want the we want the big n i times big m i plus uh m i so we want big n i here and then we want m i here and this should be one this is gonna be a irrefutable pattern as it's called and what is wrong here yeah big m i it's gonna be wrong no it should be right right so big n i is equal to so so you want to return old s what is old s here we're trying to compute the m i's right and so this is always one so that is you know the result we're getting the right result okay so big n i times big m i am i doing this correctly you multiply it by small and instead of big n that is correct uh that is absolutely correct so let's just say this is going to be sipped with it's going to be m n the wheel is going to be sipping with star and then it's going to be m n s and compute m n s and that is going to be uh this is going to be big m i times big n i let's see we're still getting weird results normalized by taking the yeah by taking the modulus so you want me to do one modulus what is the mod big n right right right right maybe like this a big m i one big big n i think yeah okay okay okay i see this is going to be like this and then giving us the right example what a test in foot okay let me i'm gonna take a quick bathroom break actually yeah i'm gonna run that check right after give me give me three minutes oops let's see let's just let's just let's just go over this just go over this a bit so we have the extended ghc right so this finds a a comma b comma r such that ax times b plus by uh no it finds x comma y for a comma b gives x comma y comma r such as ax plus b y is equal to it's equal to r okay so then let's let's just check it out okay let's just say case of uh okay this is going to be case of x comma y comma r a times x plus y times r uh b times y is equal to r res uh other goes to error invalid gcd because i just want to be making sure that because i i don't think the i think we did the extended gcd here correctly um but i don't think that's the issue okay so we we so this extended gcd is correct okay now let's so we erase this okay okay uh i mean you know we we kind of knew that already now let's look back at the chinese remainder theorem so let n i equals n over n prime breathe the product of all moduli but one as the n i are pairwise co-prime n and i y the best way to put it in there exists integers m i and m e such that m e n e plus m e n e equals one okay so now let's let's find let's find those so we wanted to want a one to be to be we want this to be zero mod n i we want this to be so these are the a's right that's the first so this is trace show uh let's see let's see this is trace show hid okay now we are going to be looking at the times let's see uh i think those are correct right so these are this are a and this is n i okay these are the n n n i's so the big n i uh the big n big n is product of n s yeah okay then m and m i n i's uh m i n i's equals map so this is gonna take in an n and it's gonna give us uh extended gcd of it so the x is going to be so the big n and this is going to be divided divided by n and the other one is going to be n and so the m and i's so let a n a big n i equals this here in extended gcd big n i big n i n comma big n i and then and then and then i'm gonna map this over the ends this is gonna be giving us the the big n i so these will give us the the n i the big m i and the small n i's so let's see here big n i a so it's gonna be this it's gonna be giving us the mi and the ni and the r and big ni comma n let's just return trace show ID at me and I s zero and there's like a parenthesis is missing here trace show to see let's just see what we're looking at big n we're just getting a feel for what we're doing this is a big n and then this is one entry okay so the n here is seven okay and the m the big the big m okay okay so these are all one so that's okay so a so a I and my big and I let's see let's let have this be a comma and I and I and it's gonna be and I and it's gonna be and I this is and it's gonna be times we don't have the ends anymore okay we need the ends okay let's say let big and I in so an extended g it's a ID so it should be giving us we're gonna have an irrefutable pattern okay of a big mi comma mi comma one okay I think we have to have a lead in and we should just have another lead here so by times and then this is gonna be big mi comma mi big ni and I yes and so so we're gonna I want to see here yes so what I want to calculate here is oh my god I want to just calculate big mi times big and I plus mi times and I did and didn't do and there's something wrong in here okay so right so this should be so big mi mi big and I and I as let's have all of this in a big tuple and it's not very clear is it this is this one it starts like this it's gonna be like this and this is all gonna be one big couple we're gonna say a a every a s there's gonna be a times big mi times big and I and this here is supposedly supposed to be the sum of the sipping the it's just gonna be the sum of the map second of a mini ni s incorrect indentation if yeah and then this is a function I mean oh yeah I mean mi and I s and where is it not in scope in here okay me mi and I s okay and let's see okay so this is the the big big mi and the small mi this is a big and I and this is ni okay and then this is the a so and the result of multiplying this with this and this with this is indeed one and then this is zero is that that is correct right this should be zero should it be zero though yeah I mean the the a here is zero so this should be zero now okay we have this the one times this plus this the amount of times this is equal to zero and the a is one so it should be one times big and I times one this is in here but this is a minus a negative number am I supposed to take just the absolute value of this no right no that's not correct because so we've we found this right AI mi and I is equal to AI okay let's see here and that's another center each of the a times big and cb modulo should be a modulo yeah exactly yes so let's check that out okay and now let's look at a big mi this all of this like this this mod mi okay let's just let's just make these in the booleans these are this is equal to one and this should be a true true true true true true true true true true true so it passes the sanity checks it won't be exactly a though but it happens for us to be exactly a right okay so how do we make it normalize oh yeah yeah that is true so how do we how do we normalize the modulus that's the question right so I do yeah exactly so I do I do modulus right no that's not true either no yeah this is just gonna be a right so we had to do mod big and okay thanks for the subscription sir c race and marty I miss marty uh I am way too way too it because it's just it's just not working out right because you know I if I do mod big and I get this number which isn't it's not what we want right so we found an x maybe we're just like not finishing the thing okay so we found an x such that okay let's see we have this okay these are the times so I just want to check okay let x so x is going to be this here right the sum of the map of the mini ns okay and then x res let's see map why does this keep I keep pressing the wrong button mod and so x modulus the number of map of the ns x res so here it says zero four six seven it should be oh yeah that that is the a's right let's see so we have the number and we want the time where the bus leaves one minute from now okay yeah okay that was when we tried push it negate this right but then we get non exhaustive patterns here so and then you know when we get that then we get that the extended gcd is not one this is a this is has come programming language has come we're trying to solve day 13 and we have all these chinese remainder theorems going on you get to negate x but negating x is not gonna I mean so what I'm saying is you know we have okay yeah yeah so so we have these okay let's negate x here right but you know then I get the wrong results so it needs to zero and it's a return one minute from now four minutes from now six minutes from now seven minutes from now yeah yeah so now I'm negated that right but it's still it's still giving me is it wrong yeah four two three one one two two is a is in fact not 10 68 7 8 1 right let's see seven departs press 13 so this would be 0 1 4 6 7 okay it is 0 1 4 6 7 so we have the times right yeah I mean but the the result is not correct right and we found an x such that such that a x mod 7 is 0 we should leave now and then x mod 13 should be minus 1 okay okay so let's see so 0 what if I do here instead of two integer y I do two integer y minus x okay all of this mod is mod begin nice okay but we don't need this it was giving us the same answer right all right we finally got it we got like a big negative number yeah this is because like you know we have the right approach like the chinese remainder theorem but then it's just like you have to make it all because you know modular arithmetic is not my forte so yeah okay so we're calculating this I'm gonna do it like calculate calculate this okay so uh what mini and eyes yeah this is gonna be the some uh some mini and eyes mod begin yeah I really should look up my chinese remainder theorem again right yeah okay so let's say we get the correct result now we don't need the ns right yeah we need the we need a big n didn't do it didn't do it all right let's say apply it to the input let's see what happens big number will it work all right we did it oof this is what happens if you fiddle around with the with the big modular theorem I you know we could have we could have used a crone chrono Kirby's algorithm but yeah and this is correct right so so this was just taken from wikipedia right we just did the gcd we even have some error assertion here which you don't really need um but uh we did the solution and you know this is not a long solution but you know it's there's a lot of tricky stuff here right and have I ever saw the problem like this before I mean not like this but I've had to I've had to use uh chinese remainder theorem for my maths courses so not exactly like this but something similar yeah to me show us your non crt solution it's just iterating and checking if it works right do you just like iterate for the iterate and then you do plus seven every time it's gonna take a while right link it to me please post the link took a while though didn't it huh if you're just joining us we just solved day 13 of haskell of um that drift code and we did we're using the chinese remainder theorem but it did take us a while we took us a while to figure it out and get it right well we did it and uh uh let's see it runs in 28 milliseconds on windows with obs and everything running that's not bad not bad at all now we're waiting for Tim it took my username to post the link to his version because I'd like to see it but I think you know instead of just doing the chinese remainder theorem thing you kind of iterate through the numbers you take plus seven every time right Tim is out of contact right now so let's see big m i yeah but at least we got it working right uh and uh map snd times quite a few lines of code let's open Tim his solution in mine on that is one line uh yeah so you do plus seven every time right or plus the first one yeah every time uh and you check so could you walk could you walk us through the parser is not there does that terminate what what was the first value for you to me for us it's 41 so i think to me solution would uh so pa here is a fold l1 reduced buses so the the id is going to be 41 so it's going to add 41 every time right and then we simply check so we do 41 we find the first one such that that is remaining remainder is zero uh wait wait so bus p pp offset okay so it starts off with zero and then you kind of keep going by multiplying with the with the number you have so far so i guess you kind of find the first time and then you keep going is that is that correct Timmy how long did it how long does it take to run yeah it does doesn't it it kind of first find the first one and then and then you you you find the you keep going right and then you find the so you find if you solve the first case essentially and then you keep going with the solution to the first case in mind that works probably uh works pretty well right to me can we get a runtime can we get a runtime i love that to me though he like created a data type for the bus we just have an int maybe int right that's so cool yeah uh this is crt uh because you like you you find the first solution right and then you use that solution to to keep the iteration going and that's kind of what the chinese remainder theorem is doing here and we have the two modulating we have this solution and then we we kind of keep going see it doesn't solve the initial problem k equations to a similar problem with k minus one equation so entering process when i actually get the solution to your initial problem so so you solve this right you find a one comma two so you kind of merge the first two but uh so you find the first two and then you keep going for the equations and yeah that's a good solution i think it's better than mine mine is more uh minus two abstract i mean i think but this is like kind of very explicitly we're using chinese remainder theorem here so you know we know it's gonna work but yeah but uh yeah but it wasn't really noticeable so so probably just a couple of milliseconds but it's cool all right y'all and i'm gonna leave you for today in three hours which is uh a bit long actually and i'm gonna see if i can go for another walk another coronavirus walk well that coronavirus is just like a quarantine walk you know you're allowed to you go for a walk with someone else you are both wear masks keep two meters apart that's allowed what i'm gonna do if it's not allowed a some icelanders can go ahead and report me there's like a button on a webpage where you can report yeah i'm gonna do it i'm um later this week maybe maybe tomorrow uh not today i was gonna do them today if this solution was dependent on it but uh yeah so if i if i'd finished this in like this in um you know maybe an hour and a half or two then i would have continued but i think it's three hours is quite long already right i'm just uh i'm a bit poofed you know to use the scientific term but also i like that the stream worked out i think uh i hope uh hope the audio was good i think the output was okay i i see that i have like 225 dropped frames in total over over three hours that's not a lot of frames at 60 fps so i think i think that it all worked out fine today anyway thanks for tuning in i'll be back tomorrow at five o'clock utc six o'clock in europe uh noon east coast us and uh thanks for joining and if you're still here you know consider following and uh and then you get a notification when i go live tomorrow it's not bad right of course if you want to subscribe with your amazon prime it would be nice too but we're not in it for subscriptions we need to solve the editor code and help santa and now i'm very curious what has happened to santa so far you know why is he booking the shuttles what happened did the plane crash nobody knows well people already did previous two days no but i don't know so that's what i care about all right thanks for today and uh see you all tomorrow


Helping students to get motivated. In this essay, I am going to talk about how students can be motivated, more specifically, how to encourage shy or reluctant students to participate in class discussions. Anticipated problems. With the possible exception of mental problems such as being a mute, most of the time I find that a student who is unwilling to talk is either not confident in their abilities, or waiting for somebody else to answer the question. Possible solution. What I have found to be a good way of encouraging students to talk who are shy is to teach them the sentence structure or grammar I want them to say before the speaking portion of the class. For example, the second conditional. I will go through the process, how it is hypothetical and the different tenses for the different parts. I will then get them to write a sentence or two, demonstrating that they are comfortable with the grammar. I will remind them that I am there to help with any problems. Whilst they are writing I will walk around the class and read the sentences as they are being formed, but otherwise will keep my input at a minimum. This is the time for the students. However, this will allow me to make sure that the sentences are correct and therefore they should be a lot more confident in their abilities and have fewer problems with speaking. Comfortable environment. My main priority with motivating students is to make sure that they feel comfortable with speaking in class. So when everybody has their sentences, I will ask them to say them out loud one by one. If people look to not be concentrated, I will ask them to give an opinion on the sentence they have just heard. The worst thing when speaking is feeling like nobody is listening to you. When the student I feel has difficulties with speaking says their sentence, I will ask them to follow up questions, ideally those which are related to what they would be asked in the exam, such as and what do you think about holidays to hot countries, do you prefer them to winter holidays? This should then allow them to answer more personally and more openly. If not, I will say my all time favorite word because it always works. Grouping. If as I mentioned the student seems like they would rather sit and wait for somebody else to answer, I would adopt a different strategy. I would probably order them in two groups. This would allow them to work with somebody else and at least communicate with their partner with the objective of achieving a common goal. Later, when we start the speaking part of the class, I will get them to alternate who talks for each bear. Everybody has the opportunity to speak, everybody talks, everybody has to try. Are you ready to begin your teaching career? Take a tough course to get more confident. In total, I think the best thing to do is to try to include everybody in the class discussions and to try and make good use of follow up questions so as to elicit as much of a dialogue as possible, even from the reluctant students. Speak with an ITTT advisor today to put together your personal plan for teaching English abroad. Send us an email or call us tollfree at 1-800-490-0531 to speak with an ITTT advisor today.